GeezerVison is showing github.com — ClassicComputerScienceProblemsInPython/Chapter3/word_search.py at master · xhf79/ClassicComputerScienceProblemsInPython

Expand file tree

word_search.py

Copy path

More file actions

Latest commit

History

93 lines (79 loc) · 3.5 KB

word_search.py

Copy path

File metadata and controls

93 lines (79 loc) · 3.5 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

# word_search.py

# From Classic Computer Science Problems in Python Chapter 3

# Licensed under the Apache License, Version 2.0 (the "License");

# you may not use this file except in compliance with the License.

# You may obtain a copy of the License at

# http://www.apache.org/licenses/LICENSE-2.0

# Unless required by applicable law or agreed to in writing, software

# distributed under the License is distributed on an "AS IS" BASIS,

# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

# See the License for the specific language governing permissions and

# limitations under the License.

from typing import NamedTuple, List, Dict, Optional

from random import choice

from string import ascii_uppercase

from csp import CSP, Constraint

Grid = List[List[str]] # type alias for grids

class GridLocation(NamedTuple):

row: int

column: int

def generate_grid(rows: int, columns: int) -> Grid:

# initialize grid with random letters

return [[choice(ascii_uppercase) for c in range(columns)] for r in range(rows)]

def display_grid(grid: Grid) -> None:

for row in grid:

print("".join(row))

def generate_domain(word: str, grid: Grid) -> List[List[GridLocation]]:

domain: List[List[GridLocation]] = []

height: int = len(grid)

width: int = len(grid[0])

length: int = len(word)

for row in range(height):

for col in range(width):

columns: range = range(col, col + length)

rows: range = range(row, row + length)

if col + length <= width:

# left to right

domain.append([GridLocation(row, c) for c in columns])

# diagonal towards bottom right

if row + length <= height:

domain.append([GridLocation(r, col + (r - row)) for r in rows])

if row + length <= height:

# top to bottom

domain.append([GridLocation(r, col) for r in rows])

# diagonal towards bottom left

if col - length >= 0:

domain.append([GridLocation(r, col - (r - row)) for r in rows])

return domain

class WordSearchConstraint(Constraint[str, List[GridLocation]]):

def __init__(self, words: List[str]) -> None:

super().__init__(words)

self.words: List[str] = words

def satisfied(self, assignment: Dict[str, List[GridLocation]]) -> bool:

# if there are any duplicates grid locations then there is an overlap

all_locations = [locs for values in assignment.values() for locs in values]

return len(set(all_locations)) == len(all_locations)

if __name__ == "__main__":

grid: Grid = generate_grid(9, 9)

words: List[str] = ["MATTHEW", "JOE", "MARY", "SARAH", "SALLY"]

locations: Dict[str, List[List[GridLocation]]] = {}

for word in words:

locations[word] = generate_domain(word, grid)

csp: CSP[str, List[GridLocation]] = CSP(words, locations)

csp.add_constraint(WordSearchConstraint(words))

solution: Optional[Dict[str, List[GridLocation]]] = csp.backtracking_search()

if solution is None:

print("No solution found!")

else:

for word, grid_locations in solution.items():

# random reverse half the time

if choice([True, False]):

grid_locations.reverse()

for index, letter in enumerate(word):

(row, col) = (grid_locations[index].row, grid_locations[index].column)

grid[row][col] = letter

display_grid(grid)