Created
April 4, 2018 22:08
-
-
Save LeReverandNox/682a035faaadb8ce9e0a4f47a762d43e to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from colorama import Back, Style | |
| class WordSearchSolver(object): | |
| def __init__(self, grid = [], seeked_words = []): | |
| self.grid = grid | |
| self.seeked_words = seeked_words | |
| self.found_words = [] | |
| self.highlighted_cells = set() | |
| self.not_found_words = [] | |
| @property | |
| def grid(self): | |
| return self._grid | |
| @grid.setter | |
| def grid(self, grid): | |
| for i, row in enumerate(grid): | |
| grid[i] = list(map(lambda c: c.upper(), row)) | |
| self._grid = grid | |
| return self.grid | |
| @property | |
| def seeked_words(self): | |
| return self._seeked_words | |
| @seeked_words.setter | |
| def seeked_words(self, words): | |
| words = set(word.upper() for word in words) | |
| self._seeked_words = words | |
| return self.seeked_words | |
| def import_grid_from_file(self, file_path): | |
| try: | |
| lines = self._get_file_lines(file_path) | |
| if not lines: | |
| raise Exception("The file {} is empty. Please put some words in it.".format(file_path)) | |
| grid = [[c for c in line] for line in lines] | |
| self.grid = grid | |
| return True | |
| except Exception as e: | |
| exit(e) | |
| def import_words_from_file(self, file_path): | |
| try: | |
| lines = self._get_file_lines(file_path) | |
| if not lines: | |
| raise Exception("The file {} is empty. Please put some words in it.".format(file_path)) | |
| self.seeked_words = lines | |
| return True | |
| except Exception as e: | |
| exit(e) | |
| def _get_file_lines(self, file_path): | |
| try: | |
| lines = [] | |
| with open(file_path) as file: | |
| content = file.readlines() | |
| lines = [line.strip() for line in content if line.strip()] | |
| file.closed | |
| return lines | |
| except Exception as _: | |
| raise Exception("The file {} is not readable.".format(file_path)) | |
| def parse_words(self, words_string): | |
| words = [word.strip() for word in words_string.split(',')] | |
| self.seeked_words = words | |
| return True | |
| def solve(self): | |
| for word in self.seeked_words: | |
| words_coords = self._find_word_in_grid(word) | |
| if words_coords: | |
| for word_coords in words_coords: | |
| self.found_words.append((word, word_coords)) | |
| else: | |
| self.not_found_words.append(word) | |
| self._get_highlighted_cells() | |
| self._print_solved_grid() | |
| def _get_highlighted_cells(self): | |
| for word in self.found_words: | |
| self.highlighted_cells |= set(word[1]) | |
| def _find_word_in_grid(self, word): | |
| first_char = word[0] | |
| matches = [] | |
| for y, row in enumerate(self.grid): | |
| for x, cell in enumerate(row): | |
| if cell == first_char: | |
| if len(word) < 2: | |
| matches.append([(y, x)]) | |
| else: | |
| near_cells = self._get_near_cells(y, x) | |
| possibilities = [d for d, letter in near_cells.items() if letter == word[1]] | |
| for direction in possibilities: | |
| word_coordinates = self._find_next_letter([(y, x)], word, direction) | |
| if word_coordinates: | |
| matches.append(word_coordinates) | |
| return matches | |
| def _find_next_letter(self, found_coordinates, word, direction = ''): | |
| if len(found_coordinates) == len(word): | |
| return found_coordinates | |
| next_letter = word[len(found_coordinates)] | |
| y, x = found_coordinates[-1][0], found_coordinates[-1][1] | |
| near_cells = self._get_near_cells(y, x) | |
| if direction == 'N' and near_cells['N'] == next_letter: | |
| found_coordinates.append((y - 1, x)) | |
| return self._find_next_letter(found_coordinates, word, 'N') | |
| elif direction == 'NE' and near_cells['NE'] == next_letter: | |
| found_coordinates.append((y - 1, x + 1)) | |
| return self._find_next_letter(found_coordinates, word, 'NE') | |
| elif direction == 'E' and near_cells['E'] == next_letter: | |
| found_coordinates.append((y, x + 1)) | |
| return self._find_next_letter(found_coordinates, word, 'E') | |
| elif direction == 'SE' and near_cells['SE'] == next_letter: | |
| found_coordinates.append((y + 1, x + 1)) | |
| return self._find_next_letter(found_coordinates, word, 'SE') | |
| elif direction == 'S' and near_cells['S'] == next_letter: | |
| found_coordinates.append((y + 1, x)) | |
| return self._find_next_letter(found_coordinates, word, 'S') | |
| elif direction == 'SO' and near_cells['SO'] == next_letter: | |
| found_coordinates.append((y + 1, x - 1)) | |
| return self._find_next_letter(found_coordinates, word, 'SO') | |
| elif direction == 'O' and near_cells['O'] == next_letter: | |
| found_coordinates.append((y, x - 1)) | |
| return self._find_next_letter(found_coordinates, word, 'O') | |
| elif direction == 'NO' and near_cells['NO'] == next_letter: | |
| found_coordinates.append((y - 1, x - 1)) | |
| return self._find_next_letter(found_coordinates, word, 'NO') | |
| else: | |
| return False | |
| def _get_near_cells(self, y, x): | |
| cells = { | |
| 'N': None, | |
| 'NE': None, | |
| 'E': None, | |
| 'SE': None, | |
| 'S': None, | |
| 'SO': None, | |
| 'O': None, | |
| 'NO': None | |
| } | |
| if (y - 1) >= 0: | |
| cells['N'] = self.grid[y - 1][x] | |
| if (y - 1) >= 0 and (x + 1) < len(self.grid[y - 1]): | |
| cells['NE'] = self.grid[y - 1][x + 1] | |
| if (x + 1) < len(self.grid[y]): | |
| cells['E'] = self.grid[y][x + 1] | |
| if (y + 1) < len(self.grid) and (x + 1) < len(self.grid[y]): | |
| cells['SE'] = self.grid[y + 1][x + 1] | |
| if (y + 1) < len(self.grid): | |
| cells['S'] = self.grid[y + 1][x] | |
| if (y + 1) < len(self.grid) and (x - 1) >= 0: | |
| cells['SO'] = self.grid[y + 1][x - 1] | |
| if (x - 1) >= 0: | |
| cells['O'] = self.grid[y][x - 1] | |
| if (y - 1) >= 0 and (x - 1) >= 0: | |
| cells['NO'] = self.grid[y - 1][x - 1] | |
| return cells | |
| def _print_solved_grid(self): | |
| for y, row in enumerate(self.grid): | |
| string = '' | |
| for x, cell in enumerate(row): | |
| if (y, x) in self.highlighted_cells: | |
| string += Back.YELLOW + cell + Style.RESET_ALL | |
| else: | |
| string += cell | |
| print(string) | |
| if self.not_found_words: | |
| print ('Words not found : ' + ', '.join(self.not_found_words)) | |
| def __str__(self): | |
| print("*** GRID ***") | |
| for row in self.grid: | |
| print(''.join(row)) | |
| print("*** GRID END***") | |
| print("*** WORDS ***") | |
| print(self.seeked_words) | |
| print("*** WORDS END ***") | |
| print("*** FOUND WORDS ***") | |
| print(self.found_words) | |
| print("*** FOUND WORDS END***") | |
| print("*** HIGHLIGHTED CELLS ***") | |
| print(self.highlighted_cells) | |
| print("*** HIGHLIGHTED CELLS END ***") | |
| return "" | |
| if __name__ == '__main__': | |
| import argparse | |
| parser = argparse.ArgumentParser() | |
| parser.add_argument("file", help="A grid file to resolve.") | |
| parser.add_argument("--words", help="A list of words to seek, separted by commas.") | |
| parser.add_argument("--words-file", help="A file containing the seeked words.") | |
| args = parser.parse_args() | |
| if not args.words and not args.words_file: | |
| exit("Please use --words or --words-file to provide a list of seeked words.") | |
| ws_solver = WordSearchSolver() | |
| if args.words: | |
| ws_solver.parse_words(args.words) | |
| elif args.words_file: | |
| ws_solver.import_words_from_file(args.words_file) | |
| ws_solver.import_grid_from_file(args.file) | |
| ws_solver.solve() | |
| # print(ws_solver) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment