import re cache = {0:"<()>"} def complement(character): dict = {"(":")","{":"}","<":">","[":"]",")":"(","}":"{",">":"<","]":"["} return dict[character] def findMatch(snippet, index): increment = 1 if snippet[index] in "({<[" else -1 stack = [] if snippet[index] in "(){}<>[]": stack.append(snippet[index]) while len(stack) > 0 and index + increment < len(snippet): index += increment if snippet[index] in "(){}<>[]": if complement(snippet[index]) == stack[-1]: stack = stack[:-1] else: stack.append(snippet[index]) return index def isTriangular(n): #Triangles must be between sqrt(2n) and cbrt(2n) if n < 0: return isTriangular(-n) for x in range(int((2*n)**(1/3.)),int((2*n)**.5)+1): if (x**2+x) == 2*n: return True return False def getTriangle(n): if n < 0: return -getTriangle(-n) #Triangles must be between sqrt(2n) and cbrt(2n) for x in range(int((2*n)**(1/3.)),int((2*n)**.5)+1): if (x**2+x) == 2*n: return x #If we don't find one we made a mistake assert False def getPolygon(n): sides = 1 while sides < n: acc = 1 size = 1 while acc <= n: if acc == n: return (sides, size) acc += size * sides size += 1 sides += 1 def isPrime(n): return not [0 for x in range(2,int(n**.5)+1) if n%x==0] and n>1 def getPrimeFactors(n): return [x for x in range(2,n/2) if n%x==0 and isPrime(x)] def divHardcode(n,m): assert n%m == 0 return "("*(m-1)+getBF(n/m)+")"*(m-1)+"{}"*(m-1) def getSimpleBF(n): if n in cache:return cache[n] if n < 0: # There is room for better solutions here return "["+getSimpleBF(-n)+"]" elif n == 0: return "" elif n < 6: return "()"*n else: #Non-edge cases solutions = [] if n >= 78 and isTriangular(n): solutions.append( min(["("+getBF(getTriangle(n))+"){({}[()])}{}","<("+getBF(getTriangle(n)+1)+")>{({}[()])}{}"],key=len) ) # The second try used to be more useful but now it seems like vesigial code # I should look into whether or not it actually improves anything significantly # There are 655 values in the first 10000 that are improved by this code # That makes a rate of 0.7% if isPrime(n): return getSimpleBF(n-1) + "()" else: #TODO multithread factors = getPrimeFactors(n) solutions += map(lambda m:divHardcode(n,m),factors) return min(solutions,key=len) def getBF(n): global cache if n in cache: return cache[n] result = getSimpleBF(n) index = n - 1 while index > n-(len(result)/2): score = getSimpleBF(index)+getSimpleBF(n-index) if len(score) < len(result):result = score index -= 1 index = n + 1 while index < n+(len(result)/2): score = getSimpleBF(index)+getSimpleBF(n-index) if len(score) < len(result):result = score index += 1 cache[n] = result return result def unpack(string): reMatch = re.match("\(*<",string) if reMatch: location =reMatch.span() return string[location[1]:findMatch(string,location[1]-1)] +string[:location[1]-1] + string[findMatch(string,location[1]-1)+1:] return string def push(n): return unpack("("+getBF(n)+")") def Triangle(n):return n**2+n print map(lambda x:push(ord(x)),'++*2J*4\++j"[]"+\-j"><"J">.'[::-1])