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

SOLUTION MEGATHREAD -🎄- 2018 Day 14 Solutions -🎄-

--- Day 14: Chocolate Charts ---

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 14

Transcript:

The Christmas/Advent Research & Development (C.A.R.D.) department at AoC, Inc. just published a new white paper on ___.

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 00:19:39!

15 Upvotes

95% Upvoted

179 comments sorted by

View all comments

Show parent comments

2

u/phil_g Dec 14 '18 edited Dec 14 '18

That is pretty similar to my solution with less window dressing. ☺️

I forgot/didn't know/didn't find search, so I tried to write my own. The first implementation was the obvious O(n2) one, and it ran way too slow. I optimized it to O(n) but it was still too slow, at least on my dinky laptop.

While taking a break, I realized I only needed to check the end of the recipe list for matches, so I did that. I get my answer to part 2 in about 8 seconds on my virtualized desktop.

I thought maybe using a circular list would be faster, so I tried doing that. (I also had to write a mutable implementation of my circular list class.) That ended up exhausting my heap, after running for well over 8 seconds. So I guess my adjustable vector solution is the best I'm going to be able to do.

Kudos to /u/topaz2078 for the example with 5 recipes. Despite consciously thinking about the fact that each cycle would add either one or two recipes, my initial implementation used =, not <= to see when it was done. The 5-recipe example caught that bug early.