TL;DR

I remembered about Union-Find. The incredible thing is that I remembered something.

While wastAHEMinvesting ðŸ™„ time with the puzzles in the 2017 edition of Advent of Code, I eventually arrived at day 12.

You might be wondering so what?!? at this point. If youâ€™re Italian, you might be even thinking of Grande Capo Estiqaatsi.

The puzzle eventually boils down to having an Undirected Graph and asking a few things about it:

• part 1: how many nodes are connected to the node whose identifier is `0`?
• part 2: how many disjoint sets of nodes are there?

Luckily for me, I took Courseraâ€™s Algorithms, Part I and incredibly remembered about the very first lesson about Union-Find, which is perfectly tailored for this puzzle.

With some more effort of memory (read: reimplemented the thing before remembering about it), I also re-discovered my implementation in Perl, of course in cglib, available at UnionFind.pm:

``````package UnionFind; # Sedgewick & Wayne, Algorithms 4th ed, Â§1.5
use strict;

sub connected { return \$_[0]->find(\$_[1]) eq \$_[0]->find(\$_[2]) }
sub count     { return \$_[0]{count} }
sub find      { return \$_[0]{cs}{\$_[0]->find_id(\$_[1])}[1] }
sub find_id;    # see below
sub new;        # see below
sub union;      # see below

my \$id = \$_[0]{id_of}->(\$_[1]);
return \$_[0] if \$_[0]{cs}{\$id};
\$_[0]{cs}{\$id} = [\$id, \$_[1], 1];
\$_[0]{count}++;
return \$_[0];
}

sub find_id {
my \$r = my \$i = \$_[0]{id_of}->(\$_[1]);
return unless exists \$_[0]{cs}{\$r};
\$r = \$_[0]{cs}{\$r}[0] while \$r ne \$_[0]{cs}{\$r}[0];
(\$i, \$_[0]{cs}{\$i}) = (\$_[0]{cs}{\$i}[0], \$_[0]{cs}{\$r}) while \$i ne \$r;
return \$r;
} ## end sub find_id

sub new {
my (\$pk, %args) = (@_ > 0 && ref(\$_[1])) ? (\$_[0], %{\$_[1]}) : @_;
my \$id_of = \$args{identifier} || sub { return "\$_[0]" };
my \$self = bless {id_of => \$id_of, count => 0}, \$pk;
return \$self;
} ## end sub new

sub union {
my (\$i, \$j) = (\$_[0]->find_id(\$_[1]), \$_[0]->find_id(\$_[2]));
return \$_[0] if \$i eq \$j;
(\$i, \$j) = (\$j, \$i) if \$_[0]{cs}{\$i}[2] < \$_[0]{cs}{\$j}[2];   # i -> max
\$_[0]{cs}{\$i}[2] += \$_[0]{cs}{\$i}[2];
\$_[0]{cs}{\$j} = \$_[0]{cs}{\$i};
\$_[0]{count}--;
return \$_[0];
} ## end sub union

1;
``````

I am totally ashamed by the lack of documentationâ€¦ although I didnâ€™t have a hard time figuring out how to use it:

``````# Input array @neighbors is an AoA; each sub-array holds a list of
# neighbors for the identifier of the sub-array itself.
sub solution (@neighbors) {
my \$uf = UnionFind->new(components => [0 .. \$#neighbors]);
\$uf->union(\$_->@*) for map {
my \$id = \$_;
map { [\$id, \$_] } \$neighbors[\$id]->@*;
} 0 .. \$#neighbors;
my \$conn0 = grep { \$uf->connected(0, \$_) } 0 .. \$#neighbors;
return (part_1 => \$conn0, part_2 => \$uf->count);
}
``````

Wellâ€¦ enough for today, stay safe!

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