# Day 6: Lanternfish

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
```

</details>
``````

1. deckard
(edited )
Python golf, day 6. Parts 1 and 2 are identical beyond the number of iterations, but I'll post 'em separately anyway. Part 1 I=*map(int,input().split(',')), F=[I.count(i)for i in range(9)] for d...

Python golf, day 6. Parts 1 and 2 are identical beyond the number of iterations, but I'll post 'em separately anyway.

Part 1
``````I=*map(int,input().split(',')),
F=[I.count(i)for i in range(9)]
for d in range(80):F=F[1:7]+[F+F,F,F]
print(sum(F))
``````
Part 2
``````I=*map(int,input().split(',')),
F=[I.count(i)for i in range(9)]
for d in range(256):F=F[1:7]+[F+F,F,F]
print(sum(F))
``````

Edit: Using `input()` instead of `open(0)` since there is only one line

2. 
PapaNachos
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...

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.

``````from collections import defaultdict
import re

#data = test_data
data = real_data
data = data.split(',')

fish_count = list()*9

for fish in data:
fish_count[int(fish)] = fish_count[int(fish)] + 1

for day in range(80):
#print(fish_count)
new_fish_count = list()*9
for i in range(0,8):
new_fish_count[i] = fish_count[i+1]
new_fish_count = new_fish_count + fish_count
new_fish_count = fish_count
#print(new_fish_count)
fish_count = new_fish_count
#print("----")
print(fish_count)
print(sum(fish_count))
``````
Day 6 Part B - Python

Because of the way I made my code, I only had to update the duration and it worked perfectly.

``````from collections import defaultdict
import re

#data = test_data
data = real_data
data = data.split(',')

fish_count = list()*9

for fish in data:
fish_count[int(fish)] = fish_count[int(fish)] + 1

for day in range(256):
#print(fish_count)
new_fish_count = list()*9
for i in range(0,8):
new_fish_count[i] = fish_count[i+1]
new_fish_count = new_fish_count + fish_count
new_fish_count = fish_count
#print(new_fish_count)
fish_count = new_fish_count
#print("----")
print(fish_count)
print(sum(fish_count))
``````
Tips
• 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

1. nothis
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...

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.

3. 
spit-evil-olive-tips
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. Part 1 def...

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.

Part 1
``````def main():
with open('006.txt') as file:
fishes = [int(age) for age in file.readline().split(',')]

for day in range(80):
print(f'day {day}: {len(fishes)}')
for i, timer in list(enumerate(fishes)):
if fishes[i] == 0:
fishes.append(8)
fishes[i] = 6
else:
fishes[i] = timer - 1

print(len(fishes))

main()
``````
Part 2
``````from collections import defaultdict

def main():
with open('006.txt') as file:
fishes = [int(age) for age in file.readline().split(',')]

population = defaultdict(int)
for timer in fishes:
population[timer] += 1

for day in range(256):
print(f'day {day}: {dict(population)}')
new_population = defaultdict(int)
for timer, count in population.items():
if timer == 0:
new_population = count
new_population += count
else:
new_population[timer-1] += count

population = new_population

print(sum(population.values()))

main()
``````

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.

1. 
cfabbro
(edited )
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...

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

1. 
Liru
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.

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.

1. Ephemere
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...

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!

2. 
blitz
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!

Well, to be fair, Python is not the most memory efficient language. It allocates 4 bytes per int. If you used `char`s in C or `u8`s in Rust you could probably get that cost down to just \$69,763!

1. Liru
(edited )
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...

It allocates 4 bytes per int.

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.

4. blitz
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...

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!

Rust Solution

5. Crestwave
(edited )
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. Part 1...

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.

Part 1
``````#!/usr/bin/awk -f
{ ptr = split(\$0, fish, ",") }

END {
for (day = 0; day < 80; ++day) {
for (i in fish) {
if (fish[i] == 0) {
fish[i] = 7
fish[++ptr] = 8
}

fish[i] -= 1
}
}

print ptr
}
``````
Part 2
``````#!/usr/bin/awk -f
{
split(\$0, input, ",")
for (i in input)
fish[input[i]] += 1
}

END {
for (day = 0; day < 256; ++day) {
for (i in fish)
state[i] = 0

for (i in fish) {
if (i == 0) {
state += fish[i]
state += fish[i]
} else {
state[i-1] += fish[i]
}
}

for (i in state)
fish[i] = state[i]
}

for (i in fish)
total += fish[i]

print total
}
``````
6. petrichor
Python def spawn(days): age = *10 for num in input.split(","): age[int(num)] += 1 for day in range(days): for i in range(len(age)): if i == 0: age += age age += age age -= age...
Python
``````def spawn(days):
age = *10
for num in input.split(","):
age[int(num)] += 1

for day in range(days):
for i in range(len(age)):
if i == 0:
age += age
age += age
age -= age
else:
age[i-1] += age[i]
age[i]   -= age[i]
return sum(age)
``````
7. 3d12
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...

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.

Part 1
``````const fs = require('fs');

let inputArr = [];

input: fileStream,
crlfDelay: Infinity
});

for await (const line of rl) {
try {
inputArr.push(line);
} catch(e) {
console.error(e);
}
}
}

function processDay(inputArray) {
let fishToBeBorn = 0;
let outputArray = [];
for (const fish of inputArray) {
if (fish === 0) {
fishToBeBorn++;
outputArray.push(6);
} else {
outputArray.push(fish - 1);
}
}
for (let i=0; i<fishToBeBorn; i++) {
outputArray.push(8);
}
return outputArray;
}

(async function mainExecution() {
let lanternFishArray = inputArr.split(',').map(e => parseInt(e));
let days = 0;
let totalFish = 0;
while (true) {
lanternFishArray = processDay(lanternFishArray);
days++;
if (days === 80) {
totalFish = lanternFishArray.length;
break;
}
}
})();
``````
Part 2
``````const fs = require('fs');

let inputArr = [];

input: fileStream,
crlfDelay: Infinity
});

for await (const line of rl) {
try {
inputArr.push(line);
} catch(e) {
console.error(e);
}
}
}

function processDay(inputSerializedArray) {
let fishToBeBorn = 0;
let outputObject = { zero: 0, one: 0, two: 0, three: 0, four: 0, five: 0, six: 0, seven: 0, eight: 0 };
if (inputSerializedArray.zero > 0) {
fishToBeBorn = inputSerializedArray.zero;
}
outputObject.zero = inputSerializedArray.one;
outputObject.one = inputSerializedArray.two;
outputObject.two = inputSerializedArray.three;
outputObject.three = inputSerializedArray.four;
outputObject.four = inputSerializedArray.five;
outputObject.five = inputSerializedArray.six;
outputObject.six = (inputSerializedArray.seven + fishToBeBorn);
outputObject.seven = inputSerializedArray.eight;
outputObject.eight = fishToBeBorn;
return outputObject;
}

function serializeArray(inputArray) {
let returnObject = { zero: 0, one: 0, two: 0, three: 0, four: 0, five: 0, six: 0, seven: 0, eight: 0 };
for (const item of inputArray) {
switch (item) {
case 0: returnObject.zero++;
break;
case 1: returnObject.one++;
break;
case 2: returnObject.two++;
break;
case 3: returnObject.three++;
break;
case 4: returnObject.four++;
break;
case 5: returnObject.five++;
break;
case 6: returnObject.six++;
break;
case 7: returnObject.seven++;
break;
case 8: returnObject.eight++;
break;
default: return new Error("Invalid number in serialization: " + item);
}
}
return returnObject;
}

(async function mainExecution() {
let lanternFishArray = serializeArray(inputArr.split(',').map(e => parseInt(e)));
console.log(lanternFishArray);
let days = 0;
let totalFish = 0;
while (true) {
console.log("DEBUG: Processing day " + (days+1) + "...");
lanternFishArray = processDay(lanternFishArray);
days++;
if (days === 256) {
totalFish = (lanternFishArray.zero + lanternFishArray.one
+ lanternFishArray.two + lanternFishArray.three
+ lanternFishArray.four + lanternFishArray.five
+ lanternFishArray.six + lanternFishArray.seven
+ lanternFishArray.eight);
break;
}
}
})();
``````
8. Bauke
I'm glad I immediately figured out what the puzzle was hinting towards and didn't fall into the trap like others mentioned. Another fun day though! Runtime Day 06 Part 1: 343441 Day 06 Part 2:...

I'm glad I immediately figured out what the puzzle was hinting towards and didn't fall into the trap like others mentioned. Another fun day though!

Runtime
``````Day 06 Part 1: 343441
Day 06 Part 2: 1569108373832
- Runtime: 308.454µs
``````
Imports and setup
``````use std::collections::HashMap;

use color_eyre::Result;

type FishMap = HashMap<isize, isize>;

pub fn solve() -> Result<()> {
let input_data = include_str!("../../data/day_06.txt").trim();
println!("Day 06 Part 1: {}", part_1(input_data)?);
println!("Day 06 Part 2: {}", part_2(input_data)?);
Ok(())
}
``````
Parsing the fishies
``````fn parse_fishes(input: &str) -> Result<FishMap> {
let mut fishes = FishMap::new();
let individual_fishes = input
.split(",")
.map(str::parse)
.collect::<Result<Vec<_>, _>>()?;

for fish in individual_fishes {
let amount = fishes.entry(fish).or_default();
*amount += 1;
}

Ok(fishes)
}
``````
Simulating the fishies

I could probably make it faster if I reused the HashMap instead of making a new one each time when simulating the fishes, but I don't think I'm going to care about an optimization when the runtime is already below millisecond territory.

``````fn simulate_fishes(fishes: FishMap) -> FishMap {
let mut new_fishes = HashMap::new();

for (mut timer, amount) in fishes {
timer -= 1;

if timer < 0 {
let new_fish = new_fishes.entry(8).or_default();
*new_fish += amount;

let reset_fish = new_fishes.entry(6).or_default();
*reset_fish += amount;
} else {
let current_fish = new_fishes.entry(timer).or_default();
*current_fish += amount;
}
}

new_fishes
}
``````
Counting the fishies
``````fn count_fishes(fishes: FishMap) -> isize {
fishes.into_iter().map(|(_, amount)| amount).sum()
}
``````
Solving both parts
``````fn part_1(input: &str) -> Result<isize> {
let mut fishes = parse_fishes(input)?;

for _ in 0..80 {
fishes = simulate_fishes(fishes);
}

Ok(count_fishes(fishes))
}

fn part_2(input: &str) -> Result<isize> {
let mut fishes = parse_fishes(input)?;

for _ in 0..256 {
fishes = simulate_fishes(fishes);
}

Ok(count_fishes(fishes))
}
``````
9. pnutzh4x0r
JavaScript (Both Days) I wrote my first solution in Python using a dictionary (I figured the brute-force method would not work right away). Once I got that to work, I re-wrote my solution in...
JavaScript (Both Days)

I wrote my first solution in Python using a dictionary (I figured the brute-force method would not work right away). Once I got that to work, I re-wrote my solution in JavaScript using a fixed sized array (thanks to @deckard for the inspiration).

One cool thing is learning about JavaScript's spread operator... hopefully I'll get more comfortable with JavaScript and can opt into trying that first (rather than doing it in Python and then translating it to JavaScript).

``````// Constants

const MAX_DAYS  = 256;
const RESET_DAY = 6;
const BIRTH_DAY = 8;

// Functions

function simulate_day(old_table) {
newborns = old_table[BIRTH_DAY];
resets   = old_table + old_table[RESET_DAY + 1];
births   = old_table;
return [...old_table.splice(1, RESET_DAY), resets, newborns, births];
}

function simulate_days(table, days = MAX_DAYS) {
for (let day = 0; day < days; day++) {
table = simulate_day(table);
}

return table.reduce((a, b) => a + b, 0);
}

// Main Execution

let fish_table = new Array(BIRTH_DAY + 1).fill(0);

IO.print(`Sample: \${simulate_days(fish_table.slice(0), 18)}`);
IO.print(`Part A: \${simulate_days(fish_table.slice(0), 80)}`);
IO.print(`Part B: \${simulate_days(fish_table.slice(0), 256)}`);
``````
10. bhrgunatha
(edited )
Notes 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...
Notes

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!

``````(define (initial-population input)
(define fish (make-vector 9))
(for ([f input])
(vector-set! fish f (add1 (vector-ref fish f))))
fish)
``````

All that's left is to simulate the change in population for a day and count the total fish.

``````(define (simulate-day fish)
(define new-fish (make-vector 9))
(define delta (vector-ref fish 0))
(vector-copy! new-fish 0 fish 1 9)
(vector-set! new-fish 8 delta)
(vector-set! new-fish 6 (+ delta (vector-ref new-fish 6)))
new-fish)

(define (population fish)
(for/sum ([f fish]) f))
``````
Part 1
``````(define (part-01 input)
(population (simulation input 80)))
``````
Part 2
``````(define (part-02 input)
(population (simulation input 256)))
``````
Tips

Copy the table of your personal stats and then enjoy them presented as charts.

11. 
Liru
I'm one of those that fell for the trap. In my defense, I hadn't had my coffee yet. Rust solution use std::collections::HashMap; use itertools::Itertools; // for `counts()` type Num = u8; pub fn...

I'm one of those that fell for the trap. In my defense, I hadn't had my coffee yet.

Rust solution
``````use std::collections::HashMap;

use itertools::Itertools; // for `counts()`

type Num = u8;

pub fn lanternfish(input: &str, days: usize) -> usize {
let mut lf: HashMap<Num, usize> = input.split(',').flat_map(str::parse).counts();

for _ in 0..days {
let mut new_lf = HashMap::new();

for (life, count) in lf {
if life == 0 {
*new_lf.entry(6).or_insert(0) += count;
*new_lf.entry(8).or_insert(0) += count;
}
else {
*new_lf.entry(life-1).or_insert(0) += count;
}
}

lf = new_lf;
}

lf.values().sum()
}

pub fn run() -> usize {
lanternfish(&i, 80)
}

pub fn run2() -> usize {
lanternfish(&i, 256)
}
``````

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.

1. 
Eabryt
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...

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?

1 vote
1. 
Liru
That's the only thing I can think of without more detail. Maybe try replacing the let i = std::fs::read_to_string("input/06.txt").unwrap(); lines with let i =...

That's the only thing I can think of without more detail. Maybe try replacing the

``````let i = std::fs::read_to_string("input/06.txt").unwrap();
``````

lines with

``````let i = std::fs::read_to_string("input/06.txt").unwrap().trim();
``````

since yours may have a newline at the end, and that fails the parse call without erroring out.

1 vote
1. Eabryt
Oh yeah, that was it. Thanks. Not sure why there was a newline though, since the file didn't seem to show one.

Oh yeah, that was it. Thanks.

Not sure why there was a newline though, since the file didn't seem to show one.

1 vote
12. 
kari
Hoooo boy, lots of Rust in here today! Well, I'll add my solution. Rust (both days) use crate::lib::aoc; pub fn run6() { let mut fish: [u64; 9] = aoc::get_lines("./inputs/day6.in") .split(",")...

Hoooo boy, lots of Rust in here today! Well, I'll add my solution.

Rust (both days)
`````` use crate::lib::aoc;

pub fn run6() {
let mut fish: [u64; 9] = aoc::get_lines("./inputs/day6.in")
.split(",")
.map(|num| num.parse::<usize>().expect("Unable to read some number"))
.fold([0; 9], |mut fishes, fish| {
fishes[fish] = fishes[fish] + 1;
fishes
});

for _ in 0..80 {
let save = fish;
fish = fish;
fish = fish;
fish = fish;
fish = fish;
fish = fish;
fish = fish;
fish = fish + save;
fish = fish;
fish = save;
}

let sum_p1: u64 = fish.iter().sum();

for _ in 80..256 {
let save = fish;
fish = fish;
fish = fish;
fish = fish;
fish = fish;
fish = fish;
fish = fish;
fish = fish + save;
fish = fish;
fish = save;
}

let sum_p2: u64 = fish.iter().sum();

aoc::big_output(
6,
"number of fish",
sum_p1,
sum_p2,
);
}
``````

I'm pretty proud of today's!

1. 
blitz
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...

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. ;)

1. kari
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...

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

1 vote
13. Crespyl
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...

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
``````def compute_p1(input)
fish = input.split(',').map(&:to_i)

80.times do |i|
fish.append(**fish.count(0))            # add a fish at 8 for each fish at 0
fish = fish.map { _1 == 0 ? 6 : _1 - 1 }   # replace all the 0s with 6s, decrement all other fish
end

return fish.size
end
``````

There's an awkward step in here where I'm adding new fish at `9` instead of `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.

