Improving a "Four Fours" puzzle solver

Question

import itertools
import math
import time
from time import time
from math import factorial
from math import sqrt


def pretty(string):
    string=string.replace("(4)","4")
    string=string.replace("factorial4","factorial(4)")
    string=string.replace("sqrt4","sqrt(4)")
    return string


def test(n):
start=time()
fails=0
for i in range(0,n+1):
    if(fours(i))!=None:
        print(fours(i))
    else:
        print("Failed: "+str(i))
        fails+=1
return("\nFailed "+str(fails)+" out of "+str(n)+"\n\nTotal time: "+str(time()-start)[:4]+"\nAverage time: "+str((time()-start)/n)[:4])

def fours(goal):
    operators = ['-','/','+','*','sqrt','^','factorial',"."]
    brackets = ["{0}{1}{0}{2}{0}{3}{0}",
                "({0}{1}{0}){2}{0}{3}{0}",
                "({0}{1}{0}{2}{0}){3}{0}",
                "({0}{1}({0}{2}{0})){3}{0}",
                "(({0}{1}{0}){2}{0}){3}{0}",
                "{0}{1}({0}{2}({0}{3}{0}))",
                "{0}{1}(({0}{2}{0}){3}{0})",
                "({0}{1}{0}){2}({0}{3}{0})"]
    for combination in itertools.product(operators, repeat=3):
        for bracket in brackets:
            try:
                formula = bracket.format("(4)", *combination).replace(".(4","(.4")
            except ValueError:
                pass
            try:
                if eval(formula)==goal:
                    return(pretty((formula + " = " + str(int(eval(formula))))))
            except:
                pass

print(test(20))

Here is the code for a solver for the "Four Fours" puzzle.http://en.wikipedia.org/wiki/Four_fours

It basically work, but the problem is that it can only use the + - / * operators, because it can't have two operators in a row(Solutions like this (4-4)/4+factorial(4) aren't allowed because of this "+factorial" part).What I could do(but would be to slow) would be to make pairings like this. ['-', '/', '+', '*', '-sqrt', '-^', '-factorial', '-.', '/sqrt', '/^', '/factorial', '/.', '+sqrt', '+^', '+factorial', '+.', 'sqrt', '^', 'factorial', '.']

This is far too many operators.

What I would like to do, would be to try something like this

formula = bracket.format(["(4)","(4*)","(4-)","(4/)"], *combination).replace(".(4","(.4")

Except this syntax is invalid.

How can I do this?

Or if you have better ideas(which I'm sure some of you do) I am open to suggestions.

Answer 1

You could try converting it into pre or post-fix. You can allow it to use ['!','sqrt','.'] anytime. '^' would only be used if at least one four is still available to be pushed on the stack. And ['+','-','/','*'] would only be pushed if there are more operators than numbers (or something like that).