2024-04-10 | Cassidoo's diceSum Problem

cassidoo's problem was stated thusly:

Imagine you have n dice, and each die has m faces on it (so the numbers are from 1 to m). Write a function where, given an integer target, it returns the number of possible ways to roll the dice to get the sum of target face up. You can safely assume m will never be larger than 20 (so you don't have to deal with mega huge numbers).

Here is my proposed solution, written in python 3.9.2 (hence the snake_case) and pared down to exclude some debugging output:

#!/usr/bin/env python3

# treat m_num_faces as a constant and generate, using dynamic programming, the memoized "number of possible combinations that sum to s_sum_target"
def build_partitions(n_num_coins, m_num_faces, s_sum_target, solutions):
# for the first "row", there is only one coin. So, as long as the target sum is sufficiently small (less than or equal to the number of faces), there is one valid outcome.
# otherwise, there are exactly zero, because the actual sum must be smaller than the target sum.
for t_sum in range(0, s_sum_target+1):
solutions[0][t_sum] = 0 if m_num_faces < (t_sum+1) else 1

for j in range(1, n_num_coins+1):
#print(f"now writing the intermediate elements in row {j}...")
for i in range(0, s_sum_target+1):
next_val = 0
lower_bound = i - m_num_faces if i > m_num_faces else 0
for subcomponent in range(lower_bound, i):
next_val += solutions[j-1][subcomponent]
solutions[j][i] = next_val

def dice_sum(dice, faces, target):
memoized = []
for j in range(0, dice):
memoized.append([])
for i in range(0, target):
memoized[j].append(0)
build_partitions(dice-1, faces, target-1, memoized)
return memoized[dice-1][target-1]

if (__name__ == "__main__"):
print("cassidoo problem (from 2024-04-08)")
n = int(input("Enter the value of n, the number of dice in use: "))
m = int(input("Enter the value of m, the number of faces per die: "))
s = int(input("Enter the target sum: "))
result = dice_sum(n, m, s)
print(f"{result}")