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
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 ret = []
17 for match in re.match(regex, line).groups():
18 try:
19 ret.append(int(match))
20 except ValueError:
21 ret.append(match)
22
23 return ret
24
25
26def parse_nums(line, negatives=True):
27 num_re = r'-?\d+' if negatives else r'\d+'
28 return [int(n) for n in re.findall(num_re, line)]
29
30
31def new_table(val, width, height):
32 return [[val for _ in range(width)] for _ in range(height)]
33
34
35def transposed(matrix):
36 """Returns the transpose of the given matrix."""
37 return [list(r) for r in zip(*matrix)]
38
39
40def rotated(matrix):
41 """Returns the given matrix rotated 90 degrees clockwise."""
42 return [list(r) for r in zip(*matrix[::-1])]
43
44
45def mul(lst):
46 """Like sum(), but for multiplication."""
47 return reduce(operator.mul, lst, 1) # NOQA
48
49
50def chunks(l, n):
51 """Yield successive n-sized chunks from l."""
52 for i in range(0, len(l), n):
53 yield l[i:i + n]
54
55
56def all_unique(lst):
57 return len(lst) == len(set(lst))
58
59
60def factors(n):
61 """Returns the factors of n."""
62 return sorted(
63 x for tup in (
64 [i, n // i] for i in range(1, int(n ** 0.5) + 1)
65 if n % i == 0)
66 for x in tup)
67
68
69def gcd(a,b):
70 """Compute the greatest common divisor of a and b"""
71 while b > 0:
72 a, b = b, a % b
73 return a
74
75
76def lcm(a, b):
77 """Compute the lowest common multiple of a and b"""
78 return a * b / gcd(a, b)
79
80
81def egcd(a, b):
82 x0, x1, y0, y1 = 1, 0, 0, 1
83 while b:
84 q, a, b = a // b, b, a % b
85 x0, x1 = x1, x0 - q * x1
86 y0, y1 = y1, y0 - q * y1
87 return a, x0, y0
88
89def modinv(a, n):
90 g, x, _ = egcd(a, n)
91 if g == 1:
92 return x % n
93 else:
94 raise ValueError("%d is not invertible mod %d" % (a, n))
95
96def crt(rems, mods):
97 ''' Solve a system of modular equivalences via the Chinese Remainder Theorem.
98 Does not require pairwise coprime moduli. '''
99
100 # copy inputs
101 orems, omods = rems, mods
102 rems = list(rems)
103 mods = list(mods)
104
105 newrems = []
106 newmods = []
107
108 for i in range(len(mods)):
109 for j in range(i+1, len(mods)):
110 g = gcd(mods[i], mods[j])
111 if g == 1:
112 continue
113 if rems[i] % g != rems[j] % g:
114 raise ValueError("inconsistent remainders at positions %d and %d (mod %d)" % (i, j, g))
115 mods[j] //= g
116
117 while 1:
118 # transfer any remaining gcds to mods[j]
119 g = gcd(mods[i], mods[j])
120 if g == 1:
121 break
122 mods[i] //= g
123 mods[j] *= g
124
125 if mods[i] == 1:
126 continue
127
128 newrems.append(rems[i] % mods[i])
129 newmods.append(mods[i])
130
131 rems, mods = newrems, newmods
132
133 # standard CRT
134 s = 0
135 n = 1
136 for k in mods:
137 n *= k
138
139 for i in range(len(mods)):
140 ni = n // mods[i]
141 s += rems[i] * modinv(ni, mods[i]) * ni
142 return s % n, n
143
144
145def min_max_xy(points):
146 if len(points) == 0:
147 return None, None, None, None
148 if type(points[0]) == tuple:
149 min_x = min(p[0] for p in points)
150 max_x = max(p[0] for p in points)
151 min_y = min(p[1] for p in points)
152 max_y = max(p[1] for p in points)
153 else:
154 min_x = min(p.x for p in points)
155 max_x = max(p.x for p in points)
156 min_y = min(p.y for p in points)
157 max_y = max(p.y for p in points)
158
159 return min_x, max_x, min_y, max_y
160
161
162def print_grid(grid, f=None, quiet=False):
163 if f is None:
164 f = lambda x: x # NOQA
165
166 counts = Counter()
167 serialized = []
168
169 if type(grid) is dict:
170 positions = grid.keys()
171 min_x, max_x, min_y, max_y = min_max_xy(positions)
172 if type(positions[0]) is tuple:
173 for y in range(min_y, max_y + 1):
174 row = ''.join(f(grid.get((x, y), ' ')) for x in range(min_x, max_x + 1))
175 if not quiet:
176 print row
177 serialized.append(row)
178 for c in row:
179 counts[c] += 1
180
181 else:
182 # (x, y) => point
183 for y in range(min_y, max_y + 1):
184 row = ''.join(f(grid.get(Point(x, y), ' ')) for x in range(min_x, max_x + 1))
185 if not quiet:
186 print row
187 serialized.append(row)
188 for c in row:
189 counts[c] += 1
190 else:
191 for y in range(len(grid)):
192 row = ''.join(f(grid[y][x]) for x in range(len(grid[0])))
193 if not quiet:
194 print row
195 serialized.append(row)
196 for c in row:
197 counts[c] += 1
198
199 # if not quiet:
200 # print "height={} ({} -> {})".format(max_y - min_y + 1, min_y, max_y)
201 # print "width={} ({} -> {})".format(max_x - min_x + 1, min_x, max_x)
202 # print "Statistics:"
203 # for item, num in counts.most_common():
204 # print "{}: {}".format(item, num)
205
206 return serialized
207
208def resolve_mapping(candidates):
209 resolved = {}
210
211 # Ensure the mapping is key -> set(values).
212 candidates_map = {}
213 for k, v in candidates.items():
214 candidates_map[k] = set(v)
215
216 while len(resolved) < len(candidates_map):
217 for candidate in candidates_map:
218 if len(candidates_map[candidate]) == 1 and candidate not in resolved:
219 r = candidates_map[candidate].pop()
220 for c in candidates_map:
221 candidates_map[c].discard(r)
222
223 resolved[candidate] = r
224 break
225
226 return resolved
227
228
229def memoize(f):
230 """Simple dictionary-based memoization decorator"""
231 cache = {}
232
233 def _mem_fn(*args):
234 hargs = (','.join(str(x) for x in args))
235 if hargs not in cache:
236 cache[hargs] = f(*args)
237 return cache[hargs]
238
239 _mem_fn.cache = cache
240 return _mem_fn
241
242
243def _eratosthenes(n):
244 """http://stackoverflow.com/a/3941967/239076"""
245 # Initialize list of primes
246 _primes = [True] * n
247
248 # Set 0 and 1 to non-prime
249 _primes[0] = _primes[1] = False
250
251 for i, is_prime in enumerate(_primes):
252 if is_prime:
253 yield i
254
255 # Mark factors as non-prime
256 for j in xrange(i * i, n, i): # NOQA
257 _primes[j] = False
258
259
260def primes(n):
261 """Return a list of primes from [2, n)"""
262 return list(_eratosthenes(n))
263
264
265def md5(msg):
266 m = hashlib.md5()
267 m.update(msg)
268 return m.hexdigest()
269
270
271def sha256(msg):
272 s = hashlib.sha256()
273 s.update(msg)
274 return s.hexdigest()
275
276
277def knot_hash(msg):
278 lengths = [ord(x) for x in msg] + [17, 31, 73, 47, 23]
279 sparse = range(0, 256)
280 pos = 0
281 skip = 0
282
283 for _ in range(64):
284 for l in lengths:
285 for i in range(l // 2):
286 x = (pos + i) % len(sparse)
287 y = (pos + l - i - 1) % len(sparse)
288 sparse[x], sparse[y] = sparse[y], sparse[x]
289
290 pos = pos + l + skip % len(sparse)
291 skip += 1
292
293 hash_val = 0
294
295 for i in range(16):
296 res = 0
297 for j in range(0, 16):
298 res ^= sparse[(i * 16) + j]
299
300 hash_val += res << ((16 - i - 1) * 8)
301
302 return '%032x' % hash_val
303
304
305HEX_DIRS = {
306 'N': (1, -1, 0),
307 'NE': (1, 0, -1),
308 'SE': (0, 1, -1),
309 'S': (-1, 1, 0),
310 'SW': (-1, 0, 1),
311 'NW': (0, -1, 1),
312}
313
314
315def hex_distance(x, y, z):
316 """Returns a given hex point's distance from the origin."""
317 return (abs(x) + abs(y) + abs(z)) // 2
318
319
320@total_ordering
321class Point:
322 """Simple 2-dimensional point."""
323 def __init__(self, x, y):
324 self.x = x
325 self.y = y
326
327 def __add__(self, other):
328 return Point(self.x + other.x, self.y + other.y)
329
330 def __sub__(self, other):
331 return Point(self.x - other.x, self.y - other.y)
332
333 def __mul__(self, n):
334 return Point(self.x * n, self.y * n)
335
336 def __div__(self, n):
337 return Point(self.x / n, self.y / n)
338
339 def __neg__(self):
340 return Point(-self.x, -self.y)
341
342 def __eq__(self, other):
343 return self.x == other.x and self.y == other.y
344
345 def __ne__(self, other):
346 return not self == other
347
348 def __lt__(self, other):
349 return self.length < other.length
350
351 def __str__(self):
352 return "({}, {})".format(self.x, self.y)
353
354 def __repr__(self):
355 return "Point({}, {})".format(self.x, self.y)
356
357 def __hash__(self):
358 return hash(tuple((self.x, self.y)))
359
360 def dist(self, other):
361 return math.sqrt((self.x - other.x) ** 2 + (self.y - other.y) ** 2)
362
363 def dist_manhattan(self, other):
364 return abs(self.x - other.x) + abs(self.y - other.y)
365
366 def angle(self, to=None):
367 if to is None:
368 return math.atan2(self.y, self.x)
369 return math.atan2(self.y - to.y, self.x - to.x)
370
371 def rotate(self, turns):
372 """Returns the rotation of the Point around (0, 0) `turn` times clockwise."""
373 turns = turns % 4
374
375 if turns == 1:
376 return Point(self.y, -self.x)
377 elif turns == 2:
378 return Point(-self.x, -self.y)
379 elif turns == 3:
380 return Point(-self.y, self.x)
381 else:
382 return self
383
384 @property
385 def manhattan(self):
386 return abs(self.x) + abs(self.y)
387
388 @property
389 def length(self):
390 return math.sqrt(self.x ** 2 + self.y ** 2)
391
392 def neighbours_4(self):
393 return [self + p for p in DIRS_4]
394
395 def neighbors_4(self):
396 return self.neighbours_4()
397
398 def neighbours(self):
399 return self.neighbours_4()
400
401 def neighbors(self):
402 return self.neighbours()
403
404 def neighbours_8(self):
405 return [self + p for p in DIRS_8]
406
407 def neighbors_8(self):
408 return self.neighbours_8()
409
410
411DIRS_4 = DIRS = [
412 Point(0, 1), # north
413 Point(1, 0), # east
414 Point(0, -1), # south
415 Point(-1, 0), # west
416]
417
418DIRS_8 = [
419 Point(0, 1), # N
420 Point(1, 1), # NE
421 Point(1, 0), # E
422 Point(1, -1), # SE
423 Point(0, -1), # S
424 Point(-1, -1), # SW
425 Point(-1, 0), # W
426 Point(-1, 1), # NW
427]