Python Riddle — Get the Longest Possible Chains from a List of Words

Given a list of words, find the longest possible chains that can be formed.

Given a list of words, find the longest possible chains that can be formed. In a chain, each word’s starting letter must be equal to the previous word’s ending letter. Let’s say we are given this list of words:

words = ["apple", "orange", "pear", "element", "replica"]

Some examples of chains that can be formed from these words are:

apple -> element
pear -> replica
replica -> apple -> element
pear -> replica -> apple -> element

Notice that in each chain, the last letter of each word is the first letter of the next word (except the first word of course).

Write a function longest_chains(words) that takes in a list of strings words, and returns a list containing the longest possible chains that can be formed using the words inside words. If there is more than 1 longest possible chain with the same length, return all of them.

Case 1

words = ["apple", "orange", "pear", "element", "replica"]

output -> [
    ["pear", "replica", "apple", "element"]
]

Case 2

words = ["apple", "boy", "cage", "doge", "elephant"]

output -> [
    ["apple", "elephant"],
    ["cage", "elephant"],
    ["doge", "elephant"]
]

Case 3

words = ["apple", "elephant", "taboo", "orange", "extra"]

output -> [
    ["apple", "elephant", "taboo", "orange", "extra"],
    ["elephant", "taboo", "orange", "extra", "apple"],
    ["taboo", "orange", "extra", "apple", "elephant"],
    ["orange", "extra", "apple", "elephant", "taboo"],
    ["extra", "apple", "elephant", "taboo", "orange"]
]

In case 3, the words can form a cyclical chain — "extra" can link back to "apple" in the first line, "apple" can link back to "elephant" in the second line and so on.

Solution Below

Do take some time to give this a go before taking a look at the solution below.

The Logic Behind The Solution

Let’s first create an adjacency matrix using our words, each key being each word in our list, and each value being a list of words our key can lead to. (Remember that the last letter of our current word needs to be the same as the first letter of the next word).

words = ["apple", "orange", "pear", "element", "replica"]

# the graph we want

g = {
    "apple": ["element"],
    "orange": ["element"],
    "pear": ["replica"],
    "element": [],
    "replica": ["apple"]
}

After we generate this graph, we can use this graph along with a queue to generate every possible chain that exists. We keep track of a queue queue, which contains a bunch of chains to search. We also keep track of a list chains that contains our chains.

1. Initialize chains to an empty list.
2. Initialize queue to contain a chain of length 1 (a list) for each word
3. Remove the first chain from queue, and assign it to current
4. Find words that are not inside the chain yet
5. If there are no such words, this is the end of the chain, and add this chain to chains
6. If there are words that are not inside the chain yet, construct a new chain containing this additional word, and add it back to queue.
7. Repeat steps 3 to 6 until queue is empty

At this point, chains should contain every possible chain of words.

chains = [
    ["element"],
    ["apple", "element"],
    ["orange", "element"],
    ["replica", "apple", "element"],
    ["pear", "replica", "apple", "element"]
]

We can then find the maximum length within the chains, and return a list of chains with this length.

The Code Solution

def longests_chain(words):

    def build_graph(words):
        g = {}
        for word in words:
            g[word] = []
            for next in words:
                if next!=word and word[-1] == next[0]:
                    g[word].append(next)
        return g

    g = build_graph(words)

    chains = []
    queue = [[word] for word in words]
    while queue:
        current = queue.pop(0)
        valid_neighbours = set(g[current[-1]]) - set(current)

        if len(valid_neighbours) == 0:
            chains.append(current)

        else:
            for neighbour in valid_neighbours:
                new = current + [neighbour]
                queue.append(new)

    maxlen = len(max(chains, key=len))
    return [c for c in chains if len(c)==maxlen]

A Quick Code Run-Through

words = ["apple", "orange", "pear", "element", "replica"]

Before the start of iteration:

queue = [
    ["apple"],
    ["orange"],
    ["pear"],
    ["element"],
    ["replica"]
]

Iteration 1 — ["apple"] itself is removed, and ["apple", "element"] is added back to the queue.

queue = [
    ["orange"],
    ["pear"],
    ["element"],
    ["replica"],
    ["apple", "element"]
]

Iteration 2 — ["orange"] is removed

queue = [
    ["pear"],
    ["element"],
    ["replica"],
    ["apple", "element"],
    ["orange", "element"]
]

Iteration 3

queue = [
    ["element"],
    ["replica"],
    ["apple", "element"],
    ["orange", "element"],
    ["pear", "replica"]
]

Iteration 4 — ["element"] is removed, but since no word begins with t, it is added to chains instead of queue.

queue = [
    ["replica"],
    ["apple", "element"],
    ["orange", "element"],
    ["pear", "replica"]
]

Iteration 5

queue = [
    ["apple", "element"],
    ["orange", "element"],
    ["pear", "replica"],
    ["replica", "apple"]
]

Iteration 6 — ["apple", "element"] is removed from queue, and since no word begins with t, it is added to chains and not back to queue.

queue = [
    ["orange", "element"],
    ["pear", "replica"],
    ["replica", "apple"]
]

Iteration 7 — same as iteration 6. ["orange", "element"] is added into chains and not back into queue.

queue = [
    ["pear", "replica"],
    ["replica", "apple"]
]

Iteration 8

queue = [
    ["replica", "apple"],
    ["pear", "replica", "apple"]
]

Iteration 9

queue = [
    ["pear", "replica", "apple"],
    ["replica", "apple", "element"]
]

Iteration 10

queue = [
    ["replica", "apple", "element"],
    ["pear", "replica", "apple", "element"]
]

Iteration 11

queue = [
    ["pear", "replica", "apple", "element"]
]

Iteration 12

queue = []

At end of all iterations:

chains = [
    ["element"],
    ["apple", "element"],
    ["orange", "element"],
    ["replica", "apple", "element"],
    ["pear", "replica", "apple", "element"]
]

And we simply use the max function to select the longest chain. And there we have it, the solution to this riddle.

Conclusion

If this article provided value and you wish to support me, do consider signing up for a Medium membership — It’s $5 a month, and you get unlimited access to articles on Medium. If you sign up using my link below, I’ll earn a tiny commission at zero additional cost to you.

Sign up using my link here to read unlimited Medium articles.

I write coding articles (once per 1–2 days) that would have probably helped the younger me speed up my learning curve. Do join my email list to get notified whenever I publish.

More content at PlainEnglish.io. Sign up for our free weekly newsletter. Follow us on Twitter and LinkedIn. Join our community Discord.