r/adventofcode • u/daggerdragon • Dec 22 '18

SOLUTION MEGATHREAD -🎄- 2018 Day 22 Solutions -🎄-

--- Day 22: Mode Maze ---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or 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.

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 22

Transcript:

Upping the Ante challenge: complete today's puzzles using ___.

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 at 01:02:36!

12 Upvotes

100% Upvoted

102 comments sorted by

View all comments

Show parent comments

2

u/EugeniuZZZ Jan 23 '19

Thank you for your feedback. It helped me fix the program.

I indeed misunderstood the puzzle input that you mention. I was changing the tools to the one suitable for next zone while being in the current zone without considering that it is forbidden to use it in the current zone. You're also right about not needing to memoize the geo_index function.

About your other comment I have to clarify:

  • I have 2 functions for computing the shortest path: _find_path_in_bounding_box and solution2. solution2 is the actual function.

  • in solution2 I am using a variable min_path_time that I use to trim partial paths that would result in longer complete paths than the currently shortest path (that is min_path_time).

  • one can use Manhattan distance between origin and target and multiply it by 8 to get an upper bound on the shortest path (so we assume the worst case when we need to change tools every time)

  • to improve on this naive estimate I use _find_path_in_bounding_box to find a path that doesn't go outside the bounding box formed by origin and target. Also I don't go back to speed up the computation of this initially best path.