``````def compute_p2(input)
fishmap = [0, 0, 0, 0, 0, 0, 0, 0, 0]
input.split(',').map(&:to_i).each { fishmap[_1] += 1 } # count how many of each stage there is

256.times do |day|
num_reproducing = fishmap.shift
fishmap += num_reproducing
fishmap.append(num_reproducing)
end

fishmap.sum
end
``````
14. primordial-soup
(edited )
I managed to find the trick to get linear runtime, but this morning my housemate realized it can be done in O(log(n)): Python(-ish) f = ls > p | one | X.split(",") | fe(int) | list # there are...

I managed to find the trick to get linear runtime, but this morning my housemate realized it can be done in O(log(n)):

Python(-ish)
``````f = ls > p | one | X.split(",") | fe(int) | list
# there are only 9 possible states that a fish can be in
s = np.c_[[f.count(n) for n in range(9)]]
# use (matrix) exponentiation by squaring to get O(log(n))
M = np.roll(np.diag(np.ones(9, dtype=object)), -1, axis=0)
M[6, 0] = 1
np.sum(np.linalg.matrix_power(M, 256) @ s)
``````

(Ignore the first line; it's just reading input from stdin. My code above actually gets transpiled to

Python
``````from more_itertools import one
from pipetools import X
from pipetools import foreach
from pipetools import pipe
import sys
from pyp import pypprint
p = pipe
fe = foreach
import numpy as np
lines = [x.rstrip('\n') for x in sys.stdin]
ls = lines
f = (ls > ((((p | one) | X.split(',')) | fe(int)) | list))
s = np.c_[[f.count(n) for n in range(9)]]
M = np.roll(np.diag(np.ones(9, dtype=object)), (- 1), axis=0)
M[(6, 0)] = 1
output = np.sum((np.linalg.matrix_power(M, 256) @ s))
if (output is not None):
pypprint(output)
``````
before Python sees it.)

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:

