By telleropnul, April 26, 2023

Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. Go check it out: Advent of Code

2021 Day 25

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import numpy as np   data = open("input.txt", "r", encoding="utf-8").read().splitlines() mapping = {'.': 0, '>': 1, 'v': 2} board1 = np.array([[mapping[x] for x in line] for line in data])   count, moved = 0, True while moved: before = board1.copy()   board2 = np.zeros_like(board1) board2[(np.roll(board1, 1, axis=1) == 1) & (board1 == 0)] = 1 board2[(board1 == 1) & (np.roll(board1, -1, axis=1) != 0)] = 1 board2[board1 == 2] = 2   board1 = np.zeros_like(board2) board1[(np.roll(board2, 1, axis=0) == 2) & (board2 == 0)] = 2 board1[(board2 == 2) & (np.roll(board2, -1, axis=0) != 0)] = 2 board1[board2 == 1] = 1   count += 1 moved = not np.array_equal(before, board1) print(count)```

2021 Day 24 Part 01 + 02

```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 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 from typing import Iterable   Cmd = list[str]     class ALU: """The ALU unit for the puzzle."""   def __init__(self, cmds: list[Cmd]) -> None: """Initialise the ALU unit with the given command set.""" self.cmds = cmds self.reg: dict[str, int] = {"w": 0, "x": 0, "y": 0, "z": 0}   def resolve(self, val: str) -> int: """Resolve either an int literal or a register into an int value.""" if val in self.reg: return self.reg[val] else: return int(val)   def __call__(self, inp: Iterable[int] | None = None) -> dict[str, int]: """Run the ALU command set on the given input.""" inputs = iter(inp or []) for op, *params in self.cmds: match op: case "inp": try: val = next(inputs) except StopIteration: raise ValueError("Not enough inputs") from None self.reg[params[0]] = val case "add": self.reg[params[0]] += self.resolve(params[1]) case "mul": self.reg[params[0]] *= self.resolve(params[1]) case "div": self.reg[params[0]] //= self.resolve(params[1]) case "mod": self.reg[params[0]] %= self.resolve(params[1]) case "eql": a = self.resolve(params[0]) b = self.resolve(params[1]) self.reg[params[0]] = int(a == b) case _: raise ValueError(f"Unknown operator: {op}")   state = self.reg.copy() self.reg = {"w": 0, "x": 0, "y": 0, "z": 0}   return state     def correct_input(inp: list[int], cmds: list[Cmd]) -> list[int]: """Correct an input sequence so that it passes the test.   The input consists of 14 processing blocks - each for one of the inputs. Each of them has the same structure and is parametrized by three variables, let's call them "div", "chk", and "add". Written in pseudocode and using "inp" for the input value each block performs the following computation:   x = (z % 26 + chk) != inp z //= div z *= 25 * x + 1 z += (inp + add) * x   This can be re-written using an if-block, which eliminates the x-register:   if z % 26 + chk != inp: z //= div z *= 26 z += inp + add else: z //= div   We note that "div" can only be one of two value: either 1 or 26. This leads us to observe that all computations are manipulations of digits of the z-register written in base 26. So it's natural to define "div = 26**shf", so that "shf" will be either 0 or 1. We can use binary operators to denote operations in base 26 as follows:   z * 26 = z << 1 z // 26 = z >> 1 z % 26 = z & 1   With this we can write the program as follows:   if z & 1 + chk != inp: z = z >> shf z = z << 1 z = z + (inp + add) else: z = z >> shf   We can also write the bitwise operations as follows:   z & 1 = z.last_bit z >> 1 = z.pop() (z << 1) & a = z.push(a) (z >> 1) << 1) & a = z.pop_push(a)   where pop/push refer to that bit stack of z in base 26 with the last bit on top. Therefore, z.pop() removes the last bit, z.push(a) appends the bit "a", and z.pop_push(a) replaces the last bit by "a".   Given that shf can only be 0 or 1 we get the following two cases:   if shf == 0: if z.last_bit + chk != inp: z.push(inp + add) elif shf == 1: if z.last_bit + chk != inp: z.pop_push(inp + add) else: z.pop()   According to the puzzle input (our input) in all cases where shf == 0 it's true that chk > 9. Given that 1 <= inp <= 9 the check (if z.last_bit + chk != inp) will therefore always be true. This gives:   if shf == 0: z.push(inp + add) elif shf == 1: if z.last_bit + chk == inp: z.pop() else: z.pop_push(inp + add)   We can summarize in words. View z as a stack of bits in base 26. Start with an empty stack. Whenever shf == 0 (div == 1) push (inp + add) on the stack. If, however, shf == 1, consider the last bit on the stack. If it's equal to (inp - chk), then remove it, otherwise replace it by (inp + add).   We also observe from the puzzle input (our input) that among the 14 instruction blocks for each of the inputs there are exactly 7 cases with shf == 0 and 7 with shf == 1. Given that for shf == 0 something is always added to the stack, our goal is to arrange the input so that for shf == 1 it's always popped from the sack, so that at the end of the program we end up with an empty bit stack, which means that z == 0, which makes the input pass the test.   To arrange this start with an arbitrary array of 14 inputs denoted by [inp_0, inp_1, ..., inp_13]. If the first two instruction blocks have shf_0 == 0 and shf_1 == 0 then after the first two inputs two bits will have been pushed to the stack:   z_stack = [inp_0 + add_0, inp_1 + add_1]   If then shf_2 == 1 we want to set inp_2 so that the last bit is popped. The last bit is popped if   z.last_bit + chk_2 == inp_2 => inp_1 + add_1 + chk_2 == inp_2   So we set (inp_2 = inp_1 + add_1 + chk_2). It can now occur that the condition 1 <= inp_2 <= 9 is violated. In this case we can add an arbitrary value to inp_2 to restore this condition. We will need to add the same value to inp_1 too in order to maintain the previous equality. We need to be careful that after these adjustments we also maintain 1 <= inp_1 <= 9. The least we can do is for cases where inp_2 < 1 to choose the value so that inp_2 = 1 and for cases with inp_2 > 9 to choose the value so that inp_2 = 9. If this still doesn't work for inp_1, then no other value will work for both either.   This strategy can be used to take any wish input sequence and correct it so that it passes the test. So for part 1 we'll want to start with the highest possible input, 99999999999999, and for part 2 with the lowest, 11111111111111.   Programmatically, to correct the input we go through code subroutines that handle each of the inputs and extract the (shf, chk, add) parameters. If shf == 0 we remember the "add" parameter by pushing it on a stack, and we also remember which input it corresponds to. If shf == 1 we pop the last "add" from the stack and use it to compute the corrected input.     Args: inp: The input array to correct. cmds: The input commands   Returns: The corrected input array. """ # copy input array inp = list(inp)   # correct input sub_len = 18 # length of the subroutine for each of the inputs. line_nos = [4, 5, 15] # line numbers with the (div, chk, add) parameters. stack = [] for i in range(14): div_chk_add = [cmds[i * sub_len + x][-1] for x in line_nos] div, chk, add = map(int, div_chk_add) if div == 1: stack.append((i, add)) elif div == 26: j, add = stack.pop() # Set the input so that the test passes inp[i] = inp[j] + add + chk # Correct the input so that 1 <= inp <= 9 if inp[i] > 9: inp[j] = inp[j] - (inp[i] - 9) inp[i] = 9 if inp[i] < 1: inp[j] = inp[j] + (1 - inp[i]) inp[i] = 1   return inp     def check(inp: list[int], cmds: list[Cmd]) -> bool: """Check if the input sequence passes the test.""" alu = ALU(cmds) reg = alu(inp) if reg["z"] == 0: return True else: return False     def solve(wish_inp: list[int], cmds: list[Cmd]) -> str: """Solve the puzzle by correcting the given wish input sequence.""" inp = correct_input(wish_inp, cmds) solution = "".join(map(str, inp)) if not check(inp, cmds): raise RuntimeError(f"Part 1 solution doesn't pass the test: {solution}")   return solution     def run(data_s: str) -> tuple[str, str]: """Solve the puzzles.""" cmds = [line.split() for line in data_s.splitlines()] part1 = solve([9] * 14, cmds) part2 = solve([1] * 14, cmds)   return part1, part2     data = open("input.txt", "r", encoding="utf-8").read() print(run(data))```

