Advent of Code Day 5!

directed acyclic graphs!

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

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

Like yesterday, I won’t be covering any feature of Raku in particular. I’ll explain new features as we use them.

Part 1

We are given a list of page ordering rules, and potential update orders. The page ordering rules give us a partial ordering of the pages, and thus can be viewed as a Directed Acyclic Graph.

On the right is a visualization of the DAG for the sample input, where an edge a -> b means a must be printed before b.

my @sections = (open 'data.txt').split("\n\n");

my %rules is default(set());

for @sections[0].lines -> $line {
  my ($before, $after) = $line.split('|').List;
  %rules{+$before} (|)= +$after;
}

my $out_file = open 'rules.gv', :create:w;
$out_file.put("digraph graphname {");
for %rules.kv -> $before, $after_set {
  for $after_set.keys -> $after {
    $out_file.put("\t$before -> $after;");
  }
}
$out_file.put("}");

There are many ways to represent a DAG. One way, that uses data structures available in Raku’s standard library, is to construct a mapping of nodes to the nodes they point to.

First, we need to split the input into rules and updates:

my @sections = (open 'data.txt').split("\n\n");

Next, we construct a map from integers to sets:

my %rules is default(set());

We’ve seen the % sigil before on Day 1, but we haven’t used it yet. A variable with the % sigil is a Map. We set a default value for keys not in the map, set(); this will be useful later. (This makes sense as the default value: if a node is not in the graph, then it does not point to any other node.)

for @sections[0].lines -> $line {
  my ($before, $after) = $line.split('|').List;
  %rules{+$before} (|)= +$after;
}

Line 7 has a bunch of new syntax, so we’ll take it step-by-step:

• +$before and +$after: The prefix + converts strings to numbers. $before and $after are strings; we just read them from the file!

• In Raku, the map index syntax is { }.

• Here’s something you (probably) weren’t expecting: = is a metaoperator²! That means it can take another operator as an argument.

  In this case, we’re using the operator (|), which gives us the union of two sets, or the union of a set and a value.

Overall, line 7 adds $after to the set for before.

Next, we need to check each update line and see if it is properly ordered:

for @sections[1].lines -> $line {
  my @updates = $line.split(',').map(+*);
  my &check = -> $i, $u { @updates[($i+1)...*].all (elem) %rules{$u} };
  if @updates.kv.map(&check).all {
    $middle_sum += @updates[@updates.elems div 2];
  }
}

The .map(+*) is converting the updates into numbers, using the Whatever Star and the prefix + operator mentioned above.

The &check Block³ takes in an index and an element, and checks if all of the following elements are in the set corresponding to that element. Making the default value of %rules the empty set is useful here; no value is an element of the empty set.

For example, in the first sample update line “75, 47, 61, 53, 29”, if &check is called with index 2 (which means we are at element $u = 61), it will check if 53 and 29 are both in the set of nodes pointed to from 61.

We use the &check Block in our condition. If all of the update pages satisfy the check, we add the middle value to the middle sum.

Part 2

We’re told to sort each list of page update numbers according to our DAG.

We can reuse much of our Part 1 solution. In fact, the only thing that needs to change is how we process updates. Here is the version of that loop for Part 2:

for @sections[1].lines -> $line {
  my @updates = $line.split(',').map(+*);
  my &check = -> $i, $u { @updates[($i+1)...*].all (elem) %rules{$u} };
  next if @updates.kv.map(&check).all;

  my &compare = -> $a, $b {
    if    $a (elem) %rules{$b} { Order::More }
    elsif $b (elem) %rules{$a} { Order::Less }
    else                       { Order::Same }
  };
  $middle_sum += @updates.sort(&compare)[@updates.elems div 2];
}

This time, we skip (line 14) all the correct lines. We define a custom compare function: If $b points to $a, then $a should come later, and vice versa. If neither points to the other, then it doesn’t matter what order they are in.

15 lines of code for part 1, and 19 lines of code for part 2. Not bad! What about performance? On my machine, I measured (with hyperfine) a runtime of around half a second for each of part 1 and 2.

Raku has excellent built-in profiling support: run a program with the --profile flag and you’ll get a standalone html file with tons of information (including a call graph and fine-grained stats about the GC and the JIT). From the profiles, the runtime behavior was pretty similar: we spent more than 90% of our time executing (instead of GC), and more than half the time was spent in &check.

I’ll write more about optimizing Raku programs in the future.