-
Notifications
You must be signed in to change notification settings - Fork 2
/
puzzle.py
110 lines (94 loc) · 4.03 KB
/
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
import json
import re
class Puzzle:
"""
A word search puzzle is a square grid of letters and a list of words found somewhere in the grid.
This solver was made as a complement to https://github.com/joshbduncan/word-search-generator
"""
DIRECTIONS = {
"N": {"x": 0, "y": -1},
"NE": {"x": 1, "y": -1},
"E": {"x": 1, "y": 0},
"SE": {"x": 1, "y": 1},
"S": {"x": 0, "y": 1},
"SW": {"x": -1, "y": 1},
"W": {"x": -1, "y": 0},
"NW": {"x": -1, "y": -1},
}
def __init__(self, path):
"""
Load a puzzle from a json file in the format produced by
https://github.com/joshbduncan/word-search-generator
"""
with open(path, "r") as f:
data = json.load(f)
self.rows = data["puzzle"]
self.words = data["words"]
self.answers = {w: f"{k['direction']} @ ({k['start_row']}, {k['start_col']})" for w, k in data["key"].items()}
def __str__(self):
return f"Puzzle: {self.size} size, {len(self.words)} words"
@property
def size(self):
return len(self.rows)
def display(self, answers=None):
"""
Answers must be dicts with the word as the key and the answer as the value.
Answer syntax is as found in https://github.com/joshbduncan/word-search-generator
Example: "E @ (12, 6)" means start at 12 down and 6 across, then read Eastward
"""
if answers:
header = "** WORD SEARCH PUZZLE: ANSWERS **"
words = ", ".join(f"{word} {location}" for word, location in answers.items())
# create answer grid
rows = [["." for _ in range(self.size)] for _ in range(self.size)] # blank grid
answer_re = re.compile(r"([NSEW]{1,2}) @ \(([0-9]+), ([0-9]+)\)")
for word, answer in answers.items():
for direction, y, x in answer_re.findall(answer):
x, y = int(x) - 1, int(y) - 1
for letter in word:
rows[y][x] = letter
x += self.DIRECTIONS[direction]["x"]
y += self.DIRECTIONS[direction]["y"]
else:
header = "** WORD SEARCH PUZZLE **"
words = ", ".join(self.words)
rows = self.rows
grid = "\n".join(" ".join(cell for cell in row) for row in rows)
print(f"{header}\n\n{grid}\n\nWords: {words}\n")
def get_cell(self, x, y):
if x < 0 or y < 0 or x >= self.size or y >= self.size:
return None
return self.rows[y][x]
def solve(self):
answers = {word: self.find_word(word) for word in self.words}
assert answers == self.answers # validate
return answers
def find_word(self, word):
"""Return a string of the x, y coordinates and direction of the word's location in the puzzle grid."""
for y in range(self.size):
for x in range(self.size):
cell = self.get_cell(x, y)
if cell == word[0]:
for direction in self.DIRECTIONS:
if self.find_rest(direction, x, y, word[1:]):
return f"{direction} @ ({y + 1}, {x + 1})" # translate to 1-indexed
raise Exception(f"word '{word}' not found")
def find_rest(self, direction, x, y, rest):
"""Move in direction checking each letter in the puzzle grid for a match against the rest of the word."""
if not rest:
return True
x += self.DIRECTIONS[direction]["x"]
y += self.DIRECTIONS[direction]["y"]
cell = self.get_cell(x, y)
if not cell or cell != rest[0]:
return False
return self.find_rest(direction, x, y, rest[1:])
if __name__ == "__main__":
import os
directory = os.path.join(os.path.dirname(__file__), "samples")
for filename in os.listdir(directory):
path = os.path.join(directory, filename)
puzzle = Puzzle(path)
puzzle.display()
answers = puzzle.solve()
puzzle.display(answers)