2021 Day 23 Part 01 + 02

```cmd
cd %LOCALAPPDATA%\Programs\Python\Python311\
(optionally add this to %PATH% environment variable.)
python --version
python -m pip --version
python -m pip install -U alive-progress
```

Learn alive-progress

```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 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 import heapq from alive_progress import alive_bar import logging     logger = logging.getLogger() logger.setLevel(logging.INFO)     HALL_LEN = 11 NUM_ROOMS = 4   ROOM_POS = {'A': 2, 'B': 4, 'C': 6, 'D': 8} ROOMS = {'A': 0, 'B': 1, 'C': 2, 'D': 3} ROOM_AT = [(2, 'A'), (4, 'B'), (6, 'C'), (8, 'D')] MOVE_COSTS = {'A': 1, 'B': 10, 'C': 100, 'D': 1000} NO_STOP = (2, 4, 6, 8)     class State: @classmethod def from_string(cls, state_str, room_size=2): hall_str = state_str[:HALL_LEN] hall = [room if room != '.' else None for room in hall_str]   room_str = state_str[HALL_LEN + 1:] rooms = [] for i in range(NUM_ROOMS): pods_in_room = tuple(pod if pod != '.' else None for pod in room_str[i * room_size:(i + 1) * room_size]) rooms.append(pods_in_room)   return State(hall, rooms, room_size)   def __init__(self, hall, rooms, room_size) -> None: self.hall = hall self.rooms = rooms assert room_size == 2 or room_size == 4 self.room_size = room_size   def __eq__(self, other): return str(self) == str(other)   def __hash__(self): return hash(str(self))   def __lt__(self, other): return False   def __repr__(self) -> str: return str(self)   def __str__(self) -> str: hall_str = ''.join(hall if hall else '.' for hall in self.hall) room_str = '' for room in self.rooms: room_str += ''.join(section if section else '.' for section in room) return hall_str + "|" + room_str   def final(self) -> bool: if self.room_size == 2: return str(self) == '...........|AABBCCDD' elif self.room_size == 4: return str(self) == '...........|AAAABBBBCCCCDDDD' else: return False   def moves_from_hall(self, hall_i): pod = self.hall[hall_i]   # if there is no pod in the hall # there is no move if not pod: return[]   pod_room = ROOM_POS[pod]   # if there is a pod between us and the room # we can't move there for hall_idx in between(hall_i, pod_room): if self.hall[hall_idx]: return []   # check if we can get to the room room_move = self.moves_into_wanted_room(pod) if not room_move: return []   # we can move to the room cost, new_rooms = room_move cost += dist(hall_i, pod_room) * MOVE_COSTS[pod] hall = self.hall[:] hall[hall_i] = None return [(cost, State(hall, new_rooms, self.room_size))]   def moves_from_room(self, room_i): possible_moves_from_room_to_hall = self.moves_from_room_to_hall(room_i) if not possible_moves_from_room_to_hall: return []   cost, pod, room_pos, new_rooms = possible_moves_from_room_to_hall   possible_stops = [] for pos in between(room_pos, HALL_LEN): if self.hall[pos]: # There is a pod in the way. break possible_stops.append(pos) for pos in between(room_pos, -1): if self.hall[pos]: # There is a pod in the way. break possible_stops.append(pos) possible_stops = [stop for stop in possible_stops if stop not in NO_STOP]   out = [] for stop in possible_stops: new_hall = self.hall[:] new_hall[stop] = pod out.append((cost + MOVE_COSTS[pod] * dist(room_pos, stop), State(new_hall, new_rooms, self.room_size))) return out   def moves_from_room_to_hall(self, room_i): room_pos, room_pod = ROOM_AT[room_i] room = self.rooms[room_i]   # check that we have occupants if not room[-1]: return None   # check if room only has correct occupants only_correct = True for space in room: if space and space != room_pod: only_correct = False break if only_correct: return None   # get the top occupant that can move steps = 1 while not room[steps - 1]: steps += 1   rooms = [list(room[:]) for room in self.rooms] pod = rooms[room_i][steps - 1] rooms[room_i][steps - 1] = None return [MOVE_COSTS[pod] * steps, pod, room_pos, rooms]   def moves_into_wanted_room(self, pod): """ Assuming you stand right outside the room what valid moves are there? returns: None or (cost, new rooms array) """ room_idx = ROOMS[pod] room = self.rooms[room_idx]   # check if room is full if room[0]: return None   # check if room contains other pods for space in room: if space and space != pod: return None   # get steps to bottom-most empty space steps = 0 for space in room: if space: break steps += 1   # Create a new room array usable for State() rooms = [list(room[:]) for room in self.rooms] rooms[room_idx][steps - 1] = pod return (MOVE_COSTS[pod] * steps, [tuple(room) for room in rooms])   def valid_moves(self): out = []   for i in range(HALL_LEN): out += self.moves_from_hall(i)   for i in range(NUM_ROOMS): out += self.moves_from_room(i)   return sorted(out)     def between(i1, i2): if i1 < i2: return range(i1 + 1, i2) return range(i1 - 1, i2, -1)     def dist(i1, i2): return abs(i1 - i2)     def tests(): # final state assert State.from_string('...........|AABBCCDD').final() assert not State.from_string('...........|ABBACCDD').final() assert not State.from_string('A..........|.BBACCDD').final() assert not State.from_string('A..........|.ABBCCDD').final() assert not State.from_string('AA.........|..BBCCDD').final()   # positions between assert list(between(5, 9)) == [6, 7, 8] assert list(between(9, 5)) == [8, 7, 6]   # distance assert dist(9, 5) == 4   # moves from hall logging.debug(State.from_string('B..........|AA.BCCDD').moves_from_hall(0)) logging.debug(State.from_string('AB.........|.A.BCCDD').moves_from_hall(1)) logging.debug(State.from_string('BA.........|.A.BCCDD').moves_from_hall(1)) logging.debug(State.from_string('.....D.....|AABBCC.D').moves_from_hall(5))   # moves from room to hall logging.debug(State.from_string('...........|.A.BCCDD').moves_from_room_to_hall(1)) logging.debug(State.from_string('...........|.B.ACCDD').moves_from_room_to_hall(1)) logging.debug(State.from_string('...........|.BBACCDD').moves_from_room_to_hall(1))   # moves from room logging.debug(State.from_string('.C.........|BBAACCDD').moves_from_room(1))   # valid moves logging.debug(State.from_string('...........|BACDBCDA').valid_moves()) logging.debug(State.from_string('...B.......|BACD.CDA').valid_moves()) logging.debug(State.from_string('...B.C.....|BA.D.CDA').valid_moves())   # verify hash state1 = State.from_string('...........|BBAACCDD') state2 = State.from_string('...........|BBAACCDD') state_set = {state1, state2} assert len(state_set) == 1     def solve(input_state, room_size=2): start = State.from_string(input_state, room_size) visited = set()   todo = [(0, start, ())]   # this is only for the progress bar last_cost = 0 if room_size == 2: max_cost = 13495 else: max_cost = 53767   with alive_bar(max_cost) as bar: while todo: cost, state, path = heapq.heappop(todo)   if state in visited: logging.debug("already visited", state) continue   # this is only for the progress bar bar(cost - last_cost) last_cost = cost logging.debug("cost", cost, "state", state)   visited.add(state)   if state.final(): logging.debug("final", cost) for step in path: logging.debug(step) return cost   for move_cost, move_to_state in state.valid_moves(): heapq.heappush(todo, (cost + move_cost, move_to_state, tuple(list(path) + [state])))     # RUN TESTS # tests()   # TEST DATA # print("Part 1:", solve("...........|BACDBCDA", 2)) # print("Part 2:", solve("...........|BDDACCBDBBACDACA", 4))   # TEST DATA # print("Part 1:", solve("...........|ACDCADBB", 2)) # print("Part 2:", solve("...........|ADDCDCBCABADBACB", 4))   # REAL DATA   ############# #...........# ###C#C#B#D### #D#A#B#A# #########   # print("Part 1:", solve("...........|CDCABBDA", 2))   ############# #...........# ###C#C#B#D###   #D#C#B#A# #D#B#A#C#   #D#A#B#A# #########   print("Part 2:", solve("...........|CDDDCCBABBABDACA", 4))```

2021 Day 22 Part 01 + 02

```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 import re from typing import List, Tuple, Union     def read_input() -> List[List[Union[str, int]]]: lines = open('input.txt').read().splitlines() steps = [] for line in lines: parts = re.match(r'(\w+) x=(-?\d+)\.\.(-?\d+),y=(-?\d+)\.\.(-?\d+),z=(-?\d+)\.\.(-?\d+)\$', line).groups() steps.append([parts[0]] + [int(i) for i in parts[1:]]) return steps     def overlapping(zone1: List[int], zone2: List[int]) -> Union[Tuple[int, ...], None]: maxx, maxy, maxz = [max(zone1[i], zone2[i]) for i in (0, 2, 4)] minx, miny, minz = [min(zone1[i], zone2[i]) for i in (1, 3, 5)]   if minx >= maxx and miny >= maxy and minz >= maxz: return maxx, minx, maxy, miny, maxz, minz else: return None     def count_lit(steps): lit = 0 counted_zones = [] for step in reversed(steps): mode, box = step[0], step[1:] minx, maxx, miny, maxy, minz, maxz = box if mode == 'on': dead_zones = [] for overlap in [overlapping(zone, box) for zone in counted_zones]: if overlap: dead_zones.append(('on', *overlap)) lit += (maxx - minx + 1) * (maxy - miny + 1) * (maxz - minz + 1) lit -= count_lit(dead_zones) counted_zones.append(box) return lit     def filter_outliers(steps, max_val=50, min_val=-50): new_steps = [] for step in steps: minx, maxx, miny, maxy, minz, maxz = step[1:] if minx <= max_val and miny <= max_val and minz <= max_val and maxx >= min_val and maxy >= min_val and maxz >= min_val: new_steps.append(step) return new_steps     steps = read_input() steps = filter_outliers(steps) print("Part 1:", count_lit(steps))   steps = read_input() print("Part 2:", count_lit(steps))```

2021 Day 21 Part 01 + 02

```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 from functools import cache   def advance(position, score, roll_sum): new_position = ((position - 1 + roll_sum) % 10) + 1 return new_position, score + new_position   # Part 1 def play_practice_game(positions) -> int: player = 0 scores = [0, 0] num_rolls = 0 roll = 0   while max(scores) <= 1000: rolls = [roll := (roll % 100) + 1 for _ in range(3)] positions[player], scores[player] = advance(positions[player], scores[player], sum(rolls)) player = 1 - player num_rolls += 3   if scores[0] >= 1000: return scores[1] * num_rolls else: return scores[0] * num_rolls   # Part 2 throw_frequencies = {3: 1, 4: 3, 5: 6, 6: 7, 7: 6, 8: 3, 9: 1}   @cache def get_wins(pos1, pos2, score1, score2, player=1): if score1 >= 21: return [1, 0]   if score2 >= 21: return [0, 1]   wins = [0, 0] for dice_sum, frequency in throw_frequencies.items(): if player == 1: pos, score = advance(pos1, score1, dice_sum) wins1, wins2 = get_wins(pos, pos2, score, score2, 2) else: pos, score = advance(pos2, score2, dice_sum) wins1, wins2 = get_wins(pos1, pos, score1, score, 1)   wins[0] += wins1 * frequency wins[1] += wins2 * frequency   return wins   data = open("input.txt", "r", encoding="utf-8").read().splitlines() pos1 = int(data[0].split(" ")[-1]) pos2 = int(data[1].split(" ")[-1])   print("Part 1:", play_practice_game([pos1, pos2])) print("Part 2:", max(get_wins(pos1, pos2, 0, 0)))```

2021 Day 21 Part 01

```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 class Die: def __init__(self, sides=100): self.sides = sides self.value = 0 self.rolled = 0   def roll(self): self.rolled += 1 self.value = self.value % self.sides + 1 return self.value     data = open("input.txt", "r", encoding="utf-8").read().splitlines() position_1 = int(data[0].split(" ")[-1]) position_2 = int(data[1].split(" ")[-1]) score_1, score_2 = 0, 0   die = Die() while True: position_1 = (position_1 + die.roll() + die.roll() + die.roll() - 1) % 10 + 1 score_1 += position_1 if score_1 >= 1000: print(score_2 * die.rolled) exit() position_2 = (position_2 + die.roll() + die.roll() + die.roll() - 1) % 10 + 1 score_2 += position_2 if score_2 >= 1000: print(score_1 * die.rolled) exit()```

2021 Day 20 Part 01 + 02

```Start Menu > type "alias" > Manage app execution aliases > disable python and python3 aliases
cmd
cd %LOCALAPPDATA%\Programs\Python\Python311\
(optionally add this to %PATH% environment variable.)
python --version
python -m pip --version
python -m pip install -U scipy
```

Learn scipy

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import numpy as np from scipy.signal import convolve2d   def enhance(times): data = open("input.txt", "r", encoding="utf-8").read().splitlines() algo = [int(x == "#") for x in data[0]] img = np.array([[int(x == "#") for x in y] for y in data[2:]])   matrix = np.array([[1, 2, 4], [8, 16, 32], [64, 128, 256]]) fillvallue = 0 for _ in range(times): idx = convolve2d(img, matrix, fillvalue=fillvallue) img = np.vectorize(lambda x: algo[x])(idx) fillvallue = algo[0] if fillvallue == 0 else algo[511] print(img.sum())   # part 1 enhance(2)   # part 2 enhance(50)```

2021 Day 19 Part 01 + 02

```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 111 112 113 114 115 116 117 118 119 120 from collections import Counter from typing import Tuple, List     def get_scanners(): raw_scanners = [scanner for scanner in open('input.txt').read().split('\n\n')]   scanners = [] for raw_scanner in raw_scanners: scanner = [[int(d) for d in line.strip().split(',')] for line in raw_scanner.splitlines()[1:]] scanners.append(scanner)   return scanners     def check_if_scanners_overlap(scanners, base: int, to_check: int) -> Tuple[List[int], List[Tuple[int, int]]]: """ Check if two scanners overlap (have 12+ beacons in common) 1. We can check this one "direction" at a time as there are no beacons with duplicate x, y, or z coordinates 2. We can assume that the base scanner (0) is aligned at X, Y, Z (whatever its alignment is, well just call it X, Y, Z) 3. The other scanner will be aligned at a random combo of [X, -X, Y, -Y, Z, -Z] (24 options) Once we find a direction where we have 12 common, we've found our scanner and know its orientation and offset If they overlap, offsets, and orientations will not be empty """ offsets, orientation = [], [] base_scanner = scanners[base] scanner_to_check = scanners[to_check]   # the base scanner is aligned at X, Y, Z => Column [0, 1, 2] # We want to find the offset and the orientation of the pair scanner in all 3 dirs for base_i in range(3):   # the scanner to check, can have any combination of [X, -X, Y, -Y, Z, -Z] # we check one orientation/direction at a time (X = (1,0) -Y = (-1, 1) etc.) for sign, dir in [(1, 0), (-1, 0), (1, 1), (-1, 1), (1, 2), (-1, 2)]:   # get all the diffs between the base and the possible orientations/directions of the check_scanner diffs = [beacon0[base_i] - sign * beacon1[dir] for beacon1 in scanner_to_check for beacon0 in base_scanner]   # if we have 12+ matched in any direction, we have found our pair scanner # and we know the offset, and also the orientation/direction of this column offset, matching_beacons = Counter(diffs).most_common()[0]   if matching_beacons >= 12: offsets.append(offset) orientation.append((sign, dir))   return offsets, orientation     def find_overlapping(scanner: int, to_check: List[int]) -> Tuple[int, List[int], List[Tuple[int, int]]]: for other_scanner in to_check: offsets, orientation = check_if_scanners_overlap(scanners, scanner, other_scanner) if len(offsets) > 0: return other_scanner, offsets, orientation return -1, [], []     def align_scanner(scanner, offsets, orientation): to_align = scanners[scanner]   # align orientation sign0, col0 = orientation[0] sign1, col1 = orientation[1] sign2, col2 = orientation[2] to_align = [[sign0 * beacon[col0], sign1 * beacon[col1], sign2 * beacon[col2]] for beacon in to_align]   # align offset to_align = [[beacon[0] + offsets[0], beacon[1] + offsets[1], beacon[2] + offsets[2]] for beacon in to_align]   scanners[scanner] = to_align     def align_scanners(scanners): aligned_scanners = [0] un_aligned_scanners = [i for i in range(1, len(scanners))]   all_offsets = []   while un_aligned_scanners: for i in aligned_scanners: overlapping_scanner, offsets, orientation = find_overlapping(i, un_aligned_scanners) if overlapping_scanner != -1: print("Found overlapping scanners:", i, overlapping_scanner, offsets, orientation) align_scanner(overlapping_scanner, offsets, orientation) un_aligned_scanners.remove(overlapping_scanner) aligned_scanners.append(overlapping_scanner) all_offsets.append(offsets)   return all_offsets     def count_beacons(scanners): unique_beacons = set()   for scanner in scanners: for beacon in scanner: unique_beacons.add((beacon[0], beacon[1], beacon[2]))   return len(unique_beacons)     def get_biggest_manhattan_distance(offsets) -> int: biggest_distance = 0   for i in range(len(offsets)): for j in range(i + 1, len(offsets)): manhattan = abs(offsets[i][0] - offsets[j][0]) + abs(offsets[i][1] - offsets[j][1]) + abs(offsets[i][2] - offsets[j][2]) biggest_distance = max(biggest_distance, manhattan)   return biggest_distance     scanners = get_scanners() offsets = align_scanners(scanners)   print("Part 01:", count_beacons(scanners)) print("Part 02:", get_biggest_manhattan_distance(offsets))```

