Here I’ve documented three different approaches to this problem:
We’re told that lanternfish populations grow exponentially, and we’re asked to model the growth of the population. Each lanternfish spawns a new lanternfish every 7 days, except for new lanternfish, which require an extra 2 days before spawning a new fish.
Our input data is a list of numbers, which are the number of days left until each fish spawns another fish. The data looks like this:
Given our input data, how many lanternfish will there be after 80 days?
At first glance, this seems like a simple problem. The naive approach is short and easy to write. Alas, as we’ll see, it has a problem!
We create list of
fish_timers from the input data, where each timer is the number of days until the next spawn. With each day, we update the existing fish timers, and add the new timers.
input_file = os.path.join(SCRIPT_DIR, INPUT_FILE) with open(input_file, mode="rt") as f: data = f.read() fish_timers = list(map(int, data.split(","))) logger.debug(fish_timers) # E.g. [3,4,3,1,2] fish_timers_copy = fish_timers.copy() days = 80 for _ in range(1, days+1): # we can't enumerate since we don't extra iterations when we spawn for i in range(len(fish_timers_copy)): if fish_timers_copy[i] == 0: fish_timers_copy[i] = 6 # reset this fish timer fish_timers_copy.append(8) # spawn a new fish else: fish_timers_copy[i] -= 1 # decrement this fish timer logger.info("After %d days, there are %d fish", days, len(fish_timers_copy))
The code above reads in the input data, splits it at the commas, and then converts each value to an
int. Nothing new there.
First, we make a copy of the
fish_timers. This is just so that we can use the same original input list when we do part 2.
Then we iterate through 80 days. Note that in this
for loop, we store each day in the variable
_. This is a convention in Python: if we’re not interested in this variable, and we’re not going to use it, then we use the value
Then, for each day, we now iterate through each
fish_timer (i.e. each fish), and do the following:
And for Part 1, this approach works fine!
2022-01-09 22:11:00.555:INFO:__main__: After 80 days, there are 376194 fish
Now we’re simply asked to determine how many fish there will be after 256 days.
This presents us with a predictable problem. Our naive solution doesn’t scale!
|Number of days||Time to solve|
If we extrapolate, this is going to take days to run! We need a different approach.
At this point, it’s obvious we can’t model every fish. We actually only need to track how many there of each timer, e.g. how many fish are spawning now, how many are 1 day away, how many are 2 days away, etc.
Here we can read the source data directly into a numpy array, using
np.loadtxt. We split the numbers at the commas, and convert each number to an int using
input_file = os.path.join(SCRIPT_DIR, INPUT_FILE) # read input, which is csv of ints # Each value is a fish timer, i.e. days until spawning another fish data = np.loadtxt(input_file, delimiter=",", dtype=np.int8) # [3 4 3 1 2]
Then we use
np.unique() with the
return_counts=True attribute to return all the unique fish timers in the input data, and count them all.
# np.unique() returns ordered unique items. With return_counts=True, it includes counts. # Timers [1 2 3 4], counts [1 1 2 1] init_fish_timers, counts = np.unique(data, return_counts=True)
We know there will be timers for all values 0-8 inclusive. Our input data may not include all of these types of timers. So let’s create a one dimensional numpy array of size 9 (i.e. 0-8 inclusive), and initialise all the values to 0. This represents our counters for each fish timer.
Then we can update this ‘zero’ array using the
counts we previously obtained from the input data. This works by using the
init_fish_timers to find all the corresponding index positions in
fish_timers, and then updating value at that position by using the corresponding position in the
# Initialise fish timers, by setting index positions to the counts in the array fish_timers = np.zeros(9, dtype=np.uint64) # [0 0 0 0 0 0 0 0 0] fish_timers[init_fish_timers] = counts # [0 1 1 2 1 0 0 0 0]
Now we create a
get_fish_count() function, which returns the number of fish after the required number of days. It works by:
np.roll(fish, -1), which effectively shifts the entire array one to the left, and wraps items on the far left over to the right. Thus, timers that were 0 now become 8 (representing new fish), items that were 1 become 0, etc.
by the number of fish that are now at
. I.e. the number of fish that have reset is equal to the number of fish that were just spawned.
def get_fish_count(fish_timers: np.ndarray, day_num: int) -> int: fish = np.copy(fish_timers) # create a new copy so we don't mutate the original fish for _ in range(day_num): fish = np.roll(fish, -1) # Roll: 2 becomes 1, 1 becomes 0, 0 becomes 8 (spawned fish) fish += fish # Add fish that were 0 are now reset to 6. return sum(fish)
We can now call this function with both 80 and 256, thus solving both Part 1 and Part 2:
for day in (80, 256): logger.info("At day %d, count=%d", day, get_fish_count(fish_timers, day))
The output looks like this:
2022-01-09 22:58:19.820:INFO:__main__: At day 80, count=376194 2022-01-09 22:58:19.830:INFO:__main__: At day 256, count=1693022481538 2022-01-09 22:58:19.831:INFO:__main__: Execution time: 0.0353 seconds
It’s quite quick!
This solution is super fast!
We don’t need numpy. We can achieve the same results using a
Counter and a
First, read the data, split it at the commas, convert each value to
int, and then store the counts of each type of fish timer:
input_file = os.path.join(SCRIPT_DIR, INPUT_FILE) with open(input_file, mode="rt") as f: data = f.read() data = [int(x) for x in data.split(",")] fish_timer_counts = Counter(data) # count the timers for each fish
Now we create a
deque that contains our nine timer values, 0-8 inclusive. The values are initialised to 0 if there weren’t any in the input data. Else, we use the counts from the input data.
# initialise an array of timer counts, for all timer values 0-8 timers = deque() for timer in range(9): timers.append(fish_timer_counts[timer] if fish_timer_counts[timer] else 0)
As before, we have a
get_fish_count() function. It does the following:
for days in (80, 256): logger.info("Fish at day %d: %d", days, get_fish_count(timers, days)) def get_fish_count(timers: deque, days: int): fish = timers.copy() # just so we can repeat this method with a different # of days for _ in range(days): fish.rotate(-1) fish += fish # count of newly spawned fish is same as count of fish that need to be reset return sum(fish)
2022-01-09 22:59:06.606:INFO:__main__: Fish at day 80: 376194 2022-01-09 22:59:06.607:INFO:__main__: Fish at day 256: 1693022481538 2022-01-09 22:59:06.608:INFO:__main__: Execution time: 0.0027 seconds
Yep, under 3ms. Pretty quick!