Rest of 2019

[aoc.git] / 2019 / 44.pl

diff --git a/2019/44.pl b/2019/44.pl
new file mode 100755 (executable)
index 0000000..70e317e
--- /dev/null
+++ b/2019/44.pl
@@ -0,0 +1,117 @@
+#!/usr/bin/perl -w
+use v5.38;
+use bigint;
+# use Math::BigInt lib => 'GMP';
+# Math::BigInt->precision(64);
+# say Math::BigInt->precision();
+
+my ($pos, $ncards, $iters) = # @ARGV;
+       # (2020, 119315717514047, 0);
+       (2020, 119315717514047, 101741582076661);
+       # (10, 11, 4);
+       # (28, 29, 1);
+       # (7975, 10007, 0);
+       # (42, 2147483647, 0);
+       # (42, 8589935681, 0);
+
+$ncards = Math::BigInt->new($ncards);
+
+chomp(my @cmds = <STDIN>);
+
+sub simplify {
+       my @cmds = @_;
+
+       RETRY:
+       for my $i (0 .. $#cmds-1) {
+               my $r = $cmds[$i].";".$cmds[$i+1];
+               if ($r =~ /new stack.*new stack/) {
+                       splice @cmds, $i, 2;
+                       goto RETRY;
+               }
+               if ($r =~ /cut (-?\d+);cut (-?\d+)/) {
+                       my $n1 = +(0+$1);
+                       my $n2 = +(0+$2);
+                       splice @cmds, $i, 2,
+                               'cut ' . (($ncards+$n1+$n2) % $ncards);
+                       goto RETRY;
+               }
+               if ($r =~ /increment (\d+);.*increment (\d+)\z/) {
+                       my $n1 = +(0+$1);
+                       my $n2 = +(0+$2);
+                       splice @cmds, $i, 2,
+                               'deal with increment ' . (($n1*$n2) % $ncards);
+                       goto RETRY;
+               }
+               # Try to move "cut" down and possibly merge it
+               if ($r =~ /cut (-?\d+);.*new stack/) {
+                       my $n1 = +(0+$1);
+                       splice @cmds, $i, 2,
+                               'deal into new stack',
+                               'cut ' . (-$n1);
+                       goto RETRY;
+               }
+               if ($r =~ /cut (-?\d+);.*increment (\d+)\z/) {
+                       my $n1 = +(0+$1);
+                       my $n2 = +(0+$2);
+                       splice @cmds, $i, 2,
+                               'deal with increment ' . ($n2),
+                               'cut ' . (($n1*$n2) % $ncards);
+                       goto RETRY;
+               }
+               if ($r =~ /new stack;.*increment (\d+)\z/) {
+                       my $n1 = +(0+$1);
+                       splice @cmds, $i, 2,
+                               'deal with increment ' . ($ncards-$n1),
+                               'cut ' . $n1;
+                       goto RETRY;
+               }
+       }
+       # say "=====\nReturning:\n", join("\n", @cmds);
+       return @cmds;
+}
+
+my $loops = $ncards-1;
+my $n = 0;
+my @repeated_cmds;
+while ((1 << $n) <= $loops) {
+       @cmds = simplify(@cmds);
+       $repeated_cmds[$n] = [ @cmds ];
+       $n++;
+       @cmds = (@cmds, @cmds);
+}
+
+sub apply {
+       my ($cmds, $pos) = @_;
+
+       # say "apply $pos:";
+       for (@$cmds) {
+               if (/new stack/) {
+                       $pos = $ncards-1-$pos;
+               } elsif (/increment (\d+)/) {
+                       $pos *= $1;
+                       $pos %= $ncards;
+               } elsif (/cut (\d+)/) {
+                       $pos -= $1;
+                       $pos %= $ncards;
+               } elsif (/cut (-\d+)/) {
+                       $pos -= $1;
+                       $pos %= $ncards;
+               }
+       }
+       return $pos;
+}
+
+my $l = $ncards - 1 - $iters;
+my @r;
+while ($n--) {
+       my $two = 1 << $n;
+       # say "1 << $n == $two, rem $l";
+       if ($l >= $two) {
+               push @r, @{ $repeated_cmds[$n] };
+               $l -= $two;
+       }
+}
+@r = simplify(@r);
+say "Rules\n", join("\n", @r);
+say apply(\@r, $pos);
+