These are my solutions for this year's contest.
If you want to copy these files, use the GitHub link.
All files covered by the UNLICENSE.
[ AoC problem link ] [ Discussion ].
#! /usr/bin/env perl
use Modern::Perl '2015';
# useful modules
use List::Util qw/sum/;
use Data::Dumper;
use POSIX qw/floor/;
#### INIT - load input data from file into array
my $testing = 0;
my @input;
my $file = $testing ? 'test.txt' : 'input.txt';
open( my $fh, '<', "$file" );
while (<$fh>) { chomp; s/\r//gm; push @input, $_; }
### CODE
my $sum;
my $sum2;
while (@input) {
my $mass = shift @input;
my $fuel = floor( $mass / 3 ) - 2;
say "$mass $fuel" if $testing;
$sum += $fuel;
$sum2 += $fuel;
while ( $fuel >= 6 ) {
$fuel = floor( $fuel / 3 ) - 2;
say $fuel if $testing;
$sum2 += $fuel;
}
}
say "Part 1: $sum";
say "Part 2: $sum2";
25 lines [ Plain text ] [ ^Top ]
[ AoC problem link ] [ Discussion ].
#! /usr/bin/env perl
use Modern::Perl '2015';
# useful modules
use List::Util qw/sum all/;
use Data::Dumper;
#### INIT - load input data from file into array
my $testing = 0;
use Test::Simple tests => 6;
my @input;
my $file = 'input.txt';
open( my $fh, '<', "$file" );
while (<$fh>) { chomp; s/\r//gm; push @input, $_; }
close $fh;
### CODE
my @state;
sub dump_state;
sub run;
my $halt = 99;
my %opcodes = (
1 => \&add,
2 => \&mult,
);
my @tests;
while () {
chomp;
push @tests, $_;
}
foreach my $line (@tests) {
# say $line;
my ( $input, $output ) = split / /, $line;
# say "$input $output";
@state = split( ',', $input );
run();
ok( join( ',', @state ) eq $output );
}
my @initial = split( /,/, $input[0] );
@state = @initial;
my $cur;
my ( $part1, $part2 );
my $target = 19690720;
LOOPS: foreach my $noun ( 0 .. 99 ) {
foreach my $verb ( 0 .. 99 ) {
@state = @initial;
$state[1] = $noun;
$state[2] = $verb;
run();
if ( $noun == 12 and $verb == 2 ) {
$part1 = $state[0];
say "Part 1: ", $part1;
}
if ( $state[0] == $target ) {
$part2 = 100 * $noun + $verb;
say "Part 2: ", $part2;
last LOOPS;
}
}
}
ok( $part1 == 5434663 );
ok( $part2 == 4559 );
### Subs
sub add {
my ( $i, $j ) = @_;
return $state[$i] + $state[$j];
}
sub mult {
my ( $i, $j ) = @_;
return $state[$i] * $state[$j];
}
sub dump_state {
say join( ',', @state );
}
sub run {
my $cur = 0;
while ( $state[$cur] != $halt ) {
my ( $op, $in1, $in2, $out ) =
@state[ $cur, $cur + 1, $cur + 2, $cur + 3 ];
last unless all { defined $_ } ( $in1, $in2, $out );
my $res;
die "unknown op: $state[$cur]" unless defined $opcodes{$op};
$res = $opcodes{$op}->( $in1, $in2 );
$state[$out] = $res;
$cur += 4;
}
}
__DATA__
1,0,0,0,99 2,0,0,0,99
2,3,0,3,99 2,3,0,6,99
2,4,4,5,99,0 2,4,4,5,99,9801
1,1,1,4,99,5,6,0,99 30,1,1,4,2,5,6,0,99
84 lines [ Plain text ] [ ^Top ]
[ AoC problem link ] [ Discussion ].
#! /usr/bin/env perl
use Modern::Perl '2015';
# useful modules
use List::Util qw/sum/;
use Test::Simple tests => 2;
#### INIT - load input data from file into array
my $testing = 0;
my @input;
my $file = $testing ? 'test.txt' : 'input.txt';
open( my $fh, '<', "$file" );
while (<$fh>) { chomp; s/\r//gm; push @input, $_; }
### CODE
my $grid;
sub manhattan_distance;
my %set_line = (
U => \&up,
D => \&down,
L => \&left,
R => \&right,
);
my $id = 1;
foreach my $line (@input) {
say "loading a line....";
my $cur = [ 0, 0, 0 ];
push @{ $grid->{0}->{0} }, { id => $id, $id=>0 };
my @list = split( /,/, $line );
my $prev = '';
while (@list) {
my $move = shift @list;
if ( $move =~ m/(U|D|L|R)(\d+)/ ) {
$cur = $set_line{$1}->( $id, $cur, $2 );
}
else {
die "can't parse move: $move";
}
}
$id++;
}
say "finding crossings...";
my @distances;
my @signals;
for my $x ( keys %$grid ) {
for my $y ( keys %{ $grid->{$x} } ) {
if ( ref $grid->{$x}->{$y} eq 'ARRAY'
and scalar @{ $grid->{$x}->{$y} } > 1 )
{
my %ids;
my $signal = 0;
foreach my $el ( @{ $grid->{$x}->{$y} } ) {
$ids{ $el->{id} }++;
$signal += sum( map { $el->{$_} ? $el->{$_} : 0 } ( 1, 2 ) );
}
if ( scalar keys %ids > 1 and ( $x != 0 and $y != 0 ) ) {
# part 1
push @distances, sum( map { abs($_) } ( $x, $y ) );
# part 2
push @signals, $signal;
}
}
}
}
my $part1 = ( sort { $a <=> $b } @distances )[0];
my $part2 = ( sort { $a <=> $b } @signals )[0];
ok( $part1 == 1626 );
ok( $part2 == 27330 );
say "Part 1: $part1";
say "Part 2: $part2";
### Subs
sub up {
my ( $id, $start, $steps ) = @_;
my ( $x_0, $y_0, $d_0 ) = @$start;
for ( my $y = 0 ; $y <= $steps ; $y++ ) {
push @{ $grid->{$x_0}->{ $y_0 + $y } }, { id => $id, $id => $d_0 + $y };
}
return [ $x_0, $y_0 + $steps, $d_0 + $steps ];
}
sub down {
my ( $id, $start, $steps ) = @_;
my ( $x_0, $y_0, $d_0 ) = @$start;
for ( my $y = 0 ; $y >= -$steps ; $y-- ) {
push @{ $grid->{$x_0}->{ $y_0 + $y } },
{ id => $id, $id => $d_0 + abs($y) };
}
return [ $x_0, $y_0 - $steps, $d_0 + $steps ];
}
sub left {
my ( $id, $start, $steps ) = @_;
my ( $x_0, $y_0, $d_0 ) = @$start;
for ( my $x = 0 ; $x >= -$steps ; $x-- ) {
push @{ $grid->{ $x_0 + $x }->{$y_0} },
{ id => $id, $id => $d_0 + abs($x) };
}
return [ $x_0 - $steps, $y_0, $d_0 + $steps ];
}
sub right {
my ( $id, $start, $steps ) = @_;
my ( $x_0, $y_0, $d_0 ) = @$start;
for ( my $x = 0 ; $x <= $steps ; $x++ ) {
push @{ $grid->{ $x_0 + $x }->{$y_0} }, { id => $id, $id => $d_0 + $x };
}
return [ $start->[0] + $steps, $start->[1], $d_0 + $steps ];
}
97 lines [ Plain text ] [ ^Top ]
[ AoC problem link ] [ Discussion ].
#! /usr/bin/env perl
use Modern::Perl '2015';
# useful modules
use List::Util qw/sum all any none/;
use Test::Simple tests => 2;
my $testing = 0;
### CODE
# problem input
my @limits = ( 245182, 790572 );
if ($testing) { $limits[1] = 300000 }
my $part1;
my $part2;
for my $N ( $limits[0] .. $limits[1] ) {
my @digits = split( //, $N );
# increasing?
my $inc = all { $digits[$_] <= $digits[ $_ + 1 ] } ( 0 .. 4 );
# duplicated digits?
my $dbl = any { $digits[$_] == $digits[ $_ + 1 ] } ( 0 .. 4 );
next unless ( $inc && $dbl );
$part1++;
my %hist;
for my $d (@digits) { $hist{$d}++ }
# discard any solutions where there are only groups of 3 or more,
# and no separate doubles
next if ( any { $_ > 2 } values %hist and none { $_ == 2 } values %hist );
$part2++;
}
ok( $part1 == 1099 );
ok( $part2 == 710 );
say "Part 1: $part1";
say "Part 2: $part2";
27 lines [ Plain text ] [ ^Top ]
[ AoC problem link ] [ Discussion ].
#! /usr/bin/env perl
use Modern::Perl '2015';
# useful modules
use List::Util qw/sum/;
use Data::Dumper;
use Test::Simple tests => 1;
#### INIT - load input data from file into array
my $testing = 0;
my $debug = 0;
my @file_contents;
my $file = $testing ? 'test.txt' : 'input.txt';
open( my $fh, '<', "$file" );
while (<$fh>) { chomp; s/\r//gm; push @file_contents, $_; }
### CODE
my $halt = 99;
my $part2 = shift || 0;
my $initial_val = $part2 ? 5 : 1;
my $program = [ split( ',', $file_contents[0] ) ];
#dump_state($program);
my ( $out_state, $out ) = run_vm( $program, [$initial_val] );
my $ans = $out->[-1];
if ($part2) {
ok( $ans == 7616021 );
}
else {
ok( $ans == 15259545 );
}
say $part2? "Part 2: " : "Part 1: ", $ans;
### SUBS
sub run_vm {
my ( $state, $in_val ) = @_;
# my @state = @{$program};
my @input = @{$in_val};
my $ptr = 0;
my $out_val;
while ( $state->[$ptr] != $halt ) {
my ( $op, $a1, $a2, $a3 ) =
@$state[ $ptr, $ptr + 1, $ptr + 2, $ptr + 3 ];
say join( ' ', $ptr, $op, $a1, $a2, $a3 ) if $debug;
my $mask;
if ( length $op > 2 )
{ # assume values in this position are either 2 digits or more
my @instr = split( //, $op );
my @tail;
for ( 1, 2 ) {
unshift @tail, pop @instr;
}
$op = join( '', @tail ) + 0;
while ( scalar @instr < 3 ) {
unshift @instr, 0;
}
$mask = [ reverse @instr ];
}
else {
$mask = [ 0, 0, 0 ];
}
my %ops = (
1 => sub { $state->[ $_[2] ] = $_[0] + $_[1]; $ptr += 4 },
2 => sub { $state->[ $_[2] ] = $_[0] * $_[1]; $ptr += 4 },
4 => sub { push @{$out_val}, $_[0]; $ptr += 2 },
5 => sub {
if ( $_[0] != 0 ) { $ptr = $_[1]; }
else { $ptr += 3; }
},
6 => sub {
if ( $_[0] == 0 ) { $ptr = $_[1]; }
else { $ptr += 3; }
},
7 => sub {
if ( $_[0] < $_[1] ) { $state->[ $_[2] ] = 1; }
else { $state->[ $_[2] ] = 0; }
$ptr += 4;
},
8 => sub {
if ( $_[0] == $_[1] ) {
$state->[ $_[2] ] = 1;
}
else {
$state->[ $_[2] ] = 0;
}
$ptr += 4;
},
);
if ( $op == 3 ) {
$state->[$a1] = shift @$in_val;
$ptr += 2;
}
else {
$a1 = $mask->[0] ? $a1 : $state->[$a1];
$a2 = $mask->[1] ? $a2 : $state->[$a2];
$ops{$op}->( $a1, $a2, $a3 );
}
}
return ( $state, $out_val );
}
sub dump_state { # shows a pretty-printed grid of the current state
my @show = split( ',', $_[0] );
print ' ';
for my $i ( 0 .. 9 ) { printf( "___%d ", $i ) }
print "\n";
my $full_rows = int( scalar @show / 10 );
my $r;
for $r ( 0 .. $full_rows - 1 ) {
printf "%2d|", $r;
for my $c ( 0 .. 9 ) {
my $el = shift @show;
printf "%4d ", $el;
}
print "\n";
}
printf "%2d|", $full_rows;
while (@show) {
my $el = shift @show;
printf "%4d ", $el;
}
print "\n";
}
111 lines [ Plain text ] [ ^Top ]
[ AoC problem link ] [ Discussion ].
#! /usr/bin/env perl
use Modern::Perl '2015';
# useful modules
use List::Util qw/sum/;
use Data::Dumper;
use Test::Simple tests => 2;
#### INIT - load input data from file into array
my $testing = 0;
my @input;
my $file = $testing ? 'test.txt' : 'input.txt';
open( my $fh, '<', "$file" );
while (<$fh>) { chomp; s/\r//gm; push @input, $_; }
### CODE
my %orbits;
while (@input) {
my ( $p, $s ) = split( /\)/, shift @input );
$orbits{$s} = $p;
}
my $count = 0;
foreach my $s ( keys %orbits ) {
count_orbits($s);
}
ok( $count == 314702 );
say "Part 1: $count";
# credit: rtbrsp
# https://www.reddit.com/r/adventofcode/comments/e6tyva/2019_day_6_solutions/f9tb2gi/
my %path;
my $S;
my $Y;
my $s;
for ( $s = 'SAN' ; $s ne 'COM' ; $s = $orbits{$s} ) {
$path{ $orbits{$s} } = $S++;
}
for ( $s = 'YOU' ; !$path{ $orbits{$s} } ; $s = $orbits{$s} ) {
$Y++;
}
$Y += $path{ $orbits{$s} };
ok( $Y == 439 );
say "Part 2: $Y";
# credit: /u/domm_plix
# https://www.reddit.com/r/adventofcode/comments/e6tyva/2019_day_6_solutions/f9tr612/
sub count_orbits {
no warnings 'recursion';
my ($in) = @_;
return unless exists $orbits{$in};
$count++;
count_orbits( $orbits{$in} );
}
40 lines [ Plain text ] [ ^Top ]
[ AoC problem link ] [ Discussion ].
#! /usr/bin/env perl
use Modern::Perl '2015';
# useful modules
use List::Util qw/sum/;
use Data::Dumper;
use Test::Simple tests=>1;
#### INIT - load input data from file into array
my $testing = 0;
my $debug = 0;
my @file_contents;
my $file = $testing ? 'test.txt' : 'input.txt';
open( my $fh, '<', "$file" );
while (<$fh>) { chomp; s/\r//gm; push @file_contents, $_; }
### CODE
# generate list of starting phase settings
my @program = split(',',$file_contents[0]);
my @list_of_phases;
my @range= (0..4);
for my $a (@range) {
for my $b (@range) {
for my $c (@range) {
for my $d (@range) {
for my $e (@range) {
my %seen = map {$_ => 1} ($a,$b,$c,$d,$e);
next unless scalar %seen == 5;
push @list_of_phases,[$a,$b,$c,$d,$e];
}
}
}
}
}
my $ptr;
my $halt = 99;
my $max = {val=>0, phase => '' };
foreach my $phase(@list_of_phases) {
my @inputs= (0);
for my $register (0..4) {
my $input = $inputs[-1];
my $p = $phase->[$register];
my ( $out_state, $out_val) = run_vm(\@program, [$p,$input]);
say "$register ", join(',',@$out_val) if $debug;
push @inputs, $out_val->[-1];
}
if ($inputs[-1] > $max->{val}) {
$max->{val} = $inputs[-1];
$max->{phase} =join ('', @$phase);
}
# say "Phase: ",join ('', @$phase), " gives $inputs[-1]";
}
ok( $max->{val} == 116680 );
say "Part 1: $max->{val}";
### Subs
sub run_vm {
my ( $state, $in_val ) = @_;
# my @state = @{$program};
my @input = @{$in_val};
my $ptr = 0;
my $out_val;
while ( $state->[$ptr] != $halt ) {
my ( $op, $a1, $a2, $a3 ) =
@$state[ $ptr, $ptr + 1, $ptr + 2, $ptr + 3 ];
# say join( ' ', $ptr, $op, $a1, $a2, $a3 ) if $debug;
my $mask;
if ( length $op > 2 )
{ # assume values in this position are either 2 digits or more
my @instr = split( //, $op );
my @tail;
for ( 1, 2 ) {
unshift @tail, pop @instr;
}
$op = join( '', @tail ) + 0;
while ( scalar @instr < 3 ) {
unshift @instr, 0;
}
$mask = [ reverse @instr ];
}
else {
$mask = [ 0, 0, 0 ];
}
my %ops = (
1 => sub { $state->[ $_[2] ] = $_[0] + $_[1]; $ptr += 4 },
2 => sub { $state->[ $_[2] ] = $_[0] * $_[1]; $ptr += 4 },
4 => sub { push @{$out_val}, $_[0]; $ptr += 2 },
5 => sub {
if ( $_[0] != 0 ) { $ptr = $_[1]; }
else { $ptr += 3; }
},
6 => sub {
if ( $_[0] == 0 ) { $ptr = $_[1]; }
else { $ptr += 3; }
},
7 => sub {
if ( $_[0] < $_[1] ) { $state->[ $_[2] ] = 1; }
else { $state->[ $_[2] ] = 0; }
$ptr += 4;
},
8 => sub {
if ( $_[0] == $_[1] ) {
$state->[ $_[2] ] = 1;
}
else {
$state->[ $_[2] ] = 0;
}
$ptr += 4;
},
);
if ( $op == 3 ) {
$state->[$a1] = shift @$in_val;
$ptr += 2;
}
else {
$a1 = $mask->[0] ? $a1 : $state->[$a1];
$a2 = $mask->[1] ? $a2 : $state->[$a2];
$ops{$op}->( $a1, $a2, $a3 );
}
}
return ( $state, $out_val );
}
sub dump_state { # shows a pretty-printed grid of the current state
my @show = split( ',', $_[0] );
print ' ';
for my $i ( 0 .. 9 ) { printf( "___%d ", $i ) }
print "\n";
my $full_rows = int( scalar @show / 10 );
my $r;
for $r ( 0 .. $full_rows - 1 ) {
printf "%2d|", $r;
for my $c ( 0 .. 9 ) {
my $el = shift @show;
printf "%4d ", $el;
}
print "\n";
}
printf "%2d|", $full_rows;
while (@show) {
my $el = shift @show;
printf "%4d ", $el;
}
print "\n";
}
132 lines [ Plain text ] [ ^Top ]
#! /usr/bin/env perl
use Modern::Perl '2015';
# useful modules
use List::Util qw/sum/;
use Data::Dumper;
use Test::Simple tests => 1;
#### INIT - load input data from file into array
my $testing = 0;
my $debug = 0;
my @file_contents;
my $file = $testing ? 'test.txt' : 'input.txt';
open( my $fh, '<', "$file" );
while (<$fh>) { chomp; s/\r//gm; push @file_contents, $_; }
### CODE
# generate list of starting phase settings
my @program = split( ',', $file_contents[0] );
my @list_of_phases;
my @range = ( 5 .. 9 );
for my $a (@range) {
for my $b (@range) {
for my $c (@range) {
for my $d (@range) {
for my $e (@range) {
my %seen = map { $_ => 1 } ( $a, $b, $c, $d, $e );
next unless scalar %seen == 5;
push @list_of_phases, [ $a, $b, $c, $d, $e ];
}
}
}
}
}
my $halt = 99;
my $max = { val => 0, phase => '' };
foreach my $phases (@list_of_phases) {
my $amp_states;
for ( 0 .. 4 ) { push @$amp_states, { state => \@program, ptr => 0 } }
my $loop_cnt = 0;
my $amp = 0;
my $prev = [0];
my $ptr;
my $state;
my @last_amp_res;
do {
for my $amp ( 0 .. 4 ) {
# only add the current phase in the very first pass
my $in_val =
$loop_cnt == 0 ? [ $phases->[$amp], $prev->[0] ] : [ $prev->[0] ];
( $prev, $ptr, $state ) = run_vm(
$in_val,
$amp_states->[$amp]->{ptr},
$amp_states->[$amp]->{state}
);
$amp_states->[$amp]->{ptr} = $ptr;
$amp_states->[$amp]->{state} = $state;
push @last_amp_res, $prev->[0] if $amp == 4 and defined $prev->[0];
}
$loop_cnt++;
} while ( scalar @$prev > 0 );
if ( $last_amp_res[-1] > $max->{val} ) {
$max = {
val => $last_amp_res[-1],
phase => join '',
@$phases
};
}
}
ok( $max->{val} == 89603079 );
say "Part 2: ", $max->{val};
### Subs
sub run_vm {
my ( $in_val, $start_ptr, $state ) = @_;
my @input = @{$in_val};
my $ptr = $start_ptr;
my $out_val = [];
LOOP: while ( $state->[$ptr] != $halt ) {
my ( $op, $a1, $a2, $a3 ) =
@$state[ $ptr, $ptr + 1, $ptr + 2, $ptr + 3 ];
my $mask;
if ( length $op > 2 )
{ # assume values in this position are either 2 digits or more
my @instr = split( //, $op );
my @tail;
for ( 1, 2 ) {
unshift @tail, pop @instr;
}
$op = join( '', @tail ) + 0;
while ( scalar @instr < 3 ) {
unshift @instr, 0;
}
$mask = [ reverse @instr ];
}
else {
$mask = [ 0, 0, 0 ];
}
my %ops = (
1 => sub { $state->[ $_[2] ] = $_[0] + $_[1]; $ptr += 4 },
2 => sub { $state->[ $_[2] ] = $_[0] * $_[1]; $ptr += 4 },
4 => sub { push @{$out_val}, $_[0]; $ptr += 2 },
5 => sub {
if ( $_[0] != 0 ) { $ptr = $_[1]; }
else { $ptr += 3; }
},
6 => sub {
if ( $_[0] == 0 ) { $ptr = $_[1]; }
else { $ptr += 3; }
},
7 => sub {
if ( $_[0] < $_[1] ) { $state->[ $_[2] ] = 1; }
else { $state->[ $_[2] ] = 0; }
$ptr += 4;
},
8 => sub {
if ( $_[0] == $_[1] ) {
$state->[ $_[2] ] = 1;
}
else {
$state->[ $_[2] ] = 0;
}
$ptr += 4;
},
);
dump_state($state) if $debug;
if ( $op == 3 ) {
my $in = shift @$in_val;
if ( !defined $in ) {
last LOOP;
}
$state->[$a1] = $in;
$ptr += 2;
}
else {
$a1 = $mask->[0] ? $a1 : $state->[$a1];
$a2 = $mask->[1] ? $a2 : $state->[$a2];
$ops{$op}->( $a1, $a2, $a3 );
}
}
return ( $out_val, $ptr, $state );
}
sub dump_state { # shows a pretty-printed grid of the current state
my ($in) = @_;
my @show = @{$in};
print ' ';
for my $i ( 0 .. 9 ) { printf( "___%d ", $i ) }
print "\n";
my $full_rows = int( scalar @show / 10 );
my $r;
for $r ( 0 .. $full_rows - 1 ) {
printf "%2d|", $r;
for my $c ( 0 .. 9 ) {
my $el = shift @show;
printf "%4d ", $el;
}
print "\n";
}
printf "%2d|", $full_rows;
while (@show) {
my $el = shift @show;
printf "%4d ", $el;
}
print "\n";
}
155 lines [ Plain text ] [ ^Top ]
Generated on Sat Dec 7 19:19:38 2019 UTC.