#!/usr/bin/perl -w

use v5.16;

$; = ',';
my %scans;
my $scanner;
my $first_scanner;
while (<>) {
	chomp;
	if (/--- (scanner \d+) ---/) {
		$scanner = $1;
		$first_scanner //= $1;
	} elsif (/^$/) {
		next;
	} else {
		$scans{$scanner}->{$_} = 1;
	}
}

my @perms = (
	[ 0, 1, 2],
	[ 0, 2, 1],
	[ 1, 0, 2],
	[ 1, 2, 0],
	[ 2, 0, 1],
	[ 2, 1, 0],
);

my @rotations;
my %r_seen;
for (0 .. 7) {
	for my $p (@perms) {
		my @r = @$p;
		$r[3] = $_ & 0x01 ? -1 : 1;
		$r[4] = $_ & 0x02 ? -1 : 1;
		$r[5] = $_ & 0x04 ? -1 : 1;
		push @rotations, \@r;
	}
}
		
use Data::Dumper;
say "rotations: ", scalar @rotations;

sub transform {
	my ($coords, $trans) = @_;
	my @res;
	for (0 .. $#$coords) {
		$res[$_] = $coords->[$trans->[$_]];
		$res[$_] *= -1 if $trans->[$_+@$coords] < 0;
	}
	return @res;
}

sub is_aligned {
	my ($s1, $s2) = @_;
	my $coords1 = $scans{$s1};
	my $coords2 = $scans{$s2};

	say "comparing $s1 and $s2";
	for my $from_t (keys %$coords1) {
		my @from = split /,/, $from_t;
		for my $rot (@rotations) {
			my @from_rotated = transform(\@from, $rot);
			# say "rotated ", join(',', @from), ' to ', join(',', @from_rotated);
			for my $to_t (keys %$coords2) {
				my @off = split /,/, $to_t;
				$off[$_] -= $from_rotated[$_] for 0..$#off;
				# say "trying offset ", join(',', @off);
				my $count = 0;
				for my $c1_t (keys %$coords1) {
					my @c1 = split /,/, $c1_t;
					@c1 = transform(\@c1, $rot);
					$c1[$_] += $off[$_] for 0..$#off;
					# say "searching for ", join(',',@c1);
					$count++ if $coords2->{join(',', @c1)};
				}
				if ($count >= 12) {
					say "found $count matches ", join(',', @$rot);
					return (\@off, $rot);
				}
			}
		}
	}
}

my %aligned_scanners = ($first_scanner => [ [ 0, 0, 0], [ 0, 1, 2, 1, 1, 1 ] ]);
my %beacons = ( %{ $scans{$first_scanner} } );
my %tested;
while (scalar keys %aligned_scanners < scalar keys %scans) {
	say scalar keys %beacons, ' beacons found:';
	for my $s1 (grep { $aligned_scanners{$_} } keys %scans) {
		for my $s2 (grep { !$aligned_scanners{$_} } keys %scans) {
			next if $tested{$s1,$s2} || $tested{$s2,$s1};
			my ($off, $rot) = is_aligned($s2, $s1);
			$tested{$s1,$s2} = $tested{$s2,$s1} = 1;
			next if !defined $rot;
			my %nscans;
			for my $c2_t (keys %{ $scans{$s2}}) {
				my @c2 = split /,/, $c2_t;
				@c2 = transform(\@c2, $rot);
				$c2[$_] += $off->[$_] for 0 .. $#c2;
				my $key = join(',', @c2);
				$beacons{$key}++;
				$nscans{$key}++;
			}
			$scans{$s2} = \%nscans;
			$aligned_scanners{$s2} = 1;
			say "$s1 and $s2 aligned: ", join(',', @$off, @$rot), " beacons: ", scalar keys %beacons;
		}
	}
}

say '=========';
for my $b (sort keys %beacons) {
	say $b;
}
say "total beacons: ", scalar keys %beacons;
