Advent of Code 2020 Day 1 – Our Solutions

James HeslipAPLLeave a Comment

The holiday season is among us, and that can only mean one thing...Advent of Code is here! Optima is hosting a little internal competition this year to see who can get the most stars. This has genius from all corners of the office, and I thought it would be nice to show off the different thought processes from some of the different departments.

Day 1 deals with a set of 200 numbers and requires the developer to find 2 (or 3) numbers which sum to 2020.


Jonners

Part 1: The first part of this problem is to find the two entries that sum to 2020. The answer will be what you get if you multiply them together.


{×/⍵/⍨⍵∊2020-⍵} d1   ⍝ Where d1 is an integer vector of the day 1 input

The process for this part was quite simple; we subtract each number from 2020, and then check where the answer is present in the list. Each member of the pair will return a 1 at the index of its counterpart, then we reduce the input using the Boolean, and multiply the result.

Part 2: Find the three entries that sum to 2020; what do you get if you multiply them together?


2020{×/⍵/⍨⍵∊⍺-∘.+⍨⍵/⍨∊⍵≤⍺-+/2↑⍵}d1   ⍝ Where d1 is a integer vector of the day 1 input in asc order.

Now we’re looking for the sum of three numbers, but we can use much the same process; instead of just subtracting each number from 2020, now we subtract the sum of each pair of numbers. The correct pair will return a 1 at the index of the third component, so we reduce the input using the Boolean, and multiply the result. I included a sort and minor filter to reduce the number of pairs that need to be checked, but this isn’t strictly necessary. I also moved the target to the left argument for some reason.


Roy

I decided to use a nested ‘while loop’ to add every value to every other value until the result was found. I quite enjoyed doing a bit of VBA again, so decided to continue with the whole thing, or at least until the requirements defeat me.

A couple of them have been a little challenging. But let’s see where it goes.

Below is the code I used.



Dim FNum, INum, UNum As Integer
Dim Val1, Val2 As Integer
FNum = 1
INum = 200
UNum = 1
' Need to find 2 values in cells that sum 2020
Cells(5, 5).Value = ""
Cells(5, 6).Value = ""
Cells(6, 5).Value = ""

Do While UNum < INum
    Val1 = Cells(UNum, 1).Value
    Do While FNum < INum
        If FNum = UNum Then
            FNum = FNum + 1
        Else
            Val2 = Cells(FNum, 1).Value
            FNum = FNum + 1
            If Val2 + Val1 = 2020 Then ‘Found it!
                Cells(5, 5).Value = Val1
                Cells(5, 6).Value = Val2
                Cells(6, 5).Value = "Multiplied : " + (CStr(Val1 * Val2))
                Exit Sub
            End If
        End If
    Loop
    UNum = UNum + 1
    FNum = 1
Loop


Mike

Being a non-coder my approach to the first problem was probably a great example of what not to do!

As the numbers had to add up to 2020, I figured that one of the numbers was probably going to be 3 digits. Looking down the list there were not very many of these. In fact, only seven: 798, 664, 558, 195, 24, 708, and 301.

So, from those choices the only answers (presuming it is one with 3 digits) could be: 1222, 1356, 1462, 1825, 1996, 1312, or 1719.

The next high-tech tool I used was the find function in Notepad. Simply using this tell me that the only number from those to appear in the original list is 1312.

Therefor the answer must be 708 and 1312 (708 + 1312 = 2020). This brute force method was effective if not particularly elegant!

For part 2 I used an even more sophisticated tool. I guessed. The first three of the 3 digit numbers from my original list were 798, 664, and 558 - these are the 3 that add up to 2020. Multiplying them together gives us the answer: 295,668,576.


James

I decided to solve the problem using both APL and Python.

Part 1 (APL):


q1_1←2020∘{×/⍵[⍸⍵∊⍺-⍵]}

My solution for part one is fairly straight forward.

The only issues I had related not to the problem itself, but to the use of ]LINK, an APL source code management utility. This Advent of Code was a fresh opportunity for me, and I saw it as a good time to try LINK for the first time.

