# Reconstruct a string, given a list of subsequence triplets

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


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:

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)

• any way to list comprehensive from line for prec in preceding_chars to prec.remove? or it does not recommend? – A.Lee Oct 31 '18 at 0:10
• As I said, I don't recommend using a comprehension, since .remove() is a mutating operation. Comprehensions should be used for constructing a new dict with no side-effects. – 200_success Oct 31 '18 at 0:13
• and for i in range(len(subseq)) if performance will be better if I to use enumerate to get index and value at same time? – A.Lee Oct 31 '18 at 0:20
• I had considered enumerate(subseq), but chose not to write it that way because you'd still need to refer to subseq[i - 1] anyway. I had also considered using zip(subseq, subseq[1:]), but then I'd have to handle the initial character as a special case. – 200_success Oct 31 '18 at 0:23