Advent Of Code – 2020 Day 1

On By ellenwoottenIn advent-of-code

Day 1 – Advent of Code 2020 (https://adventofcode.com/2020/day/1)

Data Preparation

Before even looking at the problem I like to make sure that my data is prepared nicely. I paste the “test” input given on the description page into a file named day1-test.txt and the full puzzle input into day1-input.txt.
We then want to read out this data and I link to start with it in a dictionary, where each line is an item in the list.

I like to start with a variable which sets us into what mode we want to run it – I will set real_run to False to start with, to test with and get to grips with the problem. I will set it to True when I am ready to run the code for real and produce my output

real_run = False

# Set file name based on if we are in real or test mode.
file_name = "day1-input.txt" if real_run else "day1-test.txt"

How do we get the input into a nice clean list, with no bonus characters?

I like the following method, it is neat and all on one line. I don’t want to fuss about opening the file and doing any more than I have to here. It uses the file open function, rstrip method and list comprehension.

Resources:

# create a list from the file, removing any '\n' characters
data = [line.rstrip('\n') for line in open(file_name)]

# print data to check it's what we want it to be
print(data)

['1721', '979', '366', '299', '675', '1456']

Part One

Now we have the test input in a useable format we are able to start looking at solving the problem…

The problem can be summarised as:

  • We have a list of numbers
  • A pair of numbers in this list add up to a given value (2o2o in this case)
  • Multiply the pair of numbers together and return that value
# make a note of our given sum value to find
sum_value = 2020

# it is worth doint some more data prep now, since we know all out items in our list should be whole numbers - aka ints
data = [int(val) for val in data]

# sorting may also be useful in this case
data.sort()

print(data)

[299, 366, 675, 979, 1456, 1721]

Finding the pair using ‘difference’ method

In this method we are able to use our fixed value sum_value and operate for each value in our list – until we find our pair.
For each value, we can see if the difference between it and sum_value is contained in the list.

for val in data:
    diff = sum_value - val

    if diff in data:
        pair = (val, diff)
        break

result = pair[0] * pair[1]
print(f"Found the pair! {pair}. Result: {result}")

Found the pair! (299, 1721). Result: 514579

Part Two

Incredibly similar to Part One but instead of only two values we need to find three that add up to the sum_value.

# define inner loop which will return the set of 
def inner_loop(outer_val, new_list):
    for inner_val in new_list:
        diff = sum_value - outer_val - inner_val

        if diff in new_list:
            return (outer_val, inner_val, diff)
    return None

remaining_data = data.copy()

for val in data:
    # removing the values in the top level data as once we have parsed this
    # we'll have checked it with every combination of the list so may as well get rid
    remaining_data.remove(val)

    trips = inner_loop(val, remaining_data)
    if trips:
        break


result = trips[0] * trips[1] * trips[2]
print(f"Found the trips! {trips}. Result: {result}")

Found the trips! (366, 675, 979). Result: 241861950

Bosh!

And like that, we have our results to both parts. We swap our file into real_run mode and can get our final results.

Extension

I’m going to try and go one step further than the Advent Of Code 2020 Day 1 goes and try to create a function which takes in the set size that we want to sum to our given value.

This time we want to use sets, not lists and we can use the sum and combinations methods.

Useful methods:

import itertools

def find_combination(data_list, set_size, sum_val):
    set_data = set(data)
    list_of_sets = [set(i) for i in itertools.combinations(set_data, set_size)]

    for current_set in list_of_sets:
        set_total = sum(current_set)

        if set_total == sum_val:
            return current_set

    # if combination has not been found by now... there isn't one
    return False

# Verify we get the same value as part one
find_combination(data, 2, 2020)

{299, 1721}

# Verify we get the same value as part two
find_combination(data, 3, 2020)

{366, 675, 979}

# We don't expect this to return anything sensible
find_combination(data, 4, 2020)

False

# Added up the first 4 values in the list
find_combination(data, 4, 2319)

{299, 366, 675, 979}

Made using Jupyter notebook

Leave a comment