2021 Day 18 Part 01 + 02

```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 import re   def parse_snailfish(n): v = re.split(r"(\[|\]|,)", n) v = [x for x in v if x not in ("", ",")] v = [int(x) if x.isdigit() else x for x in v] return v   def add(a, b): return ["["] + a + b + ["]"]   def explode(n): depth = 0 for i, s in enumerate(n): if s == "[": depth += 1 elif s == "]": depth -= 1   if ( depth > 4 and s == "[" and isinstance(n[i + 1], int) and isinstance(n[i + 2], int) and n[i + 3] == "]" ): for j in range(i, 0, -1): if isinstance(n[j], int): n[j] += n[i + 1] break for j in range(i + 4, len(n)): if isinstance(n[j], int): n[j] += n[i + 2] break n = n[:i] + [0] + n[i + 4 :] return n, True return n, False   def split(n): for i, s in enumerate(n): if isinstance(s, int) and s >= 10: n = n[:i] + ["[", s // 2, s - s // 2, "]"] + n[i + 1 :] return n, True return n, False   def reduce(n): to_reduce = True while to_reduce: n, to_reduce = explode(n) if not to_reduce: n, to_reduce = split(n) return n   def magnitude(n): while len(n) > 1: for i, s in enumerate(n): if ( s == "[" and isinstance(n[i + 1], int) and isinstance(n[i + 2], int) and n[i + 3] == "]" ): n = n[:i] + [3 * n[i + 1] + 2 * n[i + 2]] + n[i + 4 :] break return n[0]   data = open("input.txt", "r", encoding="utf-8").read().splitlines()   # Part 1 m = parse_snailfish(data[0]) for d in data[1:]: n = parse_snailfish(d) m = add(m, n) m = reduce(m) print('part 01: ', magnitude(m))   # Part 2 max_magnitude = 0 for d1 in data: for d2 in data: if d1 != d2: m = parse_snailfish(d1) n = parse_snailfish(d2) mag = magnitude(reduce(add(m, n))) max_magnitude = max(max_magnitude, mag) print('part 02: ', max_magnitude)```

2021 Day 17 Part 01 + 02

```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 # Example: 'target area: x=230..283, y=-107..-57\n' import re data = open("input.txt", "r", encoding="utf-8").read() data = re.findall('-?\d+',data) data = [int(x) for x in data] x1, x2, y1, y2 = data[0], data[1], data[2], data[3]   best_y, count = 0, 0 for init_vx in range(1, x2 + 1): # cannot go higher than x2, or it will go throught the target area for init_vy in range(y1, 500): vx, vy = init_vx, init_vy x, y, max_y = 0, 0, y1 while x <= x2 and y >= y1: max_y = max(max_y, y) if x1 <= x <= x2 and y1 <= y <= y2: count += 1 best_y = max(best_y, max_y) break x += vx y += vy vx = max(0, vx - 1) vy -= 1   print(f"part 01: {best_y}") print(f"part 02: {count}")```

2021 Day 16 Part 02

```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 from functools import reduce   funcDict = { 0: sum, 1: lambda a: reduce(lambda x, y: x * y, a), 2: min, 3: max, 5: lambda a: int(a[0] > a[1]), 6: lambda a: int(a[0] < a[1]), 7: lambda a: int(a[0] == a[1]) }   def evaluate(u): if packets[u][1] == 4: return packets[u][2]   res = [] for v in graph[u]: res.append(evaluate(v)) return funcDict[packets[u][1]](res)   data = open("input.txt", "r", encoding="utf-8").read().splitlines()   s = bin(int(data[0], 16))[2:] for i in data[0]: if i != '0': break s = '0' * 4 + s n = len(s) if n % 4 != 0: s = '0' * (4 - n % 4) + s n = len(s) c = 0 packets = []   while c < n and '1' in s[c:]: v = int(s[c: c + 3], 2) c += 3 t = int(s[c: c + 3], 2) c += 3   if t == 4: num = '' while s[c] == '1': num += s[c + 1: c + 5] c += 5 num += s[c + 1: c + 5] c += 5 num = int(num, 2)   packets.append([v, t, num, c]) else: l = int(s[c], 2) c += 1 if l == 0: num = int(s[c: c + 15], 2) c += 15 else: num = int(s[c: c + 11], 2) c += 11   packets.append([v, t, l, num, c])   stack = [] graph = [[] for _ in range(len(packets))]   for i, u in enumerate(packets): if len(stack) > 0: p = stack[-1] graph[p].append(i) packets[p][3] -= 1 if packets[p][3] == 0: stack.pop()   while len(stack) > 0: p = stack[-1] if packets[p][2] == 0 and packets[p][3] <= u[-1] - packets[p][-1]: stack.pop() else: break   if u[1] != 4: stack.append(i)   print(evaluate(0))```

2021 Day 16 Part 01

```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 data = open("input.txt", "r", encoding="utf-8").read().splitlines()   s = bin(int(data[0], 16))[2:] n = len(s) if n % 4 != 0: s = '0' * (4 - n % 4) + s n = len(s) res = 0 c = 0   while c < n and '1' in s[c:]: v = int(s[c: c + 3], 2) res += v c += 3 t = int(s[c: c + 3], 2) c += 3   if t == 4: num = '' while s[c] == '1': num += s[c + 1: c + 5] c += 5 num += s[c + 1: c + 5] c += 5 num = int(num, 2) else: l = int(s[c], 2) c += 1 if l == 0: num = int(s[c: c + 15], 2) c += 15 else: num = int(s[c: c + 11], 2) c += 11   print(res)```

2021 Day 15 Part 02 v2

```1 2 3 4 5 6 7 8 9 10 11 import networkx as nx import numpy as np   data = open("input.txt", "r", encoding="utf-8").read() df = np.array([[int(x) for x in line] for line in data.splitlines()]) row = np.hstack([(df + i - 1) % 9 + 1 for i in range(5)]) df = np.vstack([(row + i - 1) % 9 + 1 for i in range(5)]) w, h = df.shape G = nx.grid_2d_graph(w, h, create_using=nx.DiGraph()) nx.set_edge_attributes(G, {e: df[e[1][0], e[1][1]] for e in G.edges()}, "cost") print(nx.shortest_path_length(G, source=(0, 0), target=(w - 1, h - 1), weight="cost"))```

2021 Day 15 Part 02

