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
5from functools import total_ordering
6
7
8LETTERS = [x for x in 'abcdefghijklmnopqrstuvwxyz']
9VOWELS = {'a', 'e', 'i', 'o', 'u'}
10CONSONANTS = set(x for x in LETTERS if x not in VOWELS)
11
12
13def parse_line(regex, line):
14 ret = []
15 for match in re.match(regex, line).groups():
16 try:
17 ret.append(int(match))
18 except ValueError:
19 ret.append(match)
20
21 return ret
22
23
24def parse_nums(line, negatives=True):
25 num_re = r'-?\d+' if negatives else r'\d+'
26 return [int(n) for n in re.findall(num_re, line)]
27
28
29def new_table(val, width, height):
30 return [[val for _ in range(width)] for _ in range(height)]
31
32
33def transposed(matrix):
34 """Returns the transpose of the given matrix."""
35 return [list(r) for r in zip(*matrix)]
36
37
38def rotated(matrix):
39 """Returns the given matrix rotated 90 degrees clockwise."""
40 return [list(r) for r in zip(*matrix[::-1])]
41
42
43def mul(lst):
44 """Like sum(), but for multiplication."""
45 return reduce(operator.mul, lst, 1) # NOQA
46
47
48def chunks(l, n):
49 """Yield successive n-sized chunks from l."""
50 for i in range(0, len(l), n):
51 yield l[i:i + n]
52
53
54def all_unique(lst):
55 return len(lst) == len(set(lst))
56
57
58def factors(n):
59 """Returns the factors of n."""
60 return sorted(
61 x for tup in (
62 [i, n // i] for i in range(1, int(n ** 0.5) + 1)
63 if n % i == 0)
64 for x in tup)
65
66
67def gcd(a,b):
68 """Compute the greatest common divisor of a and b"""
69 while b > 0:
70 a, b = b, a % b
71 return a
72
73
74def lcm(a, b):
75 """Compute the lowest common multiple of a and b"""
76 return a * b / gcd(a, b)
77
78
79def min_max_xy(points):
80 if len(points) == 0:
81 return None, None, None, None
82 if type(points[0]) == tuple:
83 min_x = min(p[0] for p in points)
84 max_x = max(p[0] for p in points)
85 min_y = min(p[1] for p in points)
86 max_y = max(p[1] for p in points)
87 else:
88 min_x = min(p.x for p in points)
89 max_x = max(p.x for p in points)
90 min_y = min(p.y for p in points)
91 max_y = max(p.y for p in points)
92
93 return min_x, max_x, min_y, max_y
94
95
96def print_grid(grid, f=None):
97 if f is None:
98 f = lambda x: x # NOQA
99
100 if type(grid) is dict:
101 positions = grid.keys()
102 min_x, max_x, min_y, max_y = min_max_xy(positions)
103 if type(positions[0]) is tuple:
104 for y in range(min_y, max_y + 1):
105 print ''.join(f(grid.get((x, y), ' ')) for x in range(min_x, max_x + 1))
106 else:
107 # (x, y) => point
108 for y in range(min_y, max_y + 1):
109 print ''.join(f(grid.get(Point(x, y), ' ')) for x in range(min_x, max_x + 1))
110 else:
111 for y in range(len(grid)):
112 print ''.join(f(grid[y][x]) for x in range(len(grid[0])))
113
114
115def memoize(f):
116 """Simple dictionary-based memoization decorator"""
117 cache = {}
118
119 def _mem_fn(*args):
120 if args not in cache:
121 cache[args] = f(*args)
122 return cache[args]
123
124 _mem_fn.cache = cache
125 return _mem_fn
126
127
128def _eratosthenes(n):
129 """http://stackoverflow.com/a/3941967/239076"""
130 # Initialize list of primes
131 _primes = [True] * n
132
133 # Set 0 and 1 to non-prime
134 _primes[0] = _primes[1] = False
135
136 for i, is_prime in enumerate(_primes):
137 if is_prime:
138 yield i
139
140 # Mark factors as non-prime
141 for j in xrange(i * i, n, i): # NOQA
142 _primes[j] = False
143
144
145def primes(n):
146 """Return a list of primes from [2, n)"""
147 return list(_eratosthenes(n))
148
149
150def md5(msg):
151 m = hashlib.md5()
152 m.update(msg)
153 return m.hexdigest()
154
155
156def sha256(msg):
157 s = hashlib.sha256()
158 s.update(msg)
159 return s.hexdigest()
160
161
162def knot_hash(msg):
163 lengths = [ord(x) for x in msg] + [17, 31, 73, 47, 23]
164 sparse = range(0, 256)
165 pos = 0
166 skip = 0
167
168 for _ in range(64):
169 for l in lengths:
170 for i in range(l // 2):
171 x = (pos + i) % len(sparse)
172 y = (pos + l - i - 1) % len(sparse)
173 sparse[x], sparse[y] = sparse[y], sparse[x]
174
175 pos = pos + l + skip % len(sparse)
176 skip += 1
177
178 hash_val = 0
179
180 for i in range(16):
181 res = 0
182 for j in range(0, 16):
183 res ^= sparse[(i * 16) + j]
184
185 hash_val += res << ((16 - i - 1) * 8)
186
187 return '%032x' % hash_val
188
189
190HEX_DIRS = {
191 'N': (1, -1, 0),
192 'NE': (1, 0, -1),
193 'SE': (0, 1, -1),
194 'S': (-1, 1, 0),
195 'SW': (-1, 0, 1),
196 'NW': (0, -1, 1),
197}
198
199
200def hex_distance(x, y, z):
201 """Returns a given hex point's distance from the origin."""
202 return (abs(x) + abs(y) + abs(z)) // 2
203
204
205@total_ordering
206class Point:
207 """Simple 2-dimensional point."""
208 def __init__(self, x, y):
209 self.x = x
210 self.y = y
211
212 def __add__(self, other):
213 return Point(self.x + other.x, self.y + other.y)
214
215 def __sub__(self, other):
216 return Point(self.x - other.x, self.y - other.y)
217
218 def __mul__(self, n):
219 return Point(self.x * n, self.y * n)
220
221 def __div__(self, n):
222 return Point(self.x / n, self.y / n)
223
224 def __neg__(self):
225 return Point(-self.x, -self.y)
226
227 def __eq__(self, other):
228 return self.x == other.x and self.y == other.y
229
230 def __ne__(self, other):
231 return not self == other
232
233 def __lt__(self, other):
234 return self.length < other.length
235
236 def __str__(self):
237 return "({}, {})".format(self.x, self.y)
238
239 def __repr__(self):
240 return "Point({}, {})".format(self.x, self.y)
241
242 def __hash__(self):
243 return hash(tuple((self.x, self.y)))
244
245 def dist(self, other):
246 return math.sqrt((self.x - other.x) ** 2 + (self.y - other.y) ** 2)
247
248 def dist_manhattan(self, other):
249 return abs(self.x - other.x) + abs(self.y - other.y)
250
251 def angle(self, to=None):
252 if to is None:
253 return math.atan2(self.y, self.x)
254 return math.atan2(self.y - to.y, self.x - to.x)
255
256 @property
257 def manhattan(self):
258 return abs(self.x) + abs(self.y)
259
260 @property
261 def length(self):
262 return math.sqrt(self.x ** 2 + self.y ** 2)
263
264 def neighbours_4(self):
265 return [self + p for p in DIRS_4]
266
267 def neighbours_8(self):
268 return [self + p for p in DIRS_8]
269
270
271DIRS_4 = DIRS = [
272 Point(0, 1), # north
273 Point(1, 0), # east
274 Point(0, -1), # south
275 Point(-1, 0), # west
276]
277
278DIRS_8 = [
279 Point(0, 1), # N
280 Point(1, 1), # NE
281 Point(1, 0), # E
282 Point(1, -1), # SE
283 Point(0, -1), # S
284 Point(-1, -1), # SW
285 Point(-1, 0), # W
286 Point(-1, 1), # NW
287]