-
Notifications
You must be signed in to change notification settings - Fork 4
/
a-improved.py
139 lines (104 loc) · 2.7 KB
/
a-improved.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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
import sys; sys.dont_write_bytecode = True; from utils_improved import *
"""
To do: ensure Code Runner works (in WSL), have preloaded the day and input in Chrome,
saved input into the folder, have utils on the side, collapse regions
Strings, lists, dicts:
lmap, ints, positive_ints, floats, positive_floats, words, keyvalues
Algorithms:
bisect, binary_search, hamming_distance, edit_distance
Data structures:
Linked, UnionFind
use deque for queue: q[0], q.append and q.popleft
List/Vector operations:
GRID_DELTA, OCT_DELTA
lget, lset, fst, snd
padd, pneg, psub, pmul, pdot, pdist1, pdist2sq, pdist2
Matrices:
matmat, matvec, matexp
Previous problems:
knot
Dict things:
dict.keys()
dict.values()
dict.items()
"""
def do_case(inp: str, sample=False):
# READ THE PROBLEM FROM TOP TO BOTTOM OK
def sprint(*a, **k): sample and print(*a, **k)
lines = inp.splitlines()
starting_state = lines[0][len("initial state: "):]
state_transitions = set()
for line in lines[2:]:
left, right = line.split(" => ")
if right == "#":
state_transitions.add(left)
def to_hashable(s):
return "".join(s[0])
def generator():
state = list(starting_state)
offset = 0
def fix():
nonlocal state, offset
while state and state[0] == ".":
state.pop(0)
offset += 1
while state and state[-1] == ".":
state.pop()
fix()
yield (state, offset)
while True:
state = ["."] * 100 + state + ["."] * 100
offset -= 100
old_state = list(state)
for i in range(2,len(state)-2):
if "".join(old_state[i-2:i+3]) in state_transitions:
state[i] = "#"
else:
state[i] = "."
fix()
yield (state, offset)
N = 50000000000
sequence = RepeatingSequence(generator(), to_hashable)
pattern, offset = sequence[N]
offset_offset = sequence.second_repeated_result[1] - sequence.first_repeated_result[1]
offset += offset_offset * sequence.cycle_number(N)
out = 0
for i, c in enumerate(pattern):
if c == "#":
out += offset + i
print(out)
return # RETURNED VALUE DOESN'T DO ANYTHING, PRINT THINGS INSTEAD
run_samples_and_actual([
# Part 1
r"""
initial state: #..#.#..##......###...###
...## => #
..#.. => #
.#... => #
.#.#. => #
.#.## => #
.##.. => #
.#### => #
#.#.# => #
#.### => #
##.#. => #
##.## => #
###.. => #
###.# => #
####. => #
""",r"""
""",r"""
""",r"""
""",r"""
""",r"""
""",r"""
"""],[
# Part 2
r"""
""",r"""
""",r"""
""",r"""
""",r"""
""",r"""
""",r"""
"""], do_case)