Dec-12-2020, 06:18 AM
(This post was last modified: Dec-12-2020, 06:18 AM by deanhystad.)
This is the recursive solution with a cache. It makes 376 guesses and computes 61 partial solutions for a bag of 20 numbers divided into 5 groups.
import random ## Save partial solutions to speed things up. solutions = {} def sticks(bag, count): '''Split bag into count groups. Find the grouping that results in the highest minimum group score. Group score is the sum of numbers in the group. ''' sticks.guesses += 1 # This is a recursive solution with a cache. # Reuse partial solution when possible if score := solutions.get((len(bag), count)): return score if count == 1: # This is the last group and end of recursion. # Return the group score score = (sum(bag), [bag]) solutions[(len(bag), count)] = score return score # Find the best grouping for the remaining groups. # Split the bag into two groups with the size of the # first group ranging from 1 to len(bag)-count+1. # Use recursing to find the best grouping for the # second part. best_score = 0 for i in range(1, len(bag)-count+1): score, groups = sticks(bag[i:], count-1) groups = [bag[:i]] + groups score = min(score, sum(bag[:i])) if score > best_score: best_score = score best = groups solutions[(len(bag), count)] = (best_score, best) return (best_score, best) sticks.guesses = 0 bag = random.choices(range(1, 101), k=20) score, groups = sticks(bag, 5) print('Groups', groups) print('Score', score, [sum(group) for group in groups]) print('Guesses', sticks.guesses, 'Solutions', len(solutions))I tried the same experiment with a bag of 50 numbers and 10 groups. This code makde 6,601 guesses, cached 376 partial solutions and ran in a little under a second. I disabled the cache and it made 2,054,455,634 and ran for an hour. The non-recursive solution I posted earlier solved it in a few milliseconds and one time only needed 7 guesses.