Skip to content

Instantly share code, notes, and snippets.

@adrian17 adrian17/main.py
Created Aug 24, 2016

Embed
What would you like to do?
Python implementation of anagram solver
from collections import defaultdict
import string
words = open("enable1.txt").read().splitlines()
print(max(len(x) for x in words))
def add(a, b):
return tuple(x+y for x, y in zip(a, b))
def over(a, b):
return any(x>y for x, y in zip(a, b))
def counts(word):
count = [0]*27
for c in word.lower():
if not c.islower():
continue
count[ord(c)-ord('a')] += 1
return tuple(count)
anagrams = defaultdict(list)
by_len = defaultdict(list)
for word in words:
if len(word) <= 3:
continue
count = counts(word)
anagrams[count].append(word)
by_len[sum(count)].append(count)
def print_all(sentence, sofar):
if not sentence:
print(' '.join(sofar))
return
for word in anagrams[sentence[0]]:
print_all(sentence[1:], sofar + [word])
def recurse(target, left, curr, sentence):
if curr == target:
print_all(sentence, [])
return
for n in range(left, 0, -1):
for count in by_len[n]:
new = add(curr, count)
if over(new, target):
continue
recurse(target, left-n, new, sentence + [count])
req = 'Help, someone stole my purse'
count = counts(req)
from datetime import datetime
a = datetime.now()
recurse(count, sum(count), tuple([0]*27), [])
b = datetime.now()
print(b-a)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.