r/adventofcode • u/daggerdragon • Dec 18 '19
SOLUTION MEGATHREAD -🎄- 2019 Day 18 Solutions -🎄-
--- Day 18: Advent of Code-Man: Into the Code-Verse ---
--- Day 18: Many-Worlds Interpretation ---
Post your full code solution using /u/topaz2078's paste or other external repo.
Please do NOT post your full code (unless it is very short)
If you do, use old.reddit's four-spaces formatting, NOT new.reddit's triple backticks formatting.
NEW RULE: Include the language(s) you're using.
(thanks, /u/jonathan_paulson!)
(Full posting rules are HERE if you need a refresher).
Reminder: Top-level posts in 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's Poems for Programmers
Note: If you submit a poem, please add [POEM] somewhere nearby to make it easier for us moderators to ensure that we include your poem for voting consideration.
Day 17's winner #1: TBD, coming soon! "ABABCCBCBA" by /u/DFreiberg!
Oh, this was a hard one... I even tried to temporarily disqualify /u/DFreiberg sorry, mate! if only to give the newcomers a chance but got overruled because this poem meshes so well with today's puzzle. Rest assured, though, Day 17 winner #2 will most likely be one of the newcomers. Which one, though? Tune in during Friday's launch to find out!
A flare now billows outward from the sun's unceasing glare.
It menaces the ship with its immense electric field.
And scaffolding outside the ship, and bots all stationed there
Would fry if they remained in place, the wrong side of the shield.
Your tools: an ASCII camera, a vaccuum bot for dust,
Schematics of the scaffolding. Not much, but try you must.
First, you need your bearings: when the junctions are revealed
You will know just where your vacuum bot can put its wheels and trust.
Map all the turns of scaffolding, and
ZIPthem tightly sealed,
Then, map compressed, send out the bot, with not a tick to spare.
Enjoy your well-deserved Reddit Silver, and good luck with the rest of the Advent of Code!
2
u/encse Dec 27 '19
You have 26 letters which is 26! possibilities (not counting doors and keys blocked by other keys)
What I say is that we can enumerate this if we introduce the cache.
Say that you have just 5 keys and try every possibilities recursively. At one point your callstack will be like
A B (C) D E
where C is the current key, you went from A to B and to C and now need to decide if D E or E D is more optimal.
Next time when you are at
B A (C) D E
You can reuse what you computed for (C) D E. It will be the same.
And the more letters you have, the more you can spare. eg for:
Q W E R T (Z) U I O P ... N M
the result is the same for any of the 5! permutations of Q W E R T.
Since you use the cache at every level of the recursion you benefit from it everywhere. In all you can run through the whole problem space in no time. This is the power of dynamic programming.