🌟 Advent of Code (AoC) 2023 🌟

import numpy as np


def print_garden(garden, positions, fn):
    d = len(garden)
    r = (-d*2, d*3, 1)
    with open(fn, "w") as f:
        f.write(f"P2\n# {fn}\n{r[1]-r[0]} {r[1]-r[0]}\n3\n")
        for y in range(*r):
            for x in range(*r):
                if (x, y) in positions:
                    f.write("1")
                elif tile(garden, (x, y)) == "#":
                    f.write("0")
                else:
                    f.write("3")
                f.write(" ")
        f.write("\n")


def parse_garden(input):
    garden = input.split("\n")
    for y, row in enumerate(garden):
        x = row.find("S")
        if x >= 0:
            start = (x, y)
            garden[y] = row.replace("S", ".")
            break
    return garden, start


def garden_plots_reached(garden, start, stepsToRecord):
    positions = set()
    reachable = set()
    positions.add(start)
    numPositions = []
    for step in range(1, 1 + max(stepsToRecord)):
        for position in positions:
            for adjacentPosition in adj(position):
                if adjacentPosition not in reachable and tile(garden, adjacentPosition) != "#":
                    reachable.add(adjacentPosition)
        positions, reachable = reachable, positions
        if step in stepsToRecord:
            numPositions.append(len(positions))
            print_garden(garden, positions, f"step{step}.pgm")
    return numPositions


def adj(pos):
    for dX, dY in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
        yield (pos[0] + dX, pos[1] + dY)


def tile(garden, position):
    x, y = position
    dim = len(garden)
    return garden[y % dim][x % dim]


def garden_plots_reached_predict(garden, start, steps):
    # PlotReached(fullGardensToPass) = a + b * fullGardensToPass + c * fullGardensToPass^2
    gardenSize = len(garden)
    fullGardensToPass = steps // gardenSize
    stepsToEvenMultipleOfFullGardens = steps % gardenSize
    # Calculate number of steps for the first 3 full garden extensions, minimum needed to uniquely fix a, b and c
    samples = list(range(3))
    A = np.matrix(list([1, s, s**2] for s in samples))
    Y = garden_plots_reached(
        garden, start, [stepsToEvenMultipleOfFullGardens + gardenSize * s for s in samples])
    X = np.linalg.solve(A, np.array(Y)).astype(np.int64).tolist()
    a, b, c = X
    return a + b * fullGardensToPass + c * fullGardensToPass**2


def solve(input):
    garden, start = parse_garden(input)
    print(garden_plots_reached(garden, start, [64])[0])
    print(garden_plots_reached_predict(garden, start, 26501365))


if __name__ == "__main__":
    solve(open("input/day21.txt").read())

import re
import operator
import itertools
import numpy as np

def is_in_future(curr, initial_pos, vel):
    x_comp = operator.lt if vel[0] < 0 else operator.gt
    y_comp = operator.lt if vel[1] < 0 else operator.gt

    return x_comp(curr[0], initial_pos[0]) and y_comp(curr[1], initial_pos[1])

def solve(lines):
    num_regex = re.compile(r'(-?\d+)')
    equations = []
    for line in lines:
        px, py, pz, vx, vy, vz = map(int, num_regex.findall(line))

        # Calculate the equation for this line (y = mx + b)
        # 20x is to fix floating-point rounding issues; 1x gives a too low answer
        eq = np.polynomial.Polynomial.fit([px, px + 20*vx], [py, py + 20*vy], deg=1).convert()
        equations.append((eq, (px, py), (vx, vy)))

    num_collisions = 0
    for ((a, initial_a, vel_a), (b, initial_b, vel_b)) in itertools.combinations(equations, 2):
        roots = (a - b).roots()
        if roots.size == 0:
            continue

        x = roots[0]
        y = a(x)

        min_pos = 200000000000000
        max_pos = 400000000000000
        if min_pos <= x <= max_pos and min_pos <= y <= max_pos:
            if is_in_future((x, y), initial_a, vel_a) and is_in_future((x, y), initial_b, vel_b):
                num_collisions += 1

    return (num_collisions, 0)

if __name__=='__main__':
    lines = open('data/day24.txt').read().splitlines()
    part1, part2 = solve(lines)
    print(f"Part 1: {part1}")