This is the next to last 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.
Human Generated Solution
OMG this was a journey!
It took me two hours of coding before I gave up and decided to let it run overnight. I had initially considered doing DFS but it was running slowly. So I tried all sorts of optimizations trying to eke something out. Still not fast enough.
So I switched back to integer programming. I can represent this as a constraint satisfaction problem with constaints on the overlaps. This is a good bit faster but still not that fast. So I keep looking at better ways to represent the problem and remove symmetries. Still not fast enough.
So, overnight it is. But this is why I can’t do these sorts of problems: my mind keeps gnawing on them and certainly can’t both gnaw and sleep. So I’m up a couple hours.
Then inspiration hits. Early on one of my optimizations was to check whether a particular instance is hopeless: the total area is less than the required number of active points. But there’s another optimization: what if I just pack them in dumbly in each 3x3 grid. If so I don’t have to fully solve that one.
Now I’m skipping every single instance and after 0.002 seconds I get my answer! I can finally go to bed!
Looking at my solution in morning however I do make a disconcerting realization: in my switch to the satisfaction problem I completely forgot about fips and rotations. But yeah, I’m not gonna fix that given that I never actually use, except in the test example. Tricky tricky!!
using JuMP
using HiGHS
function solve(dims, masks, counts)
n_masks = length(values(masks))
model = Model(HiGHS.Optimizer)
set_silent(model)
@variable(model, bottomlefts[1:(dims[1] - 2), 1:(dims[2] - 2), 1:n_masks], Bin)
# Have to get the right number of each model
@constraint(model, sum(bottomlefts, dims=[1,2])[1,1,:] == counts)
# No overlaps
for xx in 1:(dims[1] - 2), yy in 1:(dims[2] - 2), offset_x in -2:2, offset_y in -2:2
offset_x == 0 && offset_y == 0 && continue
(!(1 <= (xx + offset_x) <= dims[1] - 2) || !(1 <= (yy + offset_y) <= dims[2] - 2)) && continue
for mask_1 in 1:n_masks, mask_2 in mask_1:n_masks
for x1 in 1:3, y1 in 1:3
!((1 <= (x1 + offset_x) <= 3) && (1 <= (y1 + offset_y) <= 3)) && continue
if masks[mask_1][x1, y1] && masks[mask_2][x1 + offset_x, y1 + offset_y]
@constraint(model, bottomlefts[xx, yy, mask_1] + bottomlefts[xx + offset_x, yy + offset_y, mask_2] <= 1)
break
end
end
end
end
optimize!(model)
return is_solved_and_feasible(model)
end
function part1(path="input.txt")
txt = chomp(read(path, String))
lines = split(txt, "\n\n")
shapes = lines[1:(end-1)]
regions = split(lines[end], "\n")
masks = []
for shape in shapes
tmp = split(shape, "\n")
index = parse(Int, tmp[1][1:(end-1)])
push!(masks, stack(collect.(tmp[2:end])) .== '#')
end
tot = 0
for region in regions
left, right = split(region, ": ")
dims = parse.(Int, split(left, "x"))
counts = parse.(Int, split(right, " "))
total_area = prod(dims)
required_area = sum(counts .* sum.(masks))
dumb_area = prod(div.(dims, 3)) * 9
total_area < required_area && continue # skip if it can't possibly work
if dumb_area >= 9 * sum(counts)
tot += 1
else
tot += solve(dims, masks, counts)
end
end
return tot
end
GenAI Solution
It beat me.
It starts by writing a script analyzing the slack distribution!
function parse_shape(lines)
# Filter out empty lines if any
lines = filter(!isempty, lines)
if isempty(lines)
return 0
end
# Count # in the shape
count = 0
for line in lines
count += count_ones(line)
end
return count
end
function count_ones(str)
c = 0
for char in str
if char == '#'
c += 1
end
end
return c
end
function main()
lines = readlines("input.txt")
# Parse shapes
# Shapes are 0 to 5.
# Format:
# 0:
# ...
# <empty line>
# 1:
# ...
# We can just iterate until we find the first query line (contains 'x' and ':')
shape_areas = Dict{Int, Int}()
slacks = Dict{Int, Int}()
current_shape_idx = -1
current_shape_count = 0
query_start_idx = 0
for (i, line) in enumerate(lines)
line = strip(line)
if isempty(line)
continue
end
# Check if it is a shape header "N:"
m_shape = match(r"^(\d+):$", line)
if m_shape !== nothing
if current_shape_idx != -1
shape_areas[current_shape_idx] = current_shape_count
end
current_shape_idx = parse(Int, m_shape.captures[1])
current_shape_count = 0
continue
end
# Check if it is a query line "WxH: ..."
m_query = match(r"^(\d+)x(\d+):", line)
if m_query !== nothing
# Save the last shape
if current_shape_idx != -1
shape_areas[current_shape_idx] = current_shape_count
current_shape_idx = -1
end
query_start_idx = i
break
end
# Must be part of a shape
current_shape_count += count_ones(line)
end
println("Shape Areas: ", shape_areas)
valid_count = 0
total_queries = 0
for i in query_start_idx:length(lines)
line = strip(lines[i])
if isempty(line)
continue
end
# Parse query
# 37x43: 28 31 34 28 24 23
parts = split(line, ":")
dims = split(parts[1], "x")
W = parse(Int, dims[1])
H = parse(Int, dims[2])
region_area = W * H
counts_str = strip(parts[2])
counts = [parse(Int, x) for x in split(counts_str)]
present_area = 0
for (shape_id, count) in enumerate(counts)
# shape_id is 1-based index for counts array, corresponding to shape 0..5
# So shape_id 1 is shape 0
sid = shape_id - 1
present_area += count * get(shape_areas, sid, 0)
end
slack = region_area - present_area
if slack >= 0
valid_count += 1
# Dictionary for slack counts
slacks[slack] = get(slacks, slack, 0) + 1
end
end
println("Total queries: $total_queries")
println("Queries fitting by area: $valid_count")
# Print sorted slack counts
sorted_slacks = sort(collect(slacks), by=x->x[1])
println("Slack distribution:")
for (s, c) in sorted_slacks
println("Slack $s: $c occurrences")
end
end
main()
Then it realizes that there’s a ton of slack and so it doesn’t have to solve anything. So it writes up another verbose version which just does the area checks. Spooky
# Goal: Solve AoC Day 12
# Strategy: Count number of queries where Total Present Area <= Region Area.
# 1. Parse Shapes
# 2. Parse Queries
# 3. Check Condition
# 4. Print Result
function count_ones(str)
return count(c -> c == '#', str)
end
function solve()
if !isfile("input.txt")
println("Error: input.txt not found")
return
end
lines = readlines("input.txt")
shape_areas = Dict{Int, Int}()
current_shape_idx = -1
current_shape_count = 0
query_start_idx = 0
# Parse Shapes
for (i, line) in enumerate(lines)
line = strip(line)
if isempty(line)
continue
end
m_shape = match(r"^(\d+):$", line)
if m_shape !== nothing
if current_shape_idx != -1
shape_areas[current_shape_idx] = current_shape_count
end
current_shape_idx = parse(Int, m_shape.captures[1])
current_shape_count = 0
continue
end
m_query = match(r"^(\d+)x(\d+):", line)
if m_query !== nothing
if current_shape_idx != -1
shape_areas[current_shape_idx] = current_shape_count
current_shape_idx = -1
end
query_start_idx = i
break
end
current_shape_count += count_ones(line)
end
valid_count = 0
# Process Queries
for i in query_start_idx:length(lines)
line = strip(lines[i])
if isempty(line)
continue
end
parts = split(line, ":")
dims = split(parts[1], "x")
W = parse(Int, dims[1])
H = parse(Int, dims[2])
region_area = W * H
counts = [parse(Int, x) for x in split(strip(parts[2]))]
present_area = 0
for (sid, count) in enumerate(counts)
# shapes are 0-indexed, so sid-1
present_area += count * get(shape_areas, sid-1, 0)
end
if present_area <= region_area
valid_count += 1
end
end
println(valid_count)
end
solve()