TL;DR

On with Advent of Code puzzle 13 from 2022: playing with nested lists.

This day’s puzzle has a few interesting traits that stimulated me to learn a bit more about Raku. I still didn’t grasp things… but at least I’ll have something to look back in the future.

A first challenge was reading the inputs, i.e. something like this:

[1,1,3,1,1]
[1,1,5,1,1]

[[1],[2,3,4]]
[[1],4]

[9]
[[8,7,6]]

[[4,4],4,4]
[[4,4],4,4,4]

[7,7,7,7]
[7,7,7]

[]
[3]

[[[]]]
[[]]

[1,[2,[3,[4,[5,6,7]]]],8,9]
[1,[2,[3,[4,[5,6,0]]]],8,9]

As somebody pointed out either in this challenge or in another one, it’s easy to parse each line leveraging any JSON parser. But hey! We’re reinventing wheels here, so I ventured into using grammars.

Here’s what I came up with:

sub parse-expression ($expr) {
   grammar G {
      rule TOP              { <parenthesized> }
      rule element          { <intvalue> | <parenthesized> }
      rule intvalue         { 0 | <[ 1 .. 9 ]>\d* }
      rule parenthesized    { '[' [<list-of-elements>]? ']' }
      rule list-of-elements { <element> [ ',' <list-of-elements> ]? }
   }
   class Collect {
      method TOP ($/) { make $<parenthesized>.made }
      method element ($/) {
         make $<intvalue> ?? $<intvalue>.made !! $<parenthesized>.made;
      }
      method intvalue ($/) { make $/.Int }
      method parenthesized ($/) {
         make $<list-of-elements> ?? $<list-of-elements>.made !! $[];
      }
      method list-of-elements ($/) {
         my $retval = [ $<element>.made ];
         $retval.push: $<list-of-elements>.made.Slip if $<list-of-elements>;
         make $retval;
      }
   }
   return G.parse($expr, actions => Collect.new).made;
}

I struggled a bit with the Collect class, but maybe I got the gist of the make/made pair. We’ll see. Another thing that bite me was handling of empty sub-lists, I had to add the $ in $[] to avoid dissolving it in the upper level container. This is a bit counterintuitive to me, because I expect Raku to containerize by default (something I complained about in the past), and yet it does not here. When I needed it!

Others used a simpler grammar. As an example, this solution (by s3aker, again) has this interesting shorter grammar:

grammar DeepArray {
    rule TOP     { '[' ~ ']' <element>* % ',' }
    rule element { <number> || <TOP> }
    token number { \d+ }
}

class DeepArrayActions {
    method TOP($/)     { make $<element>».made.Array }
    method element($/) { make $<number> ?? $<number>.made !! $<TOP>.made }
    method number($/)  { make $/.Int }
}

Compared to mine, I can tell that TOP and parenthesized were collapsed into one, list-of-elements is represented in some idiomatic way and there was little fussing about properly representing non-negative integers. I’ll have to dig the usage of ~ in TOP (as I get it, % is for describing lists with a separator) as well as using || instead of | in the alternation for element.

The comparison algorithm seemed perfect for coding the same function with different inputs, so I went for multi:

multi sub compare (Int $left, Int $right) { return ($right <=> $left).Int }
multi sub compare (    @left, Int $right) { return compare(@left, [$right]) }
multi sub compare (Int $left,     @right) { return compare([$left], @right) }
multi sub compare (@left is copy, @right is copy) {
   while @left && @right {
      my $comparison = compare(@left.shift, @right.shift);
      return $comparison if $comparison != 0;
   }
   return @left ?? -1 !! @right ?? 1 !! 0;
}

Part 1 was easy at this point, because the upper-level comparison tells us whether the ordering is correct or not by simply checking that the output value is +1. It was also a good occasion to use gather/take, which I love (albeit I’ve been warned about its inefficiency in the past).

sub part1 ($inputs) {
   (gather for $inputs.kv -> $i, ($left, $right) {
      my $is_correct = compare($left, $right) > 0;
      take $i + 1 if $is_correct;
   }).sum
}

This comparison function allows us to use sort, so it’s just a matter of injecting the two markers and find them out after sorting the whole list of signals:

sub part2 ($inputs) {
   my $two = [[2],];
   my $six = [[6],];
   my @all = $two, $six, (gather $inputs.map({.take for @$_})).Slip;
   my @sorted = @all.sort({ compare($^a, $^b) }).reverse;
   my %targets = ($two, $six).map({$_.raku}).Set;
   return [*] (^@sorted).grep({@sorted[$_].raku ∈ %targets }).map: * + 1;
}

Full solution.

Stay safe!