代码高尔夫：河内塔

Question

规则

河内塔是一个谜题，如果您不太熟悉它，它的工作原理如下：

游戏场地由 3 个杆和 x 个圆盘组成，每个圆盘都更大比上一个。圆盘可以放在杆上，遵循以下规则：

• 一次只能移动一个圆盘，并且必须将其移动到另一根杆的顶部，
• 该圆盘必须从一根杆的顶部取出
• 一个圆盘可以移动到某处，仅如果目标杆上最上面的圆盘大于要移动的圆盘

最后- 游戏场地开始如下：

• 一根杆，带有x个圆盘，排序后最大的位于底部，最小的位于底部顶
• 一根空杆
• 一个空杆

游戏的目标是将原来的“一堆”圆盘移到另一根杆上，即将所有圆盘放在另一根杆上杆，所以（再次）最大的在底部，最小的在顶部

实现

您的目标将是用您选择的编程语言编写一个程序，该程序接受输入（如下所述）并输出解决问题所需的步骤的位置。

与往常一样，尽量使其尽可能短。

输入

输入示例：

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

输入是一个字符串，由 3 部分组成，以逗号分隔。这些零件是 3 个杆上每一个上的圆盘列表。它们也被分开，这次用连字符（-），每个子部分都是一个数字，数字越大，磁盘越大。

因此 - 对于上面的输入，这将是一个视觉表示：

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

     ROD 1           ROD 2           ROD 3

输出

正如您在上面的表示中看到的 - 输入的最左边部分是杆号 1，中间是杆号两个，最后一个是棒号 3。

程序的输出应如下所示：

12,23,31,12,23,13

一个数字列表，以逗号分隔，定义应取出磁盘的棒，以及应放置磁盘的棒在。只有 3 根杆，因此只有 6 种可能的组合（因为磁盘必须移动到另一根杆，而不是同一杆）：

12
13
21
23
31
32

注意

输入不必描述处于“原始”状态的字段 - 它可以是中解决了。

您的程序不能产生空输出。如果输入处于原始状态，只需将磁盘放在不同的杆上即可。

输入可以有一个空杆，如下所示：

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

如果输入不是这样的格式，您的程序可能会产生未定义的行为。如果输入无效（例如较大的磁盘放在较小的磁盘上、丢失磁盘、无法解决），则可能会出现这种情况。 输入将始终有效。

确保解决方案尽可能快（尽可能少的转弯） - 也就是说，不要浪费“12,21”的转弯,12"...

测试

所以，我为你准备了这个小闪存，你可以用它来测试你的程序是否产生了一个好的解决方案，而无需写下来或任何东西。

这是： Hanoi AlgoTest （等待它加载然后刷新 -- 死链接 :|)

要使用它，请将程序的输入粘贴到 INPUT 字段，并将程序生成的输出粘贴到 PROCESS 字段。它将以您也可以更改的速度运行模拟，并以视觉表示形式打印出底部的任何错误。

希望有帮助。

Answer 1

Perl, 209 (203) char

重写以跟踪每个磁盘的位置，而不是每个杆上包含的磁盘列表。

<罢工>306 <罢工>291 <罢工>263 <罢工>244
236 213 删除不必要的空格后的 209 个字符。

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]：磁盘 j 的位置

$n：磁盘 #1 的位置

$m：要移动的磁盘数量

$p：将磁盘移动到的位置

&M(r,s)：将 $m-1 磁盘从 r 移动到 s 。附加到 $_ 并设置 @R

sub M 内的替换可优化输出，删除无关步骤。它可以被删除（12 个字符）并且输出仍然有效。

如果使用命令行开关 -apF, 调用 perl 解释器，则可以删除另外 12 个字符。加上命令行开关的额外 6 个字符，这使我们的净字符数减少到 203 个：

# 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/^,//

Answer 2

这是 10 的入门，用 Scala 编写，修改了几次。我不知道有什么问题，也没有其他想法来进一步减少

作为 Scala 脚本运行的动作。

其中的一些部分非常优雅（IMO），但其他部分是一个丑陋的黑客

最短的代码（但不是最佳的移动），跟踪磁盘的位置而不是杆上的磁盘列表（从 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",""))

谜题取自命令行。

338 字节。不算太破烂，因为这是一种静态类型语言，并且仍然相对可读（如果将 ; 替换为换行符）

可读版本如下（具有更优化的移动）

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

Answer 3

Perl 241 char

当然不是最有效的方法，但它确实有效。

更新以抑制最后一个逗号。

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

与空格相同：

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

用法：

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

输出：

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

Answer 4

尝试Lua
我尝试实现 wikipedia 的迭代解决方案，但它并没有真正起作用，但是我花在它上面的时间已经结束了，所以我希望这能激励人们去适应它。
它确实很好地解析了所有内容，包括空列。
额外的好处：它可以很好地打印堆栈，就像问题中的视觉表示一样。

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