sharparam.com
Code for the Advent of Code event
aoc
advent-of-code
1#!/usr/bin/env ruby
2# frozen_string_literal: true
3
4require 'matrix'
5
6start = nil
7
8GRID = ARGF.readlines(chomp: true).map.with_index do |line, y|
9 line.chars.each_with_index do |char, x|
10 start = Vector[x, y] if char == ?S
11 end
12end
13
14HEIGHT = GRID.size
15WIDTH = GRID[0].size
16raise 'Input must be square' unless HEIGHT == WIDTH
17SIZE = HEIGHT
18
19DIRS = [Vector[1, 0], Vector[-1, 0], Vector[0, 1], Vector[0, -1]].freeze
20
21P2_STEPS = 26_501_365
22
23def reachable(poses)
24 poses.flat_map { |pos| DIRS.map { pos + _1 }.reject { |pos|
25 GRID[pos[1] % HEIGHT][pos[0] % WIDTH] == '#'
26 } }
27end
28
29poses = [start]
30values = []
31n = 0
32
33until values.size == 3
34 n += 1
35 poses = reachable(poses).uniq
36 puts poses.size if n == 64
37 values.push poses.size if n == (P2_STEPS % SIZE) + (SIZE * values.size)
38end
39
40# because magic reasons tells us it's polynomial shitfuckery:
41# P(x) = ax² + bx + c
42# x here is more like the number of grids we've moved
43#
44# P(0) = a * 0² + b * 0 + c
45# = c
46#
47# P(1) = a * 1² + b + c
48# P(1) = a + b + c
49# b = P(1) - a - c
50#
51# P(2) = a * 2² + 2b + c
52# P(2) = 4a + 2b + c
53# 4a = P(2) - 2b - c
54# a = (P(2) - 2b - c) / 4
55# a = (P(2) - 2 * (P(1) - a - c) - c) / 4
56# a = (P(2) - 2 * P(1) + 2a + 2c - c) / 4
57# a = (P(2) - 2 * P(1) + 2a + c) / 4
58# 4a = P(2) - 2 * P(1) + 2a + c
59# 2a = P(2) - 2 * P(1) + c
60# a = (P(2) - 2 * P(1) + c) / 2
61#
62# so because the first three values for P(x) are in `values`:
63# c = P(0) = values[0]
64# a = (P(2) - 2 * P(1) + c) / 2 = (values[2] - 2 * values[1] + c) / 2
65# b = P(1) - a - c = values[1] - a - c
66
67C = values[0]
68A = (values[2] - (2 * values[1]) + C) / 2
69B = values[1] - A - C
70
71# Given that number of steps in part 2 apparently must end on an edge,
72# get which grid index we are on I guess?
73
74# Subtract the steps from start to first edge,
75# so that when we are there, we are on grid index 0
76# i.e. if P2_STEPS would be 65: (65 - 131 / 2) / 131 == 0
77# Each amount of SIZE after that is one more grid, so grid index
78# is simply remaining steps divided by the SIZE
79X = (P2_STEPS - (SIZE / 2)) / SIZE
80
81# puts "Values: #{values}"
82# puts "X = #{X}"
83# puts "A = #{A}"
84# puts "B = #{B}"
85# puts "C = #{C}"
86
87puts (A * (X**2)) + (B * X) + C
88
89# With this, I'm going to put it officially:
90# AoC 2023 day 21 part 2 can suck Santa's lollipop.