Skip to content

Instantly share code, notes, and snippets.

@alexkay
Created April 16, 2013 20:34
Show Gist options
  • Save alexkay/5399420 to your computer and use it in GitHub Desktop.
Save alexkay/5399420 to your computer and use it in GitHub Desktop.
Thumbtack PyCon 2013 challenge
#!/usr/bin/env python
import collections
import itertools
import re
import sys
words = {
word
for word in re.split(r'\W+', sys.stdin.read().lower())
if len(word) >= 4
}
pairs = collections.defaultdict(list)
where = collections.defaultdict(set)
for a, b in itertools.combinations(words, 2):
key = ''.join(sorted(a + b))
if key not in where[a] and key not in where[b]:
pairs[key].append((a, b))
where[a].add(key)
where[b].add(key)
max_len = 0
for key in pairs:
if len(pairs[key]) > max_len:
max_len = len(pairs[key])
print max_len
for key in pairs:
if len(pairs[key]) == max_len:
print pairs[key]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment