3
\$\begingroup\$

I trying to figure out the most effective way to accomplish this task:

A function, check(), contains a list of strings. Calling the function with a string as argument, will return True if the argument string is part of any of the strings in the list. False if not.

I want to guess the content of that list in as few checks as possible, using the check() function, knowing only the charset (alphanumeric + -_@.[space]) and displaying the progress (I'm using tqdm).

My code does accomplish this, but it is very inefficient. For example if "strings" is in the list, it performs checks for both "tring", "string" and "trings", which I feel like could be optimized.

Here's my code:

import string
from tqdm import tqdm


def check(text):
    """Returns True if input text is part of any of the strings in the list"""
    strings = ["we ", "_want", "t0", "gu@ess", "these-", "str1ngs"]
    return any(text in substring for substring in strings)


def remove_partials(input_list):
    """Removes strings from the input list they are a substring of any other string in the list"""
    substrings = []
    for item in input_list:
        for item_2 in input_list:
            if item != item_2 and item_2 in item:
                substrings.append(item_2)

    for partial in substrings:
        try:
            input_list.remove(partial)
        except ValueError:
            pass

    return input_list


charset = f"{string.ascii_lowercase}{string.digits}@-_. "
known = charset
tried = []
result = []


while len(known) > 0:
    found = []

    for prefix in (pbar_2 := (tqdm(known, leave=False))):
        pbar_2.set_description(prefix)

        for char in (pbar := (tqdm(charset, leave=False))):

            substring = f"{prefix}{char}"
            pbar.set_description(char)

            if substring not in tried:

                if check(substring) and substring not in found:
                    tqdm.write(f"{substring}")
                    found.append(substring)
                    result.append(substring)

            tried.append(substring)

    known = found

print()
print(remove_partials(result))
\$\endgroup\$
14
  • \$\begingroup\$ If it's "very inefficient", why does your title claim it's the "most effective" algorithm? \$\endgroup\$ Dec 9, 2022 at 11:36
  • \$\begingroup\$ Actually, it would be better if the title summarised why we're doing this, rather than the detail of how it's implemented. \$\endgroup\$ Dec 9, 2022 at 11:37
  • \$\begingroup\$ My title is referring to the desired outcome. My code is inefficient and so my question is regarding optimizing the efficiency. Do you have a suggestion for an alternative title? \$\endgroup\$
    – n0k
    Dec 9, 2022 at 12:28
  • 3
    \$\begingroup\$ You could make the purpose much clearer by showing some examples of input and the corresponding outputs. That would certainly help. \$\endgroup\$ Dec 9, 2022 at 12:44
  • 1
    \$\begingroup\$ Is the check function supposed to be a "black box", as in, it's an external function you have no control over? And you're trying to figure out which words satisfy it? \$\endgroup\$ Dec 10, 2022 at 12:27

3 Answers 3

5
\$\begingroup\$

You can do this more efficiently by using a trie.

Let's start from the beginning. Imagine the solution is ['we', 'these'].

You can call your check method with all of your initial characters, and it will tell you that only the characters: 'weths' are in the solution.

Then you can check for two character sequences, at the moment you're currently going back to the full set of initial characters, but you don't need to do this, you know that only the characters 'weths' are possible (+ the empty case where you've found a suffix. So you can just search for 'ww, we, wt, wh, ws, ew, ...' and so on.

After this you'll have the following combinations:

  • 'we', 'e$', 'th', 'he', 'es', 'se' (where $ means no extension matched - i.e. a suffix)

Now we can try and extend again. But here we have a bit more of an advantage. When we look at the word 'we' we know that it must end in a valid two-letter sequence starting with 'e', i.e. 'es' or 'e$', so we can just try 'wes', and then when that doesn't work we know we have 'we$', part of the solution. We can repeat this logic with all the remaining sequences:

  • 'we' -> either 'wes' or 'we$'
  • 'th' -> either 'the' or 'th$
  • 'he' -> either 'hes' or 'he$'
  • 'es' -> either 'ese' or 'es$'
  • 'se' -> either 'ses' or 'se$'

Once finished we're left with the following:

'we$', 'e$', 'the', 'hes', 'ese', 'se$'

We can drop the 'e$' as it's a substring of 'we$' and 'se$' and you're only looking for a minimal set of strings (I assume).

This brings us onto our third round, and at this point we can go through again, skipping complete words like 'we$'. But this time we can look at the last two letters of each word to find our next options:

  • 'we$' Complete
  • 'the' -> 'thes' or 'the$'
  • 'hes' -> 'hese' or 'hes$'
  • 'ese' -> 'ese$' only

This gives us: 'we$', 'e$', 'thes', 'hese', 'ese$', 'se$'

Now our fourth round:

  • 'thes' -> 'these' or 'thes$'
  • 'hese' -> 'hese$' only

And finally:

  • 'these' -> 'these$' only

This gives us a list of valid suffices:

['we$', 'e$', 'these$', 'hese$', 'ese$', 'se$']

Which we can deduplicate as you did above.

In terms of implementation - I'd create a trie as a nested dictionary structure, with methods to add words and identify which possible continuations words have:

from collections import defaultdict


def recursive_factory():
    return defaultdict(recursive_factory)


class Trie:
    def __init__(self):
        self._lookup = defaultdict(recursive_factory)
    
    def _add_string(self, string):
        lookup = self._lookup
        for char in string:
            lookup = lookup[char]
            
    def add_word(self, word):
        for offset in range(len(word)):
            self._add_string(word[offset:])
    
    def add_words(self, words):
        for word in words:
            self.add_word(word)
    
    def get_valid_next_chars(self, prefix=''):
        lookup = self._lookup
        for char in prefix:
            lookup = lookup[char]
        return set(lookup.keys())
    

Then we just need to go through the steps above (I created a helper class to store the final result).

class WordList:
    def __init__(self):
        self._suffices = set()
    
    def add_suffix(self, suffix):
        to_drop = set()
        for old_suffix in self._suffices:
            if old_suffix in suffix:
                to_drop.add(old_suffix)
        self._suffices -= to_drop
        self._suffices.add(suffix)
    
    def add_suffices(self, suffices):
        for suffix in suffices:
            self.add_suffix(suffix)
        
    def words(self):
        return tuple(self._suffices)


def next_guesses(valid_guesses, trie):
    for guess in valid_guesses:
        for char in trie.get_valid_next_chars(prefix=guess[1:]):
            yield guess + char

def solve(initial_guesses, check, trie=None, word_list=None):
    if trie is None:
        trie = Trie()
    if word_list is None:
        word_list = WordList()
    
    valid_guesses = [guess for guess in initial_guesses if check(guess)]
    if valid_guesses:
        trie.add_words(valid_guesses)
        word_list.add_suffices(valid_guesses)
        solve(next_guesses(valid_guesses, trie), check, trie=trie, word_list=word_list)
    return word_list.words()

All in all this algorithm is about 200x faster on my machine. It can be made faster still by increasing the speed of the check function (which can also be very efficiently solved with a trie). But at this point we're only calling check ~360 times compared to over 4000.

\$\endgroup\$
2
  • \$\begingroup\$ Great answer! I've been trying to make the script asynchronous after putting a sleep(1) in check(), but I can't seem to wrap my head around it. Do you have any suggestions? \$\endgroup\$
    – n0k
    Dec 17, 2022 at 15:55
  • \$\begingroup\$ By asynchronous, do you mean spawn the checks in a thread pool or something? I'd recommend using asyncio, and then use a gather to execute all the checks in the solve function concurrently. \$\endgroup\$ Dec 17, 2022 at 16:12
4
\$\begingroup\$

This is my first answer on this site.

Without changing the algorithm itself, we can improve performance by using set instead of list to hold and check for an existing item. On my machine, that cut about 33% off execution time.

Also, worth noting that while len(known) > 0 add while known will do the same; the latter is faster and more pythonic.

import string
from tqdm import tqdm


def check(text):
    """Returns True if input text is part of any of the strings in the list"""
    strings = ["we ", "_want", "t0", "gu@ess", "these-", "str1ngs"]
    return any(text in substring for substring in strings)


def remove_partials(input_list):
    """
    Removes strings from the input list they are a substring of any other string in the list
    """
    substrings = set()
    for item in input_list:
        for item_2 in input_list:
            if item != item_2 and item_2 in item:
                substrings.add(item_2)

    return input_list - substrings


charset = f"{string.ascii_lowercase}{string.digits}@-_. "
known = charset
tried = set()
result = set()


while len(known) > 0:
    found = set()

    for prefix in (pbar_2 := (tqdm(known, leave=False))):
        pbar_2.set_description(prefix)

        for char in (pbar := (tqdm(charset, leave=False))):

            substring = f"{prefix}{char}"
            pbar.set_description(char)

            if substring not in tried:
                tried.add(substring)
                if check(substring) and substring not in found:
                    tqdm.write(f"{substring}")
                    found.add(substring)
                    result.discard(prefix)
                    result.add(substring)

    known = found

print()
print(remove_partials(result))

Edit 1

We can reduce the number of checks of chars that never used by adding charset = "".join(char for char in charset if check(char)) before the loop.

Edit 2

while being faster using python's dis

We can look what python does on while len(x) > 0 compare to while x by using dis. As we know, fewer operation means faster code :)

In [1]: import dis

In [2]: def x1(l):
   ...:     while l:
   ...:         pass
   ...:

In [3]: def x2(l):
   ...:     while len(l) > 0:
   ...:         pass
   ...:

In [4]: dis.dis(x1)
  2     >>    0 LOAD_FAST                0 (l)
              2 POP_JUMP_IF_FALSE        6

  3           4 JUMP_ABSOLUTE            0
        >>    6 LOAD_CONST               0 (None)
              8 RETURN_VALUE

In [5]: dis.dis(x2)
  2     >>    0 LOAD_GLOBAL              0 (len)
              2 LOAD_FAST                0 (l)
              4 CALL_FUNCTION            1
              6 LOAD_CONST               1 (0)
              8 COMPARE_OP               4 (>)
             10 POP_JUMP_IF_FALSE       14

  3          12 JUMP_ABSOLUTE            0
        >>   14 LOAD_CONST               0 (None)
             16 RETURN_VALUE

Edit 3

I decided to try implement this solution using DFS instead of the BFS that your code does here. To test the code more accurate, I removed all prints (They are slowing the code a lot!).

The results are a little bit better but I think will be different with different words.

In [1]: %timeit %run codereview281798_dfs.py
3.06 ms ± 10.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [2]: %timeit %run codereview281798_bfs.py
3.24 ms ± 9.13 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

And here is the code:

import string
from tqdm import tqdm


def check(text):
    """Returns True if input text is part of any of the strings in the list"""
    strings = ["we ", "_want", "t0", "gu@ess", "these-", "str1ngs"]
    return any(text in substring for substring in strings)


def remove_partials(input_list):
    """
    Removes strings from the input list they are a substring of any other string in the list
    """
    substrings = set()
    for item in input_list:
        for item_2 in input_list:
            if item != item_2 and item_2 in item:
                substrings.add(item_2)

    return input_list - substrings


CHARSET = f"{string.ascii_lowercase}{string.digits}@-_. "


def find_words():
    charset = "".join(char for char in CHARSET if check(char))
    return remove_partials(dfs_find_words("", charset))


def dfs_find_words(prefix, charset):
    found_words = set()
    is_end_of_word = True
    for char in charset:
        substring = f"{prefix}{char}"
        if check(substring):
            is_end_of_word = False
            words = dfs_find_words(substring, charset)
            found_words = found_words.union(words)
    if is_end_of_word:
        found_words.add(prefix)
    return found_words


def find_words_1():
    charset = "".join(char for char in CHARSET if check(char))
    known = charset
    tried = set()
    result = set()

    while known:
        found = set()
        for prefix in known:
            for char in charset:
                substring = f"{prefix}{char}"
                if substring not in tried:
                    tried.add(substring)
                    if check(substring) and substring not in found:
                        found.add(substring)
                        result.discard(prefix)
                        result.add(substring)

        known = found
    return remove_partials(result)

Note: I think that Trie would be a good use here, but I don't see the immediate use of it

\$\endgroup\$
2
  • \$\begingroup\$ Is while known really faster than while len(known)? Have you measured the difference? (I agree it's better style) \$\endgroup\$ Dec 10, 2022 at 11:42
  • \$\begingroup\$ We can use timeit to measure the difference but, in this case we can also look what do python actually does, using dis and infer it based on number of operations. \$\endgroup\$
    – LazyGoose
    Dec 10, 2022 at 12:42
0
\$\begingroup\$

Here are a couple of hints to help you out:

  1. The list of strings is not changing, so you can define it globally
  2. Comparing a string of length n against m strings of length n each will have O(n*m) complexity
  3. You can preprocess and create a trie for the strings. That will reduce the searching complexity to O(n), since you just need to check for a match.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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