Anagrams By Stacks (Incinerator) - スタックを使って文字列を並べ替え
どんな問題？
Anagrams By Stacks
http://www.checkio.org/mission/anagrams-by-stacks/
文字列を並べ替えて別の単語（アナグラム）を作成せよ。例えば「rice」→「cire」など。
スタック1、2と、バッファ0（1文字分）があり、初期状態ではスタック1に「rice」が入っている。
スタック2が「cire」となるよう1文字ずつ移動させていく。
このときの最短の手順を探せ。
引数は、"rice-cire" という形で、最初の文字列と、最終的な文字列が与えられる。
戻り値は、"10,12,12,12,02" というように手順をコンマ区切りで返す。10であれば、スタック1からバッファ0への移動となる。
どうやって解く？
なんか、ハノイの塔みたいな問題だなぁ、というのが第一印象。ハノイの塔は、たしか一番小さな円盤を右に移動、それ以外の円盤を動かせる場所に動かす、の繰り返しで解けるんだっけ？
ハノイの塔との違いは、文字には円盤と違って大小がないので、どの順番でも積み上げられると言うこと。そして、真ん中の棒（バッファ）には一つしか置けないということ。ハノイの塔と同じ解き方では無理かな。
手順を考えてみる
「rice」を「cire」に変換する例を考えてみた。
まず最初に「c」をスタック2の一番底に積む必要がある。（「c」をtargetとする）
- スタック1の最後が「c」(target)で、スタック2が空なら、スタック1からスタック2に移動
- バッファ0が「c」(target)なら、スタック2を一旦すべてスタック1に移動してから、バッファ0からスタック2に移動
- バッファ0とスタック2が空で、スタック1の最後から2番目に「c」(target)があれば、スタック1からバッファ0に移動し、スタック1からスタック2に移動
- それ以外の場合（つまりスタック1の奥の方に「c」(target)がある場合）
- バッファ0に何か入っていればスタック2に移動
- 「c」(target)が出てくるまで、スタック1からスタック2に移動
- 「c」(target)をバッファ0に移動
- スタック2をすべてスタック1に移動
- 「c」(target)をバッファ0からスタック2に移動
これで「c」がスタック2の一番底に移動できた。次は「i」が新たなtargetとなる。この繰り返しでいけるはずだ。
コードを書いてみた。
def checkio(data): first, second = data.split('-') stack1 = list(first) stack0 = [] stack2 = [] result = '' target_index = 0 while stack2 != list(second): target = second[target_index] if len(stack1) > 0 and stack1[-1] == target and len(stack2) == target_index: # スタック1の最後がtargetで、スタック2が空なら、スタック1からスタック2に移動 stack2.append(stack1.pop()) result += '12,' target_index += 1 elif len(stack0) > 0 and stack0[-1] == target: # バッファ0がtargetなら、スタック2をすべてスタック1に移動してから、バッファ0からスタック2に移動 for i in range(len(stack2) - 1, target_index - 1, -1): stack1.append(stack2.pop()) result += '21,' stack2.append(stack0.pop()) result += '02,' target_index += 1 elif len(stack1) > 1 and stack1[-2] == target and len(stack0) == 0 and len(stack2) == target_index: # バッファ0とスタック2が空で、スタック1の2番目にtargetがあれば、スタック1から0＋スタック1から2 stack0.append(stack1.pop()) result += '10,' stack2.append(stack1.pop()) result += '12,' target_index += 1 else: # それ以外なら、バッファ0から2に移動、スタック1でtargetが出てくるまで1から2へ移動、targetを1から0に移動 if len(stack0) > 0: stack2.append(stack0.pop()) result += '02,' while stack1[-1] != target: stack2.append(stack1.pop()) result += '12,' stack0.append(stack1.pop()) result += '10,' return result[:-1] # 最後のカンマを除去
なんか見づらいコードだ。
とりあえず、これでセルフチェック。
……失敗
最後のmirror-mirorrの問題で、もっと短い方法があると表示されてしまった。
失敗例の分析
何が問題かを分析するために、途中経過を表示するためのshow_progress()を作っておいた。
def show_progress(data, answer): def show_stacks(): s1 = format(''.join(stacks[1]), str(len(first))) s2 = format(''.join(stacks[2]), str(len(first))) s0 = format(''.join(stacks[0]), '1') print('[{0}] [{1}] [{2}]'.format(s1, s0, s2)) first, second = data.split('-') stacks = [[], list(first), []] show_stacks() for s in answer.split(','): src, dest = int(s[0]), int(s[1]) stacks[dest].append(stacks[src].pop()) show_stacks()
[スタック1] [バッファ0] [スタック2] の順に並んで表示される。
自分の解答と正解を比較してみた。
| 自分の解答 | 正解 | ||
|---|---|---|---|
| [mirror] [ ] [ ] | [mirror] [ ] [ ] | ||
| 12 | [mirro ] [ ] [r ] | 12 | [mirro ] [ ] [r ] |
| 12 | [mirr ] [ ] [ro ] | 12 | [mirr ] [ ] [ro ] |
| 12 | [mir ] [ ] [ror ] | 10 | [mir ] [r] [ro ] |
| 12 | [mi ] [ ] [rorr ] | 12 | [mi ] [r] [ror ] |
| 12 | [m ] [ ] [rorri ] | 12 | [m ] [r] [rori ] |
| 10 | [ ] [m] [rorri ] | 02 | [m ] [ ] [rorir ] |
| 21 | [i ] [m] [rorr ] | 10 | [ ] [m] [rorir ] |
| 21 | [ir ] [m] [ror ] | 21 | [r ] [m] [rori ] |
| 21 | [irr ] [m] [ro ] | 21 | [ri ] [m] [ror ] |
| 21 | [irro ] [m] [r ] | 21 | [rir ] [m] [ro ] |
| 21 | [irror ] [m] [ ] | 21 | [riro ] [m] [r ] |
| 02 | [irror ] [ ] [m ] | 21 | [riror ] [m] [ ] |
| 12 | [irro ] [ ] [mr ] | 02 | [riror ] [ ] [m ] |
| 12 | [irr ] [ ] [mro ] | 12 | [riro ] [ ] [mr ] |
| 12 | [ir ] [ ] [mror ] | 12 | [rir ] [ ] [mro ] |
| 12 | [i ] [ ] [mrorr ] | 12 | [ri ] [ ] [mror ] |
| 10 | [ ] [i] [mrorr ] | 10 | [r ] [i] [mror ] |
| 21 | [r ] [i] [mror ] | 21 | [rr ] [i] [mro ] |
| 21 | [rr ] [i] [mro ] | 21 | [rro ] [i] [mr ] |
| 21 | [rro ] [i] [mr ] | 21 | [rror ] [i] [m ] |
| 21 | [rror ] [i] [m ] | 02 | [rror ] [ ] [mi ] |
| 02 | [rror ] [ ] [mi ] | 12 | [rro ] [ ] [mir ] |
| 12 | [rro ] [ ] [mir ] | 12 | [rr ] [ ] [miro ] |
| 12 | [rr ] [ ] [miro ] | 12 | [r ] [ ] [miror ] |
| 12 | [r ] [ ] [miror ] | 12 | [ ] [ ] [mirorr] |
| 12 | [ ] [ ] [mirorr] |
惜しい、あと一手。
気付いたのは、正解では序盤にバッファ0に「r」を入れている。これにより、序盤は一手増えているが、後半に二手減らすことができ、結果的に一手短縮しているわけだ。なぜ、「r」を入れたのか、理由はよく分からない。
- 「rr」と2つ重なっていることが理由？
- 「i」は「m」の次に来る文字なので、iが上に来るようにした？
よくわからない。
追加の問題と答え
掲示板（Discuss）を見ていたら、追加の問題と答えが書き込まれていた。これもセルフチェックに追加しておく。
http://www.checkio.org/forum/post/1334/anagrams-by-stacks-examples/
check_solution(checkio, "arrrrrgh-ghrrrrra", 9) check_solution(checkio, "checkio-iocheck", 15) check_solution(checkio, "windows-downsiw", 16) check_solution(checkio, "tests-setts", 11) check_solution(checkio, "solution-tionulos", 17) check_solution(checkio, "superman-namperus", 14) check_solution(checkio, "library-rarybil", 8)
実行してみると、mirror-mirorr 以外にも windows-downsiw と solution-tionulos でも最短手順ではなく失敗。
| [windows] [ ] [ ] | [windows] [ ] [ ] | ||
| 12 | [window ] [ ] [s ] | 12 | [window ] [ ] [s ] |
| 12 | [windo ] [ ] [sw ] | 10 | [windo ] [w] [s ] |
| 12 | [wind ] [ ] [swo ] | 12 | [wind ] [w] [so ] |
| 10 | [win ] [d] [swo ] | 02 | [wind ] [ ] [sow ] |
| 21 | [wino ] [d] [sw ] | 10 | [win ] [d] [sow ] |
| 21 | [winow ] [d] [s ] | 21 | [winw ] [d] [so ] |
| 21 | [winows ] [d] [ ] | 21 | [winwo ] [d] [s ] |
| 02 | [winows ] [ ] [d ] | 01 | [winwod ] [ ] [s ] |
| 12 | [winow ] [ ] [ds ] | 20 | [winwod ] [s] [ ] |
| 12 | [wino ] [ ] [dsw ] | 12 | [winwo ] [s] [d ] |
| 10 | [win ] [o] [dsw ] | 12 | [winw ] [s] [do ] |
| 21 | [winw ] [o] [ds ] | 12 | [win ] [s] [dow ] |
| 21 | [winws ] [o] [d ] | 12 | [wi ] [s] [down ] |
| 02 | [winws ] [ ] [do ] | 02 | [wi ] [ ] [downs ] |
| 10 | [winw ] [s] [do ] | 12 | [w ] [ ] [downsi ] |
| 12 | [win ] [s] [dow ] | 12 | [ ] [ ] [downsiw] |
| 12 | [wi ] [s] [down ] | ||
| 02 | [wi ] [ ] [downs ] | ||
| 12 | [w ] [ ] [downsi ] | ||
| 12 | [ ] [ ] [downsiw] |
| [solution] [ ] [ ] | [solution] [ ] [ ] | ||
| 12 | [solutio ] [ ] [n ] | 10 | [solutio ] [n] [ ] |
| 12 | [soluti ] [ ] [no ] | 12 | [soluti ] [n] [o ] |
| 12 | [solut ] [ ] [noi ] | 12 | [solut ] [n] [oi ] |
| 10 | [solu ] [t] [noi ] | 02 | [solut ] [ ] [oin ] |
| 21 | [solui ] [t] [no ] | 10 | [solu ] [t] [oin ] |
| 21 | [soluio ] [t] [n ] | 21 | [solun ] [t] [oi ] |
| 21 | [soluion ] [t] [ ] | 21 | [soluni ] [t] [o ] |
| 02 | [soluion ] [ ] [t ] | 01 | [solunit ] [ ] [o ] |
| 12 | [soluio ] [ ] [tn ] | 20 | [solunit ] [o] [ ] |
| 12 | [solui ] [ ] [tno ] | 12 | [soluni ] [o] [t ] |
| 10 | [solu ] [i] [tno ] | 12 | [solun ] [o] [ti ] |
| 21 | [soluo ] [i] [tn ] | 02 | [solun ] [ ] [tio ] |
| 21 | [soluon ] [i] [t ] | 12 | [solu ] [ ] [tion ] |
| 02 | [soluon ] [ ] [ti ] | 12 | [sol ] [ ] [tionu ] |
| 10 | [soluo ] [n] [ti ] | 12 | [so ] [ ] [tionul ] |
| 12 | [solu ] [n] [tio ] | 12 | [s ] [ ] [tionulo ] |
| 02 | [solu ] [ ] [tion ] | 12 | [ ] [ ] [tionulos] |
| 12 | [sol ] [ ] [tionu ] | ||
| 12 | [so ] [ ] [tionul ] | ||
| 12 | [s ] [ ] [tionulo ] | ||
| 12 | [ ] [ ] [tionulos] |
一から考え直してみる
なんか、根本的に違う気がしてきた。最短手順を探すってことは、最短経路問題ってことで、これもBFSやA*で解くような問題なのかな？
迷路の探索と比較して考えてみる。
- 上下左右への移動は、毎回のアクション('10'や'12'など)で置き換えられる。
- 現在位置とは、現在のスタックの状態と考える。
- スタートはスタック1に'rice'が入った状態、ゴールはスタック2に'cire'が入った状態と考える。
- 壁や障害物は、アクションが実行できない状態（例えばスタックが空なのにpop()する）だと考える。
こう考えると、迷路の探索と同じ考え方でいけそうだ。
BFSを使ったコード
2つのスタックとバッファは、文字列のタプルで表現する。
バッファ0が[m]、スタック1が[ir]、スタック2が[ror]なら、('m','ir','ror')となる。
def checkio(data): def get_next(stacks, action): # 次の行動("10"や"02"など)によって変化するスタックの状態を返す。 src, dest = int(action[0]), int(action[1]) dest_max_length = 1 if dest == 0 else len(first) if stacks[src] == '' or len(stacks[0]) >= dest_max_length: return None else: r = list(stacks) r[dest] += r[src][-1] r[src] = r[src][:-1] return tuple(r) def get_path(): # visitedフラグを逆にたどってスタートからの経路を作成 pt = goal result = '' while pt != start: prev, action = visited[pt] result = action + ',' + result pt = prev return result[:-1] first, second = data.split('-') start = ('', first, '') # 初期のスタックの状態 goal = ('', '', second) # 最終的なスタックの状態 visited = dict() q = [start] while len(q) > 0: current_stacks = q.pop(0) if current_stacks[2] == second: return get_path() for act in ("12", "10", "01", "02", "20", "21"): next_stacks = get_next(current_stacks, act) if next_stacks is not None and next_stacks not in visited: visited[next_stacks] = (current_stacks, act) q.append(next_stacks)
BFSなので、Queueを使っている。（q.append()で追加、q.pop(0)で取り出し。）
いつもと同じようなコードだが、これでいけるはず。
まずはセルフチェック……OK!
Run & Check……クリア～!
これまた、あんなに苦労した問題が、あっさりと解けてしまった。
BFSってすごいなぁと思う反面、結局いつもこのパターンかと少しがっかり。
もしA*探索を使うなら、ゴールまでの距離を何に置き換えればいいんだろう？
最終的なスタックの状態にどれだけ近いかを数値化、という感じかな。
まあ、それはまた後日のチャレンジということで、今日はここまで。
