Code Golf: Towers of Hanoi

Question

Rules

The Towers of Hanoi is a puzzle, and if you are not very familiar with it, here is how it works:

The play field consists of 3 rods, and x number of disks, each next one bigger than the previous one. The disks can be put on the rod, with these RULES:

• only one disk can be moved at once, and it must be moved on the top of another rod
• the disk must be taken from the top of a rod
• a disk can be moved somewhere, ONLY if the top-most disk at the target rod is bigger than the one to be moved

And finally - the play field STARTS like this:

• a rod, with x disks, sorted so the largest is on the bottom, and the smallest on the top
• an empty rod
• an empty rod

The GOAL of the game is to move the original "stack" of disks on another rod, that is - put all of the disks on another rod, so (again) the largest is on the bottom, and the smallest on the top

Implementation

YOUR goal will be to make a program in programming language of your choice, that takes an input (described below) and outputs the steps necessary to solve the position.

As always, try to make it as short as possible.

Input

An example input:

4-3,7-6-5,2-1

Input is a string, consisting of 3 parts, separated by commas. The parts are a list of disks on each of the 3 rods. They are separated too, this time with hyphens ( - ), and each subpart is a number, the larger the number is, the larger the disk is.

So - for the above input, this would be a visual representation:

       .               .               .
       |          =====|=====          |
    ===|===      ======|======        =|=
   ====|====    =======|=======      ==|==

     ROD 1           ROD 2           ROD 3

Output

As you can see in the above representation - the the left-most part of the input is rod number one, the middle is rod number two, and the last one is rod number 3.

The output of your program should look like this:

12,23,31,12,23,13

A list of numbers, separated by commas that defines the rod that a disk should be taken of, and the rod that the disk should be put on. There are only 3 rods, so there is just 6 possible combinations (because a disk has to be moved to another rod, not the same one):

12
13
21
23
31
32

Notes

The input does not have to describe a field in "original" state - it can be mid-solved.

Your program can NOT produce null output. If the input IS in the original state, just put the disks to a DIFFERENT rod.

The input can have an empty rod(s), like these:

2-1,3,
,,1
4-3,,2-1

If the input is not in this formatted like that, your program can produce undefined behavior. So it can if the input is not valid (like bigger disk on a smaller one, missing disk, unsolvable). Input will always be valid.

Make sure the solution is as fast as possible (as little turns as possible) - that is, don't waste turns by "12,21,12"...

Testing

So, I prepared this small flash for you, with which you can test if your program produced a good solution without writing it down or anything.

Here it is: Hanoi AlgoTest (wait for it to load then refresh -- Dead link :|)

To use it, paste the input to the program to the INPUT field, and the output produced by your program to the PROCESS field. It will run a simulation, at speed which you can also change, with a visual representation, printing out any errors in the bottom part.

Hope it helps.

Pyelography

Does the input have to be a valid state, or is a random state ok? Actually... now that I think about it... is there ALWAYS a solution to this puzzle, with ANY starting states or is it possible to create a starting state such that there is no solution? – Atlee

Yes, the input is always valid - that is, there are all disks included from the smallest to the largest (no 1,2,4), they are ALWAYS following the rule - smaller atop bigger. There is ALWAYS a solution. Let me put that in there... – Ernaline

But every position has two possible "correct" answers. That is, if the input is "7-3,1,2", then the solution could be "31,21", or it could start with "23,12" and continue with the 123 additional steps required to move the rest of the disks to peg 2. Your problem definition has to include the direction in which a stack is to be moved. – Emancipate

It can have two answers - doesn't matter at all. I did not say there is just one solution, I just said (written anyway) "Make sure the solution is as fast as possible - that is, don't waste turns by "12,21,12"..." - get as little steps as possible. – Ernaline

golf.shinh.org/p.rb?Tower+of+Hanoi – Leger

It is different. That problem defines just an original start position. In here, the start can be random. It is different because original start position is solvable with VERY easy recursion. – Ernaline

"4-3,7-5-6,2-1" - so the list of disks isn't the same as the order on the rod? (as the middle rod has 6 on 5, if they are ordered) – Dilworth

Yes, having to deal with a mid-solution start position makes things more difficult... – Dilworth

@Pyelography is it safe to assume the position will be along the optimal path from all starting on the first rod and using the third as aux, or can it be any random valid position? – Enquire

@Aurel300, good,saves me 7 characters :) – Dilworth

@NickLarsen - No, the position can be random. So, again, it is not just about following a linear recursion (and finding what part of it is the play field at). – Ernaline

"Your program can NOT produce null output. If the input IS in the original state, just put the disks to a DIFFERENT rod" - This is a pain. I have a solution that solves anything not in the original state, and I'll have to special-case this :( – Dilworth

