Code Golf:河内的塔楼

Question

规则

河内之塔是一个难题,如果你不熟悉它,它的工作原理如下:

游戏区域包括3个杆和x个盘,每个盘下一个比前一个更大.可以将这些磁盘放在杆上,这些规则如下:

• 一次只能移动一个磁盘,并且必须在另一个磁带的顶部移动
• 磁盘必须从杆的顶部取出
• 磁盘可以某处移动,仅如果在目标棒的最上面的磁盘是更大的一个比要被移动

最后-游戏领域STARTS是这样的:

• 一个带有x个磁盘的杆,按顺序分类,使最大的位于底部,最小的位于顶部
• 一根空杆
• 一根空杆

游戏的目标是将原始"堆叠"的磁盘移动到另一根杆上,即 - 将所有磁盘放在另一根杆上,因此(再次)最大的是在底部,最小的在顶部

履行

您的目标是使用您选择的编程语言编写程序,接受输入(如下所述)并输出解决位置所需的步骤.

一如既往,尽量让它尽可能短.

输入

输入示例:

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

输入是一个字符串,由3个部分组成,以逗号分隔.这些部件是3根杆上每个杆上的磁盘列表.它们也是分开的,这次是连字符( - ),每个子部分都是一个数字,数字越大,磁盘越大.

所以 - 对于上面的输入,这将是一个直观的表示:

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

     ROD 1           ROD 2           ROD 3

产量

正如您在上面的表示中所看到的那样 - 输入的最左侧部分是第一个杆,中间是第二个杆,最后一个是第3个杆.

程序的输出应如下所示:

12,23,31,12,23,13

一个数字列表,用逗号分隔,用于定义应该取出磁盘的磁带,以及磁盘应放在的磁带上.只有3个杆,因此只有6种可能的组合(因为盘必须移动到另一个杆,而不是相同的杆):

12
13
21
23
31
32

笔记

输入不必描述处于"原始"状态的字段 - 它可以是中间求解的.

您的程序无法生成空输出.如果输入IS处于原始状态,只需将磁盘放入不同的杆.

输入可以有一个空杆,如下所示:

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

如果输入的格式不是这样,则程序可能会产生未定义的行为.因此,如果输入无效(例如较小的磁盘,丢失的磁盘,无法解决),它就可以.输入始终有效.

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

测试

所以,我为你准备了这个小闪光灯,你可以用它来测试你的程序是否产生了一个好的解决方案,而不是写下来或任何东西.

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

要使用它,请将程序的输入粘贴到INPUT字段,并将程序生成的输出粘贴到PROCESS字段.它将运行模拟,速度也可以改变,通过可视化表示,打印出底部的任何错误.

希望能帮助到你.

Answer 1

Perl，209 (203) 字符

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

删除不必要的空格后的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 个字符）并且输出仍然有效。

如果使用命令行开关调用 perl 解释器，则可以删除另外 12 个字符-apF,。加上命令行开关的额外 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/^,//