Digits Doublets (Alice In Wonderland) - 数字の変化

どんな問題？

Digits Doublets
http://www.checkio.org/mission/digits-doublets/

与えられた数字のリストを使って、最初の数字から1桁ずつ変更して、最後の数字まで変えていく。
このときの最短の並びを探せ。

数字は100以上1000未満の3桁の整数とする。

数字のリストが [123, 991, 323, 321, 329, 121, 921, 125, 999] であれば、123 ⇒ 121 ⇒ 921 ⇒ 991 ⇒ 999 のように、最初の数字(123)から、最後の数字(999)まで変化させていく。この場合の答えは、[123,121,921,991,999] となる。

例題：

checkio([123, 991, 323, 321, 329, 121, 921, 125, 999]) == [123, 121, 921, 991, 999]
checkio([111, 222, 333, 444, 555, 666, 121, 727, 127, 777]) == [111, 121, 127, 727, 777]
checkio([456, 455, 454, 356, 656, 654]) == [456, 454, 654]  # or [456, 656, 654]

どうやって解く？

最短経路を求めるのだから、いつものようにBFSを使えばいいのかな。
ええっと、BFSはキューを使うんだっけ。（q.append()で追加、q.pop(0)で取り出し。）

迷路の探索と同じように

• visited辞書を作って、探索済みなら一つ前の要素を入れておく。
• キューから要素を取り出す。
• ゴールについたら、visited辞書からルートを計算する。
• ゴールでなければ、未探索で隣接する要素をキューに入れる。

という流れかな。

隣りに来ることができる数字は、3桁のうち2桁が同じであればいいので、

def is_adjacent(a, b):
    return len([i for i in range(3) if str(a)[i] == str(b)[i]]) == 2

としてチェックできる。

まとめ

def checkio(numbers):
    def is_adjacent(a, b):
        # aとbが隣接するならTrue
        return len([i for i in range(3) if str(a)[i] == str(b)[i]]) == 2

    def get_adjacent(num):
        # 未探索で隣接する数字を取得
        unvisited = set(numbers) - set(visited.keys())
        return [x for x in unvisited if is_adjacent(num, x)]

    def get_route():
        # visited辞書からルートを逆にたどる
        result = []
        n = numbers[-1]
        while n:
            result.insert(0, n)
            n = visited[n]
        return result

    visited = {numbers[0]: None}
    queue = [numbers[0]]
    while queue:
        cur = queue.pop(0)
        if cur == numbers[-1]:
            return get_route()
        for adj in get_adjacent(cur):
            queue.append(adj)
            visited[adj] = cur
    return []

http://www.checkio.org/mission/digits-doublets/publications/natsuki/python-3/first/

他の人の答え

そういえば、list.pop(0)は遅いから、collection.dequeを使った方がいいんだっけ。
append()で追加、popleft()で左の要素を取り出せる。_〆(ﾟ▽ﾟ*)メモメモ

CheckiOを始めた頃は、BFSもDFSもまったく知らなかったのに、なんか成長したなぁとしみじみ。