From: Jan "Yenya" Kasprzak Date: Fri, 10 Nov 2023 16:48:14 +0000 (+0100) Subject: 2019 day 15 and 17 X-Git-Url: https://www.fi.muni.cz/~kas/git//home/kas/public_html/git/?p=aoc.git;a=commitdiff_plain;h=1c9cac9b0cb348cceafc52139ec9b40ee3390960 2019 day 15 and 17 --- diff --git a/2019/29.pl b/2019/29.pl new file mode 100755 index 0000000..cf8c009 --- /dev/null +++ b/2019/29.pl @@ -0,0 +1,168 @@ +#!/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 /,/, <>); + +$; = ','; + +sub back { my $x = shift; return 1 + (($x-1) ^ 1); } +my %map; +my $c = IntComp->new(\@mem); +$c->{steps} = 0; +$map{10000,10000} = $c; +my @q = ([10_000, 10_000]); +while (my $pos = shift @q) { + my ($x, $y) = @$pos; + my $cmd; + my $orig_comp = $map{$x,$y}; + for ([0, -1], [0, 1], [-1, 0], [1, 0]) { + my $nx = $x + $_->[0]; + my $ny = $y + $_->[1]; + $cmd++; + next if defined $map{$nx,$ny}; + my $comp = IntComp->clone($orig_comp); + my $rv = $comp->run($cmd); + say "moving from $x, $y to $nx, $ny $cmd: $rv"; + if ($rv == 0) { + $map{$nx,$ny} = '#'; + } elsif ($rv == 1) { + $comp->{steps} = 1 + $orig_comp->{steps}; + $map{$nx,$ny} = $comp; + push @q, [ $nx, $ny ]; + } elsif ($rv == 2) { + say "found at $nx, $ny after ", 1 + $orig_comp->{steps}, + " steps"; + exit 0; + } + } + say "map has ", scalar keys %map, " fields"; +} diff --git a/2019/30.pl b/2019/30.pl new file mode 100755 index 0000000..c0a19ef --- /dev/null +++ b/2019/30.pl @@ -0,0 +1,198 @@ +#!/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 /,/, <>); + +$; = ','; + +sub back { my $x = shift; return 1 + (($x-1) ^ 1); } +my %map; +my $c = IntComp->new(\@mem); +$c->{steps} = 0; +$map{10000,10000} = $c; +my @q = ([10_000, 10_000]); +MAINLOOP: +while (my $pos = shift @q) { + my ($x, $y) = @$pos; + my $cmd; + my $orig_comp = $map{$x,$y}; + for ([0, -1], [0, 1], [-1, 0], [1, 0]) { + my $nx = $x + $_->[0]; + my $ny = $y + $_->[1]; + $cmd++; + next if defined $map{$nx,$ny}; + my $comp = IntComp->clone($orig_comp); + my $rv = $comp->run($cmd); + # say "moving from $x, $y to $nx, $ny $cmd: $rv"; + if ($rv == 0) { + $map{$nx,$ny} = '#'; + next; + } elsif ($rv == 1) { + $comp->{steps} = 1 + $orig_comp->{steps}; + $map{$nx,$ny} = $comp; + push @q, [ $nx, $ny ]; + } elsif ($rv == 2) { + say "found at $nx, $ny after ", 1 + $orig_comp->{steps}, + " steps"; + @q = [ $nx, $ny ]; + %map = (); + $map{$nx,$ny} = $comp; + $comp->{steps} = 0; + last MAINLOOP; + } + } +} + +while (my $pos = shift @q) { + my ($x, $y) = @$pos; + my $cmd; + my $orig_comp = $map{$x,$y}; + say "at $x, $y steps $orig_comp->{steps}"; + for ([0, -1], [0, 1], [-1, 0], [1, 0]) { + my $nx = $x + $_->[0]; + my $ny = $y + $_->[1]; + $cmd++; + next if defined $map{$nx,$ny}; + my $comp = IntComp->clone($orig_comp); + my $rv = $comp->run($cmd); + # say "moving from $x, $y to $nx, $ny $cmd: $rv"; + if ($rv == 0) { + $map{$nx,$ny} = '#'; + next; + } + $comp->{steps} = 1 + $orig_comp->{steps}; + $map{$nx,$ny} = $comp; + push @q, [ $nx, $ny ]; + say "to explore $nx, $ny steps $comp->{steps}"; + } +} + diff --git a/2019/33.pl b/2019/33.pl new file mode 100755 index 0000000..5a33ccc --- /dev/null +++ b/2019/33.pl @@ -0,0 +1,168 @@ +#!/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 $comp = IntComp->new(\@mem); + +my ($x, $y) = (0, 0); +my @prev; +my @cur; +my $sum; +my $l = ''; +while(my $rv = $comp->run()) { + my $c = chr($rv); + $cur[$x] = $c; + if ($x > 1 && $y > 1 && $c eq '#') { + if ($cur[$x-1] eq '#' && $cur[$x-2] eq '#' && $prev[$x-1] eq '#') { + $sum += ($x-1) * $y; + # $l .= ' '.( $x-1). ','. $y; + $c = '{'; + } + } + if ($rv == 10) { + $y++; $x = 0; + @prev = @cur; + print $l; + $l = ''; + @cur = (); + } else { + $x++; + } + print $c; +} + +say $sum; + +# 344 too low diff --git a/2019/34.pl b/2019/34.pl new file mode 100755 index 0000000..f4a4edf --- /dev/null +++ b/2019/34.pl @@ -0,0 +1,153 @@ +#!/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); + } +}