## DEV Community

Nicolas DUBIEN

Posted on • Updated on

# Advent of PBT 2021 - Day 11 - Solution

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`, `startPosition` and `endPosition`
it should move the tower from `startPosition` to `endPosition`

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
};

// 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`, `startPosition` and `endPosition`
it should never call `move` to 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
if (stacks[to].length !== 0) {
const headTo = stacks[to][stacks[to].length - 1];
} // or empty pillar
};
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`, `startPosition` and `endPosition`
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
const newStateString = stateToString(stacks);
expect(seenStates.has(newStateString)).toBe(false);