Advent of PBT 2021 - Day 19 - Solution
Tags: challenge, testing, webdev, javascript
Published: 2021-12-19 11:13:56

---
title: Advent of PBT 2021 - Day 19 - Solution
published: true
description: Advent of Property Based Testing 2021 - Day 19 - Solution
tags: challenge,testing,webdev,javascript
//cover_image: https://direct_url_to_image.jpg
---

Our algorithm was: **metroRoute**.
[Go to the subject itself for more details](https://dev.to/dubzzz/advent-of-pbt-2021-day-19-37ee)

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:

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

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:

```ts
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
      ]
    }));
}
```

---

## 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:

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

---

## 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:

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

---

## 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:

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

---

## 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:

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

---

## 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:

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

---

## 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:

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

---

[Back to "Advent of PBT 2021"](https://dev.to/dubzzz/advent-of-pbt-2021-13ee) to see topics covered during the other days and their solutions.

More about this serie on [@ndubien](https://twitter.com/ndubien) or with the hashtag [#AdventOfPBT](https://twitter.com/search?q=%23AdventOfPBT).