Use hypothesis to solve towers of hanoi

hanoi.py

from typing import Optional, Tuple, List

class Hanoi:
    def __init__(self, num_rings: int):
        self.num_rings = num_rings

        if num_rings < 1:
            raise ValueError("Number of rings must be at least 1.")
        self.pegs: List[List[int]] = [list(), list(), list()]
        self.pegs[0] = list(reversed(range(0, num_rings)))

    def top(self, peg: int) -> Optional[int]:
        if not 0 <= peg < 3:
            raise IndexError("Peg must be one of 0,1,2")

        if self.pegs[peg]:
            return self.pegs[peg][-1]
        else:
            return None

    def move(self, src: int, dest: int):
        if not 0 <= src < 3:
            raise IndexError("Source peg must be one of 0,1,2")
        if not 0 <= dest < 3:
            raise IndexError("Destination peg must be one of 0,1,2")

        if self.pegs[src]:
            src_ring = self.pegs[src].pop()
            dest_ring = self.top(dest)
            if dest_ring is not None and dest_ring < src_ring:
                raise ValueError(f"Invalid move of bigger ring on top of smaller ring: {src_ring} > {dest_ring}")
            else:
                self.pegs[dest].append(src_ring)

    def finished(self) -> bool:
        return self.pegs[1] == list(reversed(range(0, self.num_rings)))

import hypothesis
import hypothesis.strategies as st
from hypothesis.stateful import RuleBasedStateMachine, rule, precondition, invariant

class HanoiSolverSM(RuleBasedStateMachine):
    def __init__(self):
        super().__init__()
        self.hanoi = Hanoi(3)

    def valid_moves(self) -> List[Tuple[int, int]]:
        """ Returns a list of tuples of the form (x,y) such that
        self.hanoi.move(x,y) is a valid move.
        
        This should be implemented on the Hanoi class directly really.
        """

        moves = list()
        for x in range(0,3):
            for y in range(0,3):
                if x == y:
                    continue
                if self.hanoi.top(x) is None:
                    continue

                if self.hanoi.top(y) is None or self.hanoi.top(x) < self.hanoi.top(y):
                    moves.append((x,y))

        return moves

    @rule(data=st.data())
    def move(self, data):
        positions = data.draw(st.sampled_from(self.valid_moves()))
        self.hanoi.move(positions[0], positions[1])

    @invariant()
    def assert_on_finish(self):
        assert not self.hanoi.finished()

HanoiSolver = HanoiSolverSM.TestCase
HanoiSolver.settings = hypothesis.settings(database=None)

import pytest

def test_hanoi_init():
    h = Hanoi(5)
    assert h.pegs[0] == [4,3,2,1,0]
    assert not h.pegs[1]
    assert not h.pegs[2]

def test_hanoi_top():
    h = Hanoi(5)
    assert h.top(0) == 0
    assert h.top(1) is None
    assert h.top(2) is None

def test_hanoi_top_oob():
    h = Hanoi(4)
    with pytest.raises(IndexError, match = r'Peg must be one of 0,1,2'):
        h.top(-1)
    with pytest.raises(IndexError, match = r'Peg must be one of 0,1,2'):
        h.top(5)

def test_hanoi_move_simple():
    h = Hanoi(5)

    h.move(0, 1)
    assert h.pegs[0] == [4,3,2,1]
    assert h.pegs[1] == [0]
    assert not h.pegs[2]

def test_hanoi_move_invalid_size():
    h = Hanoi(5)

    # move smallest ring to center
    h.move(0, 1)
    with pytest.raises(ValueError, match = r'Invalid move of bigger ring on top of smaller ring: 1 > 0'):
        # move second smallest ring on top of smallest: invalid
        h.move(0, 1)
    # in general, doing h.move(x, y) twice will always be invalid if there are at least two rings at x

def test_hanoi_move_invalid_range():
    h = Hanoi(5)

    with pytest.raises(IndexError, match = r'Source peg must be one of 0,1,2'):
        h.move(-1,2)
    with pytest.raises(IndexError, match = r'Destination peg must be one of 0,1,2'):
        h.move(0,3)

def test_hanoi_move_empty_no_error():
    h = Hanoi(5)
    h.move(1,2)

def test_hanoi_not_finished():
    h = Hanoi(5)
    assert not h.finished()
    h.move(0,2)
    h.move(0,1)
    h.move(2,1)
    assert not h.finished()

def test_hanoi_finished_2():
    h = Hanoi(2)
    h.move(0,2)
    h.move(0,1)
    h.move(2,1)
    assert h.finished()

def test_hanoi_finished_3():
    h = Hanoi(3)
    # move top two to right ring
    h.move(0,1)
    h.move(0,2)
    h.move(1,2)

    # move base to center
    h.move(0,1)
    
    # move right two to center
    h.move(2,0)
    h.move(2,1)
    h.move(0,1)
    assert h.finished()

output_minimal.txt

Falsifying example: run_state_machine(factory=HanoiSolverSM, data=data(...))
state = HanoiSolverSM()
state.move(data=data(...))
Draw 1: (0, 1)
state.move(data=data(...))
Draw 2: (0, 2)
state.move(data=data(...))
Draw 3: (1, 2)
state.move(data=data(...))
Draw 4: (0, 1)
state.move(data=data(...))
Draw 5: (2, 0)
state.move(data=data(...))
Draw 6: (2, 1)
state.move(data=data(...))
Draw 7: (0, 1)
state.teardown()
You can reproduce this example by temporarily adding @reproduce_failure('4.8.0', b'AXicY2RgYAQhRhjJBGQAAACFAAw=') as a decorator on your test case

output_nonminimal.txt

Falsifying example: run_state_machine(factory=HanoiSolverSM, data=data(...))
state = HanoiSolverSM()
state.move(data=data(...))
Draw 1: (0, 1)
state.move(data=data(...))
Draw 2: (0, 2)
state.move(data=data(...))
Draw 3: (1, 2)
state.move(data=data(...))
Draw 4: (0, 1)
state.move(data=data(...))
Draw 5: (2, 0)
state.move(data=data(...))
Draw 6: (0, 2)
state.move(data=data(...))
Draw 7: (2, 0)
state.move(data=data(...))
Draw 8: (2, 1)
state.move(data=data(...))
Draw 9: (0, 1)
state.teardown()

You can reproduce this example by temporarily adding @reproduce_failure('4.8.0', b'AXicY2RgYAQhRhgJQUxALgAA2wAQ') as a decorator on your test case