#advent of code 2020
#day 10
#very similar (if not identical) to towels puzzle, 2024-d19
#memorize previous paths and just sum up the valid paths for each adapter
#although this one i think is easier due to no duplicates 
#and working on numbers instead of characters
bag = [];
PuzzleInput = open("10.in","r");
for num in PuzzleInput: bag.append(int(num));
PuzzleInput.close();
#first and last items are from puzzle description
bag = [0] + [x for x in sorted(bag)] + [max(bag) +3]; 
connections = dict();
connections[1] = 0;
connections[2] = 0;
connections[3] = 0;
#since there are no duplicates and all adapters must be connected
#we can just check against the previous value for part 1;
for index in range(1,len(bag)):
	adapter1 = bag[index];
	adapter2 = bag[index-1];	
	diff = adapter1 - adapter2;
	connections[diff] += 1;

p1 = connections[1] * connections[3];

p2 = 0;
options = dict();
options[0] = 1;
for index in range(1,len(bag)):	
	previous = bag[:index];
	possible = [x for x in previous if bag[index] - x <=3];
	options[bag[index]] = 0;
	for poss in possible:
		options[bag[index]] += options[poss];	

p2 = options[max(bag)];
print("part 1 =",p1);
print("part 2 =",p2);