import logging import random import re from enum import IntEnum from sys import stdout from typing import List, Tuple # As the search for the Chief continues, a small Elf who lives on the # station tugs on your shirt; she'd like to know if you could help her # with her word search (your puzzle input). She only has to find one word: # XMAS. # This word search allows words to be horizontal, vertical, diagonal, # written backwards, or even overlapping other words. It's a little unusual, # though, as you don't merely need to find one instance of XMAS - you need to # find all of them. LOG_FILENAME = "./day04-1.log" INPUT_FILENAME = "./input04.txt" logger = logging.Logger(__name__) formatter = logging.Formatter('[%(asctime)s][%(levelname)s] %(message)s') sh = logging.StreamHandler(stdout) sh.setLevel(logging.INFO) sh.setFormatter(formatter) fh = logging.FileHandler(LOG_FILENAME, mode="w", encoding="utf-8") fh.setLevel(logging.DEBUG) fh.setFormatter(formatter) logger.addHandler(sh) logger.addHandler(fh) class LetterValues(IntEnum): X = 1 M = 2 A = 4 S = 8 def get_word_value(word): total = 0 for i, letter in enumerate(word): total += ((3**i) * LetterValues[letter]) return total XMAS_VALUE = get_word_value("XMAS") SAMX_VALUE = get_word_value("SAMX") TEST_LINES = """MMMSXXMASM MSAMXMSMSA AMXSXMAAMM MSAMASMSMX XMASAMXAMM XXAMMXXAMA SMSMSASXSS SAXAMASAAA MAMMMXMMMM MXMXAXMASX""" class WSGrid: def __init__(self, lines: List[List[str]], word: str, print_intermediate_grids: bool=False): self.grid = [list(line) for line in lines] self.width = len(self.grid[0]) self.height = len(self.grid) self.final_grid = [['.' for _ in range(self.width)] for _ in range(self.height)] self.word = word self.words_found = 0 self.found_positions = [] self.print_intermediate_grids = print_intermediate_grids self.width def add_found_position(self: object, position: Tuple[int,int], direction: str) -> None: self.found_positions.append((position, direction)) logger.info(f"Found a match for {self.word} at {position} going {direction}.") if self.print_intermediate_grids: print("\n".join(["".join(line) for line in self.final_grid])) def search_east(self: object, position: Tuple[int,int]) -> bool: x, y = position if (self.width - x) < len(self.word): return False try: found_word = "".join([self.grid[y][x+i] for i in range(4)]) except IndexError: return False if found_word == self.word: self.words_found += 1 for i, char in enumerate(self.word): self.final_grid[y][x+i] = char self.add_found_position(position, "east") return found_word == self.word def search_west(self: object, position: Tuple[int,int]) -> bool: x, y = position if x+1 < len(self.word): return False try: found_word = "".join([self.grid[y][x-i] for i in range(4)]) except IndexError: return False if found_word == self.word: self.words_found += 1 for i, char in enumerate(self.word): self.final_grid[y][x-i] = char self.add_found_position(position, "west") return True return False def search_south(self: object, position: Tuple[int,int]) -> bool: x, y = position if (self.height - y) < len(self.word): return False try: found_word = "".join([self.grid[y+i][x] for i in range(4)]) except IndexError: return False if found_word == self.word: self.words_found += 1 for i, char in enumerate(self.word): self.final_grid[y+i][x] = char self.add_found_position(position, "south") return found_word == self.word def search_north(self: object, position: Tuple[int,int]) -> bool: x, y = position if y+1 < len(self.word): return False try: found_word = "".join([self.grid[y-i][x] for i in range(4)]) except IndexError: return False if found_word == self.word: self.words_found += 1 for i, char in enumerate(self.word): self.final_grid[y-i][x] = char self.add_found_position(position, "north") return found_word == self.word def search_northwest(self: object, position: Tuple[int,int]) -> bool: x, y = position if y+1 < len(self.word) or x+1 < len(self.word): return False try: found_word = "".join([self.grid[y-i][x-i] for i in range(4)]) except IndexError: return False if found_word == self.word: self.words_found += 1 for i, char in enumerate(self.word): self.final_grid[y-i][x-i] = char self.add_found_position(position, "northwest") return found_word == self.word def search_northeast(self: object, position: Tuple[int,int]) -> bool: x, y = position if y+1 < len(self.word) or (self.width - x) < len(self.word): return False try: found_word = "".join([self.grid[y-i][x+i] for i in range(4)]) except IndexError: return False if found_word == self.word: self.words_found += 1 for i, char in enumerate(self.word): self.final_grid[y-i][x+i] = char self.add_found_position(position, "northeast") return found_word == self.word def search_southwest(self: object, position: Tuple[int,int]) -> bool: x, y = position if (self.height - y)+1 < len(self.word) or x+1 < len(self.word): return False try: found_word = "".join([self.grid[y+i][x-i] for i in range(4)]) except IndexError: return False if found_word == self.word: self.words_found += 1 for i, char in enumerate(self.word): self.final_grid[y+i][x-i] = char self.add_found_position(position, "southwest") return found_word == self.word def search_southeast(self: object, position: Tuple[int,int]) -> bool: x, y = position if (self.height - y)+1 < len(self.word) or (self.width - x) < len(self.word): return False try: found_word = "".join([self.grid[y+i][x+i] for i in range(4)]) except IndexError: return False if found_word == self.word: self.words_found += 1 for i, char in enumerate(self.word): self.final_grid[y+i][x+i] = char self.add_found_position(position, "southeast") return found_word == self.word def find_word_at_position(self: object, position: Tuple[int,int]) -> int: return sum([ 1 if self.search_north(position) else 0, 1 if self.search_south(position) else 0, 1 if self.search_east(position) else 0, 1 if self.search_west(position) else 0, 1 if self.search_northwest(position) else 0, 1 if self.search_northeast(position) else 0, 1 if self.search_southwest(position) else 0, 1 if self.search_southeast(position) else 0 ]) def find_all_words(self: object) -> int: for y in range(len(self.grid)): for x in range(len(self.grid[0])): self.words_found += self.find_word_at_position((x,y)) return self.words_found def main041(run_test=False, print_intermediate_grids=False, print_final_grid=False): SEARCH_WORD = "XMAS" if run_test: lines = TEST_LINES.split("\n") else: with open("./input04.txt", "r", encoding="utf-8") as f: lines = [l.strip() for l in f.readlines()] finder = WSGrid(lines, SEARCH_WORD, print_intermediate_grids) total_found = finder.find_all_words() logger.info(f"Found {total_found} instances of {SEARCH_WORD}.") if print_final_grid: print("\n".join(["".join(line) for line in finder.final_grid])) if __name__ == "__main__": main041(run_test=False, print_intermediate_grids=False, print_final_grid=False)