Python(-ish)
``````f = ls > p | one | X.split(",") | fe(int) | list
# there are only 9 possible states that a fish can be in
s = np.c_[[f.count(n) for n in range(9)]]
# use (matrix) exponentiation by squaring to get O(log(n))
M = np.roll(np.diag(np.ones(9, dtype=object)), -1, axis=0)
M[6, 0] = 1
Ma = M.astype("float64")
d = 0
while True:
d += 1
t0 = time.perf_counter()
exact = np.sum(np.linalg.matrix_power(M, d) @ s)
t1 = time.perf_counter()
D, P = np.linalg.eig(Ma)
approx = np.sum(np.real(P @ np.diag(D ** d) @ np.linalg.inv(P) @ s))
t2 = time.perf_counter()
if round(approx) != exact:
print(f"{d=}", f"diff={exact - approx}")
print(f"speedup={(t1 - t0) / (t2 - t1):.2f}x")
break
``````

For my input and laptop this approximation works up to `n = 260`, but rounds the wrong way at 261. The speedup for `n = 261` is 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...

15. jzimbel
(edited )
This one lent itself well to Elixir's Stream module, 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...

This one lent itself well to Elixir's `Stream` module, 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.

Both parts
``````defmodule AdventOfCode.Solution.Year2021.Day06 do
def part1(input) do
input
|> parse_input()
|> get_population_on_day(80)
end

