### 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

return total_time
end
``````
code of conduct - report abuse  