Well, it kinda makes the program follow the original game. – Ernaline

As fast as possible... does this means, that I am not allowed to use some solution which uses more turn but hasn't such "trivial" optimization? – Reform

TRY to make it as fast as possible. Both in turns and memory / CPU usage. But you don't HAVE to, it is just a better solution. – Ernaline

"Make sure the solution is as fast as possible (as little turns as possible) " Does it have to be optimal? Consider 7-6-5,4,3-2-1. The optimal moves are move disk 4 to rod 1, then the stack 3-2-1 to rod 1. A naive approach (ie. my current algoithm :() would move stack 3-2-1 on top of disk 4, then stack 4-3-2-1 to rod 1. It wouldn't have the trivial inefficiencies you list but it's not optimal – Dilworth

Again, just try. So that programs with similar length are going to be up-voted depending on their optimality, both in algorithm and exec. speed. – Ernaline

"a disk can be moved somewhere, ONLY if the top-most disk at the target rod is smaller than the one to be moved". Shouldn't that be "bigger than the one to be moved"? – Isoline

@Mark - yeah, let me fix that... – Ernaline

Can there be no disks? (Input string ,,)? I think it's allowed by the rules above... – Dilworth

@Paul - no, there are ALWAYS going to be some disks. Also - these parts permit it: - Your program can NOT produce null output. - [...] So it can if the input is not valid (like bigger disk on a smaller one, missing disk, unsolvable). Input will always be valid. – Ernaline

OK. I think I'm done with my solution, apart from producing a minimal length version at some point. – Dilworth

Answer 1

Perl, 209 (203) char

Rewritten to keep track of the location of each disk as opposed to the list of disks that are contained on each rod.

306 291 263 244 236 213 209 chars after removing unnecessary whitespace.

sub M{my($r,$s)=@_;if(--$m){M($r,$r^$s);$_.=",$r$s";M($r^$s,$s)}s/(.),?\1//;
$R[++$m]=$p}map@R[/\d+/g]=(++$i)x99,split/,/,<>;do{1until
($n=$R[1])-($p=$R[++$m]||$n-1|2);M$n,$p}while 1<grep@R~~$_,1..3;s/^,//;print

$R[j]: the location of disk j

$n: the location of disk #1

$m: the number of disks to move

$p: the location to move the disks to

&M(r,s): move $m-1 disks from r to s. Appends to $_ and sets @R

The substitution inside sub M optimizes the output, removing extraneous steps. It could be removed (12 characters) and the output would still be valid.

Another 12 characters can be removed if the perl interpreter is invoked with the command-line switch -apF,. With the extra 6 chars for the command-line switch, this gets us down to net 203 characters:

# invoke as   perl -apF, ...
sub M{my($r,$s)=@_;if(--$m){M($r,$r^$s);$_=$a.=",$r$s";M($r^$s,$s)}
s/(.),\1//;$R[++$m]=$p}map@R[/\d+/g]=(++$i)x99,@F;
do{1until($n=$R[1])-($p=$R[++$m]||$n-1|2);M$n,$p}while 1<grep@R~~$_,1..3;s/^,//

Leger

Does it move disks when the initial state is all disks on one rod? No Perl nearby and it's difficult to tell from the code :) – Dilworth

Blast, I get mine down to 296 to beat your initial version, only for you to post an improvement. Still, I'm quite pleased with 292 for the Scala version, given it's not really known as a language suited to codegolf. It's past midnight here, I'm off... – Dilworth

Answer 2

Here's a starter for 10, in Scala, revised a few times. I don't know of any issues, and I have no other ideas for further reducing the moves

Runs as a Scala script.

Bits of this are quite elegant (IMO) but other bits are an ugly hack

Shortest code (but non-optimal moves), tracking position of disks rather than list of disks on rods (idea shamelessly stolen from the Perl solution)

 val r=args(0).split(",",-1);var d=Map{{for(q<-0 to 2 if""!=r(q);n<-r(q).split('-').map{_.toInt})yield(n,q+1)}:_*};val n=d.max._1;var m="";def s(f:Int,t:Int,n:Int):Unit=if(n!=0&&f!=t){s(f,6-f-t,n-1);d=d+(n->t);m=m+","+f+t;s(6-f-t,t,n-1)};for(c<- 2 to n)s(d(1),d(c),c-1);if(m=="")s(d(1),d(1)%3+1,n);println(m.tail.replaceAll("(.),?\\1",""))

Puzzle is taken from the command line.

338 bytes. Not too shabby since this is a statically typed language, and still relatively readable (if you replace ; with newlines)

Readable version follows (with more optimal moves)

val rods = args(0).split(",", -1);
var diskLocation = Map{
  {
    for (rod <-0 to 2 if rods(rod).nonEmpty;
         n <-rods(rod).split('-').map{_.toInt})
      yield(n, rod + 1)
  }:_*
}

val nDisks = diskLocation.max._1

var moves = ""

def moveTower(start:Int, end:Int, n:Int):Unit = 
  if (n != 0) {
    val other = 6 - start - end
    moveTower(start, other, n - 1)
    moveDisk(n, end)
    moveTower(other, end, n - 1)
  }

def moveDisk(n:Int, end:Int) = {
  moves = moves + "," + diskLocation(n) + end
  diskLocation = diskLocation.updated(n, end);
}

for (c <- 2 to nDisks) {
  var firstLocation = diskLocation(1)
  var nextLocation = diskLocation(c)
  if (firstLocation != nextLocation) {
    if (c != nDisks) {
      val diskAfter = diskLocation(c + 1)
      if (diskAfter != firstLocation && diskAfter != nextLocation) {
        moveDisk(c, diskAfter)
        nextLocation = diskAfter
      }
    }
    moveTower(diskLocation(1), diskLocation(c), c - 1);
  }
}

if (moves == "")
  moveTower(diskLocation(1), diskLocation(1)%3 + 1, nDisks)

println(moves.tail.replaceAll("(.),?\\1",""))

Waterless

I wonder, how do you test a Scala script? I mean, I tried the compiler but that just makes a Java class file... Is there some tester? – Ernaline

Just scala hanoi.scala 7-5,4-3-2,1 – Dilworth

Oh I see now! I might finally test your solution :D – Ernaline

Hmm. Bugs detected. Don't waste too much time testing (I think the really short version is OK, I've messed up the optimisations somewhere) – Dilworth

Yes, I misinterpreted your instructions. Will fix. They all have that problem – Dilworth

Fixed the long-form one - but there will be other changes. Probably best to wait. That one produces considerably shorter moves than some examples given for the Perl ones :) – Dilworth

