My Advent of Code solutions in Python.
kevinyap.ca/2019/12/going-fast-in-advent-of-code/
advent-of-code
python
1import re
2import math
3import hashlib
4import operator
5import copy
6from collections import Counter
7from functools import total_ordering, reduce
8
9
10LETTERS = [x for x in 'abcdefghijklmnopqrstuvwxyz']
11VOWELS = {'a', 'e', 'i', 'o', 'u'}
12CONSONANTS = set(x for x in LETTERS if x not in VOWELS)
13
14
15def parse_line(regex, line):
16 """Returns capture groups in regex for line. Int-ifies numbers."""
17 ret = []
18 for match in re.match(regex, line).groups():
19 try:
20 ret.append(int(match))
21 except ValueError:
22 ret.append(match)
23 except TypeError:
24 # None match
25 pass
26
27 return ret
28
29
30def parse_nums(line, negatives=True):
31 """
32 Returns a list of numbers in `line`.
33
34 Pass negatives=False to parse 1-2 as [1, 2].
35 """
36 num_re = r'-?\d+' if negatives else r'\d+'
37 return [int(n) for n in re.findall(num_re, line)]
38
39
40def new_table(width, height, val=None):
41 """Returns a `width` by `height` table populated with `val`."""
42 return [[val for _ in range(width)] for _ in range(height)]
43
44
45def transposed(matrix):
46 """Returns the transpose of the given matrix."""
47 return [list(r) for r in zip(*matrix)]
48
49
50def rotated(matrix):
51 """Returns the given matrix rotated 90 degrees clockwise."""
52 return [list(r) for r in zip(*matrix[::-1])]
53
54def firsts(matrix):
55 """Like matrix[0], but for the first column."""
56 return rotated(matrix)[0]
57
58def lasts(matrix):
59 """Like matrix[-1], but for the last column."""
60 return rotated(matrix)[-1]
61
62
63def mul(lst):
64 """Like sum(), but for multiplication."""
65 return reduce(operator.mul, lst, 1) # NOQA
66
67
68def chunks(l, n):
69 """Yield successive n-sized chunks from l."""
70 for i in range(0, len(l), n):
71 yield l[i:i + n]
72
73def parts(l, n):
74 """Splits l into n equal parts. Excess (if it exists) returned as the n+1-th."""
75 m = len(l) // n
76 for i in range(0, n):
77 yield l[i*m:(i+1)*m]
78
79 if len(l) % n != 0:
80 yield l[m*n:]
81
82
83def all_unique(lst):
84 """Returns True if all items in `lst` are unique."""
85 return len(lst) == len(set(lst))
86
87
88def topsort(graph, tiebreak=None):
89 """
90 Given a graph where graph[x] is an iterable of edges of directed
91 edges originating from x, returns a topologically sorted list of
92 nodes in the graph.
93
94 If `tiebreak` is given, this lambda is passed to sorted() when
95 choosing what node to visit next.
96 """
97 if tiebreak is None:
98 tiebreak = lambda x: x
99
100 visited = set()
101 stack = []
102
103 def _topsort(node):
104 visited.add(node)
105
106 # Reversed because the DFS causes equal level nodes to be popped backwards.
107 for n in sorted(graph[node], key=tiebreak, reverse=True):
108 if n not in visited:
109 _topsort(n)
110
111 stack.append(node)
112
113 for n in sorted(graph, key=tiebreak, reverse=True):
114 if not n in visited:
115 _topsort(n)
116
117 return stack[::-1]
118
119
120def gcd(a,b):
121 """Compute the greatest common divisor of a and b"""
122 while b > 0:
123 a, b = b, a % b
124 return a
125
126
127def lcm(a, b):
128 """Compute the lowest common multiple of a and b"""
129 return a * b / gcd(a, b)
130
131
132def egcd(a, b):
133 x0, x1, y0, y1 = 1, 0, 0, 1
134 while b:
135 q, a, b = a // b, b, a % b
136 x0, x1 = x1, x0 - q * x1
137 y0, y1 = y1, y0 - q * y1
138 return a, x0, y0
139
140def modinv(a, n):
141 g, x, _ = egcd(a, n)
142 if g == 1:
143 return x % n
144 else:
145 raise ValueError("%d is not invertible mod %d" % (a, n))
146
147def crt(rems, mods):
148 """
149 Solve a system of modular equivalences via the Chinese Remainder Theorem.
150 Does not require pairwise coprime moduli.
151
152 Returns (n, m), where n is the solution and m is the modulo.
153
154 Arguments
155 rems: the remainders of the problem
156 mods: the modulos of the problem
157
158 """
159
160 # copy inputs
161 orems, omods = rems, mods
162 rems = list(rems)
163 mods = list(mods)
164
165 newrems = []
166 newmods = []
167
168 for i in range(len(mods)):
169 for j in range(i+1, len(mods)):
170 g = gcd(mods[i], mods[j])
171 if g == 1:
172 continue
173 if rems[i] % g != rems[j] % g:
174 raise ValueError("inconsistent remainders at positions %d and %d (mod %d)" % (i, j, g))
175 mods[j] //= g
176
177 while 1:
178 # transfer any remaining gcds to mods[j]
179 g = gcd(mods[i], mods[j])
180 if g == 1:
181 break
182 mods[i] //= g
183 mods[j] *= g
184
185 if mods[i] == 1:
186 continue
187
188 newrems.append(rems[i] % mods[i])
189 newmods.append(mods[i])
190
191 rems, mods = newrems, newmods
192
193 # standard CRT
194 s = 0
195 n = 1
196 for k in mods:
197 n *= k
198
199 for i in range(len(mods)):
200 ni = n // mods[i]
201 s += rems[i] * modinv(ni, mods[i]) * ni
202 return s % n, n
203
204
205def min_max_xy(points):
206 """
207 For a list of points, returns min_x, max_x, min_y, max_y.
208 This works on tuples (x, y) and Point(x, y).
209 """
210 if len(points) == 0:
211 return None, None, None, None
212 if type(points[0]) == tuple:
213 min_x = min(p[0] for p in points)
214 max_x = max(p[0] for p in points)
215 min_y = min(p[1] for p in points)
216 max_y = max(p[1] for p in points)
217 else:
218 min_x = min(p.x for p in points)
219 max_x = max(p.x for p in points)
220 min_y = min(p.y for p in points)
221 max_y = max(p.y for p in points)
222
223 return min_x, max_x, min_y, max_y
224
225
226def print_grid(grid, f=None, quiet=False):
227 """
228 Outputs `grid` to stdout. This works whether `grid` is a 2D array,
229 or a sparse matrix (dictionary) with keys either (x, y) or Point(x, y).
230
231 This function also returns a tuple (a, b), where a is the serialized
232 representation of the grid, in case what gets printed out to stdout
233 needs to be consumed afterwards, and b is a Counter over the values
234 in `grid`.
235
236 Arguments:
237 f: a function to transform the values of grid to something printable.
238 quiet: don't output to stdout.
239
240 Returns:
241 List[String]: Serialized, printable version of the grid.
242 Counter: The values contained in the grid.
243 """
244 if f is None:
245 f = lambda x: str(x) # NOQA
246
247 counts = Counter()
248 serialized = []
249
250 if type(grid) is dict:
251 positions = list(grid.keys())
252 min_x, max_x, min_y, max_y = min_max_xy(positions)
253 if type(positions[0]) is tuple:
254 for y in range(min_y, max_y + 1):
255 row = ''.join(f(grid.get((x, y), ' ')) for x in range(min_x, max_x + 1))
256 if not quiet:
257 print(row)
258 serialized.append(row)
259 for c in row:
260 counts[c] += 1
261
262 else:
263 # (x, y) => point
264 for y in range(min_y, max_y + 1):
265 row = ''.join(f(grid.get(Point(x, y), ' ')) for x in range(min_x, max_x + 1))
266 if not quiet:
267 print(row)
268 serialized.append(row)
269 for c in row:
270 counts[c] += 1
271 else:
272 min_x = 0
273 min_y = 0
274 for y in range(len(grid)):
275 row = ''.join(f(grid[y][x]) for x in range(len(grid[0])))
276 if not quiet:
277 print(row)
278 serialized.append(row)
279 for x, c in enumerate(row):
280 counts[c] += 1
281 max_x = x
282 max_y = y
283
284 if not quiet:
285 print("height={} ({} -> {})".format(max_y - min_y + 1, min_y, max_y))
286 print("width={} ({} -> {})".format(max_x - min_x + 1, min_x, max_x))
287 print("Statistics:")
288 for item, num in counts.most_common():
289 print("{}: {}".format(item, num))
290
291 return serialized, counts
292
293def resolve_mapping(candidates):
294 """
295 Given a dictionary `candidates` mapping keys to candidate values, returns
296 a dictionary where each `key` maps to a unique `value`. Hangs if intractable.
297
298 Example:
299
300 candidates = {
301 'a': [0, 1, 2],
302 'b': [0, 1],
303 'c': [0],
304 }
305
306 resolve_mapping(candidates) -> {'c': 0, 'b': 1, 'a': 2}
307 """
308 resolved = {}
309
310 # Ensure the mapping is key -> set(values).
311 candidates_map = {}
312 for k, v in candidates.items():
313 candidates_map[k] = set(v)
314
315 while len(resolved) < len(candidates_map):
316 for candidate in candidates_map:
317 if len(candidates_map[candidate]) == 1 and candidate not in resolved:
318 r = candidates_map[candidate].pop()
319 for c in candidates_map:
320 candidates_map[c].discard(r)
321
322 resolved[candidate] = r
323 break
324
325 return resolved
326
327
328def memoize(f):
329 """Simple dictionary-based memoization decorator"""
330 cache = {}
331
332 def _mem_fn(*args):
333 hargs = (','.join(str(x) for x in args))
334 if hargs not in cache:
335 cache[hargs] = f(*args)
336 return cache[hargs]
337
338 _mem_fn.cache = cache
339 return _mem_fn
340
341
342@memoize
343def _eratosthenes(n):
344 """http://stackoverflow.com/a/3941967/239076"""
345 # Initialize list of primes
346 _primes = [True] * n
347
348 # Set 0 and 1 to non-prime
349 _primes[0] = _primes[1] = False
350
351 for i, is_prime in enumerate(_primes):
352 if is_prime:
353 yield i
354
355 # Mark factors as non-prime
356 for j in range(i * i, n, i): # NOQA
357 _primes[j] = False
358
359
360@memoize
361def primes(n):
362 """Return a list of primes from [2, n)"""
363 return list(_eratosthenes(n))
364
365
366@memoize
367def factors(n):
368 """Returns the factors of n."""
369 return sorted(
370 x for tup in (
371 [i, n // i] for i in range(1, int(n ** 0.5) + 1)
372 if n % i == 0)
373 for x in tup)
374
375
376def md5(msg):
377 m = hashlib.md5()
378 m.update(msg)
379 return m.hexdigest()
380
381
382def sha256(msg):
383 s = hashlib.sha256()
384 s.update(msg)
385 return s.hexdigest()
386
387def HASH(code):
388 val = 0
389 for c in code:
390 val += ord(c)
391 val *= 17
392 val %= 256
393 return val
394
395def knot_hash(msg):
396 lengths = [ord(x) for x in msg] + [17, 31, 73, 47, 23]
397 sparse = range(0, 256)
398 pos = 0
399 skip = 0
400
401 for _ in range(64):
402 for l in lengths:
403 for i in range(l // 2):
404 x = (pos + i) % len(sparse)
405 y = (pos + l - i - 1) % len(sparse)
406 sparse[x], sparse[y] = sparse[y], sparse[x]
407
408 pos = pos + l + skip % len(sparse)
409 skip += 1
410
411 hash_val = 0
412
413 for i in range(16):
414 res = 0
415 for j in range(0, 16):
416 res ^= sparse[(i * 16) + j]
417
418 hash_val += res << ((16 - i - 1) * 8)
419
420 return '%032x' % hash_val
421
422
423HEX_DIRS = {
424 'N': (1, -1, 0),
425 'NE': (1, 0, -1),
426 'SE': (0, 1, -1),
427 'S': (-1, 1, 0),
428 'SW': (-1, 0, 1),
429 'NW': (0, -1, 1),
430}
431
432
433def hex_distance(x, y, z):
434 """Returns a given hex point's distance from the origin."""
435 return (abs(x) + abs(y) + abs(z)) // 2
436
437
438def polygon_perimeter(points):
439 """Given a set of bounding box points, returns the perimeter of the polygon."""
440 return sum(a.dist_manhattan(b) for a, b in zip(points, points[1:] + [points[0]]))
441
442
443def polygon_area(points):
444 """Given a set of integer bounding box points, returns the total area of the polygon."""
445 # Use shoelace formula to compute internal area.
446 area = 0
447
448 for a, b in zip(points, points[1:] + [points[0]]):
449 area += (b.x + a.x) * (b.y - a.y)
450
451 area = int(abs(area / 2.0))
452
453 # Calculate perimeter.
454 perimeter = polygon_perimeter(points)
455
456 # Account for outer perimeter strip in final area computation.
457 return area + (perimeter // 2) + 1
458
459
460@total_ordering
461class Point:
462 """Simple 2-dimensional point."""
463 def __init__(self, x, y):
464 self.x = x
465 self.y = y
466
467 def __add__(self, other):
468 return Point(self.x + other.x, self.y + other.y)
469
470 def __sub__(self, other):
471 return Point(self.x - other.x, self.y - other.y)
472
473 def __mul__(self, n):
474 return Point(self.x * n, self.y * n)
475
476 def __div__(self, n):
477 return Point(self.x / n, self.y / n)
478
479 def __neg__(self):
480 return Point(-self.x, -self.y)
481
482 def __eq__(self, other):
483 if type(other) != Point:
484 return False
485 return self.x == other.x and self.y == other.y
486
487 def __ne__(self, other):
488 return not self == other
489
490 def __lt__(self, other):
491 return self.length < other.length
492
493 def __invert__(self):
494 return Point(-self.y, -self.x)
495
496 def __str__(self):
497 return "({}, {})".format(self.x, self.y)
498
499 def __repr__(self):
500 return "Point({}, {})".format(self.x, self.y)
501
502 def __hash__(self):
503 return hash(tuple((self.x, self.y)))
504
505 def dist(self, other):
506 return math.sqrt((self.x - other.x) ** 2 + (self.y - other.y) ** 2)
507
508 def dist_manhattan(self, other):
509 return abs(self.x - other.x) + abs(self.y - other.y)
510
511 def dist_chess(self, other):
512 return max(abs(self.x - other.x), abs(self.y - other.y))
513
514 def dist_chebyshev(self, other):
515 return self.dist_chess(other)
516
517 def angle(self, to=None):
518 if to is None:
519 return math.atan2(self.y, self.x)
520 return math.atan2(self.y - to.y, self.x - to.x)
521
522 def rotate(self, turns):
523 """Returns the rotation of the Point around (0, 0) `turn` times clockwise."""
524 turns = turns % 4
525
526 if turns == 1:
527 return Point(self.y, -self.x)
528 elif turns == 2:
529 return Point(-self.x, -self.y)
530 elif turns == 3:
531 return Point(-self.y, self.x)
532 else:
533 return self
534
535 @property
536 def manhattan(self):
537 return abs(self.x) + abs(self.y)
538
539 @property
540 def chess(self):
541 return max(abs(self.x), abs(self.y))
542
543 @property
544 def chebyshev(self):
545 return self.chess
546
547 @property
548 def length(self):
549 return math.sqrt(self.x ** 2 + self.y ** 2)
550
551 def neighbours_4(self):
552 return [self + p for p in DIRS_4]
553
554 def neighbors_4(self):
555 return self.neighbours_4()
556
557 def neighbours(self):
558 return self.neighbours_4()
559
560 def neighbors(self):
561 return self.neighbours()
562
563 def neighbours_8(self):
564 return [self + p for p in DIRS_8]
565
566 def neighbors_8(self):
567 return self.neighbours_8()
568
569N = Point(0, 1)
570NE = Point(1, 1)
571E = Point(1, 0)
572SE = Point(1, -1)
573S = Point(0, -1)
574SW = Point(-1, -1)
575W = Point(-1, 0)
576NW = Point(-1, 1)
577
578DIRS_4 = DIRS = [
579 Point(0, 1), # north
580 Point(1, 0), # east
581 Point(0, -1), # south
582 Point(-1, 0), # west
583]
584
585DIRS_8 = [
586 Point(0, 1), # N
587 Point(1, 1), # NE
588 Point(1, 0), # E
589 Point(1, -1), # SE
590 Point(0, -1), # S
591 Point(-1, -1), # SW
592 Point(-1, 0), # W
593 Point(-1, 1), # NW
594]
595
596class UnionFind:
597 """
598 If this comes in handy, thank you mcpower!
599 https://www.reddit.com/r/adventofcode/comments/a9c61w/2018_day_25_solutions/eci5kaf/
600 """
601 # n: int
602 # parents: List[Optional[int]]
603 # ranks: List[int]
604 # num_sets: int
605
606 def __init__(self, n: int) -> None:
607 self.n = n
608 self.parents = [None] * n
609 self.ranks = [1] * n
610 self.num_sets = n
611
612 def find(self, i: int) -> int:
613 p = self.parents[i]
614 if p is None:
615 return i
616 p = self.find(p)
617 self.parents[i] = p
618 return p
619
620 def in_same_set(self, i: int, j: int) -> bool:
621 return self.find(i) == self.find(j)
622
623 def merge(self, i: int, j: int) -> None:
624 i = self.find(i)
625 j = self.find(j)
626
627 if i == j:
628 return
629
630 i_rank = self.ranks[i]
631 j_rank = self.ranks[j]
632
633 if i_rank < j_rank:
634 self.parents[i] = j
635 elif i_rank > j_rank:
636 self.parents[j] = i
637 else:
638 self.parents[j] = i
639 self.ranks[i] += 1
640 self.num_sets -= 1