TL;DR

On with Advent of Code puzzle 22 from 2021: playing with sets and re-discovering the Inclusion-Exclusion principle.

This day’s puzzle was hard for me, but I had a lot of fun thinking of additional, alternative ways to solve it, until a last intuition that eventually brought me the solution.

And then, of course, I discovered how this should have been done in the other player’s solutions. I particularly liked the python solution by 4HbQ as announced in this post:

from re import findall

def count(cubes):
    if not cubes: return 0

    (state, *head), *tail = cubes
    if state == 'off': return count(tail)

    return volume(*head) + count(tail) - count(
       {intersect(*head, *t) for t in tail}-{None})

def intersect(x,X,y,Y,z,Z, _, u,U,v,V,w,W):
    x = x if x>u else u; X = X if X<U else U
    y = y if y>v else v; Y = Y if Y<V else V
    z = z if z>w else w; Z = Z if Z<W else W
    if x<=X and y<=Y and z<=Z: return '',x,X,y,Y,z,Z

def volume(x,X,y,Y,z,Z):
    return (X-x+1) * (Y-y+1) * (Z-z+1)

def parse(line):
    state, new = line.split()
    return state, *map(int, findall(r'-?\d+', new))

print(count(map(parse, open(0))))

I’ve looked at it in awe because I had about 200 lines of messy code and yet the solution was so simple!

It relies on the Inclusion-Exclusion principle, which is a way of calculating the items in a set. In particular, there’s the Recursive Inclusion-Exclusion principle formulation which is particularly apt for implementation.

I particularly like one of the comments to Recursive Inclusion-Exclusion principle:

I can see that the formula is correct. It is effectively saying “for each new part added, subtract the part that is already counted.” […] DanielV Jan 24 ‘21 at 12:15

So… why not? I’ll spare my original code which gave me the solution, to give instead this cleaner, better version in Raku:

# ... some boilerplate...

sub get-inputs ($filename) {
   $filename.IO.lines.map(
      {
         my $on-off = .substr(1,1) eq 'n';
         my @ranges = .comb(/ \-? \d+ /).map: -> $f, $t { (+$f, +$t) }
         ($on-off, @ranges);
      }
   ).List;
}

sub part1 ($inputs) {
   state $bounding-box = (-50, 50) xx 3;
   my @chunks = $inputs.map: { [$_[0], intersection($_[1], $bounding-box)] };
   measure(@chunks.grep({defined $_[1]}));
}

sub part2 ($inputs) { measure($inputs) }

# returns Nil if no intersection, $para of intersection otherwise
sub intersection ($para1, $para2) {
   my @para;
   for (@$para1 Z @$para2) -> ($ur, $vr) {
      my (\begin, \end) = max($ur[0], $vr[0]), min($ur[1], $vr[1]);
      return Nil unless begin <= end;
      @para.push: (begin, end);
   }
   return @para;
}

sub measure (@inputs) {
   return 0 unless @inputs.elems; # M(empty) = 0
   my ($head, @tail) = @inputs;
   my $tail-measure = measure(@tail);
   return $tail-measure unless $head[0];
   my @isects = @tail.map: { [True, intersection($_[1], $head[1])] };
   my $isects-measure = measure(@isects.grep({defined $_[1]}));
   my $volume = [*] $head[1].map({$_[1] - $_[0] + 1});
   return $volume + $tail-measure - $isects-measure;
}

The representation of a “cuboid” is provided by triples of pairs, each pair representing a range in one dimension. The intersection() function is actually from my first implementation (yay! reuse!), but the measure() function is a rip-off of the other player’s solution.

I like how Raku allows us to define the bounding box for the first part like this:

state $bounding-box = (-50, 50) xx 3;

as well as we’re able to use the same intersection() function to do this restriction in part 1.

Enough for today I guess… stay safe people!