CODEWITHSUNDEEP
pythonpython-3.x
Scott Severance
Scott Severance

Reputation: 953

Make this function take strings of arbitrary length

This function takes a string of digits and a target integer and prints all possible ways to insert operators to reach the desired target. The output must in all cases contain all the digits in order; none may be omitted.

#!/usr/bin/env python3

def find_expressions(digits, target):
    if not (isinstance(digits, str) or isinstance(digits, list)) or not isinstance(target, int):
        raise TypeError
    if len(digits) != 5:
        raise TypeError('digits must be of length 5')
    solutions = []
    operators = ('', ' + ', ' - ', ' * ', ' / ')
    for i in operators:
        for j in operators:
            for k in operators:
                for l in operators:
                    s = digits[0] + i + digits[1] + j + digits[2] + k + digits[3] + l + digits[4]
                    try:
                        if eval(s) == target:
                            solutions.append(s + ' == {}'.format(target))
                    except (ZeroDivisionError, SyntaxError):
                        pass
    print('\n'.join(solutions))

It isn't pretty, but it works. The problem is that it only takes strings of length 5. How can I make it take strings of arbitrary length? (E.g., calling find_expressions('12345678', 2) should be valid.) I'm thinking I need to replace the for loops with recursion, but I'm at a loss as to how to accomplish this.

Example Output

Calling find_expressions('75228', 5) prints:

7 + 5 + 2 / 2 - 8 == 5
7 * 5 - 22 - 8 == 5
7 * 5 - 2 - 28 == 5

Caveat

I'm not satisfied with the whole brute-force approach I'm taking by looping over every possibility. If there's a better algorithm overall, I'd like to hear about it. However, this question is about making this function take arbitrary-length input while making the smallest possible changes.

Upvotes: 1

Views: 136

Answers (2)

phihag
phihag

Reputation: 287815

Use itertools.product:

import itertools

def find_expressions(digits, target):
    if not (isinstance(digits, str) or isinstance(digits, list)) or not isinstance(target, int):
        raise TypeError

    solutions = []
    operators = ('', ' + ', ' - ', ' * ', ' / ')
    for ops in itertools.product(operators, repeat=len(digits)-1):
        s = digits[0] + ''.join(op + digit for op, digit in zip(ops, digits[1:]))
        try:
            if eval(s) == target:
                solutions.append(s + ' == {}'.format(target))
        except (ZeroDivisionError, SyntaxError):
            pass
    print('\n'.join(solutions))

Upvotes: 5

Jongware
Jongware

Reputation: 22457

The trick is to get all possible permutations of the sequence +-*/ – including duplicates, so the first sequence needs to be ++++; its length should be len(digits)-1, because for n digits, you need n - 1 operators in between.

The total number of permutations is operators ** positions; that is, every operator can appear in every single position. I don't see any handy shortcut for not actually testing all possibilities.

The following is loosely based on Get all 4-character combinations of a given alphabet; without the interjection of the digits and with the # print .. lines enabled, you will see it shows the entire list.

If your input may or may not be strings, use str(digits[x]) so the string concatenation does not barf.

The following code

def find_expressions(digits, target):
    if not (isinstance(digits, str) or isinstance(digits, list)) or not isinstance(target, int):
        raise TypeError
    solutions = []
    operators = ('', ' + ', ' - ', ' * ', ' / ')
    used = [0] * (len(digits)-1)
    for i in range(len(operators)**(len(digits)-1)):
      attempt = str(digits[0])
      for j in range(1,len(digits)):
        attempt += operators[used[j-1]] + str(digits[j])
        # print (operators[used[j-1]], end="")
      # print ()
      for j in range(len(digits)-1):
        used[j] += 1
        if used[j] >= len(operators):
          used[j] = 0
        else:
          break

      try:
        if eval(attempt) == target:
          print (attempt, '==', eval(attempt))
      except (ZeroDivisionError, SyntaxError):
        pass

find_expressions ([7,5,2,2,8], 5)

shows

7 * 5 - 2 - 28 == 5
7 * 5 - 22 - 8 == 5
7 + 5 + 2 / 2 - 8 == 5.0

(where the last one prints as float because the / makes it so).

Upvotes: 1

Related Questions