Fixed, I think. The requirement for comma-separated values (which forces the code to keep a queue of moves) and to work with an already solved puzzle add quite a lot to the shortest one :( – Dilworth

Answer 3

Perl 241 char

Certainly not the most efficient way, but it works.

Updated to suppress last comma.

map{map$g[$_]=$i|0,/\d/g;$i++}split$,=',',<>;shift@g;@G=(0)x@g;@u=(1)x10;while(!$G[@g]){$G="@G";$_="@g";$i=0;$j=$G[0]+$u[0];while($j>2||$j<0){$u[$i++]*=-1;$j=$u[$i]+$G[$i]}$r=1+$G[$i].$j+1;$G[$i]=$j;$p=1if/$G/;push@o,$r if$p&&$i++<@g}print@o

Same with whitespaces:

map{
  map $g[$_]=$i|0, /\d/g;
  $i++
}split$,=',',<>;
shift@g;
@G=(0)x@g;
@u=(1)x10;
while(!$G[@g]){
  $G="@G";
  $_="@g";
  $i=0;
  $j=$G[0]+$u[0];
  while($j>2||$j<0){
    $u[$i++]*=-1;
    $j=$u[$i]+$G[$i]
  }
  $r=1+$G[$i].$j+1;
  $G[$i]=$j;
  $p=1if/$G/;
  push@o,$r if$p&&$i++<@g
}
print@o

Usage:

echo 5-2,3-1,4 | perl hanoi.pl

Output:

21,23,12,23,12,32,21,23,12,23,12,32,21,32,12,23,21,32,21,32,12,23,12,32,21,23,12,23,21,32,21,32,12,23,21,32,21,32,12,23,12,32,21,23,12,23,12,32,21,32,12,23,21,32,21,23,12,23,12,32,21,23,12,23,21,32,21,32,12,23,21,32,21,32,12,23,12,32,21,23,12,23,21,32,21,32,12,23,21,32,21,23,12,23,12,32,21,23,12,23,12,32,21,32,12,23,21,32,21,23,12,23,12,32,21,23,12,23,12,32,21,32,12,23,21,32,21,32,12,23,12,32,21,23,12,23,21,32,21,32,12,23,21,32,21,23,12,23,12,32,21,23,12,23,12,32,21,32,12,23,21,32,21,23,12,23,12,32,21,23,12,23

Dart

Has quite some problems. First - one VERY important - the output is NOT valid. It did (or just can? it happened anyway) output a comma in the end of the output string. Not right - it is not supposed to be there. Second - yeah, it is not quite optimal... But still - I wonder if you can't just make this a little bit better - I tried "3-2-1,," and it moved the tower first to row 2, then to row 3... ? – Ernaline

Produces no output when all disks start on the 3rd rod (,,2-1, for example)? – Leger

@mobrule, yes I just tested it. It some annoying bug! – Ernaline

Answer 4

Attempt at Lua I've tried to implement the iterative solution from wikipedia, but it doesn't really work, but the time i'm spending on it is up, so I hope this inspires someone to adapt it. It does parse everything well, including empty columns. Extra goodie: it does pretty printing of the stacks as in the visual representation in the question.

-- Input "rod1,rod2,rod3" where rod? = a - seperated list of numbers, representing the disks.
p,q,r=io.read():match'([^,]*),([^,]*),([^,]*)'
print(p,q,r)
i=table.insert
u=unpack
function gen(t)
    return function(v)i(t,tonumber(v)) end
end

function basic(t,n) 
    for k,v in pairs(t) do
        print(k,"----")
        for kk,vv in pairs(v) do print("\t",kk,vv) end
    end
    print'================'
end
function pretty(t,n)
    local out={}
    for k=1,n do out[k]={} end
    for k=1,n do                -- K is each row
        local line=out[k]
        for l=1,3 do            -- L is each rod
            local d=t[l][k]
            if d~=1e9 then -- TODO Check if metahack necesarry
                line[#line+1]=(" "):rep(n-d+1)
                line[#line+1]=("="):rep(d)
                line[#line+1]="|"
                line[#line+1]=("="):rep(d)
                line[#line+1]=(" "):rep(n-d+1)
                line[#line+1]=" "
            else
                line[#line+1]=(" "):rep(2*n+4)
            end
        end
        out[k]=table.concat(line)
    end
    for k=n,1,-1 do
        io.write(out[k],"\n")
    end
end
function T(f,...)
    w=0
    for k=1,3 do
        l=({...})[k]
        w=#l==0 and w or f(w,u(l))
    end
    return w
end

Stat=pretty
t={{},{},{}} --rods 1 - 3, discs ordered 1 = bottom
for k,v in pairs{p,q,r}do -- loop over strings
    v:gsub('%d+',gen(t[k])) -- add decimal to rod
end
n=T(math.max,t[1],t[2],t[3]) -- Biggest disc = number of discs
--for k=1,3 do c=1*t[k][1] if n==c then A=k elseif m==c then C=k else B=k end end -- Rod where the biggest disc is (A)
for k=1,3 do setmetatable(t[k],{__index = function() return 1e9 end}) c=t[k] if c[#c]==1 then one=k end end -- locate smallest disc, and set index for nonexistant discs to 1e9
-- Locate second biggest disc (B), smallest stack = C -> move C to B
-- Algorithm:
-- uneven : move to the left, even: move to the right
-- move smallest, then move non-smallest.
-- repeat until done
--
-- For an even number of disks:
--
--     * make the legal move between pegs A and B
--     * make the legal move between pegs A and C
--     * make the legal move between pegs B and C
--     * repeat until complete
--
-- For an odd number of disks:
--
--     * make the legal move between pegs A and C
--     * make the legal move between pegs A and B
--     * make the legal move between pegs B and C
--     * repeat until complete
--
-- In each case, a total of 2n-1 moves are made.
d={{2,3,1},{3,1,2}}
s=d[math.fmod(n,2)+1] -- sense of movement -1 left (uneven # of discs), 1 right (even # of discs)
Stat(t,n)
for qqq=1,10 do
    -- move smallest
    d=s[one]
    print(one,d)
    if #t[d]==0 then print("skip rod",d,"next rod",s[d]) d=s[d] end-- if rod is empty, move to next in same direction
    table.insert(t[d],table.remove(t[one])) --TODO Problem
    print("Moved",one,"to",d)
    one=d -- track the small disc
    Stat(t,n)
    if #t[d]==n then break end -- destination stack reached number of discs, break off.
    -- find next valid move (compare the two non-previous-destination rod) to see which has the smallest disc, move disc to other rod.
    z=0
    for k=1,3 do
        print("-- k="..k)
        if k~=one then
            if z>0 then
                if t[k][#t[k]] > t[z][#t[z]] then   -- disc at rod z (source) is smaller than at k (destination)
                    d=k                                 -- destination = k 
                    print("-- t["..k.."]>t["..z.."], d="..d..", z="..z)
                else                                    -- disc at rod z (source) is bigger than at k (destination
                    d,z=z,k                             -- switch destination and source, so d will be z, and z will be the current rod
                    print("-- t["..k.."]<t["..z.."], d="..d..", z="..z)
                end
            else -- first of rods to compare
                z=k
                print("-- First rod to compare z="..z)
            end
        else
            print("-- disc one at this location, skipping",k)
        end
    end
    print("Will move from",z,"to",d)
    table.insert(t[d],table.remove(t[z]))
    Stat(t,n)
    if #t[d]==n then break end -- destination stack reached number of discs, break off.
end

Kauai