#!/usr/bin/python

from math import sqrt



def solve_partn(partn, target):
    house = 1
    while True:
        # Find all divisors of the house number, because those
        # determine which elves brings presents to which house.
        # If I were smart, I'd cache the results and use them in
        # both parts 1 and 2, but I can't be bothered to do that.
        divs = [1, house]
        for n in range(2, int(sqrt(house)) + 1):
            if house % n == 0:
                divs += [n, house / n]

        # Give gifts to each house as described in the puzzle text
        gifts = 0
        for d in divs:
            if partn == 1:
                gifts += 10 * d
            else: # partn == 2
                if house / d <= 50:
                    gifts += 11 * d

        if gifts >= target:
            return house

        house += 1



def main():
    # My personalized puzzle input
    target = 34000000

    print("Part 1 solution:", solve_partn(1, target)) # 786240 for me
    print("Part 2 solution:", solve_partn(2, target)) # 831600 for me



if __name__ == "__main__":
    main()