Реализация алгоритма в питоне

Question

У меня есть определенный алгоритм, который нужно реализовать.В основном это следующие правила:

1. Первый разделенный пробелами токен в строке будет определяемым словом.
2. Более поздние токены будут определением.Если определение «.», То это слово является примитивом, т. Е. Словом без определения.
3. Выходными данными является отдельная строка текста, разделенная запятой, содержащая каждое слово в словаре ровно один раз.Каждое слово должно быть напечатано только после всех слов в его определении.Обратите внимание, что для определенных наборов входов может быть несколько допустимых выходов.

Например, вход:

Civic        Honda Car
Honda        Manufacturer
VW           Manufacturer
Manufacturer .
Car          .
Beetle       VW Car

Некоторые возможные выходы:

Car, Manufactor, Honda, VW, Beetle, Civic
Manufacturer, VW, Car, Beetle, Honda, Civic
Manufacturer, Honda, VW, Car, Beetle, Civic

Моя реализация:

def defIt(pre, cur):
    # If previous and current strings are the same, no action take
    if pre == cur:
        return pre

    # Split two strings to list
    l_pre = pre.split()
    l_cur = cur.split()

    # If previous string length is shorter than the current string     length, then swap two lists
    if len(l_pre) < len(l_cur):
        l_pre, l_cur = l_cur, l_pre

    found = False


    for j, w_cur in enumerate(l_cur):
        for i, w_pre in enumerate(l_pre):
            if w_pre == w_cur:
                found = True
                return ' '.join(l_cur[j:] + l_cur[:j] + l_pre[:i] + l_pre[(i + 1):])


    if not found:
        return ' '.join(l_cur[1:] + [l_cur[0]] + l_pre)

Просто не могу понять это правильно.Чего мне не хватает?Большое спасибо.

Answer 1

def read_graph(lines):
    g = {}
    for line in lines:
        words = line.split()
        if words[1] == '.':
            words = words[:1]
        g[words[0]] = words[1:]
    return g

def dump_graph(g):
    out = []
    def dump(key):
        for k in g[key]:
            dump(k)
        if key not in out:
            out.append(key)
    for k in g:
        dump(k)
    return out

Использование:

>>> data = """Civic        Honda Car
... Honda        Manufacturer
... VW           Manufacturer
... Manufacturer .
... Car          .
... Beetle       VW Car
... """
>>> g = read_graph(data.splitlines())
>>> g
{'VW': ['Manufacturer'], 'Civic': ['Honda', 'Car'], 'Car': [],
'Honda': ['Manufacturer'], 'Beetle': ['VW', 'Car'], 'Manufacturer': []}
>>> dump_graph(g)
['Manufacturer', 'VW', 'Honda', 'Car', 'Civic', 'Beetle']
>>>

Каждое слово в результирующем списке идет после всех его слов "определения".