Alright! We got through Day 4. It's done. We completed the tasks given to us. For most of us, it is dead to us and we will speak of it no more....
For further actions, you may consider blocking this person and/or reporting abuse
Dumb order of operations mistake got me to this point 🙃was missing the parens around the last half of the conditional since like 12:20. This mirrors the classic stack match parentheses problem.
My solution is kinda pretty though:
My first inclination was to do this recursively. Had to fudge it a bit because doing a truly recursive solution exceeds the max recursive depth :(
Here's my Python for part 1. It's very slow. Gonna look into refactoring to a regex or list comprehension solution for part 2. Kind of ready to move out of string manipulation land either way!
Wow, that stack thing is clever! It didn't even occur to me that you could evaluate as you go in a single pass through the polymer. Implementing the stack in c# (from the impl i posted below) went from
~2:50 => 268ms
:OCool! Yeah -- it's kind of a play on this classic problem, which is how I recognized it!
Very slick solution!
Maybe most already know... But, parsing the polymer string as a
string
and using str.replace twice as you do is still much faster than using polymer as a list and using a list-comprehension to remove units (35% slower).E.g.
Wow, I did not see the stack-based solution in there at all. I tried the recursive approach and then one similar to @thejessleigh and stopped there! At least I enjoyed this one more than Day 4!
I went with RegExp solution. I created a regexp for all the reactions and delete everyting, then iterate until no more matches
Time: 0.265s
For part b y reuse all the code but add this
Time: 3.693s
I find the part b is a little slow using this approach
this one was easy (to me!) in comparison to yesterdays, might even be the easiest thus far. All that being said, DAMNNNNNN is part 2 slow, at least with my current impl.
00:07 run time for part 1
02:50 run time for part 2 :OOOOO
Didn't think about the stack approach til seeing other's solutions, wow so much faster! Didn't really occur to me you could accomplish the whole reduction in a single pass through the polymer.
Part 1 went from 00:07 -> 12ms
Part 2 went from 02:50 -> 269ms
I wrote this solution pretty quickly... and then kept having the wrong value.
I went down a rabbit hole involving hexdump and such because I was pretty confident in what the code was supposed to do and didn't see a valid result come up. It drove me crazy, but finally after way more time digging than I'd like to admit, here's my solution:
I'll try and find some time to write up what problem I encountered
I reached for regular expressions in Perl. I wasn't sure about the performance, but 0.4s for the part 2 seemed enough.
The regex is constructed dynamically and simply lists all the possible pairs to remove.
For the part 2, I discovered you can start from the already reduced polymer, which improved the performance more than 10 times.
...welp, that was a solid "d'oh" moment, opening this thread. Hindsight is 20/20.
Here's the brute force way in F#. I'll have to come back to it after work to implement the smart way.
Yep, stack-based trick worked just fine:
Replacing
reactString
withreactQuickly
was enough to bring the total runtime from several (many) minutes to around 3 seconds.Using the tip from @choroba and reducing everything first would probably speed it up even more.
I originally had an iterative, while-loopy, pointer-based solution, and that ran OK, but like a lot of people, I realized that it's basically an extended version of the "Matching Parentheses" problem, and that a stack would let me iterate through the list more with less backward steps. Now it runs pretty quick!
Rust's lack of easy handling of upper- and lowercase characters kind of bummed me out.
Part 1
Part 2
For part 2, I didn't iterate over all 26 letters of the alphabet no matter what, I used a set to figure out what characters were in the input and only loop over those. In this case, it doesn't help, because the input has all 26 anyhow. Oh well. I learned a lot about
.collect()
today.PHP
Second part looks kind of long because I figured it would be faster to just declare the letters rather than generate the letters programmatically. I'm pretty sure there's a way to improve performance here, since this has a long-ish runtime, but I wasn't up to optimizing performance at midnight, haha. I might fiddle with this some more to see if I can do better.
Part 1:
Part 2:
I am using Advent of Code to learn Golang, and here is the solution I came up with. Suggestions for improvements are always welcome!
I was first using a list which would go from left to right and remove pairs as they were found reacting, shifting one step to the left and continue finding pairs that react. However, this could be simplified by using Ali Spittel's stack solution in Python.
With this inspiration, here is my Golang solution. I have added timing functions just to print out the running time as I have compared them to Python it is finally a speed up using Golang for the solution in this case!
Nice!
Kotlin Solution
A nice easy one! Just fold into a stack and bada-bing-bada-boom!
Part 1
I started with String and
String.last
. This got me the solution, but it turned out to be really slow. Here's my updated code using a Java LinkedList instead, which is multiple orders of magnitude faster.Part 2
This one seemed a little too simple at first, but my brute force implementation worked in about a 1500ms (still noticeably slow). After checking that my answer was correct, I did the stack optimization above which pulled me back down to 80ms or so.
Overall, this was a nice mid-week breather, and I'm happy to spend more of my thought cycles doing my OSCP lab work.
JavaScript solution
For this solution I used a stack. If the unit on top of the stack can react to the incoming unit, I just pop it out of the stack. Otherwise, I push it and move on.
reader.js
05-common.js
05a.js
05b.js
I'm a bit behind on these, but catching up this weekend! Day 5 is my favorite so far. 😁
I actually managed to complete Part A with an O(n2) algorithm, before realizing that would be too slow for part B...then I realized I could use a stack to implement an O(n) algorithm.
Part B is iterating through all letters in the alphabet, doing the string replace and then, doing the same reduction as Part A, while tracking the minimum reduced length. I feel like there's a better way to do that, but...never figured it out.
I logged my output and saw that, for my input,
v
reduced far better than anything else.My gut tells me there's some pattern in the input that would tell you which char to remove, and that way you only have to do the reduction once (as opposed to 26 times).
I looked at that, but when it wasn't definitively the letter that showed up the most, I didn't look very much further.
I bet you're right though, there's some "clustering factor" or something that would tip you off for which letter is most productive.
Probably won't get an explanatory blog post on this one today, and need to catch up to finish/submit yesterday's, but here's my Clojure solution for Day 5 (see gist.github.com/ballpointcarrot/7e...
Hey, here's my solution with ruby.
Nice and clean!
My day 5 solutions in Elixir. I'm actually pretty happy with how the code turned out this time, might be the cleanest of all days up until now.
The main idea of the implementation of part one is to put characters on a stack, and then compare the head of the stack with the next element to determine if the head and the new element should stay or go.
Part two is a wrapper around the first part, where the input is preprocessed (e.g. units are removed) before being fed to the implementation of the first part. The units to remove are based on unicode numbers.
Common:
Part one:
Part two:
Ugh, I hated this one, mainly because I took a completely wrong approach at first in an effort to be very fast. It was fast alright but could I get it to produce the right answer?!
Ali Spittel's stack solution is beautiful.
Late, but very happy with this one and had a lot of fun
Node.js
Full code: github.com/MattMorgis/Advent-Of-Co...
This is the first one of these I've tried and I'm a lazy person at best, so I did it in Vim:
There are only 52 combinations after all. Takes about 2 minutes (with
nohlsearch
...)Stage 2? Eh, my lunchbreak is really for lunch.
Wow, thanks for the idea to use a stack. I revised my first solution in OpenEdge 4GL and it went down from 39 second (yes, seconds) to 240 msec. A-ma-zing!