Advent of Code Day 4!

2D list transformations!

I did Day 4 in Raku again! (Previously: Day 1 in Raku, Day 2 in Raku, Day 3 in Raku.)

As usual, I won’t re-describe the puzzles: take a look on Advent of Code.

Today, unlike the past two days, I won’t be covering any feature of Raku in particular. Instead, the focus today is on my solution to the puzzle. I will explain any new syntax we come across, though.

Part 1

There are four “cases” we need to search: horizontal, vertical, down-diagonal, and up-diagonal¹. The general strategy behind my solution for part 1 is “solve the horizontal case, then transform the other cases to the horizontal case”.

To demonstrate the transformations we’ll be implementing, I wrote the following CSS animations. Hover or press-and-hold any of the squares below to activate the animation!

my $file = open 'data.txt';
my @data = $file.lines.map: *.comb;
my $rows = @data.elems;
my $cols = @data[0].elems;

sub count_line(@line) {
  my $xmas = "XMAS".comb.list | "SAMX".comb.list;
  @line.rotor(4 => -3).grep(* eqv $xmas).elems
}

sub diagonals(@data) {
  my $starts_row = (0...$rows).map: { $_, 0 };
  my $starts_col = (1...$cols).map: { 0, $_ };

  my $starts = (|$starts_row, |$starts_col);

  my @diagonals = [] xx ($rows + $cols - 1);

  for $starts.kv -> $i, ($start_r, $start_c) {
    for ($start_r...$rows) Z ($start_c...$cols) -> ($r, $c) {
      @diagonals[$i].push(@data[$r][$c]);
    }
  }

  @diagonals
}

my $row_count  = [+] @data.map(&count_line);
my $col_count  = [+] ([Z] @data).map(&count_line);
my $down_count = [+] diagonals(@data).map(&count_line);
my $up_count   = [+] diagonals(@data.map: *.reverse).map(&count_line);

say $row_count + $col_count + $down_count + $up_count;

The power of Raku!

I’ll go over the solution one “chunk” at a time.

Solve the horizontal case

sub count_line(@line) {
  my $xmas = "XMAS".comb.list | "SAMX".comb.list;
  @line.rotor(4 => -3).grep(* eqv $xmas).elems
}

This is generally a combination of features we’ve seen before! The only new functions we’re using are .comb and .list. .comb with no arguments gives us a Seq (a lazy list) of the characters in the string, and .list makes the list not-lazy, which we need since we’re constructing an any Junction (discussed on Day 2).

The call to rotor was also discussed on Day 2; it gives us an overlapping window through the @line array. We then check if the windows are equivalent to $xmas, and count the ones that are.

Overall, this subroutine counts the number of (potentially overlapping) “XMAS” and “SAMX” strings in a line. This solves the horizontal case! … almost. We still need to map this function over all the lines and add up the counts. We do that here:

my $row_count  = [+] @data.map(&count_line);

This is stuff we’ve seen before! This line calls the count_line subroutine on every line, and then we sum up all the counts.

Transform the other cases to the horizontal case

Let’s look at the vertical case:

my $col_count  = [+] ([Z] @data).map(&count_line);

The only difference here is that we are using [Z] @data. We’ve seen the zip operator and reduction metaoperator before, on Day 1, but we haven’t seen them used together yet.

What the combination of them does is “zip each component list together into a new 2D list”. In other words, an elegant transpose! This converts the vertical case to the horizontal case.

The diagonal cases are a bit more involved.

sub diagonals(@data) {
  my $starts_row = (0...$rows).map: { $_, 0 };
  my $starts_col = (1...$cols).map: { 0, $_ };

  my $starts = (|$starts_row, |$starts_col);

  my @diagonals = [] xx ($rows + $cols - 1);

  for $starts.kv -> $i, ($start_r, $start_c) {
    for ($start_r...$rows) Z ($start_c...$cols) -> ($r, $c) {
      @diagonals[$i].push(@data[$r][$c]);
    }
  }

  @diagonals
}

There’s new syntax here. The ones that stick out immediately are ..., which gives us a range from the left value to the right value. $_ is also new; in a map or for loop (among other places) you can use $_ instead of defining an argument. Also, note that parentheses around lists are optional in Raku. So, the first map above is equivalent to .map: -> $a { ($a, 0) }.

