DEV Community

Nicolas DUBIEN
Nicolas DUBIEN

Posted on • Updated on

Advent of PBT 2021 - Day 19 - Solution

Our algorithm was: metroRoute.
Go to the subject itself for more details

CodeSandbox with a possible set of properties you may have come with: https://codesandbox.io/s/advent-of-pbt-day-19-solution-t470u?file=/src/index.spec.ts&previewwindow=tests


As for many of the properties we have defined so far in this Advent calendar, the idea will be to build some inputs we know a lot about. In other words we will not build fully random ones that would possibly require us to re-implement part of the logic.

For this algorithm we will need two main builders:

  • one for maps of metro with known connections between two stations
  • one for maps of the metro with a clear absence of path between two stations

For the first of the two the idea is to generate two entities:

  • a route of stations: first station will be the departure, last one will be the destination and the route itself is one of the known set of tracks to go from departure to destination
  • a set of other tracks: possibly including some that will be used to go more quickly from departure to destination

Written with fast-check:

function orientedGraphArbitrary() {
  return fc
    .record({
      // tracks that will compose the known path (starting at node=0)
      knownPathExcludingStart: fc.set(
        fc.record({ node: fc.integer({ min: 1 }), length: fc.nat() }),
        { compare: (na, nb) => na.node === nb.node }
      ),
      // some more tracks that will compose our graph
      extraTracks: fc.array(
        fc.record({ from: fc.nat(), to: fc.nat(), length: fc.nat() })
      )
    })
    .chain(({ knownPathExcludingStart, extraTracks }) => {
      const departure = 0;
      const knownPath = [
        departure,
        ...knownPathExcludingStart.map((n) => n.node)
      ];
      const knownPathTracks = knownPathExcludingStart.map((n, index) => ({
        from: index !== 0 ? knownPathExcludingStart[index - 1].node : departure,
        to: n.node,
        length: n.length
      }));
      const allTracks = [...knownPathTracks, ...extraTracks];
      return fc.record({
        knownPath: fc.constant(knownPath),
        knownPathTracks: fc.constant(knownPathTracks),
        tracks: fc.shuffledSubarray(allTracks, { minLength: allTracks.length })
      });
    });
}
Enter fullscreen mode Exit fullscreen mode

Our second builder will be responsible to build maps not having routes leading from departure to destination. In order to do so we will generate the following entries:

  • a set of tracks going from stations in [0, 9] to stations in [0, 9]
  • a set of tracks going from stations in [10, 19] to stations in [10, 19]
  • a set of tracks going from stations in [10, 19] to stations in [0, 9]
  • departure will be 0
  • destination will be 19

So we have no route going from departure to destination.

Written with fast-check:

function orientedGraphNoWayArbitrary() {
  return fc
    .record({
      // We consider start = 0 and end = 19.
      // We delimit two zones:
      // - start zone contains stations 0 to 9 (included)
      // - end zone contains stations 10 to 19 (included)
      tracksStartZone: fc.array(
        fc.record({
          from: fc.integer({ min: 0, max: 9 }),
          to: fc.integer({ min: 0, max: 9 }),
          length: fc.nat()
        })
      ),
      tracksEndZone: fc.array(
        fc.record({
          from: fc.integer({ min: 10, max: 19 }),
          to: fc.integer({ min: 10, max: 19 }),
          length: fc.nat()
        })
      ),
      tracksEndToStart: fc.array(
        fc.record({
          from: fc.integer({ min: 10, max: 19 }),
          to: fc.integer({ min: 0, max: 9 }),
          length: fc.nat()
        })
      )
    })
    .map((config) => ({
      departure: 0,
      destination: 19,
      tracks: [
        ...config.tracksStartZone,
        ...config.tracksEndZone,
        ...config.tracksEndToStart
      ]
    }));
}
Enter fullscreen mode Exit fullscreen mode

Property 1: should build a path starting by the requested departure whenever a path from start to end exists

for map of the metro and two stations "departure" and "destination" known to be connected by at least one oriented set of tracks
it should find a path with the first track starting at departure

Written with fast-check:

