Advent of Code 2022 - Day 16

This one was annoying to get right..
Part 1 is more or less instant, part 2 is super duper slow. Would probably work to memoize some computations, but I just let it run embarrassingly long instead, ~30min

https://github.com/kwando/AoC2022/blob/main/16/day16.livemd

I have this solution that runs in 5 or 10 seconds according on how much you want to cheat.

Here I have the correct solution in 5 seconds with keeping the 50_000 best paths but ymmv.

Oh and I did not refactor so it is ugly

https://github.com/lud/adventofcode/blob/main/lib/solutions/2022/day_16.ex

n/m I’m calculating the pressure relief accumulator wrong.

For part 2, has anyone figured out a way to have the two workers asynchronously search for valves to open? I thought if I cached the state of the valves and the pressure relieved at each minute in an ETS table I could just run the solution to part 1 with [1,2] |> Task.async_stream(fn _ -> do_part1(graph, time) end) but I keep getting an incorrect and inconsistent result:

iex(28)> Day16.Solve.part_2(sample, 30)
{:ok, -1413}
:ok
iex(29)> Day16.Solve.part_2(sample, 30)
{:ok, -1385}
:ok
iex(30)> Day16.Solve.part_2(sample, 30)
{:ok, -1449}
:ok
iex(31)> Day16.Solve.part_2(sample, 30)
{:ok, -1460}
:ok
iex(32)> Day16.Solve.part_2(sample, 30)
{:ok, -1357}

When Solve.part_2 finishes the last call is to destroy the ETS table so artifact from previous runs is not the cause of the variance. I’m assuming it’s a race?

Okay, I finally got a version that completes in a reasonable time for part 2 (albeit still pretty slow). I refactored everything to reduce the amount of code even though this version is slower for part 1 than my original version (or at least it seems that way, did not benchmark it). I am not too proud to admit I had to read a LOT of solutions from others over in the big reddit thread to get a sense of how to approach this. I ended up almost just translating a solution from rust into elixir, which you can probably tell by the use of arrays and bitwise tricks.

My supposition that this was a concurrency problem was way off. It was more a complementary sets problem and probably even better a dynamic programming problem (even though my solution is not really DP).

Anyway, this one pretty much ruined me and I’m probably done for the year. Sad to not get as far as last year though still happy to have learned a lot.
https://github.com/stevensonmt/advent_of_code/blob/2022/2022/day16/lib/day16.ex

This one stumped me. I understood right away it was a path finding exercise, but the detail I can’t wrap my head around is “skipping” valves, as in minute 3-4 in the example. Is the idea that you have to add edges, not just from each valve to its neighbors, but each valve to every other valve, with some sort of cost multiple to account for distance?

I think the general idea for the path-finding is to only consider paths from valuable valves to other valuable valves. I haven’t seen anything more clever than just depth first searching from each possible initial path to a valuable valve and returning the optimal full path. In my solution that’s this bit:

    defp best_path(path_map, targets, start, time, graph) do
    # I've stored the distances between valuable nodes in the "path_map" 
    # with {start, end} keys and distance values.
      for t <- targets,
          travel_time = Map.fetch!(path_map, {start, t}),
          travel_time < time, # ignore any that are not reachable due to running out of time
          relief_duration = time - travel_time, # how much time the valve will be open for
          pressure = value_of_valve(t, graph) * relief_duration,
          remaining = targets |> Enum.reject(&(&1 == t)),
          reduce: 0 do
        best ->
          if remaining == [] do
            min(best, pressure)
          else
            min(best, pressure + best_path(path_map, remaining, t, relief_duration, graph)) 
            # compare current best to sum of current sub_path to rest of the path until time 
            # runs out or all valves are opened and take the best. (In my case pressure relief
            # is a negative value so I take the min.)
          end
      end
    end

only consider paths from valuable valves to other valuable valves

Skipping the zero flow nodes is an easy bit of optimization, but I think the problem with my algo was that it was not looking ahead to see if best next segment leads to the best path overall (so in testing it goes to straight to JJ instead of DD as expected). Still not sure how your func is handling that.

Mine:

find_path = fn minutes_left, paths = [current_path | _], self -> 
  valve_system
  |> Enum.flat_map(fn 
    {valve, {flow, _}} when flow > 0 ->
      if !Enum.find(paths, fn {path, _} -> List.last(path) == valve end) do
        current_valve = current_path |> elem(0) |> List.last()
        path = graph |> :digraph.get_short_path(current_valve, valve) |> Enum.drop(1)
        [{path, (minutes_left - Enum.count(path) - 1) * flow}]
      else
        []
      end
    _ -> 
      [] 
  end)
  |> Enum.sort_by(fn {_, total_flow} -> total_flow end)
  |> List.last()
  |> case do
    nil -> Enum.reduce(paths, 0, fn {_, flow}, total -> total + flow end)
    next_path -> 
      new_minutes_left = minutes_left - (next_path |> elem(0) |> Enum.count()) - 1
      self.(new_minutes_left, [next_path | paths], self)
  end
end

My function is checking from AA to each target valve. Then from each target to each remaining target recursively until all targets have been reached or time is up, taking the max value for each full path.

from each target to each remaining target

Yeah my function isn’t actually searching all paths. Still getting the hang of recursive search functions I guess