code-golf - solucion - torres de hanoi en excel
Código de golf: Torres de Hanoi (4)
Reglas
The Towers of Hanoi es un rompecabezas, y si no estás muy familiarizado con él, aquí está cómo funciona:
El campo de juego consta de 3 barras y x número de discos, cada uno más grande que el anterior. Los discos se pueden poner en la barra, con estas REGLAS :
- solo se puede mover un disco a la vez, y se debe mover en la parte superior de otra varilla
- El disco debe sacarse de la parte superior de una varilla.
- un disco se puede mover a cualquier lugar, SOLAMENTE si el disco que está más arriba en la barra de destino es más grande que el que se va a mover
Y finalmente, el campo de juego COMIENZA así:
- una varilla, con x discos, ordenada de modo que la más grande esté en la parte inferior y la más pequeña en la parte superior
- una barra vacía
- una barra vacía
El OBJETIVO del juego es mover la "pila" original de discos en otra barra, es decir, colocar todos los discos en otra barra, así que (nuevamente) el más grande está en la parte inferior y el más pequeño en la parte superior
Implementación
SU objetivo será hacer un programa en el lenguaje de programación de su elección, que tome una entrada (que se describe a continuación) y dé los pasos necesarios para resolver la posición.
Como siempre, trata de hacerlo lo más corto posible.
Entrada
Un ejemplo de entrada:
4-3,7-6-5,2-1
La entrada es una cadena, que consta de 3 partes, separadas por comas. Las partes son una lista de discos en cada una de las 3 varillas. También están separados, esta vez con guiones (-), y cada subparte es un número, cuanto mayor sea el número, mayor será el disco.
Entonces, para la entrada anterior, esto sería una representación visual:
. . .
| =====|===== |
===|=== ======|====== =|=
====|==== =======|======= ==|==
ROD 1 ROD 2 ROD 3
Salida
Como puede ver en la representación anterior, la parte más a la izquierda de la entrada es la barra número uno, la central es la barra número dos y la última es la barra número 3.
La salida de tu programa debería verse así:
12,23,31,12,23,13
Una lista de números, separados por comas que definen la barra de la que se debe sacar un disco y la barra en la que se debe colocar el disco. Solo hay 3 barras, así que solo hay 6 combinaciones posibles (porque un disco se debe mover a otra barra, no a la misma):
12
13
21
23
31
32
Notas
La entrada no tiene que describir un campo en estado "original", ya que puede resolverse a la mitad.
Su programa NO puede producir salida nula. Si la entrada ESTÁ en el estado original, simplemente coloque los discos en una varilla DIFERENTE.
La entrada puede tener una (s) varilla (s) vacía (s), como estas:
2-1,3,
,,1
4-3,,2-1
Si la entrada no tiene este formato, su programa puede producir un comportamiento indefinido. Por lo tanto, si la entrada no es válida (como un disco más grande en uno más pequeño, falta un disco, no se puede resolver). La entrada siempre será válida .
Asegúrese de que la solución sea lo más rápida posible (lo menos posible), es decir, no desperdicie los giros en "12,21,12" ...
Pruebas
Entonces, preparé este pequeño flash para ti, con el que puedes probar si tu programa produjo una buena solución sin escribirlo ni nada.
Aquí está: Hanoi AlgoTest (espere a que se cargue y luego actualice - Enlace muerto: |)
Para usarlo, pegue la entrada al programa en el campo ENTRADA , y la salida producida por su programa en el campo PROCESO . Ejecutará una simulación, a una velocidad que también puede cambiar, con una representación visual, imprimiendo cualquier error en la parte inferior.
Espero eso ayude.
Perl, 209 (203) char
Vuelva a escribir para realizar un seguimiento de la ubicación de cada disco en lugar de la lista de discos que se encuentran en cada barra.
306 291 263 244 236 213 209 caracteres después de eliminar espacios en blanco innecesarios.
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] : la ubicación del disco j
$n : la ubicación del disco # 1
$m : el número de discos para mover
$p : la ubicación para mover los discos a
&M(r,s) : mueve los discos de $m-1 de r a s. Se anexa a $_ y establece @R
La sustitución dentro de la sub M optimiza la salida, eliminando pasos extraños. Podría eliminarse (12 caracteres) y la salida seguiría siendo válida.
Se pueden quitar otros 12 caracteres si el intérprete de perl se invoca con el interruptor de línea de comandos -apF, Con los 6 caracteres adicionales para el interruptor de línea de comandos, esto nos lleva a 203 caracteres netos:
# 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/^,//
Perl 241 char
Ciertamente no es la forma más eficiente, pero funciona.
Actualizado para suprimir la última coma.
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
Lo mismo con espacios en blanco:
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
Uso:
echo 5-2,3-1,4 | perl hanoi.pl
Salida:
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
Aquí hay un arranque para 10, en Scala, revisado algunas veces. No conozco ningún problema y no tengo otras ideas para reducir aún más los movimientos.
Se ejecuta como un script de Scala.
Bits de esto son bastante elegantes (IMO) pero otros bits son un truco feo
El código más corto (pero los movimientos no óptimos), rastrean la posición de los discos en lugar de la lista de discos en las barras (idea robada descaradamente de la solución Perl)
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 se toma de la línea de comandos.
338 bytes. No está tan mal, ya que este es un lenguaje estáticamente tipificado, y aún es relativamente legible (si reemplaza; con nuevas líneas)
La versión legible sigue (con movimientos más óptimos)
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",""))
Intento con Lua He intentado implementar la solución iterativa de wikipedia , pero no funciona, pero el tiempo que dedico a ello es mayor, así que espero que esto inspire a alguien a adaptarlo. Se analiza todo bien, incluyendo columnas vacías. Extra bueno: hace una bonita impresión de las pilas como en la representación visual en la pregunta.
-- 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