Our algorithm was: hanoiTower.
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-11-solution-n3pgt?file=/src/index.spec.ts&previewwindow=tests
Before moving on to our properties for hanoiTower, we may want to spend a bit of time on our existing tests:
it("should be able to move a tower of size 3 from 0 to 2", () => {
const move = jest.fn();
hanoiTower(3, 0, 2, move);
expect(move.mock.calls).toEqual([
// state: (1/2/3) / () / ()
[0, 2],
// state: (2/3) / () / (1)
[0, 1],
// state: (3) / (2) / (1)
[2, 1],
// state: (3) / (1/2) / ()
[0, 2],
// state: () / (1/2) / (3)
[1, 0],
// state: (1) / (2) / (3)
[1, 2],
// state: (1) / () / (2/3)
[0, 2]
// state: () / () / (1/2/3)
]);
});
In the test above, we clearly expects a precise series of calls to move. We somehow tells the implementer that the algorithm must behave exactly that way no matter if there is another way to move the tower to another pillar. For a towerHeight of 3 it is probably the shortest way to move the tower to another pillar but what if there was many to do so in an optimal way?
In property based, we will not require a precise series of calls to move. We will rather expects some relationships between those calls. In other way, we will rather tell "what" we are looking to achieve rather than the exact "how". Defining the "how" will be the aim of the implementer.
Property 1: should move the tower to the requested pillar
The first requirement of the algorithm is to move the tower from one pillar to another. So let's first assess it.
for any
towerHeight,startPositionandendPosition
it should move the tower fromstartPositiontoendPosition
We define two helper functions that will help us to build our inputs and the expected output:
/**
* Build initial disks for a tower of size towerHeight
* buildTowerStack(3) -> [3, 2, 1]
*/
function buildTowerStack(towerHeight: number): number[] {
const stack: number[] = [];
for (let diskSize = towerHeight; diskSize >= 1; --diskSize) {
stack.push(diskSize);
}
return stack;
}
/**
* Build the initial setup of the stacks
* with an hanoi tower of height towerHeight at position startPosition
*/
function buildInitialStacks(
startPosition: number,
towerHeight: number
): [number[], number[], number[]] {
return [
startPosition === 0 ? buildTowerStack(towerHeight) : [],
startPosition === 1 ? buildTowerStack(towerHeight) : [],
startPosition === 2 ? buildTowerStack(towerHeight) : []
];
}
Our initial state can be computed via buildInitialStacks(startPosition, towerHeight) and our expected final state via buildInitialStacks(endPosition, towerHeight).
Written with fast-check:
it("should move the tower to the requested pillar", () => {
fc.assert(
fc.property(
fc.constantFrom(0, 1, 2),
fc.constantFrom(0, 1, 2),
fc.integer({ min: 0, max: 10 }),
(startPosition, endPosition, towerHeight) => {
// Arrange
const stacks = buildInitialStacks(startPosition, towerHeight);
const expectedStacks = buildInitialStacks(endPosition, towerHeight);
const move = (from: number, to: number) => {
const head = stacks[from].pop()!; // not checked by this test
stacks[to].push(head);
};
// Act
hanoiTower(towerHeight, startPosition, endPosition, move);
// Assert
expect(stacks).toEqual(expectedStacks);
}
)
);
});
Property 2: should move disk on top of a larger disk or empty pillar
One of the other key requirement for the algorithm is to only move disks either on top of larger ones or on top of empty pillars.
for any
towerHeight,startPositionandendPosition
it should never callmoveto execute an illegal move (no move or move on smaller disk)
Written with fast-check:
it("should move disk on top of a larger disk or empty pillar", () => {
fc.assert(
fc.property(
fc.constantFrom(0, 1, 2),
fc.constantFrom(0, 1, 2),
fc.integer({ min: 0, max: 10 }),
(startPosition, endPosition, towerHeight) => {
// Arrange
const stacks = buildInitialStacks(startPosition, towerHeight);
// Act / Assert
const move = (from: number, to: number) => {
expect(stacks[from]).not.toEqual([]); // we need to move something
const head = stacks[from].pop()!;
if (stacks[to].length !== 0) {
const headTo = stacks[to][stacks[to].length - 1];
expect(head).toBeLessThan(headTo); // we need to move it on larger disks
} // or empty pillar
stacks[to].push(head);
};
hanoiTower(towerHeight, startPosition, endPosition, move);
}
)
);
});
Property 3: should not pass twice by the same state
As we want to minimize the number of moves, one of the easiest assertion we can make is that we never pass twice by the same state. Passing twice by the same state would mean that we did some useless moves that could be removed to reach something smaller.
for any
towerHeight,startPositionandendPosition
it should never reach twice the same state
Written with fast-check:
it("should not pass twice by the same state", () => {
fc.assert(
fc.property(
fc.constantFrom(0, 1, 2),
fc.constantFrom(0, 1, 2),
fc.integer({ min: 0, max: 10 }),
(startPosition, endPosition, towerHeight) => {
// Arrange
const stacks = buildInitialStacks(startPosition, towerHeight);
function stateToString(state: [number[], number[], number[]]): string {
return `${state[0].join(".")}/${state[1].join(".")}/${state[2].join(".")}`;
}
const seenStates = new Set<string>([stateToString(stacks)]);
// Act / Assert
const move = (from: number, to: number) => {
const head = stacks[from].pop()!; // not checked by this test
stacks[to].push(head);
const newStateString = stateToString(stacks);
expect(seenStates.has(newStateString)).toBe(false);
seenStates.add(newStateString);
};
hanoiTower(towerHeight, startPosition, endPosition, move);
}
)
);
});
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)