私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「社殿の柱を付け替えて！」（CodeIQ）を参照してください。
Pythonで解答しています。
#!/usr/local/bin/python3
End = ("JBCDEFGHIA",0)
Start = ("ABCDEFGHIJ",9)
Map = [ # 地図
[5,6], #A
[5,6,7], #B
[6,7,8], #C
[7,8,9], #D
[8,9], #E
[0,1], #F
[0,1,2], #G
[1,2,3], #H
[2,3,4], #I
[3,4], #J
]
'''
# デバッグ用の要素数の少ないテストデータ
End = ("FBCDEA",0)
Start = ("ABCDEF",Last)
Map = [ # 地図
[3,4], #A
[3,4,5], #B
[4,5], #C
[0,1], #D
[0,1,2], #E
[1,2], #F
]
'''
'''
デバッグ用
履歴を印字する
'''
def printMemo(memo):
for k,v in memo.items():
print("%s:%d" % (k,v))
'''
位置情報を更新する
swap(("JBCDEFGHIA",0), 0, 4)なら("ABCDJFGHIE",4)を返す
@param o ("位置文字列", 最後の文字の現在位置)のタプル
@param f 現在の最後の文字の位置
@param t 移動後の最後の文字の位置
'''
def swap(o, f, t):
k = ""
for i,c in enumerate(o[0]):
if i==f:
k += o[0][t]
elif i==t:
k += o[0][f]
else:
k += o[0][i]
return (k, t)
'''
探索を行う。
Start -> EndとEnd->Startの両方を同時に探索する。
どこかで同じ配列になるはずなので、同じ配列が反対側の探索で発見されていたら探索をやめる。
結果はそれまでに費やした両方の探索回数の合計+1（1足すのは見つかった時点で最後の移動を
処理しないため、その分を加える）
'''
def solve():
memo1 = {Start:0} # 履歴を初期化する
q1 = [Start] # 探索キューにスタート地点を登録する
f1 = None
memo2 = {End:0}
q2 = [End]
f2 = None
while True:
# StartからEnd方向の探索
f1 = q1.pop(0) # 現在の位置情報
if f1 == End:
break
if f1 in memo2:
break
p1 = f1[1] # 現在の位置情報から位置の要素番号を取得する
c1 = memo1[f1] # 現在の地点までのコストを取得する
# 隣接する位置を探索
for np in Map[p1]:
n = swap(f1, p1, np) # 次の位置情報を生成
# すでに探索済みなら無視
if n in memo1:
continue
q1.append(n)
memo1[n] = c1+1
# EndからStart方向の探索
f2 = q2.pop(0)
if f2 == Start:
break
if f2 in memo1:
break
p2 = f2[1] # 現在の位置情報から位置の要素番号を取得する
c2 = memo2[f2] # 現在の地点までのコストを取得する
for np in Map[p2]:
n = swap(f2, p2, np)
if n in memo2:
continue
q2.append(n)
memo2[n] = c2+1
# 見つかった時にその分の移動をしていないので1を加える
return memo1[f1] + memo2[f2] + 1
if __name__ == "__main__":
ret = solve()
print(ret)
ちょっと汚いコードになっています。solve()の中に同じような処理の繰り返しがあるので本来ならリファクタリングの必要がありますが、そのまま説明します。
基本的には幅優先探索の応用で解くことができますが1方向の探索では時間がかかりすぎるので両方向からの探索が必要です。両方向の探索とはスタートの状態からゴールの状態を目指す探索と、ゴールの状態からスタートの状態を目指す探索を組み合わせるということで、どこかで同じ状態が発生するので同じ状態を見つけたら探索を終わるということになります。
Startは開始状態、Endは終了状態を表します。タプルになっており、文字列が現在の柱の並びを1次元化したもの、数字はJの柱の位置（何文字目か）を表します。
Mapは要素番号が柱の位置に対応し、要素はその場所にある柱の異動先候補を表します。つまり、Jの柱の位置（0〜9）をMapの要素番号に与えれば次どこに移動可能かがわかるようになっています。
これで問題を解きます。
前述の通り、基本的には幅優先探索で、現在のJの位置から移動可能な場所を探索し、候補地点に移動した後でまた候補地点を探索するということを繰り返します。
memo1とmemo2は探索履歴、q1とq2はキューで、f1とf2はキューから取り出した現在の探索地点です。それぞれ1がスタートからゴール方向の探索用、2がゴールからスタート方向の探索用です。
memoはタプル("現在の柱の配列", Jの位置)をキーとし、その状態までかかった手順を値とするディクショナリです。memo1の初期状態はスタートの状態、memo2にはゴールの状態が入ります。
73行目〜112行目のループでキューから現在位置を取り出し、新たな地点に移動するという処理を行います。74行目〜93行目がスタート→ゴール方向、95行目〜112行目がゴール→スタート方向の探索です。方向が逆なだけで同じ処理なのでスタート→ゴール方向だけを説明します。
75行目で現在の探索地点をキューから取り出します。
76〜79行目の条件は終了条件のチェックです。ゴール状態になるか、反対方向からの探索履歴に同じ状態があれば終了します。実際にはゴールに到達することはなく、反対方向の探索履歴で同じ状態を発見して終了します。
85行目のループで移動可能な場所を全てチェックし、柱を移動します。swap()は柱の位置を交換したタプル("現在の柱の配列", Jの位置)を返す関数で、これが移動をシミュレートします。
89行目の条件は同じ配置が2回現れた場合、2回目以降は無駄なので以降探索の候補にしないためです。
92行目で次の探索候補をキューに追加し、93行目で履歴を追加します。
ループがブレークした時、最後の状態のそれぞれの方向の移動コストの合計が全体での移動コストになります。ただし、最後の交換がされる前に見つけるので最後の交換分の移動を+1する必要があります。
最初、「必ずJを動かす必要があり、A〜I同士での交換は行わない」という条件を見落としていて「何なんだ？ 手計算でもわかるくらい何だけど」と思っていました。やってみたら当然全然違う結果で改めて問題をきちんと読み直してわかったという状態でした。
この問題はヒントが非常に役に立ちました。前述の間違いで1回リジェクトされてプログラムを修正して（単方向の探索で）ローカルでテストしたら全然時間オーバーでしたが、ヒントが頭に残っていたので割とすぐに修正できました。