This notebook was prepared by [Donne Martin](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).

Challenge Notebook

Problem: Implement the Towers of Hanoi with 3 towers and N disks.

Constraints
Test Cases
Algorithm
Code
Unit Test
Solution Notebook

Constraints

Can we assume we already have a stack class that can be used for this problem?
- Yes

Test Cases

None tower(s)
0 disks
1 disk
2 or more disks

Algorithm

Refer to the Solution Notebook. If you are stuck and need a hint, the solution notebook's algorithm discussion might be a good place to start.

Code



In [ ]:

    
%run ../../stacks_queues/stack/stack.py
%load ../../stacks_queues/stack/stack.py



In [ ]:

    
def hanoi(num_disks, src, dest, buff):
    # TODO: Implement me
    pass

Unit Test

The following unit test is expected to fail until you solve the challenge.



In [ ]:

    
# %load test_hanoi.py
from nose.tools import assert_equal


class TestHanoi(object):

    def test_hanoi(self):
        num_disks = 3
        src = Stack()
        buff = Stack()
        dest = Stack()

        print('Test: None towers')
        hanoi(num_disks, None, None, None)

        print('Test: 0 disks')
        hanoi(num_disks, src, dest, buff)
        assert_equal(dest.pop(), None)

        print('Test: 1 disk')
        src.push(5)
        hanoi(num_disks, src, dest, buff)
        assert_equal(dest.pop(), 5)

        print('Test: 2 or more disks')
        for i in range(num_disks, -1, -1):
            src.push(i)
        hanoi(num_disks, src, dest, buff)
        for i in range(0, num_disks):
            assert_equal(dest.pop(), i)

        print('Success: test_hanoi')


def main():
    test = TestHanoi()
    test.test_hanoi()


if __name__ == '__main__':
    main()

Solution Notebook

Review the Solution Notebook for a discussion on algorithms and code solutions.