AoC 2022 | Day 15 | Solutions & Spoilers

[strange breach]

I wonder if it's because I'm artificially assuming the space is finite?

oh, there we go

welp, I'm making lunch while I think about the next part

[strange breach]

hrmmm, I better get this right on the first go because it takes several seconds to check all 4mill rows

[modest nymph]

I figured out my problem: || The regex I was using to parse my puzzle input did not capture negative numbers correctly.|| Lesson learned: write tests to cover each step and not just the analysis part 😄

[strange breach]

how would that not break on the test input? there were negative values in that too

[wary hamlet]

How to approach Part 2? Scanning 4 million lines would be too expensive, I guess.

[strange breach]

I don't know if there's a cleverer solution than making scanning one line cheap enough to do it 4E6 times

[modest nymph]

The way I wrote it caused the parser to simply skip lines that don't fit the pattern.. I'm making it raise an Exception now instead so that it does break on an unparsable line.. Basically, took a shortcut that ended up biting me in the butt 😄

[strange breach]

there are 35 sensors, I suppose the cleverest approach would be to sort the sensors by the x-axis value and then pair wise merge them so you only have ~35 merge operations...

I think I really should use regex to parse the input for day 16

[silver cipher]

p2
this runs in ~.75 ms for me
this might be the algorithm @rancid cliff used```py
from itertools import permutations, product
from re import findall

from time import perf_counter

st = perf_counter()

lines defined by their value at x=0 (slope is 1 or -1)

ranges_a = [] # like / /
ranges_b = [] # like \ \

scanners = []
with open(0) as f:
for line in f:
x, y, bx, by = map(int, findall(r"-?\d+", line))
dist = abs(x-bx) + abs(y-by)

    scanners.append((x, y, dist))

    ranges_a.append((y-x-dist, y-x+dist))
    ranges_b.append((y+x-dist, y+x+dist))

find places where a banned range ends 2 before another one starts

a_candidates = set(hi1+1 for (_, hi1), (lo2, ) in permutations(ranges_a, r=2) if hi1 + 2 == lo2)
b_candidates = set(hi1+1 for (, hi1), (lo2, _) in permutations(ranges_b, r=2) if hi1 + 2 == lo2)

for a, b in product(a_candidates, b_candidates):
# x + a = b - x
# 2x = b - a
# x = (b - a) / 2
p2x = b - a
if p2x & 1:
continue

px = p2x >> 1
py = px + a
for sx, sy, dist in scanners:
    # check if p is in the range of a scanner
    if abs(sx - px) + abs(sy - py) <= dist:
        break
else:
    print(px, py, px * 4000000 + py)
    break

print(f"{(perf_counter() - st) * 1000:.03f}ms")