This code solves a challenge problem that a local company is hosting to attract/screen applicants. The link to the challenge is here.
In brief, we are given a wordlist containing approximately 100,000 words and we are asked to find the combination of words which has MD5 hash
4624d200580677270a54ccff86b9610e. The constraint is that the correct phrase will be an anagram of "poultry outwits ants".
The code begins by first removing all words with wrong letters or too many of the right letters from the list. Then a recursive function is called to search through combinations of up to 3 words, check if the letter counts match the desired phrase, and then hash and compare to see if the correct phrase has been found.
This was my first python project and I'd be very interested in feedback on both the algorithm and my usage of the language. I'm a new programmer who is just starting out in tech (mathematics background) and need all the feedback/criticism I can get to learn fast.
# -*- coding: utf-8 -*- # md5 of our target: 4624d200580677270a54ccff86b9610e # This code ran in 48.6 seconds on a 2.5Ghz i7 Macbook Pro OSX 10.10.5 # set recursive depth to limit the length of the word combo we check. # change this if a different depth is desired: depth = 3 # import useful things from datetime import datetime startTime = datetime.now() from collections import defaultdict, deque import hashlib import itertools import sys # load words mySet = set(open('wordlist.txt')) mySet = set(map(lambda s: s.strip(), mySet)) # initialize check as our dictionary with letter counts to check against check = defaultdict(int) letterString = 'poouulttttrywissan' for letter in letterString: check[letter] += 1 # strip out words from mySet that have the wrong letters goodLetters = str('poultrywisan') newset = set() for word in mySet: for letter in word: if letter not in goodLetters: newset.add(word) break mySet.difference_update(newset) # strip out words from mySet that have too many of the right letters newset.clear() for word in mySet: c = defaultdict(int) for letter in word: c[letter] += 1 for letter in goodLetters: if c[letter] > check[letter]: newset.add(word) break mySet.difference_update(newset) # define list to iterate over, sort, and reorder to make search most efficient newList = list(mySet) newList.sort(lambda x,y: cmp(len(x), len(y))) newList.reverse() # put the likely words containing between 4 and 7 letters up front so we check combos of them first countLow = 0 countHigh = 0 for word in newList: if len(word) > 3: countLow += 1 if len(word) > 7: countHigh += 1 newList = newList[countHigh : countLow] + newList[: countHigh] + newList[countLow :] # main recursive function. def recurseHash(combo, counts): for elem in newList: if elem in combo: continue else: # update counts for letter in elem: counts[letter] += 1 # set flags to tell if our combo has not enough, or too many, of any letter lessFlag = 0 greaterFlag = 0 for letter in check: if counts[letter] < check[letter]: lessFlag = 1 elif counts[letter] > check[letter]: greaterFlag = 1 # check flags and either hash combo, call recurseHash again, or do nothing if greaterFlag == 0: combo.append(elem) if lessFlag == 0: if hashlib.md5(" ".join(combo)).hexdigest() == '4624d200580677270a54ccff86b9610e': print "Success: ", " ".join(combo) print datetime.now() - startTime sys.exit(0) elif len(combo) < depth: recurseHash(combo, counts) combo.remove(elem) # remove letters from counts for letter in elem: counts[letter] -= 1 recurseHash(deque(), defaultdict(int))