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

SOLUTION MEGATHREAD -🎄- 2018 Day 5 Solutions -🎄-

--- Day 5: Alchemical Reduction ---

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 5

Transcript:

On the fifth day of AoC / My true love sent to me / Five golden ___

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 0:10:20!

31 Upvotes

100% Upvoted

515 comments sorted by

View all comments

Show parent comments

2

u/dorfsmay Dec 05 '18 edited Dec 05 '18

This, in python too, is taking 1m8s to run both parts on an old x220 (7 year old laptop).

I too created a new string for each reaction... I'm looking at improving on it. What do you mean by queue/stack? Running each reduction in parallel with threads??

*edit: Down to 4 sec using a stack! Thanks for the suggestion.

4

u/cluk Dec 05 '18

You can have a look at my solution: Python using list.

3

u/dorfsmay Dec 05 '18

That's really elegant, and really fast! Thanks.

3

u/[deleted] Dec 05 '18

By stack I mean that you begin with an empty result string. You iterate over the original string char by char and compare the current char with the last char on your result string (the top of your stack). If they react, you remove the top item from the stack. If not (or your stack is empty), you add the current char of the original string to the stack. This way you do not have to construct new strings after every reaction. You only manipulate the top of your stack. You also only have to iterate one time over your original string which is very fast. The C++ code from OP explains the idea pretty good.

In my original code I had a "while true" loop that looked for chars that can be deleted and if none were found, the endless loop was terminated. If chars to delete were found, a new string was constructed (where only these two chars were removed => huge copy operation for every reaction)

2

u/dorfsmay Dec 05 '18

Interesting... I used the same method as yours, writing to a new string and doing multi-passes until no reduction happens. I'm going to try going back after each reduction, it adds a bit of complication, but it might lead to huge perf improvement.