inp = [int(l.strip()) for l in open("1.dat").readlines()]
gnums = sorted(inp)
tgt = 2020
orglen = len(gnums)
def bis(l, diff):
half = round(len(l)/2)
ll, ul = l[:half], l[half:]
tl = ul if ul and ul[0] <= diff else ll
if tl and tl[0] > diff:
return []
if len(tl) > 1:
tl = bis(tl, diff)
return tl
def solve_a_bis(nums):
while(len(nums)):
num = nums.pop(0)
diff = tgt - num
l = bis(nums, diff)
if len(l) and num + l[0] == tgt:
print("solve a bis", num, l[0], num*l[0])
break
def solve_a_brute(nums):
while(len(nums)):
num = nums.pop(0)
diff = tgt - num
if diff in nums:
print("solve a brute", num, diff, num*diff)
break
solve_a_bis(list(gnums))
def solve_b(nums):
rnums = list(reversed(nums))
while len(rnums):
num = rnums.pop(0)
for i, nnum in enumerate(rnums):
nsum = num + nnum
if nsum >= tgt:
continue
diff = tgt - nsum
if diff in rnums[i:]:
print("solve b", num, nnum, diff, num * nnum * diff)
return
solve_b(list(gnums))