```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 import sys from collections import defaultdict from queue import PriorityQueue import math   data = open("input.txt", "r", encoding="utf-8").read().splitlines()   def initialise(data): #set up the initial grid, before the enlargement grid = {}   for j, row in enumerate(data): for i, item in enumerate(row): grid[(i,j)] = int(item)   visit = PriorityQueue() visit.put((0,(0,0)))   distance = defaultdict(lambda: math.inf) distance[(0,0)] = 0   target = (5*len(data[0])-1, 5*len(data)-1)   return grid,visit,distance, target   def neighbour_coords(point,grid): #returns a list of coords of points adjacent to (i,j) in the grid coords_list = [] steps = [(1,0),(-1,0),(0,1),(0,-1)]   for step in steps: (i,j) = point (dx,dy) = step if 0 <= i+dx <= (5*len(data[0])-1) and 0 <= j+dy <= (5*len(data)-1): coords_list.append((i+dx,j+dy))   return coords_list   def get_node_value(point,grid): #use modular arithmetic to get the value of a node at any point in the enlarged grid #by referencing the initial grid (pre-enlargement) (x,y) = point x_len = len(data[0]) y_len = len(data)   value = grid[(x%x_len,y%y_len)] + x//x_len + y//y_len   return (value-1)%9 + 1   def dijkstra(grid,visit,distance,target):   while not visit.empty(): (d,(x,y)) = visit.get()   for nb in neighbour_coords((x,y), grid): if d + get_node_value(nb,grid) < distance[nb]: distance[nb] = d + get_node_value(nb,grid) visit.put((distance[nb], nb))   return distance[target]     grid,visit,distance, target = initialise(data)   print(dijkstra(grid,visit,distance,target))```

2021 Day 15 Part 01 v3

```Start Menu > type "alias" > Manage app execution aliases > disable python and python3 aliases
cmd
cd %LOCALAPPDATA%\Programs\Python\Python311\
(optionally add this to %PATH% environment variable.)
python --version
python -m pip --version
python -m pip install -U networkx
```

Learn networkx

```1 2 3 4 5 6 7 8 import networkx as nx   data = open("input.txt", "r", encoding="utf-8").read() df = [[int(x) for x in line] for line in data.splitlines()] w, h = len(df), len(df[0]) G = nx.grid_2d_graph(w, h, create_using=nx.DiGraph()) nx.set_edge_attributes(G, {e: df[e[1][0]][e[1][1]] for e in G.edges()}, "cost") print(nx.shortest_path_length(G, source=(0, 0), target=(w - 1, h - 1), weight="cost"))```

2021 Day 15 Part 01 v2

```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 import sys from collections import defaultdict from queue import PriorityQueue import math   data = open("input.txt", "r", encoding="utf-8").read().splitlines()   def initialise(data): #set up the grid grid = {}   for j, row in enumerate(data): for i, item in enumerate(row): grid[(i,j)] = int(item)   visit = PriorityQueue() visit.put((0,(0,0)))   distance = defaultdict(lambda: math.inf) distance[(0,0)] = 0   target = (len(data[0])-1, len(data)-1)   return grid,visit,distance,target   def neighbour_coords(point,grid): #returns a list of coords of points adjacent to (i,j) in the grid coords_list = [] steps = [(1,0),(-1,0),(0,1),(0,-1)]   for step in steps: (i,j) = point (dx,dy) = step if 0 <= i+dx <= (len(data[0])-1) and 0 <= j+dy <= (len(data)-1): coords_list.append((i+dx,j+dy))   return coords_list   def dijkstra(grid,visit,distance,target):   while not visit.empty(): (d,(x,y)) = visit.get()   for nb in neighbour_coords((x,y), grid): if d + grid[(nb)] < distance[nb]: distance[nb] = d + grid[(nb)] visit.put((distance[nb], nb))   return distance[target]     grid,visit,distance,target = initialise(data)   print(dijkstra(grid,visit,distance,target))```

2021 Day 14 Part 02

```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 from collections import Counter   data = open("input.txt", "r", encoding="utf-8").read().splitlines() template = data[0] rules = {a: b for a, b in [x.split(" -> ") for x in data[2:]]}   # Count each pair of letters in the template pairs = Counter([template[i : i + 2] for i in range(len(template) - 1)]) # slicing   # Update pairs count at each step as per rules for _ in range(40): new_pairs = Counter() for p, v in pairs.items(): if p in rules: c = rules[p] new_pairs[p[0] + c] += v new_pairs[c + p[1]] += v else: new_pairs[p] += pairs[p] pairs = new_pairs   # Count letters by counting first letter of each pair, # plus the final letter which is invariant during the whole process. count = Counter() for p, v in pairs.items(): count[p[0]] += v count[template[-1]] += 1   print(count.most_common()[0][1] - count.most_common()[-1][1])```

2021 Day 14 Part 01

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 from collections import Counter   data = open("input.txt", "r", encoding="utf-8").read().splitlines() template = data[0] # for line 2 to last, split by delimiter, to list, to dict rules = {a: b for a, b in [x.split(" -> ") for x in data[2:]]}   for _ in range(10): new = "" for i in range(len(template) - 1): pair = template[i : i + 2] # slicing new += pair[0] if pair in rules: new += rules[pair] new += template[-1] template = new   count = Counter(template).most_common() print(count[0][1] - count[-1][1])```

2021 Day 13 Part 02

```Start Menu > type "alias" > Manage app execution aliases > disable python and python3 aliases
cmd
cd %LOCALAPPDATA%\Programs\Python\Python311\
(optionally add this to %PATH% environment variable.)
python --version
python -m pip --version
python -m pip install -U imageio
```

Learn imageio

```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 import re import numpy as np from imageio import imwrite   data = open("input.txt", "r", encoding="utf-8").read() coords_section, folds_section = data.split("\n\n") coords = {tuple(map(int, c.split(","))) for c in coords_section.splitlines()} folds = [re.match(r"fold along (x|y)=(\d+)", f).groups() for f in folds_section.splitlines()] folds = [(a, int(v)) for a, v in folds]   for axis, v in folds: if axis == 'y': coords = {(x, y) for x, y in coords if y < v} | {(x, v - (y - v)) for x, y in coords if y >= v} elif axis == 'x': coords = {(x, y) for x, y in coords if x < v} | {(v - (x - v), y) for x, y in coords if x >= v}   X, Y = max(c[0] for c in coords), max(c[1] for c in coords) grid = np.zeros((X + 1, Y + 1), dtype=int) for c in coords: grid[c] = 1   # .T = transpose (swap rows and columns) print(grid) print(grid.T) imwrite("grid.png", grid.T)   # row of int values -> str # replace 1 with █ and 0 with ░, print row aa=[] for i in range(0, len(grid.T)): aa.append(''.join([str(x) for x in grid.T[i]])) print(aa[i]) for a in aa: a=a.replace("1","█") a=a.replace("0","░") print(a)```

2021 Day 13 Part 01

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 import re   data = open("input.txt", "r", encoding="utf-8").read() coords_section, folds_section = data.split("\n\n") coords = {tuple(map(int, c.split(","))) for c in coords_section.splitlines()} folds = [re.match(r"fold along (x|y)=(\d+)", f).groups() for f in folds_section.splitlines()] folds = [(a, int(v)) for a, v in folds]   for axis, v in folds[0:1]: if axis == 'y': coords = {(x, y) for x, y in coords if y < v} | {(x, v - (y - v)) for x, y in coords if y >= v} elif axis == 'x': coords = {(x, y) for x, y in coords if x < v} | {(v - (x - v), y) for x, y in coords if x >= v}   print(len(coords))```

2021 Day 12 Part 01 + 02

```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 data = open("input.txt", "r", encoding="utf-8").read() lst = [line.split("-") for line in data.splitlines()] edges = [[a, b] for a, b in lst if a != "end" and b != "start"] edges += [[b, a] for a, b in lst if a != "start" and b != "end"]     def find_path_r(current_path, found_paths, repeat): current_node = current_path[-1] if current_node == "end": found_paths.append(current_path) return for edge in edges: if edge[0] == current_node: if edge[1].isupper() or edge[1] not in current_path: find_path_r(current_path + [edge[1]], found_paths, repeat) elif edge[1].islower() and edge[1] in current_path and repeat: find_path_r(current_path + [edge[1]], found_paths, False)     def find_paths(repeat): """Find the all the paths from start to the end node""" found_paths = [] find_path_r(["start"], found_paths, repeat) return found_paths     print(f"Part 01: Paths, no repeat visit allowed: {len(find_paths(False))}") print(f"Part 02: Paths, one repeat visit allowed: {len(find_paths(True))}")```

2021 Day 11 Part 02 v2

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import numpy as np from scipy import signal   data = open("input.txt", "r", encoding="utf-8").read().splitlines() df = np.array([[int(x) for x in line] for line in data])   step = 0 while True: energy = np.ones_like(df) flashed = np.zeros_like(df) while np.any(energy.astype(bool)): df += energy flashing = np.logical_and((df > 9), np.logical_not(flashed)) energy = signal.convolve(flashing, np.array([[1, 1, 1], [1, 0, 1], [1, 1, 1]]), mode='same') flashed = np.logical_or(flashed, flashing) df[flashed] = 0 step += 1 if np.all(flashed): print(step) exit()```