This function performs the down-diagonal transformation.

We generate a list of starting indices $starts, which tells us where each diagonal starts. The | operator is similar to the ... spread operator in Javascript and Python: it flattens the list (or in this case, range) into the surrounding list.

We also initialize some lists to hold the diagonals. We will have rows + cols - 1 diagonals, and the xx operator just repeats the left argument right-argument times.

Then, we iterate over the starting indices (.kv gives us index, value instead of just value). Inside, we zip together two ranges, from the starting row index to the edge, and the starting column index to the edge. Zip stops as soon as one finishes, so this prevents us from going “over the edge” (out of bounds). We push the data at each of those indices to the corresponding diagonal list, then return the diagonals.

We use this function here:

my $down_count = [+] diagonals(@data).map(&count_line);
my $up_count   = [+] diagonals(@data.map: *.reverse).map(&count_line);

For $up_count, we map .reverse over each line². This transforms an up-diagonal to a down-diagonal (as shown in the animation above).

Part 2

In part 2, we need to find cases where there are MASs in the shape of an X, like here:

.....
.M.S.
..A..
.M.S.
.....

I wanted to reuse most of my code from Part 1, so I decided to scan for “MAS” and “SAM” in both diagonals, keeping track of where the “A”s are. Then, we can find the intersection between the two sets.

my $file = open 'data.txt';
my @data = $file.lines.map: *.comb;
my $rows = @data.elems;
my $cols = @data[0].elems;

sub find_in_diagonal(@data) {
  my $starts_row = (0...$rows).map: { $_, 0 };
  my $starts_col = (1...$cols).map: { 0, $_ };

  my $starts = (|$starts_row, |$starts_col);

  my @locations = [];

  my @current = 0 xx 3;
  my $xmas = "MAS".comb.list | "SAM".comb.list;

  for $starts.kv -> $i, ($start_r, $start_c) {
    for ($start_r...$rows) Z ($start_c...$cols) -> ($r, $c) {
      @current.shift;
      @current.push: @data[$r][$c];
      if @current.List eqv $xmas {
        @locations.push(($r - 1, $c - 1));
      }
    }
  }

  @locations
}

my @down_locs = find_in_diagonal(@data).map: -> ($a, $b) { $a * $cols + $b };
my @up_locs = find_in_diagonal(@data.map: *.reverse).map: -> ($a, $b) { $a * $cols + ($cols - $b - 1) };

my @locations = (set @down_locs) (&) (set @up_locs);

say @locations.elems;

I was able to reuse much of the part 1 solution! The key differences are in two spots:

  my @locations = [];

  my @current = 0 xx 3;
  my $xmas = "MAS".comb.list | "SAM".comb.list;

  for $starts.kv -> $i, ($start_r, $start_c) {
    for ($start_r...$rows) Z ($start_c...$cols) -> ($r, $c) {
      @current.shift;
      @current.push: @data[$r][$c];
      if @current.List eqv $xmas {
        @locations.push(($r - 1, $c - 1));
      }
    }
  }

Here, we again iterate over each diagonal. The difference here is that we keep track of 3 values along the diagonal in the array @current. For each diagonal value, we “shift” the head of @current off of the array, then push the new character onto the end. After that, we check if @current is either “MAS” or “SAM”. If so, we push the location of “A” (always one position behind!) onto @locations.

my @down_locs = find_in_diagonal(@data).map: -> ($a, $b) { $a * $cols + $b };
my @up_locs = find_in_diagonal(@data.map: *.reverse).map: -> ($a, $b) { $a * $cols + ($cols - $b - 1) };

my @locations = (set @down_locs) (&) (set @up_locs);

We are mapping the found locations into integers. Why? We want to use a Set to find the intersection between the locations. However, the locations are Lists. Sets have to hold ValueTypes, and Lists are not ValueTypes; while Lists are immutable, they can hold mutable items.

Also, we need to transform the up-diagonal locations back, hence the $cols - $b - 1, which undoes the .reverse.

Finally, we convert each array into a Set and find the intersection using (&) between the two sets.

Hopefully this was an interesting solution! I didn’t get to show off new Raku features in today’s puzzle, but I felt my approach to the puzzle was worth writing about!

I will leave you with a quote from my friend Arjun:

raku is built for aoc

Exactly! As I’ve written before, Raku is really nice for one-off scripts!