forked from tomkooij/AdventOfCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
day24.py
53 lines (41 loc) · 1.74 KB
/
day24.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# adventofcode
# day 24
from itertools import combinations
INPUTFILE = 'input/input24'
TESTCASE = range(1,6) + range(7,12)
NUMBER_OF_BINS = 4
def find_parts(weights, target, length):
found = []
for i in range(1,length):
for firstpart in combinations(weights, i):
if sum(firstpart) != target: continue
found.append(firstpart)
return set(found)
if __name__ == '__main__':
with open(INPUTFILE, 'r') as f:
lines = f.readlines()
weights = set([int(x) for x in lines])
#weights = set(TESTCASE)
bintotal = sum(weights)/NUMBER_OF_BINS
print "Dataset has %d weights. %d Bins. Binsize = %d" % (len(weights), NUMBER_OF_BINS, bintotal)
firstparts = find_parts(weights, bintotal, len(weights)/3)
print 'number of unique firstparts:', len(firstparts)
shortestpart = min([len(x) for x in firstparts])
firstparts = [x for x in firstparts if len(x) == shortestpart]
print 'length of shortest firstparts: ', len(firstparts[0])
fast_min_QE = min(reduce(lambda x,y: x*y, p) for p in firstparts)
print 'predicted min QE: ', fast_min_QE
#print 'firstparts: ', firstparts
assert NUMBER_OF_BINS == 3, 'Full search only implemented for 3 bins'
# full search of parts 2 and 3 foreach part 1
QE = []
for i, part1 in enumerate(firstparts, start=1):
if not i % 1000: print '%d firstparts searched.' % i
rest = weights - set(part1)
restparts = find_parts(rest, bintotal, len(weights)/2)
for part2 in restparts:
part3 = rest - set(part2)
if sum(part3) == bintotal:
#print "found: ", part1, part2, part3
QE.append(reduce(lambda x,y: x*y, part1))
print "min QE after fullsearch = ", min(QE)