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

by on May 11, 2012

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 # 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”