def part2(input) do
input
|> parse_input()
|> get_population_on_day(256)
end

defp parse_input(input) do
input
|> String.trim()
|> String.split(",")
|> Enum.map(&String.to_integer/1)
|> Enum.frequencies()
end

defp get_population_on_day(initial_ages, day) do
initial_ages
|> Stream.iterate(&next_day/1)
|> Enum.at(day)
|> Map.values()
|> Enum.sum()
end

defp next_day(ages) do
ages
|> Enum.flat_map(fn
{0, count} -> [{6, count}, {8, count}]
{n, count} -> [{n - 1, count}]
end)
|> Enum.group_by(fn {age, _} -> age end, fn {_, count} -> count end)
|> Enum.map(fn {age, counts} -> {age, Enum.sum(counts)} end)
|> Enum.into(%{})
end
end
``````
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.

``````iex> parse_input("3,4,3,1,2")
[3, 4, 3, 1, 2]
``````

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/1` in the standard library.

``````iex> parse_input("3,4,3,1,2")
%{3 => 2, 4 => 1, 1 => 1, 2 => 1}
``````
16. Gyrfalcon
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...

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
``````import std/[strformat, sequtils, strutils, tables, hashes, math]

proc parseFile(fileName: string): seq[int] =
var input: seq[string] = split(readLines(fileName, 1), ",")
return mapIt(input, parseInt(it))

var oldFish, newFish: seq[int]
for fish in fishes:
if fish == 0:
else:

return oldFish & newFish

proc main(inputFile: string) =
var fishes = parseFile(inputFile)

for idx in 1 .. 80:

echo &"The number of fish after 80 days is {fishes.len}"

when is_main_module:
main("input.txt")
``````
``````func fastAdvanceDay(fishes: CountTable[int]): CountTable[int] =
var newFishes: CountTable[int]

for (days, num) in pairs(fishes):
if days == 0:
newFishes = newFishes + num
else:
newFishes = num

newFishes = num
newFishes[days - 1] = newFishes[days - 1] + num
else:
newFishes[days - 1] = num

return newFishes

# Try again with something faster
var fastFishes = toCountTable(parseFile(inputFile))

for idx in 1 .. 256:

echo &"The number of fish after 256 days is {sum(toSeq(fastFishes.values()))}"
``````
17. DataWraith
(edited )
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...

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 `3,4,3,1,2` => `[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.

``````population[day + 9] += population[day];
``````

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:

``````population[day + 7] += population[day];
``````

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:

``````// Save the current population
let saved = population[day % 9];

// Clear the current day for reuse
population[day % 9] = 0;

// Spawn new fish
population[(day + 9) % 9] += saved;

// Reinsert parents
population[(day + 7) % 9] += saved;
``````

If you look at it for a bit, we're doing redundant work here because `(day + 9) % 9` equals `day`.

That means we are adding the current `saved` population 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:

``````population[(day + 7) % 9] += population[day % 9];
``````

Summary:

``````fn simulate(population: &mut [usize; 9], days: usize) -> usize {
for day in 0..days {
population[(day + 7) % 9] += population[day % 9];
}

population.iter().sum()
}
``````
18. 
Eabryt
(edited )
Part 1 was pretty easy once I got my question answered. Part I const MAXAGE: u16 = 8; #[derive(Debug)] struct Lanternfish { age: u16, } fn process_fish(mut fishes: Vec<Lanternfish>) ->...

Quick question while working on my solution in Rust.

Part 1 was pretty easy once I got my question answered.

Part I
``````const MAXAGE: u16 = 8;

#[derive(Debug)]
struct Lanternfish {
age: u16,
}

fn process_fish(mut fishes: Vec<Lanternfish>) -> Vec<Lanternfish> {
let mut fish2 = Vec::new();

for mut fish in fishes.iter_mut() {
if fish.age == 0 {
fish.age = 6;
fish2.push(Lanternfish { age: MAXAGE });
} else {
fish.age -= 1;
}
}
fishes.append(&mut fish2);

fishes
}

fn part1(input: &str) {
let ages: Vec<_> = input.split(",").collect();
let mut fishes = Vec::new();

for age in ages {
fishes.push(Lanternfish { age: age.trim().parse::<u16>().unwrap() });
}

for _x in 0..80 {
fishes = process_fish(fishes);
}
println!("{}",fishes.len());

}

fn main() {
part1(include_str!("input.txt"));
}
``````

I knew what was going to happen when I ran Part II, but I decided to break things anyway.

1. 
blitz
Can you share the full source? There’s not enough here for me to help you out.

Can you share the full source? There’s not enough here for me to help you out.

1. 
Eabryt
Sure, didn't want to overload too much. Full code so far const MAXAGE: u16 = 8; #[derive(Debug)] struct Lanternfish { age: u16, } fn process_fish(f: Vec<Lanternfish>) { println!("{:?}",f); } fn...

Sure, didn't want to overload too much.

Full code so far
``````const MAXAGE: u16 = 8;

#[derive(Debug)]
struct Lanternfish {
age: u16,
}

fn process_fish(f: Vec<Lanternfish>) {
println!("{:?}",f);
}

fn print_type_of<T>(_: &T) {
println!("{}", std::any::type_name::<T>())
}

fn part1(input: &str) {
let ages: Vec<_> = input.split(",").collect();
let mut fishes = Vec::new();

for age in ages {
fishes.push(Lanternfish { age: age.trim().parse::<u16>().unwrap() });
}

for x in 0..80 {
print_type_of(&fishes);
fishes = process_fish(fishes);
}

}

fn main() {
part1(include_str!("test.txt"));
}
``````
1. 
Liru
Your process_fish function doesn't have a return type.

Your `process_fish` function doesn't have a return type.

1 vote
1. Eabryt
Oh, duh. I knew it didn't have one yet, but didn't think about it since the error code didn't seem related. Cheers!

Oh, duh. I knew it didn't have one yet, but didn't think about it since the error code didn't seem related.

Cheers!

19. DataWraith
(edited )
Day 06 (Rust) Today I'm trying something new: Entangled, a literate programming tool. Literate programming Normally, programs are interspersed with comments to explain what is going on. Literate...

# Day 06 (Rust)

Today I'm trying something new: Entangled, a literate programming tool.

## Literate programming

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.

Simulation Since 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.

``````type LanternfishPopulation = [usize; 10];

pop += pop;
pop += pop;

for i in 0..9 {
pop[i] = pop[i + 1];
}

pop = 0;
}
``````
Parsing

