Advent-of-Code/2020/Day 1/Solution.py

target = 2020
input_file = "input.txt"


def find_sum_of_two():
    """
    Find two numbers from a list that add to a target.
    This is done by separating the numbers in a smaller than half and bigger than half of the target,
    and trying to find a match that would complement the sum, rather than adding everything together.
    :return: None
    """
    large_n = []
    small_n = []

    with open(input_file) as file:
        line = file.readline()
        while line and line != "\n":
            halftarget_count = 0

            number = int(line)
            if number > target/2:
                large_n.append(number)
            elif number == target/2:
                # Used for "early" exit if we find twice the half
                halftarget_count += 1
            else:
                small_n.append(number)

            if halftarget_count == 2:
                print(f"Found a sum : {target/2}*2 = {target}\nAnswer is {(target/2)**2}")
                break

            line = file.readline()

    # This was chosen in this order because of input I got : mainly large numbers
    for big_one in large_n:
        complement = target-big_one
        if complement in small_n:
            print(f"Found a sum : {big_one}+{complement} = {target}\nAnswer is {big_one*complement}")
            return

    print("No sum found that can reach {target}")


def sum_search(target_sum, inputs):
    """
    Basically the same as above but for an arbitrary target and list of numbers.
    :param target_sum: Sum that we are looking numbers to reach
    :param inputs: List of numbers to search for a pair adding to target_sum
    :return: The pair if found, False otherwise
    """
    lower = []
    upper = []

    for num in inputs:
        if num < target_sum/2:
            lower.append(num)
        else:
            upper.append(num)

    # As those list might be of a different repartition, search the smaller one while iterating on the larger one
    search_list = lower if len(lower) < len(upper) else upper
    iter_list = upper if len(lower) < len(upper) else lower

    for num in iter_list:
        if target_sum - num in search_list:
            return num, target_sum-num

    return False


def find_sum_of_three():
    """
    Find a triplet of number that reach a target when added together. This time, constructing a list by subtracting each
    number to the target, and using this list to check if the we can find two other numbers that add up to it.
    To put it another way, instead of searching for a,b and c in a+b+c = t, search for a,b in a+b = t-c for every c.
    :return: None
    """
    data = []
    subtracted_to_target = []
    with open(input_file) as file:
        line = file.readline()
        while line and line != "\n":
            data.append(int(line))
            subtracted_to_target.append((target-data[-1], data[-1]))

            line = file.readline()

    # Honestly not sure if it helps
    data.sort()

    for sub_target in subtracted_to_target:
        result = sum_search(sub_target[0], data)
        if result:
            print(f"Sum found : {result[0]}+{result[1]}+{sub_target[1]} = {target}\nResult is {result[0]*result[1]*sub_target[1]}")
            return

    print("No sum found")