2018/42.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.36;
   4 use strict;
   5
   6 my @code;
   7 my @regs = ((0) x 6);
   8 my $ip_reg;
   9
  10 while(<STDIN>) {
  11         if (/\A#ip (\d+)/) {
  12                 $ip_reg = $1;
  13                 next;
  14         }
  15         chomp;
  16         push @code, [ split /\s+/ ];
  17 }
  18
  19 my $nmachines = shift @ARGV;
  20 my @machines;
  21 # push @machines, [ ($_, ((0) x 6)) ] for 0 .. $nmachines;
  22 push @machines, [ (10961198, ((0) x 6)) ];
  23
  24 my %seen;
  25 my $prev_halting;
  26
  27 sub one_step($regs) {
  28         my $ip = $regs->[6];
  29         my ($op, $a, $b, $c) = @{ $code[$ip] };
  30
  31         $regs->[$ip_reg] = $ip;
  32
  33         if ($op eq 'addr') {
  34                 $regs->[$c] = $regs->[$a] + $regs->[$b];
  35         } elsif ($op eq 'addi') {
  36                 $regs->[$c] = $regs->[$a] + $b;
  37         } elsif ($op eq 'mulr') {
  38                 $regs->[$c] = $regs->[$a] * $regs->[$b];
  39         } elsif ($op eq 'muli') {
  40                 $regs->[$c] = $regs->[$a] * $b;
  41         } elsif ($op eq 'banr') {
  42                 $regs->[$c] = $regs->[$a] & $regs->[$b];
  43         } elsif ($op eq 'bani') {
  44                 $regs->[$c] = $regs->[$a] & $b;
  45         } elsif ($op eq 'borr') {
  46                 $regs->[$c] = $regs->[$a] | $regs->[$b];
  47         } elsif ($op eq 'bori') {
  48                 $regs->[$c] = $regs->[$a] | $b;
  49         } elsif ($op eq 'setr') {
  50                 $regs->[$c] = $regs->[$a];
  51         } elsif ($op eq 'seti') {
  52                 $regs->[$c] = $a;
  53         } elsif ($op eq 'gtrr') {
  54                 $regs->[$c] = $regs->[$a] > $regs->[$b] ? 1 : 0;
  55         } elsif ($op eq 'gtir') {
  56                 $regs->[$c] = $a > $regs->[$b] ? 1 : 0;
  57         } elsif ($op eq 'eqrr') {
  58                 $regs->[$c] = $regs->[$a] == $regs->[$b] ? 1 : 0;
  59         } elsif ($op eq 'eqri') {
  60                 $regs->[$c] = $regs->[$a] == $b ? 1 : 0;
  61         } elsif ($op eq 'nop') {
  62
  63         } else {
  64                 die "Unknown op $ op at $ip";
  65         }
  66         # say join(' ', @{ $code[$ip] }, "\t", @$regs);
  67         # $regs->[3] = $ARGV[0] if $ip == 35;
  68         $regs->[6] = $regs->[$ip_reg] + 1;
  69
  70         if ($regs->[6] == 28) {
  71                 if ($seen{$regs->[4]}++) {
  72                         say "$regs->[4] already seen";
  73                         return 1;
  74                 }
  75                 say "halts at $regs->[4]\t", sprintf("%08x", $regs->[4]);
  76                 $prev_halting = $regs->[4];
  77         }
  78
  79 #       if ($seen{join(',', @$regs)}++) {
  80 #               say "seen";
  81 #               $regs->[6] = -1;
  82 #               return 0;
  83 #       }
  84         if ($regs->[6] >= @code) {
  85                 say "halts";
  86                 return 1;
  87         } else {
  88                 return undef;
  89         }
  90 }
  91
  92 my $step = 0;
  93 while (1) {
  94         ++$step;
  95         # say "step ", ++$step;
  96         for my $m (0 .. $#machines) {
  97                 next if $machines[$m]->[6] == -1;
  98                 # say "machine $m";
  99                 if (one_step($machines[$m])) {
 100                         say "Machine $m halts after step $step prev $prev_halting";
 101                         exit 0;
 102                 }
 103         }
 104 }
 105