AoC 2022/22 - Dicey assumptions

TL;DR

On with Advent of Code puzzle 22 from 2022: where we have to move over a cube.

Wow yes, two posts today!

The 22th puzzle starts somehow quiet; there’s a strange field where we have to move a cursor, taking turns or going ahead according to the inputs.

Let’s start from the inputs, then. Here is the example (I hope copying it here qualifies as fair use):

        ...#
        .#..
        #...
        ....
...#.......#
........#...
..#....#....
..........#.
        ...#....
        .....#..
        .#......
        ......#.

10R5L5R10L4R5L5

This is how I addressed it:

sub get-inputs ($filename) {
   my ($lines, $code) = $filename.IO.slurp.split(/\n\n+/);
   my @moves = $code.trim.split(/ \d+ /, :v, :skip-empty)
      .map: { $_ ~~ Match ?? $_.Int !! $_ };
   return {:$lines, :@moves};
}

The file is completely slurped into memory and immediately split into the two parts, i.e. the initial field and the movement instructions, based on the empty line in between. Reading everything in memory at once makes sense for this kind of applications, because we’re not dealing with huge amounts of data and we would read and store everything in any case.

We will see shortly how to cope with the field; The moves are a sequence of digits and direction letters, so I opted for spliting on the numbers, but keeping them with the :v adverb, while also removing leading and trailing empty stuff with :skip-empty.

I’ve been looking for :skip-empty for some time, as it makes the behaviour closer to what’s available in Perl, while still allowing for different alternatives. I would have probably kept it as default, but it’s a matter of taste.

The split leaves us with a mix of letters and matches, the latter containing the integer amounts for advancing our “cursor”; to complete the parsing operations, we turn them into integers so that we give out only letters or integers.

Part 1: Pac-Man

In part 1, the movement rules tell us that we’re stopped by walls # but not by edges, that work Pac-Man style.

This is interesting, because the field has an irregular shape, so empty positions are actually “non existent” ones and have not to be considered. Which means that each row or column will have its own rules for wrapping at the edges.

There’s also another matter, which is important for a generic solution: do we have to cope with exiting from one side and landing on another side, like in the following picture?

  ...        ...
  ...---->---...
  ...        ...
.................

As it became clear in part 2, this cannot happen, but still.

The solution… is this:

sub part1 ($inputs) {
   my $field = Field.new(lines => $inputs<lines>);
   $field.apply($inputs<moves>);
   return 1004 + $field.y * 1000 + $field.x * 4 + $field.d;
}

The hard work is done by the Field class, which implements all rules for moving in part 1.

I suspected that the “only” change for part 2 would be different wrapping rules, and I was right to a point. Well, I did not anticipate how the wrapping rules would change, I though it would just go “to the other side”, flipping the things, but it was not like this.

So… the class. We start with the member variables and the initialization. I opted for using TWEAK, because the only thing that comes upon initialization is the text containing the field, but we want to represent it as a list of lines, as well as keeping track of other data like the number of columns in $.n-cols, or the “current” position with $.x and $.y. The clone and dump method are there just for debugging purposes and can be disregarded.

class Field {
   has @.lines;
   has $.x = 0;
   has $.y = 0;
   has $.d = 0;
   has $.n-cols;

   submethod TWEAK (:$lines) {
      @!lines = $lines.split(/\n+/, :skip-empty);
      $!n-cols = @!lines».chars.max;
      $_ ~= (' ' x ($!n-cols - .chars)) for @!lines;
      $!x = @!lines[0].index('.');
   }
   method clone { nextwith :lines(@!lines.clone), |%_ }

   method dump {
      say "($!x, $!y), facing {self.direction}, width $!n-cols, map:";
      say '   +', ('-' x $!n-cols), '+';
      @.lines.map: { "   |$_|".say };
      say '   +', ('-' x $!n-cols), '+';
   }

Then we have a couple of helpers to abstract transforming a direction into its own character, as well as actually placeing the cursor in a position:

   method direction { '>v<^'.substr($!d, 1) }

