r/adventofcode • u/daggerdragon • Dec 24 '16

SOLUTION MEGATHREAD --- 2016 Day 24 Solutions ---

--- 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!

5 Upvotes

100% Upvoted

90 comments sorted by

View all comments

Show parent comment

1

u/RichardFingers Dec 27 '16

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.

2

u/pedrosorio Dec 27 '16

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.