Advent of PBT 2021 - Day 19

export type Track = { from: number; to: number; length: number };

/**
 * Given a map of all the tracks connecting stations of a metro,
 * we want to compute the shortest path (in terms of distance) to
 * reach the destination.
 *
 * @param departure - Id of the station used as departure
 *                    (must be an integer value)
 * @param destination - Id of the station used as destination
 *                      (must be an integer value)
 * @param tracks - List of all the connections between stations
 *                 of the map
 *
 * @returns
 * The list of tracks to take to go from departure to destination and
 * resulting into the shortest path (if there is one).
 * If there is no path going to the destination, then it returns
 * undefined.
 */
declare function metroRoute(
  departure: number,
  destination: number,
  tracks: Track[]
): Track[] | undefined;

it("should find the only route leading from 1 to 5", () => {
  // Arrange
  const tracks: Track[] = [
    { from: 1, to: 2, length: 2 },
    { from: 2, to: 3, length: 3 },
    { from: 3, to: 4, length: 8 },
    { from: 4, to: 5, length: 1 }
  ];

  // Act
  const route = metroRoute(1, 5, tracks);

  // Assert
  expect(route).toEqual([tracks[0], tracks[1], tracks[2], tracks[3]]);
});

it("should find the shortest route leading from 1 to 5", () => {
  // Arrange
  const tracks: Track[] = [
    { from: 1, to: 2, length: 2 },
    { from: 2, to: 3, length: 3 },
    { from: 3, to: 4, length: 8 },
    { from: 4, to: 5, length: 1 },
    { from: 1, to: 5, length: 100 },
    { from: 3, to: 4, length: 1 }
  ];

  // Act
  const route = metroRoute(1, 5, tracks);

  // Assert
  expect(route).toEqual([tracks[0], tracks[1], tracks[5], tracks[3]]);
});

it("should not consider going backward on the route from 1 to 5", () => {
  // Arrange
  const tracks: Track[] = [
    { from: 1, to: 2, length: 2 },
    { from: 2, to: 3, length: 3 },
    { from: 3, to: 4, length: 8 },
    { from: 4, to: 5, length: 1 }
  ];

  // Act
  const route = metroRoute(5, 1, tracks);

  // Assert
  expect(route).toBe(undefined);
});