15.md

Day 15

	Part 1	Part 2	Total
Time	56:13	1:13:27	2:09:40

Long one. Finished second in NJIT ACM for Part 1 and first for Part 2.

Part 1

I think Part 1 is off by one. Not sure, I had to subtract 1 from the answer it gave me and I honestly forget why.

from helpers.datagetter import data_in, submit
from tqdm import tqdm

ans = 0
din = data_in(split=True, numbers=True)

y = 2000000
#y = 10
sensed = []
beacons = []


def get_manhattan(posx, posy, dist):
    global sensed, y

    if abs(posy - y) <= dist:
        print(posx, posy, posy - y, dist)
        lr = dist - abs(posy - y)
        sensed.append([posx - lr, posx + lr + 1])


for line in tqdm(din):
    get_manhattan(line[0], line[1], abs(line[0] - line[2]) + abs(line[1] - line[3]))
    if line[3] == y:
        beacons.append(line[2])

print(sensed)
print(beacons)

for i in range(len(sensed)):
    for j in range(len(sensed)):
        if i == j or sensed[i] == [None, None] or sensed[j] == [None, None]:
            continue
        #print(sensed[i], sensed[j])
        if sensed[j][0] > sensed[i][0] and sensed[j][0] < sensed[i][1]:
            sensed[i][1] = sensed[j][0]

        if sensed[j][0] >= sensed[i][0] and sensed[j][1] <= sensed[i][1]:
            sensed[j][0] = None
            sensed[j][1] = None
        #print("Changed to: ", sensed[i], sensed[j])


print()
print(sensed)
print(beacons)

for thing in sensed:
    if thing != [None, None]:
        ans += thing[1] - thing[0]

print(ans)
submit(ans)

Part 2

I had a bug in my datagetter.py helper that made it so it was not getting negative numbers! I have no idea how Part 1 ran. Perhaps none of the scanners in range of line 4000000 didn't have their beacons at negative coordinates. Anyway, after a while I caught that bug and my code ran marvelously... for 3 whole minutes, consuming lots of RAM, and finally spit out the single answer. Pardon the ugly code.

from helpers.datagetter import data_in, submit
from tqdm import tqdm

ans = 0
din = data_in(split=True, numbers=True, n_type=int)

bounds = 4000000
sensed = {}
beacons = []


def get_manhattan(posx, posy, dist):
    global sensed

    for yi in range(bounds+1):
        if yi not in sensed:
            sensed[yi] = []
        if abs(posy - yi) <= dist:
            lr = dist - abs(posy - yi)
            #print(posx, posy, dist, yi, lr, [posx - lr, posx + lr + 1])
            sensed[yi].append([posx - lr, posx + lr + 1])


for line in tqdm(din):
    #print(line[0], line[1], abs(line[0] - line[2]) + abs(line[1] - line[3]))
    get_manhattan(line[0], line[1], abs(line[0] - line[2]) + abs(line[1] - line[3]))
    if [line[2], line[3]] not in beacons:
        beacons.append([line[2], line[3]])
    if [line[0], line[1]] not in beacons:
        beacons.append([line[0], line[1]])

#print(sensed)
#print(beacons)

for y in tqdm(range(bounds+1)):
    for i in range(len(sensed[y])):
        for j in range(len(sensed[y])):
            if i == j or sensed[y][i] == [None, None] or sensed[y][j] == [None, None]:
                continue
            #print(sensed[y][i], sensed[y][j])
            if sensed[y][j][0] >= sensed[y][i][0] and sensed[y][j][1] <= sensed[y][i][1]:
                sensed[y][j][0] = None
                sensed[y][j][1] = None
                continue

            if sensed[y][j][0] >= sensed[y][i][0] and sensed[y][j][0] < sensed[y][i][1]:
                sensed[y][i][1] = sensed[y][j][0]
                continue
            #print("Changed to: ", sensed[i], sensed[j])


for y in tqdm(range(bounds+1)):
    l = []
    for thing in sensed[y]:
        if thing != [None, None]:
            l.append(thing)

    l = sorted(l)
    #print(y, l)

    for i in range(len(l)-1):
        if l[i][1] != l[i+1][0] and l[i+1][0] <= bounds:
            ans = l[i][1] * 4000000 + y
            print(ans)
            submit(ans)
            exit()