Advent of Code 2020 in Python, Day 1

I’m late to Advent of Code this year, but I thought I’d post my solution anyway. I can’t say if I’ll continue doing more of these (and posting them here) or not — I’m well-rested and have the energy after a week of vacation tonight, but I return to work on Monday and may get busy with other things in life.

The prompt for day 1 asks you, in the first part, to find the two integers in the input data that add to 2020, and multiply them together and return the product.

In my first solution, I wrote two functions. The first takes an integer term, a list of integer terms, and a desired total and returns the first integer from the list of terms that satisfies term + x = total.

def find_addend_to_sum_to_num(term1, terms, total=2020):
    """
    Given a term (integer) and a list of terms, find the other term in the list
    of terms to satisfy:
    term + ____ = total
    Returns an integer
    """
    matches = [x for x in terms if total - x == term1]
    if len(matches) < 1:
        return None
    return matches[0]

A second function takes the list of all terms and a desired total as arguments. It splits the terms into three lists: lower has all terms less than half of total; upper has all terms greater than half of total; and half has all terms that are half of total. I split it because any solution for two terms will either involve one number less than half of the total and one number greater than half of the total, or two numbers that are both exactly half of the total. If there are two items in half, that’s the solution. Otherwise, loop through the terms that are less than half of the total and use find_addend_to_sum_to_num to find a matching term from the upper terms.

def find_terms_adding_to_num(terms, total=2020):
    """
    Given a list of `terms`, find the two that add to `total`
    Returns a tuple of integers
    """
    lower = [x for x in terms if x <= total / 2]
    upper = [x for x in terms if x > total / 2]
    half = [x for x in lower if x == total / 2]

    if len(half) >= 2:
        return (half[0], half[1])

    for term in lower:
        match = find_addend_to_sum_to_num(term, upper, total=2020)
        if match:
            return (term, match)

    return (None, None)

Part 2 is a variation on the theme, asking for three terms summing to 2020 instead of two.

At first I wrote another function to solve part 2 that works on a similar principle to finding_terms_adding_to_num, except instead of looping through all the lower terms it recursively loops through every term, since that trick doesn’t work if you’re dividing it in more than two pieces, and then loops through every other term in a while loop, checking for a matching third term with find_addend_to_sum_to_num.

def solve_part_2(terms, total=2020):
    term1 = terms.pop()
    working_terms = list(terms)
    while len(working_terms) > 0:
        term2 = working_terms.pop()
        if term1 + term2 < total:
            match = find_addend_to_sum_to_num(term1 + term2, working_terms,
                                              total=total)
            if match:
                return (term1, term2, match)

    return solve_part_2(terms, total=total)

These solutions worked, but I realized I could refactor the recursive solution to part 2 to work for any number of terms and solve both parts with one function.

def find_terms_adding_to_x(terms, n=2, total=2020):
    """ Given a list of integer `terms`, find the `n` terms that add
    to `total`
    Return those `n` terms as a tuple of integers.
    """
    if len(terms) == 0:
        return []

    if n == 1:
        if total in terms:
            return [total]
        return []

    working_terms = list(terms)
    term1 = working_terms.pop()
    remaining_terms = list(working_terms)
    matches = find_terms_adding_to_x(remaining_terms,
                                     n=n - 1,
                                     total=total - term1)
    if matches:
        return [term1] + matches

    return find_terms_adding_to_x(working_terms, n=n, total=total)

This simplifies things significantly — it can find any number of terms that sum to some total, and it no longer needs the separate find_addends_to_sum_to_num function. It works in basically the same way as the solve_part_2 function, except it replaces the while loop with pure recursion.

This wrapper function calls it and returns the solution:

def solve(terms, n=2, total=2020):
    """ Given a list of integer `terms`, find the `n` terms that add
    to `total` and return the product of those terms multiplied together """
    return reduce(mul, find_terms_adding_to_x(terms, n=n, total=total))