Word ladder

問題文

[12/4/2012] Challenge #114 [Easy] Word ladder steps : dailyprogrammer

ワード・ラダーは、単語を一度に一文字だけ変更することによって生成される単語の順列のことである。例:

cold → cord → card → ward → warm

この問題では、四文字単語の辞書を用いて、一つの単語が与えられたさい、一度に一文字変更する操作によって作ることのできるすべての単語を列挙してください。

辞書(RAWを選んで保存):selected four-letter words - Pastebin.com

入力例:
puma
出力例
duma
pima
puja
pula
pump
puna
pupa

上記リンクの辞書リストからは、bestはいくつの単語を作ることができるだろうか?
ボーナス問題1:ある単語は一度の操作で33個の別の単語を作ることができる。それは何か?
ボーナス問題2:3回以下の変更操作で、bestはいくつの単語を作ることができるだろうか。

解答

全探索でも(この問題サイズなら)そんなに時間はかからない。

def neighbor_words(target_word, dictionary):
    neighbor_words = []
    for word in dictionary:
        count = 0
        word_length = len(word)
        for i in range(word_length):
            if word[i] == target_word[i]:
                count += 1
        if count == word_length-1:
            neighbor_words.append(word)
    return neighbor_words

def neighbor_words_with_depth(target_word, dictionary, depth=3):
    words = set([target_word])
    for i in range(depth):
        w = []
        for word in words:
            w.extend(neighbor_words(word, dictionary))
        words.update(set(w))
    return words

def main():
    best = "best"
    with open("./raw.txt") as f:
        lines = f.readlines()
        words = [line.rstrip() for line in lines]
    # Problem
    print neighbor_words(best, words)
    # => ['bast', 'beat', 'beet', 'belt', 'bent', 'bust', 'gest', 'hest', 'jest', 'lest', 'nest', 'pest', 'rest', 'test', 'vest', 'west', 'zest']

    # Bonus1
    for word in words:
        n = len(neighbor_words(word, words))
        if n == 33:
            print word
    # => care

    #Bonus2
    print len(neighbor_words_with_depth(best, words, 3))
    # => 575

if __name__ == "__main__":
    main()