44.pl

   1 #!/usr/bin/perl -w
   2
   3 use strict;
   4
   5 local $/ = "\n\n";
   6
   7 my @pl1 = <> =~ /^(\d+)$/gxms;
   8 my @pl2 = <> =~ /^(\d+)$/gxms;
   9
  10 print "sum=", play(\@pl1, \@pl2), "\n";
  11
  12 sub play {
  13         my ($d1, $d2) = @_;
  14         my @pl1 = @$d1;
  15         my @pl2 = @$d2;
  16
  17         my %seen;
  18
  19         while (@pl1 && @pl2) {
  20                 my $conf = join('|', @pl1, "#", @pl2);
  21                 if ($seen{$conf}++) {
  22                         return score(@pl1);
  23                 }
  24                 my $p1 = shift @pl1;
  25                 my $p2 = shift @pl2;
  26
  27                 if ($p1 <= @pl1 && $p2 <= @pl2) {
  28                         my @sub1 = @pl1[0 .. $p1-1];
  29                         my @sub2 = @pl2[0 .. $p2-1];
  30                         if (play(\@sub1, \@sub2) > 0) {
  31                                 push @pl1, $p1, $p2;
  32                         } else {
  33                                 push @pl2, $p2, $p1;
  34                         }
  35                 } else {
  36                         if ($p1 > $p2) {
  37                                 push @pl1, $p1, $p2;
  38                         } else {
  39                                 push @pl2, $p2, $p1;
  40                         }
  41                 }
  42         }
  43         if (@pl1) {
  44                 return score(@pl1);
  45         } else {
  46                 return -score(@pl2);
  47         }
  48 }
  49
  50 sub score {
  51         my @pl1 = @_;
  52         my $sum = 0;
  53         while (@pl1) {
  54                 $sum += +$pl1[0] * @pl1;
  55                 shift @pl1;
  56         }
  57         return $sum;
  58 }
  59