Year 2018

[aoc.git] / 2018 / 42.pl

diff --git a/2018/42.pl b/2018/42.pl
new file mode 100755 (executable)
index 0000000..9a4f095
--- /dev/null
+++ b/2018/42.pl
@@ -0,0 +1,105 @@
+#!/usr/bin/perl -w
+
+use v5.36;
+use strict;
+
+my @code;
+my @regs = ((0) x 6);
+my $ip_reg;
+
+while(<STDIN>) {
+       if (/\A#ip (\d+)/) {
+               $ip_reg = $1;
+               next;
+       }
+       chomp;
+       push @code, [ split /\s+/ ];
+}
+
+my $nmachines = shift @ARGV;
+my @machines;
+# push @machines, [ ($_, ((0) x 6)) ] for 0 .. $nmachines;
+push @machines, [ (10961198, ((0) x 6)) ];
+
+my %seen;
+my $prev_halting;
+
+sub one_step($regs) {
+       my $ip = $regs->[6];
+       my ($op, $a, $b, $c) = @{ $code[$ip] };
+
+       $regs->[$ip_reg] = $ip;
+
+       if ($op eq 'addr') {
+               $regs->[$c] = $regs->[$a] + $regs->[$b];
+       } elsif ($op eq 'addi') {
+               $regs->[$c] = $regs->[$a] + $b;
+       } elsif ($op eq 'mulr') {
+               $regs->[$c] = $regs->[$a] * $regs->[$b];
+       } elsif ($op eq 'muli') {
+               $regs->[$c] = $regs->[$a] * $b;
+       } elsif ($op eq 'banr') {
+               $regs->[$c] = $regs->[$a] & $regs->[$b];
+       } elsif ($op eq 'bani') {
+               $regs->[$c] = $regs->[$a] & $b;
+       } elsif ($op eq 'borr') {
+               $regs->[$c] = $regs->[$a] | $regs->[$b];
+       } elsif ($op eq 'bori') {
+               $regs->[$c] = $regs->[$a] | $b;
+       } elsif ($op eq 'setr') {
+               $regs->[$c] = $regs->[$a];
+       } elsif ($op eq 'seti') {
+               $regs->[$c] = $a;
+       } elsif ($op eq 'gtrr') {
+               $regs->[$c] = $regs->[$a] > $regs->[$b] ? 1 : 0;
+       } elsif ($op eq 'gtir') {
+               $regs->[$c] = $a > $regs->[$b] ? 1 : 0;
+       } elsif ($op eq 'eqrr') {
+               $regs->[$c] = $regs->[$a] == $regs->[$b] ? 1 : 0;
+       } elsif ($op eq 'eqri') {
+               $regs->[$c] = $regs->[$a] == $b ? 1 : 0;
+       } elsif ($op eq 'nop') {
+               
+       } else {
+               die "Unknown op $ op at $ip";
+       }
+       # say join(' ', @{ $code[$ip] }, "\t", @$regs);
+       # $regs->[3] = $ARGV[0] if $ip == 35;
+       $regs->[6] = $regs->[$ip_reg] + 1;
+
+       if ($regs->[6] == 28) {
+               if ($seen{$regs->[4]}++) {
+                       say "$regs->[4] already seen";
+                       return 1;
+               }
+               say "halts at $regs->[4]\t", sprintf("%08x", $regs->[4]);
+               $prev_halting = $regs->[4];
+       }
+       
+#      if ($seen{join(',', @$regs)}++) {
+#              say "seen";
+#              $regs->[6] = -1;
+#              return 0;
+#      }
+       if ($regs->[6] >= @code) {
+               say "halts";
+               return 1;
+       } else {
+               return undef;
+       }
+}
+
+my $step = 0;
+while (1) {
+       ++$step;
+       # say "step ", ++$step;
+       for my $m (0 .. $#machines) {
+               next if $machines[$m]->[6] == -1;
+               # say "machine $m";
+               if (one_step($machines[$m])) {
+                       say "Machine $m halts after step $step prev $prev_halting";
+                       exit 0;
+               }
+       }
+}
+