Merge pull request #7143 from ealvar3z/challenge-191-refactor

refactored Python solution

1 files changed, 78 insertions, 35 deletions

diff --git a/challenge-191/ealvar3z/python/ch-2.py b/challenge-191/ealvar3z/python/ch-2.py
index e013d84da8..a937537025 100644
--- a/challenge-191/ealvar3z/python/ch-2.py
+++ b/challenge-191/ealvar3z/python/ch-2.py
@@ -1,39 +1,82 @@
 #!/usr/bin/env python3
-import unittest
-
-
-class TestSolutionII(unittest.TestCase):
-
-    def cute_list(self, n):
-        bitset_total = 2**n
-        bitset = [[0 for i in range(bitset_total)] for j in range(n+1)]
-        # set the base case
-        bitset[0][0] = 1
-
-        # iterate over all of the positions
-        for i in range(1, n+1):
-            # iterate over all of the subsets
-            for j in range(bitset_total):
-                # iterate over all of the numbers w/in each subset
-                for k in range(n):
-                    # for each number in the subset
-                    # check if the number exists?
-                    visit = (j & (1 << k))  # is the bit set?
-                    condition_one_holds = ((k+1) % i == 0)
-                    condition_two_holds = (i % (k+1) == 0)
-                    if visit and condition_one_holds or condition_two_holds:
-                        # if one of these conditions hold, and we have seen the
-                        # value, then the list is cute.
-                        # Grab the count of what we've seen and return it.
-                        # if this bit was set, unset it
-                        visited = (j ^ (1 << k))
-                        saw_it = bitset[i-1][visited]
-                        count = bitset[i][j] = bitset[i][j] + saw_it
-        return count
-
-    def test_cute_list(self):
-        self.assertEqual(self.cute_list(2), 2)
+from collections import Counter, defaultdict
+from functools import lru_cache
+from unittest import main, TestCase
+
+
+class TestSolutionII(TestCase):
+
+    # backtracking solution
+    def cute(self, n: int) -> int:
+        @lru_cache(maxsize=None)
+        def backtrack(_list):
+            if len(_list) == 1:
+                return 1
+
+            count = 0
+            for j in range(len(_list)):
+                if _list[j] % len(_list) == 0 or len(_list) % _list[j] == 0:
+                    count += backtrack(_list[:j] + _list[j+1:])
+
+            return count
+
+        return backtrack(tuple(range(1, n+1)))
+
+    # backtracking, bitmask, & dp solution
+    def cuter(self, n: int) -> int:
+        num_slots = defaultdict(set)
+        for i in range(1, n + 1):
+            # For each num, find all its (f)actors and (p)roducts from [1 .. n]
+            f = 1
+            p = f * f
+            factors = i // f
+            while p <= i:
+                if i % f == 0:
+                    num_slots[f].add(i)
+                    num_slots[factors].add(i)
+                    num_slots[i].add(factors)
+                    num_slots[i].add(f)
+                f += 1
+            num_slots[i].add(i)
+
+        # Get a list of the indices, and count the number of ways we get
+        # a unique value from each array.  Sort by length for easier
+        # memoization, and reduces "branching".
+        values = sorted(num_slots.values(), key=len)
+
+        # Pass values to our helper function to run the counter.
+        return self.runner(values)
+
+    @lru_cache(maxsize=None)
+    def runner(self, values, start=0, seen={0: 1}):
+        # `seen` represents the states so far: Each key is a possible set of
+        # numbers that we've already been seen, as a bitmask.  Each value is
+        # the # of ways we could have arrived at that set.
+
+        # base case
+        if start == len(values):
+            return sum(seen.values())
+
+        cache = Counter()
+
+        # For each path we've seen
+        for k, v in seen.items():
+            # For each available number
+            for i in values[start]:
+                # if it has not been chosen
+                if (1 << i) & k == 0:
+                    # grab the count, and add it to the cache
+                    cache[k + (1 << i)] += v
+
+        # backtrack
+        return self.runner(values, start + 1, cache)
+
+    def test_cute(self):
+        self.assertEqual(self.cute(15), 24679)
+
+    def test_cuter(self):
+        self.assertEqual(self.cute(15), 24679)
 
 
 if __name__ == "__main__":
-    unittest.main(verbosity=True)
+    main(verbosity=True)