Year 2018

[aoc.git] / 2018 / 30.pl

diff --git a/2018/30.pl b/2018/30.pl
new file mode 100755 (executable)
index 0000000..61e60e5
--- /dev/null
+++ b/2018/30.pl
@@ -0,0 +1,208 @@
+#!/usr/bin/perl -w
+
+use v5.36;
+use strict;
+use experimental 'multidimensional';
+
+my @input = <>;
+
+my (@map, $xmax, $ymax, @units);
+
+sub init_map {
+       @map = map { chomp; [ split // ] } @input;
+       $xmax = $#{ $map[0] };
+       $ymax = $#map;
+
+       @units = ();
+       for my $y (0 .. $ymax) {
+               for my $x (0 .. $xmax) {
+                       if ($map[$y][$x] eq 'G') {
+                               push @units, [$x, $y, 'G', 200];
+                       } elsif ($map[$y][$x] eq 'E') {
+                               push @units, [$x, $y, 'E', 200];
+                       }
+               }
+       }
+}
+
+init_map;
+
+sub enemy_of($unit) { $unit->[2] eq 'G' ? 'E' : 'G' }
+
+my @neighbors = ([0, -1], [-1, 0], [1, 0], [0, 1]);
+
+sub reading_sort {
+       return sort { $a->[1] == $b->[1] ? $a->[0] <=> $b->[0] : $a->[1] <=> $b->[1] } @_;
+}
+
+sub print_map {
+       for my $y (0 .. $ymax) {
+               for my $x (0 .. $xmax) {
+                       print $map[$y][$x];
+               }
+               print "\n";
+       }
+       for my $unit (grep { $_->[3] } reading_sort(@units)) {
+               say "$unit->[2] at $unit->[0],$unit->[1] ($unit->[3])"
+       }
+}
+
+sub neigh_squares($unit, $type) {
+       my @rv;
+       for my $n (@neighbors) {
+               my ($dx, $dy) = @$n;
+               $dx += $unit->[0];
+               $dy += $unit->[1];
+               if ($map[$dy][$dx] eq $type) {
+                       push @rv, [ $dx, $dy ];
+               }
+       }
+       return @rv;
+}
+
+sub enemy_within_range($unit) {
+       return neigh_squares($unit, enemy_of($unit));
+}
+
+sub loc2unit($loc) {
+       for my $unit (@units) {
+               return $unit
+                       if $unit->[0] == $loc->[0] && $unit->[1] == $loc->[1];
+       }
+       die "Can't locate unit at ", join(',', @$loc);
+}
+
+sub attack($unit, $enemies, $power) {
+       say "Attacking unit: ", join(',', @$unit);
+       my $min_hp;
+       my @min_hp;
+       for my $enemy (@$enemies) {
+               say "Enemy: ", join(',', @$enemy);
+               my $enemy_unit = loc2unit($enemy);
+               if (!defined $min_hp || $min_hp > $enemy_unit->[3]) {
+                       $min_hp = $enemy_unit->[3];
+                       @min_hp = ();
+               }
+               if ($min_hp == $enemy_unit->[3]) {
+                       push @min_hp, $enemy_unit;
+               }
+       }
+
+       @min_hp = reading_sort(@min_hp);
+       my $enemy = shift @min_hp;
+       say "attacking";
+       $enemy->[3] -= $power;
+       if ($enemy->[3] <= 0) {
+               die if $enemy->[2] eq 'E';
+               $enemy->[3] = 0;
+               $map[$enemy->[1]][$enemy->[0]] = '.';
+       }
+       $enemy->[3] = 0 if $enemy->[3] < 0;
+       say "attacked ", join(',', @$enemy);
+}
+
+sub dump_path($path) {
+       join(' ', map { "[$_->[0],$_->[1]]" } @$path);
+}
+
+sub move($unit) {
+       my %target_sq;
+       for my $enemy (grep { $_->[2] ne $unit->[2] } @units) {
+               for my $sq (neigh_squares($enemy, '.')) {
+                       if (!$target_sq{$sq->[0],$sq->[1]}++) {
+                               # say "target square $sq->[0],$sq->[1]";
+                       }
+               }
+       }
+
+       my @q = [ [ $unit->[0], $unit->[1] ] ];
+       my %visited;
+       my $found_at_dist;
+       my @reachable;
+       while (@q) {
+               my $path = shift @q;
+               # say "walking path ", dump_path($path);
+               last if $found_at_dist && @$path > $found_at_dist;
+               for my $sq (neigh_squares($path->[-1], '.')) {
+                       next if $visited{$sq->[0],$sq->[1]}++;
+
+                       if ($target_sq{$sq->[0],$sq->[1]}) {
+                               $found_at_dist //= @$path;
+                               my $path1 = [ @$path, [ @$sq ] ];
+                               # say "Found square $sq->[0],$sq->[1] through ",
+                               #       dump_path($path1);
+                               push @reachable, [ @$sq, @{ $path1->[1] } ];
+                       } else {
+                               push @q, [ @$path, [ @$sq ] ];
+                       }
+               }
+       }
+
+       if (!@reachable) {
+               # say "no reachable squares";
+               return;
+       }
+
+       @reachable = reading_sort(@reachable);
+       my $target = $reachable[0];
+       # say "moving to $target->[0],$target->[1] via $target->[2],$target->[3]";
+       $map[$unit->[1]][$unit->[0]] = '.';
+       $map[$unit->[1] = $target->[3]][$unit->[0] = $target->[2]] = $unit->[2];
+}
+
+sub unit_round($unit, $attack) {
+       return if !$unit->[3]; # are we alive?
+       # say "\nunit_round ", join(',', @$unit);
+
+       my @enemies = enemy_within_range($unit);
+       if (!@enemies) {
+               move($unit);
+               @enemies = enemy_within_range($unit);
+       }
+       if (@enemies) {
+               attack($unit, \@enemies, $attack);
+       }
+}
+
+sub battle($elf_hp) {
+       my $round = 0;
+       init_map;
+       say "elf_hp: $elf_hp =====================================";
+       my %total_hp;
+       ROUND:
+       while (1) {
+               say "After $round rounds:";
+               print_map;
+               $round++;
+               @units = reading_sort(grep { $_->[3] } @units);
+
+               for my $unit (@units) {
+                       next if !$unit->[3];
+                       %total_hp = ();
+                       for my $u (@units) {
+                               $total_hp{$u->[2]} += $u->[3]
+                                       if $u->[3];
+                       }
+                       if (keys %total_hp < 2) {
+                               $round--;
+                               last ROUND;
+                       }
+                       eval { unit_round($unit, $unit->[2] eq 'E' ? $elf_hp : 3); };
+                       return 0 if $@;
+               }
+
+       }
+       say "After $round rounds with hp $elf_hp:";
+       print_map;
+
+       say "elf_hp $elf_hp ended after round $round with hp ", join('=>', %total_hp);
+       say $round * (%total_hp)[1];
+       return 1;
+}
+
+my $elf_hp = 4;
+$elf_hp++ while !battle($elf_hp);
+
+# There is a bug out there - on the real puzzle input it returned
+# remaining hp lower by three, which means there had to be one less Goblin
+# attack somewhere.