Project Euler P.259

• 연산의 정확도를 위해서 fractions.Fraction을 사용하면 수행시간이 오래걸림.

#!/usr/bin/env python
# 20101196798

import operator
import sys
from fractions import Fraction

operators = (operator.add, operator.sub, operator.mul, operator.div)
answer = set()

def concat(l):
  c = ''
  for n in l:
    c += str(n)
  return int(c)
    
def func():
  global answer
  for i in range(0, 2 ** 8):
    l = [1]
    digit = 2
    for j in range(0, 8):
      flag = (0 != i & (1 << (7-j)))
      if flag:
        tmp = l.pop()
        l.append(concat( [tmp, digit] ))
      else:
        l.append(digit)
      digit += 1
    print l
    l = map(lambda x: Fraction(x, 1), l)
    if len(l) > 1:
      calculate(l[:2], l[2:])
    else:
      answer.add(int(l[0]))
  print 'Answer: ', reduce(operator.add, answer)

def calculate(s, d):
  global answer
  global maximum
  if len(s) == 1 and len(d) == 0:
    if s[0] > 0 and (s[0].denominator == 1):
      answer.add(s[0])
    return

  if len(s) >= 2:
    a = s[-2]
    b = s[-1]
    for op in operators:
      try:
        c = op(a, b)
        calculate(s[:-2] + [c], d)
      except ZeroDivisionError, ex:
        continue

  if len(d) > 0:
    calculate(s + [d[0]], d[1:])

if __name__ == '__main__':
  func()