Advent Of Code and Algorithms
By Tyler
Authors note
I’ve had a hard time thinking of a topic to write on for this month. I knew I wanted something to do with Christmas, but couldn’t come up with something I found suitable. However at work this month I helped give two trainings where we solved one of the Advent of Code Puzzles for this year, and discussed the algorithmic complexity of two different solutions. Coming up on the end of the month, I decided that a discussion of the training, being tied to the advent of code, might be as much of a link to Christmas as I was going to get. I hope you all had a thoughtful and loving Christmas and have a happy New Year.
Introduction
Many years ago I came across Skiena’s Algorithm Design Manual. It was when I was first learning about computer science, and I found the topic enthralling. Skiena’s stories were intriguing and the methods taught were approachable. However when it came to the analysis of algorithms, I felt a little out of my element. The problem was that I really didn’t have enough experience to understand what the purpose of it all was. While I could grasp the ideas behind it, I failed to understand them.
Fast forward a few years, and I had the opportunity to provide a training at work. Through the course of this training we were able to learn and talk about these same concepts, such as algorithmic complexity and Big-O notation. The exercise was so exciting, and fun. Whats more is that now with experience under my belt, I felt I understood the concepts. My hope with this post is that at least a little of that excitment comes accross, and maybe some of the understanding too.
Problem Statement
For the training we decided that we would solve Day 6 of the 2021 Advent of Code. If you haven’t ever had the pleasure of learning about the Advent of Code, it is yearly fixture wherein every day leading up to Christmas a new programming challenge or puzzle is released. In this post I would like to walk down the same problem, with an eye to algorithmic analysis of the two solutions we came up with.
For a full treatment of the problem, I invite you to read the statement from the above link. Otherwise here is the wrap up. We are searching the sea floor in a yuletide submarine, searching for Santa’s sleigh keys. While there we notice a sizeable population of lanternfish and decide to model their population growth. Every 7 days a lanternfish will spawn a new fish, with newly spawned fish taking 9 days to spawn their first child fish, and then 7 days for all following children.
When developing and analyzing algorithms, the first thing we want to do is specify the task formally, describing both our inputs and our outputs. This will give us some common ideas to work with and reference in our solutions. Lets do that:
Given an array \(A: \langle v_1, v_2, v_3, …v_i \rangle \) where \(v_i \in [0, 1, 2, 3, 4, 5, 6] \), for \(n\) days, what would the length of \(A\) be if every day, for every \(v_i = 0 \), we added a new \(v_j = 8 \) to \(A\) , and set \(v_i = 6\) , with all other \(v_i \ne 0\) are decremented, such that \(v_i^\prime = v_i - 1\).
Now that we have formally specified our task at hand we can see that we are dealing with two inputs: \(A\) our initial array of fish, and \(n\), the number of days to simulate the growth of fish. We also are seeking one output: the length of \(A\) after \(n\) days.
Solution 1: Simulation
The code
The most straightforward solution would be to simulate the population growth by modeling each fish, and adding to the initial array as we go. This is the process that is described by the problem statement. Following the instructions is a surefire way to get the correct answer, so lets try it out. Below is some pseudo-code describing such a method:
|
|
That is fairly simple, with each line corresponding to a step in the above defined process. We start the procedure by initializing a loop over each day. Then for each day we loop over the existing values in the array. If a value in the array is equal to 0, we change it to be 6, and push a new value of 8 to the array. Otherwise we simple decrement the value in question by one. Once we have gone through all the days, we return the resulting length of the array \(A\).
How do we analyze algorithms?
The solution is simple and for now we will assume it is correct too. But how can we know how efficient it is before we do the work of programming it? This is where we need to start looking at a way to model our code in a theoretical computer. This will allow us to ignore strange details like the hardware being used, and the efficiency of languages used to implement our code. Using such a model would also allow us compare two or more procedures and make judgments on their relative efficiency.
The most common model when doing such an analysis is the Random-access Machine (RAM) model. With the RAM we assume we have a computer which can perform basic instructions (add, subtract, multiply, divide, assign variables, access variables, etc.) each in some constant (though not necessarily equal for each instruction) amount of time. Also the machine acts sequentially, processing each instruction in order.
Using this model, we can analyze pseudo-code of an algorithm and get an idea of how fast it can execute, before even programming it into a real machine. We simply count how many times each step will be executed, multiplying it by the cost of that step. With algorithms that only use basic instructions we will assume each line has some independent constant cost \(c_i\), where \(i\) is the line being executed.
Analyzing the simulation method
So let’s start counting the number of times each statement is executed, in our proposed solution.
|
|
Lines 1, and 8 are easy. Line 1 is executed \(n\) times, entering the loop
each time, and then 1 additional time on the last check, where the loop is
closed. Line 8 is only executed once, returning the final result. Lines 2-7,
however are trickier, as the value returned by A.length() will grow as we
progress. Not only that but because the \(A\) can come in with any values, we
don’t know when that growth will properly happen, and so it makes counting the
amount of runs difficult.
Because of this we are going to make 3 simplifying assumptions:
- We are going to assume our initial array starts with all \(v_i = 0\).
- We will not account for the initial “cooldown” for each new fish. In other words, whenever a new \(v_i\) is added to \(A\) it will have a value of 6, not 8.
- Finally we assume that \(n\) is divisible by 7.
We can justify these assumptions, since both Assumptions 1 and 2 have the effect of overestimating the time our procedure will take. This gives us an upper bound on the worst case possible. Assumption 3 doesn’t affect the final outcome on a worst case level, as it is trivial to pick an \(n\) with a value that is divisible by 7, and it simplifies the math for us. Analyzing the worst case is also the standard when comparing algorithms.
Armed with those three assumptions, we can begin to estimate how many times we
will run lines 2-7. In order to get a feel for it lets begin looking at the first few
days individually. In our calculations we will let \(\alpha\) be equal to the
initial length of A, and \(I_j\) be the number of times line 2 is run
for day \(j\).
Then on day 0: $$ I_0 = \alpha + 1$$
We run the loop \(\alpha\) times, and an additional check that closes the loop. Because of assumption 1, by the time we have completed the fist day \(A\) has doubled in size, with every value in \(A\) now being set to \(6\) (assumption 2). We then will have to wait 7 more days until the next large spawn, such that:
$$ I_1 = 2\alpha + 1$$ $$ I_2 = 2\alpha + 1$$ $$ I_3 = 2\alpha + 1$$ $$ … $$
And so on until \(I_8\) where the length of \(A\) has doubled again, resulting in: $$ I_8 = 4\alpha + 1$$
Following this pattern:
$$I_{15} = 8\alpha + 1 $$ $$I_{22} = 16\alpha + 1$$ $$…$$ $$I_{n} = 2^{\lceil{n/7}\rceil}\alpha + 1$$
So then the total number of times line 2 is run would be: $$ I_0 + I_1 + I_2 + … + I_n $$
Which we can rewrite as
$$ \sum_{d=0}^{n} 2^{\lceil{d/7}\rceil}\alpha + 1$$
This is a nasty sum, but it is solvable, reducing to $$ 14\alpha2^{\frac{n}{7}} + n - 13\alpha + 1$$ (see the Appendix for a full treatment on how to derive this solution to the sum)
We have now calculated how many times line 2 is run. Using similar logic, we can see that Line 3 is run \(14\alpha2^{\frac{n}{7}} - 13\alpha \) dropping the n and 1, because the checks to close the loop do not apply to this line.
Lines 4, 5 are both run \({14\alpha2^{\frac{n}{7}} - 13\alpha}\over 7 \), times, because the lines are only run when \(v_i=0\). Conversely lines 6, 7 are run \(6({14\alpha2^{\frac{n}{7}} - 13\alpha})\over 7 \) times.
We now have a good estimate on how long our algorithm will run, given any size \(n\) and \(A\). However the resulting equation is hideous.
$$ c_1(n + 1) + c_2(14\alpha2^{\frac{n}{7}} + n - 13\alpha + 1) + c_3(14\alpha2^{\frac{n}{7}} - 13\alpha) + {c_4{14\alpha2^{\frac{n}{7}} - 13\alpha}\over 7} + {c_5{14\alpha2^{\frac{n}{7}} - 13\alpha}\over 7} + {c_66({14\alpha2^{\frac{n}{7}} - 13\alpha})\over 7} + {c_76({14\alpha2^{\frac{n}{7}} - 13\alpha})\over 7} + c8 $$
This is where Big-O notation steps in. Even with all the assumptions we have made, we are getting more detail than we really care for. What Big-O does is shows us how our algorithm grows in the limit. As \(n\) gets very large, we can ignore constants, as they are merely scaling factors. Likewise we really only need to focus on the largest polynomial value, as lower order polynomials will be over-shaddowed by the largest one.
In doing this we can say that our Simulation algorithm runs in \(O(2^{n/7})\) time. This means that as we simulate more days, the algorithm will take exponentially more time to run. While simulating 70 days may be feasible (\(2^{70/7} = 1024\)), just trying to get to 210 days gets us into the level of billions. Clearly this is not a great solution. Could there be a better way?
Solution 2: Counting with a dictionary
The Code
Because we know that all fish advance days at the same intervals (i.e every fish experiences a new day at the same rate), any two fish on the same cycle are indistinguishable. What we could do, rather than simulate each individual fish, is keep track of how many fish are on what day in their countdown towards spawning a new fish. We could use a dictionary that maps each day (0-8), with the number of fish on that day in their reproduction cycle. Each day, we advance the values at each key to the next key, with key 0 being added to day 6, and day 8, representing the spawning of new fish. See below for our pseudo-code for this process:
|
|
Analysis
Because we are not dealing with the exponential growth of our array, analyzing the pseudo-code is far simpler:
|
|
Lets look at Each Line:
- Line 1 has a cost of 0 because it is a comment and not executed
- Line 2 has a cost of 0 because it is a comment and not executed
- Line 3 starts off our procedure, by creating a new dictionary with the keys 0 through 8, with each key having a 0 value. Because the dictionary is fixed in size we assume a constant cost to this step.
- Line 4 starts a loop to seed our
fish_dictwith the counts of fish at each day in the reproduction cycle, this means it will loop over all \(\alpha\) items, plus 1 other time to close the loop. - Line 5 is run \(\alpha\) times.
- Line 6 is run \(\alpha\) times.
- Line 7 has a cost of 0 because it is a comment and not executed
- Line 8 is run \(n+1\) times
- Line 9 is run \(n\) times.
- Line 10 is run \(9n\) times because it is run 9 times (once for every number 1-8, plus the time to close the loop), for every iteration of the outer loop.
- Line 11 is run \(8n\) times, once for every number 1-8, for every iteration of the outer loop.
- Line 12 is run \(n\) times.
- Line 13 is run \(n\) times.
Our resulting equation is:
$$ c_3 + c_4(α + 1) + c_5α + c_6α+ c_8(n + 1)+ c_9n+ 9c_{10}n+ 8c_{11}n+ c_{12}n+ c_{13}n+ c_{14} $$
Once again, we only care about the highest order polynomial, which in this case is \(n\). This means that our complexity is \(O(n)\), a huge improvement on our original solution. Running for 70 days our second algorithm is 14 times faster, and at 210 days it is over 5 million times faster.
Does it work?
All of this math and assumptions seems like an awful lot like armchair programming. Does any of this pan out in reality? To answer that question I implemented both versions of the pseduocode into a single python script (see appendix). I then timed the execution for \(n=70\), of 100 separate trials. Our first solution took an average of 0.490 seconds each round, and the second solution took on average 0.026 seconds to complete. This is about 18 times faster, which aligns closely with our predictions from our analysis.
So what?
There are a lot of things I enjoy about working with algorithms, and analyzing them. The math can be fun, and coming up with an efficient solution is rewarding. However there is a deeper insight I have learned from algorithm design, than merely getting computers to run faster. It is to “Work Smarter not Harder”. Christmas time and the New Year are natural times for us to pause and reflect on new goals and habits that we want to build into our lives. Sometimes the list of things we want to accomplish can feel overwhelming. Like our first solution, if we rely on our own sheer willpower we will quickly use up that limited resource. I know that in my own life, struggles that I have had were overcome, not by myself alone, but with the help of faith, family and friends. Christmas time is when we can recognize The Gift God has given us, with Christ showing us a more excellent way to live our lives in happiness. Rely on these resources and work smarter this coming year. Merry Christmas and Happy New Year!
Appendix
Summation
In order to solve:
$$ \sum_{d=0}^{n} 2^{\lceil{d/7}\rceil}\alpha + 1$$
we first remember that \(I_1 = I_2 = I_3 =…= I_7\), and so on for every 7 iterations, so that we can re-arrange the summation:
$$ \alpha + 1 + 7\sum_{d=1}^{n/7} 2^d\alpha + 1$$ Note that we pulled out \(I_0\) from the sum, and began the summation at \(d=1\). We also are able to sum to \(n/7\), because we have assumed n is divisible by 7 (assumption 3).
Using the linearity of summations we can expand this to:
$$ \alpha + 1 + 7\alpha\sum_{d=1}^{n/7} 2^d + 7\sum_{d=1}^{n/7} 1$$
Which simplifies to:
$$\alpha + n + 1 + 7\alpha\sum_{d=1}^{n/7} 2^d$$
Now that we have it simplified we can see that our main summation is a Geometric Series. Luckily some big brained mathematicians have figured out how to derive a formula from a geometric series, which means we can write this all as
$$\alpha + n + 1 + 7\alpha(2^{\frac{n}{7} + 1} - 2)$$ or $$ 7\alpha2^{\frac{n}{7} + 1} + n - 13\alpha + 1$$ and finally using some exponent rules $$ 14\alpha2^{\frac{n}{7}} + n - 13\alpha + 1$$
Simulate.py
#!/usr/bin/env python3
"""Simulate the Population Growth of Lanternfish"""
import argparse
def main():
parser = argparse.ArgumentParser()
parser.add_argument(
"-m", "--method", choices=["simulate", "mapping"], default="simulate"
)
parser.add_argument("days", type=int)
args = parser.parse_args()
if args.method == "simulate":
simulate_lanternfish(args.days)
else:
mapping_lanternfish(args.days)
DATA = [
1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1,
1, 1, 4, 1, 1, 1, 1, 3, 1, 1, 3, 1, 1, 1, 4, 1, 5, 1, 3, 1, 1, 1, 1, 1, 5,
1, 1, 1, 1, 1, 5, 5, 2, 5, 1, 1, 2, 1, 1, 1, 1, 3, 4, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 5, 4, 1, 1, 1, 1, 1, 5, 1, 2, 4, 1, 1, 1, 1,
1, 3, 3, 2, 1, 1, 4, 1, 1, 5, 5, 1, 1, 1, 1, 1, 2, 5, 1, 4, 1, 1, 1, 1, 1,
1, 2, 1, 1, 5, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 4, 3, 1, 1, 3, 1, 3, 1, 4, 1, 5, 4, 1, 1, 2, 1, 1,
5, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 4, 1, 1, 1, 1, 1,
1, 1, 5, 4, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 4, 1, 1, 1, 2, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 2, 1, 2, 1, 1,
4, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 4, 1, 5, 1, 1, 1,
4, 5, 1, 1, 1, 1, 1, 1, 5, 1, 1, 5, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 5, 5, 3,
]
def advance_day(fish_dict):
repro = fish_dict[0]
for i in range(1, 9):
fish_dict[i - 1] = fish_dict[i]
fish_dict[6] += repro
fish_dict[8] = repro
def mapping_lanternfish(n: int):
"""Simulates the Growth of a lanternfish population
This was our second algorithm written because our original became too slow at even moderate
amount of days. It Takes the fish, makes an initial counter of all the fish located at each
day, and then iterates over the days, moving and adding to the counter to keep track of
the number of lantern fish.
Args:
n (int): Number of days to simulate
"""
fish = {
# Day: Count
0: 0,
1: 0,
2: 0,
3: 0,
4: 0,
5: 0,
6: 0,
7: 0,
8: 0,
}
# Inital Seeding of fish:
for f in DATA:
fish[f] += 1
for _ in range(0, n):
advance_day(fish)
print(sum(fish.values()))
class LanternFish:
def __init__(self, time_to_reproduce=8):
self._time_to_reproduce = time_to_reproduce
def __str__(self):
return str(self._time_to_reproduce)
def advance_age(self):
"""Advances age, and produces a New Fish if time has come"""
baby_fish = None
self._time_to_reproduce -= 1
# self._time_to_reproduce = self._time_to_reproduce - 1
if self._time_to_reproduce < 0:
baby_fish = self.reproduce()
self._time_to_reproduce = 6
return baby_fish
def reproduce(self):
return LanternFish()
def simulate_lanternfish(n: int):
"""Simulates the Growth of the lanternfish population
This is our initial 'naive' attempt at solving a simulation for the growth of the lanternfish
population. The algorithim is straightforward, as it starts with an initial group of lantern
fish and iterates over it for every day, adding fish to the arrray as required.
Args:
n (int): Number of days to simulate
"""
initial_fish = [LanternFish(x) for x in DATA]
for day in range(0, n):
new_fish = []
for fish in initial_fish:
baby = fish.advance_age()
if baby:
new_fish.append(baby)
initial_fish.extend(new_fish)
if day % 10 == 0:
print(f"Day {day}: Total {len(initial_fish)}")
print(f"final total {len(initial_fish)}")
if __name__ == "__main__":
main()