Find The Longest Word Sequence in Word Snake Game Problems

user_14849037 0
Viewed 98

I was playing the game Word Snake and I was wandering if it is be possible to solve this game using an algorithm.

Here is the description of the game:

Given a bag (a set with possible repeating values) of phrases: S = {phrase1, phrase2, phrase3, ..., phraseN}

A snake is an ordered list of phrases from S such that, except for the first phrase, the first word in the phrase matches the last word in the previous phrase. Also, the phrasei (where 1 ≤ i ≤ N) can only be present once.

How to find the maximum length of all possible snakes?

Example: For S = { 'A B' , 'B C' , 'B D' , 'C B' , 'C D'}, the maximum length would be 4 because ['A B', 'B C', 'C B', 'B D'] is the longest snake.

dynamic-programming graph-algorithm optimization algorithm
2 Answers

This likely can be solved by some variation of optmization problem of Eulerian Path problem.

Reduce the problem to a graph:

G = (V, E) where:
V = { all words }
E = {(word1, word2) | ​If there is a phrase word1, word2 }

In your example:

V = {A, B, C, D }
E = {(A,B), (B,C) (B,D), (C, B), (C, D) }

Now, Unfortunately, this instance of the problem is not an Eulerian Path, but if an Eulerian path existed - finding it would have got you the optimal solution. Example, if you add the phrase 'D C', the graph becomes eulerian, and indeed you can find the euler path:

A -> B -> C -> B -> D -> C -> D, which stands for 'A B', 'B C', 'C B', 'B D', 'D C', C D'

The good news about Eulerian path - this problem can be solved efficiently and is Not NP Complete (unless P=NP).

Note: This solution is working out of the box to find if there is a sequence containing ALL phrases (and lets you find it easily). I am not familiar, and haven't studies the issue, if the optimization problem is substantially harder though.

user_5726700

Edit: I assumed phrase repetition is forbidden. If phrase repetition is allowed, one can check if any cycle is accessible from the starting phrase. If so, output infinity. Otherwise, proceed as in the DAG approach.

We can arrange the phrases into a graph, where each vertex is a phrase, and there exists a directed edge from phraseA to phraseB if and only if the last word from phraseA is the same as the first word from phraseB. Once we have constructed this graph, we want to find the longest path in this graph.

If the graph is acyclic, which means there exist no cycles, then it is possible to find the longest path by using a Bellman-Ford algorithm on the same graph, but with edges of weight -1.

If, however, the graph contains cycles, which is the overwhelming majority of cases, the problem becomes NP-hard, possibly apart from some other edge cases.

Notice, that your very simple example already contains a cycle: 'B C' -> 'C B' -> 'B C'.

In conclusion, the only way you can hope to solve the problem is by iterating over all of the n! possibilities, where n is the size of S.

user_144066820
Related