Countdown number game solver

Question

I haven't a clue whether this works for every case, but it has in the ones I tried. If there are any optimizations that could happen anywhere please do comment on it. Regarding my code style, I'm sure there's something to fix there.

In this game you are given a set of numbers and a target. You need to reach the target using only the given numbers and the operators (\$ + \$, \$ - \$, \$ / \$, \$ \times \$). You cannot use any number more than once, but every operator can be used as many times as necessary. You do not need to use every number/operator.

import itertools
target = 225
numbers = [25, 1, 9, 9, 4, 2]
math_functions = "+-/*"
solution = None
def generate_number_permutations(numbers, length):
 return list(itertools.permutations(numbers, length))
def generate_function_permutations(length):
 return list(itertools.product(math_functions, repeat=length))
for x in range(len(numbers)):
 number_permutations = generate_number_permutations(numbers, x+1)
 function_permutations = generate_function_permutations(x)
 if x == 0:
 for y in number_permutations:
 if y[0] == target:
 solution = y[0]
 break
 else:
 continue
 for permutation in number_permutations:
 for functions in function_permutations:
 value = permutation[0]
 for function in enumerate(functions):
 if function[1] == "+":
 value += permutation[function[0]+1]
 elif function[1] == "-":
 value -= permutation[function[0]+1]
 elif function[1] == "/":
 value /= permutation[function[0]+1]
 else:
 value *= permutation[function[0]+1]
 if value == target:
 solution = permutation, functions
 break
 else:
 continue
 break
 
 if solution is not None:
 break
print(solution)

• user228914: Can you elaborate in the question body on what the program does?
• El-Chief: @AryanParekh added
• user228914: To be 100% honest, the thing is it's difficult to write optimization tactics for this program without changing the logic a LOT.
• superb rain: Fails solving for example target = 2; numbers = [3, 4, 14].

Answer 1

Globals

Since target, numbers and math_functions are global constants, they should be all-caps - e.g. TARGET. That said, you should refactor this so that the target and numbers are parametric, so that they can (eventually) be randomly generated.

Solution does not belong as a global, since it is mutable - its presence prevents your program from being re-entrant.

Likewise, the globally-scoped code starting with for x should be moved into a function.

Use of operators

This falls into the category of "code as data". This block:

 if function[1] == "+":
 value += permutation[function[0]+1]
 elif function[1] == "-":
 value -= permutation[function[0]+1]
 elif function[1] == "/":
 value /= permutation[function[0]+1]
 else:
 value *= permutation[function[0]+1]

can be greatly simplified if you change your math_functions to be a tuple (or maybe dictionary) of character-operator pairs, where you import your operators from https://docs.python.org/3/library/operator.html .

Answer 2

Operators

This is just to add on to @Reinderien answer. You can create a function, pass in the values you want to operate on and the operator you want to use, and return the calculation of those two numbers.

def perform_operator(op: str, a: int, b: int) -> int:
 return { "+": a + b, "-": a - b, "*": a * b, "/": a / b }[op]

Here's how you would use this function

...
for function in enumerate(functions):
 value = perform_operator(function[1], value, permutation[function[0] + 1])
if value == target:
 solution = permutation, functions
 break
...

• Reinderien: For this case the dictionary approach is fine, since the expressions are cheap. It doesn't scale, though, because it requires that every single possible expression is evaluated and then only one returned.