2021 Day 11 Part 01 v2

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 import numpy as np from scipy import signal   data = open("input.txt", "r", encoding="utf-8").read().splitlines() df = np.array([[int(x) for x in line] for line in data])   total = 0 for i in range(100): energy = np.ones_like(df) flashed = np.zeros_like(df) while np.any(energy.astype(bool)): df += energy flashing = np.logical_and((df > 9), np.logical_not(flashed)) energy = signal.convolve(flashing, np.array([[1, 1, 1], [1, 0, 1], [1, 1, 1]]), mode='same') flashed = np.logical_or(flashed, flashing) df[flashed] = 0 total += np.sum(flashed) print(total)```

2021 Day 11 Part 01 + 02

```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 octopi = open("input.txt", "r", encoding="utf-8").read().splitlines() octopi = [[int(x) for x in line] for line in octopi]   max_x = len(octopi[0]) - 1 max_y = len(octopi) - 1 total_octopi = (max_x + 1) * (max_y + 1)   neighbors = dict() part1 = 0   for y in range(max_y + 1): for x in range(max_x + 1): d = neighbors.setdefault((x,y),list()) if x > 0: d.append((x-1,y)) if x < max_x: d.append((x+1,y)) if y > 0: d.append((x,y-1)) if y < max_y: d.append((x,y+1))   i = 0 while True: part2 = 0 queue = list() for y in range(max_y + 1): for x in range(max_x + 1): v = octopi[y][x] if v == 9: part2 += 1 octopi[y][x] = 0 queue.append((x,y)) else: octopi[y][x] = v + 1 while len(queue) > 0: (x,y) = queue.pop(0) for yy in range(max(y-1,0),min(y+1,max_y)+1): for xx in range(max(x-1,0),min(x+1,max_x)+1): if (xx,yy) != (x,y): v = octopi[yy][xx] if v != 0: if v == 9: part2 += 1 octopi[yy][xx] = 0 queue.append((xx,yy)) else: octopi[yy][xx] = v + 1 i += 1 part1 += part2 if i == 100: print(f"Part 1: Number of total flashes after 100 steps: {part1}") if part2 == total_octopi: # print('\n'.join([''.join([str(x) for x in line]) for line in octopi])) print(f"Part 2: First step when all octopi are flashing: {i}") break```

2021 Day 10 Part 02

```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 from statistics import median   def checker(line): stack = [] for char in line: if char in '([{<': stack.append(char) elif char in ')': if stack.pop() != '(': return 0 elif char in ']': if stack.pop() != '[': return 0 elif char in '}': if stack.pop() != '{': return 0 elif char in '>': if stack.pop() != '<': return 0 score = 0 d = {'(': 1, '[': 2, '{': 3, '<': 4} for char in stack[::-1]: score *= 5 score += d[char] return score   data = open("input.txt", "r", encoding="utf-8").read().splitlines() scores = [checker(line) for line in data] print(median([x for x in scores if x != 0]))```

2021 Day 10 Part 01

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 def checker(line): stack = [] for char in line: if char in '([{<': stack.append(char) elif char in ')': if stack.pop() != '(': return 3 elif char in ']': if stack.pop() != '[': return 57 elif char in '}': if stack.pop() != '{': return 1197 elif char in '>': if stack.pop() != '<': return 25137 return 0   data = open("input.txt", "r", encoding="utf-8").read().splitlines() print(sum(checker(line) for line in data))```

2021 Day 09 Part 02 v2

```Start Menu > type "alias" > Manage app execution aliases > disable python and python3 aliases
cmd
cd %LOCALAPPDATA%\Programs\Python\Python311\
(optionally add this to %PATH% environment variable.)
python --version
python -m pip --version
python -m pip install -U scikit-image
error: Microsoft Visual C++ 14.0 or greater is required. Get it with "Microsoft C++ Build Tools": https://visualstudio.microsoft.com/visual-cpp-build-tools/
Note: scikit-image module is written in C++ and comes as source code that needs compiling.
```

How-to-C++-using-Visual-Studio-Code-rabbit-hole

Learn Scikit-Image (‘skimage’)

```1 2 3 4 5 import numpy as np from skimage.measure import label, regionprops   df = np.array([list(map(int, [c for c in line])) for line in open("input.txt", "r", encoding="utf-8").read().splitlines()]) print(np.prod(sorted([r.area for r in regionprops(label(df < 9, connectivity=1))])[-3:]))```

2021 Day 09 Part 02

```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 # We need to group the numbers between 0–8 (not 9), # so 9 will be like a wall that separates the groups. # Then make a list of groups and the number of members in it. # The result will be the product of the top three groups.   import math   def get_adjacents(i, j): adjacents = [] if i+1 < len(grid[0]): adjacents.append(grid[j][i+1]) if i-1 >= 0: adjacents.append(grid[j][i-1]) if j+1 < len(grid): adjacents.append(grid[j+1][i]) if j-1 >= 0: adjacents.append(grid[j-1][i]) return adjacents   def count_groups(i, j): if j < 0 or j >= len(grid) or \ i < 0 or i >= len(grid[0]) or \ grid[j][i] == 9 or \ grid[j][i] == -1: return grid[j][i] = -1 groups[len(groups)-1] += 1 count_groups(i+1, j) count_groups(i-1, j) count_groups(i, j+1) count_groups(i, j-1)   grid = open("input.txt", "r").read().splitlines() grid = [list(map(int, x)) for x in grid]   groups = [] for i in range(0, len(grid)): for j in range(0, len(grid[0])): groups.append(0) count_groups(j, i) print(math.prod(sorted(groups, reverse=True)[:3]))```

2021 Day 09 Part 01 v2

```1 2 3 4 5 6 7 8 9 10 11 12 import numpy as np   data = open("input.txt", "r", encoding="utf-8").read() df = np.array([list(map(int, [c for c in line])) for line in data.splitlines()]) pad = np.pad(df, ((1, 1), (1, 1)), "constant", constant_values=10) mask = ( (df < pad[1:-1, 0:-2]).astype(int) # left + (df < pad[1:-1, 2:]).astype(int) # right + (df < pad[0:-2, 1:-1]).astype(int) # top + (df < pad[2:, 1:-1]).astype(int) # bottom ) print((df + 1)[mask == 4].sum())```

2021 Day 09 Part 01

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 def get_adjacents(i, j): adjacents = [] if i+1 < len(grid[0]): adjacents.append(grid[j][i+1]) if i-1 >= 0: adjacents.append(grid[j][i-1]) if j+1 < len(grid): adjacents.append(grid[j+1][i]) if j-1 >= 0: adjacents.append(grid[j-1][i]) return adjacents   grid = open("input.txt", "r").read().splitlines() grid = [list(map(int, x)) for x in grid]   result = 0 for j in range(0, len(grid)): for i in range(0, len(grid[0])): if grid[j][i] < min(get_adjacents(i, j)): result += 1 + grid[j][i] print(result)```

2021 Day 08 Part 02

```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 data = open("input.txt", "r").read().splitlines() data = [x.split('|') for x in data] data = [(i.split(), o.split()) for i, o in data]     def intersect(a, b): return len(set(a).intersection(b))     total = 0 for d in data:   # Find wires representations of 1, 4, 7, 8 based on number of wires used for n in d[0]: n = ''.join(sorted(n)) length = len(n)   # 1 has 2 segments if length == 2: one = n # 4 has 4 segments elif length == 4: four = n # 7 has 3 segments elif length == 3: seven = n # 8 has 7 segments elif length == 7: eight = n   # Deduce others digits only by comparing wires with representation of 1, 4, 7, 8 for n in d[0]: n = ''.join(sorted(n)) length = len(n)   # 0, 6 and 9 have 6 segments if length == 6: if intersect(n, four) == 4: nine = n elif intersect(n, one) == 2: zero = n else: six = n   # 2, 3 and 5 have 5 segments if length == 5: if intersect(n, one) == 2: three = n elif intersect(n, four) == 2: two = n else: five = n   match = { zero: '0', one: '1', two: '2', three: '3', four: '4', five: '5', six: '6', seven: '7', eight: '8', nine: '9' }   value = ''.join(match[''.join(sorted(x))] for x in d[1]) total += int(value)   print(total)```

