CodeIQ：ハノイの塔ではありません

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ハノイの塔ではありません」（CodeIQ）を参照してください。

問題の概要

問題を引用します。
【概要】
「鷲」「鮫」「豹」と名付けられた三本の棒と、中心に穴が空いた円盤が何枚かあります。
最初は「鷲」の棒に、全ての円盤が刺さっています。
円盤を一回に一枚ずつどれかの棒に移動させることができますが、以下の条件を常に満たさなくてはいけません：

どの円盤も、自分よりも上には、自分よりも大きな円盤は1枚以下しかない。

例をいくつか挙げます：
上←→下説明
1, 2, 3, 4いずれの円盤も、自分より上に自分よりも大きな円盤がないので OK
7, 7, 7, 7いずれの円盤も、自分より上に自分よりも大きな円盤がないので OK
7, 6, 7, 7「6」より上に「6」よりも大きな円盤があるが、1枚なのでOK
2, 1, 4, 3, 6, 5「1」「3」「5」より上に自分よりも大きな円盤があるが、いずれも1枚なのでOK
2, 3, 1「1」より上に「1」より大きな円盤が2枚あるのでNG

最初「鷲」に、上から順に 1, 2, 3, 4 のサイズの円盤が刺さっている場合、例えば
手数鷲鮫豹
01234
12341
23421
34321
44321
52431
61243

のように、6手で全てを「鮫」に移動することができます。

で。
全ての円盤を「鮫」に移動するのに必要な最小の手数を計算して下さい。

【入出力】
入力は
1234
のようになっています。
これは「鷲」に刺さっている円盤の大きさ(1〜9 の整数)を上から順に書いたものです。
区切り文字はありません。

出力は、
6
のような感じです。
最小の手数を普通に10進数で出力して下さい。

【例】
入力出力
12346
1234
13145

【補足】
不正な入力に対処する必要はありません。
円盤の枚数は 1枚 以上、 7枚 以下です。
ゴールの状態としては「鮫」に全て刺さっていればOKです。元の順序を維持している必要はありません。

私のプログラム

Rubyで解答しています。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#!/usr/bin/ruby
 
$Memo = {}
 
def check(str)
    (str.size-1).downto(2){|i|
        big = 0
        (i-1).downto(0){|j|
            big += 1 if str[i] < str[j]
            return false if big > 1
        }
    }
    return true
end
 
def move(board, from, to)
    return nil if board[from].empty?
 
    f = board[from][1..-1]
    t = board[from][0] + board[to]
    return nil if check(t) == false
 
    if (from == 0) && (to == 1) then    ret = [f, t, board[2]]
    elsif (from == 0) && (to == 2) then ret = [f, board[1], t]
    elsif (from == 1) && (to == 2) then ret = [board[0], f, t]
    elsif (from == 1) && (to == 0) then ret = [t, f, board[2]]
    elsif (from == 2) && (to == 0) then ret = [t, board[1], f]
    elsif (from == 2) && (to == 1) then ret = [board[0], t, f]
    end
 
    j = ret.join(",")
    return nil if $Memo[j]
 
    $Memo[j] = true
#   printf("%s, from=%d, to=%d, %s\n", board, from, to, ret)
    return ret
end
 
def solve(st)
    queue = [[st, "", ""]]
    $Memo[st + ",,"] = true
    mv = [[0,1], [0,2], [1,2], [1,0], [2,0], [2,1]]
 
    cnt = 1
    while true
        nq = []
 
        while !queue.empty?
            b = queue.shift
 
            for m in mv
                x = move(b, m[0], m[1])
                if x == nil then next
                elsif (x[0].empty? && x[2].empty?) || (x[0].empty? && x[1].empty?) then return cnt
                else nq << x if x != nil
                end
            end
        end
 
        queue = nq
        cnt += 1
    end
end
 
# main
while line = gets
    line.strip!
    next if line.empty?
 
    p solve(line)
end

解説

ハノイの塔の変形では無いような気がします。

考え方

ハノイの塔をベースにちょっと考えてみましたがどうも違うのでは無いかと思います。

うまい手順を思いつかなかったので単純に総当たりでどうかと思いました。
気になるのが計算量です。見積もれていないのですが、それほど多く無い気がしたので総当たりでやることにしました。

問題文では「鮫」に移すことになっていますが最小手数を求めるだけなので、別に「豹」に移しても構いません。なので適当に移して「鮫」か「豹」に全部移せたら良いことにします。

次に求めるのは最小手数なので最小手数を見つけたらそれ以上やる必要はありません。再帰でやった場合、最初に見つかったパターンが最小手数かはわからないので手順ごとのループにしました。

main

入力値をsolve()に渡し、結果を印字します。

solve(st)

引数stは最初の並びです。

queueに最初の状態を入れます。要素は[鷲,鮫,豹]にある円盤です。最初は全部「鷲」にあるのでその状態を設定します。
$Memoは一度発生した状態をキー、値をtrueとして記録します。これは同じ状態を無視するために使用します。
mvは円盤をどこからどこに移動するかを表すパターンで、0は「鷲」、1は「鮫」、2は「豹」を表します。
cntは操作回数です。

45〜62行目のループで「鮫」か「豹」に全部の円盤が移動するまで操作を繰り返します。「鮫」と「豹」を区別しないのは考え方に書いた通りです。

48〜58行目のループでqueueに入っている状態を1つずつ取り出し操作します。

mvの移動パターン全てに対してmove()で移動を処理します。
move()は移動が不正か過去に出現した状態になったらnilを返します。
nilで無いときに「鮫」か「豹」に全部の円盤があれば、つまりその他の場所に円盤がなければ、終了条件を満たしたのでcntを返却して終わります。
nilでなく終了条件を満たしていなければ次回操作の開始状態としてnqに追加します。

48〜58行目のループで終了条件に達しなければqueueをnqで更新し、操作回数cntをインクリメントして繰り返します。

move(board, from, to)

円盤の移動を行います。
boardは[鷲,鮫,豹]の円盤の状態です。
fromは移動元の要素番号、toは移動先の要素番号です。

移動元に円盤がなければ不正なのでnilを返します（17行目）。
19行目で移動元から円盤をとり、20行目で移動先に円盤を移します。
21行目で円盤が条件を満たして積まれているかをチェックします。不正な積み方になっていた（check()がfalseを返した）場合、nilを返します。

23〜29行目は移動パターンごとに次の状態の配列を作成しています。

31〜32行目はそのパターンが過去に出現したかをチェックし、出現しているならnilを返します。$Memoに過去の出現パターンをキーとして記録していますが、キーはパターンを","で連結した文字列になっているのでjoin()しています。

新たなパターンならそれを$Memoに記録し、パターンを返却します。

check(str)

円盤の積まれ方が条件に合っているかをチェックします。
もっとうまい方法がありそうですが単純に一番下のものから上から3番目のものまで、それぞれ自分の上に自分より大きな値が最大1つしか無いかを調べています。

ちなみに一番上の円盤は上に何も無いので調べる必要がなく、上から2番目の円盤もどんな円盤が乗っていても条件を満たすので調べる必要がありません。

雑感

非常に素朴なコードですがこれで大丈夫でした。
ただし、円盤の数が8枚になったら多分時間切れです。
もっとうまい方法があるんだろうと思います。