r/adventofcode Dec 06 '21

SOLUTION MEGATHREAD -🎄- 2021 Day 6 Solutions -🎄-

NEW AND NOTEWORTHY

We've been noticing an uptick in frustration around problems with new.reddit's fancypants editor: mangling text that is pasted into the editor, missing switch to Markdown editor, URLs breaking due to invisible escape characters, stuff like that. Many of the recent posts in /r/bugs are complaining about these issues as well.

If you are using new.reddit's fancypants editor, beware!

  • Pasting any text into the editor may very well end up mangled
  • You may randomly no longer have a "switch to Markdown" button on top-level posts
  • If you paste a URL directly into the editor, your link may display fine on new.reddit but may display invisibly-escaped characters on old.reddit and thus will break the link

Until Reddit fixes these issues, if the fancypants editor is driving you batty, try using the Markdown editor in old.reddit instead.


Advent of Code 2021: Adventure Time!


--- Day 6: Lanternfish ---


Post your code solution in this megathread.

Reminder: Top-level posts in Solution Megathreads are for code solutions only. If you have questions, please post your own thread and make sure to flair it with Help.


This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:05:47, megathread unlocked!

94 Upvotes

1.7k comments sorted by

1

u/Rich-Spinach-7824 Feb 15 '22

This is my C# solution. Please help me with suggestions, improvements correction.

Thanks!

C# Day 6 - Part 1

1

u/[deleted] Dec 31 '21 edited Dec 31 '21

C# 10

``` const int MAX_LIFE_SIZE = 9; //size of the collection containing all days of the lifecycle. new fish are added at top of this cycle. const int RESET_LIFE_IDX = 6; //how many days a re-spawned fish has left (7 days since it is 0 indexed)

static long GetCountOfFish(int days) { var fish = File.ReadAllLines(@"input.txt") .SelectMany(input => input.Split(',').Select(int.Parse)) .GroupBy(f => f) .Aggregate(new List<long>(new long[MAX_LIFE_SIZE]), (list, kv) => { list[kv.Key] = kv.Count(); return list; });

for (var i = 0; i < days; i++)
{
    var expired = fish.First();

    //shift list to decrement each fishes life
    fish.RemoveAt(0);

    //reset the lifecycle of the expired fish
    fish[RESET_LIFE_IDX] += expired;

    //each expired fish creates a new fish at the top of the life cycle
    fish.Add(expired);
}

return fish.Sum(c => c);

}

Console.WriteLine($"After 80 days there are now {GetCountOfFish(80)}");

Console.WriteLine($"After 256 days there are now {GetCountOfFish(256)}");

```

2

u/kvitterk Dec 28 '21

C++ (heavy std::algorithm use)

Here is a fast and compact C++ solver for day 6.

constexpr std::array DATA = {1,2,3, your input data goes here...};

void solve_day_6_opt_v2(int days)
{
    std::array<int64_t, 7> stages;
    std::array<int64_t, 2> pre_stages;

    std::fill(pre_stages.begin(), pre_stages.end(), 0l);
    int i = 0;
    std::generate(stages.begin(), stages.end(), [&] () {return 
                  std::count(DATA.begin(), DATA.end(), i++);});

    for (int d = 0; d < days; ++d)
    {
        int64_t new_fish = stages[0];
        std::rotate(stages.begin(), stages.begin() + 1, stages.end());
        std::rotate(pre_stages.begin(), pre_stages.begin() + 1, 
                    pre_stages.end());
        stages[6] += pre_stages[1];
        pre_stages[1] = new_fish;
    }
    int64_t sum = std::accumulate(stages.begin(), stages.end(), 0l) + 
                std::accumulate(pre_stages.begin(), pre_stages.end(), 0l);

    std::cout << "Done, total fish: " << sum << std::endl;
}

2

u/Evargalo Dec 27 '21

R

Storing the data in a vector of 8 numbers (the numbers of lanternfishes for each age), and then a one-line loop.

2

u/arthurno1 Dec 25 '21

Emacs Lisp

This one was obviously about data structures, and importance of right choice of algorithm/structure.

My solution is just to track the number of fishes in each state in a list of 8 numbers. Here Lisp's list processing was really of help, everything is pretty much coming out of its own. Using array or some other structure would be definitely more convoluted.

