Advent of Code 2021 - Day 6

Learning Questions & Discussions Coding Challenges
21

Looking at the replies, nothing special with my solution. Frequencies and updates. Just that I used reduce.

Enum.reduce(1..256, start_state, fn _, state ->
  state
  |> Enum.reduce(%{}, fn
    {0, c}, curr_state ->
      curr_state |> Map.update(6, c, &(c + &1)) |> Map.update(8, c, &(c + &1))

    {age, c}, curr_state ->
      curr_state |> Map.update(age - 1, c, &(c + &1))
  end)
end)
|> Map.values()
|> Enum.sum()

Full Livebook https://github.com/Klohto/AdventOfCode/blob/main/2021/day6.livemd

2 Likes
22

I tried to solve the problem in a mathematical way, like a Fibonacci sequence. I believe there’s a better way than mine in math.

solution

1 Like
23

Do you have your DynamicSupervisor solution somewhere? Thanks

24
25

Cool. We tried to build a DynamicSupervisor solution today at work. Our solution was similar to yours. We quickly stumbled into the process limit of the VM. We could increase it enough for part 1 to work, but the maximum amount was still not enough for part 2 without going multi-node. Maybe we can explore it next time :slight_smile:

Also we tried casting but then the count of fishes would be wrong.

26

That’s exactly what I meant when I ended my comment with “and boom.”

:slight_smile:

27

I think there is an elegant mathematical way, using linear algebra: the amount of fish that have specific day can be modeled as a vector, where element 0 is the amount of fish that have 0 days left. Total number of fish at any given day is the sum of elements of that vector.

We can multiply that vector with a matrix K, that produces the next day’s fish counts. Here’s what K could look like (apologies for Octave/Matlab syntax, I used that to verify the approach):

K0 = [
  0 0 0 0 0 0 1 0 1;
  1 0 0 0 0 0 0 0 0;
  0 1 0 0 0 0 0 0 0;
  0 0 1 0 0 0 0 0 0;
  0 0 0 1 0 0 0 0 0;
  0 0 0 0 1 0 0 0 0;
  0 0 0 0 0 1 0 0 0;
  0 0 0 0 0 0 1 0 0;
  0 0 0 0 0 0 0 1 0
];

# Fun fact: matrix for computing any initial condition to day 80 is:
K80 = K0 ^ 80;

# Get day 1 from day 0 counts per day:
v1 = v0 * K;

# Get day 80 from day 0 counts per day:
v80 = v0 * K80;

Full code here for my input: aoc2021_day6.m

I’ve yet to figure out how to do this in Elixir fluently and it seems it’s time to learn some Nx. :grin:

4 Likes
28

OK, that was more fun than expected. (pun not intended)

Nx solution module over here: Aoc2021.Day6.LinAlg

Nx multiply and especially Nx.power are done by element, so I had to resort to reduce when multiplying the tensors. Otherwise it pretty much follows the Octave style. I like Nx so far, this was easy to install and play around with.

4 Likes
29

Thank you for sharing this! This matrix is awesome!

I watched @josevalim 's video on day 6, and oh man, it was so amazing and blew my mind. In the end, he tried the same matrix idea with Nx. It was so delightful to watch him thinking, solving, and explaining.

3 Likes