@@ 115,46 115,68 @@ sol1(Data) ->
[{_, Val} | _] = search_options_n(Data, Matrix, "AA", 0, sets:new()),
Val.
--define(TIME_LIMIT_2, 26).
+-record(pstate, {path, unseen, time, total}).
-% 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}]).
+paths(Data, Matrix, T) ->
+ Keys = sets:from_list(maps:keys(Data)),
+ Keys0 = sets:del_element("AA", Keys),
+ Valves = sets:filter(fun (Id) ->
+ #valve{flow_rate=FlowRate} = maps:get(Id, Data),
+ FlowRate =/= 0
+ end, Keys0),
+ State = #pstate{path=["AA"], unseen=Valves, time=T, total=0},
+ paths_gen(Data, Matrix, queue:in(State, queue:new()), []).
-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
+paths_gen(Data, Matrix, Q, P) ->
+ case paths_gen_next(Data, Matrix, Q) of
+ done -> P;
+ {ok, Pstate, Q1} -> paths_gen(Data, Matrix, Q1, [Pstate | P])
+ end.
+paths_gen_next(Data, Matrix, Q) ->
+ case queue:out(Q) of
+ {empty, Q} -> done;
+ {{value, State}, Q1} ->
+ #pstate{path=Path, unseen=Unseen, time=Time, total=Total} = State,
+ Cur = hd(Path),
+ Q2 = lists:foldl(fun (Pos, Qn) ->
+ Distance = matrix_get(Cur, Pos, Matrix),
+ if
+ Distance > Time -> Qn;
+ true ->
+ #valve{flow_rate=FlowRate} = maps:get(Pos, Data),
+ Unseen1 = sets:del_element(Pos, Unseen),
+ Time1 = Time - Distance - 1,
+ Total1 = Total + FlowRate * Time1,
+ State1 = #pstate{path=[Pos | Path], unseen=Unseen1, time=Time1, total=Total1},
+ queue:in(State1, Qn)
+ end
+ end, Q1, sets:to_list(Unseen)),
+ {ok, State, Q2}
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.
+sol1_alt(Data) ->
+ Matrix = matrix(Data),
+ Paths = paths(Data, Matrix, 30),
+ lists:foldl(fun
+ (#pstate{total=Total}, undefined) -> Total;
+ (#pstate{total=Total}, Best) -> max(Total, Best)
+ end, undefined, Paths).
+
+mapset_from_list(List) ->
+ maps:from_keys(List, true).
+mapset_del_element(Id, Map) ->
+ maps:remove(Id, Map).
+mapset_is_disjoint(Map1, Map2) ->
+ maps:without(maps:keys(Map2), Map1) =:= Map1.
sol2(Data) ->
Matrix = matrix(Data),
- search_poly(Data, Matrix).
+ Paths = paths(Data, Matrix, 26),
+ Sums = [Total1 + Total2 ||
+ #pstate{path=Path1, total=Total1} <- Paths,
+ #pstate{path=Path2, total=Total2} <- Paths,
+ Total1 + Total2 > 1673,
+ mapset_is_disjoint(
+ mapset_del_element("AA", mapset_from_list(Path1)),
+ mapset_del_element("AA", mapset_from_list(Path2)))],
+ lists:max(Sums).