3
\$\begingroup\$

First I'm not sure what this is called formally but whatever.

Basically I need to form "wildcard buckets". I think the best way to explain what I need to do is to take an example. For instance, say I have the three words "aaa", "aab", and "baa".

Let me use * as the wildcard. Then from aaa I can form -aa, a-a, aa-, --a, a--, a-a, and ---. I then add these to a dictionary where the keys are the buckets and values are sets of (complete) words that fit these buckets. I repeat for all my words. So in the end I get that, for instance, -a- fits all three of the example words that I have above.

I have working code, but it is very slow in forming these buckets when I have a word list that has hundreds of thousands of words.

for numberSpaces in range(0, len(word) + 1):  # loop through all spaces of word
    buckets = itertools.combinations(range(0, len(word)), numberSpaces)
    for indicesToReplace in buckets:  # for each index in this combination
        newWord = word  
        for index in indicesToReplace:  # replace character with "*"
            newWord = newWord[0:index] + "*" + newWord[index + 1:]
        if newWord not in bucketDictionary.keys(): # Add to dictionary
            bucketDictionary[newWord] = set()
        bucketDictionary[newWord].add(word)

I would like to know how to best optimize this code. I've tried recursion but I'm not sure if that is any better than this iterative method.

Thank you!

\$\endgroup\$
4
\$\begingroup\$

I think the way to optimize it is to try an entirely different approach -- given a pattern that matches all the words in a set, and a new word to add to the set, how do you modify the pattern to match the new word as well? Simple answer: as long as the non-wild characters in the pattern match the new word, leave them; otherwise change the pattern to have a wildcard at that position. You could implement this either recursively or iteratively.

from typing import List

WILD = "*"

def build_common_pattern(words: List[str]) -> str:
    """Build a pattern matching all input words.
    WILD matches any single character."""
    pattern = words[0]
    for word in words:
        assert len(word) == len(pattern)
        for i in range(len(word)):
            assert word[i] != WILD
            if pattern[i] != word[i]:
                pattern = pattern[:i] + WILD + pattern[i+1:]
    return pattern

print(build_common_pattern(["aaa", "aab", "baa"]))

This is also a potential use case for functools.reduce:

def build_common_pattern(words: List[str]) -> str:
    """Build a pattern matching all input words.
    WILD matches any single character."""
    def union(a: str, b: str) -> str:
        result = ""
        assert len(a) == len(b)
        for i in range(len(a)):
            result += a[i] if a[i] == b[i] else WILD
        return result

    return reduce(union, words)
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Starting with the answer by @SamStafford, you could take this even further and make it a nice inheritance exercise by using a sub-class of str that compares true to any other character:

class WildCard(str):
    def __eq__(self, other):
        # all other strings are equal to the wildcard
        return isinstance(other, str)

STAR = WildCard("*")

def build_common_pattern(words):
    """Build a pattern matching all input words.
    WILD matches any single character."""
    pattern = list(words[0])
    for word in words:
        assert len(word) == len(pattern)
        pattern = [p if c == p else STAR for c, p in zip(word, pattern)]
    return "".join(pattern)

This way you avoid having to do many string slices, although this makes it only perform better for really large strings (patterns with each character having a 50% chance to be a wildcard and a length of more than 1k characters):

enter image description here


However, this does not solve the exact problem your code solves, since it does not build a dictionary mapping patterns to words that match it. For this I can only give you some stylistic advice on how to improve your code.

  • Python has an official style-guide, PEP8, which recommends lower_case for functions and variables.

  • You can use collections.defaultdict(set) to avoid having to check if you have seen a pattern before.

  • range starts by default at 0, and so do slices.

  • Use the same way I used above to avoid string slices and iterate over the word/pattern instead.

from collections import defaultdict
from itertools import combinations

def build_buckets(words):
    buckets_dict = defaultdict(set)
    for word in words:
        for number_spaces in range(len(word) + 1):  # loop through all spaces of word
            buckets = combinations(range(len(word)), number_spaces)
            for indices in map(set, buckets):  # for each index in this combination
                new_word = "".join(c if i not in indices else "*"
                                   for i, c in enumerate(word))
                buckets_dict[new_word].add(word)
    return buckets_dict

Note that this is probably a futile effort, since if there were no wordlist, the number of patterns grows exponentially. Since you do have a wordlist it does not, but the number of patterns will still increase rapidly. For 15 words of length 15, your code already takes almost 2 seconds.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.