/ 12.py
12.py
1 #!/usr/bin/python3 2 3 # run it as this, redirect is iportant not to fuck up ncurses 4 # ./12.py inputs/12 [--one | --two] 2>/tmp/knut_i_plet 5 6 import sys 7 import math 8 import time 9 import copy 10 from collections import namedtuple, Counter 11 import curses 12 import logging 13 if '--debug' in sys.argv: 14 logging.basicConfig(level=logging.DEBUG) 15 logger = logging.getLogger() 16 17 stdscr = None 18 19 with open(sys.argv[1]) as f: 20 # reversed to have (0, 0) in bottom left corner 21 MAP = [line.strip() for line in reversed(f.readlines())] 22 MAP_MAX_X = len(MAP) 23 MAP_MAX_Y = len(MAP[0]) 24 25 26 CoordinateBase = namedtuple('Coordinate', ['x', 'y']) 27 28 DIRECTIONS = {"up": (1, 0), 29 "right": (0, 1), 30 "left": (0, -1), 31 "down": (-1, 0)} 32 33 class Coordinate(CoordinateBase): 34 35 def __init__(self, x, y): 36 assert x in range(MAP_MAX_X) 37 assert y in range(MAP_MAX_Y) 38 self.elevation = ord(MAP[self.x][self.y]) 39 if self.elevation == ord('S'): 40 self.elevation = ord('a') 41 if self.elevation == ord('E'): 42 self.elevation = ord('z') 43 44 def neighbors(self): 45 result = [] 46 for neighbor in [(self.x + 1, self.y), 47 (self.x, self.y - 1), 48 (self.x, self.y + 1), 49 (self.x - 1, self.y)]: 50 if neighbor[0] in range(MAP_MAX_X) and neighbor[1] in range(MAP_MAX_Y): 51 result.append(Coordinate(*neighbor)) 52 return result 53 54 55 class WalkerWithMemory: 56 57 def __init__(self, start, reverse_rules=False, stop_at_obstacles=False): 58 self.current = Coordinate(*start) 59 self.visited = list() 60 self.knows_what_to_do = True 61 self.reverse_rules = reverse_rules 62 self.stop_at_obstacles = stop_at_obstacles 63 64 def walk(self, destination, stop_at_steps=6): 65 global stdscr 66 for _ in range(stop_at_steps): 67 if self.current not in self.visited: 68 self.visited.append(self.current) 69 stdscr.addch(self.current.x, self.current.y + 3, "☭", curses.color_pair(1)) 70 stdscr.refresh() 71 candidates = [] 72 for neighbor in self.current.neighbors(): 73 if self.reverse_rules: 74 if ((neighbor.elevation >= self.current.elevation or 75 self.current.elevation - 1 == neighbor.elevation) and 76 neighbor not in self.visited): 77 candidates.append(neighbor) 78 else: 79 if ((neighbor.elevation <= self.current.elevation or 80 self.current.elevation + 1 == neighbor.elevation) and 81 neighbor not in self.visited): 82 candidates.append(neighbor) 83 if not candidates: 84 stdscr.addch(self.current.x, self.current.y + 3, "@", 85 curses.color_pair(2)) 86 self.knows_what_to_do = False 87 continue 88 if self.stop_at_obstacles and type(destination) == str: 89 destination_t = list(self.current) 90 destination_t[0] += DIRECTIONS[destination][0] 91 destination_t[1] += DIRECTIONS[destination][1] 92 destination_t = tuple(destination_t) 93 if destination_t in candidates: 94 self.current = Coordinate(*destination_t) 95 else: 96 sorted_candidates = sorted(candidates, key=lambda x: math.dist(x, destination)) 97 logger.debug(sorted_candidates) 98 self.current = sorted_candidates[0] 99 if self.current not in self.visited: 100 self.visited.append(self.current) 101 102 START_POINT = Coordinate(20, 0) 103 FINAL_DESTINATION = Coordinate(20, 43) 104 105 class WalkingContest: 106 107 def __init__(self, start, final_destination, reverse_rules): 108 self.start = start 109 self.final_destination = final_destination 110 self.walkers = [WalkerWithMemory(self.start, stop_at_obstacles=True, reverse_rules=reverse_rules)] 111 self.steps = 1 112 self.iteration = 0 113 self.counter = Counter() 114 115 def did_we_win(self): 116 for walker in self.walkers: 117 if walker.current == self.final_destination: 118 for coordinate in walker.visited: 119 stdscr.addch(coordinate.x, coordinate.y + 3, "%", 120 curses.color_pair(3)) 121 logger.error(f'solution found, length is {len(walker.visited) - 1}') 122 stdscr.getkey() 123 124 def did_we_win_part_two(self): 125 for walker in self.walkers: 126 if walker.current.elevation == ord('a'): 127 for coordinate in walker.visited: 128 stdscr.addch(coordinate.x, coordinate.y + 3, "%", 129 curses.color_pair(3)) 130 logger.error(f'solution found, length is {len(walker.visited) - 1}') 131 stdscr.getkey() 132 133 def do_step(self): 134 """ 135 brute force possible paths in 4 directions 136 """ 137 newwalkers = [] 138 for walker in self.walkers: 139 logger.debug(f"walker: {walker.current}") 140 for direction in DIRECTIONS.keys(): 141 newwalker = copy.deepcopy(walker) 142 newwalker.walk(direction, stop_at_steps=self.steps) 143 newwalkers.append(newwalker) 144 logger.error(len(newwalkers)) 145 self.walkers = [] 146 # pruning walkers to avoid computational explosion 147 for walker in newwalkers: 148 self.counter.update({walker.current: 1}) 149 # if we visited a tile 4 times than it make sense to never visit it again 150 if self.counter[walker.current] < 4: 151 self.walkers.append(walker) 152 logger.error(len(self.walkers)) 153 logger.error('---') 154 for walker in self.walkers: 155 stdscr.addch(walker.current.x, walker.current.y + 3, "@", 156 curses.color_pair(2)) 157 self.iteration += 1 158 159 160 def main(stdscr): 161 stdscr.clear() 162 curses.start_color() 163 curses.use_default_colors() 164 curses.init_pair(1, curses.COLOR_RED, -1) 165 curses.init_pair(2, curses.COLOR_BLUE, -1) 166 curses.init_pair(3, curses.COLOR_YELLOW, -1) 167 for number, line in enumerate(MAP): 168 stdscr.addstr(number, 0, f"{number:2} {line}") 169 stdscr.refresh() 170 if '--one' in sys.argv: 171 SWAMP = WalkingContest(START_POINT, FINAL_DESTINATION, reverse_rules=False) 172 while True: 173 SWAMP.do_step() 174 SWAMP.did_we_win() 175 if '--two' in sys.argv: 176 MOUNTAIN = WalkingContest(FINAL_DESTINATION, START_POINT, reverse_rules=True) 177 while True: 178 MOUNTAIN.do_step() 179 MOUNTAIN.did_we_win_part_two() 180 181 if __name__ == '__main__': 182 stdscr = curses.initscr() 183 curses.wrapper(main)