Programming Challenge - Game Scoring

Question

Can this solution be made more efficient?

game_scoring.py

"""
Game Scoring
Imagine a game where the player can score 1, 2, or 3 points depending on the move they make. Write a function or functions,
that for a given final score computes every combination of points that a player could score to achieve the specified score in the game.
Signature
int[][] gameScoring(int score)
Input
Integer score representing the desired score
Output
Array of sorted integer arrays demonstrating the combinations of points that can sum to the target score
Example 1:
Input: 
score = 4
Output: 
[ [ 1, 1, 1, 1 ], [ 1, 1, 2 ], [ 1, 2, 1 ], [ 1, 3 ], [ 2, 1, 1 ], [ 2, 2 ], [ 3, 1 ] ]
Example 2:
Input: 
score = 5
Output:
[ [ 1, 1, 1, 1, 1 ], [1, 1, 1, 2 ], [ 1, 1, 2, 1 ], [ 1, 1, 3 ], [ 1, 2, 1, 1 ], [ 1, 2, 2 ], [ 1, 3, 1 ], [ 2, 1, 1, 1 ], [ 2, 1, 2 ], [ 2, 2, 1 ], [ 2, 3 ], [ 3, 1, 1 ], [ 3, 2 ] ]
"""
from itertools import combinations_with_replacement, product
import sys
sys.dont_write_bytecode = True
def gameScoring(score):
 points = [1,2,3]
 combos = list()
 for L in range(1,score+1):
 combos += list(combinations_with_replacement(points, L))
 for M in range(len(combos)):
 combos += list(product(combos[M], repeat=len(combos[M])-1))
 for i,combo in enumerate(combos):
 if sum(combo) != score:
 combos[i] = None
 output = sorted(list(set(combo for combo in combos if combo is not None)))
 return [list(out) for out in output]
# These are the tests we use to determine if the solution is correct.
# You can add your own at the bottom.
test_case_number = 1
def check(expected, output):
 global test_case_number
 result = True
 if len(expected) == len(output):
 for score in expected:
 result = result & (score in output)
 for score in output:
 result = result & (score in expected)
 else:
 result = False
 rightTick = '\u2713'
 wrongTick = '\u2717'
 if result:
 print(rightTick, ' Test #', test_case_number, sep='')
 else:
 print(wrongTick, ' Test #', test_case_number, ': Expected ', sep='', end='')
 print(expected)
 print(' Your output: ', end='')
 print(output)
 print()
 test_case_number += 1
if __name__ == "__main__":
 test_1 = 4
 expected_1 = [
 [1, 1, 1, 1],
 [1, 1, 2],
 [1, 2, 1],
 [1, 3],
 [2, 1, 1],
 [2, 2],
 [3, 1]
 ]
 output_1 = gameScoring(test_1)
 check(expected_1, output_1)
 test_2 = 5
 expected_2 = [
 [1, 1, 1, 1, 1],
 [1, 1, 1, 2],
 [1, 1, 2, 1],
 [1, 1, 3],
 [1, 2, 1, 1],
 [1, 2, 2],
 [1, 3, 1],
 [2, 1, 1, 1],
 [2, 1, 2],
 [2, 2, 1],
 [2, 3],
 [3, 1, 1],
 [3, 2],
 ]
 output_2 = gameScoring(test_2)
 check(expected_2, output_2)
 
 # Add your own test cases here
 

Answer 1

You've chosen a deeply inefficient algorithm. Your strategy is basically "throw a million darts at random and check which ones land on the board". You can do better. Improvement one is to recognise that you're really only generating permutations of combinations:

def score_permute(score: int) -> Iterator[tuple[int, ...]]:
 points = range(1, N + 1)
 for L in range(1, score + 1):
 combos = combinations_with_replacement(points, L)
 for combo in combos:
 if sum(combo) == score:
 yield from permutations(combo)

But much more importantly, you can directly generate these combinations with the correct sum as a given, something like:

