How to collect results of recursive backtracking?

Question

I'm teaching myself recursive backtracking. For a dice summing problem I can't figure out how to elegantly collect the results.

For reference here's my code that just prints any dice roll which meets the criteria. Ideally I want to change it so instead of printing the output, I can build up a list of those chosen dice and return it.

Below here is code that does not do what I want

def dice_sum(num_dice: int, target_sum: int) -> None:
    dice_sum_helper(num_dice, target_sum, [])


def dice_sum_helper(num_dice: int, target_sum: int, chosen: List[int]) -> None:
    if num_dice == 0 and sum(chosen) == target_sum:
        print(chosen)
    elif num_dice == 0:
        pass
    else:
        for i in range(1, 7):
            chosen.append(i)
            dice_sum_helper(num_dice - 1, target_sum, chosen)
            chosen.pop()

Instead I want it to do something like this

from typing import List
DiceResult = List[List[int]]


def dice_sum(num_dice: int, target_sum: int) -> DiceResult:
    return dice_sum_helper(num_dice, target_sum, [])


def dice_sum_helper(num_dice: int, target_sum: int, chosen: List[int]) -> DiceResult:
    if num_dice == 0 and sum(chosen) == target_sum:
        # Return the value that meets the constraints
        return chosen
    elif num_dice == 0:
        pass
    else:
        for i in range(1, 7):
            chosen.append(i)
            # Return the result of my recursive call and build the list of lists?
            result = dice_sum_helper(num_dice - 1, target_sum, chosen)
            return result.append(result)
            # End of that logic
            chosen.pop()

I'm looking more for the theory or pattern to use than the exact code. I can't quite get the code to collect and append each result without using an external list working.

score 2 · Answer 1 · answered Jul 06 '19 at 19:39

You could utilize yield and yield from to return results from your functions:

from typing import List

def dice_sum(num_dice: int, target_sum: int) -> None:
    yield from dice_sum_helper(num_dice, target_sum, [])


def dice_sum_helper(num_dice: int, target_sum: int, chosen: List[int]) -> None:
    if num_dice == 0 and sum(chosen) == target_sum:
        yield chosen[:]
    elif num_dice == 0:
        pass
    else:
        for i in range(1, 7):
            chosen.append(i)
            yield from dice_sum_helper(num_dice - 1, target_sum, chosen)
            chosen.pop()

# you can store the results e.g. to list: 
# results = list(dice_sum(3, 12))

for dices in dice_sum(3, 12):
    for d in dices:
        print('{: ^4}'.format(d), end='|')
    print()

Prints:

 1  | 5  | 6  |
 1  | 6  | 5  |
 2  | 4  | 6  |
 2  | 5  | 5  |
 2  | 6  | 4  |
 3  | 3  | 6  |
 3  | 4  | 5  |
 3  | 5  | 4  |
 3  | 6  | 3  |
 4  | 2  | 6  |
 4  | 3  | 5  |
 4  | 4  | 4  |
 4  | 5  | 3  |
 4  | 6  | 2  |
 5  | 1  | 6  |
 5  | 2  | 5  |
 5  | 3  | 4  |
 5  | 4  | 3  |
 5  | 5  | 2  |
 5  | 6  | 1  |
 6  | 1  | 5  |
 6  | 2  | 4  |
 6  | 3  | 3  |
 6  | 4  | 2  |
 6  | 5  | 1  |

M Somerville · Accepted Answer · 2019-07-07T07:39:11.100

You can pass a 'results' list in which to store the results:

from typing import List
DiceResult = List[List[int]]


def dice_sum(num_dice: int, target_sum: int) -> DiceResult:
    results = []
    dice_sum_helper(num_dice, target_sum, [], results)
    return results


def dice_sum_helper(num_dice: int, target_sum: int, chosen: List[int], results: DiceResult):
    if num_dice == 0 and sum(chosen) == target_sum:
        # Store the value that meets the constraints
        results.append(chosen.copy())
    elif num_dice == 0:
        pass
    else:
        for i in range(1, 7):
            chosen.append(i)
            dice_sum_helper(num_dice - 1, target_sum, chosen, results)
            chosen.pop()

Note this will be returning many duplicates, if ordering does not matter. You may want to investigate changing this to calculate a smaller target sum each recursion, and memoizing that in some way so it save on a lot of work. See also e.g. Calculate the number of ways to roll a certain number

I might be doing something wrong, when I try to use the add to list parameter method of getting the results, I'm getting back a list of empty lists. I've tried modifying my code and pasting yours in directly. With 2 dice and a target_sum of 9, I get result (left side) vs expected (right side) assert [[], [], [], []] == [[3, 6], [4, 5], [5, 4], [6, 3]] — Josh R, Jul 06 '19 at 20:54
Apologies, I missed out a `copy()` when storing the result (otherwise as passed by reference, your `pop()`ing removes the result as the program continues :) ), fixed now. — M Somerville, Jul 07 '19 at 07:40

score 1 · Answer 3 · answered Jul 07 '19 at 04:44

For the stated goal of elegance, I would go with a simpler design without a helper function nor passing extra arguments:

def dice_sum(num_dice, target_sum):
    solutions = []

    for i in range(1, 7):
        if target_sum < i:
            continue

        if target_sum == i:
            if num_dice == 1:
                solutions.append([i])

            continue

        for solution in dice_sum(num_dice - 1, target_sum - i):
            solutions.append([i] + solution)

    return solutions

print(dice_sum(3, 5))

OUTPUT

> python3 test.py
[[1, 1, 3], [1, 2, 2], [1, 3, 1], [2, 1, 2], [2, 2, 1], [3, 1, 1]]
>

For added efficiency, you could add:

if target_sum - i < num_dice - 1:
            continue

before the inner for loop to avoid the recursion if there's no hope.

Nice, especially if you add e.g. https://wiki.python.org/moin/PythonDecoratorLibrary#Memoize so it only ever calculates any (dice+sum) combo once. — M Somerville, Jul 07 '19 at 08:08

score 0 · Answer 4 · answered Aug 06 '19 at 09:41

A recursive generator with early abort conditions, so you don't get duplicate solutions, with regards to the order of die rolls. I.e. I assume that your dice are not identifiable and therefor the order of the numbers shouldn't matter.

def dice_sum (num_dice, target_sum, start=1):
    if num_dice == 1 and 0 < target_sum < 7:
        yield (target_sum, )
        return
    if num_dice * 6 < target_sum or num_dice > target_sum:
        return
    for i in xrange(start, 7):
        for option in dice_sum(num_dice - 1, target_sum - i, i):
            if i > option[0]:
                return
            yield (i, ) + option

>>> tuple(dice_sum(3, 12))
((1, 5, 6), (2, 4, 6), (2, 5, 5), (3, 3, 6), (3, 4, 5), (4, 4, 4))

How to collect results of recursive backtracking?

4 Answers4

Linked

Related