This is the next installment of my series on solving Advent of Code. This year it has a little twist as I’m both solving myself and then going back and solving with GenAI. For more context read my intro post.
Part 1
Human Solution
The best possible feeling during Advent of Code is when you can straightforwardly apply your Part 1 solution to Part 2. I already had this feeling on Day 3 (where I changed one number) and Day 4 (where I just wrapped my solution in a loop). But as it gets more complicated you don’t just chance upon these opportunities. Often Part 1 tries to tempt you into solving it the obvious way only to reveal in Part 2 that this won’t work. Hence why on Day 3 I decided to do the DP solution even though it was overkill for just two digits.
Now we have a similar situation but we need to figure out what we think is going to happen in part 2. The obvious solution here is to do a BFS to find the shortest number of presses that ends up at the output state. But consider that there’s an entire vector at the end that we’re not using: what could it possibly be? It’s the same length as the vector of indicator lights so it presumably corresponds to each light. I suspect it’ll be something that’ll explode the state space. Like it could be that part 2 is “oh; actually it’s not on and off, but there’s colors and on=white, off=black, but then there’s a lot of colors past that: figure out how to make the lights all black”.
So this leads us to an interesting choice: do we invest in the BFS solution and hope it’s not a trap or try something more clever?
Of course I decide to do the more clever thing. This looks a lot like an integer program: minimize(sum(presses)) subject to the constraint that the correct lights are on. Indeed it’s exactly that but with a subtlety to the light constraint: you can’t exactly introduce a modulus constraint. So you need to add a trick: \(x = y % k\) implies that there is an \(n\) such that \(x = k * n + y\) which is a linear constraint. So you just introduce \(n\) as a convenience variable and it solves nicely.
This is a little bit of a gamble; it could be that our part 2 is no longer expressable as a integer program in which case we have to restart our BFS. But if I’m right that the state space explodes writing up an efficient branch-and-bound algorithm is much harder than just relying on the very efficient solvers. Plus it’s just way faster to write out a JuMP model.
using JuMP
using HiGHS
function solve_opt(toggles, outputs)
n_lights = length(outputs)
n_buttons = size(toggles, 2)
model = Model(HiGHS.Optimizer)
set_silent(model) # lifesaver
@variable(model, presses[1:n_buttons] >= 0, Int)
@variable(model, multiples[1:n_lights] >= 0, Int)
@constraint(model, toggles * presses == 2 * multiples + outputs)
@objective(model, Min, sum(presses))
optimize!(model)
return sum(value(presses))
end
function part1(path = "input.txt")
tot = 0
for line in eachline(path)
vecs = split(line, ' ')
outputs = collect(vecs[1][2:(end-1)]) .== '#'
toggle = zeros(Int, length(outputs), length(vecs) - 2)
for ind in 2:(length(vecs) - 1)
light_indices = parse.(Int, split(vecs[ind][2:(end-1)], ',')) .+ 1
toggle[light_indices, ind-1] .= 1
end
tot += solve_opt(toggle, outputs)
end
return Int(tot)
end
GenAI Solution
For each machine: Construct matrix \(A\) where columns are button vectors. Construct target vector \(b\) from light diagram (offset by initial state which is 0, so just the diagram). Solve \(Ax = b\) over GF(2). Use Gaussian elimination to find RREF. Identify particular solution and null space basis. If unique solution, weight is Hamming weight of solution. If multiple solutions, iterate through linear combinations of null space basis vectors added to particular solution to find minimum integer weight.
And it, uh, does that. It’s super wasteful and doesn’t really make use of any of the Julia ecosystem. And I really am not going to review all of this in the full detail it would need.
using LinearAlgebra
struct Machine
target::Vector{Int}
buttons::Vector{Vector{Int}}
end
function parse_input(filename::String)
machines = Machine[]
lines = readlines(filename)
for line in lines
isempty(strip(line)) && continue
# Parse target state: [...]
m_target = match(r"\[([\.#]+)\]", line)
isnothing(m_target) && continue
target_str = m_target.captures[1]
target = [c == '#' ? 1 : 0 for c in target_str]
# Parse buttons: (...)
# Remove the target part to avoid confusion or regex issues, though regex iteration works fine
# Find all (...) matches
button_matches = eachmatch(r"\(([\d,]+)\)", line)
buttons = Vector{Int}[]
for bm in button_matches
indices = parse.(Int, split(bm.captures[1], ","))
# Create button vector of same length as target, 0s and 1s
btn_vec = zeros(Int, length(target))
for idx in indices
# Indices in input are 0-based, Julia is 1-based
btn_vec[idx + 1] = 1
end
push!(buttons, btn_vec)
end
push!(machines, Machine(target, buttons))
end
return machines
end
# Gaussian elimination over GF(2)
function solve_gf2(A::Matrix{Int}, b::Vector{Int})
rows, cols = size(A)
# Augment A with b
M = hcat(A, b)
pivot_row = 1
pivots = Int[] # which column has the pivot?
for col in 1:cols
if pivot_row > rows
break
end
# Find a row with a 1 in this column, at or below pivot_row
row_with_one = -1
for r in pivot_row:rows
if M[r, col] == 1
row_with_one = r
break
end
end
if row_with_one != -1
# Swap rows
M[pivot_row, :], M[row_with_one, :] = M[row_with_one, :], M[pivot_row, :]
# Eliminate other rows
for r in 1:rows
if r != pivot_row && M[r, col] == 1
M[r, :] = (M[r, :] .+ M[pivot_row, :]) .% 2
end
end
push!(pivots, col)
pivot_row += 1
end
end
# Check consistency
# If any row is all zeros in A part but 1 in b part, no solution
for r in pivot_row:rows
if M[r, end] == 1
return nothing, nothing # No solution
end
end
# Extract particular solution
# The pivot variables are determined by the b column
x_particular = zeros(Int, cols)
for (i, p_col) in enumerate(pivots)
x_particular[p_col] = M[i, end]
end
# Null space basis construction
# Free variables correspond to columns not in pivots
free_cols = setdiff(1:cols, pivots)
basis = Vector{Int}[]
for free in free_cols
# Create a basis vector for this free variable
vec = zeros(Int, cols)
vec[free] = 1 # Set the free variable to 1
# Determine values of pivot variables to satisfy Ax = 0
# For each pivot, if the pivot row 'i' has a 1 in 'free' column,
# then that pivot variable must benefit from the free variable's value to stay 0?
# A_reduced * basis_vec = 0
# pivot_var + \sum (free_vars) = 0 => pivot_var = \sum (free_vars) (mod 2)
for (i, p_col) in enumerate(pivots)
# The row 'i' corresponds to the pivot at 'p_col'
# The equation is: x[p_col] + sum(M[i, f] * x[f]) = 0 (mod 2)
# giving x[p_col] = M[i, free]
if M[i, free] == 1
vec[p_col] = 1
end
end
push!(basis, vec)
end
return x_particular, basis
end
function get_min_presses(x_p, basis)
min_presses = sum(x_p)
# If basis is small, exhaustive search
# In this problem, we just want minimum total presses.
# We can iterate through all combinations of the basis vectors.
n_basis = length(basis)
if n_basis == 0
return min_presses
end
# Iterate 2^n_basis combinations
from = 0
to = (1 << n_basis) - 1
for mask in from:to
# Copy particular solution
curr_x = copy(x_p)
for i in 1:n_basis
if (mask >> (i-1)) & 1 == 1
curr_x = (curr_x .+ basis[i]) .% 2
end
end
w = sum(curr_x)
if w < min_presses
min_presses = w
end
end
return min_presses
end
function solve_system(machine::Machine)
# n lights (rows), m buttons (cols)
n = length(machine.target)
m = length(machine.buttons)
A = zeros(Int, n, m)
for (col, btn) in enumerate(machine.buttons)
A[:, col] = btn
end
b = machine.target
x_p, basis = solve_gf2(A, b)
if isnothing(x_p)
return Inf # Should not happen based on problem desc (guaranteed solvable usually, but let's see)
end
return get_min_presses(x_p, basis)
end
function main()
# Test example first
println("Running Example...")
example_machines = parse_input("prompt.txt")
# Based on prompt.txt, there are lines that are NOT machine descriptions (text)
# The parse_input function handles lines starting with [...] mostly, but prompt.txt has examples in text context.
# The prompt.txt parsing might be tricky if I construct it blindly from the full file.
# Let's extract the known example lines manually for a quick unit test or just rely on robust regex.
# The regex `^\[` might be safer or just looking for the structure.
# My parse_input looks for `[` anywhere, which matches prompt lines 7, 8, 9, 26, 34, 39 etc.
# Duplicate lines in prompt.txt might be an issue if I sum them all.
# Actually, let's just create a dummy file content string for testing.
example_str = raw"""
[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}
[...#.] (0,2,3,4) (2,3) (0,4) (0,1,2) (1,2,3,4) {7,5,12,7,2}
[.###.#] (0,1,2,3,4) (0,3,4) (0,1,2,4,5) (1,2) {10,11,11,5,10,5}
"""
# Write temp example file
open("example_temp.txt", "w") do f
write(f, example_str)
end
ex_machines = parse_input("example_temp.txt")
total_ex = 0
for m in ex_machines
p = solve_system(m)
println("Machine presses: ", p)
total_ex += p
end
println("Total Example Presses: ", total_ex) # Should be 7
println("\nRunning Input...")
machines = parse_input("input.txt")
total_presses = 0
for (i, m) in enumerate(machines)
p = solve_system(m)
if p == Inf
println("Machine $i: No solution")
else
total_presses += p
end
end
println("Total Input Presses: ", Int(total_presses))
end
if abspath(PROGRAM_FILE) == @__FILE__
main()
end
But it works so there!
Part 2
Human Solution
This is the rare case of a simpler part 2! With the integer programming approach we correctly anticipated that we’d use the extra numbers as new constraints. But didn’t anticipate that we’d drop the old constraints! Since that was the hard bit this actually solves a lot faster than part1. Immensely satisfying.
using JuMP
using HiGHS
function solve_opt_2(toggles, joltages)
n_lights = length(outputs)
n_buttons = size(toggles, 2)
model = Model(HiGHS.Optimizer)
set_silent(model) # lifesaver
@variable(model, presses[1:n_buttons] >= 0, Int)
@constraint(model, toggles * presses == joltages)
@objective(model, Min, sum(presses))
optimize!(model)
return sum(value(presses))
end
function part2(path = "input.txt")
tot = 0
for line in eachline(path)
vecs = split(line, ' ')
joltages = parse.(Int, split(vecs[end][2:(end-1)], ','))
toggle = zeros(Int, length(joltages), length(vecs) - 2)
for ind in 2:(length(vecs) - 1)
light_indices = parse.(Int, split(vecs[ind][2:(end-1)], ',')) .+ 1
toggle[light_indices, ind-1] .= 1
end
tot += solve_opt_2(toggle, joltages)
end
return Int(tot)
end
GenAI Solution
Given the outcome for part1 I added to my prompt the request to use existing libraries when possible. And then I fought it when it was like “sure I can use LinearAlgebra’s gaussian elimination” and pushed towards using an integer programming library. And it got so close… I examined the thinking trace and saw
I’ve been thinking about the user’s question regarding integer linear programming packages in Julia. While JuMP with GLPK or HiGHS are obvious choices, the user’s focus on AoC problems suggests prioritizing simplicity and standard libraries initially. I’m leaning towards recommending a practical, straightforward approach unless the problem proves exceptionally complex
But a little more forceful insisting and it eventually gets the message!
using JuMP
using SCIP
struct JoltageMachine
target::Vector{Int}
buttons::Vector{Vector{Int}}
end
function parse_input(filename::String)
machines = JoltageMachine[]
lines = readlines(filename)
for line in lines
isempty(strip(line)) && continue
# Parse joltage target: {...}
m_target = match(r"\{([\d,]+)\}", line)
if isnothing(m_target)
# Try to support prompt.txt where lines might be different or pure text
continue
end
target = parse.(Int, split(m_target.captures[1], ","))
# Parse buttons: (...)
# The regex strategy from part 1 is good
button_matches = eachmatch(r"\(([\d,]+)\)", line)
buttons = Vector{Int}[]
# We need to know the max index to properly size the button vectors
# or we just resize them to match 'target' length
n_counters = length(target)
for bm in button_matches
indices = parse.(Int, split(bm.captures[1], ","))
btn_vec = zeros(Int, n_counters)
for idx in indices
# Indices in input are 0-based, Julia is 1-based
if idx + 1 <= n_counters
btn_vec[idx + 1] = 1
end
end
push!(buttons, btn_vec)
end
push!(machines, JoltageMachine(target, buttons))
end
return machines
end
function solve_machine(machine::JoltageMachine)
n = length(machine.target)
m = length(machine.buttons)
model = Model(SCIP.Optimizer)
set_silent(model)
# Variables: number of presses for each button, must be non-negative integers
@variable(model, x[1:m] >= 0, Int)
# Constraints: sum of button effects must equal target for each counter
for i in 1:n
@constraint(model, sum(machine.buttons[j][i] * x[j] for j in 1:m) == machine.target[i])
end
# Objective: Minimize total presses
@objective(model, Min, sum(x))
optimize!(model)
status = termination_status(model)
if status == MOI.OPTIMAL
return Int(objective_value(model))
else
return nothing
end
end
function main()
println("Running Example...")
# Using the same trick to test specific example lines from prompt/part2
example_str = raw"""
[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}
[...#.] (0,2,3,4) (2,3) (0,4) (0,1,2) (1,2,3,4) {7,5,12,7,2}
[.###.#] (0,1,2,3,4) (0,3,4) (0,1,2,4,5) (1,2) {10,11,11,5,10,5}
"""
open("part2_example_temp.txt", "w") do f
write(f, example_str)
end
ex_machines = parse_input("part2_example_temp.txt")
total_ex = 0
for m in ex_machines
res = solve_machine(m)
if !isnothing(res)
println("Machine presses: ", res)
total_ex += res
else
println("Machine NO SOLUTION")
end
end
println("Total Example Presses: ", total_ex) # Should be 33
println("\nRunning Input...")
machines = parse_input("input.txt")
total_presses = 0
for (i, m) in enumerate(machines)
res = solve_machine(m)
if isnothing(res)
println("Machine $i: No solution")
else
total_presses += res
end
end
println("Total Input Presses: ", total_presses)
end
if abspath(PROGRAM_FILE) == @__FILE__
main()
end