16 time to start catching up :)

3 files changed,236insertions(+),0deletions(-) A => 16/input.txt A => 16/sol.erl A => 16/test.txt

A => 16/input.txt +66 -0

@@ 0,0 1,66 @@+Valve DB has flow rate=0; tunnels lead to valves AC, UN +Valve LC has flow rate=6; tunnels lead to valves UV, CM, RD, IM, YQ +Valve SU has flow rate=0; tunnels lead to valves OH, BX +Valve JS has flow rate=0; tunnels lead to valves GR, RW +Valve BX has flow rate=18; tunnels lead to valves PA, SU +Valve WI has flow rate=0; tunnels lead to valves GR, JI +Valve YQ has flow rate=0; tunnels lead to valves LC, SB +Valve HX has flow rate=10; tunnels lead to valves VR, GZ, ID +Valve RI has flow rate=0; tunnels lead to valves HF, UV +Valve JQ has flow rate=0; tunnels lead to valves AA, IF +Valve RK has flow rate=0; tunnels lead to valves AA, CM +Valve AC has flow rate=0; tunnels lead to valves DB, HF +Valve JI has flow rate=12; tunnels lead to valves WI, YH, ND, ID +Valve DF has flow rate=0; tunnels lead to valves JW, AA +Valve PA has flow rate=0; tunnels lead to valves BX, RB +Valve OU has flow rate=0; tunnels lead to valves OH, XM +Valve YO has flow rate=0; tunnels lead to valves OK, HF +Valve YY has flow rate=0; tunnels lead to valves UN, MC +Valve OJ has flow rate=0; tunnels lead to valves SC, GR +Valve VR has flow rate=0; tunnels lead to valves IR, HX +Valve EY has flow rate=0; tunnels lead to valves HR, OK +Valve LE has flow rate=0; tunnels lead to valves GV, GZ +Valve HF has flow rate=14; tunnels lead to valves DS, YO, AC, RI, WP +Valve OM has flow rate=0; tunnels lead to valves DS, GV +Valve JW has flow rate=0; tunnels lead to valves UN, DF +Valve OK has flow rate=9; tunnels lead to valves IF, EY, OV, YO, WM +Valve RB has flow rate=0; tunnels lead to valves PA, XM +Valve HR has flow rate=0; tunnels lead to valves EY, CQ +Valve YM has flow rate=0; tunnels lead to valves GB, NB +Valve UN has flow rate=5; tunnels lead to valves RD, DB, JW, YY, WC +Valve SO has flow rate=0; tunnels lead to valves AA, RH +Valve RW has flow rate=0; tunnels lead to valves JS, GV +Valve IF has flow rate=0; tunnels lead to valves OK, JQ +Valve WP has flow rate=0; tunnels lead to valves HF, CQ +Valve YK has flow rate=0; tunnels lead to valves MO, GV +Valve MQ has flow rate=0; tunnels lead to valves AA, HI +Valve RH has flow rate=0; tunnels lead to valves SO, GB +Valve GB has flow rate=7; tunnels lead to valves YM, RH, PU +Valve XM has flow rate=16; tunnels lead to valves OU, ND, NB, RB +Valve RD has flow rate=0; tunnels lead to valves UN, LC +Valve HI has flow rate=0; tunnels lead to valves MQ, GR +Valve OH has flow rate=19; tunnels lead to valves OU, SU +Valve DS has flow rate=0; tunnels lead to valves OM, HF +Valve GV has flow rate=24; tunnels lead to valves RW, MC, YK, OM, LE +Valve AA has flow rate=0; tunnels lead to valves SO, DF, RK, MQ, JQ +Valve CQ has flow rate=17; tunnels lead to valves SB, MO, WP, SC, HR +Valve UV has flow rate=0; tunnels lead to valves LC, RI +Valve OV has flow rate=0; tunnels lead to valves OK, WC +Valve CM has flow rate=0; tunnels lead to valves RK, LC +Valve YH has flow rate=0; tunnels lead to valves NW, JI +Valve GZ has flow rate=0; tunnels lead to valves LE, HX +Valve WC has flow rate=0; tunnels lead to valves UN, OV +Valve ID has flow rate=0; tunnels lead to valves JI, HX +Valve SC has flow rate=0; tunnels lead to valves OJ, CQ +Valve GR has flow rate=11; tunnels lead to valves OJ, WI, HI, PU, JS +Valve IM has flow rate=0; tunnels lead to valves LC, WM +Valve NB has flow rate=0; tunnels lead to valves YM, XM +Valve TS has flow rate=20; tunnel leads to valve NW +Valve SB has flow rate=0; tunnels lead to valves CQ, YQ +Valve MC has flow rate=0; tunnels lead to valves GV, YY +Valve ND has flow rate=0; tunnels lead to valves JI, XM +Valve MO has flow rate=0; tunnels lead to valves CQ, YK +Valve PU has flow rate=0; tunnels lead to valves GB, GR +Valve IR has flow rate=13; tunnel leads to valve VR +Valve NW has flow rate=0; tunnels lead to valves YH, TS +Valve WM has flow rate=0; tunnels lead to valves IM, OK

