3
\$\begingroup\$

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
  
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.