Project Euler Solution 26

ek-euler-26.py

#!/usr/bin/env python

# solution to project euler problem #26
# https://projecteuler.net/problem=26

from decimal import *
import re

# manually crank up the significant digits until we hit the right answer
sig_dig = 10000

# return a string of length sig_dig representing the decimal portion of 1 / d
def decimal_rep(d, sig_dig):
  pattern = re.compile(r'^0\.(\d*)$')
  getcontext().prec = sig_dig
  dec = Decimal(1)/Decimal(d)
  matches = pattern.match(str(dec))
  if matches:
    return matches.group(1)
  else:
    return ""

# store a dictionary of the smallest cycle detected for each value of d
min_matches = {}
# store the largest cycle detected
max_match = 0

# loop for d < 1000
for d in range(1, 999):
  decimal_str = decimal_rep(d, sig_dig)
  if decimal_str == "":
    next
  # brute force search for cycles of length 2 - 2000
  # manually crank up this number until we hit the right answer
  for j in range(2,2000):
    # slice the string into sets and look for matches / cycles
    # this is reliant on small numbers b/c eventually this would detect a 'false positive' match
    # two sets of slices were chosen to reduce this likelihood, but it works with one...
    # call it a premature optimization
    if (decimal_str[0:j] == decimal_str[j:j+j]) and \
       (decimal_str[j+j:j+j+j] == decimal_str[j+j+j:j+j+j+j]):
      # store the first (smallest) match for each value of d
      # this effectively eliminates detection of smaller cycles within the larger cycles
      if not min_matches.has_key(str(d)):
        # store the smallest match for this value of d
        min_matches[str(d)] = j
        # store the overall largest match detected - this is the answer
        if (j > max_match):
          max_match = j

# loop through all matches to find the maximum
for key, val in min_matches.iteritems():
  # ding ding ding
  if val == max_match:
    print str(key) + " has match of length " + str(val)
    print decimal_rep(key, sig_dig)[0:val]
    print decimal_rep(key, sig_dig)[val:val+val]