1 files changed, 58 insertions(+), 36 deletions(-)

M 16/sol.erl
M 16/sol.erl +58 -36
@@ 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).