@davidfeng88/

word_chain

Python

https://github.com/davidfeng88/CodingSamples/tree/master/word_chain

fork
loading
Files
  • main.py
  • dict.txt
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
from collections import deque
from string import ascii_lowercase

class WordChainer:
    def __init__(self):
        with open("./dict.txt") as dict:
            self.dictionary = { line.strip() for line in dict }

    def find_chain(self, source, target):
        self.setup(source, target)
        while self.to_explore:
            current_word = self.to_explore.popleft()
            self.explore_word(current_word)
            if self.found:
                self.output_chain()
                return
        print("Could not find a chain")

    def setup(self, source, target):
        self.explored = { source: None } # key: word; value: the previous word
        self.to_explore = deque([source])
        self.target = target
        self.found = False

    def explore_word(self, current_word):
        for adjacent_word in self.adjacent_word_gen(current_word):
            self.explored[adjacent_word] = current_word
            if adjacent_word == self.target:
                self.found = True
                return
            self.to_explore.append(adjacent_word)

    def adjacent_word_gen(self, current_word):
        for index, current_letter in enumerate(current_word):
            for new_letter in ascii_lowercase:
                if new_letter == current_letter:
                    continue
                candidate = current_word[:index] + new_letter + current_word[index + 1:]
                if candidate in self.dictionary and candidate not in self.explored:
                    yield candidate

    def output_chain(self):
        print("Chain found")
        chain = self.build_chain()
        print(chain)

    def build_chain(self):
        reversed_chain = []
        current_word = self.target
        while current_word:
            reversed_chain.append(current_word)
            previous_word = self.explored[current_word]
            current_word = previous_word
        chain = reversed_chain[::-1]
        return chain

wc = WordChainer()
print("Example: wc.find_chain('duck', 'ruby')")
wc.find_chain('duck', 'ruby')