First half of Year 2019

[aoc.git] / 2019 / 20.pl

diff --git a/2019/20.pl b/2019/20.pl
new file mode 100755 (executable)
index 0000000..d34db6f
--- /dev/null
+++ b/2019/20.pl
@@ -0,0 +1,124 @@
+#!/usr/bin/perl -w
+
+use v5.16;
+
+my %m;
+$; = ',';
+my $y = 0;
+my ($maxx, $maxy);
+while (<>) {
+       chomp;
+       my $x = 0;
+       $maxx = length;
+       for my $c (split //) {
+               $m{$x,$y}++ if $c eq '#';
+               $x++;
+       }
+       $y++;
+}
+$maxy = $y;
+
+my %gcd;
+sub gcd {
+       my ($n1, $n2) = @_;
+       return $gcd{$n1,$n2} //=
+               $n1 == $n2 ? $n1
+               : $n1 > $n2 ? gcd($n2, $n1-$n2)
+               : gcd($n1, $n2-$n1);
+}
+
+my %dir;
+sub dir1 {
+       my ($x, $y) = @_;
+       return (0, 1) if $x == 0 && $y > 0;
+       return (0,-1) if $x == 0 && $y < 0;
+       return (1, 0) if $y == 0 && $x > 0;
+       return (-1,0) if $y == 0 && $x < 0;
+       my $g = gcd(abs($x), abs($y));
+       return ($x/$g, $y/$g);
+}
+
+sub dir {
+       my ($x, $y) = @_;
+       $dir{$x,$y} //= [ dir1($x,$y) ];
+       return @{ $dir{$x,$y} };
+}
+
+my $max_sum;
+my $max_pos;
+my @max_dirs;
+for (keys %m) {
+       my ($x,$y) = split /,/;
+       my $sum;
+       my @dirs;
+       ASTEROID:
+       for (keys %m) {
+               my ($ax, $ay) = split /,/;
+               next if $ax == $x && $ay == $y;
+               # say "testing $ax,$ay from $x,$y";
+               my ($dx, $dy) = dir($ax-$x, $ay-$y);
+               # next if $tried_dir{$dx,$dy}++;
+               # say "dx,dy=$dx,$dy";
+               my ($x0, $y0) = ($x+$dx, $y+$dy);
+               while ($x0 != $ax || $y0 != $ay) {
+                       # say "x0,y0=$x0,$y0";
+                       if ($m{$x0,$y0}) {
+                               # say "$ax,$ay cannot be seen from $x,$y because of $x0,$y0";
+                               next ASTEROID;
+                       }
+                       $x0 += $dx; $y0 += $dy;
+               }
+               # say "$ax,$ay CAN be seen from $x,$y";
+               push @dirs, [$dx, $dy];
+               $sum++;
+       }
+       if (!defined $max_sum || $max_sum < $sum) {
+               $max_sum = $sum;
+               $max_pos = "$x,$y";
+               @max_dirs = @dirs;
+       }
+}
+
+say $max_pos, '=', $max_sum;
+
+my $x;
+($x, $y) = split /,/, $max_pos;
+my @dirs = (
+       (grep { $_->[0] == 0 && $_->[1] < 0 } @max_dirs),
+       (sort { $b->[0]/$b->[1] <=> $a->[0]/$a->[1] }
+               grep { $_->[0] > 0 && $_->[1] < 0 } @max_dirs),
+       (grep { $_->[0] > 0 && $_->[1] == 0 } @max_dirs),
+       (sort { $b->[0]/$b->[1] <=> $a->[0]/$a->[1] }
+               grep { $_->[0] > 0 && $_->[1] > 0 } @max_dirs),
+       (grep { $_->[0] == 0 && $_->[1] > 0 } @max_dirs),
+       (sort { $b->[0]/$b->[1] <=> $a->[0]/$a->[1] }
+               grep { $_->[0] < 0 && $_->[1] > 0 } @max_dirs),
+       (grep { $_->[0] < 0 && $_->[1] == 0 } @max_dirs),
+       (sort { $b->[0]/$b->[1] <=> $a->[0]/$a->[1] }
+               grep { $_->[0] < 0 && $_->[1] < 0 } @max_dirs),
+);
+
+
+my %seen;
+my $count;
+my %skip_dir;
+while (1) {
+       for my $dir (@dirs) {
+               my ($dx,$dy) = @$dir;
+               next if $skip_dir{$dx,$dy};
+               #say "dir $dx,$dy";
+               my ($x0, $y0) = ($x + $dx, $y + $dy);
+               while ($x0 >= 0 && $y0 >= 0 && $x0 < $maxx && $y0 < $maxy) {
+                       if (!$seen{$x0,$y0} && $m{$x0,$y0}) {
+                               $seen{$x0,$y0} = 1;
+                               say ++$count, " at $x0,$y0 dir $dx,$dy (", 100*$x0+$y0, ")";
+                               exit 0 if $count == 200;
+                               goto OUT;
+                       }
+                       $x0 += $dx; $y0 += $dy;
+               }
+               $skip_dir{$dx,$dy}=1;
+       OUT:
+       }
+}
+