Big(O) in a Little Pond
Happy December and Merry Advent of Code! 🎅🏻 🖥
For those who don’t know, Advent of Code is an annual coding challenge that runs from December 1-25. Instead of opening a little door to reveal a dry piece of chocolate, a new puzzle is released each night at 12:00am EST. The puzzles are code agnostic (use whatever language you want!) and the solution to each puzzle is a number, which you can calculate by processing your unique input (everyone gets their own!) with whatever code you write. Puzzles get harder every day and each consists of Parts 1 and 2, which build or vary on each other. Finishing a Part wins you a star, while finishing a whole puzzle gives you access to the next puzzle and fills in a line of color on the visual calendar.
The puzzles are contextualized in wild stories that give the whole challenge a lot more entertainment value and motivation than dry algo practice on HackerRack. The community around AoC is hugely supportive, which is especially helpful for those new to tech like me. (I highly recommend the subreddit for some amazing visualizations and solutions in hilarious/insane languages.) Many use AoC to level-up their skills, practice with or learn a new language, or get on the global leaderboard by solving each day in a matter of minutes.
Last year I tried out AoC when I was still just learning to code and it was such a fun challenge, even though I didn’t finish. Now that I have Flatiron’s Data Science bootcamp behind me, I’m excited to see how far I can get!
What’s the Big O-dea?
Day 6 hit something I’ve learned to love about AoC: creative optimization. Although the puzzle description was as far-fetched as the rest of them (watching glowing deep-sea lanternfish reproduce asexually and exponentially from my elf-run Christmas submarine), the solution ran into an actual, real issue that I often see discussed only in theoretical terms: Big O complexity.
There are many detailed explanations only a Google search away, so for now I’ll say that Big O refers to the worst-case scenario that could result from a piece of code in terms of how much memory and/or time the code requires to run.
For example, searching for a value in a list or array by iterating over every item has O(n) (say: “O of N”) time, or linear time. That’s because the worst case is that the item you’re looking for is at the end of the list, so you have to look through n items. Calculating y=2x has O(1) time, or constant time, because no matter how big x is, you only have to do one calculation. However, things like nested for loops may run in O(n)-times-O(n), or quadratic O(n²) time, if one loop iterates over its entire array n times within the other loop.
While discussions of Big O are often a Big Yawn, today’s AoC puzzle showed me firsthand how important these concepts really are.
Big Ef-fish-iency Gains
In the puzzle, each fish in a school reproduces (on its own) every 7 days. However, not only are the fish not synced up, brand new fish actually take 9 days to reproduce their first time, then 7 after that.
The given puzzle input represents each fish as an element in an array; the value of each fish represents the number of days until it reproduces. For example, the array [3, 4, 2, 1, 1] contains 5 fish in total. The first fish has 3 days left before it reproduces, the second fish has 4 days, etc.
After 1 day, the array would look like this: [2, 3, 2, 0, 1] The fourth fish is about to reproduce!
After 2 days, it would look like this: [1, 2, 1, 6, 0, 8] Another fish has been added at the end, with 8 days left before it reproduces, while the fourth fish’s counter has reset from 0 to 6.
The question posed is, how many fish will there be after 80 days? Here’s my initial solution:
I split up my solution into one poorly-named helper function and one main solution() function, and it worked just fine. I submitted my final answer, collected my star, and happily read Part 2:
Suppose the lanternfish live forever and have unlimited food and space. Would they take over the entire ocean? After 256 days in the example above, there would be a total of
26984457539lanternfish!How many lanternfish would there be after 256 days?
Easy! I typed solution(puzzle_input, 256) and confidently hit return, then waited. And waited. And waited.
I went to get some water, came back, and my code was still running 5 minutes later. Weird, I thought. It’s just simple addition and subtraction. And then it hit me like a ton of fish.
O(holy night), quadratic time is real
The puzzle description had even said that the fish “must spawn quickly to reach such large numbers — maybe exponentially quickly,” but did I listen? Big n(O)!
I ran some visualizations to check — yup, the population was doubling every 7 days, exactly as I would have expected if I had, you know, paid attention in the first place.
My original solution was classic O(n²), but given the constraints of my computer’s memory and processing power, I clearly needed a more optimized solution if I wanted an answer now. Trying to create and iterate over an array of over 1.5 trillion elements (yes, actually) was simply not going to cut it. I had run into actual, physical limits — and learned a hard lesson in Big O.
I researched population growth equations, but those only got me estimates, not answers. I fiddled around with my code and analyzed counts and sums and ratios, but couldn’t see a way around that big, big O. I was stuck. Finally, I went looking for help and stumbled across a hint in the Advent of Code subreddit that seemed as mysterious and important as the Rosetta Stone:
“To solve this puzzle, you only need a 9-element array.”
What?! How??? It seemed too good to be true. But knowing that it could be done turned out to be half the battle.
Joy to the linear time!
I finally realized I could use a type of solution that brings me far more joy than it should. Rather than representing each fish as its own array element, I could use the array indices as a source of information about the whole school! Each element at index i could represent the number of fish with i many days left before reproducing.
In other words, [3, 4, 2, 1, 1] would be [0, 2, 1, 1, 1, 0, 0, 0, 0]. Two iterations later, [1, 2, 1, 6, 0, 8] would be likewise be represented as [1, 2, 1, 0, 0, 0, 1, 0, 1]. The problem would run in constant O(n) time instead of quadratic time and use far less space as well.
Instead of an array with over a trillion elements, my array had only 9. It’s also possible to use a dictionary/hash table instead and I’m sure I didn’t need to import deque. I make no claims to have the best solution; in fact, I’m sure there are still more optimized ways to write this solution — maybe even a constant O(1) time solution.
What I love about this solution though is how it makes optimal use of the array, using every bit of it to contain information. It’s a lesson I’ve learned before in theory, but I think experiencing the consequences of quadratic O(n²) time for myself will really make it stick. Or so I hope.
Merry Advent of Code and keep coding O(n!) (Wait, that’s the worst one…)
(Edit: I have corrected an error in this article. I originally described O(n²) as exponential time, which is incorrect! O(2^n) is exponential time; O(n²) is quadratic time.
