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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
#!/usr/bin/python
from itertools import combinations
def solve_partn(partn, masses):
if partn == 1:
num_groups = 3
else: # partn == 2
num_groups = 4
m_total = sum(masses)
m_group = int(m_total / num_groups)
# At first, it seems the easiest way is to generate all possible
# grouping of packages, and then just keep the ones that are valid,
# and find the best among the remaining configurations. However,
# the input file has 28 packages, so there are 3^28 = 23 trillion
# possible groupings, which is obviously too much to brute-force.
# Instead, we find the candidates for group 1: subsets of the packages
# whose masses add up to `m_group', with the smallest number of items.
# Step 1: Find all combinations of packages in a certain range
k_min = int((m_group - 1) / max(masses)) + 1
k_max = int(len(masses) / num_groups)
combos = []
for k in range(k_min, k_max + 1):
combos += combinations(masses, k)
# Step 2: Keep only combinations whose masses add up to `m_group'
group1 = []
for c in combos:
if sum(c) == m_group:
group1.append(c)
# Step 3: Keep only candidates with the smallest package count
min_len = min(map(len, group1))
smallest = {}
for g1 in group1:
if len(g1) == min_len:
smallest[g1] = []
# Verify for each group 1 candidate that the remaining packages can be
# divided into 2 more groups of mass `m_group'. This takes time and it
# turns out that no candidates get rejected, hence it's commented out.
#for i, g1 in enumerate(smallest):
# remaining = []
# for m in masses:
# if m not in g1:
# remaining.append(m)
# k_max = int(len(remaining) / (num_groups - 1))
# combos = []
# for k in range(k_min, k_max + 1):
# combos += combinations(remaining, k)
# for c in combos:
# if sum(c) == m_group:
# smallest[g1].append(c)
#valid = {}
#for g1 in smallest.keys():
# if len(smallest[g1]) > 0:
# valid[g1] = smallest[g1]
# Calculate quantum entanglement of each group 1 candidate
qentangs = []
for g1 in smallest.keys():
qe = 1
for m in g1:
qe *= m
qentangs.append(qe)
return min(qentangs)
def main():
# Read package weights from input text file
with open("input.txt", "r") as f:
masses = list(map(int, f.read().splitlines()))
print("Part 1 solution:", solve_partn(1, masses)) # 10439961859 for me
print("Part 2 solution:", solve_partn(2, masses)) # 72050269 for me
if __name__ == "__main__":
main()
|
