2018/30.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.36;
   4 use strict;
   5 use experimental 'multidimensional';
   6
   7 my @input = <>;
   8
   9 my (@map, $xmax, $ymax, @units);
  10
  11 sub init_map {
  12         @map = map { chomp; [ split // ] } @input;
  13         $xmax = $#{ $map[0] };
  14         $ymax = $#map;
  15
  16         @units = ();
  17         for my $y (0 .. $ymax) {
  18                 for my $x (0 .. $xmax) {
  19                         if ($map[$y][$x] eq 'G') {
  20                                 push @units, [$x, $y, 'G', 200];
  21                         } elsif ($map[$y][$x] eq 'E') {
  22                                 push @units, [$x, $y, 'E', 200];
  23                         }
  24                 }
  25         }
  26 }
  27
  28 init_map;
  29
  30 sub enemy_of($unit) { $unit->[2] eq 'G' ? 'E' : 'G' }
  31
  32 my @neighbors = ([0, -1], [-1, 0], [1, 0], [0, 1]);
  33
  34 sub reading_sort {
  35         return sort { $a->[1] == $b->[1] ? $a->[0] <=> $b->[0] : $a->[1] <=> $b->[1] } @_;
  36 }
  37
  38 sub print_map {
  39         for my $y (0 .. $ymax) {
  40                 for my $x (0 .. $xmax) {
  41                         print $map[$y][$x];
  42                 }
  43                 print "\n";
  44         }
  45         for my $unit (grep { $_->[3] } reading_sort(@units)) {
  46                 say "# $unit->[2] at ($unit->[1]+$unit->[0]j) $unit->[3]"
  47         }
  48 }
  49
  50 sub neigh_squares($unit, $type) {
  51         my @rv;
  52         for my $n (@neighbors) {
  53                 my ($dx, $dy) = @$n;
  54                 $dx += $unit->[0];
  55                 $dy += $unit->[1];
  56                 if ($map[$dy][$dx] eq $type) {
  57                         push @rv, [ $dx, $dy ];
  58                 }
  59         }
  60         return @rv;
  61 }
  62
  63 sub enemy_within_range($unit) {
  64         return neigh_squares($unit, enemy_of($unit));
  65 }
  66
  67 sub loc2unit($loc) {
  68         for my $unit (@units) {
  69                 return $unit
  70                         if $unit->[0] == $loc->[0] && $unit->[1] == $loc->[1];
  71         }
  72         die "Can't locate unit at ", join(',', @$loc);
  73 }
  74
  75 sub attack($unit, $enemies, $power) {
  76         say "Attacking unit: ", join(',', @$unit);
  77         my $min_hp;
  78         my @min_hp;
  79         for my $enemy (@$enemies) {
  80                 say "Enemy: ", join(',', @$enemy);
  81                 my $enemy_unit = loc2unit($enemy);
  82                 if (!defined $min_hp || $min_hp > $enemy_unit->[3]) {
  83                         $min_hp = $enemy_unit->[3];
  84                         @min_hp = ();
  85                 }
  86                 if ($min_hp == $enemy_unit->[3]) {
  87                         push @min_hp, $enemy_unit;
  88                 }
  89         }
  90
  91         @min_hp = reading_sort(@min_hp);
  92         my $enemy = shift @min_hp;
  93         say "attacking";
  94         $enemy->[3] -= $power;
  95         if ($enemy->[3] <= 0) {
  96                 die if $enemy->[2] eq 'E';
  97                 $enemy->[3] = 0;
  98                 $map[$enemy->[1]][$enemy->[0]] = '.';
  99         }
 100         $enemy->[3] = 0 if $enemy->[3] < 0;
 101         say "attacked ", join(',', @$enemy);
 102 }
 103
 104 sub dump_path($path) {
 105         join(' ', map { "[$_->[0],$_->[1]]" } @$path);
 106 }
 107
 108 sub move($unit) {
 109         my %target_sq;
 110         for my $enemy (grep { $_->[2] ne $unit->[2] && $_->[3] > 0 } @units) {
 111                 for my $sq (neigh_squares($enemy, '.')) {
 112                         if (!$target_sq{$sq->[0],$sq->[1]}++) {
 113                                 # say "target square $sq->[0],$sq->[1]";
 114                         }
 115                 }
 116         }
 117
 118         my @q = [ [ $unit->[0], $unit->[1] ] ];
 119         my %visited;
 120         my $found_at_dist;
 121         my @reachable;
 122         while (@q) {
 123                 my $path = shift @q;
 124                 # say "walking path ", dump_path($path);
 125                 last if $found_at_dist && @$path > $found_at_dist;
 126                 for my $sq (neigh_squares($path->[-1], '.')) {
 127                         next if $visited{$sq->[0],$sq->[1]}++;
 128
 129                         if ($target_sq{$sq->[0],$sq->[1]}) {
 130                                 $found_at_dist //= @$path;
 131                                 my $path1 = [ @$path, [ @$sq ] ];
 132                                 # say "Found square $sq->[0],$sq->[1] through ",
 133                                 #       dump_path($path1);
 134                                 push @reachable, [ @$sq, @{ $path1->[1] } ];
 135                         } else {
 136                                 push @q, [ @$path, [ @$sq ] ];
 137                         }
 138                 }
 139         }
 140
 141         if (!@reachable) {
 142                 # say "no reachable squares";
 143                 return;
 144         }
 145
 146         @reachable = reading_sort(@reachable);
 147         my $target = $reachable[0];
 148         say "moving to $target->[0],$target->[1] via $target->[2],$target->[3]";
 149         $map[$unit->[1]][$unit->[0]] = '.';
 150         $map[$unit->[1] = $target->[3]][$unit->[0] = $target->[2]] = $unit->[2];
 151 }
 152
 153 sub unit_round($unit, $attack) {
 154         return if !$unit->[3]; # are we alive?
 155         # say "\nunit_round ", join(',', @$unit);
 156
 157         my @enemies = enemy_within_range($unit);
 158         if (!@enemies) {
 159                 move($unit);
 160                 @enemies = enemy_within_range($unit);
 161         }
 162         if (@enemies) {
 163                 attack($unit, \@enemies, $attack);
 164         }
 165 }
 166
 167 sub battle($elf_hp) {
 168         my $round = 0;
 169         init_map;
 170         say "elf_hp: $elf_hp =====================================";
 171         my %total_hp;
 172         ROUND:
 173         while (1) {
 174                 say "After $round rounds:";
 175                 print_map;
 176                 $round++;
 177                 @units = reading_sort(grep { $_->[3] } @units);
 178
 179                 for my $unit (@units) {
 180                         next if !$unit->[3];
 181                         %total_hp = ();
 182                         for my $u (@units) {
 183                                 $total_hp{$u->[2]} += $u->[3]
 184                                         if $u->[3];
 185                         }
 186                         if (keys %total_hp < 2) {
 187                                 $round--;
 188                                 last ROUND;
 189                         }
 190                         eval { unit_round($unit, $unit->[2] eq 'E' ? $elf_hp : 3); };
 191                         return 0 if $@;
 192                 }
 193
 194         }
 195         say "After $round rounds with hp $elf_hp:";
 196         print_map;
 197
 198         say "elf_hp $elf_hp ended after round $round with hp ", join('=>', %total_hp);
 199         say $round * (%total_hp)[1];
 200         return 1;
 201 }
 202
 203 my $elf_hp = 12;
 204 $elf_hp++ while !battle($elf_hp);
 205