Discussion on: AoC Day 7: The Sum of Its Parts

[Mustafa Haddara]

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