2019/30.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.16;
   4
   5 package IntComp;
   6 use bigint;
   7
   8 sub new {
   9         my ($class, $mem, $inputs) = @_;
  10         my $self = {
  11                 mem => [ @$mem ],
  12                 pc  => 0,
  13                 want_input => undef,
  14                 base => 0,
  15         };
  16         $self->{inputs} = [ @$inputs ]
  17                 if defined $inputs;
  18         bless $self, $class;
  19 }
  20
  21 sub clone {
  22         my ($class, $other) = @_;
  23         my $self = {
  24                 mem => [ @{ $other->{mem} } ],
  25                 pc  => $other->{pc},
  26                 want_input => undef,
  27                 base => $other->{base},
  28                 inputs => [ ],
  29         };
  30         bless $self, $class;
  31 }
  32
  33 sub m2val {
  34         my ($self, $off, $mode) = @_;
  35         if ($mode == 0) {
  36                 return $self->{mem}->[ $self->{mem}->[$self->{pc} + $off] ] // 0;
  37         } elsif ($mode == 1) {
  38                 return $self->{mem}->[$self->{pc} + $off] // 0;
  39         } elsif ($mode == 2) {
  40                 return $self->{mem}->[ $self->{mem}->[$self->{pc} + $off ] + $self->{base} ] // 0;
  41         }
  42 }
  43
  44 sub m2pos {
  45         my ($self, $off, $mode) = @_;
  46         if ($mode == 0) {
  47                 return $self->{mem}->[$self->{pc} + $off];
  48         } elsif ($mode == 2) {
  49                 return $self->{mem}->[$self->{pc} + $off] + $self->{base};
  50         }
  51 }
  52
  53 sub input {
  54         my ($self, @input) = @_;
  55         push @{ $self->{inputs} }, @input;
  56 }
  57
  58 sub run {
  59         my ($self, @input) = @_;
  60         my $mem = $self->{mem};
  61
  62         push @{ $self->{inputs} }, @input;
  63         if (defined $self->{want_input}) {
  64                 $mem->[$self->{want_input}] = shift @{ $self->{inputs} };
  65                 $self->{want_input} = undef;
  66         }
  67
  68         while (1) {
  69                 my $opcode = $mem->[$self->{pc}];
  70                 # say "pc=", $self->{pc}, " opcode=$opcode";
  71                 # say "mem=", join(',', map { $_ // '_' } @{ $self->{mem} });
  72                 my $op = int($opcode % 100);
  73                 my $m1 = int($opcode / 100) % 10;
  74                 my $m2 = int($opcode / 1000) % 10;
  75                 my $m3 = int($opcode / 10000) % 10;
  76                 if ($op == 1) {
  77                         $mem->[ m2pos($self, 3, $m3) ]
  78                                 = m2val($self, 1, $m1)
  79                                 + m2val($self, 2, $m2);
  80                         $self->{pc} += 4;
  81                 } elsif ($op == 2) {
  82                         $mem->[ m2pos($self, 3, $m3) ]
  83                                 = m2val($self, 1, $m1)
  84                                 * m2val($self, 2, $m2);
  85                         $self->{pc} += 4;
  86                 } elsif ($op == 3) {
  87                         if (@{ $self->{inputs} }) {
  88                                 $mem->[ m2pos($self, 1, $m1) ]
  89                                         = shift @{ $self->{inputs} };
  90                                 $self->{pc} += 2;
  91                         } else {
  92                                 $self->{want_input} = m2pos($self, 1, $m1);
  93                                 $self->{pc} += 2;
  94                                 return undef;
  95                         }
  96                 } elsif ($op == 4) {
  97                         my $val = m2val($self, 1, $m1);
  98                         $self->{pc} += 2;
  99                         return $val;
 100                 } elsif ($op == 5) {
 101                         if (m2val($self, 1, $m1)) {
 102                                 $self->{pc} = m2val($self, 2, $m2);
 103                         } else {
 104                                 $self->{pc} += 3;
 105                         }
 106                 } elsif ($op == 6) {
 107                         if (!m2val($self, 1, $m1)) {
 108                                 $self->{pc} = m2val($self, 2, $m2);
 109                         } else {
 110                                 $self->{pc} += 3;
 111                         }
 112                 } elsif ($op == 7) {
 113                         $mem->[ m2pos($self, 3, $m3) ] =
 114                                 m2val($self, 1, $m1)
 115                                 < m2val($self, 2, $m2) ? 1 : 0;
 116                         $self->{pc} += 4;
 117                 } elsif ($op == 8) {
 118                         $mem->[ m2pos($self, 3, $m3) ] =
 119                                 m2val($self, 1, $m1)
 120                                 == m2val($self, 2, $m2) ? 1 : 0;
 121                         $self->{pc} += 4;
 122                 } elsif ($op == 9) {
 123                         $self->{base} += m2val($self, 1, $m1);
 124                         $self->{pc} += 2;
 125                 } elsif ($op == 99) {
 126                         return undef;
 127                 }
 128         }
 129 }
 130
 131 package main;
 132
 133 chomp (my @mem = split /,/, <>);
 134
 135 $; = ',';
 136
 137 sub back { my $x = shift; return 1 + (($x-1) ^ 1); }
 138 my %map;
 139 my $c = IntComp->new(\@mem);
 140 $c->{steps} = 0;
 141 $map{10000,10000} = $c;
 142 my @q = ([10_000, 10_000]);
 143 MAINLOOP:
 144 while (my $pos = shift @q) {
 145         my ($x, $y) = @$pos;
 146         my $cmd;
 147         my $orig_comp = $map{$x,$y};
 148         for ([0, -1], [0, 1], [-1, 0], [1, 0]) {
 149                 my $nx = $x + $_->[0];
 150                 my $ny = $y + $_->[1];
 151                 $cmd++;
 152                 next if defined $map{$nx,$ny};
 153                 my $comp = IntComp->clone($orig_comp);
 154                 my $rv = $comp->run($cmd);
 155                 # say "moving from $x, $y to $nx, $ny $cmd: $rv";
 156                 if ($rv == 0) {
 157                         $map{$nx,$ny} = '#';
 158                         next;
 159                 } elsif ($rv == 1) {
 160                         $comp->{steps} = 1 + $orig_comp->{steps};
 161                         $map{$nx,$ny} = $comp;
 162                         push @q, [ $nx, $ny ];
 163                 } elsif ($rv == 2) {
 164                         say "found at $nx, $ny after ", 1 + $orig_comp->{steps},
 165                                 " steps";
 166                         @q = [ $nx, $ny ];
 167                         %map = ();
 168                         $map{$nx,$ny} = $comp;
 169                         $comp->{steps} = 0;
 170                         last MAINLOOP;
 171                 }
 172         }
 173 }
 174
 175 while (my $pos = shift @q) {
 176         my ($x, $y) = @$pos;
 177         my $cmd;
 178         my $orig_comp = $map{$x,$y};
 179         say "at $x, $y steps $orig_comp->{steps}";
 180         for ([0, -1], [0, 1], [-1, 0], [1, 0]) {
 181                 my $nx = $x + $_->[0];
 182                 my $ny = $y + $_->[1];
 183                 $cmd++;
 184                 next if defined $map{$nx,$ny};
 185                 my $comp = IntComp->clone($orig_comp);
 186                 my $rv = $comp->run($cmd);
 187                 # say "moving from $x, $y to $nx, $ny $cmd: $rv";
 188                 if ($rv == 0) {
 189                         $map{$nx,$ny} = '#';
 190                         next;
 191                 }
 192                 $comp->{steps} = 1 + $orig_comp->{steps};
 193                 $map{$nx,$ny} = $comp;
 194                 push @q, [ $nx, $ny ];
 195                 say "to explore $nx, $ny steps $comp->{steps}";
 196         }
 197 }
 198