CODEWITHSUNDEEP
pythonpermutation
TMrtSmith
TMrtSmith

Reputation: 471

Combination of lists with a specific sum

I want to solve this problem using python:

Take the digits 1,2,3 up to 9 in numerical order and put either a plus sign or a minus sign or neither between the digits to make a sum that adds up to 100. For example, one way of achieving this is: 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100, which uses six plusses and minuses. What is the fewest number of plusses and minuses you need to do this?

I thought about starting by generating valid tuples, e.g. (1,2,34,567,89), and then working out which ones add up to 100, and then finding the shortest.

To do this, I started by created a list of the possible digits, tens and hundreds since I'm pretty sure there are no combinations with 4-digit numbers.

strnumbers = [str(x) for x in range(1,10)]
digits = [int(i) for i in strnumbers]
tens = [int(strnumbers[a] + strnumbers[a+1]) for a in range(8)]
hundreds = [int(strnumbers[a] + strnumbers[a+1] + strnumbers[a+2]) for a in range(7)]

However, I'm not sure how to create the actual possible lists.

My question is two-fold:

  1. How would you create the possible tuples, using digits tens and hundreds?

  2. Is this a reasonable approach in terms of calculations? It feels like I'm creating a lot of extra work

Upvotes: 1

Views: 318

Answers (3)

Rory Daulton
Rory Daulton

Reputation: 22564

Here is one approach, which I used for a similar problem. You did not show enough code for me to show my complete solution, so this is an outline of ideas. This approach differs from yours but you need not worry about the number of digits of each term.

  1. You want the digits in order with some other characters between them, so consider the string '1{}2{}3{}4{}5{}6{}7{}8{}9'.
  2. Use itertools.product() to get all possible ways of filling up those braces with '+', '-', or ''. You need eight of those short strings. The total number of products will be 3**8 == 6561 which is a small number for a Python program.
  3. For each possible product, create a full expression by using the format() method of the string on the product.
  4. Use eval() to calculate the value of that expression. Using eval() is often dangerous, but since you are using it only on strings that you have constructed there is no problem.
  5. Compare the value to 100 and store the strings that result in that value.
  6. When all the strings are collected, find the one with the shortest length. That one will have the fewest plusses and minuses.
  7. Subtract 9, the number of digits, from that shortest length, print it, and you are done.

Steps 5 through 7 can be combined, reducing memory usage. Using the product as a generator and looping over it, not making a list from it, also keeps memory usage down.

Upvotes: 2

Błotosmętek
Błotosmętek

Reputation: 12927

import itertools

results = []
for opers in itertools.product(('-','+',''),repeat=8):
    expression = '1{}2{}3{}4{}5{}6{}7{}8{}9'.format(*opers)
    result = eval(expression)
    if result == 100:
        results.append(expression)
best_result = min(results, key=len)
print(best_result, len(best_result)-9)

Upvotes: 3

javidcf
javidcf

Reputation: 59741

I would approach this problem differently. You have your list of digits:

digits = [1, 2, 3, 4, 5, 6, 7, 8, 9]

Therefore, you have to take 8 decisions for how to join the digits (or 9, if it is allowed to put a minus before 1, but I'll consider it is not here). For each of these decisions you have three choices: plus, minus or neither (join). Hence there are 3^8 choices. I would just iterate them to find the best one:

from itertools import product

digits = [1, 2, 3, 4, 5, 6, 7, 8, 9]
options = ["", "+", "-"]
number = 100
best_sol_str = ""
best_sol_cost = 10  # Or infinity
for sol in product(*([options] * 8)):  # `* 9` if starting with "-" allowed
    factor = 1
    current = 0
    total = 0
    sol_cost = 0
    sol_str = ""
    # Remove `("",) + ` if used `* 9` before
    for opt, d in zip(("",) + sol, digits):  
        sol_str += opt + str(d)
        if opt == "":
            current = current * 10 + d
        else:
            total += factor * current
            current = d
            sol_cost += 1
            if opt == "+":
                factor = 1
            elif opt == "-":
                factor = -1
    total += factor * current
    if total == number and sol_cost < best_sol_cost:
        best_sol_str = sol_str
        best_sol_cost = sol_cost

print("Best solution: {}={} ({} operations).".format(
    best_sol_str, number, best_sol_cost))

Upvotes: 1

Related Questions