So, it’s that time of year again when I spend a bit of time tackling some of the Advent Of Code challenges. As a bit of an exercise I’ve decided to write down an explanation of how I tackled Day 1.

Part 1

Each Day’s challenge consists of two parts and the simplified explanation for the first part for Day 1’s challenge is:

Given a list of numbers find two that numbers that add up to 2020. Take those two numbers and multiply them together to get your solution.

Multiplication is trivial, getting the two numbers that add up to 2020 is the part of the challenge that you have to think a little bit about. So let’s look at how I tackled that.

So we need a function that given a list finds the two entries that add up to 2020 - lets call it findTwoEntriesThatSumTo. The first parameter can be the number we want the two list entries to add up to, the rest of the parameters can be the list.

Now we know what our function is going to be called and what parameters it takes, we can write a test:

use Day_01 qw( findTwoEntriesThatSumTo );

my @testExpenses = ( 1721, 979, 366, 299, 675, 1456 );

subtest 'Part 1' => sub {
    cmp_deeply(
        [ findTwoEntriesThatSumTo(2020, @testExpenses ) ],
        bag( 1721, 299 ),
        "Should find the two entries that sum to 2020"
    );
};

We’re comparing against a bag as the order that the two entries are returned doesn’t matter.

Now that we have a failing test we can write the code to make it pass. There’s a lot of different ways to tackle the problem, but the one I ended up with is:

sub findTwoEntriesThatSumTo {
    my ( $value, @list ) = @_;

    while ( my $a = shift @list ) {
        foreach my $b ( @list ) {
            return ( $a, $b ) if $a + $b == $value;
        }
    }

    return;
}

The first line defines the function, and the second extracts the parameters into variables (Perl passes parameters into a function via the special @_ array).

In Perl shift removes the first item from an array and returns it. If the list is empty then it’ll return undef, if the condition in a while loop evaluates to undefined then the while loop is done.

Inside the while loop we have a foreach loop that loops through the entries left in our array.

Inside that foreach loop we’ll return the two values if they add add up to the value we’re looking for, otherwise the foreach loop will move onto the next value in the list.

If the foreach loop completes without finding a suitable value then control is returned to the while loop which takes the next value off the start of the list and runs through the foreach loop again to see if any other number in the list will add up with it to the value we’re looking for. (Note that each time round the while loop the list is getting shorter).

If there isn’t a pair of numbers in the list that add up to 2020 then eventually the list will be empty and the while loop will hand control to the next statement after it, which in this case is a simple return. That return at the end of the function makes sure that we’ll get an undef back from the function if it doesn’t find a suitable answer.

Once the that was written, the bugs fixed and the test passing I put together a simple script that used it to find the answer to the first part of the Day 1 challenge.

Part 2

Part 2’s challenge is almost identical to Part 1 except this time we’re looking for three numbers that add up to 2020. So lets create a new function called findThreeEntriesThatSumTo that takes the same parameters as our function that solves Part 1. As before we’ll create a test so that we know what we’re trying to achieve:

subtest 'Part 2' => sub {
    cmp_deeply(
        [ findThreeEntriesThatSumTo( 2020, @testExpenses ) ],
        bag( 979, 366, 675 ),
        "Should find the three entries that sum to 2020"
    );
};

With a failing test we’re in a position to write our function to solve the problem. There’s a lot of ways to view the new challenge, but there all going to involve looping through our list of numbers trying to find two others that when added to it gives us 2020. Luckily for us we already have a function that given a target value and a list of numbers will try to find two that add up to that target value. So lets use that in a similar while loop to that we used in Part 1:

sub findThreeEntriesThatSumTo {
    my ( $value, @list ) = @_;

    while ( my $a = shift @list ) {
        my ( $b, $c ) = findTwoEntriesThatSumTo( $value - $a, @list );
        return ( $a, $b, $c ) if defined $b;
    }

    return;
}

The while loop functions in exactly the same way as it does in our solution to Part 1, shifting the first entry out of the list on each time round.

Each iteration of the while loop starts by calling the findTwoEntriesThatSumTo function and storing the result in the variables $b and $c. The first parameter passed to findTwoEntriesThatSumTo is the result of subtracting the number we shifted off the start of our list ($a) from our target value ($value), the rest of the parameters we pass are what remains of our list.

If our findTwoEntriesThatSumTo function doesn’t find two values then it returns undef and $b an $c will both be undefined. We can use this as a check on the next line to see if we’ve found our answer or if we need to carry on to the next time round the loop. If $b is defined then it’s found an answer and can return the three values it has found ($a, $b and $c). However, if $b isn’t defined then the while loop will move on and try the next number in our list.

If by some chance it doesn’t find three numbers in the list that add up to our target value then the while loop will finish and the return at the end of the function will return undef to the caller.

Once the function was working I updated my script from Part 1 to also call our new function to solve Part 2.