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.

Difficulty: interview

Starter code:

def recoverSecret(triplets):
	

Solutions:
def recoverSecret(triplets):
  r = list(set([i for l in triplets for i in l]))
  for l in triplets:
    fix(r, l[1], l[2])
    fix(r, l[0], l[1])
  return ''.join(r)
  
def fix(l, a, b):
   """let l.index(a) < l.index(b)"""
   if l.index(a) > l.index(b):
       l.remove(a)
       l.insert(l.index(b), a)

def recoverSecret(triplets):
    letters = list(set([l for t in triplets for l in t]))        
            
    for t in triplets * len(letters):
        for i in range(len(t)-1):
            a, b = letters.index(t[i]), letters.index(t[i+1])
            if( a > b ): letters[b], letters[a] = letters[a], letters[b]
            
    return ''.join(letters)

import collections, functools, itertools

def recoverSecret(triplets):
    """triplets is a list of triplets from the secret string. Return the string."""
    
    # Build a reverse directed graph of letters
    graph = Graph()
    for triplet in triplets:
        for i, j in pairwise(triplet):
            graph[i].goes_to(graph[j])
    
    # Pop off orphan letters one-by-one to form the word
    cardinality = lambda node: len([ p for p in node.parents if p.value in graph ])
    getnext = functools.partial(min, graph.viewvalues(), key=cardinality)
    word = ( graph.pop(getnext().value).value for i in xrange(len(graph)) )
    
    return ''.join(word)
    
class Graph(collections.defaultdict):
    """A graph that autocreates nodes"""
    def __missing__(self, key):
        self[key] = Node(key)
        return self[key]

class Node(object):
    """A directed graph node that knows its parents"""
    def __init__(self, value):
        self.value = value
        self.parents = []
    def goes_to(self, child):
        child.parents.append(self)

def pairwise(iterable):
    """Iterates through an iterable in pairs [a,b,c,d] --> ( [a,b], [b,c], [c,d] )"""
    a, b = itertools.tee(iterable)
    next(b, None)
    return itertools.izip(a, b)

def recoverSecret(a):
    out = list(zip(*a)) 
    h = [j for j in (set(out[0])-set(out[1]+out[2]))]
    for i in a:
        if i[0] in h:
            i[:2], i[2] = i[1:], ''
        
    return h[0]+recoverSecret(a) if h else str()


def recoverSecret(a):
    out = list(zip(*a))  # transpose the list
    h = [j for j in (set(out[0])-set(out[1]+out[2]))]  # find the first letter
    for i in a:
        if i[0] in h:  # find triplets starting with that letter
            i[:2], i[2] = i[1:], ''   # remove the first letter and move other letters up
        
    return h[0]+recoverSecret(a) if h else str()  # return the first letter plus the recursion on the rest


def recoverSecret(triplets):
    'triplets is a list of triplets from the secrent string. Return the string.'
    res = ''
    while triplets != []:
        non_firsts = [num for t in triplets for num in t[1:]]
        firsts = [t[0] for t in triplets]
        for f in firsts:
            if f not in non_firsts:
                res += f
                for t in triplets:
                    if t[0] == f:
                        t.pop(0)
                break
        triplets = [t for t in triplets if t != []]
    return res

def recoverSecret(triplets):
    ansList = list({triplet[i] for i in range(3) for triplet in triplets})
    indexDict = {letter:i for i,letter in enumerate(ansList)}
    
    isModified = True
    while isModified:
        isModified = False
        for triplet in triplets:
            for i in range(2):
                if indexDict[ triplet[i] ] > indexDict[ triplet[i+1] ]:
                    isModified = True
                    indexDict[ triplet[i] ], indexDict[ triplet[i+1] ] = indexDict[ triplet[i+1] ], indexDict[ triplet[i] ]
    
    for k in indexDict.keys(): ansList[ indexDict[k] ] = k
    return ''.join(ansList)

from itertools import cycle
def recoverSecret(ts):
    orders = set(sum([[(a,b),(b,c),(a,c)] for a,b,c in ts],[]))
    secret, complete = list(set(l for t in ts for l in t)), False
    for a,b in cycle(orders):
        i, j = (secret.index(a), secret.index(b))
        complete = i < j and complete + 1
        if j < i: secret[j], secret[i] = a, b
        elif complete >= len(orders): break  
    return ''.join(secret)


from collections import defaultdict


def recoverSecret(triplets):
    letters = defaultdict(set)
    for a, b, c in triplets:
        letters[a].add(b)
        letters[a].add(c)
        letters[b].add(c)

    for key, value in list(letters.items()):
        for after_key in value:
            letters[key] = letters[key].union(letters[after_key])

    return ''.join(k for k, _ in sorted(
        iter(letters.items()), key=lambda __v: len(__v[1]), reverse=True
    ))


def recoverSecret(triplets):
    'triplets is a list of triplets from the secrent string. Return the string.'
    res = ""
    table = {}
    visited = set()
    for a,b,c in triplets:
        if not table.has_key(a):
            table[a] = set()
        if not table.has_key(b):
            table[b] = set()
        if not table.has_key(c):
            table[c] = set()
        table[a].add(b)
        table[a].add(c)
        table[b].add(c)

    count = len(table.keys())
    while len(visited) < count:
        Min = count
        c = ''
        for k,v in table.iteritems():
            l = len([elem for elem in v if elem not in visited])
            if l < Min and k not in visited:
                Min = l
                c = k
        visited.add(c)
        res += c
    return res[::-1]

def recoverSecret(triplets):
    # Initialize the answer to the letters we're given in the triplets (use set() to drop duplicates)
    answer = list(set([item for sublist in triplets for item in sublist]))
    # Convert the triplets into sets of pairs, to more easily do comparisons
    clues = []
    for t in triplets:             # copy remaining triplets as pairs
        clues.append([t[0], t[1]])
        clues.append([t[1], t[2]])

    # Loop through the clue pairs, swapping (sorting) letters that are out of order.
    # Once we've made no more swaps, we know we are done.
    while True:
        changed = False
        for pair in clues:
            left = answer.index(pair[0])
            right = answer.index(pair[1])
            if left > right:     # These letters are out-of-order, so swap them
                answer[left], answer[right] = answer[right], answer[left]
                changed = True
        if not changed:
            break
    return "".join(answer)