Code Golf: Towers of Hanoi
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.
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/^,//
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",""))
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
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
加载中,请稍侯......
精彩评论