]> www.fi.muni.cz Git - aoc.git/commitdiff
Day 19: boring work, long and ugly code
authorJan "Yenya" Kasprzak <kas@fi.muni.cz>
Sun, 19 Dec 2021 08:15:04 +0000 (09:15 +0100)
committerJan "Yenya" Kasprzak <kas@fi.muni.cz>
Sun, 19 Dec 2021 08:15:04 +0000 (09:15 +0100)
37.pl [new file with mode: 0755]
38.pl [new file with mode: 0755]

diff --git a/37.pl b/37.pl
new file mode 100755 (executable)
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 (executable)
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;
+