`minimize` should be able to trim/attempt to trim steps that mostly undo other steps

[Zannick]

Excerpt from the minimize diff:

   Take exit Glacier > Grid 31,9-12 > Midair ==> Ebih > Base Camp > East 11 (1)
   Move... to Ebih > Base Camp > Bunker Entry
   Take exit Ebih > Base Camp > Bunker Entry ==> Interior > Bunker Interior > Entry (1)
-  Move... to Interior > Bunker Interior > Desk
-  Move... to Interior > Bunker Interior > Entry
   Take exit Interior > Bunker Interior > Entry ==> Ebih > Base Camp > Bunker Entry (1)
   Move... to Ebih > Base Camp > Save Point
   Move... to Ebih > Base Camp > Tent Entry
   Take exit Ebih > Base Camp > Tent Entry ==> Interior > Tent Interior > Entry (1)
-  Move... to Interior > Tent Interior > Desk
-  Move... to Interior > Tent Interior > Entry
   Take exit Interior > Tent Interior > Entry ==> Ebih > Base Camp > Tent Entry (1)
   Move... to Ebih > Base Camp > West 13

With the old steps removed, this route enters Interior > Bunker Interior (line 3) then immediately exits it (line 6). Because AV2 tracks the previous area, this is not a duplicate state, and if we observed the previous area (which I think we do on every movement) then we don't get to use the solve trie. However, attempting a full route replay would show us that it works. The challenge, of course, is figuring out where to skip ahead to.

[Zannick]

One simpler option is to have some context fields ignored for observation purposes (or matching trie purpose). We already discard a trimming attempt if we can't actually perform the replay for whatever reason, so we won't need to rearchitect anything to prevent crashes.

This would be computationally less expensive than trying to detect where a route is looped, not to mention may cover other scenarios. On the other hand, there are relatively few solutions so it may be feasible to run that kind of minimization only on solutions.

Such a minimizer would perhaps create a HashMap<SpotId, Vec<usize>> mapping spots to a list of history indices. We would essentially look for neighboring pairs of small enough distances, and then try the full replay after skipping the steps in between. Would that accomplish more than ignoring certain context variables like AV2's prev_area? It's not clear to me.

[Zannick]

   Move... to Ebih > Base Camp > Tent Entry
-  Take exit Ebih > Base Camp > Tent Entry ==> Interior > Tent Interior > Entry (1)
-  Move... to Interior > Tent Interior > Desk
-  Move... to Interior > Tent Interior > Entry
-  Take exit Interior > Tent Interior > Entry ==> Ebih > Base Camp > Tent Entry (1)
   Move... to Ebih > Base Camp > West 13

Looks like a success!

[Zannick]

I think we do want the extra minimizer attempts, as our best solve is still going around a door in order to open it and go through it, and this gave us an observation we can't otherwise trim (which makes it much harder to produce a successful route).

[Zannick]

I believe this part is working, but... the route I was attempting to get it to minimize has a different quirk that is causing this:

The loop we want to cut out involves going out of our way to open a door inefficiently from the right side, after which we go through the door and back to the rest of the route. I was mistaken about how the trie would handle this kind of case: it does indeed trim the excess out because the observations do match. But in this case, the inefficient loop allowed us to later go through that door from the left side without adding an additional step to open the door (which would be more efficient from this side). When I edit the input route to explicitly avoid using the door, the trie minimizer catches it.

Improving in that scenario is tough because it involves two separate segments of the route that have to change. Ideally the main search could handle that by exploring the alternate route that doesn't open the door at the first segment... but the search space between the two segments could be vast--we'd benefit from priming the queue with the modified replay up to that point (if we had observations for route sections, that would make that easy, as well as make it simpler to finish the replay immediately after updating the second section), or figuring out if we can modify the route ourselves.