1 files changed, 86 insertions, 0 deletions
diff --git a/24/main.py b/24/main.py
new file mode 100755
index 0000000..61c97a6
--- /dev/null
+++ b/24/main.py
@@ -0,0 +1,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()