Parsing is simple today: the input is a single line with comma-separated numbers.

``````fn parse(input: &str) -> LanternfishPopulation {
let mut population = [0; 10];

for fish in input.trim().split(',').map(|n| n.parse::<usize>().unwrap()) {
population[fish] += 1;
}

population
}
``````
Solution

We simply tick the simulation 80 times.

``````fn iterate(population: &mut LanternfishPopulation, rounds: usize) -> usize {
for i in 0..rounds {
}

let mut sum = 0;

for i in 0..9 {
sum += population[i] as usize;
}

sum.into()
}
``````

Part B is trivial today, we just have to tick the simulation 256 times.

``````fn main() {
let input = parse(include_str!("../../input-06.txt"));
println!("Part I:  {}", iterate(&mut input.clone(), 80));
println!("Part II: {}", iterate(&mut input.clone(), 256));
}
``````
Tests
``````#[cfg(test)]
mod test {
use super::*;

#[test]
fn it_solves_the_examples() {
let input = parse("3,4,3,1,2");
assert_eq!(iterate(&mut input.clone(), 18), 26);
assert_eq!(iterate(&mut input.clone(), 80), 5934);
assert_eq!(iterate(&mut input.clone(), 256), 26984457539);
}
}
``````
Thought process
• Ugh, a variable-length list
• Maybe I can sort it to be more efficient?
• Hm, it has few distinct values; let's use counting sort
• Wait, it doesn't need to be sorted at all, just rotated left

