Code Golf: Towers of Hanoi

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",""))

回答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

回答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