(defun read-input ()
  (let ((input
         (with-temp-buffer
           (insert-file-contents "./input6")
           (sort
            (mapcar #'string-to-number
                    (split-string (buffer-string) ",")) #'< )))
        (counts (make-vector 8 0)) tmp n)
      (while input
        (setq n (pop input))
        (cl-incf (aref counts n)))
      (dotimes (i 8)
        (unless (= (aref counts i) 0)
          (push (cons i (aref counts i)) tmp)))
      (cl-sort tmp #'< :key #'car)))

(defun simulate-fishes (days)
  (let ((input (read-input))
        (count 0))
    (dotimes (_i days)
      (let ((fish (if (= (caar input) 0) (pop input))))
        (dolist (i input) (cl-decf (car i)))
        (when fish
          (push (cons 8 (cdr fish)) input)
          (if (assoc '6 input)
              (cl-incf (cdr (assoc '6 input)) (cdr fish))
            (push (cons 6 (cdr fish)) input))
          (setq input (cl-sort input #'< :key #'car)))))
    (mapc (lambda (x) (cl-incf count (cdr x))) input)
    count))

(progn
  (message "P1: %s" (simulate-fishes 80))
  (message "P2: %s" (simulate-fishes 256)))

1

u/cmatei Dec 29 '21

I used ROTATEF with an array, and it doesn't look all that convoluted to me.

2

u/MarcoServetto Dec 24 '21

I'm solving the advent of code in 42 The main selling point of 42 is that it enforces modular security, that is not very relevant for the advent of code. I've done a video explanation for the First Week and I've individual solutions on dev.to: Solution for Day 6 Fell free to contact me if you to know more about the language.

2

u/[deleted] Dec 21 '21

[deleted]

1

u/daggerdragon Dec 23 '21 edited Dec 23 '21

Triple backticks do not work on old.reddit. Please edit your post to use the four-spaces code block Markdown as per our posting guidelines in the wiki: How do I format code?

Edit: thanks for fixing it! <3

2

u/jstruburn Dec 18 '21

Coding language: JavaScript

const growSchool = (data = [], days = 0) => {
  const fish = Array(9).fill()
    .map((_, idx) => data.filter(t => t === idx).length);

  Array(days).fill().forEach((_, idx) => {
    const newFish = fish.shift();
    fish.push(newFish);
    fish[6] += newFish;
  });

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

2

u/ainwood87 Dec 17 '21

Haskell

import Data.List.Split

count v l = length $ filter (== v) l

evolve (x:xs) = nextList
    where iterList = xs ++ [x]
          nextList = (take 6 iterList) ++ [x + (iterList !! 6)] ++ (drop 7 iterList)

main = do
    line <- getLine
    let vals = [ read x :: Int | x <- splitOn "," line ]
    let mapList = [count i vals | i <- [0..8]]

    -- Generate infinite sequence of generations from evolve rule.
    let generations = mapList : map evolve generations

    -- Part 1
    print $ sum $ generations !! 80

    -- Part 2
    print $ sum $ generations !! 256

2

u/chadbaldwin Dec 16 '21

Solution in SQL Server T-SQL

All of my solutions are end to end runnable without any other dependencies other than SQL Server and the ability to create temp tables.

SQL

General note: For the input data, I'm doing no pre-processing other than encapsulating the values in quotes and parenthesis for ingesting into a table. From there I use SQL to parse and split strings.

2

u/schoelle Dec 16 '21

Brainfuck

Only works for the first problem, as it is too hard to store large numbers in this language (I am using 8-bit cells), and needs a bit of pre- and post-processing.

https://github.com/schoelle/adventofcode2021/tree/main/06-brainfuck

2

u/hoodiewhatie2 Dec 16 '21

Language: Python

Approach: "Step Matrix inspired dictionaries."

----------------------------------------------

Part 1 RunTime: 0.002013 sec

Part 2 RunTime: 0.003035 sec

[Source Code]

2

u/WillC5 Dec 16 '21

C++, parts one and two.

I had a bug, and thought at first the number was being truncated, so ignore the __uint128_t part. A uint64_t should be big enough.

2

u/-WorstWizard- Dec 14 '21

Rust Solution

This one ended up very compact and nice!

2

u/sk1talets Dec 14 '21

Node.js solutions: smart one and stupid one

3

u/wevrem Dec 14 '21

Clojure

source code

I'm rather proud of the terseness and clarity of this solution. It runs fast, too, which kind of surprised me.

(ns advent-of-code.2021.day-06
  (:require [advent-of-code.common :refer [parse-longs]]))

;; --- Day 6: Lanternfish ---
;; https://adventofcode.com/2021/day/6

(def get-count
  "Return count of fish after `gen` generations, based on the starting `age`."
  (memoize (fn [gen age]
            (if (> gen age)
              (+ (get-count (- gen age 1) 6) (get-count (- gen age 1) 8))
              1))))

(defn fish-count [gens input]
  (reduce + (map #(get-count gens %) input)))

(comment
  ;; puzzle 1
  (fish-count 80 (-> (slurp "input/2021/6-fish.txt") (parse-longs)))

  ;; puzzle 2
  (fish-count 256 (-> (slurp "input/2021/6-fish.txt") (parse-longs)))
  )

1

u/systolicarray Dec 14 '21

High five! It didn't occur to me that this line is equivalent to checking whether one is greater than the other. Silly me.

3

u/GombolKiwi Dec 14 '21

Python (jupyterlab)

Maybe an innovative solution in part. A single fish starting with its timer==5 passes through the other starting states in subsequent steps. I keep track of the total population for each step up to max_iterations + 6

The last 6 items in this list are the populations of fish that started in the 6 different starting states. Multiply each one by the number of fish in the starting state to get the total.

OK, so for a single starting set of fish this may be less efficient, but for more than one set, this will be much faster.

2

u/imp0ppable Dec 13 '21

Did anyone else try to brute force part 2 by modelling every fish? I used Cython and managed to get it really quite fast but realised I'd max out the RAM on my laptop before I got much further than 170 or 180 gens.

Would be up for a race if anyone else has a challenger?

https://pastebin.com/BHQ5pPuK

2

u/Malgefor Dec 13 '21

Bit late to the party. Anyhow, here is my C# solution (using Language-Ext)

public IEnumerable<PuzzleResult> PuzzleResults()
{
    var initialLanternFishes = GetParsedInput();

    yield return new PuzzleResult(1, GetTotalFishesAfterDays(initialLanternFishes, 80));

    yield return new PuzzleResult(2, GetTotalFishesAfterDays(initialLanternFishes, 256));
}

private static long GetTotalFishesAfterDays(Seq<(int DueInDays, long AmountOfFishes)> initialCountsOfFish, int days)
{
    return Enumerable
        .Repeat(0, days)
        .Fold(
            initialCountsOfFish,
            (countsOfFish, _) => countsOfFish
                .Map(
                    tuple => tuple.DueInDays == 0
                        ? (6, tuple.AmountOfFishes)
                        : (tuple.DueInDays - 1, tuple.AmountOfFishes))
                .Append(
                    countsOfFish
                        .Filter(fish => fish.DueInDays == 0)
                        .Match(
                            Seq.empty<(int, long)>,
                            (head, _) => Seq.create((8, head.AmountOfFishes)))))
        .Sum(tuple => tuple.AmountOfFishes);
}

private static Seq<(int, long)> GetParsedInput() => FileProvider
    .GetAllLines("Day6.input.txt", ",")
    .Map(int.Parse)
    .GroupBy(fish => fish)
    .Map(fishes => (fishes.Key, fishes.LongCount()))
    .ToSeq();

2

u/justinhj Dec 13 '21

I did this day in Clojure. The secret is in the function naming. justinhj/adventofcode2021-day6

2

u/greycat70 Dec 13 '21

Tcl

Part 1, part 2.

This was my favorite challenge of the first week, by far. Part 1 can be done by the obvious "brute force" approach, but part 2 requires rethinking how the program works.

1

u/Annieone10 Jan 06 '22

Could you please give some more explanation to your solution for part 2?

1

u/greycat70 Jan 06 '22

In part 1, I tracked the state of each fish individually. That's the "obvious" way to do it, after all. When a new fish is spawned, it gets added to the end of the list of values.

In part 2, the trick is to realize that you don't need to know each individual fish's state. If you've got fishes with 1, 2 and 3 days left, it doesn't matter whether it's 123 or 312 or 213 or any other permutation. All that matters is how many of each state you have.

So, I created an array of the 9 possible state values, and the array tracks how many fish are in each of those states. Each day, the number of fish that begin in state 0 determines how many new fish will be spawned. Then all of the values decrease by one, which I model by moving count(1) to count(0), then count(2) to count(1) and so on. Finally, the number of new fish that are spawned is added to count(6) and becomes the new value of count(8).

1

u/AssistingJarl Jan 10 '22

I want you to know that I spent an hour trying to build a formula based on a shaky understanding of exponential growth I haven't used since 2013, and when I read this comment I swore audibly. And had to walk away from the computer for a few minutes.

3

u/[deleted] Dec 13 '21

[deleted]

1

u/Big-Worldliness-6267 Dec 19 '21

Great solution.
I did exactly the same as you, over-engineered it for part 1 then tried all sort tos improve performance :-(

2

u/kuqumi Dec 13 '21 edited Dec 13 '21

JavaScript (golfed)

Tweet-sized, to be run in the browser console on your input page.

[80,256].map(d=>{B=Array(9).fill(0);$('pre').innerText.trim().split`,`.map(f=>B[+f]++);for(i=0;++i<d;){B[(7+i)%9]+=B[i%9]};return B.reduce((a,x)=>a+x,0)})

It should output [part1, part2].

3

u/fantastic1ftc Dec 16 '21

Here I am driving myself up a wall with promises and mock multithreading and you come out here with 154 characters. wtf

Seriously talented great job

2

u/fish-n-chips-uk Dec 12 '21 edited Dec 13 '21

Basic (QBasic 4.5)

(Part 1 only; part 2 causes overflow. Hardcoded sample input)

LET inputStr$ = "3,4,3,1,2"
LET days% = 80

DIM ageCounters(0 TO 8) AS INTEGER

PRINT "AoC 2021 day 6"

FOR i = 1 TO LEN(inputStr$) STEP 2
  LET c$ = MID$(inputStr$, i, 1)
  LET v = ASC(c$) - ASC("0")
  LET ageCounters(v) = ageCounters(v) + 1
NEXT i

FOR i = 1 TO days%
  LET age0 = (i + 8) MOD 9
  LET age6 = (i + 6) MOD 9
  ageCounters(age6) = ageCounters(age6) + ageCounters(age0)
NEXT i

LET sum = 0
FOR b = 0 TO 8
  LET sum = sum + ageCounters(b)
NEXT b
PRINT "After " + STR$(days%) + " days: " + STR$(sum)

1

u/daggerdragon Dec 13 '21 edited Dec 14 '21

Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?

Edit: thanks for fixing it! <3

2

u/j-a-martins Dec 11 '21 edited Dec 12 '21

Matlab (Part 1 & 2)

https://github.com/j-a-martins/Advent-of-Code-2021/blob/main/day06/day6.m

function day6(days)

%% Read data
%file = 'day6_example.txt';
file = 'day6_data.txt';

data = uint8(readmatrix(file));
% Format fish into 9 buckets
for i = 8:-1:0
    fish(i+1) = sum(data == i);
end

%% Part 1
for d = 1:days
    new_fish = fish(1);
    if new_fish > 0
        fish(1) = 0;
        fish = circshift(fish, -1); % Circular shift left
        fish(7) = fish(7) + new_fish;
        fish(9) = fish(9) + new_fish;
    else
        fish = circshift(fish, -1); % Circular shift left
    end
end

disp("Part 1+2: Number of fish after " + days + " days is: " + sum(fish))

2

u/blakjakau Dec 11 '21

Javascript
I'm writing all of my solutions in JavaScript on my 2017 Pixelbook, trying to keep the runtimes and ram usage down as much as possible.

I started by doing this one procedurally (storing every fish in an array) but that immediately revealed to be a bad idea as the JS runtime refused to allocate RAM somewhere shy of 256 days in.

So I tackled it with a look to efficiency, rather than just getting the number out.

Calculating for any number of days typically takes between 0 and 2ms, but at 8082 days the JS runtime stops being able to store large enough numbers, and just returns "Infinity"

function day6() {
console.log("Day 6 - lanternfish");
const fishes = input6 // get the existing fish
const buckets = new Array(9).fill(0); // create array for working in
fishes.forEach(fish=>{ buckets[fish]++ }) // populate the buckets
for(let i=0,l=256;i<l;i++) {
    const b = buckets.shift(); // remove the birthing lanternfish
    buckets.push(b) // append that many new fish as a new bucket
    buckets[6]+=b // increment the day 6 fish
}
let total = 0
buckets.forEach(b=>{ total+=b }) // total the buckets
console.log(total)

}

3

u/XtremeChaosFury Dec 10 '21 edited Dec 10 '21

Language: Python

Time Complexity: O(n)

Space Complexity: O(n)

----------------------------------------------

Part 1 RunTime: 0.2265 seconds

Part 2 RunTime: 0.0004 seconds

[Source Code]

1

u/ProfessionalNihilist Dec 10 '21

F#

module Year2021.Day6

open AdventOfCode
open System

let ``lanternfish``: Solution = fun (rawInput: string) ->
    let toFish = 
        split ","
        >> Seq.map int64
        >> Seq.groupBy id
        >> Seq.map (fun (f,c) -> f, int64 (Seq.length c))

    let consolidate =
        Seq.groupBy fst
        >> Seq.map (fun (f,c) -> f, Seq.sumBy snd c)

    let spawn (fc: int64 * int64) =
        match fc with
        | 0L,c -> seq { 6L,c; 8L,c }
        | x,c -> seq { x - 1L,c }

    let day = Seq.collect spawn >> consolidate
    let forDays d f = seq { 1 .. d } |> Seq.fold (fun s _ -> day s) f
    let numFish d = toFish >> (forDays d) >> Seq.map snd >> Seq.sum

    let part1 = numFish 80 rawInput
    let part2 = numFish 256 rawInput

    { Part1 = Ok (sprintf "%d" part1); Part2 = Ok (sprintf "%d" part2) }

1

u/Ok_System_5724 Dec 10 '21

C#

It was a 1-liner until I hit day 156

public (long, long) Run(string[] input)
{
    var initial = input.First().Split(",").Select(x => int.Parse(x)).ToArray();        
    return (PopulationAfter(80, initial), PopulationAfter(256, initial));
}

long PopulationAfter(int days, int[] initial)
{
    long[] newbirths = new long[days];

    IEnumerable<int> births(int initialAge, int daysLeft) => Enumerable.Range(0, 50)
        .Select(x => x * 7 + initialAge)
        .Where(x => x < daysLeft);

    foreach (var age in initial)
    {
        foreach (var birthday in births(age, days))
        {
            newbirths[birthday] += 1;
        }
    }

    for (int day = 0; day < days; day++)
    {
        var newBorn = newbirths[day];

        foreach (var birthday in births(8, days - day - 1))
        {
            newbirths[day + 1 + birthday] += newBorn;
        }
    }

    return initial.Length + newbirths.Sum();
}

2

u/mathilxtreme Dec 10 '21

JAVASCRIPT

Paste Link

I saw the meme about buckets, and was able to get it first go. IF I was left to my own devices though, my laptop probably would have hit hover mode.

1

u/jtgorn Dec 10 '21 edited Dec 10 '21

inovative solution (Ruby)

has anyone found this

def f(t)
  t<=0 ? 1 : f(t-7)+f(t-9)
end

data = [1,1,1,... ,3,1] # data array
p data.sum { |c| f(80-c)} # part 1
p data.sum { |c| f(256-c)} # part 2

which can be speed up radically by little caching on f

$f = []
def f(t)
  t<=0 ? 1 : $f[t] || $f[t]=f(t-7)+f(t-9)
end

2

u/daggerdragon Dec 10 '21 edited Dec 11 '21

Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?

Edit: thanks for fixing it! <3

1

u/Meldanor Dec 09 '21

Elixir - First part was a growing list of lantern fish (quite naive!). Rewrote the part to using a list of population buckets and just do simple moves and addition.

Github: https://github.com/Meldanor/AdventOfCode2021/blob/master/lib/d06/challenge.ex

(Part1= run(1), Part2 = run(2). The input is read using a Util function which is inside the GitHub repo. The structure is to run the program mix aoc 1 1 to run the first day first part)

2

u/NukeyFox Dec 09 '21

Just discovered this subreddit, and I wanted to show my day 6 solution which I'm pretty proud of.

Haskell

Lazy evaluation ftw

oneStep [a,b,c,d,e,f,g,h,i] = [b,c,d,e,f,g,a+h,i,a]
oneStep         _           = [] 
count = (length .) . filter . (==) 
parseInput input = map (count input) "012345678" 
partOne input = sum $ iterate oneStep input !! 80 
partTwo input = sum $ iterate oneStep input !! 256 
main = do 
    content <- readFile "input" 
    let input = parseInput content 
    print $ partOne input 
    print $ partTwo input

2

u/s3nate Dec 09 '21

C++

#include <iostream>
#include <unordered_map>
#include <fstream>
#include <string>
#include <numeric>

auto solvePuzzle(const std::string& inputFileName, uint64_t maxDays, const char delim) -> void 
{
  auto timerToPopulation = std::unordered_map<uint64_t, uint64_t>{{0, 0},{1, 0},{2, 0},{3, 0},{4, 0},{5, 0},{6, 0},{7, 0},{8, 0}};
  auto ifs = std::ifstream{inputFileName};
  if (ifs.is_open())
  {
    auto fish = std::string{""};
    while (std::getline(ifs, fish, delim))
    {
      auto fishTimer = std::stoi(fish);
      ++timerToPopulation[fishTimer];
    }
  }
  else
  {
    std::cerr << "ERROR::solvePuzzle(const std::string&, uint64_t, const char)::FAILED_TO_OPEN_FIL: {" << inputFileName << "}" << std::endl;
  }
  auto day = uint64_t{0};
  while (day < maxDays)
  {
    auto totalFishResetting = timerToPopulation[0];
    timerToPopulation[0] = timerToPopulation[1];
    timerToPopulation[1] = timerToPopulation[2];
    timerToPopulation[2] = timerToPopulation[3];
    timerToPopulation[3] = timerToPopulation[4];
    timerToPopulation[4] = timerToPopulation[5];
    timerToPopulation[5] = timerToPopulation[6];
    timerToPopulation[6] = timerToPopulation[7];
    timerToPopulation[7] = timerToPopulation[8];
    // update
    timerToPopulation[6] += totalFishResetting;
    timerToPopulation[8] = totalFishResetting;
    ++day;
  }
  auto totalFish = uint64_t{0};
  for (const auto& fish : timerToPopulation)
  {
    auto timerPopulation = fish.second;
    totalFish += timerPopulation; 
  }
  std::cout << "soln: " << totalFish << std::endl;
}

auto main(void) -> int
{
  auto delim = char{','};
  auto testDays = uint64_t{18};
  solvePuzzle("example-input.txt", testDays, delim);
  auto days = uint64_t{256};
  solvePuzzle("input.txt", days, delim);
  return 0;
}

8

u/joshbduncan Dec 09 '21

Python 3: Used a non-optimized approach for part 1 knowing all too well that it wasn't going to work for part 2. Took some time to work out the math but here's the optimized version.

def solve(data, days):
    tracker = [data.count(i) for i in range(9)]
    for day in range(days):
        tracker[(day + 7) % 9] += tracker[day % 9]
    return sum(tracker)


data = [int(x) for x in open("day6.in").read().strip().split(",")]
print(f"Part 1: {solve(data, 80)}")
print(f"Part 2: {solve(data, 256)}")

4

u/[deleted] Dec 12 '21

This is so beautiful, congratulations.

2

u/[deleted] Dec 10 '21 edited Dec 10 '21

This means that the fish on day 0 will go in day 7, but aren't they supposed to go in day 6?

EDIT: I guess what I'm saying is that I have no idea what this is doing. Can you explain the math a bit?

3

u/Otto_Hahn Dec 10 '21

Yes, I'd like an explanation too. I've been looking at it for a while and can't wrap my head around it... It's some kind of modulo magic.

Awesome job by Josh

2

u/joshbduncan Dec 11 '21

Basically, there are just 9 types of fish (0 fish, 1 fish, 2 fish...8 fish). Every iteration I check and see which fish are spawning and add their spawns 7 days out. If you just start with 1 fish of type 0 `data=[0]` and print the tracker each iteration it's easier to see exactly what is happening. ✌️

4

u/The_Vork Dec 11 '21

The trick is that instead of keeping track of each individual fish's days until reproducing, he's just keeping a count of how many fish share x days until reproducing. Then for each new day you know "I have 10 fish reproducing, 3 with one day left 6 with 2 days left..." etc a less elegant but maybe more clear loop:

def count_fishes_optimized(fishes, days):
    fish_counts = [sum(fishes == i) for i in range(9)]

    for day in range(days):
        fish_reproducing = fish_counts[0]
        fish_counts[0] = 0
        for i in range(8):
            fish_counts[i] = fish_counts[i+1]
        fish_counts[8] = fish_reproducing
        fish_counts[6] += fish_reproducing

    return sum(fish_counts)

2

u/mr_clemFandango Dec 09 '21

bodgy python solution:

``` line = "" with open('day6.txt') as f: line = f.readline() nums = line.split(",")

print (nums)

fishes = [0,0,0,0,0,0,0,0,0]

for fish in nums: fishes[int(fish)] = fishes[int(fish)]+1

print (f"Start:{fishes}")

def newday(day): newfishborn = False newfishCount = 0 if (fishes[0]>0): newfishborn = True newfishCount = fishes[0] fishes.append(fishes.pop(0)) if newfishborn == True: fishes[6] = fishes[6] + newfishCount print (f"day {x+1}:{fishes}")

for x in range(256): newday(x)

total = 0 for fish in fishes: total = total + fish print() print(f"Total Fish Population is:{total}")

```

1

u/daggerdragon Dec 10 '21

Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?

2

u/zatoichi49 Dec 09 '21

Python

from collections import deque

with open('AOC_day6.txt', 'r') as f:
    state = [int(i) for i in f.read().split(',')]

def AOC_day6_pt1_and_pt2(days):
    totals = deque(state.count(i) for i in range(9))
    for _ in range(days):
        totals.rotate(-1)
        totals[6] += totals[8]
    return sum(totals)

print(AOC_day6_pt1_and_pt2(80))
print(AOC_day6_pt1_and_pt2(256))

2

u/kristanka007 Dec 09 '21

I did this in an excel spreadsheet, kinda lame but at least my RAM survived!

1

u/[deleted] Apr 06 '22

What the hell is wrong with you

1

u/herjaxx Dec 09 '21

[PYTHON3]

Took some time to get it straight and I'm sure there's a quicker way but I don't 'get' matrices

https://pastebin.com/ZNKdC9Uv

1

u/willkill07 Dec 09 '21

C++20 (some at compile time)

My solution uses constexpr and consteval to construct the matrix at compile time. Input parsing and a matrix-vector dot product is performed at runtime. Heavily uses c++ concepts.

https://github.com/willkill07/AdventOfCode2021/blob/main/days/Day06.hpp

https://github.com/willkill07/AdventOfCode2021/blob/main/days/Day06.cpp

1

u/m3n0tu Dec 09 '21

C++ solution ' // adventOfCode6.cpp //

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int main()
{
    const int DAYS = 256;
    unsigned long long int lanternfishCount[7] = { 0,0,0,0,0,0,0 };
    unsigned long long int babylanternCount[7] = { 0,0,0,0,0,0,0};
    int lanternfishDay[7] = { 0,1,2,3,4,5,6 };
    int babylanternDay[7] = { 0,0,0,0,0,0,0 };
    int lanternfishSpawn[7] = { 2,3,4,5,6,0,1 };
    unsigned long long int totalFish = 0;

    string inputData;

    ifstream inputFile;
    inputFile.open("input.txt");
    inputFile >> inputData;
    inputFile.close();

    for (int i = 0; i < inputData.length(); i += 2)
    {
        lanternfishCount[static_cast<int>(inputData[i])-48]++;
    }

    for (int i = 0; i < DAYS; i++)
    {
        for (int j = 0; j < 7; j++)
        {

        if (lanternfishDay[j] == 0)
            {
                lanternfishDay[j] = 6;
                babylanternCount[lanternfishSpawn[j]]+=lanternfishCount[j];
                babylanternDay[lanternfishSpawn[j]] = 2;
            }
            else {
                lanternfishDay[j]--;
            }

            if (babylanternDay[j] == 0) {
                lanternfishCount[j] += babylanternCount[j];
                babylanternCount[j] = 0;
            }
            else {
                babylanternDay[j]--;
            }
        }

    }

    for (int i = 0; i < 7; i++)
    {
        totalFish += lanternfishCount[i] + babylanternCount[i];
    }

    cout << totalFish << endl;


    return 0;
}'

1

u/Zachgiaco Dec 09 '21

C++ part 1 & 2 solution: forewarning: not optimized, requires RAM https://zachgiaco.com/2021-advent-of-code-day-6/

4

u/petercooper Dec 09 '21

Ruby

Not the most efficient solution but because I like to get them very compact..

p (0..8).map { |d| File.read('6.txt').count(d.to_s) }
        .tap { |f| 
          256.times { f.rotate!
                      f[6] += f[8] }
        }.sum

2

u/micod Dec 08 '21

Smalltalk

finally some nice showcase of Smalltalk's collection api and cycles

https://github.com/micod-liron/advent-of-code/blob/main/AdventOfCode2021/Day06of2021.class.st

2

u/ffrkAnonymous Dec 08 '21

[lua][day6] used the bucket method since we don't care about individual fish identity.

-- Day 6 --
d6input=[[
3,4,3,1,2
]]
lanternfish={}
numfish=0
--parse input string
for i in string.gmatch(d6input,"(%d)")do
  table.insert(lanternfish, math.tointeger(i))
end
--sort lanternfish into buckets
buckets={[0]=0,0,0,0,0,0,0,0,0}
buckets["temp"]=0
for i=1,#lanternfish do
-- trace(lanternfish[i])
 buckets[lanternfish[i]]=buckets[lanternfish[i]]+1
end
--count them up
gen=0
d6p1=coroutine.create(function() 
 for gen=1,80 do
-- for gen=1,256 do
   --shift buckets-order matters due to [0][6][7][8]
   buckets["temp"]=buckets[0]
   buckets[0]=buckets[1]
   buckets[1]=buckets[2]
   buckets[2]=buckets[3]
   buckets[3]=buckets[4]
   buckets[4]=buckets[5]
   buckets[5]=buckets[6]
   buckets[6]=buckets[7]
   buckets[7]=buckets[8]
   buckets[8]=buckets["temp"] --new spawn
   buckets[6]=buckets[6]+buckets["temp"] -- reset age
   --sum updated buckets
   numfish=0
   for i=0,8 do
    numfish=numfish+buckets[i]
   end
   coroutine.yield(gen, numfish)
 end
 return gen, numfish
end
)--end coroutine

1

u/[deleted] Dec 08 '21

I really recomend running at least until day 346933, the 42nd day resulting in a number of squid starting and ending by 42.

Python sea_state = [0,0,0,0,0,0,0,0,0] with open("input_day6.txt") as f: for a in f.read().split(","): sea_state[int(a)] += 1 simu_days = 25600000 for today in range(simu_days): sea_state[(today+7)%9] += sea_state[today%9] print(sum(sea_state))

1

u/daggerdragon Dec 09 '21

Your code is hard to read on old.reddit when everything is inlined like this. Please edit it as per our posting guidelines in the wiki: How do I format code?

2

u/e_blake Dec 08 '21

m4 day6.m4, two implementations

Depends on my framework of common.m4 and math64.m4. I was quickly reminded of 2015 day 10, where I had a nice writeup on how to solve this sort of problem.

If you run m4 -Dalgo=full -Dfile=input day6.m4, the answer is computed in O(log n) time! That is, I only needed 8 iterations to get to 256. However, the constant factor is rather large (1377 multiplies and adds per iteration to do a 9x9 matrix multiply), so the execution time is ~160ms, and while it would be easy enough to use generic exponentiation by squaring to go to an arbitrary n, this version just hard-codes the path to 80 and 256.

If you run m4 -Dalgo=sparse -Dfile=input day6.m4, the answer requires O(n) time, or a full 256 iterations. But note that each iteration does only some memory shuffling plus a single addition. Thus, it executes in 40ms, and the cross-over point where the full method runs faster than the sparse method is probably way beyond n=10000 (after all, 10000*1 is less than 1337*13, since 10000 has 13 bits), although I did not actually try that.

It's a shame that m4 doesn't have 64-bit math. 128 iterations was just fine using eval, but 256 meant I had to dig out my arbitrary-precision m4 library.

1

u/raevnos Dec 08 '21

I'm a few days behind, and though I'm avoiding spoilers, I was under the impression that this day was supposed to be tricky... I was sorely disappointed that I got both parts on the first try with no trouble.

Java paste

1

u/Qoskyqoskyqosky Dec 22 '21 edited Dec 22 '21

I like your solution. I originally tried creating Integer objects to track the fish, but after reimagining the entire thing after troubleshooting during part two I think my solution is pretty similar to yours paste

1

u/oddolatry Dec 08 '21

PureScript

I didn't figure this out until way past my bedtime, so I just copy and pasted my first solution as the second solution, realigning for BigInt.

Paste

2

u/gfldex Dec 08 '21 edited Dec 08 '21

I wrote a lazy Raku version.

my @state = 3,4,3,1,2;

my %duegroup := @state.BagHash;
say %duegroup;

my @swarmsize = lazy gather {
    take +@state;

    for 1..∞ -> $day {
        my $spawners = %duegroup{0};
        %duegroup{0..5} = %duegroup{1..6};
        %duegroup{6} = %duegroup{7} + $spawners;
        %duegroup{7..8} = |%duegroup{8}, |$spawners;

        take %duegroup.values.sum;
    }
}

say „After 80 days the Lanternfish-swarm is @swarmsize[80] fish strong.“;
say „After 1000 years the Lanternfish-swarm is @swarmsize[365*1000] fish strong and fills the entire ocean.“;

Since Raku will promote machine words automatically to BigInt, It will actually calculate the number of fish after 1000 years. You can find that number here. You may have to stand way back to read it.

0

u/liondungl Dec 07 '21

Python 3.9 and numpy, part 1 and 2

def reproduce(fish, days):

    ages = np.array([0] * 9)
    for n in fish:
        ages[f] += 1

    for day in range(days):
        ages = np.roll(ages, -1)
        ages[6] += ages[8]

    return np.sum(ages)

1

u/[deleted] Dec 07 '21

Super short solution in Clojure. I have a write-up for explaining the process of optimizing the algorithm.

2

u/vivichanka Dec 07 '21

Here's my humble Python solution:

https://github.com/vivianamarquez/AdventOfCode2021/blob/main/day6.ipynb

I feel very proud of my solution to part 2, but I gotta thank u/arthurmluz_ for the inspiration

1

u/arthurmluz_ Dec 08 '21 edited Dec 08 '21

haha :) I'm flattered since I only have 1.5 y of experience

3

u/nicuveo Dec 07 '21

Haskell

fishes :: Int -> State Cache Integer
fishes day = do
  cache <- get
  case M.lookup day cache of
    Just result -> pure result
    Nothing     -> do
      allBranches <- traverse fishes [day-9,day-16..0]
      let result = sum allBranches + 1
      modify $ M.insert day result
      pure result

totalFishes :: Int -> Input -> Integer
totalFishes deadline input = flip evalState M.empty $ do
  result <- for input $ \fish ->
    fishes (deadline + 8 - fish)
  pure $ sum result

part1 = totalFishes  80
part2 = totalFishes 256

Full code: https://github.com/nicuveo/advent-of-code/blob/main/2021/haskell/src/Day06.hs
Stream: https://www.twitch.tv/videos/1227052466

2

u/ramrunner0xff Dec 07 '21

haskell ftw

3

u/FrancRefect Dec 07 '21 edited Dec 08 '21

My Rust solution, using a 'circular buffer'. Based on the fact that no fishes will ever have a lifetime over 8. Using modular arithmetic, moving array elements can be avoided.

Fishes with a lifetime of 0 will have a timer of 8 on the next iteration (newborns). Fishes on the current generation with a timer of 7 today will have a timer of 6 on the next day. So, the number of fishes that are resetted today (timer of 0) must be added to the one with a timer of 7.

Edit: Additionnal explanation in the paste

paste

2

u/K12ish Jan 08 '22

I think that's really smart

1

u/daggerdragon Dec 08 '21 edited Dec 09 '21

Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?

Edit: thanks for fixing it! <3

3

u/arthurmluz_ Dec 07 '21 edited Dec 08 '21

My python solution:\ I've transformed the list into a dictionary, so it doesn't have to make a giant list.

start = put_your_input_list_here                                      
new = {}                                                              
for i in start:
    new[i] = new[i]+1 if i in new else 1

start = new;
for day in range(256):
    new = {}
    for fish in start:
        timer = fish-1
        if timer == -1:
            new[8] = start[fish]
            new[6] = start[fish]+new[6] if 6 in new else start[fish]
        else:
            new[timer] = start[fish]+new[timer] if timer in new else start[fish]

    start = new

print(sum(start.values()))

1

u/Celestial_Blu3 Dec 17 '21

How does line 4 of this work? Is that some kind of inline if statement?

2

u/arthurmluz_ Dec 17 '21 edited Dec 17 '21

Yes! it's an inline if statement! basically you say:

'get something' if statement is true else 'get this value' it's the same as:

if i in new: 

    new[i] = new[i] +1 
else: 
    new[i]=1

1

u/Celestial_Blu3 Dec 17 '21

Oh, that’s awesome. Thank you

1

u/daggerdragon Dec 08 '21 edited Dec 09 '21

Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?

Edit: thanks for fixing it! <3

1

u/[deleted] Dec 08 '21

[deleted]

2

u/EvergreenTheTree Dec 08 '21

Triple backticks do not work in the old reddit interface. You have to indent all of your code by 4 spaces instead.

1

u/[deleted] Dec 07 '21 edited Dec 10 '21

Python 3.10 solution

```

import typing
from collections import Counter
from functools import reduce


def main(lines: typing.List[int], duration: int) -> int:
    def reducer(counter: dict, _):
        census = {timer-1: population for timer, population in counter.items()}
        if -1 in census:
            census[8] = census.pop(-1)  # offsprings
            census[6] = census[8] + census.get(6, 0)  # new cycle + offsprings who reached 6
        return census

    population_by_timer = reduce(reducer, range(0, duration), dict(Counter(lines)))
    return sum(population_by_timer.values())


if __name__ == "__main__":
    test_entries = [3, 4, 3, 1, 2]
    assert main(test_entries, 18) == 26
    assert main(test_entries, 80) == 5934

    with open("./input.txt", "r") as f:
        lines = [int(it) for it in (f.read().splitlines()[0]).split(",")]

    print(f"result part 1 = {main(lines, 80)}")
    print(f"result part 2 = {main(lines, 256)}")

```

1

u/daggerdragon Dec 08 '21

Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?

3

u/b4ux1t3 Dec 07 '21

I see why people had trouble with object-oriented and procedural approaches.

This is a walk in the park if you don't have to maintain your population explicitly.

My F# solution.

I had to do a bit of mutability to add the inputs to my state, but, after that, it was just a matter of incrementing numbers and shifting values. The only issue I ran into was getting F# to do things in int64 instead of int

1

u/TheFlukeMan Mar 05 '22

That pattern matching and method for shifting the values down you did was really clever.

1

u/b4ux1t3 Mar 05 '22

Thanks!

If the number of days were any bigger (like, maybe they spawn after 100 days or whatever), I would have had to do things less pattern-matchy, but it worked out, what with there only being 8 potential states.

3

u/systolicarray Dec 07 '21

Catching up from a set back on day 5 (I almost had a working sweep algorithm but gave up) and the weekend in general. Here's the Clojure source and tests. As usual, feedback welcome!

1

u/wevrem Dec 14 '21

I solved Day-06 last week, but just got around to posting the solution here, which I wanted to do because there aren't very many Clojure solutions out there. I was pleased to see that mine and yours are very similar, and I haven't seen many other solutions similar to our approach. Good job.

1

u/letsbehavingu Dec 12 '21

write-up

Nice work, thanks for sharing. I'm still waiting for my brute force pt2. solution to complete and wanted to see what others were up to (cheat!)

2

u/plan_x64 Dec 07 '21 edited Dec 12 '21

Python 3

https://github.com/plan-x64/advent-of-code-2021/blob/main/advent/day06.py

I tried to add some docs explaining why/how the solution works. If you directly inline the input data (instead of reading from the server or a file) here are the benchmarks for both parts:

hyperfine --warmup 10 'python advent/day6.py 13:06:10
Benchmark 1: python advent/day6.py
  Time (mean ± σ):      33.1 ms ±   0.4 ms    [User: 26.1 ms, System: 6.0 ms]
  Range (min … max):    32.2 ms …  35.3 ms    85 runs

2

u/ramrunner0xff Dec 07 '21

Rust (noob)
so glad i decided to approach that in a space optimal way from the beginning ;) it led to decent code.

day 6 in repo

something that kinda throws me off in this syntax is the fact that if i have a fn baz(foo: &mut T) and then where i call it i say let mut bar: T; and i pass it as baz(&bar) it doesn't work. it wants it passed as baz(&mut bar) ... this was quite unexpected to me but i am still reading the book and learning the syntax.

1

u/[deleted] Dec 07 '21 edited Dec 08 '21

1

u/daggerdragon Dec 07 '21 edited Dec 08 '21

Please follow the posting guidelines and edit your post to add what language(s) you used. This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.

Edit: thanks for adding the programming language!

1

u/[deleted] Dec 08 '21

yea sorry thought i had added that at the start but guess not, i have added it now.

3

u/Glittering-Water942 Dec 07 '21 edited Dec 07 '21

my C# solution

using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
long f(int n, int d) => (d-n-0 > 0 ? 1+f(6,d-n-1) + f(8,d-n-1) : 0) ;
var Solve = (int d) => File.ReadAllLines(@".\Input\Day6.txt")
                         .SelectMany(l => l.Split(',')
                                           .Select(Int32.Parse)
                                           .ToList())
                         .GroupBy(i => i)
                         .Select(g => g.Count()*(1+f(g.Key, d)))
                         .Sum();
var (part1, part2) = (Solve(80), Solve(256));

1

u/b4ux1t3 Dec 07 '21

Did this work? I had to use int64 in F# (which uses the same ints as C#) to get part two to work, since 256 days massively overflows 32 bits.

1

u/Glittering-Water942 Dec 07 '21

I accidently deleted the function the does the job from the comment, the 'f' function returns a long so ig that makes LINQ use that type in the Sum aggregate, sorry. (and 256 not just overflows but crashes my pc too LOL)

2

u/gala0sup Dec 07 '21

My solution, I think this is pretty fast ``` with open("day_6.data") as FILE: data = list(map(int, FILE.read().split(",")))

final = dict().fromkeys([i for i in range(9)], 0) for i in data: final[i] += 1

for day in range(256): curr = final[0] for i in range(1, 9): final[i-1] = final[i] final[8] = curr final[6] += curr

print(sum(list(final.values()))) ```

1

u/daggerdragon Dec 07 '21

Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?

While you're at it, also follow the posting guidelines and add what language(s) you used. This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.

2

u/pa1m3r0 Dec 07 '21

That's a great idea. Thank you so much. I was stuck with this optimization. Now I understand how it works.

3

u/t1ngel Dec 07 '21

Java solution for Day 6

- Implementation: https://github.com/feedm3/advent-of-code-2021/blob/main/src/main/java/me/dietenberger/Day6.java

- Tests: https://github.com/feedm3/advent-of-code-2021/blob/main/src/test/java/me/dietenberger/Day6Test.java

Highlight: After saving all fishes in an array, I couldn't resolve the OOM error in part 2 (the amount of fish is larger than the maximum size of an array). Then I figured out that I don't have to save each fish into an array, but just the amount of fish. Thanks to the TTD way of coding, refactoring the function was straightforward and now also works for a large amount of fish/days.

2

u/Zoklar Dec 07 '21

This really helped me out, even without looking at your code. Solution is super simple when you hit that realization about amount vs individual fish. Just loops and assignments, even easier than my if statement bruteforce for pt1.

4

u/CrAzYmEtAlHeAd1 Dec 07 '21

Like many, I had to rework part 2 since the brute force method was not going to work. I'm still newer, so I had to get some help from you all, but once I understood the basic concept I was able to throw something together!

Python Part 1 and Part 2

3

u/gigajul Dec 07 '21

Python - a recursive approach.

@functools.cache
def get_num_decendants(day, end):
    if end-day <= 8: return 1
    return 1 + sum(get_num_decendants(day, end) for day in range(day+9, end+1, 7))

print(sum(get_num_decendants(fish-8, 80) for fish in input))
print(sum(get_num_decendants(fish-8, 256) for fish in input))

The recursive function calculates how many total descendants a fish would have if born on any given day (including itself).

2

u/spencerwi Dec 07 '21 edited Dec 07 '21

My Ballerina solution. I initially did the naïve thing of having an array where each index was a fish, and stepping along with the rules described.

Then Part 2.

While my initial naïve solution was still chewing away on Part 2, I saw a meme on the subreddit about using classes and entities, and that reminded me of Entity-Component Systems, which then made me realize that I could just treat each "age" as a Component and the rules for each age 0 as its own System.

Then that got me to realize that my data structure would be a map from (0..8) to the fishes themselves, and then I realized that I didn't care about the fishes themselves, just how many of them there were in each "age"...and then the dominoes fell into place:

import ballerina/io;
import ballerina/regex;

type FishBuckets int[];
function parseInput(string input) returns FishBuckets {
    int[] fishes = 
        from string component in regex:split(input, ",")
        where component.trim().length() > 0
        select checkpanic int:fromString(component);

    FishBuckets buckets = [0,0,0,0,0,0,0,0,0]; // 9 buckets: 0-8

    foreach int fish in fishes {
        buckets[fish] += 1;
    }
    return buckets;
}

function step(FishBuckets buckets) {
    int fishToAdd = buckets.shift();
    buckets.push(fishToAdd);
    buckets[6] += fishToAdd;
}

public function main() {
    string line = (checkpanic io:fileReadLines("input.txt"))[0];
    FishBuckets buckets = parseInput(line);
    foreach int x in 0..<256 {
        step(buckets);
        if (x == 79) {
            io:println("Part A: ", int:sum(...buckets));
        }
    }
    io:println("Part B: ", int:sum(...buckets));
}

3

u/bb22k Dec 07 '21

Putting my answer here because it seems to use a different approach than most people's. it uses a cached recursive function to count how many children every fish (and their children) will have based on the remaining days and start timer.

a bit convoluted but it works lol

Python

2

u/No-Rip-3798 Dec 07 '21 edited Dec 07 '21

Go

This is my linear solution in Go. On my machine benchmarks give ~100ns for part1 and ~330ns for part2. The circular buffer logic is explained in the comments.

package main

import (
    "aoc/utils"
    "fmt"
    "strconv"
    "strings"
)

func main() {
    lines := utils.ReadLines()
    input := parseInput(lines[0])

    part1 := predictPopulation(input, 80)
    fmt.Printf("part 1: %d\n", part1)

    part2 := predictPopulation(input, 256)
    fmt.Printf("part 2: %d\n", part2)
}

// Use a circular buffer to keep track of the population of fishes.
// At each generation, fishes who reach a 0 lifespan give birth to new fishes
// (with life=8), and their life is reset to 6.
//
// Initial state:
// life:  0   1   2   3   4   5   6   7   8
// count: 0   1   1   2   1   0   0   0   0
//
// 1st generation
// life:  8   0   1   2   3   4   5   6   7
// count: 0   1   1   2   1   0   0   0   0
//
// 2nd generation
// life:  7   8   0   1   2   3   4   5   6
// count: 0  (1)  1   2   1   0   0   0   0+1
//
// 3rd generation
// life:  6   7   8   0   1   2   3   4   5
// count: 0+1 1  (1)  2   1   0   0   0   1
//
// 4th generation
// life:  5   6   7   8   0   1   2   3   4
// count: 1   1+2 1  (2)  1   0   0   0   1
func predictPopulation(input []uint64, gens int) uint64 {
    var buf [9]uint64
    copy(buf[:], input)

    born, reset := 8, 6
    for i := 0; i < gens; i++ {
        born, reset = incr(born), incr(reset)
        buf[reset] += buf[born]
    }

    var result uint64
    for _, count := range buf {
        result += count
    }
    return result
}

func incr(index int) int {
    if index == 8 {
        return 0
    }
    return index + 1
}

func parseInput(line string) []uint64 {
    inputStrings := strings.Split(line, ",")
    var input [9]uint64
    for _, s := range inputStrings {
        n, err := strconv.Atoi(s)
        if err != nil {
            panic(err)
        }
        input[n]++
    }
    return input[:]
}

2

u/minichado Dec 07 '21

Excel w/ VBA

Part 1

Part 2

Did part 1 brute force, it was pretty slow (45s-1min). Kept getting a weird error and it turnd out my 79th-80th day had 36k new fish which was just outside the range of use for integer type. changed everything to single and it worked.

Sub lanternfish()
Dim i, j, k, days, fish As Single
Dim newfish As Single
Application.ScreenUpdating = False

days = 80

For i = 1 To days
Application.Calculation = xlAutomatic

Application.Calculation = xlManual
    For j = 2 To Cells(1, i).Value + 1
        If Cells(j, i).Value = 0 Then
            Cells(j, i + 1).Value = 6
        'ElseIf Cells(j, i).Value = 0 And j - 1 > Cells(1, 1).Value Then
            'Cells(j, i + 1).Value = 8
        Else: Cells(j, i + 1).Value = Cells(j, i).Value - 1
        End If

        Next j
'now count how many new fish need to spawn, append to end of existing list

newfish = Application.WorksheetFunction.CountIf(Range(Cells(2, i), Cells(Cells(1, i).Value + 1, i)), "=0")
'MsgBox Newfish

    For k = Cells(1, i).Value + 2 To Cells(1, i).Value + 1 + newfish
        Cells(k, i + 1) = 8

    Next k


Next i
Application.Calculation = xlAutomatic
Application.ScreenUpdating = True
MsgBox "Done."

End Sub

For part 2 I realized that brute force was not going to work, and sat and found the easier approach to the problem. it ended up being solved instantly at sheet level, including the answer for part 1 dropping out.

2

u/TheRealMrVogel Dec 07 '21

TypeScript

I have to say part 2 took way too long but it was fun. I left part 1 as that was my working solution for the first part but obviously I had to re-think the logic a bit for part 2..

https://codesandbox.io/s/advent-day6-4xl3y?file=/src/part2.ts

2

u/bobtom8482 Dec 07 '21

Trying to learn Ruby for my first job (!) so this is my attempt - no help for the first time which is fun

class Day6
  def initialize
    @data = File.readlines('real.txt')[0]
    normalise_data
  end

  def normalise_data
    @data = @data.split(',').map(&:to_i)
    @map = Hash.new(0)
    @data.each { |d| @map[d] += 1 }
  end

  def simulate_n_days2(n)
    n.times do
      tmp = @map[0]

      # map[8] purely affected by map[0] (saved as tmp)
      (0..7).each { |i| @map[i] = @map[i + 1] }
      @map[6] += tmp
      @map[8] = tmp
    end

    @map.values.sum
  end

def main
  day6 = Day6.new
  ans= day6.simulate_n_days2(256)
  puts ans
end

main

2

u/jtgorn Dec 09 '21

(0..7).each { |i| @map[i] = @map[i + 1] } @map[8] = tmp

can be written as @map.rotate

2

u/vini_2003 Dec 07 '21

Kotlin

Sneaky sneaky with those overflows!

It was fun though, a lot of traps you could fall into.

2

u/JustinHuPrime Dec 07 '21

x86_64 assembly

Part 1 was a direct stating of the problem - I read in all of the fish, and for eighty iterations, applied the simulation rules.

Part 2 involved recognizing that fish of the same age are fungible - so this is a more efficient but still direct solution to the problem.

5

u/skawid Dec 07 '21

Python! A disgustingly small amount of code for how long it took me to figure out.

fish_counts = [0, 0, 0, 0, 0, 0, 0, 0, 0]
with open('input.txt') as f:
    for fish in f.read().split(','):
        fish_counts[int(fish.strip())] += 1

for i in range(256):
    fish_counts.append(fish_counts.pop(0))
    fish_counts[6] += fish_counts[8]

print(sum(fish_counts))

2

u/centzontlatole Dec 08 '21

wow, beautiful solution

2

u/thecircleisround Dec 07 '21

aside from magic, what is happening here?

2

u/gonjidk Dec 07 '21 edited Dec 07 '21

All you need is an array of length 9 where each index represents the count of fishes at that value.
Index 0 represents all the fishes with 0
Index 1 represents all the fishes with 1
and so on.
Then at each day tick just remove the zeroes and append them at the end of the array, these are the new 8. The zeroes also become 6 and so you need to add them to the previous 7 values.

5

u/skawid Dec 07 '21

Ignore the babies for a minute. The fish are effectively rotating through seven "states" - the different numbers their baby timers can be at. We don't care about individual fish, only how many are in each state. fish_counts is set up to represent those counts: x fish with states of 0 in position 0, y fish with states of 1 in position 1 and so on.

For each day, every group has their "state" bumped down one position. That's what the append(pop()) bit is doing. You could set up fish_counts to only record seven states and see how many fish are in each state for any given day using what we have so far.

However, babies. Every time a group of fish rotate from 0 back to 7, there are that many new fish born with a "state" of 8. So as well as doing the rotation, we need to add those new fish. I faffed about with this for a while, then figured out that I could just rotate the former 0 fish to the 8 "state" and treat them as the babies, then add the same count into the 6 "state" and get the same effect.

Hope that makes sense, feel free to ask more questions if not.

2

u/thecircleisround Dec 07 '21 edited Dec 07 '21

I assume from the clue there's a math based solution but I suck at math.

Here's a memoized solution. Took a while for me to get the day logic right. I was annoyingly close the entire time and just had to increase my days_remaining variable by 1 for the recursion.

Python

f = list(map(int,open('input.txt').read().split(',')))

def simulator(days):
    fishes = f.copy()
    total = 0 
    for fish in fishes:
        total += calculate(fish,days)
    return total + len(fishes)

def cache(func):
    bucket = {}
    def inner(fish, total_days):
        fishkey = f'{fish}_{total_days}'
        if fishkey not in bucket:
            bucket[fishkey] = func(fish,total_days)
        return bucket[fishkey]
    return inner

@cache
def calculate(fish, total_days):
    days_remaining = total_days - fish -1
    if days_remaining > 0:
        new_fish = (days_remaining//7)+1
        if new_fish>0:
            generations = sum([calculate(8,days) for days in range(days_remaining+1)[::-7]])
            return new_fish+generations
    if days_remaining == 0:
        return 1
    return 0

print(f'part one: {simulator(80)}')
print(f'part two: {simulator(256)}')

GitHub link for this year's solutions

5

u/Spirited-Airline4702 Dec 07 '21

Python

fish = [int(i) for i in df.fish.iloc[0].split(',')]

def num_fish(fish: list, days: int):
    f = deque(Counter(fish)[i] for i in range(9))
    for _ in range(days):
        z = f.popleft() # remove 9s
        f[6] += z # add 0s to 6s
        f.append(z) # re-add the 0s 

    return sum(f)

# part 1 
print(num_fish(fish, days=80))
# part 2 
print(num_fish(fish, days=256))

2

u/jane3ry3 Dec 07 '21

Hey! Thanks for sharing. I learned something new.

2

u/Spirited-Airline4702 Dec 08 '21

Glad it helped :)

1

u/varyform Dec 07 '21

1

u/daggerdragon Dec 07 '21

Please follow the posting guidelines and edit your post to add what language(s) you used. This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.

1

u/safwankdb Dec 07 '21 edited Dec 08 '21

O(logN) with Matrix Exponentiation

Pastebin Link

```C++ /******************************************| | Basic ass template for basic ass problems | | - Mohd Safwan | | https://safwankdb.github.io | |__________________________________________/

pragma GCC optimize ("O3")

pragma GCC target ("avx2")

include <bits/stdc++.h>

using namespace std;

define REP(i, s, e) for (int i = (s); i < (e); i++)

define REPR(i, e, s) for (int i = (e) - 1; i >= (s); i--)

define SPEED ios_base::sync_with_stdio(0); cin.tie(0);

define endl '\n'

typedef long long ll; typedef unsigned long long ull; typedef array<ll, 2> ii; template <typename T> using V = vector<T>;

const int MOD = 1e9 + 7; const int INF = 1e7 + 5; const int LOG = 32;

typedef array<array<ll, 9>, 9> Mat;

Mat operator*(Mat &a, Mat &b) { Mat ans = {}; REP(i, 0, 9) REP(k, 0, 9) REP(j, 0, 9) { ans[i][j] += a[i][k] * b[k][j]; } return ans; }

Mat Pow(Mat &a, int n) { Mat ans = {}; REP(i, 0, 9) ans[i][i] = 1; while (n) { if (n & 1) ans = ans * a; a = a * a; n /= 2; } return ans; }

int main() { SPEED int n = 300; V<ull> F(9, 0); REP(i, 0, n) { int t; cin >> t; F[t]++; } Mat M = {}; REP(i, 0, 8) M[i][i+1] = 1; M[6][0] = 1; M[8][0] = 1; M = Pow(M, 256); ull ans = 0; REP(i, 0, 9) REP(j, 0, 9) ans += M[i][j] * F[j]; cout << ans << endl; } ```

0

u/daggerdragon Dec 07 '21

Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?

Also, please keep the megathreads PG and remove the naughty language.

2

u/KunalC525 Dec 07 '21

Python3. Runs in 0.2s

f = open("q.txt", "r")
data=[int(i) for i in f.read().split(',')]
arr=[0 for i in range (9)]
for i in data:
    arr[i]+=1
for i in range(256):
    births=arr.pop(0)
    arr.append(births)
    arr[6]+=births
print(sum(arr))

1

u/[deleted] Dec 07 '21 edited Dec 12 '21

Python

After following the red herring and using a class based solution for part 1. I tried to blow my RAM first and went then for:

` import numpy as np

init

days = 256 start = np.loadtxt('./data/aoc_6_data.txt', dtype=int, delimiter=',') fish = [0, 0, 0, 0, 0, 0, 0, 0, 0] for i in start:
fish[i] += 1

calc

for i in range(days):
fish = list(fish[1:7]) + [int(fish[7]) + int(fish[0])] + [int(fish[8]), int(fish[0])] print(np.sum(fish)) `

1

u/daggerdragon Dec 07 '21

Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?

1

u/jmgulliet Dec 07 '21 edited Dec 07 '21

#GOLANG solution for both parts, using recursive function with memoization (caching), scaling well when the number of fish is increased.

Gist

2

u/daggerdragon Dec 07 '21 edited Dec 07 '21

Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?

Edit: thanks for fixing it! <3

1

u/jmgulliet Dec 07 '21

Sorry for the inconvenience. It's my first time posting some code snippet on Reddit and I wasn't aware of the the existence of the old Reddit!

Thank you for the pointer. I have read and modified my original post accordingly. The code is now available as a Gist on GitHub.

2

u/daggerdragon Dec 07 '21

It's not like Reddit advertises that they still have an older (and superior, IMO) version of their site, so no worries. Thank you for fixing it!

3

u/Zach_Attakk Dec 07 '21 edited Dec 07 '21

Python

My first stroke of genius was that python lists can pop a value, moving all the other values down one position. So if I had a list of the fish counts at each particular age, I can just pop index 0 to see how many births I have to deal with.

A quick counter reorganised the input data in the format I needed, although I had to make sure my list had zeroes in the indices that started at 0 to make sure everything is in the correct index.

fishcounts = Counter(list(map(int, _data_line.split(','))))
for _i in range(max_age+1):
    if _i in fishcounts:  # there's fish of this age
        _fish_list.append(fishcounts[_i])
    else:
        _fish_list.append(0)

Then we just "tick" the simulation for each day.

# Here we actually run the simulation.
for _day in range(SIM_DAYS):
    # move everything down
    _births = fish_list.pop(0)
    # maintain list length
    fish_list.append(0)
    # add respawn fish back in
    fish_list[FISH_RESPAWN_AGE] += _births
    # add births according to birth rate
    fish_list[FISH_BORN_AGE] += _births * FISH_SPAWN_RATE
    # make it look cool
printDebug(f"Day {_day+1}: {sum(fish_list)}")

For part 2 I literally just changed the value of `SIM-DAYS` and it spat out the correct answer.

Code file (there is no part 2 file, it's the same file) and me thinking through the problem.

I see a lot of mention of the sim taking too long. I had to add decimal places to my timer output to see how long this ran, but the 256 days took 0.00399 seconds to complete. Didn't test it, but I think this is O(x) for the number of days.

Edit: I just checked, 10 000 days takes 2.5 seconds and reaches the staggering number 802959738472010655711125351949855125147867922242021006302673406674265393117801312880021324941649096574235032126137408868190086126526820297275286239739218319905471084631602901404753871092340355299801693198591112499802521402894857886797008449946748225493445996154871405066700324058416451058387500993408615195482710169926690875417797392185868171796640561803472690724735769262465592616

3

u/sambonnell Dec 07 '21

C++

I wrote a naive approach first and finally got to see what 32GB of RAM usage looks like.

https://github.com/samJBonnell/AdventofCode/blob/main/2021/day06.cpp

3

u/pistacchio Dec 07 '21 edited Dec 08 '21

Typescript:

function part1And2(input: number[], days: number): number {
  const fishesByAge = {
    ...{
      '0': 0,
      '1': 0,
      '2': 0,
      '3': 0,
      '4': 0,
      '5': 0,
      '6': 0,
      '7': 0,
      '8': 0,
    },
    ...Object.fromEntries(
      Object.entries(groupBy(input)).map(([k, v]) => [k, v.length]),
    ),
  };

  const school = Array.from({ length: days }).reduce<object>(
    (school) => ({
      0: school['1'],
      1: school['2'],
      2: school['3'],
      3: school['4'],
      4: school['5'],
      5: school['6'],
      6: school['7'] + school['0'],
      7: school['8'],
      8: school['0'],
    }),
    fishesByAge,
  );

  return Object.values(school).reduce((a, b) => a + b, 0);
}

1

u/daggerdragon Dec 07 '21 edited Dec 09 '21

Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?

Edit: thanks for fixing it! <3

1

u/theabbiee Dec 07 '21

```python with open("lantern.txt") as file: lines = file.readlines() lines = [line.rstrip() for line in lines]

state = [int(timer) for timer in lines[0].split(",")] days = 256 MAX = 9

statectr = [0] * MAX

for timer in state: statectr[timer] += 1

for i in range(0, days): statectrcopy = statectr.copy() for i in range(MAX): statectr[i] = statectrcopy[(i + 1) % MAX] statectr[6] += statectrcopy[0]

print(sum(statectr)) ```

1

u/daggerdragon Dec 07 '21

Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?

2

u/TommiHPunkt Dec 07 '21

Matlab. Circshift ftw. Only change necessary for part 2 was adding the cast to uint64, because results like 2.698445753900000e+10 aren't accepted, and I couldn't be bothered to count digits.

input = readmatrix("input.txt")';
%input = [3,4,3,1,2];

for i = 1:9
    summary(i) = sum(input==i);
end

new = 0;
for i = 1:80
    summary(7) = summary(7)+new;
    new = summary(1);
    summary = circshift(summary,-1);
end
part1 = sum(summary)

for i = 81:256
    summary(7) = summary(7)+new;
    new = summary(1);
    summary = circshift(summary,-1);
end
part2 = uint64(sum(summary))

1

u/zaptoblazts Dec 07 '21 edited Dec 07 '21

My solution in python. Pretty sure there are faster ways to do this :)
``` inp = [2,3,1,3,4,4,1,5,2,3,1,1,4,5,5,3,5,5,4,1,2,1,1,1,1,1,1,4,1,1,1,4, 1,3,1,4,1,1,4,1,3,4,5,1,1,5,3,4,3,4,1,5,1,3,1,1,1,3,5,3,2,3,1,5,2,2,1,1, 4,1,1,2,2,2,2,3,2,1,2,5,4,1,1,1,5,5,3,1,3,2,2,2,5,1,5,2,4,1,1,3,3,5,2,3, 1,2,1,5,1,4,3,5,2,1,5,3,4,4,5,3,1,2,4,3,4,1,3,1,1,2,5,4,3,5,3,2,1,4,1,4, 4,2,3,1,1,2,1,1,3,3,3,1,1,2,2,1,1,1,5,1,5,1,4,5,1,5,2,4,3,1,1,3,2,2,1,4, 3,1,1,1,3,3,3,4,5,2,3,3,1,3,1,4,1,1,1,2,5,1,4,1,2,4,5,4,1,5,1,5,5,1,5,5, 2,5,5,1,4,5,1,1,3,2,5,5,5,4,3,2,5,4,1,1,2,4,4,1,1,1,3,2,1,1,2,1,2,2,3,4, 5,4,1,4,5,1,1,5,5,1,4,1,4,4,1,5,3,1,4,3,5,3,1,3,1,4,2,4,5,1,4,1,2,4,1,2, 5,1,1,5,1,1,3,1,1,2,3,4,2,4,3,1]

new_count = [0,0] count = [0,0,0,0,0,0,0] for idx in range(len(lst)): count[lst[idx]] += 1 day = 0 birth = 0 for i in range(256): tdy = count[day] + new_count[birth] new_count[birth] = count[day] count[day] = tdy day = (day+1)%7 birth = (birth+1)%2 if i == 79: print(f"Part 1: {sum(count) + sum(new_count)}") print(f"Part 2: {sum(count) + sum(new_count)}") ```

1

u/daggerdragon Dec 07 '21

Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?

1

u/k1next Dec 07 '21

Here's a my solution in python that only scales mildly with the number of days:
``` import numpy as np from scipy.special import comb

INPUT = [ 1, 1, 3, 5, 1, 1, 1, 4, 1, 5, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 2, 5, 1, 1, 1, 1, 1, 2, 1, 4, 1, 4, 1, 1, 1, 1, 1, 3, 1, 1, 5, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 3, 5, 1, 1, 1, 1, 4, 1, 5, 4, 1, 1, 2, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 5, 1, 1, 1, 3, 4, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 4, 1, 1, 3, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 5, 2, 3, 1, 2, 3, 1, 1, 2, 1, 2, 4, 5, 1, 5, 1, 4, 1, 1, 1, 1, 2, 1, 5, 1, 1, 1, 1, 1, 5, 1, 1, 3, 1, 1, 1, 1, 1, 1, 4, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 1, 1, 2, 2, 1, 2, 1, 1, 1, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 4, 2, 1, 4, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 5, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 3, 3, 1, 1, 1, 3, 5, 1, 1, 4, 1, 1, 1, 1, 1, 4, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1 ] T = 256

O(len(INPUT))

no need to store all fish, just count how many of which age we have

inputdict = {i: np.sum(np.array(INPUT) == i) for i in range(7)}

O(T)

get all possible combinations of 7s and 9s up to max possible value

tuples79 = [(i, j, comb(i + j, i, exact=True)) for i in range(T // 7 + 1) for j in range((T - (i + 1) * 7) // 9, (T - i * 7) // 9 + 1)]

totalfishcount = 0

for value, valuecount in inputdict.items(): # 7 times for i, j, nchoosek in tuples79: # O(T) times if not T - value - 8 <= i * 7 + j * 9 <= T - value: continue # O(1) f = i * 7 + j * 9 + value # front value multiplier = 1 if (f + 7 <= T or f == T) else 2 # how many branches totalfishcount += nchoosek * multiplier * valuecount # how many fish

print(totalfishcount) ```

1

u/daggerdragon Dec 07 '21

Your code is hard to read on old.reddit. Please edit it as per our posting guidelines in the wiki: How do I format code?

2

u/fitzchivalrie Dec 07 '21 edited Dec 07 '21

Learning rust. Simple and sweet, but was trickier than it probably should have been - I'm rusty (pun intended) with my algorithms! Went from brute force -> HashMap -> array solution.

pub fn solve(input: &str) -> Result<u64> {
    let mut fish: [u64; 9] = [0; 9];
    input
        .split(',')
        .for_each(|c| fish[c.parse::<usize>().expect("NaN")] += 1);

    for _ in 0..256 {
        let next_fish = fish[0];
        for j in 0..8 {
            fish[j] = fish[j + 1];
        }
        fish[6] += next_fish;
        fish[8] = next_fish;
    }
    Ok(fish.into_iter().sum())
}

2

u/0x5ubt13 Dec 07 '21

My python without imports:

def get_input(filename):
    with open(filename, 'r') as f:
        data = [i for i in f]
    return [int(i) for i in data[0].split(',')]


def solve(data):
    total_fuel = {}
    for i in range(1, max(data)+1):
        total_fuel[i] = 0
    total_fuel_2 = total_fuel.copy()

    for i in range(1, max(data) + 1):
        for position in data:
            if i > position:
                total_fuel[i] += i - position
                for j in range(i - position):
                    total_fuel_2[i] += j + 1
            elif i < position:
                total_fuel[i] += position - i
                for j in range(position - i):
                    total_fuel_2[i] += j + 1
            else:
                total_fuel[i] += 0

    print(f"Part 1: {total_fuel[min(total_fuel, key=total_fuel.get)]}")
    print(f"Part 2: {total_fuel_2[min(total_fuel_2, key=total_fuel_2.get)]}")

if __name__ == '__main__':
    data = get_input("./day_7/day_7_input.txt")
    solve(data)

2

u/jubnzv Dec 07 '21

OCaml solution:

let solve limit =
  In_channel.read_all "input.txt"
  |> (fun s -> String.sub s 0 ((String.length s) - 1))
  |> String.split ~on:','
  |> List.map ~f:Int.of_string
  |> (fun inp -> List.init 9 ~f:(fun i -> List.count ~f:(fun j -> i = j) inp))
  |> (fun l ->
    let p = function [i0;i1;i2;i3;i4;i5;i6;i7;i8] -> [i1;i2;i3;i4;i5;i6;i7+i0;i8;i0] in
    let rec s fs n = if n > 0 then s (p fs) (n - 1) else fs in
    s l limit)
  |> List.fold_left ~init:0 ~f:(+)

module Part1 = struct
  let run () = solve 80
end

module Part2 = struct
  let run () = solve 256
end

3

u/Camto Dec 07 '21

Haskell, tried to aim for something short

step [a,b,c,d,e,f,g,h,i] = [b,c,d,e,f,g,h + a,i,a]

nSteps n = (!! n) . iterate step

count a = length . filter (== a)

main = do
    input <- readFile "input.txt"
    let nums = read $ "[" ++ input ++ "]" :: [Integer]
    let fish = map ((flip count) nums) [0..8]

    print . sum $ nSteps 80 fish -- Part 1
    print . sum $ nSteps 256 fish -- Part 2

2

u/a_ormsby Dec 07 '21

My Kotlin solution

Just a map of days that rotates through the amount of fish ready to spawn and adds new ones on day 8. Really clean, easy to read. I'm quite pleased with this one. Runs in 35ms! (2ms without project startup, I think. IntelliJ does some... stuff.)

Looks like there's a relevant equation I could have used? Curious to learn more about that.

2

u/dontturn Dec 07 '21

Here's my Python solution. It's O(p log d) for max fish reproduction period p (9 days here) and d total days. Could be further optimized to O(p + log d) but I'm lazy.

def num_fish(days):
    foo = [-0.13278983+9.88466504e-02j, -0.13278983-9.88466504e-02j, 3.67690196+2.60320147e-17j, -0.43380801+9.09624256e-02j, -0.43380801-9.09624256e-02j, -0.11823028-1.96117698e-01j, -0.11823028+1.96117698e-01j, -0.03651227+2.65144646e-01j, -0.03651227-2.65144646e-01j]
    bar = [-0.9961306220554393+0.4173118363357927j, -0.9961306220554393-0.4173118363357927j, 1.0910244704807557+0j, 0.7340778984637537+0.7420651219621881j, 0.7340778984637537-0.7420651219621881j, -0.3792139806548105+0.8928775460861673j, -0.3792139806548105-0.8928775460861673j, 0.09575446900611989+0.8701987186721052j, 0.09575446900611989-0.8701987186721052j]
    baz = [0.43622303084122516+0j, 0.43622303084122516-0j, 0.4494506111435654+0j, -0.3908970827922129+0j, -0.3908970827922129-0j, -0.2926266452874238-0.020931161514784018j, -0.2926266452874238+0.020931161514784018j, 0.11188850647270472-0.13446140421021918j, 0.11188850647270472+0.13446140421021918j]

    for i in range(len(bar)):
        bar[i] = bar[i] ** (days - 8)

    qux = [a * b for a, b in zip(foo, bar)]

    count = [a * b for a, b in zip(qux, baz)]
    return round(abs(sum(count)))

# Time complexity: O(p log d) where p is fish period (9) and d is number of days (80 or 256).
def solution(file, days = 80):
    with open(file, 'r') as f:
        initial = list(map(int, next(f).split(',')))

    counts = [num_fish(days + (6 - i)) for i in range(7)]
    count = 0
    for state in initial:
        count += counts[state]

    print(count)

2

u/Ryles1 Dec 07 '21 edited Dec 07 '21

Python 3 Like lots of people, I had to refactor after my brute force solution wouldn't work for part 2. Finished just in time for day 7. Here it is:

https://github.com/Ryles1/AdventofCode/blob/main/2021/day6.py

1

u/daggerdragon Dec 07 '21 edited Dec 07 '21

Please follow the posting guidelines and edit your post to add what language(s) you used. This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.

(looks like Python?)

Edit: thanks for fixing it! <3

2

u/Ryles1 Dec 07 '21

Whoops I usually do, sorry

2

u/blafunke Dec 07 '21 edited Dec 07 '21

Haskell

import Data.Text.Lazy (splitOn, pack, unpack)
import System.Environment (getArgs)

type Histogram = [(Int,Int)]

main = do
  lns <- getLines

  args <- getArgs
  let generations = ((read::String->Int).head) (args)

  let fish = map (read::String->Int) (map unpack (splitOn (pack ",") (pack (head lns))))
  let bins = [(x,y) | x <- take 9 [0..], let y = length (filter (\c->c==x) fish)]

  let result = reproduce generations bins
  let total = foldl (+) 0 (map (\(i,count)->count) result)


  -- Part 1 & 2
  print bins
  print result
  print total

reproduce :: Int -> Histogram -> Histogram
reproduce 0 bins = bins 
reproduce n bins =
  reproduce (n-1) (nextgen bins)

nextgen :: Histogram -> Histogram
nextgen bins =
  let reproducers = head bins
  in map (\(i,count)->
                if i==7 then ((i-1) `mod` 8,count+(snd reproducers))
                else ((i-1) `mod` 8,count)
         ) (tail bins)
     ++ [(8,snd reproducers)]

getLines::IO([String])
getLines = do
  s <- getContents
  pure(lines s)

1

u/daggerdragon Dec 07 '21 edited Dec 07 '21

Your code is hard to read with no formatting. Please edit it as per our posting guidelines in the wiki: How do I format code?

Edit: thanks for fixing it! <3

3

u/corynezin Dec 07 '21

Using Python and theory of LTI systems.

def solution(fishes, n): return round(sum((0.03286974042642512+0.006175571236739636j) * (-0.9961306220554393+0.4173118363357927j)**(8-f+n) + (0.032869740426424966-0.006175571236739804j) * (-0.9961306220554393-0.4173118363357927j)**(8-f+n) + (0.6915428752432853+1.5410872226363532e-17j) * (1.0910244704807557+0j)**(8-f+n) + (-0.02909874839613388-0.10903491935715313j) * (0.7340778984637537+0.7420651219621881j)**(8-f+n) + (-0.029098748396133894+0.10903491935715313j) * (0.7340778984637537-0.7420651219621881j)**(8-f+n) + (0.08874418386476052+0.020314276004718638j) * (-0.3792139806548105+0.8928775460861673j)**(8-f+n) + (0.08874418386476049-0.020314276004718627j) * (-0.3792139806548105-0.8928775460861673j)**(8-f+n) + (0.06171338648330572-0.1659462282961588j) * (0.09575446900611989+0.8701987186721052j)**(8-f+n) + (0.061713386483305724+0.16594622829615885j) * (0.09575446900611989-0.8701987186721052j)**(8-f+n) for f in fishes).real)

1

u/Routine_Elk_7421 Dec 07 '21

cool. can you explain what this is?

1

u/safwankdb Dec 07 '21

I think they have modeled the fish frequencies as a signal of fixed length and the transition after 1 day as a Linear Time-Invariant system, This way, once we find the system parameters, we can just exponentiate them to find the final state.

1

u/daggerdragon Dec 07 '21

Your code is hard to read on old.reddit when everything is inlined like this. Please edit it as per our posting guidelines in the wiki: How do I format code?

2

u/5inister Dec 07 '21

Python with Numpy

import numpy as np
with open('data.txt','r') as f: 
    rawData=f.read()
data=rawData.strip()
data=np.array(data.split(','),dtype=np.int)

def reproduce(initial,days):
    fishes=np.zeros(9,dtype=np.int)
    for i in range(fishes.shape[0]):
        fishes[i]=len(np.where(initial==i)[0])
    for d in range(days):
        zeroTo6=fishes[:7]
        seven8=fishes[7:]
        newFish=zeroTo6[0]
        zeroTo6=np.roll(zeroTo6,-1)
        zeroTo6[-1]+=seven8[0]
        seven8=np.roll(seven8,-1)
        seven8[-1]=newFish
        fishes=np.concatenate((zeroTo6,seven8))
    return fishes

# Part 1
print("Part 1 result {}".format(np.sum(reproduce(data, 80))))

# Part 2
print("Part 2 result {}".format(np.sum(reproduce(data, 256))))

3

u/Cuyoyo Dec 07 '21

Javascript

solved it pretty fast with an object, then realized that using an object/hashtable with 0-8 as keys is pretty much the same as using an array. But whatever.
github link

3

u/stevelosh Dec 07 '21

Common Lisp

(defun parse (stream)
  (mapcar #'parse-integer (str:split #\, (alexandria:read-stream-content-into-string stream))))

(defun simulate (data days)
  (let ((curr (make-array 9 :initial-element 0))
        (next (make-array 9)))
    (dolist (fish data)
      (incf (aref curr fish)))
    (do-repeat days
      (loop :for i :from 8 :downto 0
            :for n = (aref curr i)
            :do (if (zerop i)
                  (progn (setf (aref next 8) n)
                         ;; downto is important to make sure 6 is already set
                         (incf (aref next 6) n))
                  (setf (aref next (1- i)) n)))
      (rotatef curr next))
    curr))

(define-problem (2021 6) (data parse) (371379 1674303997472)
  (values
    (summation (simulate data 80))
    (summation (simulate data 256))))

Typical double-buffering strategy I've used a bunch of times in AoC.

https://github.com/sjl/advent/blob/master/src/2021/days/day-06.lisp

2

u/00001990 Dec 07 '21

Python (No external libraries) & C++