code-golf - Code Golf : Towers of Hanoi

Question

锁定。这个问题及其答案是 locked，因为这个问题离题但具有历史意义。它目前不接受新的答案或交互。








规则

汉诺塔是一个谜，如果你不是很熟悉它，这里是它的工作原理:

游戏场由 3 根杆和 x 个圆盘组成，下一个比上一个大。磁盘可以放在杆上，这些 规则 :

一次只能移动一个磁盘，并且必须在另一个杆的顶部移动

必须从杆的顶部取出磁盘

磁盘可以移动到某处，前提是目标杆上最上面的磁盘大于要移动的磁盘

最后 - 比赛 field STARTS 像这样:

一根棒，有 x 个圆盘，排序后最大的在底部，最小的在顶部

空杆

空杆

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

执行

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

与往常一样，尽量缩短它。

输入

示例输入:

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

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

所以 - 对于上述输入，这将是一个视觉表示:

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

     ROD 1           ROD 2           ROD 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) 字符

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

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