My Advent of Code solutions in Python.
kevinyap.ca/2019/12/going-fast-in-advent-of-code/
advent-of-code
python
1import sys
2import fileinput
3from hashlib import md5
4from collections import defaultdict
5
6from utils import memoize
7
8
9@memoize
10def salty_md5(salt, i):
11 return md5('{}{}'.format(salt, i)).hexdigest()
12
13
14@memoize
15def stretched_md5(salt, i):
16 h = salty_md5(salt, i)
17 for _ in range(2016):
18 h = md5(h).hexdigest()
19
20 return h
21
22
23def first_triple(s):
24 for i in range(len(s) - 2):
25 a, b, c = s[i:i+3]
26 if a == b == c:
27 return a
28
29
30def all_quintuples(s):
31 for i in range(len(s) - 4):
32 a, b, c, d, e = s[i:i+5]
33 if a == b == c == d == e:
34 yield a
35
36
37def find_64th_pad_key(salt, hash_fn):
38 valid_keys = 0
39 triples = {}
40 quintuples = defaultdict(set)
41 i = 0
42
43 while True:
44 digest = hash_fn(salt, i)
45 triple = first_triple(digest)
46
47 if triple is not None:
48 triples[i] = triple
49
50 for quint in all_quintuples(digest):
51 quintuples[i].add(quint)
52
53 if (i - 1000) in triples:
54 n = i - 1000
55 triple = triples[n]
56 for j in range(n + 1, n + 1001):
57 if triple in quintuples[j]:
58 valid_keys += 1
59 sys.stdout.write('.')
60 sys.stdout.flush()
61
62 if valid_keys >= 64:
63 return n
64
65 break
66
67 i += 1
68
69
70if __name__ == "__main__":
71 SALT = fileinput.input()[0].strip()
72 print "Index of 64th one-time pad key", find_64th_pad_key(SALT, salty_md5)
73 print "Index of key-stretched pad key", find_64th_pad_key(SALT, stretched_md5)