DEV Community

Nicolas DUBIEN
Nicolas DUBIEN

Posted on • Updated on

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;
Enter fullscreen mode Exit fullscreen mode

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);
});
Enter fullscreen mode Exit fullscreen mode

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.

Discussion (0)