From 68615a9ad2c942254135cffb00cf25a84a3b1356 Mon Sep 17 00:00:00 2001
From: Prefetch
Date: Sat, 31 Dec 2022 22:21:39 +0100
Subject: Initial commit

---
 24/input.txt | 28 ++++++++++++++++++++
 24/main.py   | 86 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 24/test.py   | 18 +++++++++++++
 3 files changed, 132 insertions(+)
 create mode 100644 24/input.txt
 create mode 100755 24/main.py
 create mode 100755 24/test.py

(limited to '24')

diff --git a/24/input.txt b/24/input.txt
new file mode 100644
index 0000000..e204f7d
--- /dev/null
+++ b/24/input.txt
@@ -0,0 +1,28 @@
+1
+3
+5
+11
+13
+17
+19
+23
+29
+31
+37
+41
+43
+47
+53
+59
+67
+71
+73
+79
+83
+89
+97
+101
+103
+107
+109
+113
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()
diff --git a/24/test.py b/24/test.py
new file mode 100755
index 0000000..2c2655c
--- /dev/null
+++ b/24/test.py
@@ -0,0 +1,18 @@
+#!/usr/bin/python
+
+import unittest
+
+import main
+
+
+
+class Examples(unittest.TestCase):
+    def test_example1(self):
+        masses = [1, 2, 3, 4, 5, 7, 8, 9, 10, 11]
+        self.assertEqual(main.solve_partn(1, masses), 99)
+        self.assertEqual(main.solve_partn(2, masses), 44)
+
+
+
+if __name__ == "__main__":
+    unittest.main()
-- 
cgit v1.2.3