Sean McLemon | Advent of Code

2021-12-06 - Lanternfish

(original .ipynb)

Day 6 puzzle input is a sequence of integers representing the ages of lanternfish (mine is here). Part 1 involves following the lifecycle of these lanternfish over 80 days, where every 7 days lanternfish will spawn a new one (so a lanternfish that starts with age 4 will produce a new fish in 4 days, then another 7 days after that). Part 2 involves doing this over 256 days.

puzzle_input_str = open("puzzle_input/day6.txt").read()

test_input_str = """3,4,3,1,2"""


def part_one(input_str, days=80):
    fish = [int(age) for age in input_str.split(",")]
    while days > 0:
        new_fish = 0
        for i in range(len(fish)):
            if fish[i] == 0:
                fish[i] = 6
                new_fish += 1
            else:
                fish[i] -= 1
                
        fish += [8] * new_fish
        days -= 1

    return len(fish)


assert 5934 == part_one(test_input_str)
print("part one:", part_one(puzzle_input_str))

part one: 356190

# part_one(puzzle_input_str, 256) <--- with 102 steps remaining the naive algo reports
#                                      that there are 244,225,750 fish which suggests
#                                      I do not have enough memory to keep this going
#
# so after seeing the O(N^2) algo won't run in reasonable time my heart sunk and I realised
# I might actually have to think about this one. first thought: could I maybe keep the
# existing brute force algo and chunk it into 12 processes and just run it on my 12 core
# cpu at home ... then when trying to break the problem down like that realised the order
# of the fish doesn't matter - just need to count how many there are at each step
#
# we are not our best selves at 6:00am

def part_two(input_str):
    fish = [0] * 9
    for age in input_str.split(","):
        fish[int(age)] += 1
        
    days = 256
    while days > 0:
        next_fish = [0] * 9
        for age, count in enumerate(fish):
            if age == 0:
                next_fish[6] += count
                next_fish[8] += count
            else:
                next_fish[age-1] += count
        fish = next_fish
        days -= 1
        
    return sum(fish)


assert 26984457539 == part_two(test_input_str)
print("part two:", part_two(puzzle_input_str))

part two: 1617359101538