I'm bothered by my answer to this SO question.
I'm pretty sure it's more efficient than the sort-and-cull implementations, but I'm having trouble expressing that in a way that I trust.
Also, it's rather convoluted by python standards.
Is there a way to express the same process more clearly, without pages of comments?
The problem statement:
Given a subject list of strings, make a list containing every element of the subject that isn't a substring of a different element of the subject.
Original Current solution:
from itertools import groupby
from operator import itemgetter
from typing import Dict, Generator, Iterable, List, Union
# Exploded is a recursive data type representing a culled list of strings as a tree of character-by-character common prefixes. The leaves are the non-common suffixes.
Exploded = None
Exploded = Dict[str, Union[Exploded, str]]
def explode(subject:typing.Iterable[str])->Exploded:
heads_to_tails = dict()
for s in subject:
if s:
head = s[0]
tail = s[1:]
if head in heads_to_tails:
heads_to_tails[head].append(tail)
else:
heads_to_tails[head] = [tail]
return {
h: prune_or_follow(t)
for (h, t) in heads_to_tails.items()
}
def prune_or_follow(tails: List[str]) -> Union[Exploded, str]:
if 1 < len(tails):
return explode(tails)
else: #we just assume it's not empty.
return tails[0]
def implode(e: Exploded) -> Generator[str, None, None]:
for (head, continued) in e.items():
if isinstance(continued, str):
yield head + continued
else:
for tail in implode(continued):
yield head + tail
def cull(subject: List[str]) -> List[str]:
return list(implode(explode(subject)))
print(cull(['a','ab','ac','add']))
print(cull([ 'a boy ran' , 'green apples are worse' , 'a boy ran towards the mill' , ' this is another sentence ' , 'a boy ran towards the mill and fell']))
print(cull(['a', 'ab', 'ac', 'b', 'add']))
I know that it works for the two three test cases.
print(cull(['a', 'ab', 'ac', 'b', 'add']))
outputs['add', 'b']
.groupby()
does not sort it's input, so when the dictionary comprehension inexplode()
gets to 'add', it overwrites the entry for 'a' that was created when processing `['a', 'ab', 'ac']. \$\endgroup\$groupby
would sort, and why we'd care if it did. This isn't even the first time I've been hit by this. In absolute seriousness, who in hell publishes a function like that to a public library? \$\endgroup\$