day14.erl

%%% @doc
%%% welcome to day fourteen, which surely won't beat yesterday
%%% @end
-module(day14).
-export([p1/0, p2/0]).
-ifdef(TEST).
-export([to_graph/2, count_ore/2, max_fuel/2]).
-endif.

p1() ->
    G = digraph:new([acyclic]),
    to_graph(G, advent:input("day14")),
    count_ore(G, {1, "FUEL"}).

p2() ->
    G = digraph:new([acyclic]),
    to_graph(G, advent:input("day14")),
    max_fuel(G, 1000000000000).

max_fuel(G, Break) ->
    {Below, Above} = exp_search(G, 2, Break),
    binary_search(G, Below, Above, Break).

exp_search(G, OldN, BreakingPoint) ->
    N = trunc(math:pow(OldN, 2)),
    Count = count_ore(G, {N, "FUEL"}),
    if Count > BreakingPoint -> {OldN, N}
     ; Count =< BreakingPoint -> exp_search(G, N, BreakingPoint)
    end.

binary_search(G, Below, Above, Break) ->
    Half = Below + ((Above - Below) div 2),
    Count = count_ore(G, {Half, "FUEL"}),
    if Count =:= Break -> Half;
       Half == Below; Half == Above -> Half;
       Count > Break -> binary_search(G, Below, Half, Break);
       Count < Break -> binary_search(G, Half, Above, Break)
    end.

to_graph(G, Str) ->
    Lines = [string:lexemes(string:trim(Line), "=>")
     || Line <- string:lexemes(Str, "\n")],
    digraph:add_vertex(G, "ORE", 1),
    [digraph:add_vertex(G, Name, Ct)
     || [_, Res] <- Lines,
        {Name, Ct} <- [parse_count(Res)]],
    [digraph:add_edge(G, V1, V2, Ct)
     || [Deps, Res] <- Lines,
        {V1, _} <- [parse_count(Res)],
        Dep <- string:lexemes(Deps, ","),
        {V2, Ct} <- [parse_count(Dep)]],
    ok.

parse_count(Str) ->
    [StrInt, Name] = string:lexemes(string:trim(Str), " "),
    {Name, list_to_integer(StrInt)}.

count_ore(G, {Ct, Start}) ->
    maps:get("ORE", count(G, digraph_utils:topsort(G), #{Start => Ct})).

count(_, [], Acc) ->
    Acc;
count(G, [H|T], Acc) ->
    {H, Produced} = digraph:vertex(G, H),
    Needed = maps:get(H, Acc, 0),
    Batches = Needed div Produced
            + (if Needed rem Produced =/= 0 -> 1
                ; true -> 0
               end),
    Deps = [{Name, Batches*ECt}
            || E <- digraph:out_edges(G, H),
               {_,_,Name,ECt} <- [digraph:edge(G, E)]],
    NewAcc = lists:foldl(
        fun({N,C}, Map) ->
            maps:update_with(N, fun(Old) -> Old+C end, C, Map)
        end,
        Acc,
        Deps
    ),
    count(G, T, NewAcc).