AoC 2016/11 - New parsing


On with Advent of Code puzzle 11 from 2016: parsing inputs to fit the New representation.

First of all, we will have to read data and fit it in the new representation. Let’s start with some variables to help us read the inputs correctly:

my $generators = 0;
my $microchips = 0;
my $n_elements = 0;

my %floor_shift_of = (
   fourth => 0,
   third  => 8,
   second => 16,
   first  => 24,
my %mask_of    = ();
my $next_mask  = 0x1;


my $start = {
   elevator   => 3,
   generators => $generators,
   microchips => $microchips,
   n_elements => $n_elements

The first three variables ($generators, $microchips, and $n_elements) will hold the values that will eventually end up in our $start representation of the starting state at the end. Note that $start holds a magic number for the starting elevator position, that is floor 1, that is integer 3 as we already described in New representation.

The hash %floor_shift_of helps us transforming the floor name into a bit shift that is compatible with our representation. The shifts are set according to the rules we set: the least significant octet represents the fourth floor, so there is no shift involved, while the most significant octet represents the first floor, so elements there are shifted by 24 positions (so that we can correctly place them in the most significant octet in our 32-bits representation).

Variables %mask_of and $next_mask work in tandem to assign a specific and consistent bit position to each element. At any time, an element either has an entry in %mask_of, or needs a new one provided by $next_mask.

Let’s now move to the actual inputs reading part:

 1 my $filename   = shift || basename(__FILE__) =~ s{\.pl\z}{.tmp}rmxs;
 2 open my $fh, '<', $filename;
 3 while (<$fh>) {
 4    s{\A The \s+ (\S+) \s+ floor \s+ contains \s+}{}mxs;
 5    my $floor_shift = $floor_shift_of{$1};
 7    for my $group (
 8       [qr{(\S+)-compatible}mxs, \$microchips],
 9       [qr{(\S+) \s+ generator}mxs, \$generators],
10    ) {
11       while (s{$group->[0]}{}mxs) {
12          my $element = $1;
13          if (!exists $mask_of{$element}) {
14             $mask_of{$element} = $next_mask;
15             $next_mask <<= 1;
16             ++$n_elements;
17          }
18          ${$group->[1]} |= ($mask_of{$element} << $floor_shift);
19       }
20    }
21 } ## end while (<$fh>)
22 close $fh;

We still leverage the same regular expressions as before, only using their data differently.

The floor name is transformed into a $floor_shift (line 5). This will allow us to put all elements that are read in a line into the right floor, that is into the right octet in the unsigned integer (line 18).

After reading the floor, it’s time to read microchips and generators. We’re actually doing pretty much the same thing with only slightly different objects here, so it makes sense to factor all common parts together. This is why we have the weird loop at line 7: we first take care of microchips, with the specific regular expression and working on the right variable (hence the reference to $microchips in line 8), then we move on with generators.

For each occurrence of the regular expression, we first ensure that the read-in element has a position (that is, a mask) in the octet (lines 13 through 17), then move the mask to the right floor (via the shift operation << in line 18) and burn it into the target integer (again, line 18).

Assigning a new mask (line 14) means that we hit a new element, so we also take care to increment the associated counter (line 16) as well as prepare for the next element, if any (line 15).

At the end of the loop, $next_mask holds precious information that can be used to build up the goal state too. We first build a goal strip, that is a sequence of bits that is representative of a goal state for microchips and generators:

my $goal_strip = 0;
my $last_mask  = $next_mask;
$goal_strip |= $last_mask while $last_mask >>= 1;

Afterwards, we use this strip to build our $goal state:

my $goal = {
   elevator   => 0,
   generators => $goal_strip,
   microchips => $goal_strip,
   n_elements => $n_elements

Again, in this case the elevator is set to 0, representing the fourth floor.

And we’re done with adapting the input reading to the new representation!

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