#advent of code 2020
#day 09
#genuinely surprised the simple solution worked
#shamelessly googled the code for combinations, 
#didn't feel like implementing it
#if i reversed the "visited" list the runtime could be faster but w/e

def PossibleCombs(n,k):
	combinations = [];
	if k==1: return n;
	for i in range(len(n)):
		head = n[i:i+1]
		tail = PossibleCombs(n[i+1:],k-1);
		for j in range(len(tail)):
			if type(tail[j]) == int:
				comb = head + [tail[j]]
			else: 
				comb = head + tail[j];
			combinations.append(comb);
	return combinations;

p1 = None;
limit = 25;
numbers = [];
PuzzleInput = open("09.in","r");
for line in PuzzleInput: numbers.append(int(line));
PuzzleInput.close();
previous = numbers[:limit];
counter = limit -1;

for n in numbers[limit:]:
	counter += 1;
	found = False;
	for combo in PossibleCombs(previous,2):
		if n == sum(combo): 
			previous = previous[1:] + [n];
			found = True;
			break;
	if not found: 
		p1 = n;
		break;

visited = numbers[:counter];
for i,n in enumerate(visited):
	subsum = 0 + n;
	subcounter = 0 + i;
	while subsum < p1:
		subcounter += 1;
		subsum += visited[subcounter];
	if subsum == p1:
		p2 = min(visited[i:subcounter]) + max(visited[i:subcounter]) ;
		break;

print("part 1 =",p1);
print("part 2 =",p2);