### re: AoC Day 7: The Sum of Its Parts VIEW POST

I quite liked this puzzle! It took me a few false starts-- I couldn't decide whether to track a step's dependencies or dependents --but ultimately I quite like the way my code turned out. Calling sort on every step seemed...wasteful...to me, but it was fast enough, so it all worked out in the end.

Here's my Julia code (boring parsing, etc. omitted but available here)

function step_ordering(input)
step_map = parse_input(input)
result = alpha_bfs(step_map)

return result
end

function alpha_bfs(step_map)
roots = find_roots(step_map)
result = ""
seen = Set()
while (!isempty(roots))
sort!(roots)
found = popfirst!(roots)
result *= found

for other in values(step_map)
delete!(other.prev, found)
if isempty(other.prev) && !(other.name in seen)
push!(seen, other.name)
push!(roots, other.name)
end
end
end
return result
end

function find_roots(step_map)
all_nodes = Set{String}()
for node in values(step_map)
for prev in node.prev
push!(all_nodes, prev)
end
end

return collect(setdiff(all_nodes, keys(step_map)))
end

Part 2 was also enjoyable-- I briefly considered actually spawning 5 worker threads and keeping a global clock, but then I realized I could just track how much work was being done in between tracking which nodes are now available.

function costed_alpha_bfs(step_map)
roots = find_roots(step_map)
result = ""
seen = Set()
total_time = 0
costs = Dict{String, Int}()
base_cost = 60
max_workers = 5
workers = max_workers
while (!isempty(roots) || !isempty(costs))
sort!(roots)
while workers > 0 && !isempty(roots)
found = popfirst!(roots)
costs[found] = cost_of_node(found) + base_cost
workers -= 1
end

(cost,found) = findmin(costs)
result *= found
total_time += cost
workers = min(max_workers, workers+1)

delete!(costs, found)
for in_progress in keys(costs)
costs[in_progress] -= cost
end

for other in values(step_map)
delete!(other.prev, found)
if isempty(other.prev) && !(other.name in seen)
push!(seen, other.name)
push!(roots, other.name)
end
end
end