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
Another fun one; for some reason is seems like there’s always a graph algorithm towards the end of Advent of Code. This one is relatively straightforward. We’re told it’s a DAG which makes things super easy to do dynamic programming on: you just need to go through the nodes using a topological sort [such that each parent shows up before any of its descendents].
Most of the time was spent figuring out how to get the graph built. Fortunately there’s a nice NamedGraphs package which lets me use the vertex names.
using Graphs
using NamedGraphs
function part1(path = "input.txt")
g = NamedDiGraph()
for line in eachline(path)
source, sinks = split(line, ": ")
sinks = split(sinks, " ")
add_vertex!(g, source)
for sink in sinks
add_vertex!(g, sink)
add_edge!(g, source, sink)
end
end
paths = Dict(node => 0 for node in vertices(g))
paths["you"] = 1
for node in topological_sort(g)
for desc in outneighbors(g, node)
paths[desc] += paths[node]
end
end
return paths["out"]
end
GenAI Solution
The AI comes up with a similar approach with DFS being equivalent to topological sorting.
Use Depth First Search (DFS) with memoization to count paths. Function count_paths(current_node, adj_list, memo): Base case: If current_node == “out”, return 1. If current_node in memo, return memo[current_node]. Recursively sum count_paths for all neighbors. Store result in memo and return.
# Parse the input file into an adjacency list
function parse_input(filename)
adj_list = Dict{String, Vector{String}}()
open(filename, "r") do file
for line in eachline(file)
if isempty(strip(line))
continue
end
parts = split(line, ": ")
src = parts[1]
if length(parts) > 1
dests = split(parts[2], " ")
adj_list[src] = String.(dests)
else
adj_list[src] = String[]
end
end
end
return adj_list
end
# DFS with memoization to count paths
function count_paths(current_node, adj_list, memo)
if current_node == "out"
return 1
end
if haskey(memo, current_node)
return memo[current_node]
end
total_paths = 0
if haskey(adj_list, current_node)
for neighbor in adj_list[current_node]
total_paths += count_paths(neighbor, adj_list, memo)
end
end
memo[current_node] = total_paths
return total_paths
end
function solve(filename)
adj_list = parse_input(filename)
memo = Dict{String, Int}()
# The start node is "you"
return count_paths("you", adj_list, memo)
end
# Run on test input
println("Test Answer: ", solve("test.txt"))
# Run on real input
println("Input Answer: ", solve("input.txt"))
As I’ve come to expect it’s implementing it itself rather than using the Memoize package. I’d go back and modify that myself if this wasn’t a throwaway.
Part 2
Human Solution
Well that escalated quickly. This number is way bigger than the previous one. But our same general approach holds: iterate through the topological sort and update our counters. We’ll just need multiple counters to enumerate which nodes we’ve visited [Neither dac or fft; only dac; only fft; both dac and fft]. Then when we visit either dac or fft we update the counts accordingly.
using Graphs
using NamedGraphs
function part2(path = "input.txt")
g = NamedDiGraph()
for line in eachline(path)
source, sinks = split(line, ": ")
sinks = split(sinks, " ")
add_vertex!(g, source)
for sink in sinks
add_vertex!(g, sink)
add_edge!(g, source, sink)
end
end
# Sort as any_path, fft_visited, dac_visited, both_fft_dac_visited
paths = Dict(node => [0, 0, 0, 0] for node in vertices(g))
paths["svr"] = [1, 0, 0, 0]
for node in topological_sort(g)
for desc in outneighbors(g, node)
if desc == "fft"
paths[desc] .+= [0, paths[node][1], 0, paths[node][3]]
elseif desc == "dac"
paths[desc] .+= [0, 0, paths[node][1], paths[node][2]]
else
paths[desc] += paths[node]
end
end
end
return paths["out"][4]
end
GenAI Solution
Quite happy with this solution. The AI correctly identifies that it just needs to calculate the product of npaths(start, intermediate 1), npaths(intermediate 1, intermediate 2), and npaths(intermediate 2, end).
# Parse the input file into an adjacency list
function parse_input(filename)
adj_list = Dict{String, Vector{String}}()
open(filename, "r") do file
for line in eachline(file)
if isempty(strip(line))
continue
end
parts = split(line, ": ")
src = parts[1]
if length(parts) > 1
dests = split(parts[2], " ")
adj_list[src] = String.(dests)
else
adj_list[src] = String[]
end
end
end
return adj_list
end
# DFS with memoization to count paths between start_node and end_node
function count_paths(current_node, target_node, adj_list, memo)
if current_node == target_node
return 1
end
if haskey(memo, current_node)
return memo[current_node]
end
total_paths = 0
if haskey(adj_list, current_node)
for neighbor in adj_list[current_node]
total_paths += count_paths(neighbor, target_node, adj_list, memo)
end
end
memo[current_node] = total_paths
return total_paths
end
function solve_part2(filename)
adj_list = parse_input(filename)
# Path A: svr -> dac -> fft -> out
memo1 = Dict{String, Int}()
p1 = count_paths("svr", "dac", adj_list, memo1)
memo2 = Dict{String, Int}()
p2 = count_paths("dac", "fft", adj_list, memo2)
memo3 = Dict{String, Int}()
p3 = count_paths("fft", "out", adj_list, memo3)
path_a = p1 * p2 * p3
# Path B: svr -> fft -> dac -> out
memo4 = Dict{String, Int}()
p4 = count_paths("svr", "fft", adj_list, memo4)
memo5 = Dict{String, Int}()
p5 = count_paths("fft", "dac", adj_list, memo5)
memo6 = Dict{String, Int}()
p6 = count_paths("dac", "out", adj_list, memo6)
path_b = p4 * p5 * p6
return path_a + path_b
end
# Part 2 Test
println("Part 2 Test Answer: ", solve_part2("test.txt"))
# Run on real input
println("Part 2 Input Answer: ", solve_part2("input.txt"))