| Part 1 | Part 2 | Total | |
|---|---|---|---|
| Time | 1:29:11 | >24h | >24h |
(Total time approximately 25:30:00.)
Another one, wow.
from helpers.datagetter import data_in, submit
from helpers.matrix import Matrix
import re
from collections import Counter, defaultdict
import time
import math
ans = 0
din = data_in(split=True, numbers=False)
gas = [*din[0]]
print(gas)
rock_patterns = [
[[1, 1, 1, 1]],
[[0, 1, 0], [1, 1, 1], [0, 1, 0]],
[[0, 0, 1], [0, 0, 1], [1, 1, 1]],
[[1], [1], [1], [1]],
[[1, 1], [1, 1]]
]
def move_rock(rock, x, y):
global placed_rocks
for i in range(len(rock)):
for j in range(len(rock[0])):
if rock[i][j] == 1 and placed_rocks[f"{x+j},{y-i}"] == 1:
return False
return True
def place_rock(rock, x, y):
global placed_rocks, highest
for i in range(len(rock)):
for j in range(len(rock[0])):
if rock[i][j] == 1:
placed_rocks[f"{x+j},{y-i}"] = 1
placed_rocks = defaultdict(int)
for i in range(7):
placed_rocks[f"{i},{0}"] = 1
highest = 0
j = 0
for i in range(2022):
rock = rock_patterns[i % len(rock_patterns)]
x = 2
y = highest + 3 + len(rock)
#print("start", x, y)
while True:
# Move by jets
oldx = x
if gas[j % len(gas)] == '>':
x += 1
print("right")
else:
x -= 1
print("left")
j += 1
if x + len(rock[0]) > 7:
x = 7 - len(rock[0])
elif x < 0:
x = 0
if not move_rock(rock, x, y):
print("bad move")
x = oldx
# Move down
print(x, y, highest)
if not move_rock(rock, x, y-1):
break
else:
y -= 1
place_rock(rock, x, y)
highest = max(highest, y)
print(rock, x, y)
print()
ans = highest
print(ans)
submit(ans)I was very quick to figure out the cycle (and that we needed to use one), but I kept getting off by one or two for the example input, so I threw in the towel way too late. Should have just gone to bed and come at it with a fresh set of eyes in the morning. Anyways, after I finished Day 18, I went back to this, did some debugging, and finally got it!
Essentially, it finds a cycle of states where the top 2000 rows are the same, and at the same place in the jet pattern. Then it multiplies the difference between the heights at the starts of two consecutive cycle loops for however many loops are needed to reach the limit. Then it adds the difference of the remainging heights when the cycle does not evenly divide the cycle. I also needed to add the height that was present at the start of the first cycle.
I'm not sure why 2000 rows works, but some lower numbers don't. I just kept increasing it until it worked. I'm sure there's some smarter way to look for cycles. For example, using 2000 rows on my input finds a cycle of length 1745 and takes 40 seconds to run, but I think there is a shorter one of length ~384 which would be much much faster to compute.
from helpers.datagetter import data_in, submit
from helpers.matrix import Matrix
import re
from collections import Counter, defaultdict
import time
import math
from tqdm import tqdm
ans = 0
din = data_in(split=True, numbers=False)
gas = [*din[0]]
rock_patterns = [
[[1, 1, 1, 1]],
[[0, 1, 0], [1, 1, 1], [0, 1, 0]],
[[0, 0, 1], [0, 0, 1], [1, 1, 1]],
[[1], [1], [1], [1]],
[[1, 1], [1, 1]]
]
def move_rock(rock, x, y):
global placed_rocks
for i in range(len(rock)):
for j in range(len(rock[0])):
if rock[i][j] == 1 and placed_rocks[f"{x+j},{y-i}"] == 1:
return False
return True
def place_rock(rock, x, y):
global placed_rocks, highest
for i in range(len(rock)):
for j in range(len(rock[0])):
if rock[i][j] == 1:
placed_rocks[f"{x+j},{y-i}"] = 1
placed_rocks = defaultdict(int)
for i in range(7):
placed_rocks[f"{i},{0}"] = 1
highest = 0
j = 0
options = {}
first = 0
start = 0
end = 0
p = []
for i in tqdm(range(10000000)):
rock = rock_patterns[i % len(rock_patterns)]
x = 2
y = highest + 3 + len(rock)
orig_j = j
#print("start", x, y)
while True:
#print(x, y)
# Move by jets
oldx = x
if gas[j % len(gas)] == '>':
x += 1
else:
x -= 1
j += 1
if x + len(rock[0]) > 7:
x = 7 - len(rock[0])
elif x < 0:
x = 0
if not move_rock(rock, x, y):
x = oldx
# Move down
if not move_rock(rock, x, y-1):
break
else:
y -= 1
place_rock(rock, x, y)
highest = max(highest, y)
#print(i, i % len(rock_patterns), highest, orig_j % len(gas))
#if i % len(rock_patterns) == 0:
thing = []
for a in range(2000):
temp = []
for z in range(7):
temp.append(str(placed_rocks[f"{z},{highest-a}"]))
thing.append(",".join(temp))
#thing.append("1,1,1,1,1,1,1")
#print("|".join(thing) + "." + str(j % len(gas)))
if "|".join(thing) + "." + str(orig_j % len(gas)) in options:
index = list(options.keys()).index("|".join(thing) + "." + str(orig_j % len(gas))) + 1
if first == 0:
first = index
end = highest
#print("FOUND AT ", list(options.keys()).index("|".join(thing) + "." + str(orig_j % len(gas))) + 1)
if list(options.keys()).index("|".join(thing) + "." + str(orig_j % len(gas))) + 1 == len(options):
start = p[first-1]
break
p.append(highest)
options["|".join(thing) + "." + str(orig_j % len(gas))] = 1
#print("Length", len(options))
pattern_length = len(options) - first + 1
pattern_diff = end - start
print("Pattern Length", pattern_length)
print("Pattern Diff", pattern_diff)
limit = 1000000000000
#limit = 1999
ans += (start) + (((limit - first) // (pattern_length)) * (pattern_diff))
print("ANS", ans)
print((limit - first + 1) % (pattern_length))
print(first - 1 + ((limit - first + 1) % (pattern_length)))
ans += p[first - 1 + ((limit - first) % (pattern_length))] - p[first - 1]
print("ANS", ans)
submit(ans)