2021 Day 08 Part 01

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import numpy as np   data = open("input.txt", "r").read().splitlines() data = [x.split('|') for x in data] data = [(i.split(), o.split()) for i, o in data]   # Example: # First line of input is split into a list of two values. The two values are then split into a list each: # fcdeba edcbag decab adcefg acdfb gdcfb acf fabe fa eacfgbd | aefb cfa acf cdabf # ['fcdeba edcbag decab adcefg acdfb gdcfb acf fabe fa eacfgbd'],['aefb cfa acf cdabf'] # ['fcdeba','edcbag','decab','adcefg','acdfb','gdcfb','acf','fabe','fa','eacfgbd'],['aefb','cfa','acf','cdabf']   total = 0 for d in data: # process lines nb_segments = [len(x) for x in d[1]] # length of each string value in d[1] nb_segments = np.array(nb_segments) is1 = (nb_segments == 2).sum() # 1 has 2 segments is4 = (nb_segments == 4).sum() # 4 has 4 segments is7 = (nb_segments == 3).sum() # 7 has 3 segments is8 = (nb_segments == 7).sum() # 8 has 7 segments total += is1 + is4 + is7 + is8   print(total)```

2021 Day 07 Part 02 v2

```1 2 3 4 5 data = open('input.txt', encoding='utf-8').read() df = list(map(int, data.split(','))) p_min, p_max = min(df), max(df) fuels = [sum(map(lambda x: abs(x - p) * (abs(x - p) + 1) // 2, df)) for p in range(p_min, p_max + 1)] print(min(fuels))```

2021 Day 07 Part 02

```1 2 3 4 5 6 7 8 9 10 11 data = open('input.txt', encoding='utf-8').read() df = list(map(int, data.split(','))) p_min, p_max = min(df), max(df) fuels = [] for p in range(p_min, p_max + 1): # for this position, calculate total fuel spend over all crabs fuel = 0 for i in range(len(df)): fuel += abs(df[i] - p) * (abs(df[i] - p) + 1) // 2 fuels.append(fuel) print(min(fuels))```

2021 Day 07 Part 01 v2

```1 2 3 4 5 data = open('input.txt', encoding='utf-8').read() df = list(map(int, data.split(','))) p_min, p_max = min(df), max(df) fuels = [sum(map(lambda x: abs(x - p), df)) for p in range(p_min, p_max + 1)] print(min(fuels))```

2021 Day 07 Part 01

```1 2 3 4 5 6 7 8 9 10 11 data = open('input.txt', encoding='utf-8').read() df = list(map(int, data.split(','))) p_min, p_max = min(df), max(df) fuels = [] for p in range(p_min, p_max + 1): # for this position, calculate total fuel spend over all crabs fuel = 0 for i in range(len(df)): fuel += abs(df[i] - p) fuels.append(fuel) print(min(fuels))```

2021 Day 06 Part 02

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 from collections import Counter   data = open("input.txt", encoding='utf-8').read() df = Counter([int(x) for x in data.split(",")]) for i in range(-1, 9): if i not in df: df[i] = 0   for day in range(256): for i in range(9): df[i-1] = df[i] df[6] += df[-1] df[8] = df[-1] df[-1] = 0 print(f"After {day+1} days:", df)   total = 0 for i in range(9): total += df[i] print(total)```

2021 Day 06 Part 01

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 import numpy as np   data = open("input.txt", encoding='utf-8').read() df = np.array([int(x) for x in data.split(",")])   for day in range(80): df -= 1 new = np.sum(df < 0) df = np.where(df < 0, 6, df) if new: df = np.hstack([df, np.full(new, 8)]) print(f"After {day+1} days:", df)   print(df.shape)```

2021 Day 05 Part 02 v2

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import numpy as np   data = open("input.txt").read().splitlines() data = [x.replace(' -> ', ',').split(',') for x in data] data = [list(map(int, x)) for x in data]   size = max(max(x) for x in data) + 1 diagram = np.zeros((size, size), dtype=int)   for x1, y1, x2, y2 in data: if x1 == x2 or y1 == y2: x1, y1, x2, y2 = min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2) diagram[y1: y2+1, x1: x2+1] += 1 else: x = range(x1, x2+1) if x1 <= x2 else range(x1, x2-1, -1) y = range(y1, y2+1) if y1 <= y2 else range(y1, y2-1, -1) for i, j in zip(x, y): diagram[j, i] += 1   print(np.sum(diagram > 1))```

2021 Day 05 Part 01 v2

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 import numpy as np   data = open("input.txt").read().splitlines() data = [x.replace(' -> ', ',').split(',') for x in data] data = [list(map(int, x)) for x in data]   size = max(max(x) for x in data) + 1 diagram = np.zeros((size, size), dtype=int)   for x1, y1, x2, y2 in data: x1, y1, x2, y2 = min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2) if x1 == x2 or y1 == y2: diagram[y1: y2+1, x1: x2+1] += 1   print(np.sum(diagram > 1))```

2021 Day 05 Part 01 + 02

```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 import collections   def cordinate(obj): # Convert coordinates from string to int return tuple(map(int, obj.split(',')))   def draw_horizontal_line(grid, y, x, x1): intersections = 0 for i in range(min(x, x1), max(x, x1) + 1): grid[(i, y)] += 1   if grid[(i, y)] == 2: intersections += 1 return intersections   def draw_vertical_line(grid, x, y, y1): intersections = 0 for i in range(min(y, y1), max(y, y1) + 1): grid[(x, i)] += 1   if grid[(x, i)] == 2: intersections += 1 return intersections   def draw_diagonal_line(grid, x, y, x1, y1): intersections = 0 upto = abs(x1 - x) for _ in range(upto + 1): grid[(x, y)] += 1 if grid[(x, y)] == 2: intersections += 1   # We need to increment the x and y coordinates to draw diagonal lines # For that we need to identify the slope of the line x += 1 if x1 > x else -1 y += 1 if y1 > y else -1 return intersections   grid = collections.defaultdict(int) counter = 0   with open('input.txt', 'r') as f: lines = f.readlines() lines = [line.split(' -> ') for line in lines]   for line in lines: p1, p2 = tuple(map(cordinate, line)) if p1[0] == p2[0]: counter += draw_vertical_line(grid, p1[0], p1[1], p2[1]) elif p1[1] == p2[1]: counter += draw_horizontal_line(grid, p1[1], p1[0], p2[0])   print(f'-= PART 01 =-\nTotal number of overlapping points: {counter}')   grid = collections.defaultdict(int) counter = 0   for line in lines: p1, p2 = tuple(map(cordinate, line)) if p1[0] == p2[0]: counter += draw_vertical_line(grid, p1[0], p1[1], p2[1]) elif p1[1] == p2[1]: counter += draw_horizontal_line(grid, p1[1], p1[0], p2[0]) else: counter += draw_diagonal_line(grid, p1[0], p1[1], p2[0], p2[1])   print(f'-= PART 02 =-\nTotal number of overlapping points: {counter}')```

2021 Day 04 Part 02 v2

