Reputation: 471
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:
How would you create the possible tuples, using digits tens and hundreds?
Is this a reasonable approach in terms of calculations? It feels like I'm creating a lot of extra work
Upvotes: 1
Views: 318
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{}2{}3{}4{}5{}6{}7{}8{}9'
.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.format()
method of the string on the product.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.100
and store the strings that result in that value.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
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
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