Ok, that was a rough one today.
I haven’t found a way to improve the algorithm further. Part 1 runs in .5 seconds, Part 2 in ~ 5 minutes.
I went the way of precalculating all possible paths between non-zero flow rate valves using :digraph.get_short_path/3. Then I recursively calculate the best step. That works find for 1 actor / 30 iterations. For 2 actors / 26 iterations, that is however still a bit much.
Does anybody have a prettier solution?
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 
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 
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.
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
Not sure if you ever got this figured out. If still interested I would just suggest that rather than taking the shortest path for each valve to the head of the last path, you need to search from the head of the last path to each valve. And then your recursion is from the head of that resulting path to the remaining valves with a terminal condition of either time running out or all valves being used.
Thanks, yeah once I accepted that the only way to solve was search the whole path tree I was able to get part 1. Had to give up at part 2 though due to lack of time. Looking forward to trying again next year.
© Copyright Elixir Forum | Terms | Privacy & Cookies
