Home > Enterprise >  Function which find longest circle sequence from set of words
Function which find longest circle sequence from set of words

Time:11-17

My problem is pretty simple.

I have this code

def get_neighbors(word, choices):
    return set(x for x in choices if x[0] == word[-1])


def longest_path_from(word, choices):
    choices = choices - {word}
    neighbors = get_neighbors(word, choices)

    if neighbors:
        paths = (longest_path_from(w, choices) for w in neighbors)
        max_path = max(paths, key=len)
    else:
        max_path = []

    return [word]   max_path


def longest_path(choices):
    return max((longest_path_from(w, choices) for w in choices), key=len)

Which from set of words finds longest sequence where last letter of first word equals to first letter of second word

I would like to adjust this code to find longest cyclic sequence.

So for examples.

  • longest_path({'ca', 'abc', 'cd', 'da'}) returns ['ca', 'abc', 'cd', 'da'] which is correct but i would like it to be ["abc","cd","da"] so there is one more condition and that is that last char of last word matches first char of first word.

I cant seem to find where to put it.

Thanks in for any help.

CodePudding user response:

Per my comment, longest_path_from returns to you all the sequences it found. Just run through those and discard the ones that aren't circular.

def get_neighbors(word, choices):
    return set(x for x in choices if x[0] == word[-1])

def longest_path_from(word, choices):
    choices = choices - {word}
    neighbors = get_neighbors(word, choices)

    if neighbors:
        paths = (longest_path_from(w, choices) for w in neighbors)
        max_path = max(paths, key=len)
    else:
        max_path = []

    return [word]   max_path


def longest_path(choices):
    newlist = []
    for s in list(longest_path_from(w, choices) for w in choices):
        if s[0][0] == s[-1][-1]:
            newlist.append( s )
    return max(len(s) for s in newlist)

print(longest_path({'ca','abc','cd','da'}))

longest_path could be turned into a one-liner, but that's pathological. ;)

  • Related