Hanoi Jane

Counting in binary to solve the Towers of Hanoi

Surely there are easier ways to do this?

Yes, there are. This is very much a Solved Problem. However, I was inspired to implement this solution after watching 3 Blue 1 Brown’s fascinating video, in which Grant relates the Towers Of Hanoi to the Rhythm Of Counting In Binary:


Running it

bundle exec rake
bundle exec rake install
hanoi console

(or just gem install hanoi-jane, of course)

Constrained version

There is a constrained variant of the problem, with the restriction that a disc may only move to an adjacent stack. I’ve also implemented the solution for this (which maps to the Rhythm Of Counting In Ternary) - you can run this with

hanoi --constrained


To use it in your own code, try something like:

require 'hanoi/jane'

towers = Hanoi::Jane::ConstrainedTowers.new 2
towers.each do |state|
  puts state.inspect

which will give you:

{:stacks=>[[1, 0], [], []], :moves=>0, :moved=>nil, :ternary=>'00'}
{:stacks=>[[1], [0], []], :moves=>1, :moved=>0, :ternary=>'01'}
{:stacks=>[[1], [], [0]], :moves=>2, :moved=>0, :ternary=>'02'}
{:stacks=>[[], [1], [0]], :moves=>3, :moved=>1, :ternary=>'10'}
{:stacks=>[[], [1, 0], []], :moves=>4, :moved=>0, :ternary=>'11'}
{:stacks=>[[0], [1], []], :moves=>5, :moved=>0, :ternary=>'12'}
{:stacks=>[[0], [], [1]], :moves=>6, :moved=>1, :ternary=>'20'}
{:stacks=>[[], [0], [1]], :moves=>7, :moved=>0, :ternary=>'21'}
{:stacks=>[[], [], [1, 0]], :moves=>8, :moved=>0, :ternary=>'22'}

where moved is the disc that was moved last


In order to over-engineer this, I’ve wrapped a very thin Flask app around the MicroDot pHAT. Try

hanoi phat --phat <address_of_your_pi> --constrained

to watch this all play out on the pHAT:


Tags: ruby

Back to top