A => 16/sol.erl +160 -0

@@ 0,0 1,160 @@+-module(sol). +-compile(export_all). + +-record(valve, {flow_rate, conns}). + +parse(Lines) -> + {ok, Re} = re:compile("Valve ([A-Z]{2}) has flow rate=(\\d+); tunnels? leads? to valves? (.*)$"), + parse(Lines, Re, #{}). + +parse([], _, Data) -> + Data; +parse([Line | Rest], Re, Data) -> + {match, [_, Id, FlowRate, ConnsStr]} = re:run(Line, Re, [{capture, all, list}]), + Conns = string:split(ConnsStr, ", ", all), + Data1 = Data#{Id => #valve{flow_rate=list_to_integer(FlowRate), conns=Conns}}, + parse(Rest, Re, Data1). + +matrix(Data) -> + Matrix = lists:foldl(fun (Id0, Matrix0) -> + Matrix1 = matrix_update(Id0, Id0, 0, Matrix0), + Valve = maps:get(Id0, Data), + Matrix2 = lists:foldl(fun (Id1, Matrix3) -> + matrix_update(Id0, Id1, 1, Matrix3) + end, Matrix1, Valve#valve.conns), + Matrix2 + end, maps:new(), maps:keys(Data)), + matrix_floydwarshall_n(Data, Matrix). + +matrix_floydwarshall(Data, Matrix) -> + Ids = maps:keys(Data), + lists:foldl(fun ({A, B, Detour}, Matrix1) -> + AB = matrix_get(A, B, Matrix1), + AD = matrix_get(A, Detour, Matrix1), + DB = matrix_get(Detour, B, Matrix1), + AdB = distance_add(AD, DB), + case distance_compare(AB, AdB) of + gt -> matrix_update(A, B, AdB, Matrix1); + _ -> Matrix1 + end + end, Matrix, [{A, B, C} || A <- Ids, B <- Ids, C <- Ids]). + +matrix_floydwarshall_n(Data, Matrix) -> + % TODO: Probably something's not right with the above implementation; but I + % couldn't be arsed to solve it properly, so instead you get this fixed point + % search version. + Matrix1 = matrix_floydwarshall(Data, Matrix), + if + Matrix =:= Matrix1 -> Matrix; + true -> matrix_floydwarshall_n(Data, Matrix1) + end. + +matrix_update(A, B, Dist, Matrix) when A > B -> + matrix_update(B, A, Dist, Matrix); +matrix_update(A, B, Dist, Matrix) -> + maps:put({A, B}, Dist, Matrix). + +matrix_get(A, B, Matrix) when A > B -> + matrix_get(B, A, Matrix); +matrix_get(A, B, Matrix) -> + maps:get({A, B}, Matrix, infinity). + +distance_add(infinity, _) -> infinity; +distance_add(_, infinity) -> infinity; +distance_add(A, B) -> A + B. + +distance_compare(X, X) -> eq; +distance_compare(infinity, _) -> gt; +distance_compare(_, infinity) -> lt; +distance_compare(A, B) when A > B -> gt; +distance_compare(A, B) when A < B -> lt. + +-define(TIME_LIMIT, 30). + +search_benefit(Data, Matrix, Current, Id, Time, Open) -> + case sets:is_element(Id, Open) of + true -> 0; + false -> + #valve{flow_rate=FlowRate} = maps:get(Id, Data), + Distance = matrix_get(Current, Id, Matrix), + Benefit = FlowRate * ((?TIME_LIMIT - Time) - (Distance + 1)), + max(Benefit, 0) + end. + +search_options_1(Data, Matrix, Current, Time, Open) -> + Options1 = lists:map(fun (Id) -> + Benefit = search_benefit(Data, Matrix, Current, Id, Time, Open), + {Id, Benefit} + end, maps:keys(Data)), + lists:sort(fun ({_, B1}, {_, B2}) -> B2 =< B1 end, Options1). + +search_options_n(_, _, _, Time, _) when Time >= 30 -> []; +search_options_n(Data, Matrix, Current, Time, Open) -> + Options0 = [Id || {Id, #valve{flow_rate=FlowRate}} <- maps:to_list(Data), FlowRate > 0], + Options = lists:map(fun (Id) -> + case sets:is_element(Id, Open) of + true -> {Id, 0}; + false -> + Distance = matrix_get(Current, Id, Matrix), + Direct = search_benefit(Data, Matrix, Current, Id, Time, Open), + + Time1 = Time + Distance + 1, + Open1 = sets:add_element(Id, Open), + Options1 = search_options_n(Data, Matrix, Id, Time1, Open1), + Indirect = case Options1 of + [] -> 0; + [{_, Max} | _] -> Max + end, + {Id, Direct + Indirect} + end + end, Options0), + lists:sort(fun ({_, B1}, {_, B2}) -> B2 =< B1 end, Options). + +sol1(Data) -> + Matrix = matrix(Data), + [{_, Val} | _] = search_options_n(Data, Matrix, "AA", 0, sets:new()), + Val. + +-define(TIME_LIMIT_2, 26). + +% This approach is paramount to having cheated; +% the idea of evaluating the moves in turn comes from: +% https://old.reddit.com/r/adventofcode/comments/zn6k1l/2022_day_16_solutions/j0fjofh/ +% Still not that fast for Erlang in particular. It's not made for number crunching! +% That said, seems that nobody had a good solution for this one; +% the ones people posted didn't seem that great either. +search_poly(Data, Matrix) -> + Valves = sets:from_list([Id || {Id, #valve{flow_rate=FR}} <- maps:to_list(Data), FR > 0]), + search_poly(Data, Matrix, Valves, [{"AA", 0}, {"AA", 0}]). + +search_poly_end(Data, States) -> + lists:foldl(fun ({Id, T}, Sum) -> + #valve{flow_rate=FlowRate} = maps:get(Id, Data), + Px = FlowRate * (?TIME_LIMIT_2 - T), + Sum + Px + end, 0, States). + +search_poly(Data, Matrix, Pending, States) -> + case lists:all(fun ({_, T}) -> T >= ?TIME_LIMIT_2 end, States) of + true -> 0; + false -> + case sets:is_empty(Pending) of + true -> search_poly_end(Data, States); + false -> search_poly_rot(Data, Matrix, Pending, States) + end + end. + +search_poly_rot(Data, Matrix, Pending, [{Cur, T} | Rest]) -> + #valve{flow_rate=FlowRate} = maps:get(Cur, Data), + Px = FlowRate * (?TIME_LIMIT_2 - T), + Best = lists:foldl(fun (Id, Best) -> + Pending1 = sets:del_element(Id, Pending), + Distance = matrix_get(Cur, Id, Matrix), + Res = search_poly(Data, Matrix, Pending1, Rest ++ [{Id, T + Distance + 1}]), + max(Best, Res) + end, 0, sets:to_list(Pending)), + Px + Best. + +sol2(Data) -> + Matrix = matrix(Data), + search_poly(Data, Matrix).

A => 16/test.txt +10 -0

@@ 0,0 1,10 @@+Valve AA has flow rate=0; tunnels lead to valves DD, II, BB +Valve BB has flow rate=13; tunnels lead to valves CC, AA +Valve CC has flow rate=2; tunnels lead to valves DD, BB +Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE +Valve EE has flow rate=3; tunnels lead to valves FF, DD +Valve FF has flow rate=0; tunnels lead to valves EE, GG +Valve GG has flow rate=0; tunnels lead to valves FF, HH +Valve HH has flow rate=22; tunnel leads to valve GG +Valve II has flow rate=0; tunnels lead to valves AA, JJ +Valve JJ has flow rate=21; tunnel leads to valve II No newline at end of file