I did have a bit of a battle getting used to it as I would often create a variable in the session and forget to run ]LINK.add to track it. I also encountered an issue early on as this solution uses composition; I join 2020 as a left argument to my function when assigning it to a name. LINK doesn’t handle this, but Adám from Dyalog helped me find a way around it:


∇ q1_1←q1_1
  q1_1←2020∘{×/⍵[⍸⍵∊⍺-⍵]}
∇

Part 2 (APL): The second phase of this question was more fun. I started with a brutally memory intensive one-liner:

2020 ∘ ∇{×/⍵[∪⊃¨⍸⍺=⍵∘.+,∘.+⍨⍵⌿⍨⍵≤⍺-+/2↑⍵]} 
∇ ⊂∘⍋⌷⊢

The double use of outer product worked, but it wasn’t doing it for me. I decided to refactor for efficiency:

∇ r←q1_2 input;goal;sortedInput;sumOfTwo;indLargestThird;largestThirds;totals;filtered

 goal←2020                                                  ⍝ Set target
 sortedInput←(⊂∘⍋⌷⊢)input                                   ⍝ Sort input
 filtered←goal{⍵⌿⍨⍵≤⍺-+/2↑⍵}sortedInput                     ⍝ Remove any numbers which are less than the sum of the first two
 sumOfTwo←∘.+⍨filtered                                      ⍝ Find the sum of remaining numbers
 indLargestThird←(⌈/⍸)⍤1⊢(goal-⊃sortedInput)>sumOfTwo       ⍝ Find the index of the largest possible third number
 largestThirds←filtered[indLargestThird]                    ⍝ Lookup those numbers
 totals←largestThirds+⍤1⊢sumOfTwo                           ⍝ and sum with the previous two
 r←goal{×/⍵,⍺-+/⍵}sortedInput[∊⍸totals∊goal]                ⍝ Find the index where this sums is the goal, and return the product of it's three elements
∇


Part 1 (Python):


def q1_1(target, data):
    # Find the two entries that sum to 2020; what do you get if you multiply them together?

        # Comparing every number
        for num1 in data:

            # Generate the necessary second number to reach the target
            # and if it exists, return the product of the two
            num2 = target - num1
            if num2 in data:
                return num1 * num2

    return -1   # return not found

Part 2 (Python):


def q1_2(target, data):
    # what is the product of the three entries that sum to 2020?

        # Comparing every number
        for num1 in data:
       
            # With every number
            for num2 in data:

                # Generate the necessary third number to reach the target
                # and if it exists, return the product of the three numbers
                num3 = target - num1 - num2
                if num3 in data:
                    return num1 * num2 * num3

    return -1   # return not found

Side note: I realise none of my solutions factor in *distinct* number solutions. I wonder if the question was asking for non-duplicate values? In my case, all the numbers were unique, but I wonder if this is always the case...


Sam

Part 1 solution:


{×/⍵[∪∊⍸2020∊⍨∘.+⍨⍵]}

Part 2 solution:

{×/⍵[∪∊⍸2020∊⍨(∘.+⍣2)⍨⍵]}

Seeing how I amended the solution for part 1 to solve part 2, I could refactor my code to include the use of the power operator but instead of using 2 explicitly I could change it to alpha and pass the appropriate argument to solve either part.

This how I refactored the solution for Day 1 to work in both in scenarios, being the amount of times to apply the ∘.+ operation:


{×/⍵[∪∊⍸2020∊⍨(∘.+⍣⍺)⍨⍵]}

Closing words from James

No doubt the problems will get more difficult as the days progress. I'm keeping an eye on Jonners, the newbie, as his solution is still more efficient than my refactored attempt... Beginners luck, methinks. I'm also particularly fond of how Sam's solution can be extended beyond three numbers.

For our next post we plan to look at Day 5. Happy coding!

About the Author

A picture of James Heslip the author of this blog

James Heslip

APL Team Leader


James is an APL Programmer with a keen interest in mathematics. His love for computing was almost an accident. From a young age he always enjoyed using them- playing video games and such- but it was never considered that anything more would come from it. James originally had plans to pursue a career in finance. More about James.


More from James



Other Posts