Skip to content

Instantly share code, notes, and snippets.

@ferd

ferd/day14.erl Secret

Created Dec 14, 2019
Embed
What would you like to do?
%%% @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).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment