Türme von Hanoi.
Türme von Hanoi. (source: Bin im Garten on Wikimedia Commons)

100 Days of Algorithms is a series of Medium posts and Jupyter Notebooks by Tomáš Bouda that implement 100 interesting algorithms. They're a programming exercise that Tomáš set for himself: can he implement 100 interesting algorithms, one per day?

The answer was “yes.” The algorithms range from classics like Towers of Hanoi to Bloom filters and graph traversal. Over the coming weeks, we’ll be featuring selections from Tomáš’ 100 Days of Algorithms project here on O’Reilly.

Towers of Hanoi (Day 1)

Everybody knows the towers of Hanoi: it's a staple in introductory programming courses. You have three poles, one with a set of rings stacked on it, from the largest to the smallest. (Think the common ring stacking toy.) Move the rings one at a time from the left pole to the right one without ever placing a larger ring on top of a smaller ring. The solution is shockingly short and elegant.

Here's Tomáš’ Medium post on the towers of Hanoi. Below you’ll find a static version of his Jupyter Notebook. The notebook can be accessed and cloned here.

algorithm

def hanoi(height, left='left', right='right', middle='middle'):
    if height:
        hanoi(height - 1, left, middle, right)
        print(left, '=>', right)
        hanoi(height - 1, middle, right, left)

run

hanoi(1)
left => right

hanoi(2)
left => middle
left => right
middle => right

hanoi(3)
left => right
left => middle
right => middle
left => right
middle => left
middle => right
left => right

Technical notes

The implementations work; the Jupyter Notebooks all run. Since this started off as a personal exercise, don't expect the implementations to be optimal, bullet-proof, or even necessarily correct (though we don't see anything wrong with them). And don't expect them to contain your favorite algorithms (or the ones you need for your homework assignments).

The easiest way to install Jupyter Notebooks is to use Anaconda. The second easiest (and most bulletproof) way is to install Docker and then use the scipy-notebook container.

If you're rolling your own Jupyter environment, you need:

Article image: Türme von Hanoi. (source: Bin im Garten on Wikimedia Commons).