3
\$\begingroup\$

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)
\$\endgroup\$
4
  • \$\begingroup\$ Can you elaborate in the question body on what the program does? \$\endgroup\$
    – user228914
    Oct 8, 2020 at 15:32
  • \$\begingroup\$ @AryanParekh added \$\endgroup\$
    – El-Chief
    Oct 8, 2020 at 15:38
  • \$\begingroup\$ To be 100% honest, the thing is it's difficult to write optimization tactics for this program without changing the logic a LOT. \$\endgroup\$
    – user228914
    Oct 8, 2020 at 18:05
  • 4
    \$\begingroup\$ Fails solving for example target = 2; numbers = [3, 4, 14]. \$\endgroup\$ Oct 8, 2020 at 20:54

2 Answers 2

3
\$\begingroup\$

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 .

\$\endgroup\$
0
0
\$\begingroup\$

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
...
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – Reinderien
    Oct 9, 2020 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.