CODEWITHSUNDEEP
pythonalgorithm
J. Doe
J. Doe

Reputation: 1419

Closest to a number from user inputs

So I wanted to know if it was possible to take 3 numbers from the user all ranging from 1-6 and take 1 more input from the user ranging from 1 - 144 and make a program that takes the first 3 numbers you got and finds a way using addition, subtraction, multiplication, division, roots, and powers to find a way, using the 3 numbers, to get the 4th user input. If you can't get the 4th user input find the closest that you can get to it from the first 3 inputs.Then the program should tell you the operations it used and which numbers it used it on. This is basically recreating the game ThinkFun Math Dice.

For example: If the first 3 numbers the user inuts are 5, 2, and 9 and the 4th number is 86, the program should do 9^2 which is 81 and 81+5 which is 86. In another case if the 3 numbers are 6, 4, and 2 and the the final answer is(4th input)24, the program should do 6*4 -2 or 6*4 +2 or 4^2+6 since these all equal to 26 or 22 and there is no possible solution to get 24.

Upvotes: 0

Views: 239

Answers (2)

Dillon Davis
Dillon Davis

Reputation: 7740

While btilly's answer is absolutely correct, it is a bit more than what's needed for this problem, at least in python. Using the itertools library and the eval() function, you can get by with a much shorter and simpler approach. Do note that eval() and exec() are considered insecure, since they will execute anything passed, however as a script for personal use it should be fine. Any malicious code would probably trip an exception casting the inputs to ints anyways. from itertools import permutations

coeffs = list(map(int, input("Coefficents, separated by spaces:\n").split()))
target = int(input("Target value:\n"))

operators = ["({}+{})","({}-{})","({}*{})","({}/{})","({}**{})","({}**(1.0/{}))"]

def make_expr(expr, coeffs, target):
    if not coeffs:
        try:
            return eval(expr), expr
        except OverflowError:
            return None
        except ArithmeticError:
            return None

    solutions =  [make_expr(op.format(expr, coeffs[0]), coeffs[1:], target) for op in operators]
    solutions += [make_expr(op.format(coeffs[0], expr), coeffs[1:], target) for op in operators]
    solutions = [x for x in solutions if x is not None]
    val, expr = min(solutions, key=lambda x: abs(x[0]-target))
    return val, expr

def find_best(coeffs, target):
    assert(len(coeffs) > 1)
    solutions = [make_expr(perm[0], perm[1:], target) for perm in permutations(coeffs)]
    solutions = [x for x in solutions if x is not None]
    val, expr = min(solutions, key=lambda x: abs(x[0]-target))
    return "Closest value: {0}\nExpression: {1}".format(val, expr)

print(find_best(coeffs, target))

To support more operators, just insert them into the list, with {}'s where the arguments go, and surrounded by paretheses. I've added support for extra operators, however since I do not shortcut the iteration when it finds a perfect solution, it can take a very long time for 3+ operators.

Upvotes: 1

btilly
btilly

Reputation: 46389

The heart of the problem is to decide what format to use to write out the possible calculations, list them, try each one, and select the best.

I'm going to suggest RPN notation because it is simple to work with. I've given you the code to list possible calculations in RPN notation. You still need to do IO and write an RPN calculator. IO is easy. There are lots of examples of RPN calculators online that you can study.

def list_perms (args):
    if 0 == len(args):
        yield []
    else:
        x = args[0]
        for p in list_perms(args[1:]):
            for i in range(0, len(p)+1):
                yield p[:i] + [x] + p[i:]


def list_rpn (x, y, z):
    ops = ['+', '-', '*', '/', '^', 'r']
    for p in list_perms([x, y, z]):
        for op1 in ops:
            for op2 in ops:
                yield p + [op1, op2]
                yield p[0:2] + [op1, p[2], op2]

def evaluate (calc):
    return 'you have to figure this out'

def find_best (x, y, z, r):
    best_val = x+y+z
    best_calc = [x, y, z, '+', '+']
    for calc in list_rpn(5, 6, 8):
        try:
            val = evaluate(calc)
            if val == r:
                return calc
            elif abs(val - r) < abs(best_val - r): 
                best_val = val
                best_calc = calc
        except Exception:
            # Throw exceptions on things like divide by 0, or powers of
            # negative numbers that aren't n or 1/n where n is an odd number
            pass

    return best_calc

# You should also do proper IO here.
print(find_best(5, 2, 9, 24))

Upvotes: 1

Related Questions