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