代号高尔夫:河内塔 [英] Code Golf: Towers of Hanoi
问题描述
河内塔是一个难题，如果您不太熟悉它，它的工作方式如下:
The Towers of Hanoi is a puzzle, and if you are not very familiar with it, here is how it works:
比赛场地包括3个杆和 x 个盘，每个盘比上一个大.可以使用以下 规则
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
最后-像这样的比赛场 STARTS :
And finally - the play field STARTS like this:
- 一根带有 x 个盘的杆，其排序方式是最大的在底部，最小的在顶部
- 一根空棒
- 一根空棒
- 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
游戏的 GOAL 是将原始的磁盘堆栈"移动到另一根棒上，即-将所有磁盘放在另一根棒上，因此(再次)最大的位于底部，最小的位于顶部
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
您的目标是使用您选择的编程语言制作一个程序，该程序需要输入(如下所述)并输出解决该职位所需的步骤.
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.
输入
示例输入:
4-3,7-6-5,2-1
输入是一个字符串，由3个部分组成，以逗号分隔.零件是3个杆上的每个圆盘的列表.它们也被分隔，这次用连字符(-)分隔，每个子部分都是一个数字，数字越大，磁盘越大.
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
输出
如上图所示，输入的最左部分是第一号杆，中间是第二号杆，最后一个是3号杆.
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
一个数字列表，用逗号分隔，该数字定义了应该拿起磁盘的杆和应该将磁盘放在其上的杆.只有3个杆，因此只有6种可能的组合(因为必须将磁盘移动到另一杆，而不是同一杆):
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.
您的程序无法产生空输出.如果输入的IS处于原始状态，则只需将磁盘放在DIFFERENT杆上即可.
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.
确保解决方案尽可能快(尽可能少地转弯)-也就是说，不要浪费转弯"12,21,12" ...
Make sure the solution is as fast as possible (as little turns as possible) - that is, don't waste turns by "12,21,12"...
因此，我为您准备了这个小巧的闪存，您可以用它测试程序是否产生了良好的解决方案，而无需写下来.
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.
这里是:河内AlgoTest (等待使其加载然后刷新-死链接:|)
Here it is: Hanoi AlgoTest (wait for it to load then refresh -- Dead link :|)
要使用它，请将输入的程序粘贴到 INPUT 字段，并将程序产生的输出粘贴到 PROCESS 字段.它会以模拟的速度运行，您也可以更改它的速度，并以可视化的方式在底部打印出所有错误.
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.
希望有帮助.
推荐答案
Perl，209(203)个字符
重写以跟踪每个磁盘的位置，而不是每个杆中包含的磁盘列表.
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个字符.
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]:磁盘j的位置
$n:磁盘#1的位置
$m:要移动的磁盘数
$p:将磁盘移动到的位置
$p: the location to move the disks to
&M(r,s):将$m-1磁盘从r移到s.附加到$_并设置@R
&M(r,s): move $m-1 disks from r to s. Appends to $_ and sets @R
sub M内部的替换优化了输出，消除了不必要的步骤.可以将其删除(12个字符)，并且输出仍然有效.
The substitution inside sub M optimizes the output, removing extraneous steps. It could be removed (12 characters) and the output would still be valid.
如果使用命令行开关-apF,调用perl解释器，则可以删除另外12个字符.使用命令行开关的额外6个字符，这使我们的字符数减少到净203个字符:
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/^,//
这篇关于代号高尔夫:河内塔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
