37.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.16;
   4
   5 $; = ',';
   6 my %scans;
   7 my $scanner;
   8 my $first_scanner;
   9 while (<>) {
  10         chomp;
  11         if (/--- (scanner \d+) ---/) {
  12                 $scanner = $1;
  13                 $first_scanner //= $1;
  14         } elsif (/^$/) {
  15                 next;
  16         } else {
  17                 $scans{$scanner}->{$_} = 1;
  18         }
  19 }
  20
  21 my @perms = (
  22         [ 0, 1, 2],
  23         [ 0, 2, 1],
  24         [ 1, 0, 2],
  25         [ 1, 2, 0],
  26         [ 2, 0, 1],
  27         [ 2, 1, 0],
  28 );
  29
  30 my @rotations;
  31 my %r_seen;
  32 for (0 .. 7) {
  33         for my $p (@perms) {
  34                 my @r = @$p;
  35                 $r[3] = $_ & 0x01 ? -1 : 1;
  36                 $r[4] = $_ & 0x02 ? -1 : 1;
  37                 $r[5] = $_ & 0x04 ? -1 : 1;
  38                 push @rotations, \@r;
  39         }
  40 }
  41
  42 use Data::Dumper;
  43 say "rotations: ", scalar @rotations;
  44
  45 sub transform {
  46         my ($coords, $trans) = @_;
  47         my @res;
  48         for (0 .. $#$coords) {
  49                 $res[$_] = $coords->[$trans->[$_]];
  50                 $res[$_] *= -1 if $trans->[$_+@$coords] < 0;
  51         }
  52         return @res;
  53 }
  54
  55 sub is_aligned {
  56         my ($s1, $s2) = @_;
  57         my $coords1 = $scans{$s1};
  58         my $coords2 = $scans{$s2};
  59
  60         say "comparing $s1 and $s2";
  61         for my $from_t (keys %$coords1) {
  62                 my @from = split /,/, $from_t;
  63                 for my $rot (@rotations) {
  64                         my @from_rotated = transform(\@from, $rot);
  65                         # say "rotated ", join(',', @from), ' to ', join(',', @from_rotated);
  66                         for my $to_t (keys %$coords2) {
  67                                 my @off = split /,/, $to_t;
  68                                 $off[$_] -= $from_rotated[$_] for 0..$#off;
  69                                 # say "trying offset ", join(',', @off);
  70                                 my $count = 0;
  71                                 for my $c1_t (keys %$coords1) {
  72                                         my @c1 = split /,/, $c1_t;
  73                                         @c1 = transform(\@c1, $rot);
  74                                         $c1[$_] += $off[$_] for 0..$#off;
  75                                         # say "searching for ", join(',',@c1);
  76                                         $count++ if $coords2->{join(',', @c1)};
  77                                 }
  78                                 if ($count >= 12) {
  79                                         say "found $count matches ", join(',', @$rot);
  80                                         return (\@off, $rot);
  81                                 }
  82                         }
  83                 }
  84         }
  85 }
  86
  87 my %aligned_scanners = ($first_scanner => [ [ 0, 0, 0], [ 0, 1, 2, 1, 1, 1 ] ]);
  88 my %beacons = ( %{ $scans{$first_scanner} } );
  89 my %tested;
  90 while (scalar keys %aligned_scanners < scalar keys %scans) {
  91         say scalar keys %beacons, ' beacons found:';
  92         for my $s1 (grep { $aligned_scanners{$_} } keys %scans) {
  93                 for my $s2 (grep { !$aligned_scanners{$_} } keys %scans) {
  94                         next if $tested{$s1,$s2} || $tested{$s2,$s1};
  95                         my ($off, $rot) = is_aligned($s2, $s1);
  96                         $tested{$s1,$s2} = $tested{$s2,$s1} = 1;
  97                         next if !defined $rot;
  98                         my %nscans;
  99                         for my $c2_t (keys %{ $scans{$s2}}) {
 100                                 my @c2 = split /,/, $c2_t;
 101                                 @c2 = transform(\@c2, $rot);
 102                                 $c2[$_] += $off->[$_] for 0 .. $#c2;
 103                                 my $key = join(',', @c2);
 104                                 $beacons{$key}++;
 105                                 $nscans{$key}++;
 106                         }
 107                         $scans{$s2} = \%nscans;
 108                         $aligned_scanners{$s2} = 1;
 109                         say "$s1 and $s2 aligned: ", join(',', @$off, @$rot), " beacons: ", scalar keys %beacons;
 110                 }
 111         }
 112 }
 113
 114 say '=========';
 115 for my $b (sort keys %beacons) {
 116         say $b;
 117 }
 118 say "total beacons: ", scalar keys %beacons;