Day 6: Lanternfish
Today's problem description: https://adventofcode.com/2021/day/6
Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace
python with any of the "short names" listed in this page of supported languages):
<details> <summary>Part 1</summary> ```python Your code here. ``` </details>
Python golf, day 6. Parts 1 and 2 are identical beyond the number of iterations, but I'll post 'em separately anyway.
open(0)since there is only one line
I knew I sensed a trap when I read that problem description. This one is really mean if you don't know how to deal with a problem like this. It's a bit of a gotcha.
Day 6 Part A- Python
I feel like the problem description implies that you should create fish objects and let them reproduce. That would be a nightmare. I just made a list representing populations for a given number of days remain and shoved them around.
Day 6 Part B - Python
Because of the way I made my code, I only had to update the duration and it worked perfectly.
If you try to fully model this problem, your code risks imploding. And by imploding I mean taking an incredible amount of time to run. This problem deals with exponents and that will make your numbers get very big very quickly.
Try to look at what's actually happening with the math. What do you really care about and what can you ignore?
All fish with the same number of days remaining perform the same action
There are a limited number of possible days a fish can have
Dammit, just keeping track of fishes per timer count is genius. I would never have thought of essentially turning the problem backwards and just counting fish count per timer state.
What I did was doing 8*256 caches and brute-forcing it. It worked and it's surprisingly fast. Still such a mess compared to this, lol.
part 1 I did via brute force. when part 2 was revealed, I just updated my script to simulate 256 days, let it run, and then started writing part 2 using the non-brute-force approach.
when I killed the brute-force script (after about 11 minutes), it was only on day 155, with a fish population of 237636802. its memory consumption was around 17gb. based on the ratio of that population to the population on my final day, it would have taken ~112 terabytes of RAM to host all 256 days of the brute-force simulation (to say nothing of the runtime)
meanwhile my more optimized part 2 runs in 27 milliseconds and uses negligible memory compared to the overhead of the Python runtime.
LOL, that would have required 3,500 32GB DIMMs. The cheapest on pcpartpicker currently being $79.73 per. So even if you could fit that many inside a computer, it would have cost $279,055, at minimum. :P
You laugh, but I legitimately have coworkers that would just decide to throw money at hardware to solve the problem instead of optimizing a simple calculation.
I almost went with that attitude. I had plugged in an sqlite memory-to-DBI translation layer to overcome my limited physical memory before I realized the critical trick. On the plus side, it's trivial to do!
Well, to be fair, Python is not the most memory efficient language. It allocates 4 bytes per int. If you used
chars in C or
u8s in Rust you could probably get that cost down to just $69,763!
Actually, numbers in Python have an overhead of 24 bytes of memory if you use them "normally". A number for this challenge in Python is 28 bytes.
Edit: It kind of helps that they're all interned in this case, though. Because of that, a long array would be reduced to roughly 8 bytes per entry, since it's just a pointer to a cached number.
I didn't have the spidey sense that @PapaNachos had when they read the problem, I actually implemented part 1 in the naive way that they described. I knew it was in trouble when my program was stalling out calculating just the example on part 2!
After a bit of thinking though, I was able to get to the same solution as PapaNachos, using a deque!
This was interesting. It gives you a simple problem then repeats the exact same problem again for part 2, but with an input large enough that you are forced to optimize your solution.
I knew something was up with the way the problem was described, but to be honest, I was expecting a change in the reproduction mechanism instead of what we got. The part 2 twist seemed almost too simple until I saw my code struggling to run the test data and eventually getting an "invalid size error" trying to fit 169 million values into an array. Definitely an interesting mislead. I feel pity for anyone who tried to model part 1 using objects.
One thing I've learned from AoC is that I suck very badly at trying to write code quickly which doesn't mesh well with being competitive.
I guess anyone who's a competitive programmer (or thoughtful - unlike me) fell for the same trap in Part 1 because the question was deliberately presented to lead you in that direction... Bad Eric.
As usual, the right data structure makes all the difference!
All that's left is to simulate the change in population for a day and count the total fish.
Copy the table of your personal stats and then enjoy them presented as charts.
I'm one of those that fell for the trap. In my defense, I hadn't had my coffee yet.
Runs in about 200 microseconds on my machine, despite the fact that it can still be optimized even more. May do so when I get home from work.
Dumb question, but I was having some issues with my code for Part II so I figured I'd look at what you're doing. When I try to run your code I am not getting the correct answer.
My Part I gives me: 351188
Yours gives me: 350154
The only thing I could think of is maybe related to the input file format?
That's the only thing I can think of without more detail. Maybe try replacing the
since yours may have a newline at the end, and that fails the parse call without erroring out.
Oh yeah, that was it. Thanks.
Not sure why there was a newline though, since the file didn't seem to show one.
Hoooo boy, lots of Rust in here today! Well, I'll add my solution.
Rust (both days)
I'm pretty proud of today's!
I make excuses for myself when all the pythonistas post really simple code. I say "oh, well Rust is way more verbose and complicated, there's no way I could make my code look as nice and easy to understand as theirs."
And then you show up with that beautiful solution and just completely ruin my day. ;)
That's how I feel with my Rust most of the time :P I was pretty proud I figured out a relatively simple solution for today's. And, if it makes you feel better, my code for most of the earlier days is pretty gross :P
Hey, it's the first optimization puzzle of the year!
I did the same brute-force approach as many others for the first part, found the trick for part two pretty quickly, then spent way too long getting my implementation to work right (it didn't help that I'd left my inefficient part one code running in the background until it ate all my memory and stalled out my PC until I went back and closed it out).
Part 1 Ruby
There's an awkward step in here where I'm adding new fish at
8, so that the decrement step in the next line leaves things in the correct state. I think this could be cleaned up, but the whole thing gets re-written in P2 anyway.
Part 2 Ruby
Hey, here's the cool trick version! I immediately realized that there was no way we could keep a separate integer for each fish. As with the big grid problems in years past, I started thinking of a hashmap relating the timer/state of each fish to the number of fish in that state (since the order/heritage of each fish doesn't matter, just the total number). I also recognized that there are only 9 different states a fish can be in (0-8), and a "hashmap" that only has integer keys 0-8 is really just an array with 9 elements. From there the trick of treating the array as a queue was a natural step.
I managed to find the trick to get linear runtime, but this morning my housemate realized it can be done in O(log(n)):
(Ignore the first line; it's just reading input from stdin. My code above actually gets transpiled to
By my tests this is slower than my linear-time version for
n = 256, but it starts beating my linear-time version around
n = 2_000_000(~ 5 s runtime).
There is then also a speedup that can be had by diagonalizing the transition matrix when taking the power of it, but I'm not sure how to do this (fast) without introducing numerical error:
For my input and laptop this approximation works up to
n = 260, but rounds the wrong way at 261. The speedup for
n = 261is about 2.3x.
I tried using sympy do this exactly but it was much slower than not diagonalizing and just using Python's
int. Let me know if any of you know of a way to get the speedup without losing precision...
This one lent itself well to Elixir's
Streammodule, which lets you create and work with lazy, potentially infinite enumerables that generate elements one at a time on demand. I could set up a stream that emits each day's modeled fish population, index into it as if it were a list (with
Enum.at/3), and get the population count on the day in question.
As with others, I went with the naive approach to modeling the fish population for part 1, then needed to update the data structure used to avoid running out of memory while running the solution for part 2.
Fish-modeling data structure, before and after
For part 1, I went with the puzzle description's suggestion of modeling each fish as a number representing its age, where the list grows in length every time a new fish is born.
For part 2, I changed the structure to a map that groups all fish of the same age together, since there isn't any different behavior for two fish of the same age. This prevents the memory footprint from growing every time a new fish is added to the population. It was also made especially easy by the function
Enum.frequencies/1in the standard library.
Once I again I suspected the twist, and still did it the naive way for part 1. I almost think it is a little more fun that way! Anyway, the data structure I used yesterday as a easy way to count up the vents came in handy and did a lot of the work for me, which I enjoyed.
Nim Part 1
Nim Part 2 Additions
I found an even more elegant solution online.
It took me a while to understand why it works; I worked through it in writing and I thought it might be of interest to the thread.
Very elegant solution
Assumption: we have an initial array of size 256 with the number of fish that reproduce on that day.
E.g. for input
[0, 1, 1, 2, 1, 0, 0, 0, 0, ...].
Since our array is ordered by days, we can look at each day in succession.
Every day-entry in our array tells us how many fish spawn offspring that day, and since all fish are spawned with a timer value of 8, we need to insert them 9 days in the future, so that they are exactly 8 days removed once the day rolls over.
Now we need to deal with the parent fishes. They can create another offspring 7 days later
(equivalent to a timer value of 6) so we insert them at that time:
Then we can read out the appropriate elements of the population vector and get the correct answer to the puzzle at that number of days.
However, there is a clever optimization possible: since we only ever need to look ahead for 9 days,
we can reuse the current array entry for the day 9 days hence.
To do that, we wrap our indices with the modulo operator:
If you look at it for a bit, we're doing redundant work here because
(day + 9) % 9equals
That means we are adding the current
savedpopulation to exactly the entry we had just cleared out.
So we don't need to save and clear that entry at all, because it ends up with the same number of fishes anyway.
This leaves us with a single instruction for updating the population:
Quick question while working on my solution in Rust.
Part 1 was pretty easy once I got my question answered.
I knew what was going to happen when I ran Part II, but I decided to break things anyway.
Can you share the full source? There’s not enough here for me to help you out.
Sure, didn't want to overload too much.
Full code so far
process_fishfunction doesn't have a return type.
Oh, duh. I knew it didn't have one yet, but didn't think about it since the error code didn't seem related.
Day 06 (Rust)
Today I'm trying something new: Entangled, a literate programming tool.
Normally, programs are interspersed with comments to explain what is going on.
Literate programming turns this on its head -- the primary artifact is the human-readable documentation, in which the source code is embedded.
Through a process called tangling, the source code is extracted from the documentation and written to a standalone file for compilation and execution.
Entangled is especially nice, because it allows you to automatically synchronize your work: tangling copies code from the markdown source into an
.rs-file, while stitching does the opposite, taking changes to the source code and transplanting them back into the documentation.
SimulationSince the timer of a Lanternfish is bounded in \[0, 8\], we can simply make an array of size 10 to hold the count of fish with that timer value. The extra slot at the end of the array is used to store a temporary count for newly spawned fish.
Note how we're using indices that are one higher than stated in the problem description -- we're always decrementing the counter instead of keeping it constant when necessary, and hence start it one higher than expected.
Parsing is simple today: the input is a single line with comma-separated numbers.
We simply tick the simulation 80 times.
Part B is trivial today, we just have to tick the simulation 256 times.
It just occurred to me, that the fish are independent of each other. So you can calculate how many other fish a single fish spawns, and then sum that value up for each fish in the input. This immediately leads to a memoized solution.
It's about 3x slower than the array method, but I thought it was neat:
I fell in this bait, so I after the first task I redid almost all.