-3

This is example of the problem (sequence ends if last 2 letters are "te")

lasagna nato top operation online nervous usable levitate -> end word ended with "te"

There are around >100K words and the "end" letters are given and you cannot use same word more than once. I tried using going "backward" (find words that end with the begining of the words that end with "te") in a recursive fashion but that takes way to long. What's the most optimal way of finding the longest sequence?

Improve this question
1

3 Answers 3

Reset to default
2

These rules define a directed graph:

  • the words are the vertices of the graph

  • the edges of the graph are the directed connections between two words where the first word ends with the two starting letters of the second word, with the exception of pairs where the first word starts with "xx".

Finding the longest sequence of words then means to find the longest path in that graph, which is known as the Longest Path problem. It is known to be NP-hard, so don't expect to find an efficient algorithm. Wikipedia, however, mentions an approximation algorithm, and you could try to apply a discrete optimization algorithm like Simulated Annealing to find "good" (but nor necessarily optimal) solutions in a reasonable amount of time.

Improve this answer
9
  • >100k words, 26x26 = 676 connecting letters, so every word connects to 150 words on average. No way on earth to find an optimal solution. I’d read up what I can about approximation algorithms.
    – gnasher729
    May 29, 2021 at 20:07
  • Thanks for the answer, but what are edges in this graph (first letters or 2 first/last letters)?
    – tnemele12
    May 29, 2021 at 20:29
  • @rokob: neither. The edges are the pairs of words where the first word ends with the same two letters as the second one begins with (with the exceptions of those "xx" endings.
    – Doc Brown
    May 29, 2021 at 21:51
  • I keep seeing the two letters as nodes and each word as an edge. Any good reason to not do it that way?
    – candied_orange
    May 29, 2021 at 23:00
  • 2
    @candied_orange: the problem statement was "you cannot use same word more than once.", not "you cannot use same two-letter sequence more than once.", so using the words as vertices directly maps to the longest-path problem.
    – Doc Brown
    May 30, 2021 at 7:12
0

There’s no chance to find an optimal solution. Too many possibilities.

I’d start with a random last word that has the required end letters, then pick earlier words at random according to the rules, and see how far I get. 100,000 words, so make a few thousand attempts.

I’d then try to find out if there is some heuristics which words can be picked to get longer sequences. Like preferring words with more / fewer connections.

One observation: If say 30 words start with “ab” and 90 words end with “ab” then “ab” can be used as a connection only 30 times, so 60 words can never be used. If you prefer connections that are available often then you’d take this into account.

Improve this answer
-1

I'm not sure what the context for the question is, but if I was solving this problem, I'd use regular expressions. I'll assume that the words are all separated by a single space character.

The regex to match all word endings followed by a space then the ending repeated again would be /(\w\w)(?= \1)/. Try pasting it into regexr.com to see how it works. Using regex varies per programming language.

As for the word duplication requirement:

you cannot use same word more than once

you could split the string by each space character to get an array, then deduplicate that.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.