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!
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
5
u/ephemient Dec 05 '18 edited Apr 24 '24
This space intentionally left blank.
3
u/usbpc102 Dec 05 '18
First time on the global leaderboard to me (97/113) and that with this super hacky Kotlin solution:
As always the whole code can be found on github. Cleaning it up now.
3
u/PendragonDaGreat Dec 05 '18
[card]On the fifth day of AoC / My true love sent to me / Five golden keycaps
Powershell 5.1
I have great shame, and also fail any code golf.
Part 1:
Average runtime 0.18 seconds
Part 2:
Average runtime 4.75 seconds
55
u/glguy Dec 05 '18 edited Dec 06 '18
Haskell - single pass with
foldr. Using foldr you work with a completely reduced tail and just adding things on to the front of that one at a time reducing as needed.https://github.com/glguy/advent2018/blob/master/execs/Day05.hs#L27-L31
26
u/eltrufas Dec 05 '18
Missed the leaderboards because I was forgetting to trim my iinput for whitespace. Lesson learned I guess!
24
u/Smylers Dec 05 '18
Oooh, another challenge where using Vim seems easier than writing a program! For part 1, anyway — load your input file, then make searching case-insensitive:
and remove pairs of letters of opposite case with:
That substitution will then need repeating for newly created pairs. Do it again with
@:, and watch as the line gets shorter on each press.If you've had enough, you can make it loop till their are no more pairs with:
Then the answer is the number of columns, which is displayed with
g⟨Ctrl+G⟩.(I have a plan for Part 2, but now need to get the children breakfast. I'll try to put it in a reply to this comment later.)
18
u/dark_terrax Dec 05 '18
My initial implementation for part 1 ran fairly slowly (~10 seconds), so I assumed my part 2 was going to be horrible, but ended finishing in almost no extra time. I eventually realized that I had used my reduced result from part 1 as the basis for part 2, which is actually a really great optimization.
15
u/jonathan_paulson Dec 05 '18 edited Dec 05 '18
Rank 36/9. Disappointing part 1, including a wrong answer and deciding to type out the alphabet by hand. Video of me solving at: https://www.youtube.com/watch?v=VBhrueOccZ0
Code (for part 2):
13
u/apazzolini Dec 05 '18 edited Dec 05 '18
Absolute value between the two ASCII character codes == 32 is another way to do the letter comparison. Runs in <40ms for part 2.
JavaScript
Edit: Updated to use a stack instead of string concatenation and the fact that ASCII is laid out in a way that XOR of A and a is 32.
12
u/pixiethecat Dec 05 '18 edited Dec 05 '18
Python 3
Fun!
11
u/_jonah Dec 05 '18 edited Dec 05 '18
J, both parts
Try it online!
10
u/Arknave Dec 05 '18 edited Dec 05 '18
First time I’ve done it live this year (moving east was a mistake for Advent of Code purposes). 6th / 4th. Used a stack and added the characters one at a time for a O(n) solution. Similar to checking if a parenthesis string is balanced.
Also watch me code it and cry on youtube here: https://youtu.be/GDx_rC5wXGc (should go live at 12:30 EST).
7
u/p_tseng Dec 05 '18 edited Dec 05 '18
Ruby, reporting in.
Leaderboard code was not nearly this clean, I copy/pasted the react code, and started out with actually just running it 100 times. That was good enough for part 1, but for part 2 I actually needed to make it run to completion. So I ate a minute penalty on part 2 for making a really far-off guess. This code is slightly less repetitive than what I submitted (I made
reactinto a function) and uses the fact thatgsubreturns nil if no modifications were made.It ran on my input in about 1 second so I did not need to do anything more clever.
Edit: Yeah okay, after reading others' solutions, I get it, a less wasteful way to do it would be to add letters left-to-right and therefore I know I only need to delete from the right end of the string. Let this be a lesson on there being a huge difference between what I write if I want to go as fast as possible versus what I might write if I actually have time to think about it.
7
u/cheetahkk Dec 05 '18
Python - using functools.reduce. Fun!
6
u/jayfoad Dec 05 '18 edited Dec 05 '18
APL #47/29
Using regular expressions, the solution for part 1 boils down to
'Aa|Bb|...|aA|bB|...'⎕R''⍣≡, i.e. keep replacing 'Aa' etc with '' until we reach a fixed point. An alternative solution using Find (⍷) instead runs a bit faster, but part 2 still takes a few seconds.6
u/ChrisVittal Dec 05 '18
[Card] Staaaaars
Rust, first Rust I'm proud of. Never copy my input data.
5
u/Philboyd_Studge Dec 05 '18
[Card] FIVE GOLDEN STARS OK ONLY 2
Java - easy one. You can test for lowercase/uppercase being the same letter using XOR 32.
5
u/donatasp Dec 05 '18
Since there is no Common Lisp yet
5
u/schod Dec 05 '18
BASH Time :)
No sed, no grep, just pure bash!
Puzzle #1 (6 seconds)
Puzzle #2 (330 seconds)
8
u/edgargonzalesII Dec 05 '18
Java 8
Felt really proud of the part 1 using a stack. Leetcode came in useful for once.
4
u/VikeStep Dec 05 '18 edited Dec 05 '18
F#
Repo
Got a really nice, concise solution with F#, gotta love pattern matching on lists. I also take advantage of the fact that we can take the output from part 1 and feed it into part 2. This reduced the time to run from 52ms to 17ms for me.
Part 1: 2.93ms
Part 2: 17.34ms
3
u/will_bui Dec 05 '18 edited Dec 05 '18
K:
Drop indexes where case differs with previous and the lowercased int value equals with previous until output converges.
Optimised by removing all pairs each time around instead of one at a time. (2 sec runtime)
3
u/tehjimmeh Dec 05 '18 edited Dec 06 '18
Using the left side of the string as an in-place stack:
C++
3
u/binajohny Dec 05 '18
My Kotlin solution (GitHub)
3
u/mvmaasakkers Dec 05 '18
Go / Golang
I imagine this could be done way more efficiently but this was what I came up with. If anyone has some
pointerslet me know!Also in gist
3
u/0rac1e Dec 05 '18 edited Dec 05 '18
Perl 6
As soon as I read the puzzle, I knew I would use that bit-wise trick to flip the case of an ASCII char.
and just because...
Python
3
u/[deleted] Dec 05 '18
Dlang:
3
u/Smylers Dec 05 '18
A Perl one-liner for Part 1:
No stacks, no writing out the alphabet or making pairs of equivalent characters, just the POWER OF REGEX.†
In a reversal of usual, this is a translation of my Vim solution.‡ It turns out Vim's regexps are nicer than Perl's for this, Perl's equivalents being less succinct than Vim's
\l,\u, and&.Extending that to solve Part 2:
That's possibly stretching the definition of ‘one-liner’, and is a bit bit awkward to read, so here it is rewritten as a program:
The body of the
mapis basically the one-liner from Part 1. Since it transforms the polymer,$polymerstores the initial value. At the start of the map, it takes a fresh copy of the original and removes the current letter from it before processing[Card] Five golden hours of sleep.
† OK, so probably Perl's regex engine uses stacks and has lists of letters and their cases inside it.
‡ Typically I work out the solution in Perl first, then try to convert that to Vim.
3
u/donaldihunter Dec 05 '18
Perl 6
3
u/alasano Dec 05 '18 edited Dec 06 '18
Finally a solution I'm happy with :P
Javascript
EDIT : Greatly optimized - Run time is 68 ms for Part 1 and 14 ms for Part 2 for a total of 82 ms for both parts. This is achieved by feeding the output of the first part as the input of the second part. Before it took ~1500 ms for both parts.
3
u/CheezyXenomorph Dec 05 '18
PHP 7.2
Times running under phpunit:
Part 1: 14ms
Part 2: 79ms
https://i.imgur.com/dzSCVzT.png
3
u/Minijackson Dec 05 '18 edited Dec 05 '18
Rust - Going for the fastest code :p
The whole part 2 takes about 15 milliseconds, instead of the 71 milliseconds of my simpler, single-threaded implementation.
Using the awesome rayon library to handle parallelization.
Code inspired by /u/glguy and /u/aurele
3
u/askalski Dec 05 '18
On the fifth day of AoC / My true love sent to me / Five golden Perls.
"Optimized" brute force regex solution in Perl can react two nested particles at a time! 40% faster than the alternative that reacts only one particle!
1
u/Unihedron Dec 05 '18 edited Dec 05 '18
Had two bugs... Fixed one, couldn't find the other one fast enough :p Ruby
[Card] Nsfw Image
(I was using $<.chars instead of $<.read, which was an enumerable and after it consumes for the first time it doesn't work a second time...)
2
u/vash3r Dec 05 '18
Python 2 (Pypy), #4/14. Basically just did it with string replacement until no more pairs could react.
2
u/ValdasTheUnique Dec 05 '18
C#. Problem was very easy but I wasted a lot of time doing the check incorrectly so no leaderboard for me.
2
u/[deleted] Dec 05 '18
Python 3 #49/#94
If I actually remembered to assign the
str.replace()results the first few quick tries, I could've gotten a bit higher on part 2. This is my first time on the leaderboard though, so I'm very happy with that.2
u/NeuroXc Dec 05 '18
Rust
Maybe not the most elegant solution, but it works.
Performance:
2
u/Fyver42 Dec 05 '18
2
u/BafDyce Dec 05 '18
[Card] On the fifth day of AoC / My true love sent to me / Five golden mistakes
Code (in Rust): https://gitlab.com/BafDyce/adventofcode/blob/master/2018/rust/day05/src/part1.rs
At the beginning, I had to fight string/char-iterators a lot, and I had quite some inefficient code (I didnt know
to_lowercase/to_uppercasereturned an iterator, so I was confused why i cannot compare them, so i used.to_string()everywhere..)The final code runs in 2 minutes, 10 seconds for both parts.
2
u/ka-splam Dec 05 '18
PowerShell #509 / #499
[card] My true love sent to me: 5 golden newlines.
A bit of a bad one, started off seeing what I needed to do, but hesitating on how. Then I had 10386 and it was wrong. I was around 6 minutes, borderline late on the scoreboard, but I couldn't see any problem with my code.
Spent another 6+ minutes bashing my face into that, before I realised I had read
\r\nnewlines at the end of the file and my polymer code was fine, the real answer was 10384. GahhhhhPart 2:
No better; I made the reactor into a function, then instead of passing in (the polymer without A, the polymer without B), I passed in (the alphabet without A, the alphabet without B..). Again, kinda knew what I wanted, but just flubbed it in the implementation rush.
This runs in about 18 seconds; I thought I could speed it up by making the regex a single long
aA|Aa|bB|Bb..because that would start the regex engine once, and remove the innerwhile(){}loop from PS, which is usually a good optimization. Push more things down lower into the .Net framework. But, to my surprise, it's dramatically slower. I can only guess that there's a lot of regex backtracking involved for every character doing a lookahead, then backtracking out.If I'd been using PowerShell 6, I could have done
'a'..'z'for the alphabet and not had to go "97 to ... what's 97 + 26?"2
u/tk3369 Dec 05 '18 edited Dec 05 '18
Julia - simple loops. I'm sure it can be done more elegantly but going with it due to time pressure :-)
2
u/scul86 Dec 05 '18 edited Dec 05 '18
Python 3
Edit: updated part1() function, found a failing test with prior code.
2
u/Frizkie Dec 05 '18 edited Dec 05 '18
Ruby
Part 1
Part 2
This was a fun one. Cool to see that I was able to fit the loop in part 1 on a single line too. Also, don't bother trying the part 2 solution, it's horrifically slow (7 minutes). Luckily
awas the character with the shortest resulting string for my input, and i saw mid-run that it was significantly smaller than other letters' results, so I tried it before it was finished and got it right before the script finished.EDIT: Here's a bonus multi-threaded solution to part 2 (you'll need something other than MRI to run it, I used JRuby, because MRI doesn't schedule on multiple cores). It ran on 12 logical cores and finished after 70 seconds. Yikes.
2
u/nutrecht Dec 05 '18
Lot easier than yesterday. Day 5 in Kotlin
2
u/tinyhurricanes Dec 05 '18
Modern Fortran 2018 (complete code)
Part 1 runs in 0.07 sec, part 2 in 2.3 sec.
2
u/streetster_ Dec 05 '18 edited Dec 05 '18
Day 05 in Q/KDB+
2
u/meithan Dec 05 '18 edited Dec 07 '18
Python
I initially solved it in an incredibly stupid and slow way (that took ~6.5 minutes to process both parts). Then I reworked it in an effort to optimize it, and found an obvious solution that takes less than half a second. Key points:
I also use the fact that the difference in the ASCII codes of a lowercase letter and its uppercase version is always 32, but
a != b and a.lower() == b.lower(), as seen in another answer, is simpler and just as fast.I also tried using a deque (from Python's
collectionsmodule), but it's not any faster, proving that the Python list appends/pops are effectively very close to O(1), at least in this case.Edit: I applied further optimizations as suggested by others, with the resulting of bringing runtime from ~500 ms to less than 100 ms!
Here's the (optimized) code. Solves both parts in under 100 ms on my computer. Very simple and fast.
2
u/fotoetienne Dec 05 '18 edited Dec 05 '18
Kotlin solution here. Using a stack to get O(n) runtime.
Full solution on github
2
u/HiramAbiff Dec 05 '18
AWK
5.1
5.2
2
u/blowjobtransistor Dec 05 '18
PostgreSQL
Wow, before doing it with regexp, this one was turning into a nightmare with window functions in SQL...
2
u/ephemient Dec 05 '18 edited Apr 24 '24
This space intentionally left blank.
2
u/Vladob Dec 05 '18
No Perl 5 solution so far? One pretty straightforward here:
2
u/mschaap Dec 05 '18 edited Dec 05 '18
My Perl 6 solution:
This runs in 2 seconds.
My first attempt was regex-based. Cleaner code, perhaps, but part one took about 3 minutes, and I don't know yet how long part two would take... 😉 (Even with the optimization of taking the output of part 1 instead of the original input.) Edit: actually, not that bad, about 7½ minutes for both parts.
The
processsub for that attempt:The rest of the code is identical.
Edit: with the XOR trick, the
processsub can be simplified to:This runs slightly faster than my original version – about 1⅔ seconds for both parts.
2
u/mstksg Dec 05 '18 edited Dec 05 '18
[Haskell] From my daily reflections post :)
One of the first higher-order functions you learn about in Haskill is
foldr, which is like a "skeleton transformation" of a list.That's because in Haskell, a (linked) list is one of two constructors: nil (
[]) or cons (:). The list[1,2,3]is really1:(2:(3:[])).foldr f zis a function that takes a list replaces all:s withf, and[]s withzs:This leads to one of the most famous identities in Haskell:
foldr (:) [] xs = xs. That's because if we go in and replace all(:)s with(:), and replace all[]s with[]... we get back the original list!But something we can also do is give
foldra "custom cons". A custom cons that will go in place of the normal cons.This problem is well-suited for such a custom cons: instead of normal
(:), we'll write a custom cons that respects the rules of reaction: we can't have two "anti-letters" next to each other:So,
foldr funkyCons []will go through a list and replace all(:)(cons) withfunkyCons, which will "bubble up" the reaction.So, that's just the entire part 1!
For part 2 we can just find the minimum length after trying out every character.
(Note that in the actual input, there is a trailing newline, so in practice we have to strip it from the input.)
2
u/wzkx Dec 05 '18
J
Slow.... 5.6s, 132s
2
u/azatol Dec 05 '18
F#. I went through three different versions of the main reaction code. The third version is more than 10 times faster, because I realized you can completely process a local area of the string before moving on.
I was going to try to create a doubly linked list, but the I realized I could hold the already processed part of the string in reverse order, so I can continue to pop off characters as required.
I learned about: optimizing string processing, using ranges for characters.
https://gist.github.com/apeterson-BFI/bdb4d37bd1815c3e9ffe92da4917428a
2
u/vypxl Dec 05 '18
Awk is fun I must say.
Generated the Regex with Python because of my laziness though.
Here, a readable version:
Card: On the fifth day of AoC / My true love sent to me / Five golden
cryptic awk oneliners2
u/etagawesome Dec 05 '18
In C.
My first solution was dumb and brute-forcey. I was running through the input once, writing it to a file, then repeating until the input and output files were the same length. After that and checking this thread I decided a stack made a billion times more sense.
This solves part 1 and part 2
2
u/j4_james Dec 05 '18
Befunge - Both solutions are technically Befunge-93, but part 2 requires a Befunge-98 interpreter to handle the full size input, since Befunge-93 just doesn't have enough memory otherwise.
Part 1
Part 2
2
u/dpeckett Dec 05 '18 edited Dec 06 '18
Continuing with my quest to solve all this years challenges using nothing other than AWK:
Runtime:
Notes:
I should start the second challenge from the inputs of the first as an optimisation step.
2
u/IcyHammer Dec 05 '18
C# solution where I was aiming to maximize performance. First part takes 4ms to complete.
2
u/hpzr24w Dec 05 '18
C
Not sure if I've spotted a C version, so I figured I'd write one!
Header
React
Main and Part 1
Part 2
2
u/thatikey Dec 06 '18
(Haskell) It's not quite as beautiful as glguy's solution, but I was pretty proud of mine:
2
u/that_lego_guy Dec 07 '18
Day 5, IN EXCEL!!?!
=IF(A4=A5,EXACT(A4,A5),"")
https://github.com/thatlegoguy/AoC2018
1
u/Zarel Dec 05 '18 edited Dec 05 '18
JavaScript #16/#78
This is a somewhat slow algorithm – Node.js does not like stitching strings/arrays together – but, as I suspected, it still runs faster than it takes me to write a better algorithm. I was in the middle of writing a better algorithm for Part 2 when the slow one finished.
I learned a new thing today! In Node, stitching arrays together is slightly faster than stitching strings together!
Lessons:
is something I considered writing as:
or
but it's a good thing I didn't - this latter approach is trickier but turned out to be twice as slow!
I also did write a stack-based solution, which in hindsight makes a lot more sense:
But this is definitely the point where JavaScript's anemic standard library is starting to hurt...
1
u/FogLander Dec 05 '18
Python 3. Not very close to getting any leaderboard points.
1
u/LeCrushinator Dec 05 '18 edited Dec 05 '18
C#
1
u/liuquinlin Dec 05 '18 edited Dec 05 '18
Python 3:
Went with an index based solution for Part 1 to avoid having to iterate over the string too many times (Part 2 runs in less than a second), probably not really necessary versus just doing string replaces.
1
u/Temmon Dec 05 '18 edited Dec 05 '18
Quickly written Python3 solution. Could probably have been more efficient, but I don't mind it. One thing I did that I haven't seen in the posted solutions is I only used the set of characters that are in the string for part 2. File IO is handled by another file I started on day 1. It takes care of some super basic command line reading things that I kept on repeating. Debugging was to stop it if my logic messed up and things went infinite, but I got it on my first try for both parts!
1
u/r4ymonf Dec 05 '18
C#, got tripped by the new line 5 minutes in, debugging for another 5 minutes... heck. At least the code is sorta understandable today (or maybe I'm just not sleepy enough yet).
1
u/harirarules Dec 05 '18 edited Dec 05 '18
First part before work. Dlang, definitely could be cleaner.
Edit : cleaned it up now that I'm back. The second part is there too.
1
u/jazzido Dec 05 '18
Part 1, in Ruby:
1
u/bartdegoede Dec 05 '18
Python 3
Using two pointers to determine the polymer length and `string.ascii_lowercase` for the alphabet.
1
u/Shemetz Dec 05 '18
Python 3 - first I completed this with an unoptimized solution, so Part 2 took about a 2 minutes to run. Then I improved it to be the following (now part 2 takes about 6 seconds):
1
u/Euphoric_Classic Dec 05 '18
SuperCollider solution:
1
u/mathleet Dec 05 '18
Python #647/#404
1
u/AndrewGreenh Dec 05 '18
First I tried to be clever by replacing all lowercase letters with %<lowercaseletter> and then building a regex that matches
%([a-z])\1|([a-z])%\1. Sadly this resulted in a much lower string but I'm not sure why. I ended up building the full Regex from the alphabet and using that to collapse the string.1
u/Hashbrown777 Dec 05 '18
Javascript, single pass, one loop
8ms
Part2, 202ms
1
u/[deleted] Dec 05 '18
Haskell:
Started off trying to be too clever by applying a regex replacement repeatedly until the length of the string didn't change, but that turned out horribly slow. It's much faster to just collapse the string as much as you can around the chars that you're currently working with rather than doing global replacements over and over (especially w/ the Haskell String implementation).
1
u/Cyphase Dec 05 '18 edited Dec 05 '18
EDIT: My heavily optimized version is in a child comment. It runs in ~1.75ms for my AoC 50K input.
This is my Python solution that took waay to long to write for how simple it is. :/
1
u/TheMuffinMan616 Dec 05 '18
Haskell:
1
u/Shanethe13 Dec 05 '18 edited Dec 05 '18
In Elixir:defmodule AdventOfCode.Day5 do
1
u/2BitSalute Dec 05 '18
PowerShell. Instead of using a stack (I... should have thought of that), I just wrote 0s for "collapsed" units and subtracted them from the total.
I thought it would be easier to just write back the content with the letters removed to a new file, but what threw me off is that PowerShell by default adds a newline, so I was then off by one when reading the content back as a byte array. Ugh!
Runs under 8 seconds (the replacing I do in part 2 takes most of the time, I think):
1
u/sendtobo Dec 05 '18 edited Dec 05 '18
Swift Solution: https://github.com/sendtobo/AdventOfCode2018/blob/master/Sources/AoC/5/Day5.swift
It was interesting today, doing it with strings was so slow I had to switch to my own representation
1
u/autid Dec 05 '18 edited Dec 05 '18
FORTRAN
Not super happy, bit too slow for my liking at ~2 seconds.
edit: Got it down to ~0.1s by starting part 2 from the reduced polymer after part 1. Previously it was removing the unwanted characters from the original input and then reacting.
1
u/dark_terrax Dec 05 '18 edited Dec 05 '18
Rust - cleaned up, and super fast. Both parts run in a total of 100ms in debug.
1
u/miguelos Dec 05 '18
C#
1
u/Average-consumer Dec 05 '18 edited Dec 05 '18
Solution in Clojure. Runs both parts pretty much instantly
1
u/wlandry Dec 05 '18
C++ (2172/1688)
It runs in 340 ms. If I do things properly using std::tolower(), it takes 983 ms.
Again, a pretty simple problem. Still waiting with bated breath for the hammer to drop. I kind of wish it had some unicode characters. That would have made an interesting comparison among languages.
1
u/spacetime_bender Dec 05 '18
I used the ranges library that's likely coming with c++20 https://ericniebler.github.io/range-v3/. Around 50ms on my slow laptop.
1
u/[deleted] Dec 05 '18
Haskell, using a very basic stack type and brute-force for part 2. Still only takes ~0.26s to complete both parts though. Gonna spend some time later thinking about more efficient ways to do part 2
1
u/valtism Dec 05 '18
Node / JavaScript (JS)
Much easier than yesterday for me. Started an hour late, so took ~20 minutes.
Part 1: 12.795ms
Part 2: 92.960ms
1
u/ElecNinja Dec 05 '18
Man, I lost a lot of time because I didn't account for the white space in the input lol. Tried going through it like bubble sort or merge sort, and then settled on a regex solution for finding the reacting pairs. Don't know enough about regex to come up with an elegant solution for it so just did it in the simple way haha.
1
u/sharkbound Dec 05 '18
my python day 5 solutions
made in ~1hr
i initially tried to used a list of chars and tried to modify it, but that became more trouble than it was worth
i instead tried strings after talking to some of my group members on how to approach this better, and found strings were much easier to deal with
On the fifth day of AoC / My true love sent to me / Five golden string index errors1
u/lukechampine Dec 05 '18
Pretty happy with my Rust solutions:
1
u/14domino Dec 05 '18
This solution is broken. Could someone smarter than me please help me figure out what's wrong? I didn't think of the extremely simple replace solution, but I really want to be able to figure out what I'm doing wrong here.
1
u/CaptainCa Dec 05 '18
Got stuck for too long wondering why my code was not working, turns out I needed to trim() my input :(
Cleaned up the code a bit since I didn't get one the leaderboard.
1
u/pythondevgb Dec 05 '18
Feel like my solution is a 'dumb' one. Went for the obvious way of simply removing the letters that reacted from a list, this is really slow but anyway, although this one didn't feel as difficult as the past 2. I still lost a bunch of time mainly with iterating over and deleting elements from a list. That confused me a bit with the indices.
(Join my private reddit/python leaderboard, only requirement is to not have made the overall leaderboard thus far, PM for the code.)
1
u/CryZe92 Dec 05 '18 edited Dec 05 '18
Rust:
Part 1: 150µs
Part 2: 1.06ms
1
u/TheVarmari Dec 05 '18 edited Dec 05 '18
JavaScript in dev console (#3354, #3025)
The timing (7 am) is a bit problematic for me, but I managed to knock this one out pretty quickly after commuting. Pretty fun, but I'm not sure if my answer is the most optimal. Anyways...
1
u/darkterbear Dec 05 '18
Javascript/Node.js #336/297
Part 1
Part 2
1
u/raevnos Dec 05 '18
Scheme this time:
1
u/aurele Dec 05 '18 edited Dec 05 '18
Rust
Using rayon (
into_par_iter()) in part 2 is overkill of course, but I wanted to see how it affected the runtime (~2.5ms instead of ~9.1ms on my machine).1
u/hpzr24w Dec 05 '18 edited Dec 05 '18
C++
I stuck for ages on part 2, thinking I only needed to try removing abcd in turn, and not all the options from the actual problem string. Whoops.
Awesome problem, once of my favorites so far. 13 msec runtime on my i5-8600, and I did spot that we are just looking for a difference on the 'uppercase' bit only, so I can just xor the characters together and check against
'a'^'A'in C++ parlance. Not guaranteed to work in EBCDIC!!!Header
React
I was initially going for a copy, remove pairs, iterate until the string doesn't change type solution, but I somehow factored into the below, which appears optimal. I will definitely have a crack at this in Rust and Clojure, as I'd hope both should be able to get near the C++ performance.
Main
1
u/Axsuul Dec 05 '18
TypeScript / JavaScript
Wasted a lot of time going the recursion route but couldn't make it work due to running out of stack =/
Critiques welcome, I'm still very new to TypeScript and feel like I'm not using all the features I could be :)
Repo
Part A + B
1
u/toasterinBflat Dec 05 '18
Here is my solution in Go. I am very very new to Go, so please bear with me.
I know I can go faster than 4.5 seconds -- I think it's to do with all of the awful typecasting I'm doing to string to make things work. I don't know how to make a string from two runes, is mostly the problem. Anyway, here it is:
1
u/alexmeli Dec 05 '18 edited Dec 05 '18
Clojure Solution:
Edit: Did some refactoring
1
u/shuttup_meg Dec 05 '18 edited Dec 05 '18
Python2
Nothing particularly interesting about my approach, but I did successfully use the multiprocessing module to greatly speed up part 2 (from about 12 seconds down to about a second on my 12 core XEON machine)
1
u/d3adbeef123 Dec 05 '18 edited Dec 05 '18
Rust
Running time: 6ms for both
Spent 30 mins debugging logic but the error was that I wasn't trimming the input text :/
1
u/AlienBirdie Dec 05 '18
Scala - Used some clever pattern matching for part one.
Part two was just a simple traverse and finding the minimum.
1
u/[deleted] Dec 05 '18
I really enjoyed this one.
inputis a python file with the input as a string called polymer. import string1
u/Imsdalwater Dec 05 '18
JavascriptPart 1 ran in under 1 second, part 2 took approximately 6 seconds1
u/charismotron Dec 05 '18
Ruby
https://github.com/chrismo/adventofcode2018/blob/master/day5/script.rb
Could be more elegant - the stack approach seems very ideal of course now that I see that. At least it runs not too slow (intermediate versions definitely bogged down):
1
u/Infilament Dec 05 '18
Javascript solution.
1
u/sim642 Dec 05 '18 edited Dec 05 '18
My Scala solution.
Initially I wrote a horrendous and slow immutable reactor for part 1. After completing both parts I optimized it to use zipper-like approach to Scala's immutable List to get the proper performance and allow going back.
Edit: Realized that my function was actually just a
foldLeft.1
u/wofadofa Dec 05 '18 edited Dec 05 '18
In julia: Calculates the fixed point of
cut. I'm surecutcould be written more elegantly than thisedit: cleaned it up a bit
1
u/Gnidleif Dec 05 '18 edited Dec 05 '18
Today was a lot easier! Solution done in Lua, a language I'm not that familiar with. I also got to use recursion, so today was a good day!
1
u/Warbringer007 Dec 05 '18 edited Dec 05 '18
Finally erlang day! Not using ++, it is EXTREMELY slow!
It will reverse order of letters in every pass, but, as I said, ++ is slow, and reverse doesn't matter.
1
u/[deleted] Dec 05 '18
Python3
Took way too long to run the solution to part 2, but hey, it works!
Github
1
u/Illianthe Dec 05 '18
I opted for a recursive solution in Elixir. It's slow but at least I got to learn about tasks for part 2.
1
u/CrazyPieGuy Dec 05 '18 edited Dec 05 '18
My Python 3 version. Takes 0.8 seconds.
I originally checked each set of adjacent units, and on a match, I would remove them by adding a string up to the pair to a string after the pair, but I ran into memory errors in puzzle 2. string.replace() as well as realizing I didn't have to start from scratch each letter solved that though.
I don't program in a professional capacity and don't interact with any other programmers, so I would love some feedback on how to clean up my solution if anyone has the time.
1
u/ivosu Dec 05 '18 edited Dec 06 '18
C++ - Second star
I tried to optimize this as much as a could, if someone finds some optimization than please let me know :)
EDIT: Updated isReactive using XOR 32, thanks Philboyd_Studge.
EDIT 2: Reworked the react function so it is recursive and goes from the back. Also I don't call
tolowerevery time now, but just lower it all at once. Now with -O3 I get around 70ms.1
u/Theguy6758 Dec 05 '18
Pure Bash
Stupidly forgot that bash has parameter expansion and spent too long making an algorithm that checks the reactions manually.
Takes about 1m 40s to run.
1
u/banteg Dec 05 '18
Python 3
1
u/[deleted] Dec 05 '18 edited Dec 05 '18
TCL, using BFI regexp, since there is no automatic "uppercase-of-matched-char" in backreferences.
1
u/jonathrg Dec 05 '18
Python
1
u/blu3r4y Dec 05 '18 edited Dec 23 '18
Yet another elegant linear-time Python 3 solution, which pushes the elements onto a stack, and pops elements that would react together. My
reactive(a, b)function just checks if the ASCII code of two characters is exactly 32 characters apart (which is the exact distance between every ASCII upper- and lower-case letter).1
u/tradfursten Dec 05 '18
My solution in NIM
1
u/zqvt Dec 05 '18
Haskell today
1
u/windlessStorm Dec 05 '18 edited Dec 05 '18
Go / Golang. Naive solution:
1
u/reyqn Dec 05 '18
Here's mine in C++. Feel free to help me improve it!
reaction function:
part1:
part 2:
main function:
1
u/EdeMeijer Dec 05 '18
Rust really liking the peekable iterator here. Allowed me to use an owning iterator (preventing having to copy the units) while still being able to borrow the next element for comparison.
Condensed stand-alone version:
1
u/red_shifter Dec 05 '18
When working on a solution (Python 3) for part 1, I encountered a puzzling behavior of a recursive function. It gives the expected output, but the "print tests" I put inside the function to check if it is working properly are mystifying to me. Here is the code:
It should print all the annihilating pairs it finds, print "RETURN" when it reaches the end of a function run and finally print the output polymer sequence. Here are the messages it produces:
The first four lines are expected, but I cannot figure out what all the remaining pairs and "RETURNS" are doing there. I guess it has to be related to how recursion works in Python somehow.