Edit:

Alternative implementation

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:

``````#[memoize]
fn num_fishes(timer: usize, days: usize) -> usize {
if days == 0 {
return 1;
}

if timer == 0 {
return num_fishes(6, days - 1) + num_fishes(8, days - 1);
}

num_fishes(timer - 1, days - 1)
}
``````
20. wycy
Rust Rust use std::env; use std::io::{self}; const INITIAL_SPAWN_DAYS: usize = 8; const RESPAWN_DAYS: usize = 6; const DAYS_P1: usize = 80; const DAYS_P2: usize = 256; fn day06(input: &str) ->...

Rust

Rust
``````use std::env;
use std::io::{self};
const INITIAL_SPAWN_DAYS: usize = 8;
const RESPAWN_DAYS: usize = 6;
const DAYS_P1: usize = 80;
const DAYS_P2: usize = 256;
fn day06(input: &str) -> io::Result<()> {
// Input
let input_str = input_str.trim();
let fishes: Vec<_> = input_str.split(',').map(|x| x.parse::<isize>().unwrap()).collect();
// Initialize
let mut num_fishes = fishes.len() as isize;
let mut spawns = vec![0; INITIAL_SPAWN_DAYS+1]; // index is number of days away
for fish in fishes {
spawns[fish as usize] += 1;
}
// Run
for day in 0..DAYS_P2 {
if day == DAYS_P1 { println!("Part 1: {}", num_fishes); } // 351188
let new_fish = spawns;
num_fishes += new_fish;
spawns.rotate_left(1);
spawns[INITIAL_SPAWN_DAYS] = new_fish;
spawns[RESPAWN_DAYS] += new_fish;
}
println!("Part 2: {}", num_fishes); // 1595779846729
Ok(())
}
fn main() {
let args: Vec<String> = env::args().collect();
let filename = &args;
day06(&filename).unwrap();
}
``````
21. asterisk
(edited )
``````fishes = [list(map(int, open("input.txt").readline().split(","))).count(i) for i in range(9)]