Project Euler 93: Using four distinct digits and the rules of arithmetic, find the longest sequence of target numbers.

I finished Project Euler 93 this morning.

I enjoyed reading Kristian’s blueprint to the problem at Mathblog, and I emulated his approach in generating all the brute force combinations of digits a

Rather then writing code for the mathematical operators +,-,*,/ and figuring out how to write the priority of mathematical operators (i.e. scan from left to right, do operators within parentheses first, and do *,/ before doing +,-), I ended up mostly doing string operations and then sending the resulting string directly to the Python operator using the eval() function.

You have to be careful of the DIV/#0 error, so you have to write an exception handler for that error.

Also, you have to be careful because in python, all of the numbers are initially handled as integers, so when dividing, i.e. 4/3, Python will give you the result 1. So when dealing with division, you have to convert the numbers to float first, to get Python to return 4/3 = 1.3333.

Finally - we keep track of the maximum N and the combination that yields that maximum N.

Solution took 100 seconds, so it did violate the 1 minute rule for Project Euler. Oh well!

# euler 93
import time
t0 = time.time()

import itertools

temp = itertools.combinations(’0123456789′,4)
c = []
for i in temp:
    j = [x for x in i]
    c.append(j)

op = [i for i in itertools.product('+-*/',repeat=3)]

def calc(c, op):
    temp = c[0] + op[0] + c[1] + op[1] + c[2] + op[2] + c[3]
    return temp

## use string operations to insert parentheses

def insParenth(s):  #takes a+b+c+d
    a = s[:]
    b = s[:2] + ‘(‘ + s[2:5] + ‘)’ + s[5:]  # a + (b+c) + d
    c = s[:4] + ‘(‘ + s[4:7] + ‘)’ # a+b+(c+d)
    d = s[:2] + ‘(‘ + s[2:7] + ‘)’   # a+(b+c+d)
    e = ‘(‘ + s[:3] + ‘)’ + s[3] + ‘(‘ + s[4:7] + ‘)’  #(a+b)+(c+d)
    return [a,b,c,d,e]

def convToFloat(st):  #if there is a divide operation, we need to convert to floating
    if ‘/’ in st:
        output = ”
        for i in st:
            if i in ’0123456789′:
                output += ‘float(‘ + i + ‘)’
            else:
                output += i
        return output
    else:
        return st

def evalP(par):
    output = []
    for a in par:
        try:
            output.append(eval(a))
        except ZeroDivisionError:
            output.append(None)
    return output

largestSoFar = 0

for i in c:  #unique combinations of a= 1:
                    test.add(k)
                elif type(k) == float:
                    if int(k) !=0:
                        if k % int(k) == 0 and k >= 1:
                            test.add(int(k))
##    print i, test
    startNum = 1
    while startNum in test:
        startNum += 1
##    print “the first number not in the set is “, startNum
    mn = startNum – 1
##    print “the max number is “, mn
    if mn > largestSoFar:
        largestSoFar = mn
        answer = i
        print “the largest N so far is “, largestSoFar
        print “the answer so far is “, answer
        print “”

t1 = time.time()
print t1-t0, “seconds”