#!/usr/bin/env python
# problem4.py - My solution to Puzzle 4 of the Google Treasure Hunt 2008.
#
# @author   Alan Saqui <alan.saqui@gmail.com>

import re

# Find all sums of sum_len consecutive primes that are in match_list.
# prime_list is the master list of prime numbers
def find_primes_sums(prime_list, match_list, sum_len):
    num_primes = len(primes)
    beg_idx = 0
    end_idx = sum_len
    candidates = []
    sum_limit = match_list[-1]
    subsum = sum([primes[i] for i in range(beg_idx, end_idx)])
    while end_idx != num_primes:
        if subsum > sum_limit:
            return candidates
        if subsum in match_list:
            candidates.append(subsum)
        # Speed up the summation by using a 'sliding window'
        subsum -= prime_list[beg_idx]
        beg_idx += 1
        subsum += prime_list[end_idx]
        end_idx += 1
    return candidates

# Load a list of prime numbers. The list used here came from  
# http://primes.utm.edu/lists/small/millions/primes1.zip
def load_prime_list():
    f = open('primes1.txt', 'r')
    primes = []
    # Cheating a little here. Full list of 1000000 primes took too long to sift
    # through, so I just tried 100000, 200000, 300000, until I found a limit
    # that gave me an answer ;-)
    limit = 700000
    for line in f:
        # Strip out lines that don't start with a number.
        if re.match('^\s+\d+', line) == None:
            continue
        line = line.strip()
        sublist = re.split('\s+', line)
        sublist = [int(num.strip()) for num in sublist]
        primes.extend(sublist)
        if len(primes) >= limit:
            break
    return primes

print "Loading primes list... "
primes = load_prime_list()

sum_lens = [723, 19, 17, 3]
# First match list is the list of primes
match_list = primes
for sum_len in sum_lens:
    print "Finding matches for sum length %d..." % (sum_len)
    match_list = find_primes_sums(primes, match_list, sum_len)
    if match_list == []:
        print "No matches found sum length %d." % (sum_len)
        break
    print "%d matches found for sum length %d." % (len(match_list), sum_len)
else:
    print "Answer found: %s" % (match_list[0])