8000 Add day 19 (oof) · nthistle/advent-of-code@75a717b · GitHub
[go: up one dir, main page]
Skip to content

Commit 75a717b

Browse files
nthistlenthistle
committed
Add day 19 (oof)
1 parent c7b2208 commit 75a717b

File tree

4 files changed

+521
-0
lines changed

4 files changed

+521
-0
lines changed

‎2022/day19/Solve.java

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
import java.util.*;
2+
3+
public static class Solve {
4+
public static Hash
5+
public static void main(String[] args) {
6+
7+
}
8+
9+
public stat
10+
}

‎2022/day19/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& 8000 quot; 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_w 67E6 indow = []
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/day19/day19.py

Lines changed: 216 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,216 @@
1+
import string
2+
from collections import defaultdict
3+
from aoc_tools import *
4+
import functools
5+
import sys
6+
#sys.setrecursionlimit(10000000)
7+
dirs = ((0,1),(1,0),(0,-1),(-1,0))
8+
dirs3 = ((1,0,0),(-1,0,0),(0,1,0),(0,-1,0),(0,0,1),(0,0,-1))
9+
10+
with open(r"input.txt") as f:
11+
s = f.read().strip()
12+
print("\n".join(x[:60] for x in s.split("\n")[:6]))
13+
14+
s = """Blueprint 1: Each ore robot costs 4 ore. Each clay robot costs 2 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 2 ore and 7 obsidian.
15+
Blueprint 2: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 8 clay. Each geode robot costs 3 ore and 12 obsidian."""
16+
17+
18+
mp = {"ore":0,"clay":1,"obsidian":2}
19+
all_r = []
20+
for jj,l in enumerate(s.split("\n")):
21+
r = l.split(": ")[1]
22+
r = r.strip(".").split(". ")
23+
r = [x[5:] for x in r]
24+
r = [x.split(" costs ") for x in r]
25+
r = [(rt, tuple((int(n), mp[t]) for it in recipe.split(" and ")
26+
for n,t in [it.split(" ")]
27+
)) for rt,recipe in r]
28+
all_r.append((jj + 1, r))
29+
30+
all_pruned_r = []
31+
for i,(idx,r1) in enumerate(all_r):
32+
dominates = True
33+
for _,r2 in all_r[i+1:]:
34+
# check if r2 dominates r1
35+
for (_, rec1), (_, rec2) in zip(r1,r2):
36+
if any(qty1 < qty2 for (_,qty1),(_,qty2) in zip(rec1,rec2)):
37+
dominates = False
38+
break
39+
if not dominates:
40+
print(f"{i} is dominated!")
41+
else:
42+
all_pruned_r.append((idx,r1))
43+
44+
for rnum,r in all_pruned_r:
45+
print("checking bot", rnum)
46+
print(r)
47+
48+
# dp[#ore,#clay,#obs,#geo,t] = max value we can get
49+
50+
rlimits = [0,0,0]
51+
for _, recipe in r:
52+
for qty,typ in recipe:
53+
rlimits[typ] = max(rlimits[typ],qty)
54+
55+
global bbv
56+
bbv = 0
57+
58+
dominated_on_12 = []
59+
dominated_on_14 = []
60+
61+
@functools.lru_cache(maxsize=None)
62+
def solve(resources, robots, t_left):
63+
global bbv
64+
65+
if t_left == 12:
66+
for dresources, drobots in dominated_on_12:
67+
if all(dresources[i] >= resources[i] for i in range(3)) and (
68+
all(drobots[i] >= robots[i] for i in range(4))):
69+
print("PRUNED12!")
70+
return 0
71+
dominated_on_12.append((resources, robots))
72+
73+
if t_left == 14:
74+
for dresources, drobots in dominated_on_14:
75+
if all(dresources[i] >= resources[i] for i in range(3)) and (
76+
all(drobots[i] >= robots[i] for i in range(4))):
77+
print("PRUNED14!")
78+
return 0
79+
dominated_on_14.append((resources, robots))
80+
81+
if t_left >= 12:
82+
print(t_left, resources, robots)
83+
#global d
84+
#d += 1
85+
#if d % 10000 == 0:
86+
# print(resources, robots, t_left,cb)
87+
# resources is 3-tuple
88+
# robots is 4-tuple
89+
new_resources = list(resources)
90+
91+
bv = 0
92+
93+
# if at this point, we can build 1 of every robot, we made a mistake
94+
if robots[1] == 0:
95+
# if we haven't built a clay, and we have at least enough ore to
96+
# build a clay or ore bot, just do it
97+
if resources[0] >= rlimits[0]:
98+
return 0
99+
elif robots[2] == 0:
100+
# if we haven't built an obsidian, and have enough to build
101+
if resources[0] >= rlimits[0] and resources[1] > rlimits[1]:
102+
return 0
103+
elif all(resources[i] >= rlimits[i] for i in range(3)):
104+
return 0
105+
106+
v = 0
107+
for i in range(3):
108+
new_resources[i] += robots[i]
109+
v += robots[3]
110+
111+
if t_left == 1:
112+
return v
113+
114+
## max_builds = [
115+
## min(resources[typ]//qty for qty,typ in r[j][1])
116+
## for j in range(4)
117+
## ]
118+
119+
for i in range(4):
120+
# can we build robot of type i?
121+
if all(resources[typ] >= qty for qty,typ in r[i][1]):
122+
# try building robot of type i?
123+
new_new_resources = new_resources.copy()
124+
125+
126+
127+
## for built_num2 in range(max_builds[-1],-1,-1):
128+
## for built_num in itertools.product(*[range(max_build,-1,-1) for max_build in
129+
## max_builds[:3]]):
130+
## built_num = built_num + (built_num2,)
131+
## new_new_resources = new_resources.copy()
132+
## for i in range(4):
133+
## for qty, typ in r[i][1]:
134+
## new_new_resources[typ] -= qty * built_num[i]
135+
## if min(new_new_resources) < 0:
136+
## continue
137+
##
138+
## new_robots = list(robots)
139+
## for i in range(4):
140+
## new_robots[i] += built_num[i]
141+
## bv = max(bv, v + solve(tuple(new_new_resources),
142+
## tuple(new_robots),
143+
## t_left - 1))
144+
if bv > bbv:
145+
print("MAX:",bv)
146+
bbv = bv
147+
return bv
148+
149+
## ONLY_ORE = 6
150+
## ore_cnt = 0
151+
## ore_rbt = 1
152+
## for i in range(ONLY_ORE):
153+
## n = 0
154+
## if ore_cnt >= r[0][1][0][0]:
155+
## n += ore_cnt // r[0][1][0][0]
156+
## ore_cnt -= n * r[0][1][0][0]
157+
## ore_cnt += ore_rbt
158+
## ore_rbt += n
159+
## print(ore_cnt, ore_rbt)
160+
161+
import time
162+
st = time.time()
163+
print(solve((0,0,0),(1,0,0,0),24))
164+
#print(solve((ore_cnt,0,0),(ore_rbt,0,0,0), 24 - ONLY_ORE))
165+
et = time.time()
166+
print(et - st)
167+
break
168+
169+
170+
171+
172+
173+
174+
175+
176+
177+
178+
179+
180+
181+
182+
183+
184+
185+
186+
187+
188+
189+
190+
191+
192+
193+
194+
195+
196+
197+
198+
199+
200+
201+
202+
203+
204+
205+
206+
207+
208+
209+
210+
211+
212+
213+
214+
215+
216+

0 commit comments

Comments
 (0)
0