問題文
[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()