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
          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, 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
          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, 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
          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.