21.md

Day 21

Part 2 very hard, solved on 12/24.

	Part 1	Part 2	Total
Time	11:11	>24h	>24h

Part 1

Easy Part 1, just bruteforce calculate it with BFS. Not much of note.

Oh, there is one bug which was slightly annoying for Part 2. The "S" position should be considered walkable, which was an error when generating the world map (line 13). That's why I had to add one at the end.

from helpers.datagetter import aocd_data_in
from helpers.matrix import Matrix

din, aocd_submit = aocd_data_in(split=True, numbers=False)
ans = 0

garden = Matrix([len(din), len(din[0])], 0)
start = ()

for i in range(len(din)):
    for j in range(len(din[0])):
        if din[i][j] in "#S":
            garden.set([i, j], 1)
        if din[i][j] == "S":
            start = (i, j, 0)

visited = set()
positions = set()
queue = [start]

while queue:
    node = queue.pop(0)
    x, y, moved = node
    curr = (x, y)

    if node in visited:
        continue
    if moved >= 64:
        positions.add(curr)
        continue
    visited.add(node)

    for val, pos in garden.neighbors(list(curr)):
        if val == 0:
            queue.append(tuple([pos[0], pos[1], moved + 1]))

aocd_submit(len(positions) + 1)

Part 2

After noticing that the global leaderboard for Part 2 was not filling up, I decided to just go to bed, but not before trying some things. Proudly, one of the first things I had tried was plugging some numbers from the example into a quadratic regression calculator and noticing that they closely predicted some of the higher example numbers. But the residuals were quite bad and would obviously blow out of proportion on the scale which we needed for Part 2. So, before bed, my friends and I from NJIT decided to look at the Reddit to see what the answer was looking to be.

Quadratic regression! But specifically with regard to the special fact that (26501365 % 131) == 65, where 131 is the width and height of the square input plot, and 65 is the exact center. It should also be noted that from (65, 65) to each edge of the plot was unobstructed, causing a perfect quadratic relation to form if you check the numbers of valid positions every 65 + k * 131 steps. The first three are obviously then enough to get the equation to predict the value at X = 26501365.

I solved it with an online quadratic regression calculator then wanted to code it, but didn't feel like taking too long so I referenced a solution by mgtezak I found online pretty much verbatim.

There is also some optimization in there that I made along the way for computing the number of possible locations after each step, but it was pretty common among other solutions, so I don't feel like I need to add an explanation for that. In fact, others' explanations for this day's are way better, so I recommend checking out r/AdventOfCode for the satisfying maths.

from helpers.datagetter import aocd_data_in
from helpers.matrix import Matrix
from collections import deque

din, aocd_submit = aocd_data_in(split=True, numbers=False)

garden = Matrix([len(din), len(din[0])], 0, wrap=True)
start = []

for i in range(len(din)):
    for j in range(len(din[0])):
        if din[i][j] in "#":
            garden.set([i, j], 1)
        if din[i][j] == "S":
            start = (i, j)

queue = deque([start])
visited = set()
evenodd = [0, 0]
first_few = []
for i in range(1, 26501365):
    for _ in range(len(queue)):
        place = queue.popleft()
        for val, pos in garden.neighbors(place):
            if tuple(pos) in visited:
                continue
            if val == 0:
                visited.add(tuple(pos))
                queue.append(pos)
                evenodd[i % 2] += 1

    if i % 131 == 65:
        first_few.append(evenodd[i % 2])
        if len(first_few) == 3:
            break

# Credit to mgtezak ; https://github.com/mgtezak/Advent_of_Code/blob/master/2023/Day_21.py
y = first_few
a = (y[2] - (2 * y[1]) + y[0]) // 2
b = y[1] - y[0] - a
c = y[0]
x = (26501365 - 65) // 131

aocd_submit((a * x**2) + (b * x) + c)