Advent of PBT 2021 - Day 19

Advent of PBT 2021 — Learn how to use property based testing and fast-check through examples

Our algorithm today is: metroRoute.
It comes with the following documentation and prototype:

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;

We already wrote some examples based tests for it:

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);
});

How would you cover it with Property Based Tests?

In order to ease your task we provide you with an already setup CodeSandbox, with examples based tests already written and a possible implementation of the algorithm: https://codesandbox.io/s/advent-of-pbt-day-19-nwpzp?file=/src/index.spec.ts&previewwindow=tests

You wanna see the solution? Here is the set of properties I came with to cover today's algorithm: https://dev.to/dubzzz/advent-of-pbt-2021-day-19-solution-e57

---

Back to "Advent of PBT 2021" to see topics covered during the other days and their solutions.

More about this serie on @ndubien or with the hashtag #AdventOfPBT.