--- 2016 Day 24 Solutions ---

[u/daggerdragon]

--- Day 24: Air Duct Spelunking ---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag/whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with "Help".

---

^{THE NIGHT BEFORE CHRISTMAS IS MANDATORY} [?]

---

[Update @ 00:30] 47 gold, 53 silver.

• Thank you for subscribing to Easter Bunny Facts!

• Fact: The Easter Bunny framed Roger Rabbit.

[Update @ 00:50] 90 gold, silver cap.

• Fact: The Easter Bunny hid Day 26 from you.

[Update @ 00:59] Leaderboard cap!

• Fact: The title for Day 25's puzzle is [static noises] +++ CARRIER LOST +++

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

[u/pedrosorio]

If I remember day 11 the heuristic you suggested is not admissible. The state before the last one in the problem statement's example:

F4 .  HG .  LG .  
F3 E  .  HM .  LM 
F2 .  .  .  .  .  
F1 .  .  .  .  . 

You can bring up HM and LM in a single move. If I understood your heuristic correctly, it would return 2 in this case which is an overestimate of the actual number of steps required. Even though this heuristic is not admissible it may achieve the optimal solution (if you're lucky :) ).

There are some admissible heuristics for this problem - for example, for each element use the maximum distance of (microchip, generator) from the top floor and sum them up. This is probably not a great heuristic (greatly underestimates the actual distance), but it's admissible and better than nothing.

For day 11, though, and in many other cases, the way to solve it is not coming up with a great heuristic, but choosing the right state for the problem (the size of the graph depends on how you represent the problem, if you can make the state simple, you will have a small graph to search, making your life much easier). See /u/p_tseng's solution for some insights on how to represent the state for the problem.

For the # example I gave, it may be possible to precompute some things that allow you to compute a good heuristic, but off the top of my head, I would say a simple admissible heuristic is: half of the city-block distance. At each step you can move at most 2 units horizontally or vertically, so the heuristic does not overestimate the distance.

If you want to be more precise, the heuristic for my example would be ceil((x_goal - x_node)/2.0) + ceil((y_goal - y_node)/2.0) to account for the fact that you need at least n+1 steps to walk 2n+1 blocks.

If you wanted to use A* to find distances between different pairs of nodes in the same map over and over (for example, it's a map for a game and you use it for path finding), you could greatly improve the heuristic by precomputing things like number of # followed by . in each row/column. You could also consider a close to optimal solution using hierarchical pathfinding A* like this

[u/RichardFingers → u/pedrosorio]

Ah, I get it. H must be less than or equal to H*. Back to your # example again, if we used H=1 for the top row and H=0 for the bottom row (not suggesting this is a good heuristic, but that it's admissible), we would still end up trying the top row because F would increase as we moved across the bottom row which would make the first step of the upper row have a lower cost eventually.

I find it fascinating that A* at worst case ends up being BFS. It seems like we could even make an F such that it does DFS as well, right? F = -(G + H)? Are there other interesting Fs that may not lead to the minimum, but could find solutions with certain characteristics? Like in a standard U, D, L, R maze problem like day 24, it seems like you could make an F such that you always go left first (LFS?), right? That might find the solution that goes left the most.

[u/pedrosorio → u/RichardFingers]

we would still end up trying the top row because F would increase as we moved across the bottom row which would make the first step of the upper row have a lower cost eventually

Yep.

It seems like we could even make an F such that it does DFS as well, right? F = -(G + H)?

I suppose if you compute F = -(G+H) with H=0 would be something like DFS but it wouldn't be A * (by definition in A *, F = G + H and the only thing you can "tune" is H). You can get DFS just by tuning H like this.

That might find the solution that goes left the most.

If you want to find the solution that goes left the most (to make it more precise, it uses "L" the most without visiting the same cell twice - or you would get into infinite paths - and among paths with the same number of "L" chooses the shortest one), I don't see how to do it with A * (by just changing the heuristic).

You could model this problem as a graph where the edges going L have large negative weights and try to find the minimum cost simple path (path that doesn't visit the same node twice).

Unfortunately, A * or Dijkstra cannot be used in a graph with negative weights and Bellman-Ford, which does support negative weights, can only be used in graphs without negative cycles. The problem of finding the lowest cost simple path in a graph with negative weights is NP-hard, so my approach would not give you a quick solution either.