Python word game. Last letter of first word == first letter of second word. Find longest possible sequence of words

Question

I'm trying to write a program that mimics a word game where, from a given set of words, it will find the longest possible sequence of words. No word can be used twice.

I can do the matching letters and words up, and storing them into lists, but I'm having trouble getting my head around how to handle the potentially exponential number of possibilities of words in lists. If word 1 matches word 2 and then I go down that route, how do I then back up to see if words 3 or 4 match up with word one and then start their own routes, all stemming from the first word?

I was thinking some way of calling the function inside itself maybe?

I know it's nowhere near doing what I need it to do, but it's a start. Thanks in advance for any help!

g = "audino bagon baltoy banette bidoof braviary bronzor carracosta charmeleon cresselia croagunk darmanitan deino emboar emolga exeggcute gabite girafarig gulpin haxorus"

def pokemon():
    count = 1
    names = g.split()
    first = names[count]
    master = []
    for i in names:
        print (i, first, i[0], first[-1])
        if i[0] == first[-1] and i not in master:
            master.append(i)
            count += 1
            first = i
            print ("success", master)
    if len(master) == 0:
        return "Pokemon", first, "does not work"
    count += 1
    first = names[count]

pokemon()

Answer 1

Your idea of calling a function inside of itself is a good one. We can solve this with recursion:

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 - set([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)

Now we just define our word list:

words = ("audino bagon baltoy banette bidoof braviary bronzor carracosta "
         "charmeleon cresselia croagunk darmanitan deino emboar emolga "
         "exeggcute gabite girafarig gulpin haxorus")

words = frozenset(words.split())

Call longest_path with a set of words:

>>> longest_path(words)
['girafarig', 'gabite', 'exeggcute', 'emolga', 'audino']

A couple of things to know: as you point out, this has exponential complexity, so beware! Also, know that python has a recursion limit!