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.
Top comments (0)