def score_direct(score: int) -> Iterator[tuple[int, ...]]:
 scores = [1] * score
 while True:
 yield tuple(scores)
 new_ones = 0
 while True:
 new_ones += scores.pop()
 if len(scores) == 0:
 return
 if scores[-1] < N:
 break
 scores[-1] += 1
 new_ones -= 1
 scores.extend((1,) * new_ones)

The test code is kind of bad, and bare assert will be preferable.

Suggested

"""
Game Scoring
Imagine a game where the player can score 1, 2, or 3 points depending on the move they make. Write a function or functions,
that for a given final score computes every combination of points that a player could score to achieve the specified score in the game.
Signature
int[][] gameScoring(int score)
Input
Integer score representing the desired score
Output
Array of sorted integer arrays demonstrating the combinations of points that can sum to the target score
Example 1:
Input:
score = 4
Output:
[ [ 1, 1, 1, 1 ], [ 1, 1, 2 ], [ 1, 2, 1 ], [ 1, 3 ], [ 2, 1, 1 ], [ 2, 2 ], [ 3, 1 ] ]
Example 2:
Input:
score = 5
Output:
[ [ 1, 1, 1, 1, 1 ], [1, 1, 1, 2 ], [ 1, 1, 2, 1 ], [ 1, 1, 3 ], [ 1, 2, 1, 1 ], [ 1, 2, 2 ], [ 1, 3, 1 ], [ 2, 1, 1, 1 ], [ 2, 1, 2 ], [ 2, 2, 1 ], [ 2, 3 ], [ 3, 1, 1 ], [ 3, 2 ] ]
"""
from itertools import combinations_with_replacement, permutations, product
from timeit import timeit
from typing import Iterator
N = 3
def score_orig(score: int) -> Iterator[tuple[int, ...]]:
 points = [1, 2, 3]
 combos = list()
 for L in range(1, score + 1):
 combos += list(combinations_with_replacement(points, L))
 for M in range(len(combos)):
 combos += list(product(combos[M], repeat=len(combos[M]) - 1))
 for i, combo in enumerate(combos):
 if sum(combo) != score:
 combos[i] = None
 output = sorted(list(set(combo for combo in combos if combo is not None)))
 return [list(out) for out in output]
def score_permute(score: int) -> Iterator[tuple[int, ...]]:
 points = range(1, N + 1)
 for L in range(1, score + 1):
 combos = combinations_with_replacement(points, L)
 for combo in combos:
 if sum(combo) == score:
 yield from permutations(combo)
def score_direct(score: int) -> Iterator[tuple[int, ...]]:
 scores = [1] * score
 while True:
 yield tuple(scores)
 new_ones = 0
 while True:
 new_ones += scores.pop()
 if len(scores) == 0:
 return
 if scores[-1] < N:
 break
 scores[-1] += 1
 new_ones -= 1
 scores.extend((1,) * new_ones)
METHODS = (score_orig, score_permute, score_direct)
def test() -> None:
 test_1 = (
 4, {
 (1, 1, 1, 1),
 (1, 1, 2),
 (1, 2, 1),
 (1, 3),
 (2, 1, 1),
 (2, 2),
 (3, 1),
 }
 )
 test_2 = (
 5, {
 (1, 1, 1, 1, 1),
 (1, 1, 1, 2),
 (1, 1, 2, 1),
 (1, 1, 3),
 (1, 2, 1, 1),
 (1, 2, 2),
 (1, 3, 1),
 (2, 1, 1, 1),
 (2, 1, 2),
 (2, 2, 1),
 (2, 3),
 (3, 1, 1),
 (3, 2),
 }
 )
 for method in METHODS:
 for score, expected in (test_1, test_2):
 output = {tuple(s) for s in method(score)}
 assert output == expected
def compare() -> None:
 for n, method in zip(
 (7, 10, 25),
 METHODS,
 ):
 def with_arg():
 tuple(method(n))
 t = timeit(with_arg, number=1)
 print(f'{method.__name__} n={n} in {t:.3f} s')
if __name__ == "__main__":
 test()
 compare()

Output

score_orig n=7 in 1.171 s
score_permute n=10 in 0.503 s
score_direct n=25 in 1.084 s