Given A List Of Words, How To Put Them Into "families"?

I'm creating an evil hangman game using python and I'm stuck. I'm trying to figure out how to put words into families. For example, suppose I have a list ALLY BETA COOL DEAL ELSE F

Solution 1:

from itertools import groupby

words = ['ALLY', 'BETA', 'COOL', 'DEAL', 'ELSE', 'FLEW', 'GOOD', 'HOPE', 'IBEX']
e_locs = sorted(([c == 'E'for c in w], i) for i, w inenumerate(words))
result = [[words[i] for x, i in g] for k, g in groupby(e_locs, lambda x: x[0])]

Result:

>>> result
[['ALLY', 'COOL', 'GOOD'], ['HOPE'], ['FLEW', 'IBEX'], ['BETA', 'DEAL'], ['ELSE']]

Here is a version that also keeps track of where the Es are:

words = ['ALLY', 'BETA', 'COOL', 'DEAL', 'ELSE', 'FLEW', 'GOOD', 'HOPE', 'IBEX']
result = {}
forwordin words:
    key = ' '.join('E'if c == 'E'else'-'forcin word)
    if key not in result:
        result[key] = []
    result[key].append(word)

Result:

>>> pprint.pprint(result)
{'- - - -': ['ALLY', 'COOL', 'GOOD'],
 '- - - E': ['HOPE'],
 '- - E -': ['FLEW', 'IBEX'],
 '- E - -': ['BETA', 'DEAL'],
 'E - - E': ['ELSE']}

To choose the biggest family (using the first version, where result is a list of lists):

>>> max(result, key=len)
['ALLY', 'COOL', 'GOOD']

To choose the biggest family using the second version you can just use result.values() instead of result, or to get a tuple with the E locations and the family you could use the following:

>>> max(result.items(), key=lambda k_v: len(k_v[1]))
('- - - -', ['ALLY', 'COOL', 'GOOD'])

Solution 2:

In [1]: from itertools import groupby

In [2]: import string

In [3]: words = "ALLY BETA COOL DEAL ELSE FLEW GOOD HOPE IBEX".split()

In [4]: table = string.maketrans('ABCDEFGHIJKLMNOPQRSTUVWXYZ',
   ...:                          '????E?????????????????????')

In [5]: f = lambda w: w.translate(table)

In [6]: for k,g in groupby(sorted(words, key=f), f):
   ...:     print k, list(g)
   ...:     
???? ['ALLY', 'COOL', 'GOOD']
???E ['HOPE']
??E? ['FLEW', 'IBEX']
?E?? ['BETA', 'DEAL']
E??E ['ELSE']

# to get the biggest group
In [7]: max((list(g) for _,g in groupby(sorted(words, key=f), f)), key=len)
Out[7]: ['ALLY', 'COOL', 'GOOD']

Solution 3:

Using regular exprssions you could do something like this:

import re

definto_families(words):
    # here you could add as many families as you want
    families = {
                '....': re.compile('[^E]{4}'),
                '...E': re.compile('[^E]{3}E'),
                '..E.': re.compile('[^E]{2}E[^E]'),
                '.E..': re.compile('[^E]E[^E]{2}'),
                'E..E': re.compile('E[^E]{2}E'),
    }
    returndict((k, [w for w in words if r.match(w)]) for k, r in families.items())

Or if you want to create the regular expressions dynamically:

def into_families(words):
    family_names = set(''.join('E' if x == 'E' else '.' for x in w) for w in words)
    families = dict((x, re.compile(x.replace('.', '[^E]'))) for x in family_names)
    return dict((k, [w for w in words if r.match(w)]) for k, r in families.items())

Solution 4:

from collections import defaultdict
import re

words = 'ALLY BETA COOL DEAL ELSE FLEW GOOD HOPE IBEX'.split()

groups = defaultdict(list)

for word in words:
    indices = tuple(m.start() for m in re.finditer('E', word))
    groups[indices].append(word)

for k, v insorted(groups.items()):
    tpl = ['E'if i in k else'-'for i inrange(4)]
    print' '.join(tpl), ' '.join(v)