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. ;)