-
Notifications
You must be signed in to change notification settings - Fork 0
/
word_ladder_puzzle.py
171 lines (143 loc) · 5.19 KB
/
word_ladder_puzzle.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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
# Assignment 2 - Puzzle Game
#
# CSC148 Summer 2017, University of Toronto
# ---------------------------------------------
"""Word ladder module.
Your task is to complete the implementation of this class so that
you can use it to play Word Ladder in your game program.
Rules of Word Ladder
--------------------
1. You are given a start word and a target word (all words in this puzzle
are lowercase).
2. Your goal is to reach the target word by making a series of *legal moves*,
beginning from the start word.
3. A legal move at the current word is to change ONE letter to get
a current new word, where the new word must be a valid English word.
The sequence of words from the start to the target is called
a "word ladder," hence the name of the puzzle.
Example:
Start word: 'make'
Target word: 'cure'
Solution:
make
bake
bare
care
cure
Note that there are many possible solutions, and in fact a shorter one
exists for the above puzzle. Do you see it?
Implementation details:
- We have provided some starter code in the constructor which reads in a list
of valid English words from wordsEn.txt. You should use this list to
determine what moves are valid.
- **WARNING**: unlike Sudoku, Word Ladder has the possibility of getting
into infinite recursion if you aren't careful. The puzzle state
should keep track not just of the current word, but all words
in the ladder. This way, in the 'extensions' method you can just
return the possible new words which haven't already been used.
"""
import copy
from puzzle import Puzzle
CHARS = 'abcdefghijklmnopqrstuvwyz'
class WordLadderPuzzle(Puzzle):
"""A word ladder puzzle."""
# TODO: add to this list of private attributes!
# === Private attributes ===
# @type _words: list[str]
# List of allowed English words
def __init__(self, start, target):
"""Create a new word ladder puzzle with given start and target words.
Note: you may add OPTIONAL arguments to this constructor,
but you may not change the purpose of <start> and <target>.
@type self: WordLadderPuzzle
@type start: str
@type target: str
@rtype: None
"""
# Code to initialize _words - you don't need to change this.
self._words = []
with open('wordsEn.txt') as wordfile:
for line in wordfile:
self._words.append(line.strip())
self.start = start
self.target = target
self._hist = [start]
def __str__(self):
"""
Return a string of every move that is made in the word ladder puzzle
@type self: WordLadderPuzzle
@rtype: str
"""
return ' '.join(self._hist)
def is_solved(self):
"""
return if the WordLadderPuzzle is solved
@type self: WordLadderPuzzle
@rtype: bool
"""
return self.start == self.target
def __eq__(self, other):
"""
return if the other and self are equal
@type self: WordLadderPuzzle
@type other: WordLadderPuzzle
@rtype: bool
"""
return self.start == other.start and self.target == other.target
def extensions(self):
"""Return a list of possible new states after a valid move.
The valid move must change exactly one character of the
current word, and must result in an English word stored in
self._words.
You should *not* perform any moves which produce a word
that is already in the ladder.
The returned moves should be sorted in alphabetical order
of the produced word.
@type self: WordLadderPuzzle
@rtype: list[WordLadderPuzzle]
"""
lst = []
lst2 = []
word = list(self.start)
wordcopy = copy.copy(word)
check = list(CHARS)
for i in range(len(word)):
for j in check:
wordcopy[i] = j
if "".join(wordcopy) in self._words and not "".join(wordcopy) in self._hist:
lst.append("".join(wordcopy))
wordcopy = copy.copy(word)
sort = sorted(lst)
for i in sort:
worr = WordLadderPuzzle(i,self.target)
newhist = copy.copy(self._hist)
newhist.append(i)
worr._hist = newhist
lst2.append(worr)
return lst2
def move_finder(self, puzzle_end):
"""
find the string that was made previously with the puzzle_end
@type self: WordLadderPuzzle
@type puzzle_end: WordLadderPuzzle
@rtype: str
"""
return puzzle_end._hist[-1]
def move(self, move):
"""
Make a move and return the state of the system
@type self: WordLadderPuzzle
@type move: str
@rtype: WordLadderPuzzle
"""
ext = self.extensions()
moves = []
for i in ext:
moves.append(i.start)
if not move in moves:
raise ValueError("Invalid Word")
word = WordLadderPuzzle(move,self.target)
newhist = copy.copy(self._hist)
newhist.append(move)
word._hist = newhist
return word