# Programming Challenge - Game Scoring

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.

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(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)



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 =  * 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 =  * 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