euler_answer_md5_brute_force.py

"""Brute force as many md5-hashed Project Euler answers as possible.
"""

import re
import requests

from datetime import datetime, timedelta
from itertools import count, islice
from hashlib import md5

_HASH_ANSWER_SOURCE = 'http://kmkeen.com/local-euler/project_euler.txt'

def get_hashed_answers():
    """Downloads and extracts md5 hashed answers from _HASH_ANSWER_SOURCE."""
    response = requests.get(_HASH_ANSWER_SOURCE)

    if response.status_code != 200:
        return []

    return re.findall(r'Problem (\d+).*?Answer: ((?:[a-f]|\d){32})', response.text, re.S)

def md5sum(number):
    """Convenience function for generating the md5sum of an integer."""
    hash_builder = md5()
    hash_builder.update(str(number).encode('utf-8'))
    return hash_builder.hexdigest()

def brute_force(hashes, limit_in_seconds=60):
    """Brute force as many non-negative answers as possible."""
    limit = datetime.now() + timedelta(seconds=limit_in_seconds)

    results = []

    infinite_iterator = count(start=0, step=1)

    while limit > datetime.now():
        results.extend((n, md5sum(n))
                       for n in islice(infinite_iterator, 10000)
                       if md5sum(n) in hashes)

    return results

def main():
    questions_and_hashed_answers = get_hashed_answers()

    if len(questions_and_hashed_answers) <= 0:
        print('Failed to download hashed answers from {0}', _HashedAnswerSource)
        return

    questions_by_hash = dict((h, q) for q, h in questions_and_hashed_answers)
    hashes = [h for _, h in questions_and_hashed_answers]

    answers_and_hashes = brute_force(hashes)

    questions_and_answers = [(questions_by_hash[h], a) for a, h in answers_and_hashes]

    sorted_questions_and_answers = sorted(questions_and_answers, key=lambda q: int(q[0]))

    for question, answer in sorted_questions_and_answers:
        print('{0}: {1}'.format(question, answer))

    print('\n{0} results found.'.format(len(sorted_questions_and_answers)))

if __name__ == '__main__':
    main()