regexyl · March 28, 2023 12:09 · Mar 28, 2023
diff --git a/diceCombinations.py b/diceCombinations.py
@@ -0,0 +1,46 @@
+from functools import cache
+
+"""
+You are throwing a dice for a fixed number of times (`throwCount`), of which
+you know the average of the total score. The total score is calculated by
+adding up all the dice scores from each throw. You only know the score of a
+few of the dice throws.
+
+Find all possible combinations of the remaining dice that fulfill
+the above information.
+
+throwCount: Total of number of dice throws
+diceAverage: Average score of all thrown dices
+someThrown: Scores of some of the dice that had been thrown (<= throwCount)
+"""
+
+# Assuming order of dice thrown doesn't matter
+def diceCombinations(throwCount: int, diceAverage: int, someThrown: list[int]):
+  remaining = throwCount - len(someThrown)
+  remainingSum = diceAverage * throwCount - sum(someThrown)
+  possible = []
+  seen = set()
+
+  # Find all combinations of dice that can make up remaining sum
+  @cache
+  def dp(total: int, tries: int, combi: tuple[int]):
+    if tries == 0 and total == 0:
+      combiTuple = tuple(sorted(combi))
+      if combiTuple in seen or len(list(combi)) == 0:
+        return
+      possible.append(list(combi))
+      seen.add(combiTuple)
+      return
+    elif tries <= 0 or total <= 0:
+      return
+
+    for i in range(1, 7):
+      dp(total - i, tries - 1, combi + (i,))
+
+  dp(remainingSum, remaining, ())
+  return possible
+
+# Any combi that adds up to 8 and is within 3 throws: 1 combi -> [1, 4, 3]
+print(diceCombinations(7, 3, [4, 6, 1, 2]))
+# `someThrown` already lists all 7 scores: result -> []
+print(diceCombinations(7, 3, [4, 6, 1, 2, 1, 1, 6]))
No results found