From 51f951351d95b416c9f27b4660d230e5b2cf8541 Mon Sep 17 00:00:00 2001
From: "Jan \"Yenya\" Kasprzak" <kas@fi.muni.cz>
Date: Sun, 19 Dec 2021 09:15:04 +0100
Subject: [PATCH] Day 19: boring work, long and ugly code

---
 37.pl | 118 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 38.pl |  45 ++++++++++++++++++++++
 2 files changed, 163 insertions(+)
 create mode 100755 37.pl
 create mode 100755 38.pl

diff --git a/37.pl b/37.pl
new file mode 100755
index 0000000..8770cb7
--- /dev/null
+++ b/37.pl
@@ -0,0 +1,118 @@
+#!/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;
diff --git a/38.pl b/38.pl
new file mode 100755
index 0000000..b604ecc
--- /dev/null
+++ b/38.pl
@@ -0,0 +1,45 @@
+#!/usr/bin/perl -w
+
+use v5.16;
+
+$; = ',';
+
+sub transform {
+	my ($coords, $trans) = @_;
+	my @res;
+	for (0 .. $#$coords) {
+		$res[$_] = $coords->[$trans->[$_]];
+		$res[$_] *= -1 if $trans->[$_+@$coords] < 0;
+	}
+	return @res;
+}
+
+my %aligned_scanners = ('scanner 0' => [ 0, 0, 0 ]);
+
+# parsing the debugging output of the first part ...
+while (<>) {
+	my ($s1, $s2, $rest) = /(.*) and (.*) aligned: (.*) beacons:/;
+	next if !$rest;
+
+	my @r = split /,/, $rest;
+	my @off = @r[0..2];
+	my @rot = @r[3..8];
+
+	# @off = transform(\@off, \@rot);
+	say "$s1 to $s2";
+	# $off[$_] += $aligned_scanners{$s1}->[$_] for 0..2;
+	say "$s2 at ", join(',', @off);
+	$aligned_scanners{$s2} = [ @off ];
+}
+
+my $max_dist = 0;
+for my $s1 (keys %aligned_scanners) {
+for my $s2 (keys %aligned_scanners) {
+	my $dist;
+	$dist += abs($aligned_scanners{$s1}->[$_] - $aligned_scanners{$s2}->[$_]) for 0 .. 2;
+	$max_dist = $dist if $dist > $max_dist;
+	say "$s1 to $s2 = $dist";
+} }
+
+say $max_dist;
+
-- 
2.43.0