   method place ($c = Nil) {
      @!lines[$!y].substr-rw($!x, 1) = $c // self.direction }

Now we’re at the movement parts. We can do two kind of movements: turning on the spot, or advancing based on where we are and where we’re pointing to, applying the Pac-Man rules when applicable and stopping upon hitting a wall.

This seemed like the perfect thing to represent with multi methods, because the two different ways of moving are represented by different data types (Str for rotations, Int for translations):

   multi method move (Str $rotations, $place = True) {
      $!d = ($!d + ($_ eq 'R' ?? 1 !! 3)) % 4 for $rotations.comb;
      self.place if $place;
   }
   multi method move (Int $steps, $place = True) {
      state @deltas = [1, 0], [0, 1], [-1, 0], [0, -1];

      self.place if $place;

      my ($dx, $dy) = @deltas[$!d].Slip;
      my ($x, $y) = $!x, $!y;
      for ^$steps {
         my $c;
         loop {
            $x = ($x + $dx) % $!n-cols;
            $y = ($y + $dy) % @!lines;
            last if ($c = @!lines[$y].substr($x, 1)) ne ' ';
         }

         last if $c eq '#'; # The Wall

         # save position, rinse, repeat
         ($!x, $!y) = $x, $y;
         self.place if $place;
      }
   }

We conclude with the method to apply a list of @moves, sequentially:

   method apply (@moves) {
      self.move($_, True) for @moves;
      return self;
   }
}

So much for part 1!

Part 2 - Like an ant on a cube

The mystery unfolds, and it’s dicey: the shape represents a cube! This means that exiting on an edge in one direction, generally means landing on an edge in a different direction and we have to figure this out.

I opted for a generic solution, instead of focusing on my input only. At the end of the day, anyway, it seems that we all received a variation of the field over the same template shape.

Each face of the cube has four edges, connecting the face to four other faces. I decided that I wanted to represent the cube as a graph of these “side on a face”, where each side has three connected peers:

  • one on the same face, going clockwise (cw)
  • one on the same face, going counter-clockwise (ccw)
  • one on the adjacent face (adj).

This lands us on this representation:

class DieSide {
   has $.face;
   has $.d;
   has $.cw  is rw = Nil;
   has $.ccw is rw = Nil;
   has $.adj is rw = Nil;

   method attach ($other-side) {
      self.adj = $other-side;
      $other-side.adj = self;
      return self;
   }

   method id { "{$!face.name}/$!d" }
   method adj-id { defined($!adj) ?? $!adj.id !! '---' }
   method dump {
      my ($cw, $ccw, $adj) = ($!cw, $!ccw, $!adj).map: { $_ ?? $_.id !! '' };
      say "{self.id} cw<$cw> ccw<$ccw> adj<$adj>" }
}

The $.d member represents the direction that the side is pointing towards (from the point of view of the puzzle input).

Four DieSide are cointained in a DieFace, which takes care of their initialization and gives support to some debugging:

class DieFace {
   has $.name;
   has $.x;
   has $.y;
   has @.sides is rw; # a face has four sides
   submethod TWEAK (:$!name, :$!x, :$!y) {
      for ^4 -> $d {
         my $side = DieSide.new(face => self, :$d);
         if @!sides {
            $side.ccw = @!sides[*-1];
            @!sides[*-1].cw = $side;
         }
         @!sides.push: $side;
      }
      @!sides[0].ccw = @!sides[*-1];
      @!sides[*-1].cw = @!sides[0];
   }
   method attach ($other-face, $d) {
      @!sides[$d].attach($other-face.sides[(2 + $d) % 4]);
      return self;
   }
   method stringify {
      my ($e, $s, $w, $n) = @!sides».adj-id;
      return join "\n",
         "($!x, $!y)",
         '+-----------+',
         "|    $n    |",
         '|           |',
         "|$w [{self.name}] $e|",
         '|           |',
         "|    $s    |",
         '+-----------+',
         '';
   }
}

Again, TWEAK is helping us to perform some non-standard initialization. The four sides are immediately connected in a merry-go-round, while all the $.adj peerings are left dangling. This is where method attach() will come handy later.

The two coordinate values $.x and $.y represent the upper-left corner of the face inside the input data.

We can assemble six faces in a Die:

class Die {
   has %.faces;
   submethod TWEAK (:$lines, :$face-size) {
      my @macro-map;
      my $y = 0;
      my $n-faces = 0;
      while $y * $face-size < $lines.elems {
         @macro-map.push: [];
         my $x = 0;
         while $x * $face-size < $lines[0].chars {
            my $face = Nil;
            if $lines[$y * $face-size].substr($x * $face-size, 1) ne ' ' {
               $face = DieFace.new(name => ++$n-faces, :$x, :$y);
               $face.attach(@macro-map[$y][$x - 1], 2) # to west
                  if $x > 0 && defined @macro-map[$y][$x - 1];
               $face.attach(@macro-map[$y - 1][$x], 3) # to north
                  if $y > 0 && defined @macro-map[$y - 1][$x];
               %!faces{"$x,$y"} = $face;
            }
            @macro-map[$y].push: $face;
            ++$x;
         }
         ++$y;
      }
      loop {
         my $n-updates = 0;
         for %!faces.values -> $face {
            my $side = $face.sides[0];
            for ^4 {
               my $cw = $side.cw;
               if defined($side.adj) && defined($cw.adj) {
                  my $n1 = $side.adj.ccw;
                  if ! defined $n1.adj { # set new adjacency
                     $n1.attach($cw.adj.cw);
                     ++$n-updates;
                  }
               }
               $side = $cw; # go to next pair
            }
         }
         last if $n-updates == 0;
      }
   }
}

It only has a TWEAK method to initialize the die according to the input, taking care to create the six faces (in the while loop) and joining them to create the whole graph of adjacent face sided (in the loop).

The initial while loop is only able to set some of the adjacencies between DieSide objects; in particular, all those related to the shape edges will be left out for discovery, which is what is done in loop.

Building the whole graph can seem tricky, and it is to some extent. Here, we’re passing over all the faces, trying to do some “connection” work until there’s no more work to be done, as tracked by $n-updates.

The key insight here is that each face that has adjacencies on two consecutive sides has a potential for “closing a loop” of adjancencies. Let’s consider the following example:

+-----+-----+
|     |     |
|  A 2|4 B  |
|  1  |  x  |
+-----+-----+
|  3  |
|  C y|
|     |
+-----+

Face A already has adjacencies towards B (sides 2 and 4) and towards C (sides 1 and 3); these adjacencies allow us to also resolve the two sides marked as x and y, because the are each other’s adjacent, according to the cube unfolding rules.

The Die object starts with all the knowledge we need for properly moving over the input, so we can code the equivalent of the Field from part 1, i.e. our DicedField. We start just like before, with a couple of member variables more:

