8000 Add day 15 · nthistle/advent-of-code@fc40d95 · GitHub
[go: up one dir, main page]
Skip to content

Commit fc40d95

Browse files
nthistlenthistle
committed
Add day 15
1 parent cf2cb42 commit fc40d95

File tree

4 files changed

+272
-0
lines changed

4 files changed

+272
-0
lines changed

‎2022/day15/aoc_tools.py

Lines changed: 95 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,95 @@
1+
from collections import deque, defaultdict, Counter
2+
import itertools
3+
import re
4+
from typing import TypeVar, Generator, Iterable, Tuple, List
5+
6+
_T = TypeVar("T")
7+
8+
def adjacent_pairs(elements: Iterable[_T]) -> Generator[Tuple[_T, _T], None, None]:
9+
elements_iter = iter(elements)
10+
last_element = next(elements_iter)
11+
for element in elements_iter:
12+
yield (last_element, element)
13+
last_element = element
14+
15+
def all_pairs(elements: Iterable[_T]) -> Generator[Tuple[_T, _T], None, None]:
16+
elements_list = list(elements)
17+
for i in range(len(elements_list)):
18+
for j in range(i + 1, len(elements_list)):
19+
yield (elements_list[i], elements_list[j])
20+
21+
def all_tuples(elements: Iterable[_T]) -> Generator[Tuple[_T, _T], None, None]:
22+
elements_list = list(elements)
23+
for i in range(len(elements_list)):
24+
for j in range(len(elements_list)):
25+
if j == i: continue
26+
yield (elements_list[i], elements_list[j])
27+
28+
29+
# yes, everyone else calls this "cumsum" but ohwell
30+
def rolling_sum(elements: Iterable[_T], start: _T = None) -> List[_T]:
31+
rsum = []
32+
elements_iter = iter(elements)
33+
34+
if start is None:
35+
rsum.append(next(elements_iter))
36+
else:
37+
rsum.append(start)
38+
39+
for element in elements_iter:
40+
rsum.append(rsum[-1] + element)
41+
return rsum
42+
43+
44+
# I did some rough experiments with this version vs. a version that uses a deque, which
45+
# has efficient popleft, and it seems like this version actually wins because of how slow
46+
# iterating over a deque is (which you have to do if you want to use the results)
47+
def rolling_window(
48+
elements: Iterable[_T],
49+
window_size: int,
50+
) -> Generator[Tuple[_T, ...], None, None]:
51+
current_window = []
52+
for element in elements:
53+
current_window.append(element)
54+
if len(current_window) > window_size:
55+
del current_window[0]
56+
if len(current_window) == window_size:
57+
yield current_window
58+
59+
60+
61+
# this is like slightly borked because it doesn't get negative numbers
62+
# oh well i guess
63+
#nums_regex = regex.compile("([^\\d]*)((?P<nums>\\d+)([^\\d]*))*")
64+
65+
def nums(s):
66+
m = nums_regex.match(s)
67+
vals = m.capturesdict()["nums"]
68+
return [int(x) for x in vals]
69+
70+
def nums(s):
71+
m = re.findall("-?\d+", s)
72+
return [int(x) for x in m]
73+
74+
def numsp(s):
75+
m = re.findall("-?\d+", s)
76+
return [int(x) for x in m]
77+
78+
def sign(x):
79+
if x < 0:
80+
return -1
81+
elif x == 0:
82+
return 0
83+
else:
84+
return 1
85+
86+
87+
# underscored names are in case functions get shadowed by accident
88+
adjp = _adjp = adjacent_pairs
89+
ap = _ap = all_pairs
90+
at = _at = all_tuples
91+
rw = _rw = rolling_window
92+
rsum = _rsum = rolling_sum
93+
94+
dd = _dd = defaultdict
95+
ctr = _ctr = Counter

