Day 16: Proboscidea Volcanium

I taught my :elephant: elephant to change places with me if his room name is bigger than mine and that cut the number of search options in half :joy: But this isn’t enough to get the answer fast anyway…

1 Like

This one almost broke me, I was close to skipping the day.

I wasted hours until I realized that if a Valve has only one tunnel the text is shorter (“valves” instead of “valve”). Should have used Find_Token or Index again, but I tried to be “smart”…

Maybe I’ll try it again tomorrow.

I wasn’t sure I was going to finish part B before bedtime, but I managed to get it going and then get gnatprove to be happy with it. Part A runs very quickly, but Part B takes about 60 seconds on my desktop, but only 30 seconds on my laptop with a much newer Ryzen processor.

My Part A strategy is: First thing for both parts is to reduce the graph to only AA and the nodes that have a flow rate, by just calculating the distances from AA to those nodes and between those nodes. I had only 15 such nodes. Then I just do a recursive routine that tries each node that hasn’t been opened yet and makes sure it hasn’t run out of minutes. There’s probably a more efficient way to compute scores, but I generate a list of when each valve opens and then I iterate through each minute.

Part B strategy: After a few false starts, I made two search routines similar to the first. The outer one is searching for the path that I would take. When it gets to the point where it would compute a score, it instead calls the elephant search that starts at AA, but inherits the outer one’s list of visited nodes, so it can only visit nodes the outer one hasn’t. The inner one then calls the scoring routine. I made a separate scoring routine because the outer and inner search routines generate the own lists of when each valve gets open.

1 Like

I’ve looked at both your spoilers and the hints available online and I cannot fathom why my solutions, which as far as I can tell are essentially doing what y’all suggest, are taking so much longer.

Part 1 solved in several tens of minutes; don’t know precisely how many.

Part 2 has been running… and running… and running… I must be misunderstanding something!

i stumbled over this too!

My part 1 works not so long, but part too solves each “minute iteration” longer and longer, so I decided to restrict size of search by dropping solutions which have expected pressure release less then 1/4 of the best found. After that I got the answer :slight_smile:

OK, so the answer seems to be: the next time I think that depth-first search is the answer to the problem… I’m not thinking about it enough.

Based on discussions I saw online, I switched to an adapted breadth-first solution and I have a solution to Part 2 relatively quickly.

Was also stuck with a depth-first search running forever (12 hours before I’ve interrupted it).
I have added a function that filters out too lazy paths, and the run time is down to 7 seconds on the same machine (a lame laptop)

    if time_left = 0 or else score < laziness_filter (time_left) then
      return 0;
    end if;
1 Like