Advent of Code 2021: Day 6

I’ve been a bit busy so I skipped doing the tasks in Raku for a couple days, but today’s seemed fun. As usual SPOILERS ahead.

So the problem is basically: you have certain amounts of fish which have a “spawn-timer”, when they reach it they get reset to 6, and create a new fish with a spawn timer set at 8. Given an initial list of fish, we want to know how many fish we have after some days.

You, Clever Reader will certainly have noticed that we have an exponential behaviour: at each step we generate more fish, which will generate more more fish next time, and more more more fish and so on§.

The abstract solution in my mind would be:

• set the initial values in some container structure
• call some step function the given amount of days
• count the total entries in the container

This, more or less

sub solve(@ints, $days) { # ints is something like [1, 2, 3, 3, 1, 4..]
  <whatever>
  step(<whatever>) for ^$days;
  [+] <whatever>;
}

the only interesting thing here is the construct

<do-something> for ^$number

where ^$number is a short form to define a range from 0 to $number and the rest is a short form to do a loop over the right hand size of the for keyword.

Extended this might look like

for 0..$days -> $day { <do-something> }

which I find less entertaining§.

The question to answer next is: what should we use as container?

Raku obviously has a Hash class, and we could initialize it with a default and then iterate over the initial values to build.

> my @ints= [1, 3, 3, 3, 3, 2]
[1 3 3 3 3 2]
> my %counts is default(0);
{}
> %counts{$_}++ for @ints
Nil
> %counts
{1 => 1, 2 => 1, 3 => 4}

The only new bit we see is the is default annotation that builds a container with a default value. But it seemed weird I have to do this, surely Raku has some builtin way to count things, like Ruby’s Enumerable#tally ?

And of course it does. It has More Than One Way To Do It, of course. For example, it provides a Bag class which is an immutable container for counting items, and can be extracted from another sequence trivially

> my @ints = [1, 3, 3, 3, 3, 2]
[1 3 3 3 3 2]
> @ints.Bag
Bag(1 2 3(4))

And a corresponding BagHash which returns a mutable container for counting.

Being a map from Any to Int these also come with a nice default, so when we access a missing item we get 0

> my $bh = @ints.BagHash
BagHash(1 2 3(4))
> $bh{1}
1
> $bh{2}
1
> $bh{3}
4
> $bh{99}
0

Wait, you might say, why are you using a scalar for that object, instead of a hash? Shouldn’t it be %bh rather than $bh?

The answer is: I don’t really know§

> my %bh-as-hash = $bh
{1 => 1, 2 => 1, 3 => 4}
> %bh-as-hash{99}  # no default in the hash!
(Any)
> $bh{99}          # still default in the BagHash!
0
> $bh{99} = 3      # you can update the BagHash
3
> $bh{99}
3
> %bh-as-hash{99}  # but the hash is unaffected
(Any)

You can alternatively use the := binding operator, which performs an assignment without casting:

> my %bh-as-hash-casted := $bh  # notice the representation
BagHash(1 2 3(4) 99(3))
> %bh-as-hash-casted{100} = 100 # it's the same object!
100
> $bh{100}
100

So our full solve can be

sub solve(@ints, $days) {
  my $counts = @ints.BagHash;
  step($counts) for ^$days;
  [+] $counts.values;
}

Now, how does the step function look? It is pretty straightforward, but it has a tricky bit

sub step($counts) {
  my $old = $counts.clone;
  for 8...0 -> $idx {
    $counts{$idx} = $old{$idx + 1};
    if $idx == 0 {
      $counts{8} = $old{0};
      $counts{6} += $old{0};
    }
  }
}

Do you see the… oddity? Look at this:

> for 1..3 -> $i { say $i }
1
2
3
> for 1...3 -> $i { say $i }
1
2
3
> for 3..1 -> $i { say $i }
Nil
> for 3...1 -> $i { say $i }
3
2
1

you cannot iterate in reverse one of those! This is because the .. operator builds a Range while ... builds a Seq. A Range is list of consecutive numbers, with a beginning and an end, while a Seq is something that can be iterated over.

So there are no numbers in an inverse Range, and if you iterate over it you get zero iterations. In my very humble rubyist opinion, this is very confusing™ , but I guess real Raku people are used to it.

Back to our task: of course, the Astute Reader will have noticed we can do this more tersely by simply shifting the array and adding it to itself, and then brining back the extra items. This is a simpler solution, and it’s pretty nice, but we need to build a list rather than a BagHash:.

sub solve2(@ints, $days) {
  my @list is default(0);      # create a list with default value 0
  @list[$_]++ for @ints;       # add all the fish to it
  step2(@list) for ^$days;     # do the steps
  [+] @list;                   # add up the values in the list
}

I have a feeling the first two lines can be collapsed, but I don’t know how, if you have an idea please let me know in the comments.

Our step function becomes very small

sub step2(@counts) {
  @counts.rotate;
  @counts[6] += @counts[8];
}

And honestly, I feel this is as expressive as it can be.

See you next time!