it("should build a path starting by the requested departure whenever a path from start to end exists", () => {
  fc.assert(
    fc.property(orientedGraphArbitrary(), ({ knownPath, tracks }) => {
      // Arrange
      const departure = knownPath[0];
      const destination = knownPath[knownPath.length - 1];

      // Act
      const shortestPath = metroRoute(departure, destination, tracks);

      // Assert
      if (departure === destination) expect(shortestPath).toEqual([]);
      else expect(shortestPath![0].from).toBe(departure);
    })
  );
});
Enter fullscreen mode Exit fullscreen mode

Property 2: should build a path ending by the requested destination whenever a path from start to end exists

for map of the metro and two stations "departure" and "destination" known to be connected by at least one oriented set of tracks
it should find a path with the end track ending at destination

Written with fast-check:

it("should build a path ending by the requested destination whenever a path from start to end exists", () => {
  fc.assert(
    fc.property(orientedGraphArbitrary(), ({ knownPath, tracks }) => {
      // Arrange
      const departure = knownPath[0];
      const destination = knownPath[knownPath.length - 1];

      // Act
      const shortestPath = metroRoute(departure, destination, tracks);

      // Assert
      if (departure === destination) expect(shortestPath).toEqual([]);
      else expect(shortestPath![shortestPath!.length - 1].to).toBe(destination);
    })
  );
});
Enter fullscreen mode Exit fullscreen mode

Property 3: should build an ordered path of tracks whenever a path from start to end exists

for map of the metro and two stations "departure" and "destination" known to be connected by at least one oriented set of tracks
it should find a path with the start of each track connected to the end of the previous one

Written with fast-check:

it("should build an ordered path of tracks whenever a path from start to end exists", () => {
  fc.assert(
    fc.property(orientedGraphArbitrary(), ({ knownPath, tracks }) => {
      // Arrange
      const departure = knownPath[0];
      const destination = knownPath[knownPath.length - 1];

      // Act
      const shortestPath = metroRoute(departure, destination, tracks);

      // Assert
      for (let index = 1; index < shortestPath!.length; ++index) {
        expect(shortestPath![index].from).toBe(shortestPath![index - 1].to);
      }
    })
  );
});
Enter fullscreen mode Exit fullscreen mode

Property 4: should build a path of tracks being a subset of the tracks of the graph whenever a path from start to end exists

for map of the metro and two stations "departure" and "destination" known to be connected by at least one oriented set of tracks
it should find a path with only tracks declared in the set of tracks

Written with fast-check:

it("should build a path of tracks being a subset of the tracks of the graph whenever a path from start to end exists", () => {
  fc.assert(
    fc.property(orientedGraphArbitrary(), ({ knownPath, tracks }) => {
      // Arrange
      const departure = knownPath[0];
      const destination = knownPath[knownPath.length - 1];

      // Act
      const shortestPath = metroRoute(departure, destination, tracks);

      // Assert
      for (const edge of shortestPath!) {
        expect(shortestPath).toContainEqual(edge);
      }
    })
  );
});
Enter fullscreen mode Exit fullscreen mode

Property 5: should be able to find a path shorther or equal to the one we come up with

for map of the metro and two stations "departure" and "destination" known to be connected by at least one oriented set of tracks
it should find a path with length shorter or equal to the known route

Written with fast-check:

it("should be able to find a path shorther or equal to the one we come up with", () => {
  fc.assert(
    fc.property(
      orientedGraphArbitrary(),
      ({ knownPath, knownPathTracks, tracks }) => {
        // Arrange
        const departure = knownPath[0];
        const destination = knownPath[knownPath.length - 1];

        // Act
        const shortestPath = metroRoute(departure, destination, tracks);

        // Assert
        const distanceKnownPath = knownPathTracks.reduce((acc, e) => acc + e.length, 0);
        const distanceShortestPath = shortestPath!.reduce((acc, e) => acc + e.length, 0);
        expect(distanceShortestPath).toBeLessThanOrEqual(distanceKnownPath);
      }
    )
  );
});
Enter fullscreen mode Exit fullscreen mode

Property 6: should not return any path whenever there is no way going from start to end

for map of the metro and two stations "departure" and "destination" known not to be connected
it should not find any track going from "departure" to "destination"

Written with fast-check:

it("should not return any path whenever there is no way going from start to end", () => {
  fc.assert(
    fc.property(
      orientedGraphNoWayArbitrary(),
      ({ departure, destination, tracks }) => {
        // Arrange / Act
        const shortestPath = metroRoute(departure, destination, tracks);

        // Assert
        expect(shortestPath).toBe(undefined);
      }
    )
  );
});
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)