Reconstruct a string, given a list of subsequence triplets

Question

I wrote a solution to this CodeWars challenge:

There is a secret string which is unknown to you. Given a collection of random triplets from the string, recover the original string.

A triplet here is defined as a sequence of three letters such that each letter occurs somewhere before the next in the given string. "whi" is a triplet for the string "whatisup".

As a simplification, you may assume that no letter occurs more than once in the secret string.

You can assume nothing about the triplets given to you other than that they are valid triplets and that they contain sufficient information to deduce the original string. In particular, this means that the secret string will never contain letters that do not occur in one of the triplets given to you.

So, for example, given triplets [['t','u','p'], ['w','h','i'], ['t','s','u'], ['a','t','s'], ['h','a','p'], ['t','i','s'], ['w','h','s']], my code would reconstruct the secret string whatisup. My code builds a dictionary, with each character from string as a key, and possible characters that precede the key as the value. Then, it loops through the dictionary, building the secret string a character at a time.

def recoverSecret(triplets):
    secret = ''
    secret_dict = {}
    # any better way to build a dictionary based on relationship of triplets?
    for x in triplets:
        for y in x:
            secret_dict.setdefault(y, set()).update(x[x.index(y) - 1]) if x.index(y) != 0 else secret_dict.setdefault(y, set())

    def removeChar(c) -> dict:
        '''find first char in secret'''
        #any better way to remove element from set that is value of dictionary when value in set?
        {v.remove(c) for k, v in secret_dict.items() if c in v}

    def findChar() -> str:
        '''find first char in secret when there is no char in front of it'''
        #any better way to find character when value is dictionary is empty?
        return next(k for k, v in secret_dict.items() if not v)

    while secret_dict:
        first_char = findChar()
        #any better way to rebuild dictionary when key == k?
        secret_dict = {k: v for k, v in secret_dict.items() if k != first_char}
        removeChar(first_char)
        secret = secret + first_char
    return secret

Answer 1

It looks like you have implemented Kahn's algorithm for topological sorting.

By PEP 8, the official Python style guide, function names should be lower_case_with_underscores. Also, since the code would work equally well with an n-tuples as inputs, I'd rename triplets to subsequences.

For building secret_dict, I suggest:

• using collections.defaultdict(set)
• iterating by index, so as to avoid calling x.index(y).

The removeChar() function does not actually return a dict, as claimed — there's no return statement! For clarity, I'd avoid the bogus use of a set comprehension that actually surreptitiously mutates secret_dict's values as a side-effect, and just write it as a loop.

I don't think that removeChar() and findChar() need to be defined as inner functions, especially since they are both short. The functions don't really help with code clarity, since they act on secret_dict by closure.

from collections import defaultdict

def recover_secret(subsequences):
    preceding_chars = defaultdict(set)
    for subseq in subsequences:
        for i in range(len(subseq)):
            preceding_chars[subseq[i]].update(subseq[i - 1] if i else '')

    secret = []
    while preceding_chars:
        c = next(k for k, v in preceding_chars.items() if not v)
        del preceding_chars[c]
        for prec in preceding_chars.values():
            if c in prec:
                prec.remove(c)
        secret.append(c)
    return ''.join(secret)