Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. People use them as a speed contest, interview prep, company training, university coursework, practice problems, or to challenge each other.

So, a friend of mine recently introduced me to the Advent of Code challenge. It seemed pretty cool, and I thought - why not? Besides, it’s been quite a while since I practiced some problem solving with code! And of course, it also helps that the organizers themselves have a whimsical sense of humour.

So, here goes a record of my attempts at solving our little daily puzzles!

Day 1

Report Repair

We begin with a little story about Santa taking a break before Christmas (gotta clear those annual leave days with a little downtime!), and it appears that before he can leave the Elves need some accounting help. The problem is simple enough: they need you to find the two entries that sum to 2020 and then multiply those two numbers together.

Part 1

Simple enough - we can approach this using a quick and dirty brute force method: calculate the sum of every possible pair, and the moment we hit our sum, we spit out our answers.

import pandas as pd

df1 = pd.read_csv("input.txt", header=None)
arr=df1.values

The main function itself is pretty simple, just two nested for loops:

def getPairs(arr, sum): 
    n = len(arr)

    # Cycle through all pairs and check sum 
    for i in range(0, n): 
        for j in range(i + 1, n): 
            if arr[i] + arr[j] == sum: 
                ans1=arr[i]
                ans2=arr[j]
                print(arr[i],arr[j])

    return ans1,ans2

ans1,ans2=getPairs(arr,2020)
print(ans1*ans2)

[1124] [896]
[1007104]

And there’s our answer! Ans: 1007104

Part 2

The Elves in accounting are thankful for your help; one of them even offers you a starfish coin they had left over from a past vacation. They offer you a second one if you can find three numbers in your expense report that meet the same criteria.

Here, we find ourselves in a little bit of a rut. (Well, technically not really, since we don’t have any constraints on our time complexity or space complexity. But I mean, we’re trying to do things somewhat optimized here)

It turns out that our little brute force method from before wouldn’t be quite as efficient in finding a triplet. Blindly running through every single combination for a triplet with three nested for loops is a \(O(n^3)\) solution - still alright for our little 200 element sized input, but not great if the Elves suddenly unearthed 5 more piles of accounting tables.

So, a little bit of thinking later (and some googling, not gonna lie), I chanced upon the Two Pointer Technique. The concept is simple: Given a sorted array A (sorted in ascending order), having N integers, find if there exists any pair of elements (A[i], A[j]) such that their sum is equal to X. This is a lot smarter, because by finding smart pairs (i.e. comparing the sum we’re getting to what we want), we can reduce the time complexity of our solution down to \(O(n^2)+O(n \log n)\approx O(n^2)\). Yay for optimization!

The algorithm is then pretty simple:

1. First, we hold out one of the triplets, finding our desired sum of the pair.
2. We use the two pointer technique to efficiently determine whether the sum can be reached.
3. If not, skip and move on to hold out the next element of the array.
4. Repeat till our triplet is golden :)

import numpy as np

arr1=np.ndarray.flatten(arr)
arr1.sort()
arr1

def getTriplet(arr, sum): 
    n = len(arr)
    
    arr.sort() # sort from lowest to highest, fix first element
    
    for i in range(0, n-2): 
        l = i + 1 # left is one after locked value
          
        r = n-1 # right is end of array
        while (l < r): 
            if( arr[i] + arr[l] + arr[r] == sum): 
                print(arr[i], arr[l], arr[r])
                return arr[i], arr[l], arr[r]

            # if less than sum, move to a larger number (left move)
            elif (arr[i] + arr[l] + arr[r] < sum): 
                l += 1
            # if more than sum, move to a smaller number (right move)
            else: # A[i] + A[l] + A[r] > sum 
                r -= 1
  
    # rip no triplet shrugs
    return 0,0,0

ans1,ans2,ans3=getTriplet(arr1,2020)
print(ans1*ans2*ans3)

24 539 1457
18847752

And there we have it - our golden triplet, 24 539 1457! Ans: 18847752

Thoughts after day 1: given that it’s the first day, the problems weren’t too difficult - nonetheless, it’s a good start to the month, and my problem solving engines have been revved up. Onwards we go!