2019/20.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.16;
   4
   5 my %m;
   6 $; = ',';
   7 my $y = 0;
   8 my ($maxx, $maxy);
   9 while (<>) {
  10         chomp;
  11         my $x = 0;
  12         $maxx = length;
  13         for my $c (split //) {
  14                 $m{$x,$y}++ if $c eq '#';
  15                 $x++;
  16         }
  17         $y++;
  18 }
  19 $maxy = $y;
  20
  21 my %gcd;
  22 sub gcd {
  23         my ($n1, $n2) = @_;
  24         return $gcd{$n1,$n2} //=
  25                 $n1 == $n2 ? $n1
  26                 : $n1 > $n2 ? gcd($n2, $n1-$n2)
  27                 : gcd($n1, $n2-$n1);
  28 }
  29
  30 my %dir;
  31 sub dir1 {
  32         my ($x, $y) = @_;
  33         return (0, 1) if $x == 0 && $y > 0;
  34         return (0,-1) if $x == 0 && $y < 0;
  35         return (1, 0) if $y == 0 && $x > 0;
  36         return (-1,0) if $y == 0 && $x < 0;
  37         my $g = gcd(abs($x), abs($y));
  38         return ($x/$g, $y/$g);
  39 }
  40
  41 sub dir {
  42         my ($x, $y) = @_;
  43         $dir{$x,$y} //= [ dir1($x,$y) ];
  44         return @{ $dir{$x,$y} };
  45 }
  46
  47 my $max_sum;
  48 my $max_pos;
  49 my @max_dirs;
  50 for (keys %m) {
  51         my ($x,$y) = split /,/;
  52         my $sum;
  53         my @dirs;
  54         ASTEROID:
  55         for (keys %m) {
  56                 my ($ax, $ay) = split /,/;
  57                 next if $ax == $x && $ay == $y;
  58                 # say "testing $ax,$ay from $x,$y";
  59                 my ($dx, $dy) = dir($ax-$x, $ay-$y);
  60                 # next if $tried_dir{$dx,$dy}++;
  61                 # say "dx,dy=$dx,$dy";
  62                 my ($x0, $y0) = ($x+$dx, $y+$dy);
  63                 while ($x0 != $ax || $y0 != $ay) {
  64                         # say "x0,y0=$x0,$y0";
  65                         if ($m{$x0,$y0}) {
  66                                 # say "$ax,$ay cannot be seen from $x,$y because of $x0,$y0";
  67                                 next ASTEROID;
  68                         }
  69                         $x0 += $dx; $y0 += $dy;
  70                 }
  71                 # say "$ax,$ay CAN be seen from $x,$y";
  72                 push @dirs, [$dx, $dy];
  73                 $sum++;
  74         }
  75         if (!defined $max_sum || $max_sum < $sum) {
  76                 $max_sum = $sum;
  77                 $max_pos = "$x,$y";
  78                 @max_dirs = @dirs;
  79         }
  80 }
  81
  82 say $max_pos, '=', $max_sum;
  83
  84 my $x;
  85 ($x, $y) = split /,/, $max_pos;
  86 my @dirs = (
  87         (grep { $_->[0] == 0 && $_->[1] < 0 } @max_dirs),
  88         (sort { $b->[0]/$b->[1] <=> $a->[0]/$a->[1] }
  89                 grep { $_->[0] > 0 && $_->[1] < 0 } @max_dirs),
  90         (grep { $_->[0] > 0 && $_->[1] == 0 } @max_dirs),
  91         (sort { $b->[0]/$b->[1] <=> $a->[0]/$a->[1] }
  92                 grep { $_->[0] > 0 && $_->[1] > 0 } @max_dirs),
  93         (grep { $_->[0] == 0 && $_->[1] > 0 } @max_dirs),
  94         (sort { $b->[0]/$b->[1] <=> $a->[0]/$a->[1] }
  95                 grep { $_->[0] < 0 && $_->[1] > 0 } @max_dirs),
  96         (grep { $_->[0] < 0 && $_->[1] == 0 } @max_dirs),
  97         (sort { $b->[0]/$b->[1] <=> $a->[0]/$a->[1] }
  98                 grep { $_->[0] < 0 && $_->[1] < 0 } @max_dirs),
  99 );
 100
 101
 102 my %seen;
 103 my $count;
 104 my %skip_dir;
 105 while (1) {
 106         for my $dir (@dirs) {
 107                 my ($dx,$dy) = @$dir;
 108                 next if $skip_dir{$dx,$dy};
 109                 #say "dir $dx,$dy";
 110                 my ($x0, $y0) = ($x + $dx, $y + $dy);
 111                 while ($x0 >= 0 && $y0 >= 0 && $x0 < $maxx && $y0 < $maxy) {
 112                         if (!$seen{$x0,$y0} && $m{$x0,$y0}) {
 113                                 $seen{$x0,$y0} = 1;
 114                                 say ++$count, " at $x0,$y0 dir $dx,$dy (", 100*$x0+$y0, ")";
 115                                 exit 0 if $count == 200;
 116                                 goto OUT;
 117                         }
 118                         $x0 += $dx; $y0 += $dy;
 119                 }
 120                 $skip_dir{$dx,$dy}=1;
 121         OUT:
 122         }
 123 }
 124