Advent of Code: Day #01 - Report Repair

The advent of code is a virtual advent calender that replaces chocolate with small programming puzzles! I'm going to be completing the problems in Python because it's fast to write and i'll be completing these problems on a morning likely before my morning coffee so the solutions may not be the most thought out or efficient.

For the first task we must identify some discrepancies in the expense report and find two numbers that sum to 2020 then return their product.

Reading in the data

The first step is to read in the input data. Whilst doing this I noticed that whilst most of the numbers are large >1000 a handful where less than 1000. I created two arrays and stored the large numbers in one and the small in the others.

def read_data(path):
    big_nums = []
    small_nums = []
    with open(path, "r") as file:
        for line in file.readlines():
            num = int(line)
            if num < 1000:
                small_nums.append(num)
            else:
                big_nums.append(num)
    return big_nums, small_nums

The Solution

The smallest number in the big_nums array is 1072, this shows us that to get 2020 we need to sum one big number and one small number because it's not possible for two of the large numbers to make 2020 (Would need two big numbers around 1010). By splitting the data into the two arrays we simply have to compare each big number against every small number as opposed to all numbers, this cuts the numbers we need to check from 199 down to 11.

def task_one(big, small):
    for b_num in big:
        for s_num in small:
            if b_num + s_num == 2020:
                return b_num * s_num

The Solution

The second task is similar to the fist, we must again find numbers that sum to 2020 and return their product but this time it is three numbers instead of two. It was obvious to me that the three numbers we need will be found in the small numbers array. To find these I decided to nest 3 for loops to look at all the small numbers, this is not an elegant solution by any means with a time complexity of O(n^3) it's actually pretty awful but it works fine in this case where there are only 11 elements in the small numbers array.

def task_two(small):
    for i, s_num in enumerate(small):
        for j, s_num2 in enumerate(small[i + 1:]):
            for k, s_num3 in enumerate(small[j + 1:]):
                if s_num + s_num2 + s_num3 == 2020:
                    return s_num * s_num2 * s_num3

And thats day one completed! Links to the code and the GitHub repo is provided below. If you wish to join me and tackle the advent of code yourself consider joining my private leaderboard by using this code: 353270-1fc6ef28