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