‎2022/day15/day15.py

Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
import string
2+
from collections import defaultdict
3+
from aoc_tools import *
4+
dirs = [(0,1),(1,0),(0,-1),(-1,0)]
5+
6+
with open(r"C:\Users\Neil\Documents\AOC2022\day15\input.txt") as f:
7+
s = f.read().strip()
8+
#print("\n".join(x[:60] for x in s.split("\n")[:6]))
9+
10+
d = [nums(r) for r in s.split("\n")]
11+
12+
dist = lambda x1,y1,x2,y2 : abs(y2-y1) + abs(x2-x1)
13+
14+
c = 0
15+
# (sum>, sum<, x-y>, x-y<)
16+
constraints = []
17+
18+
# if sx,sy = (5,5)
19+
# z = 3
20+
#
21+
# 2,5 => 7
22+
#
23+
# 7,6 = 13
24+
# 8,5 = 13
25+
# 9,4 = 13
26+
#
27+
28+
for sx,sy,bx,by in d:
29+
z = dist(sx,sy,bx,by)
30+
# must be the case that |ty-sy|+|tx-sx|>z
31+
# +,+ ty-sy+tx-sx>z
32+
# +,+ ty+tx>z+sx+sy
33+
# -,+ -ty+sy+tx-sx>z
34+
# -,+ tx-ty>z+sx-sy
35+
# +,- ty-sy-tx+sx>z
36+
# +,- -tx+ty>z-sx+sy
37+
# +,- tx-ty<-z+sx-sy
38+
# -,- -ty+sy-tx+sx>z
39+
# -,- -(tx+ty)>z-sx-sy
40+
# -,- tx+ty<-z+sx+sy
41+
constraints.append(
42+
(z + sx + sy, -z + sx + sy, z + sx - sy, -z + sx - sy)
43+
)
44+
45+
from z3 import *
46+
x = Int("x")
47+
y = Int("y")
48+
sumxy = x + y
49+
difxy = x - y
50+
s = Solver()
51+
for a,b,c,d in constraints:
52+
s.add(Or((sumxy > a), (sumxy < b), (difxy > c), (difxy < d)))
53+
s.add(x >= 0)
54+
s.add(x <= 4000000)
55+
s.add(y >= 0)
56+
s.add(y <= 4000000)
57+
print(s.check())
58+
print(s.model())
59+
60+
###for x in range(-4619876, 4619876):
61+
##for x in range(-9019876, 9019876):
62+
## if x % 100_000 == 0:
63+
## print(x)
64+
## y = 2000000
65+
## poss = True
66+
## for sx,sy,bx,by in d:
67+
## if (x,y) == (bx,by):
68+
## poss = True
69+
## break
70+
## if dist(sx,sy,x,y) <= dist(sx,sy,bx,by):
71+
## poss = False
72+
## break
73+
## if not poss:
74+
## c += 1
75+
##print(c)
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+

‎2022/day15/day15_p1.py

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
import string
2+
from collections import defaultdict
3+
from aoc_tools import *
4+
dirs = [(0,1),(1,0),(0,-1),(-1,0)]
5+
6+
with open(r"C:\Users\Neil\Documents\AOC2022\day15\input.txt") as f:
7+
s = f.read().strip()
8+
9+
d = [nums(r) for r in s.split("\n")]
10+
11+
dist = lambda x1,y1,x2,y2 : abs(y2-y1) + abs(x2-x1)
12+
13+
c = 0
14+
15+
for x in range(-9019876, 9019876):
16+
if x % 100_000 == 0:
17+
print(x)
18+
y = 2000000
19+
poss = True
20+
for sx,sy,bx,by in d:
21+
if (x,y) == (bx,by):
22+
poss = True
23+
break
24+
if dist(sx,sy,x,y) <= dist(sx,sy,bx,by):
25+
poss = False
26+
break
27+
if not poss:
28+
c += 1
29+
print(c)

‎2022/day15/day15_p2.py

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
import string
2+
from collections import defaultdict
3+
from aoc_tools import *
4+
dirs = [(0,1),(1,0),(0,-1),(-1,0)]
5+
6+
with open(r"C:\Users\Neil\Documents\AOC2022\day15\input.txt") as f:
7+
s = f.read().strip()
8+
9+
d = [nums(r) for r in s.split("\n")]
10+
11+
dist = lambda x1,y1,x2,y2 : abs(y2-y1) + abs(x2-x1)
12+
13+
constraints = []
14+
for sx,sy,bx,by in d:
15+
z = dist(sx,sy,bx,by)
16+
# must be the case that |ty-sy|+|tx-sx|>z
17+
# +,+ ty-sy+tx-sx>z
18+
# +,+ ty+tx>z+sx+sy
19+
# -,+ -ty+sy+tx-sx>z
20+
# -,+ tx-ty>z+sx-sy
21+
# +,- ty-sy-tx+sx>z
22+
# +,- -tx+ty>z-sx+sy
23+
# +,- tx-ty<-z+sx-sy
24+
# -,- -ty+sy-tx+sx>z
25+
# -,- -(tx+ty)>z-sx-sy
26+
# -,- tx+ty<-z+sx+sy
27+
constraints.append(
28+
(z + sx + sy, -z + sx + sy, z + sx - sy, -z + sx - sy)
29+
)
30+
31+
from z3 import *
32+
x = Int("x")
33+
y = Int("y")
34+
sumxy = x + y
35+
difxy = x - y
36+
s = Solver()
37+
for a,b,c,d in constraints:
38+
s.add(Or((sumxy > a), (sumxy < b), (difxy > c), (difxy < d)))
39+
s.add(x >= 0)
40+
s.add(x <= 4000000)
41+
s.add(y >= 0)
42+
s.add(y <= 4000000)
43+
print(s.check())
44+
print(s.model()[x].as_long() * 4000000 + s.model()[y].as_long())

0 commit comments

Comments
 (0)
0