Longest word chain from a list of words

Question

So, this is a part of a function I'm trying to make.

I don't want the code to be too complicated.

I have a list of words, e.g.

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse'] 

The idea of the word chain sequence is for the next word to begin with the letter that the last word ended in.

(Edit: Each word cannot be used more than once. Other than that there are no other constraints.)

I want the output to give the longest word chain sequence, which in this case is:

['hedgehog', 'giraffe', 'elephant', 'tiger', 'racoon'] 

I'm not really sure how to do it, I had different attempts at trying this. One of them...

This code finds the word chain correctly if we start with a specific word from the list, e.g. words[0] (so 'giraffe'):

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']  word_chain = []  word_chain.append(words[0])  for word in words:     for char in word[0]:         if char == word_chain[-1][-1]:             word_chain.append(word)  print(word_chain) 

Output:

['giraffe', 'elephant', 'tiger', 'racoon'] 

BUT, I want to find the longest possible chain of words (explained above).

My method: So, I tried to use the above working code that I wrote and loop through, using each word from the list as the starting point and finding the word chain for each word[0], word[1], word[2] etc. Then I tried to find the longest word chain by using an if statement and compare the length to the previous longest chain, but I can't get it done properly and I don't really know where this is going.

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']  word_chain = [] max_length = 0 for starting_word_index in range(len(words) - 1):      word_chain.append(words[starting_word_index])      for word in words:         for char in word[0]:              if char == word_chain[-1][-1]:                 word_chain.append(word)      # Not sure      if len(word_chain) > max_length:         final_word_chain = word_chain         longest = len(word_chain)         word_chain.clear()  print(final_word_chain) 

This is my nth attempt, I think this one prints an empty list, I had different attempts before this that failed to clear the word_chain list properly and ended up repeating words over again.

Any help much appreciated. Hopefully I didn't make this too teedious or confusing... Thanks!

Answer 1

You can use recursion to explore every "branch" that emerges when every possible letter containing the proper initial character is added to a running list:

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse'] def get_results(_start, _current, _seen):   if all(c in _seen for c in words if c[0] == _start[-1]):     yield _current   else:       for i in words:         if i[0] == _start[-1]:           yield from get_results(i, _current+[i], _seen+[i])   new_d = [list(get_results(i, [i], []))[0] for i in words] final_d = max([i for i in new_d if len(i) == len(set(i))], key=len) 

Output:

['hedgehog', 'giraffe', 'elephant', 'tiger', 'racoon'] 

This solution works similar to the breadth-first search, as the function get_resuls will continue to iterate over the entire list as long as the current value has not been called on before. Values that have been seen by the function are added to the _seen list, ultimately ceasing the stream of recursive calls.

This solution will also ignore results with duplicates:

words = ['giraffe', 'elephant', 'ant', 'ning', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse',] new_d = [list(get_results(i, [i], []))[0] for i in words] final_d = max([i for i in new_d if len(i) == len(set(i))], key=len) 

Output:

['ant', 'tiger', 'racoon', 'ning', 'giraffe', 'elephant']