Hi! Day 14 is here. Unfortunately, I'm falling behind, but I'll catch back up this weekend. And I'm excited to get caught up because then I can look at everybody else's solutions.
Today, we encounter a couple of elves making some hot chocolate with different recipes. Much like the marbles a few days ago, it's looking like we're looping over some scores and adding in some new ones.
Top comments (15)
Today's is a low-level one. Might be interesting to do it in assembly language, if I could remember any. The key insight is you're going to eventually need a very large array but we only ever append to it, so preallocating the buffer is a sensible idea for performance. I decided to forego all the high-level modelling and implement it C-style.
First make a big buffer and initialise all the state we need.
I'm storing the values as the ASCII characters for the digits, so one high-level language comfort is a helper function to pull out the values.
Then run the algorithm until we have enough data in the buffer:
And extract the answer:
Part 2 makes the problem slightly harder in that we don't know the eventual size of the buffer. A classic approach is to start with some sensible number (let's say 1024) and reallocate it twice the size each time we hit the end. The number of copies is therefore limited to log2(N).
The other tricky part is that we don't know how many digits are added to the array each iteration, so we can't assume the target string is right at the end. We know it is near the end though, so I therefore search for the target string from 5 characters before the old end to the new end of the array.
Full code here
This bit me too at first, but then I realized you only ever need to check the very end or offset by one character. This is because you can only ever add 1 or 2 digits to the end of the array!
You're right. So I could have optimised a tiny bit more by starting at oldLength-4.
Anyway I quite enjoyed today's low-level one after aiming to do them all in a mostly functional style up to now. Takes me back to my years doing embedded C and Linux device drivers.
A python solution using a generator.
A translation of the python solution with generators to C++.
It works but my C++ is very, very limited.
Part 1 was rather easy - just generate an array of numbers.
Part 2 took a while to figure out why test cases pass, but my input gave me "out of memory" error. Very sneaky :)
The part 1 was super easy: I just pushed new elements to an array.
When I adapted the algorithm for the part 2, it took almost a minute to get the answer. To optimize it, I used strings instead of arrays of numbers (strings are not arrays in Perl).
Part two of this really needed some performance work to finish. The
next_recipesmethod does the work of moving the elves from their current scores to the next. Then the loops are built differently to return the final result.
This is my attempt in Crystal:
tailrecsolution for the books. I had some issue with how long this took. After a few frustrating minutes, I figured out that
.takeLast()was not as efficient as the
.get()or array access notation.
This one threw me, since the solution was so much farther out than I expected...
I liked this one quite a bit too!
OK, I'm caving. I'm going to be doing these in Python from here on out, I think. They're getting tough enough that I don't need to be fighting with Rust's borrow checker and the challenge itself. It feels like trying to win a debate on foreign policy in Mandarin. Also, Python is way more fun. And it's Christmas, so Merry Christmas to me and Python. 😬
Anyways, enough whining from me. Here's my solution from day 14.
I did Part 1 using arrays and I attempted Part 2 using indexOf to locate the input inside the array.
I was getting memory errors, so I wrote an algorithm that would always attempt to find the input as the last N elements of the scorecard, backwards. With a few optimizations, it runs in 5 seconds!