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
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:
- First, we hold out one of the triplets, finding our desired sum of the pair.
- We use the two pointer technique to efficiently determine whether the sum can be reached.
- If not, skip and move on to hold out the next element of the array.
- 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!