-
Notifications
You must be signed in to change notification settings - Fork 3
/
day13.py
65 lines (43 loc) · 1.77 KB
/
day13.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
from collections import defaultdict
from math import gcd
from functools import reduce
with open('./inputs/13.txt') as f:
instructions = f.readlines()
firewall = defaultdict(set)
for line in instructions:
depth, height = (int(n) for n in line.split(': '))
firewall[height].add(depth)
def is_caught(depth, height, delay=0):
return (depth + delay) % (2 * (height - 1)) == 0
def calculate_severity(fw):
severity = 0
for height, depths in fw.items():
for depth in depths:
if is_caught(depth, height):
severity += depth * height
return severity
first = calculate_severity(firewall)
print(first)
# walls which will have only one allowed delay in `find_allowed_delay`
one_remains = lambda h, ds: len(ds) == h - 2
calc_group = [w for w in firewall.items() if one_remains(*w)]
control_group = [w for w in firewall.items() if not one_remains(*w)]
def find_allowed_delay(height, depths):
period = 2 * (height - 1)
potential = set(range(0, period, 2)) # ony even, because of "1: 2" layer
forbidden = {-depth % period for depth in depths}
allowed_delay = (potential - forbidden).pop() # just one value in the set
return allowed_delay, period
def find_delay_params(walls):
potential_delays = {find_allowed_delay(h, ds) for h, ds in walls}
lcm = lambda a, b: a * b // gcd(a, b)
common_multi = reduce(lcm, (period for _, period in potential_delays))
delays = set(range(common_multi))
for delay, period in potential_delays:
s = {delay + i*period for i in range(common_multi // period)}
delays &= s
return delays.pop(), common_multi
delay, step = find_delay_params(calc_group)
while any(is_caught(d, h, delay) for h, ds in control_group for d in ds):
delay += step
print(delay)