From 8cf8b4ef795669e7787670bdd6811cd2095bf75f Mon Sep 17 00:00:00 2001 From: "Jan \"Yenya\" Kasprzak" Date: Tue, 21 Nov 2023 22:35:11 +0100 Subject: [PATCH] Rest of 2019 --- 2019/39.pl | 72 +++++++++++++++++++++ 2019/40.pl | 78 ++++++++++++++++++++++ 2019/41.pl | 155 ++++++++++++++++++++++++++++++++++++++++++++ 2019/42.pl | 159 +++++++++++++++++++++++++++++++++++++++++++++ 2019/43.pl | 32 +++++++++ 2019/44.pl | 117 +++++++++++++++++++++++++++++++++ 2019/45.pl | 171 ++++++++++++++++++++++++++++++++++++++++++++++++ 2019/46.pl | 187 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2019/47.pl | 43 ++++++++++++ 2019/48.pl | 68 +++++++++++++++++++ 2019/49.pl | 159 +++++++++++++++++++++++++++++++++++++++++++++ 2019/50.pl | 5 ++ 12 files changed, 1246 insertions(+) create mode 100755 2019/39.pl create mode 100755 2019/40.pl create mode 100755 2019/41.pl create mode 100755 2019/42.pl create mode 100755 2019/43.pl create mode 100755 2019/44.pl create mode 100755 2019/45.pl create mode 100755 2019/46.pl create mode 100755 2019/47.pl create mode 100755 2019/48.pl create mode 100755 2019/49.pl create mode 100755 2019/50.pl diff --git a/2019/39.pl b/2019/39.pl new file mode 100755 index 0000000..b067ebd --- /dev/null +++ b/2019/39.pl @@ -0,0 +1,72 @@ +#!/usr/bin/perl -w + +use v5.16; + +my @map = map { chomp; [ split // ] } <>; +my $maxx = @{ $map[0] }; +my $maxy = @map; + +$; = ','; + +my %portals; + +sub add_portal { + my ($name, $x, $y) = @_; + say "add_portal: $name, $x, $y"; + if (defined $portals{$name}) { + my ($x1, $y1) = @{ $portals{$name} }; + $map[$y][$x] = [$x1, $y1]; + $map[$y1][$x1] = [$x, $y]; + say "portal $name: $x,$y <==> $x1,$y1"; + } else { + $portals{$name} = [$x, $y]; + } +} + +sub find_portals { + my @d = @_; + for my $x (2 .. $maxx-3) { + for my $y (2 .. $maxy-3) { + next if $map[$y][$x] ne '.'; + my $l1 = $map[$y+$d[1]][$x+$d[0]]; + my $l2 = $map[$y+$d[3]][$x+$d[2]]; + next if "$l1$l2" !~ /^[A-Z][A-Z]$/; + add_portal("$l1$l2", $x, $y); + } + } +} + +find_portals(0, -2, 0, -1); +find_portals(0, 1, 0, 2); +find_portals(-2, 0, -1, 0); +find_portals(1, 0, 2, 0); + + +my %seen; +my @q = [ @{ $portals{'AA'} }, 0 ]; +my ($ex, $ey) = @{ $portals{'ZZ'} }; +say "walking towards $ex, $ey"; + +while (@q) { + my ($x, $y, $steps) = @{ shift @q }; + next if $seen{$x,$y}++; + say "at $x,$y $steps"; + + if ($x == $ex && $y == $ey) { + say "Found after $steps steps"; + last; + } + + $steps++; + if (ref $map[$y][$x]) { + my ($nx, $ny) = @{ $map[$y][$x] }; + push @q, [ $nx, $ny, $steps ]; + } + for my ($dx, $dy) (0, 1, 1, 0, -1, 0, 0, -1) { + my $nx = $x + $dx; + my $ny = $y + $dy; + next if $map[$ny][$nx] ne '.' && !ref $map[$ny][$nx]; + push @q, [$nx, $ny, $steps]; + } +} + diff --git a/2019/40.pl b/2019/40.pl new file mode 100755 index 0000000..27ea338 --- /dev/null +++ b/2019/40.pl @@ -0,0 +1,78 @@ +#!/usr/bin/perl -w + +use v5.16; + +my @map = map { chomp; [ split // ] } <>; +my $maxx = @{ $map[0] }; +my $maxy = @map; + +$; = ','; + +my %portals; + +sub add_portal { + my ($name, $x, $y) = @_; + say "add_portal: $name, $x, $y"; + if (defined $portals{$name}) { + my ($x1, $y1) = @{ $portals{$name} }; + $map[$y][$x] = [$x1, $y1]; + $map[$y1][$x1] = [$x, $y]; + say "portal $name: $x,$y <==> $x1,$y1"; + } else { + $portals{$name} = [$x, $y]; + } +} + +sub find_portals { + my @d = @_; + for my $x (2 .. $maxx-3) { + for my $y (2 .. $maxy-3) { + next if $map[$y][$x] ne '.'; + my $l1 = $map[$y+$d[1]][$x+$d[0]]; + my $l2 = $map[$y+$d[3]][$x+$d[2]]; + next if "$l1$l2" !~ /^[A-Z][A-Z]$/; + add_portal("$l1$l2", $x, $y); + } + } +} + +find_portals(0, -2, 0, -1); +find_portals(0, 1, 0, 2); +find_portals(-2, 0, -1, 0); +find_portals(1, 0, 2, 0); + + +my %seen; +my @q = [ @{ $portals{'AA'} }, 0, 0 ]; +my ($ex, $ey) = @{ $portals{'ZZ'} }; +say "walking towards $ex, $ey, 0"; + +while (@q) { + my ($x, $y, $z, $steps) = @{ shift @q }; + next if $seen{$x,$y,$z}++; + say "at $x,$y,$z $steps"; + + if ($x == $ex && $y == $ey && $z == 0) { + say "Found after $steps steps"; + last; + } + + $steps++; + if (ref $map[$y][$x]) { + my ($nx, $ny) = @{ $map[$y][$x] }; + if ($x == 2 || $y == 2 || $x == $maxx - 3 || $y == $maxy - 3) { + if ($z > 0) { + push @q, [ $nx, $ny, $z-1, $steps ]; + } + } else { + push @q, [ $nx, $ny, $z+1, $steps ]; + } + } + for my ($dx, $dy) (0, 1, 1, 0, -1, 0, 0, -1) { + my $nx = $x + $dx; + my $ny = $y + $dy; + next if $map[$ny][$nx] ne '.' && !ref $map[$ny][$nx]; + push @q, [$nx, $ny, $z, $steps]; + } +} + diff --git a/2019/41.pl b/2019/41.pl new file mode 100755 index 0000000..a8c57ef --- /dev/null +++ b/2019/41.pl @@ -0,0 +1,155 @@ +#!/usr/bin/perl -w + +use v5.16; + +package IntComp; +use bigint; + +sub new { + my ($class, $mem, $inputs) = @_; + my $self = { + mem => [ @$mem ], + pc => 0, + want_input => undef, + base => 0, + }; + $self->{inputs} = [ @$inputs ] + if defined $inputs; + bless $self, $class; +} + +sub clone { + my ($class, $other) = @_; + my $self = { + mem => [ @{ $other->{mem} } ], + pc => $other->{pc}, + want_input => undef, + base => $other->{base}, + inputs => [ ], + }; + bless $self, $class; +} + +sub m2val { + my ($self, $off, $mode) = @_; + if ($mode == 0) { + return $self->{mem}->[ $self->{mem}->[$self->{pc} + $off] ] // 0; + } elsif ($mode == 1) { + return $self->{mem}->[$self->{pc} + $off] // 0; + } elsif ($mode == 2) { + return $self->{mem}->[ $self->{mem}->[$self->{pc} + $off ] + $self->{base} ] // 0; + } +} + +sub m2pos { + my ($self, $off, $mode) = @_; + if ($mode == 0) { + return $self->{mem}->[$self->{pc} + $off]; + } elsif ($mode == 2) { + return $self->{mem}->[$self->{pc} + $off] + $self->{base}; + } +} + +sub input { + my ($self, @input) = @_; + push @{ $self->{inputs} }, @input; +} + +sub run { + my ($self, @input) = @_; + my $mem = $self->{mem}; + + push @{ $self->{inputs} }, @input; + if (defined $self->{want_input}) { + $mem->[$self->{want_input}] = shift @{ $self->{inputs} }; + $self->{want_input} = undef; + } + + while (1) { + my $opcode = $mem->[$self->{pc}]; + # say "pc=", $self->{pc}, " opcode=$opcode"; + # say "mem=", join(',', map { $_ // '_' } @{ $self->{mem} }); + my $op = int($opcode % 100); + my $m1 = int($opcode / 100) % 10; + my $m2 = int($opcode / 1000) % 10; + my $m3 = int($opcode / 10000) % 10; + if ($op == 1) { + $mem->[ m2pos($self, 3, $m3) ] + = m2val($self, 1, $m1) + + m2val($self, 2, $m2); + $self->{pc} += 4; + } elsif ($op == 2) { + $mem->[ m2pos($self, 3, $m3) ] + = m2val($self, 1, $m1) + * m2val($self, 2, $m2); + $self->{pc} += 4; + } elsif ($op == 3) { + if (@{ $self->{inputs} }) { + $mem->[ m2pos($self, 1, $m1) ] + = shift @{ $self->{inputs} }; + $self->{pc} += 2; + } else { + $self->{want_input} = m2pos($self, 1, $m1); + $self->{pc} += 2; + return undef; + } + } elsif ($op == 4) { + my $val = m2val($self, 1, $m1); + $self->{pc} += 2; + return $val; + } elsif ($op == 5) { + if (m2val($self, 1, $m1)) { + $self->{pc} = m2val($self, 2, $m2); + } else { + $self->{pc} += 3; + } + } elsif ($op == 6) { + if (!m2val($self, 1, $m1)) { + $self->{pc} = m2val($self, 2, $m2); + } else { + $self->{pc} += 3; + } + } elsif ($op == 7) { + $mem->[ m2pos($self, 3, $m3) ] = + m2val($self, 1, $m1) + < m2val($self, 2, $m2) ? 1 : 0; + $self->{pc} += 4; + } elsif ($op == 8) { + $mem->[ m2pos($self, 3, $m3) ] = + m2val($self, 1, $m1) + == m2val($self, 2, $m2) ? 1 : 0; + $self->{pc} += 4; + } elsif ($op == 9) { + $self->{base} += m2val($self, 1, $m1); + $self->{pc} += 2; + } elsif ($op == 99) { + return undef; + } + } +} + +package main; + +chomp (my @mem = split /,/, <>); + +$; = ','; + +my $input = <new(\@mem, [ map { ord } split //, $input ]); + +while (my $rv = $comp->run()) { + if ($rv > 126) { + say $rv; + } else { + print chr($rv); + } +} diff --git a/2019/42.pl b/2019/42.pl new file mode 100755 index 0000000..62c6ed4 --- /dev/null +++ b/2019/42.pl @@ -0,0 +1,159 @@ +#!/usr/bin/perl -w + +use v5.16; + +package IntComp; +use bigint; + +sub new { + my ($class, $mem, $inputs) = @_; + my $self = { + mem => [ @$mem ], + pc => 0, + want_input => undef, + base => 0, + }; + $self->{inputs} = [ @$inputs ] + if defined $inputs; + bless $self, $class; +} + +sub clone { + my ($class, $other) = @_; + my $self = { + mem => [ @{ $other->{mem} } ], + pc => $other->{pc}, + want_input => undef, + base => $other->{base}, + inputs => [ ], + }; + bless $self, $class; +} + +sub m2val { + my ($self, $off, $mode) = @_; + if ($mode == 0) { + return $self->{mem}->[ $self->{mem}->[$self->{pc} + $off] ] // 0; + } elsif ($mode == 1) { + return $self->{mem}->[$self->{pc} + $off] // 0; + } elsif ($mode == 2) { + return $self->{mem}->[ $self->{mem}->[$self->{pc} + $off ] + $self->{base} ] // 0; + } +} + +sub m2pos { + my ($self, $off, $mode) = @_; + if ($mode == 0) { + return $self->{mem}->[$self->{pc} + $off]; + } elsif ($mode == 2) { + return $self->{mem}->[$self->{pc} + $off] + $self->{base}; + } +} + +sub input { + my ($self, @input) = @_; + push @{ $self->{inputs} }, @input; +} + +sub run { + my ($self, @input) = @_; + my $mem = $self->{mem}; + + push @{ $self->{inputs} }, @input; + if (defined $self->{want_input}) { + $mem->[$self->{want_input}] = shift @{ $self->{inputs} }; + $self->{want_input} = undef; + } + + while (1) { + my $opcode = $mem->[$self->{pc}]; + # say "pc=", $self->{pc}, " opcode=$opcode"; + # say "mem=", join(',', map { $_ // '_' } @{ $self->{mem} }); + my $op = int($opcode % 100); + my $m1 = int($opcode / 100) % 10; + my $m2 = int($opcode / 1000) % 10; + my $m3 = int($opcode / 10000) % 10; + if ($op == 1) { + $mem->[ m2pos($self, 3, $m3) ] + = m2val($self, 1, $m1) + + m2val($self, 2, $m2); + $self->{pc} += 4; + } elsif ($op == 2) { + $mem->[ m2pos($self, 3, $m3) ] + = m2val($self, 1, $m1) + * m2val($self, 2, $m2); + $self->{pc} += 4; + } elsif ($op == 3) { + if (@{ $self->{inputs} }) { + $mem->[ m2pos($self, 1, $m1) ] + = shift @{ $self->{inputs} }; + $self->{pc} += 2; + } else { + $self->{want_input} = m2pos($self, 1, $m1); + $self->{pc} += 2; + return undef; + } + } elsif ($op == 4) { + my $val = m2val($self, 1, $m1); + $self->{pc} += 2; + return $val; + } elsif ($op == 5) { + if (m2val($self, 1, $m1)) { + $self->{pc} = m2val($self, 2, $m2); + } else { + $self->{pc} += 3; + } + } elsif ($op == 6) { + if (!m2val($self, 1, $m1)) { + $self->{pc} = m2val($self, 2, $m2); + } else { + $self->{pc} += 3; + } + } elsif ($op == 7) { + $mem->[ m2pos($self, 3, $m3) ] = + m2val($self, 1, $m1) + < m2val($self, 2, $m2) ? 1 : 0; + $self->{pc} += 4; + } elsif ($op == 8) { + $mem->[ m2pos($self, 3, $m3) ] = + m2val($self, 1, $m1) + == m2val($self, 2, $m2) ? 1 : 0; + $self->{pc} += 4; + } elsif ($op == 9) { + $self->{base} += m2val($self, 1, $m1); + $self->{pc} += 2; + } elsif ($op == 99) { + return undef; + } + } +} + +package main; + +chomp (my @mem = split /,/, <>); + +$; = ','; + +my $input = <new(\@mem, [ map { ord } split //, $input ]); + +while (my $rv = $comp->run()) { + if ($rv > 126) { + say $rv; + } else { + print chr($rv); + } +} diff --git a/2019/43.pl b/2019/43.pl new file mode 100755 index 0000000..be352c5 --- /dev/null +++ b/2019/43.pl @@ -0,0 +1,32 @@ +#!/usr/bin/perl -w + +use v5.16; + +my @deck = (0 .. 10006); +# my @deck = (0 .. 9); + +while (<>) { + if (/new stack/) { + @deck = reverse @deck; + } elsif (/increment (\d+)/) { + my @nd; + my $p = 0; + for (@deck) { + $nd[$p] = $_; + $p += $1; + $p %= @deck; + } + @deck = @nd; + } elsif (/cut (\d+)/) { + push @deck, splice @deck, 0, $1; + } elsif (/cut (-\d+)/) { + unshift @deck, splice @deck, $1; + } + say join(' ', @deck); +} + +my $p = 0; +for (@deck) { + say "pos $p" if $_ == 2019; + $p++; +} diff --git a/2019/44.pl b/2019/44.pl new file mode 100755 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 = ); + +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); + diff --git a/2019/45.pl b/2019/45.pl new file mode 100755 index 0000000..9342c73 --- /dev/null +++ b/2019/45.pl @@ -0,0 +1,171 @@ +#!/usr/bin/perl -w + +use v5.16; + +package IntComp; +use bigint; + +sub new { + my ($class, $mem, $inputs) = @_; + my $self = { + mem => [ @$mem ], + pc => 0, + want_input => undef, + base => 0, + }; + $self->{inputs} = [ @$inputs ] + if defined $inputs; + bless $self, $class; +} + +sub clone { + my ($class, $other) = @_; + my $self = { + mem => [ @{ $other->{mem} } ], + pc => $other->{pc}, + want_input => undef, + base => $other->{base}, + inputs => [ ], + }; + bless $self, $class; +} + +sub m2val { + my ($self, $off, $mode) = @_; + if ($mode == 0) { + return $self->{mem}->[ $self->{mem}->[$self->{pc} + $off] ] // 0; + } elsif ($mode == 1) { + return $self->{mem}->[$self->{pc} + $off] // 0; + } elsif ($mode == 2) { + return $self->{mem}->[ $self->{mem}->[$self->{pc} + $off ] + $self->{base} ] // 0; + } +} + +sub m2pos { + my ($self, $off, $mode) = @_; + if ($mode == 0) { + return $self->{mem}->[$self->{pc} + $off]; + } elsif ($mode == 2) { + return $self->{mem}->[$self->{pc} + $off] + $self->{base}; + } +} + +sub input { + my ($self, @input) = @_; + push @{ $self->{inputs} }, @input; +} + +sub run { + my ($self, @input) = @_; + my $mem = $self->{mem}; + + push @{ $self->{inputs} }, @input; + if (defined $self->{want_input}) { + $mem->[$self->{want_input}] = shift @{ $self->{inputs} }; + $self->{want_input} = undef; + } + + while (1) { + my $opcode = $mem->[$self->{pc}]; + # say "pc=", $self->{pc}, " opcode=$opcode"; + # say "mem=", join(',', map { $_ // '_' } @{ $self->{mem} }); + my $op = int($opcode % 100); + my $m1 = int($opcode / 100) % 10; + my $m2 = int($opcode / 1000) % 10; + my $m3 = int($opcode / 10000) % 10; + if ($op == 1) { + $mem->[ m2pos($self, 3, $m3) ] + = m2val($self, 1, $m1) + + m2val($self, 2, $m2); + $self->{pc} += 4; + } elsif ($op == 2) { + $mem->[ m2pos($self, 3, $m3) ] + = m2val($self, 1, $m1) + * m2val($self, 2, $m2); + $self->{pc} += 4; + } elsif ($op == 3) { + if (@{ $self->{inputs} }) { + $mem->[ m2pos($self, 1, $m1) ] + = shift @{ $self->{inputs} }; + $self->{pc} += 2; + } else { + $self->{want_input} = m2pos($self, 1, $m1); + $self->{pc} += 2; + return undef; + } + } elsif ($op == 4) { + my $val = m2val($self, 1, $m1); + $self->{pc} += 2; + return $val; + } elsif ($op == 5) { + if (m2val($self, 1, $m1)) { + $self->{pc} = m2val($self, 2, $m2); + } else { + $self->{pc} += 3; + } + } elsif ($op == 6) { + if (!m2val($self, 1, $m1)) { + $self->{pc} = m2val($self, 2, $m2); + } else { + $self->{pc} += 3; + } + } elsif ($op == 7) { + $mem->[ m2pos($self, 3, $m3) ] = + m2val($self, 1, $m1) + < m2val($self, 2, $m2) ? 1 : 0; + $self->{pc} += 4; + } elsif ($op == 8) { + $mem->[ m2pos($self, 3, $m3) ] = + m2val($self, 1, $m1) + == m2val($self, 2, $m2) ? 1 : 0; + $self->{pc} += 4; + } elsif ($op == 9) { + $self->{base} += m2val($self, 1, $m1); + $self->{pc} += 2; + } elsif ($op == 99) { + return undef; + } + } +} + +package main; + +chomp (my @mem = split /,/, <>); + +$; = ','; + +my @comps; +for (0 .. 49) { + push @comps, IntComp->new(\@mem, [ $_ ]); +} + +my @queues; +push @queues, [] for 1 .. 50; + +while(1) { +for my $i (0 .. 49) { + my $c = $comps[$i]; + my $dst = $c->run; + if (!defined $dst) { + say "$i wants input"; + my $q = $queues[$i]; + if (defined $q->[0]) { + my $in = shift @$q; + $c->input(@$in); + say "$i received @$in"; + } else { + say "$i queue empty"; + $c->input(-1); + } + } else { + my ($x, $y) = ($c->run, $c->run); + + say "$i sends $dst $x $y"; + my $q = $queues[$dst]; + push @$q, [$x, $y]; + if ($dst == 255) { + exit 0; + } + } +} +} diff --git a/2019/46.pl b/2019/46.pl new file mode 100755 index 0000000..c66cee6 --- /dev/null +++ b/2019/46.pl @@ -0,0 +1,187 @@ +#!/usr/bin/perl -w + +use v5.16; + +package IntComp; +use bigint; + +sub new { + my ($class, $mem, $inputs) = @_; + my $self = { + mem => [ @$mem ], + pc => 0, + want_input => undef, + base => 0, + }; + $self->{inputs} = [ @$inputs ] + if defined $inputs; + bless $self, $class; +} + +sub clone { + my ($class, $other) = @_; + my $self = { + mem => [ @{ $other->{mem} } ], + pc => $other->{pc}, + want_input => undef, + base => $other->{base}, + inputs => [ ], + }; + bless $self, $class; +} + +sub m2val { + my ($self, $off, $mode) = @_; + if ($mode == 0) { + return $self->{mem}->[ $self->{mem}->[$self->{pc} + $off] ] // 0; + } elsif ($mode == 1) { + return $self->{mem}->[$self->{pc} + $off] // 0; + } elsif ($mode == 2) { + return $self->{mem}->[ $self->{mem}->[$self->{pc} + $off ] + $self->{base} ] // 0; + } +} + +sub m2pos { + my ($self, $off, $mode) = @_; + if ($mode == 0) { + return $self->{mem}->[$self->{pc} + $off]; + } elsif ($mode == 2) { + return $self->{mem}->[$self->{pc} + $off] + $self->{base}; + } +} + +sub input { + my ($self, @input) = @_; + push @{ $self->{inputs} }, @input; +} + +sub run { + my ($self, @input) = @_; + my $mem = $self->{mem}; + + push @{ $self->{inputs} }, @input; + if (defined $self->{want_input}) { + $mem->[$self->{want_input}] = shift @{ $self->{inputs} }; + $self->{want_input} = undef; + } + + while (1) { + my $opcode = $mem->[$self->{pc}]; + # say "pc=", $self->{pc}, " opcode=$opcode"; + # say "mem=", join(',', map { $_ // '_' } @{ $self->{mem} }); + my $op = int($opcode % 100); + my $m1 = int($opcode / 100) % 10; + my $m2 = int($opcode / 1000) % 10; + my $m3 = int($opcode / 10000) % 10; + if ($op == 1) { + $mem->[ m2pos($self, 3, $m3) ] + = m2val($self, 1, $m1) + + m2val($self, 2, $m2); + $self->{pc} += 4; + } elsif ($op == 2) { + $mem->[ m2pos($self, 3, $m3) ] + = m2val($self, 1, $m1) + * m2val($self, 2, $m2); + $self->{pc} += 4; + } elsif ($op == 3) { + if (@{ $self->{inputs} }) { + $mem->[ m2pos($self, 1, $m1) ] + = shift @{ $self->{inputs} }; + $self->{pc} += 2; + } else { + $self->{want_input} = m2pos($self, 1, $m1); + $self->{pc} += 2; + return undef; + } + } elsif ($op == 4) { + my $val = m2val($self, 1, $m1); + $self->{pc} += 2; + return $val; + } elsif ($op == 5) { + if (m2val($self, 1, $m1)) { + $self->{pc} = m2val($self, 2, $m2); + } else { + $self->{pc} += 3; + } + } elsif ($op == 6) { + if (!m2val($self, 1, $m1)) { + $self->{pc} = m2val($self, 2, $m2); + } else { + $self->{pc} += 3; + } + } elsif ($op == 7) { + $mem->[ m2pos($self, 3, $m3) ] = + m2val($self, 1, $m1) + < m2val($self, 2, $m2) ? 1 : 0; + $self->{pc} += 4; + } elsif ($op == 8) { + $mem->[ m2pos($self, 3, $m3) ] = + m2val($self, 1, $m1) + == m2val($self, 2, $m2) ? 1 : 0; + $self->{pc} += 4; + } elsif ($op == 9) { + $self->{base} += m2val($self, 1, $m1); + $self->{pc} += 2; + } elsif ($op == 99) { + return undef; + } + } +} + +package main; + +chomp (my @mem = split /,/, <>); + +$; = ','; + +my @comps; +for (0 .. 49) { + push @comps, IntComp->new(\@mem, [ $_ ]); +} + +my @queues; +push @queues, [] for 1 .. 50; + +my @nat; +my $prev_y; + +while(1) { + my $idle = 1; + for my $i (0 .. 49) { + my $c = $comps[$i]; + my $dst = $c->run; + if (!defined $dst) { + say "$i wants input"; + my $q = $queues[$i]; + if (defined $q->[0]) { + my $in = shift @$q; + $c->input(@$in); + say "$i received @$in"; + $idle = 0; + } else { + say "$i queue empty"; + $c->input(-1); + } + } else { + my ($x, $y) = ($c->run, $c->run); + + say "$i sends $dst $x $y"; + $idle = 0; + if ($dst == 255) { + @nat = ($x, $y); + } else { + my $q = $queues[$dst]; + push @$q, [$x, $y]; + } + } + } + if ($idle) { + say "all idle, sending ", join(' ', @nat), " to 0"; + $comps[0]->input(@nat); + if (defined $prev_y && $nat[1] == $prev_y) { + say "$prev_y sent second time"; + exit 0; + } + $prev_y = $nat[1]; + } +} diff --git a/2019/47.pl b/2019/47.pl new file mode 100755 index 0000000..c02aaf9 --- /dev/null +++ b/2019/47.pl @@ -0,0 +1,43 @@ +#!/usr/bin/perl -w + +use v5.16; + +my @map = map { chomp; [ split // ] } <>; + +my $min; +my %seen; +while (1) { + say "After ", ++$min, ":"; + my @nm; + for my $y (0 .. 4) { + for my $x (0 .. 4) { + my $sum = 0; + for my ($dx, $dy) (1, 0, 0, 1, -1, 0, 0, -1) { + my $nx = $x + $dx; + my $ny = $y + $dy; + next if $nx < 0 || $nx > 4 || $ny < 0 || $ny > 4; + $sum++ if $map[$ny][$nx] eq '#'; + } + # say "at $x $y neigbors $sum"; + if ($map[$y][$x] eq '#') { + $nm[$y][$x] = $sum == 1 ? '#' : '.'; + } else { + $nm[$y][$x] = $sum == 1 || $sum == 2 ? '#' : '.'; + } + print $nm[$y][$x]; + } + print "\n"; + } + @map = @nm; + my $key = join('', map { join('', @$_) } @map); + if ($seen{$key}) { + say "this one was last seen at min $seen{$key}"; + my $b = reverse $key; + $b =~ tr/.#/01/; + say oct "0b$b"; + last; + } + $seen{$key} = $min; + print "\n"; +} + diff --git a/2019/48.pl b/2019/48.pl new file mode 100755 index 0000000..bf0bdd4 --- /dev/null +++ b/2019/48.pl @@ -0,0 +1,68 @@ +#!/usr/bin/perl -w + +use v5.16; + +my @map = [ map { chomp; [ split // ] } <> ]; + +my $min; +my $levels = 0; +while (1) { + say "After ", ++$min, ":"; + my $count = 0; + my @nm; + $levels += 2; + for my $l (0 .. $levels) { + say "Depth ", $l - $min; + for my $y (0 .. 4) { + for my $x (0 .. 4) { + my $sum = 0; + my @pts; + for my ($dx, $dy) (1, 0, 0, 1, -1, 0, 0, -1) { + my $nx = $x + $dx; + my $ny = $y + $dy; + if ($nx < 0) { + push @pts, [$l-2, 2, 1]; # L Y X + } elsif ($ny < 0) { + push @pts, [$l-2, 1, 2]; + } elsif ($nx > 4) { + push @pts, [$l-2, 2, 3]; + } elsif ($ny > 4) { + push @pts, [$l-2, 3, 2]; + } elsif ($nx == 2 && $ny == 2) { + if ($x == 1) { + push @pts, [$l, $_, 0] for 0 .. 4; + } elsif ($y == 1) { + push @pts, [$l, 0, $_] for 0 .. 4; + } elsif ($x == 3) { + push @pts, [$l, $_, 4] for 0 .. 4; + } elsif ($y == 3) { + push @pts, [$l, 4, $_] for 0 .. 4; + } + } else { + push @pts, [$l-1, $ny, $nx]; + } + } + for my $pt (@pts) { + my ($nl, $ny, $nx) = @$pt; + next if $nl < 0 || $nl > $levels-2; + $sum++ if $map[$nl][$ny][$nx] eq '#'; + } + if ($x == 2 & $y == 2) { + $nm[$l][$y][$x] = '?'; + } elsif ($l > 0 && $l <= $levels-1 && $map[$l-1][$y][$x] eq '#') { + $nm[$l][$y][$x] = $sum == 1 ? '#' : '.'; + } else { + $nm[$l][$y][$x] = $sum == 1 || $sum == 2 ? '#' : '.'; + } + print $nm[$l][$y][$x]; + $count++ if $nm[$l][$y][$x] eq '#'; + } + print "\n"; + } + print "\n"; + } + @map = @nm; + print "==== $count ====\n"; + last if $min >= 200; +} + diff --git a/2019/49.pl b/2019/49.pl new file mode 100755 index 0000000..c734f7f --- /dev/null +++ b/2019/49.pl @@ -0,0 +1,159 @@ +#!/usr/bin/perl -w + +use v5.16; + +package IntComp; +use bigint; + +sub new { + my ($class, $mem, $inputs) = @_; + my $self = { + mem => [ @$mem ], + pc => 0, + want_input => undef, + base => 0, + }; + $self->{inputs} = [ @$inputs ] + if defined $inputs; + bless $self, $class; +} + +sub clone { + my ($class, $other) = @_; + my $self = { + mem => [ @{ $other->{mem} } ], + pc => $other->{pc}, + want_input => undef, + base => $other->{base}, + inputs => [ ], + }; + bless $self, $class; +} + +sub m2val { + my ($self, $off, $mode) = @_; + if ($mode == 0) { + return $self->{mem}->[ $self->{mem}->[$self->{pc} + $off] ] // 0; + } elsif ($mode == 1) { + return $self->{mem}->[$self->{pc} + $off] // 0; + } elsif ($mode == 2) { + return $self->{mem}->[ $self->{mem}->[$self->{pc} + $off ] + $self->{base} ] // 0; + } +} + +sub m2pos { + my ($self, $off, $mode) = @_; + if ($mode == 0) { + return $self->{mem}->[$self->{pc} + $off]; + } elsif ($mode == 2) { + return $self->{mem}->[$self->{pc} + $off] + $self->{base}; + } +} + +sub input { + my ($self, @input) = @_; + push @{ $self->{inputs} }, @input; +} + +sub run { + my ($self, @input) = @_; + my $mem = $self->{mem}; + + push @{ $self->{inputs} }, @input; + if (defined $self->{want_input}) { + $mem->[$self->{want_input}] = shift @{ $self->{inputs} }; + $self->{want_input} = undef; + } + + while (1) { + my $opcode = $mem->[$self->{pc}]; + # say "pc=", $self->{pc}, " opcode=$opcode"; + # say "mem=", join(',', map { $_ // '_' } @{ $self->{mem} }); + my $op = int($opcode % 100); + my $m1 = int($opcode / 100) % 10; + my $m2 = int($opcode / 1000) % 10; + my $m3 = int($opcode / 10000) % 10; + if ($op == 1) { + $mem->[ m2pos($self, 3, $m3) ] + = m2val($self, 1, $m1) + + m2val($self, 2, $m2); + $self->{pc} += 4; + } elsif ($op == 2) { + $mem->[ m2pos($self, 3, $m3) ] + = m2val($self, 1, $m1) + * m2val($self, 2, $m2); + $self->{pc} += 4; + } elsif ($op == 3) { + if (@{ $self->{inputs} }) { + $mem->[ m2pos($self, 1, $m1) ] + = shift @{ $self->{inputs} }; + $self->{pc} += 2; + } else { + $self->{want_input} = m2pos($self, 1, $m1); + $self->{pc} += 2; + return undef; + } + } elsif ($op == 4) { + my $val = m2val($self, 1, $m1); + $self->{pc} += 2; + return $val; + } elsif ($op == 5) { + if (m2val($self, 1, $m1)) { + $self->{pc} = m2val($self, 2, $m2); + } else { + $self->{pc} += 3; + } + } elsif ($op == 6) { + if (!m2val($self, 1, $m1)) { + $self->{pc} = m2val($self, 2, $m2); + } else { + $self->{pc} += 3; + } + } elsif ($op == 7) { + $mem->[ m2pos($self, 3, $m3) ] = + m2val($self, 1, $m1) + < m2val($self, 2, $m2) ? 1 : 0; + $self->{pc} += 4; + } elsif ($op == 8) { + $mem->[ m2pos($self, 3, $m3) ] = + m2val($self, 1, $m1) + == m2val($self, 2, $m2) ? 1 : 0; + $self->{pc} += 4; + } elsif ($op == 9) { + $self->{base} += m2val($self, 1, $m1); + $self->{pc} += 2; + } elsif ($op == 99) { + return undef; + } + } +} + +sub ascii { + my ($self, $text) = @_; + $text .= "\n" if $text !~ /\n\z/; + my @bytes = map { ord } split //, $text; + $self->input(@bytes); + return $self; +} + +package main; + +open my $fh, '<', $ARGV[0] or die; +my @mem; +{ local $/; chomp(@mem = split /,/, <>) }; + +$; = ','; + +my $comp = IntComp->new(\@mem); + +while (my $rv = $comp->run) { + print chr($rv); +} + +while () { + $comp->ascii($_); + + while (my $rv = $comp->run) { + print chr($rv); + } +} diff --git a/2019/50.pl b/2019/50.pl new file mode 100755 index 0000000..d3b8573 --- /dev/null +++ b/2019/50.pl @@ -0,0 +1,5 @@ +#!/usr/bin/perl -w + +use v5.16; + + -- 2.43.0