Advent of PBT 2021 - Day 4

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

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

/**
 * Definition of a LinkedList
 */
export type LinkedList = {
  value: number;
  next: LinkedList | undefined;
};

/**
 * Check if there is a cycle in a given linked list.
 *
 * @param list - The linked list to check.
 *
 * @returns
 * true if there is a cycle, false otherwise.
 */
declare function detectCycleInLinkedList(list: LinkedList): boolean;

We already wrote some examples based tests for it:

it("should not detect any cycle for a one-element list", () => {
  const list: LinkedList = {
    value: 0,
    next: undefined
  };
  expect(detectCycleInLinkedList(list)).toBe(false);
});

it("should not detect any cycle for a two-element list", () => {
  const list: LinkedList = {
    value: 0,
    next: { value: 1, next: undefined }
  };
  expect(detectCycleInLinkedList(list)).toBe(false);
});

it("should not detect any cycle for a list with duplicates", () => {
  const list: LinkedList = {
    value: 0,
    next: { value: 0, next: undefined }
  };
  expect(detectCycleInLinkedList(list)).toBe(false);
});

it("should detect a cycle if a node appear twice", () => {
  const list: LinkedList = {
    value: 0,
    next: undefined
  };
  list.next = list;
  expect(detectCycleInLinkedList(list)).toBe(true);
});

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-4-g0jdy?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-4-solution-lh2

---

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.