/ domm

I hack Perl for fun and profit

Follow me on twitter!
Atom Icom ... on Atom!
03.01.2021: Bulk downloading all episodes of a podcast
12.12.2020: Advent of Code Day 12 - sailing to a pause
11.12.2020: Advent of Code Day 11 - slow SeatGoL
10.12.2020: Advent of Code Day 10 - trillion jolts
09.12.2020: Advent of Code Day 9 - while learning

The main takeaway of this day was that it makes a lot of sense to remember what we learned on previous days. Which I realized the hard way, after wasting 25 minutes on playing around with List::Permutor, when in fact this problem was a slightly extended version of day 1.

https://adventofcode.com/2020/day/9

Part 1

This time the test and live data used different sizes for the "preamble", so I get that value from the command line:

perl 09_1.pl 25 < 09.data

Then I read in the input, removing newlines via chomp. The main loop runs check() (see below). If the check fails we remove the first element of the input, if not we exit the loop and print the value in the input after the "preamble".

my $size = shift;
my @in   = map { chomp; $_ } <>;

while (1) {
    check() ? shift @in : last;
}
say $in[$size];

sub check {
    my %lu = map { $_, 1 } @in[ 0 .. $size - 1 ];
    for my $a ( keys %lu ) {
        if ( $lu{ $in[$size] - $a } ) {
            return 1;
        }
    }
    return;
}

Now about the check-function. We're again looking for two values in a list that sum up to a specific value, so we can reuse the trick we learned on day 1. I generate the list of "candidates" via an array slice:

   my %lu = map { $_, 1 } @in[ 0 .. $size - 1 ];

The target value is located after the "preamble", i.e. at $in[$size], so we loop through the candidates and see if the lookup hash contains a value at target - current value. We return true, which will exit the main loop.

Part 2

As Part 2 reuses the result from Part 1, but I didn't want to hard-code it, I just added some more code (and I'll skip the old code here, you can view it on github)

Instead of just printing the result, we store it in $target. I also use a few functions from List::Util. And as my algorithm is destructive on the input, I copy the original data into @in2.

use List::Util qw (min max sum);
my @in2  = @in;
my $target = $in[$size];

while (1) {
    my @try = @in2;
    my @cand;

    while (1) {
        push( @cand, shift @try );
        my $sum = sum(@cand);

        if ( $sum == $target ) {
            say min(@cand) + max(@cand);
            exit;
        }
        last if $sum > $target;
    }
    shift(@in2);
}

In the outer loop we copy the input again, prepare an array to store the candidates, and (at the end, in the last row) remove the first element of the input.

In the inner loop, we take the first element from the input, and push it onto the candidates array. The we calc the sum of the candidates, compare it with the target, and if it matches calculate the final result.

No Spaces

eval(qq{use$"List::Util"min","max","sum"});my$s=shift;my@x=map{chomp;$_}<>;my@y=@x
;$b=sub{my%l=map{$_,1}@x[0..$s-1];for(keys%l){if($l{$x[$s]-$_}){return"1"}}};while
(1){&$b?shift@x:last}my$t=$x[$s];while(1){my@t=@y;my@z;while(1){push(@z,shift@t);
my$r=sum(@z);if($r==$t){say(min(@z)+max(@z));exit}if($r>$t){last}}shift(@y)}

I cheated a little bit with using eval to load List::Util, but still nice enough.

Stats & Links

Comments (via senph)

08.12.2020: Advent of Code Day 8 - running code
07.12.2020: Advent of Code Day 7 - baggy recursion
06.12.2020: Advent of Code Day 6 - simple counting
05.12.2020: Advent of Code Day 5 - hard fail
04.12.2020: Advent of Code Day 4 - validating regex
>>>>>>>>>>
<