code-golf - コードゴルフ: タワーズオブハノイ

Question

ルール

ハノイの塔はパズルです。よく知らない場合は、次のように操作します。

プレイフィールドは 3 つのロッドとx個のディスクで構成され、次のディスクは前のディスクよりも大きくなっています。ディスクは、次のルールでロッドに取り付けることができます。

一度に移動できるディスクは 1 つだけであり、別のロッドの上で移動する必要があります
ディスクはロッドの上部から取らなければなりません
ターゲットロッドの最上部のディスクが移動するディスクよりも大きい場合にのみ、ディスクをどこかに移動できます

そして最後に - プレイフィールドは次のように始まります:

x個の円盤があり、最大のものを下に、最小のものを上に並べた棒
空の棒
空の棒

ゲームの目標は、ディスクの元の「スタック」を別のロッドに移動することです。つまり、すべてのディスクを別のロッドに配置します。したがって、(ここでも)最大のものは下に、最小のものは上になります。

実装

あなたの目標は、選択したプログラミング言語でプログラムを作成することです。このプログラムは、入力 (以下で説明) を受け取り、位置を解決するために必要なステップを出力します。

いつものように、できるだけ短くするようにしてください。

入力

入力例:

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

入力は、コンマで区切られた 3 つの部分で構成される文字列です。パーツは、3 つのロッドのそれぞれにあるディスクのリストです。今回はハイフン ( - ) で区切られており、各サブパートは数字であり、数字が大きいほどディスクが大きくなります。

したがって、上記の入力の場合、これは視覚的な表現になります。

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

     ROD 1           ROD 2           ROD 3

出力

上の図でわかるように、入力の一番左の部分がロッド番号 1、中央がロッド番号 2、最後の部分がロッド番号 3 です。

プログラムの出力は次のようになります。

12,23,31,12,23,13

ディスクを取り出すロッドとディスクを取り付けるロッドを定義する、コンマで区切られた番号のリスト。ロッドは 3 つしかないため、考えられる組み合わせは 6 つだけです (ディスクを同じロッドではなく別のロッドに移動する必要があるため)。

ノート

入力は、「元の」状態のフィールドを記述する必要はありません。解決の途中でもかまいません。

あなたのプログラムはヌル出力を生成できません。入力が元の状態の場合は、ディスクを別のロッドに入れるだけです。

入力には、次のように空のロッドを含めることができます。

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

入力がこのようにフォーマットされていない場合、プログラムは未定義の動作を引き起こす可能性があります。そのため、入力が有効でない場合 (小さいディスクに大きなディスクが接続されている、ディスクが見つからない、解決できないなど) は可能です。入力は常に有効です。

ソリューションが可能な限り高速であることを確認してください (可能な限り少ないターン)。つまり、「12,21,12」でターンを無駄にしないでください...

テスト

そこで、この小さなフラッシュを用意しました。これを使用すると、プログラムが適切なソリューションを生成したかどうかを書き留めたり何もせずにテストしたりできます。

ここにあります：Hanoi AlgoTest（ロードしてから更新するのを待ちます-デッドリンク:|）

これを使用するには、プログラムへの入力をINPUTフィールドに貼り付け、プログラムによって生成された出力をPROCESSフィールドに貼り付けます。変更可能な速度でシミュレーションを実行し、視覚的な表現を使用して、下部にエラーを出力します。

それが役に立てば幸い。

score 4 · Accepted Answer

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

score 4 · Accepted Answer

これは Scala の 10 のスターターで、数回改訂されています。私は何の問題も知りませんし、動きをさらに減らすための他のアイデアもありません

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

score 1 · Accepted Answer

パール 241 文字

確かに最も効率的な方法ではありませんが、うまくいきます。

最後のコンマを抑制するように更新されました。

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

score 0 · Accepted Answer

Lua での試みウィキペディアから反復ソリューションを実装しようとしましたが、実際には機能しませんが、それに費やしている時間はなくなったので、これが誰かにそれを適応させるよう促すことを願っています. 空の列を含め、すべてを適切に解析します。おまけ：質問の視覚的表現のように、スタックをきれいに印刷します。

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

code-golf - コード ゴルフ: タワーズ オブ ハノイ

ルール

実装

ノート

テスト

4 に答える 4

Perl、209 (203) 文字

パール 241 文字

使用法：

出力：

Related

Reference

code-golf - コードゴルフ: タワーズオブハノイ