14 votes

Day 6: Lanternfish

Today's problem description: https://adventofcode.com/2021/day/6

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
Your code here.
```

</details>

35 comments

  1. tjf
    (edited )
    Link
    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[0]+F[7],F[8],F[0]]
    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[0]+F[7],F[8],F[0]]
    print(sum(F))
    

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

    8 votes
  2. [2]
    PapaNachos
    Link
    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([0])*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([0])*9
        for i in range(0,8):
            new_fish_count[i] = fish_count[i+1]
        new_fish_count[6] = new_fish_count[6] + fish_count[0]
        new_fish_count[8] = fish_count[0]
        #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([0])*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([0])*9
        for i in range(0,8):
            new_fish_count[i] = fish_count[i+1]
        new_fish_count[6] = new_fish_count[6] + fish_count[0]
        new_fish_count[8] = fish_count[0]
        #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

    5 votes
    1. nothis
      Link Parent
      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 votes
  3. [6]
    spit-evil-olive-tips
    Link
    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[8] = count
                    new_population[6] += 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.

    5 votes
    1. [5]
      cfabbro
      (edited )
      Link Parent
      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

      3 votes
      1. [2]
        Liru
        Link Parent
        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.

        3 votes
        1. Ephemere
          Link Parent
          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 votes
      2. [2]
        blitz
        Link Parent
        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 chars in C or u8s in Rust you could probably get that cost down to just $69,763!

        2 votes
        1. Liru
          (edited )
          Link Parent
          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.

          2 votes
  4. blitz
    Link
    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

    4 votes
  5. Crestwave
    (edited )
    Link
    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[8] += fish[i]
    				state[6] += 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
    }
    
    4 votes
  6. petrichor
    Link
    Python def spawn(days): age = [0]*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[7] += age[0] age[9] += age[0] age[0] -= age[0]...
    Python
    def spawn(days):
        age = [0]*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[7] += age[0]
                    age[9] += age[0]
                    age[0] -= age[0]
                else:
                    age[i-1] += age[i]
                    age[i]   -= age[i]
        return sum(age)
    
    4 votes
  7. 3d12
    Link
    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');
    const readline = require('readline');
    
    let inputArr = [];
    
    async function openFileForReading(file) {
    	const fileStream = fs.createReadStream(file);
    
    	const rl = readline.createInterface({
    		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() {
    	await openFileForReading('input.txt');
    	let lanternFishArray = inputArr[0].split(',').map(e => parseInt(e));
    	let days = 0;
    	let totalFish = 0;
    	while (true) {
    		lanternFishArray = processDay(lanternFishArray);
    		days++;
    		if (days === 80) {
    			totalFish = lanternFishArray.length;
    			break;
    		}
    	}
    	console.log("Answer found! " + totalFish);
    })();
    
    Part 2
    const fs = require('fs');
    const readline = require('readline');
    
    let inputArr = [];
    
    async function openFileForReading(file) {
    	const fileStream = fs.createReadStream(file);
    
    	const rl = readline.createInterface({
    		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() {
    	await openFileForReading('input.txt');
    	let lanternFishArray = serializeArray(inputArr[0].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;
    		}
    	}
    	console.log("Answer found! " + totalFish);
    })();
    
    4 votes
  8. pnutzh4x0r
    Link
    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[0] + old_table[RESET_DAY + 1];
        births   = old_table[0];
        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.readline(line => line.split(',')).forEach(number => fish_table[parseInt(number)]++);
    
    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)}`);
    
    4 votes
  9. bhrgunatha
    (edited )
    Link
    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.

    3 votes
  10. [4]
    Liru
    Link
    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 {
        let i = std::fs::read_to_string("input/06.txt").unwrap();
        lanternfish(&i, 80)
    }
    
    pub fn run2() -> usize {
        let i = std::fs::read_to_string("input/06.txt").unwrap();
        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.

    3 votes
    1. [3]
      Eabryt
      Link Parent
      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. [2]
        Liru
        Link Parent
        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
          Link Parent
          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
  11. [3]
    kari
    Link
    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")[0] .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")[0]
            .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[0];
            fish[0] = fish[1];
            fish[1] = fish[2];
            fish[2] = fish[3];
            fish[3] = fish[4];
            fish[4] = fish[5];
            fish[5] = fish[6];
            fish[6] = fish[7] + save;
            fish[7] = fish[8];
            fish[8] = save;
        }
    
        let sum_p1: u64 = fish.iter().sum();
    
        for _ in 80..256 {
            let save = fish[0];
            fish[0] = fish[1];
            fish[1] = fish[2];
            fish[2] = fish[3];
            fish[3] = fish[4];
            fish[4] = fish[5];
            fish[5] = fish[6];
            fish[6] = fish[7] + save;
            fish[7] = fish[8];
            fish[8] = 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!

    3 votes
    1. [2]
      blitz
      Link Parent
      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. ;)

      3 votes
      1. kari
        Link Parent
        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
  12. Crespyl
    Link
    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(*[9]*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[6] += num_reproducing
        fishmap.append(num_reproducing)
      end
    
      fishmap.sum
    end
    
    3 votes
  13. primordial-soup
    (edited )
    Link
    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...

    3 votes
  14. jzimbel
    (edited )
    Link
    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}
    
    3 votes
  15. Gyrfalcon
    Link
    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)[0], ",")
      return mapIt(input, parseInt(it))
    
    func advanceDay(fishes: seq[int]): seq[int] =
      var oldFish, newFish: seq[int]
      for fish in fishes:
        if fish == 0:
          oldFish.add(6)
          newFish.add(8)
        else:
          oldFish.add(fish - 1)
    
      return oldFish & newFish
    
    proc main(inputFile: string) =
      var fishes = parseFile(inputFile)
    
      for idx in 1 .. 80:
        fishes = advanceDay(fishes)
    
      echo &"The number of fish after 80 days is {fishes.len}"
    
    when is_main_module:
      main("input.txt")
    
    Nim Part 2 Additions
    func fastAdvanceDay(fishes: CountTable[int]): CountTable[int] =
      var newFishes: CountTable[int]
    
      for (days, num) in pairs(fishes):
        if days == 0:
          if hasKey(newFishes, 6):
            newFishes[6] = newFishes[6] + num
          else:
            newFishes[6] = num
    
          newFishes[8] = num
        elif hasKey(newFishes, days - 1):
          newFishes[days - 1] = newFishes[days - 1] + num
        else:
          newFishes[days - 1] = num
    
      return newFishes
    
    ## Added to main
    # Try again with something faster
      var fastFishes = toCountTable(parseFile(inputFile))
    
      for idx in 1 .. 256:
        fastFishes = fastAdvanceDay(fastFishes)
    
      echo &"The number of fish after 256 days is {sum(toSeq(fastFishes.values()))}"
    
    3 votes
  16. DataWraith
    (edited )
    Link
    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()
    }
    
    3 votes
  17. [5]
    Eabryt
    (edited )
    Link
    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.

    2 votes
    1. [4]
      blitz
      Link Parent
      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. [3]
        Eabryt
        Link Parent
        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. [2]
          Liru
          Link Parent
          Your process_fish function doesn't have a return type.

          Your process_fish function doesn't have a return type.

          1 vote
          1. Eabryt
            Link Parent
            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!

  18. DataWraith
    (edited )
    Link
    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];
    
    fn advance(pop: &mut LanternfishPopulation) {
        pop[7] += pop[0];
        pop[9] += pop[0];
    
        for i in 0..9 {
            pop[i] = pop[i + 1];
        }
    
        pop[9] = 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 {
            advance(population);
        }
    
        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)
    }
    
    2 votes
  19. wycy
    Link
    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 = std::fs::read_to_string(input).unwrap();
        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[0];
            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[1];
        day06(&filename).unwrap();
    }
    
    2 votes
  20. asterisk
    (edited )
    Link
    Python fishes = [list(map(int, open("input.txt").readline().split(","))).count(i) for i in range(9)] for _ in range(256): # For Part One: 80 fishes = fishes[1:7] + [fishes[0] + fishes[7],...
    Python
    fishes = [list(map(int, open("input.txt").readline().split(","))).count(i) for i in range(9)]
    
    for _ in range(256):  # For Part One: 80
        fishes = fishes[1:7] + [fishes[0] + fishes[7], fishes[8], fishes[0]]
    
    print("Answer:", sum(fishes))
    

    I fell in this bait, so I after the first task I redid almost all.

    2 votes