-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathday10.py
118 lines (100 loc) · 1.93 KB
/
day10.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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
from collections import defaultdict
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
from aocd.models import Puzzle
def solve_puzzle_one(input_array):
diffs = np.diff(sorted(input_array))
unique, counts = np.unique(diffs, return_counts=True)
counts = dict(zip(unique, counts))
print((counts[1] + 1) * (counts[3] + 1))
def solve_puzzle_two_graph(input_array):
"""
Networkx impl is to slow
"""
sort = np.array(sorted(np.append(input_array, 0)))
graph = nx.DiGraph()
graph.add_nodes_from(sort)
for value in sort:
for jump in [1, 2, 3]:
if value + jump in sort:
graph.add_edge(value, value + jump)
# print_graph(graph)
count = 0
for _ in nx.all_simple_paths(graph, 0, sort[-1]):
count += 1
print(count)
def solve_puzzle_two_tribonacci(input_array):
sort = np.array(sorted(input_array))
counter = defaultdict(int)
counter[0] = 1
for value in sort:
counter[value] = counter[value - 1] + counter[value - 2] + counter[value - 3]
print(counter[sort[-1]])
def print_graph(graph):
options = {
"font_size": 12,
"node_size": 500,
"node_color": "white",
"edgecolors": "black",
"linewidths": 1,
}
nx.draw_networkx(graph, None, **options)
# Set margins for the axes so that nodes aren't clipped
ax = plt.gca()
ax.margins(0.10)
plt.axis("off")
plt.show()
def parse_input(data):
return np.fromstring(data, dtype=np.int, sep='\n')
test_input = """16
10
15
5
1
11
7
19
6
12
4"""
test_input2 = """28
33
18
42
31
14
46
20
48
47
24
23
49
45
19
38
39
11
1
32
25
35
8
17
7
9
4
2
34
10
3"""
if __name__ == '__main__':
puzzle = Puzzle(year=2020, day=10)
if False:
array = parse_input(test_input2)
else:
array = parse_input(puzzle.input_data)
print(array)
solve_puzzle_one(array)
solve_puzzle_two_tribonacci(array)