sam.pikesley.org

Using the rhythms of counting in binary to solve the Towers Of Hanoi

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:

Screenshot

Running it

bundle
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 console --discs 6 --constrained

API

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
end

which will give you:

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

where moved is the disc that was moved last

pHAT

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> --interval 0.1

to watch this all play out on the pHAT:

Screenshot

Gitpaint

Who hasn't, at some time in their life, wanted to play Towers of Hanoi on the Github commit-history graph? I've now built a formatter to generate output suitable for this - see hanoi-painter for more on how it all works

Hanoi Jane on Github