  • $.face-size to track the face size (this is 4 in the example input and 50 in the full input)
  • $.die to hold a Die object corresponding to the inputs.
class DicedField {
   has @.lines;
   has $.x = 0;
   has $.y = 0;
   has $.d = 0;
   has $.n-cols;
   has $.face-size;
   has $.die;

   submethod TWEAK (:$lines) {
      @!lines = $lines.split(/\n+/, :skip-empty);
      $!n-cols = @!lines».chars.max;
      $_ ~= (' ' x ($!n-cols - .chars)) for @!lines;
      $!x = @!lines[0].index('.');
      $!face-size = $!n-cols < 150 ?? 4 !! 50;
      $!die = Die.new(lines => @!lines, :$!face-size);
   }
   method clone { nextwith :lines(@!lines.clone), |%_ }

   method dump {
      say "($!x, $!y), facing {self.direction}, width $!n-cols, map:";
      say '   +', ('-' x $!n-cols), '+';
      @.lines.map: { "   |$_|".say };
      say '   +', ('-' x $!n-cols), '+';
   }

   method direction { '>v<^'.substr($!d, 1) }

   method place ($c = Nil) {
      @!lines[$!y].substr-rw($!x, 1) = $c // self.direction }

Again, we’re are the move point, and we use multi. Turning in-place is exactly like before, but moving in a “straight” line is a bit more convoluted, but definitely doable thanks to the Die:

   multi method move (Str $rotations, $place = True) {
      $!d = ($!d + ($_ eq 'R' ?? 1 !! 3)) % 4 for $rotations.comb;
      self.place if $place;
   }
   multi method move (Int $steps, $place = True) {
      state @deltas = [1, 0], [0, 1], [-1, 0], [0, -1];

      self.place if $place;

      my ($x, $y, $d) = $!x, $!y, $!d;
      my ($dx, $dy) = @deltas[$d].Slip;
      for ^$steps {
         $x = $x + $dx;
         $y = $y + $dy;

         my $in-bounds = (0 <= $x < $!n-cols) && (0 <= $y < @!lines);
         my $c = $in-bounds ?? @!lines[$y].substr($x, 1) !! ' ';
         if $c eq ' ' { # do the magic
            my $offset = ($d %% 2 ?? $!y !! $!x) % $!face-size;

            # get original die face
            my $dfx = $!x div $!face-size;
            my $dfy = $!y div $!face-size;
            my $face = $.die.faces{"$dfx,$dfy"};

            my $side = $face.sides[$d];
            my $landing-side = $side.adj;


            my $landing-face = $landing-side.face;
            my $target-d = $landing-side.d;

            my $target-src-d = ($target-d + 2) % 4;
            while $d != $target-src-d {
               $offset = $.face-size - 1 - $offset if $d %% 2;
               $d = ($d + 1) % 4;
            }

            $x = $landing-face.x * $!face-size;
            $y = $landing-face.y * $!face-size;
            if $d %% 2 {
               $x += $!face-size - 1 if $d > 1;
               $y += $offset;
            }
            else {
               $x += $offset;
               $y += $!face-size - 1 if $d > 1;
            }

            $c = @!lines[$y].substr($x, 1);
            ($dx, $dy) = @deltas[$d].Slip;
         }

         last if $c eq '#'; # The Wall

         # save position, rinse, repeat
         ($!x, $!y, $!d) = $x, $y, $d;
         self.place if $place;
      }
   }

   method apply (@moves) {
      self.move($_, True) for @moves;
      return self;
   }
}

Conclusions

We’re at the end of the ride, and I admit it’s been a fun one. You can find the full solution, too.

Stay safe!


Comments? Octodon, , GitHub, Reddit, or drop me a line!