Advent of PBT 2021 - Day 4 - Solution

Our algorithm was: detectCycleInLinkedList.
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-4-solution-jxqle?file=/src/index.spec.ts&previewwindow=tests

---

Property 1: should not detect any cycle in a non-looping linked list

For this first property, we will come up with tailored inputs having some already known characteristics. Instead of taking two fully random strings, we build two strings having some links together.

for any linked list not defining any cycle
it should not detect any cycle

Written with fast-check:

it("should not detect any cycle in a non-looping linked list", () => {
  // fc.letrec allows us to generate a recursive structure
  // as our typing said a LinkedList is just a value
  // and potentially another LinkedList defined via next
  const noCycleLinkedListArbitrary = fc.letrec((tie) => ({
    node: fc.record({
      value: fc.integer(),
      next: fc.option(tie("node") as fc.Arbitrary<LinkedList>, {
        nil: undefined,
        depthFactor: 1
      })
    })
  })).node;
  fc.assert(
    fc.property(noCycleLinkedListArbitrary, (linkedList) => {
      // Arrange / Act
      const cycleDetected = detectCycleInLinkedList(linkedList);

      // Assert
      expect(cycleDetected).toBe(false);
    })
  );
});

Property 2: should detect a cycle in a looping linked list

As we did for our example based test building a linked list with a cycle, we will create a linked list and attach the next of the last item to the first one.

for any linked list defining a cycle
it should detect any cycle

Written with fast-check:

it("should detect a cycle in a looping linked list", () => {
  fc.assert(
    fc.property(fc.array(fc.integer(), { minLength: 1 }), (nodes) => {
      // Arrange
      const lastNode: LinkedList = { value: nodes[0], next: undefined };
      const linkedList = nodes
        .slice(1)
        .reduce((acc, n) => ({ value: n, next: acc }), lastNode);
      lastNode.next = linkedList;

      // Act
      const cycleDetected = detectCycleInLinkedList(linkedList);

      // Assert
      expect(cycleDetected).toBe(true);
    })
  );
});

Please node that the reduce trick could also have been used to build the first property without relying on fc.letrec.

---

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.