# ETOOBUSY ðŸš€ minimal blogging for the impatient

# AoC 2017/12 - Rediscovering Union-Find

**TL;DR**

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

rememberedsomething.

While wast**AHEM**investing ðŸ™„ 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 add; # see below
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
sub add {
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;
$self->add($_) for @{$args{components} || []};
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, Twitter, GitHub, Reddit, or drop me a line!*