```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 import numpy as np   data = open('input.txt', encoding='utf-8').read().splitlines() drawn = [int(x) for x in data[0].split(',')]   boards_count = (len(data) - 1) // 6 boards = [] for i in range(boards_count): board = [(list(int(x) for x in data[i*6+j+2].split())) for j in range(5)] boards.append(np.array(board))   def is_win(board): return np.any(np.sum(board, axis=1) == -board.shape[0]) or np.any(np.sum(board, axis=0) == -board.shape[1])   def score(board): return np.sum(board[board != -1])   solved_boards = 0 for d in drawn: for i, b in enumerate(boards): X, Y = b.shape for x in range(X): for y in range(Y): if b[x, y] == d: b[x, y] = -1 if is_win(b): boards[i] = np.full(b.shape, -2) solved_boards += 1 if solved_boards == boards_count: print("board", i, "with score", score(b)) print("solution", score(b) * d) exit()```

2021 Day 04 Part 01 v2

```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 import numpy as np   data = open('input.txt', encoding='utf-8').read().splitlines() drawn = [int(x) for x in data[0].split(',')]   boards_count = (len(data) - 1) // 6 boards = [] for i in range(boards_count): board = [(list(int(x) for x in data[i*6+j+2].split())) for j in range(5)] boards.append(np.array(board))   def is_win(board): return np.any(np.sum(board, axis=1) == -board.shape[0]) or np.any(np.sum(board, axis=0) == -board.shape[1])   def score(board): return np.sum(board[board != -1])   for d in drawn: for i, b in enumerate(boards): X, Y = b.shape for x in range(X): for y in range(Y): if b[x, y] == d: b[x, y] = -1 if is_win(b): print("board", i, "win", "score", score(b)) print("solution", score(b) * d) exit()```

2021 Day 04 Part 01 + 02

```Start Menu > type "alias" > Manage app execution aliases > disable python and python3 aliases
cmd
cd %LOCALAPPDATA%\Programs\Python\Python311\
(optionally add this to %PATH% environment variable.)
python --version
python -m pip --version
python -m pip install -U numpy
```

Learn Numpy

```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 import numpy as np   class Board: def __init__(self): self.board = np.zeros((5,5), dtype=int) self.marked = np.zeros((5,5))   def read_from_lines(self, lines): for i in range(5): line_entries = [int(entry) for entry in lines[i].split(' ') if entry != ''] self.board[i] = line_entries   def check_called_number(self, called_number): if called_number in self.board: indices = np.where(self.board == called_number) self.marked[indices[0], indices[1]] = 1   def check_win(self): return self.marked.all(axis=0).any() or self.marked.all(axis=1).any()   def calculate_score(self, called_number): return (self.board * (self.marked==0)).sum() * called_number   def find_first_winner(called_numbers, boards): for called_number in called_numbers: for j in range(len(boards)): boards[j].check_called_number(called_number) if boards[j].check_win(): print(f"board #{j+1} wins!") print(f"board #{j+1} marked:\n{boards[j].marked}") return j, called_number   def find_last_winner(called_numbers, boards): winners = [] winner_call = 0 for called_number in called_numbers: for j in range(len(boards)): if j not in winners: boards[j].check_called_number(called_number) if boards[j].check_win(): winners.append(j) print(f"Board #{j+1:03d} is the next winner!") print(f"board #{j+1} marked:\n{boards[j].marked}") winner_call = called_number return winners[-1], winner_call   with open('input.txt', 'r') as f: lines = [entry.strip() for entry in f.readlines()]   called_numbers = [int(entry) for entry in lines[0].split(',')] print(f"called numbers: {called_numbers}")   number_of_boards = (len(lines)-1)//6 print(f"number of boards: {number_of_boards}")   boards = dict() for j in range(number_of_boards): boards[j] = Board() boards[j].read_from_lines(lines[(2 + j*6):(2+5+(j+1)*6)])   print("-= Part 01 =-") winner_index, called_number = find_first_winner(called_numbers, boards) print(f"[score: {boards[winner_index].calculate_score(called_number)}")   print("-= Part 02 =-") winner_index, called_number = find_last_winner(called_numbers, boards) print(f"score: {boards[winner_index].calculate_score(called_number)}")```

2021 Day 03 Part 02

```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 from copy import copy   with open('input.txt', 'r') as f: lines = f.readlines() diagnostics = [entry.strip() for entry in lines]   o2 = copy(diagnostics) for i in range(len(diagnostics[0])): if len(o2) == 1: break all_entries_at_pos = [entry[i] for entry in o2] most_common_bit = '1' if all_entries_at_pos.count('1') >= len(o2)/2 else '0' o2 = [entry for entry in o2 if entry[i]==most_common_bit] o2dec = int(o2[0], base=2) print(f" [o2]: {o2[0]} {o2dec}")   co2 = copy(diagnostics) for i in range(len(diagnostics[0])): if len(co2) == 1: break all_entries_at_pos = [entry[i] for entry in co2] least_common_bit = '0' if all_entries_at_pos.count('1') >= len(co2)/2 else '1' co2 = [entry for entry in co2 if entry[i]==least_common_bit] co2dec = int(co2[0], base=2) print(f"[co2]: {co2[0]} {co2dec}") print(f"[life support rating]: {o2dec} x {co2dec} = {o2dec * co2dec}")```

2021 Day 03 Part 01 v2

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 data = open('input.txt', 'r', encoding='utf-8').read().splitlines()   N = len(data[0])   gamma = 0 epsilon = 0   for n in range(N): count0 = sum(1 for line in data if line[n] == '0') count1 = len(data) - count0 gamma *= 2 epsilon *= 2 if count0 < count1: gamma += 1 else: epsilon += 1   print(gamma * epsilon)```

2021 Day 03 Part 01

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 with open('input.txt', 'r') as f: lines = f.readlines() diagnostics = [entry.strip() for entry in lines] gamma, epsilon = '', '' for i in range(len(diagnostics[0])): all_entries_at_pos = [entry[i] for entry in diagnostics] if all_entries_at_pos.count('0') > len(diagnostics)/2: gamma += '0' #epsilon += '1' else: gamma += '1' #epsilon += '0' print(f"DEBUG [gamma]: {gamma}\n[epsilon]: {epsilon}") gamma = int(gamma, base=2) #epsilon = int(epsilon, base=2) epsilon = gamma ^ 0b111111111111 print(f"[gamma]: {bin(gamma)} {gamma}\n[epsilon]: {bin(epsilon)} {epsilon}") print(f"[gamma] x [epsilon] = {gamma} x {epsilon} = {gamma * epsilon}")```

2021 Day 02 Part 02

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 with open('input.txt', 'r') as f: lines = f.readlines() commands = [entry.strip() for entry in lines] pos_hor, depth, aim = 0, 0, 0   for command in commands: direction, amount = command.split(' ')[0], int(command.split(' ')[1]) if 'forward' in direction: pos_hor += amount depth += aim * amount elif 'up' in direction: aim -= amount elif 'down' in direction: aim += amount print(f"[horizontal final position] x [final depth] = {pos_hor * depth}")```

2021 Day 02 Part 01

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 with open('input.txt', 'r') as f: lines = f.readlines() commands = [entry.strip() for entry in lines] pos_hor, depth = 0, 0   for command in commands: direction, amount = command.split(' ')[0], int(command.split(' ')[1]) if 'forward' in direction: pos_hor += amount elif 'up' in direction: depth -= amount elif 'down' in direction: depth += amount   print(f"[horizontal final position] x [final depth] = {pos_hor * depth}")```

2021 Day 01 Part 02

Python Slicing

```1 2 3 4 5 6 7 8 9 10 11 f = open("input.txt", "r") depths = f.read().splitlines() depths = [ int(x) for x in depths ] count = 0 prev = None for i in range(len(depths)-2): tridepth = sum(depths[i:i+3]) if prev != None and tridepth > prev: count += 1 prev = tridepth print(f"Number of increases in tri-depth measurements is: {count}")```

2021 Day 01 Part 01

```1 2 3 4 5 6 7 8 9 10 f = open("input.txt", "r") depths = f.read().splitlines() depths = [ int(x) for x in depths ] prev = depths[0] count = 0 for depth in depths[1:]: if depth > prev: count += 1 prev = depth print(f"Number of increases in depth measurements is: {count}")```

How to Advent of Code (Python)

When I say “list of strings” to “array of integers” I should have said “list of integers”.
When installing Python, tick the option “add to path.
When installing Python, change the folder to C:\python or D:\python for ease of use.