Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

My friend gave me a problem that he says is easy, but I can't figure out a good algorithm to use to do it.

You are given an input of 100 random English words. You have to find the longest string of words where the last letter in one word matches the first letter in the next word. You can only use each word once.

For example, if you were given the words "cat", "dog", "that", the longest string you could make would be "cat -> that". If you were given the words "mouse", "moose", "unicorn", the longest string you could make would just be one word (since none of those words link). If you were given the words "bird", "dish", "harb", the longest string you could make would be "harb -> bird -> dish" (or "dish -> harb -> bird" or "bird -> dish -> harb").

I came up with the idea of modeling this as a directed cyclic graph. Each node would just be a word, with vertices going to each word/node that started with the letter this word ended with.

+-------+         \ +------+
|  cat  |-----------| that |
+-------+         / +------+
    |                  |
   \|/                 |
+-------+ /            |
|  the  |--------------+
+-------+ \

This problem appears to be a longest path search, which is NP-Hard.

Is there a better way to do it? Or even some sort of approximation algorithm that could be used? Or some way to exploit qualities of English to reduce the search space?

share|improve this question
4  
With 100 words, you get (at least) 100! = 9.332622e+157 combinations. Good luck with that, I think your friend is pulling your leg saying this is easy. –  Martin Wickman Aug 11 '13 at 8:34
1  
But, the number of possible combinations is much less than that, because on average a single word is only linked to about 6 or 7 other words. –  Abe Tool Aug 11 '13 at 12:56
2  
You are correct that this is exactly a longest path search. I think your friend is wrong. However, an exhaustive search is not hard to code, and may not run all that long. –  kevin cline Aug 12 '13 at 4:16
4  
Just for fun, I coded up a brute force exhaustive search (as @kevincline pointed out) in Ruby (gist.github.com/anonymous/6225361). With 100 words, it only took ~96 seconds (gist.github.com/anonymous/6225364 ). And this was a highly inefficient, un-optimized, interpreted-language, quick-and-dirty script. So with only 100 words even a slow version of brute force runs in a sane amount of time. My code doesn't actually create an acyclic graph and then search through it, it just recursively builds every possible path starting from each word, and keeps track of the longest ones. –  Ben Lee Aug 13 '13 at 20:37
3  
The problem states that there are 100 words. I think this means you can apply a dynamic programming solution, which is mentioned in the article you are referring to. –  Julien Guertault Aug 14 '13 at 8:17

2 Answers 2

I think this is related to the longest path (LP) problem that you mentioned, but it's a little different. The primary difference is that the LP problem has a higher degree of connectivity than what your suggested problem does. By restricting your connections to the last and first letters, you remove a large number of potential combinations.

Here's how I would recommend tackling this one:

  1. For each word in the list, count the possible connections in and connections out.
  2. Discard any words that have 0 ins and 0 outs.
  3. Identify an initial set of "starter words" with the lowest numbers of ins and outs, and the outs must be greater than 0.
  4. Each starter word receives its own working copy of the ins / outs connection count. This forms the head of the chain.
  5. For each chain, identify a list of "next words" based upon:
    • last letter of starter or previous word
    • lowest number of of ins and outs connections (again, the outs must be greater than 0)
  6. For each next word, repeat step 5 until the chain terminates.

Keep in mind that:

  • You'll need to keep track of the length of the chains and have some global mechanism to identify the longest chain.

  • You'll also need to remove each word from the working copy of the connection counts in order to avoid a recursive loop.

  • At some point, your chain will terminate and you have to select a word with a 0 connection out count.

  • You may have to recalculate ins / outs as words are removed from the working lists. At first glance, I don't think this will be necessary as the overall sets will be relatively small. If you scaled out to 1000 words, then having static counts may slow down the algorithm from converging.

I kind of saw this as a packing problem. To me, the connections in and out identify the shape to be packed. The lower the connections, the more odd the shape. The more odd the shape, the sooner I want to pack it as I perceived having decreasing odds of being able to pack an odd shape the later I got into the chain.

As an example:

{dog, gopher, alpha, cube, elegant, this, that, bart}

dog     0, 1
gopher  1, 0
alpha   0, 0
cube    0, 1
elegant 1, 2
this    3, 0
that    2, 1
bart    0, 2

//alpha is dropped with 0 in and 0 out.
//two candidates found: dog, cube

//chain 1
dog => gopher
//chain 2
cube => elegant => that => this

//Note 1: the following chain won't occur due to selection rules
//that takes priority over this because of output count
cube => elegant => this

//Note 2: this chain won't occur either due to selection rules
bart => that => this
share|improve this answer
2  
Is there any guarantee that this algorithm will always find the longest path? Off the top of my head, I can't think of a counter-example, but this seems like it might fall for a "local maximum" type solution. –  Ben Lee Aug 14 '13 at 19:48
    
@BenLee - I'm a software engineer; I never guarantee my code. :-) Seriously though, I don't know the answer to your question. My set theory and mathematical proof skills are weak, to put it mildly, so I don't have any way beyond empirical evaluation to validate my algorithm. I'm not sure this problem is really NP-hard, but I can't validate that claim either. If it's not NP-hard then there ought to be a means to validate the algorithm. –  GlenH7 Aug 14 '13 at 20:46
2  
What about a word list like this: "dog, gopher, bun, nun, noon, nub". The algorithm would incorrectly pick the longest list as "dog -> gopher", when it actually is any combination of "bun, nun, noon, nub". –  Abe Tool Aug 15 '13 at 9:19
1  
@AbeTool - good example there. I would add another iteration (or two) to allow for "lowest input >= 1" and "lowest output >= 1" combinations then. –  GlenH7 Aug 15 '13 at 11:50
2  
I don't think that's going to solve the problem in all cases. I think this falls into a "local maximum" type solution. –  Abe Tool Aug 17 '13 at 3:33

If you make 26X26 matrix to represent directed graph of vertex as each alphabet and words as edge. For example word - APPLE connect vertex A and E with edge directed from A to E. Now the problem reduces to finding largest Eulerian trail (path which includes maximum number of edges, visiting each edge once wit possible repetition of vertices) in the graph. One of the O(E) algorithm would be to start randomly from a pair of vertices. Find a path between them. Than keep relaxing the path till it is possible.

update @GlenH7 I solved a similar question on www.hackerearth/jda recently, there was relative marks with respect to best solution and I scored the highest marks with the following approch-

Given list of words. Find the longest chain that can be formed by them. A chain is valid if every word begin with a letter *ending at the ending of last word.

Approch =

1)make the graph of alphabets as vertices and words as edges. In place of using multiple edges use one with weight equal to number of edges.

2)find the strongly connected component of graph with maximum edges. Temporarily discard other edges.

3)For each vertex make its indegree equal to its outdegree.

4)Now their exists eulerian circuit in graph. Find it.

5)Now in remaining graph(w.r.t orignal graph find the longest trail with first vertex in chosen strongly connected component. I think this is NP hard.

6)Include the above trail in Elerian circuit converting eulerian circuit into trail.

Why - I accept that this question is most probably NP hard(guess, not mathematically speaking). But the above approach works best when there is a long list(1000+) of uniformly distributed words(i.e. not intended to be w.c. for above approach). Let us assume that after converting given list to graph mentioned above, it luckily turns out to be a eulerian graph(see http://en.wikipedia.org/wiki/Eulerian_path for conditions), then without any doubt we can say that answer to above question is P and is actually the eulerian path in the graph(see http://www.graph-magics.com/articles/euler.php for a very simple approch to do so and see this to verify that your graph has single http://www.geeksforgeeks.org/strongly-connected-components/ and if not temporarily clean other small scc because eulerian path exists for single scc). Thus for not lucky cases(which are almost all cases) I try to convert them to lucky cases(i.e eulerian trail condition are fulfilled). How to do this? I tried do increasing depth search for irrelevant edges(the set of edges in a path staring from vertex with outdegree greater than indegree and ending at vertex with indegree greater than outdegree). Increasing depth search means that first I searched for all such set of one edge in path than two edges in path and so on. It may seem at first look that ith depth search would take O(nodes^i) thus total time complexity of O(nodes + nodes^2 + nodes^3 + ....) till it is a lucky case. But amortized analysis will revel it is O(edges). Once it is reduced lucky case find eulerian circuit.

Till here it was all polynomial time. This would give almost the best solution. But to further increase your solution(perfect solution is NP hard) try some greedy approach in remaining graph to find a long trail staring with one of vertices in chosen scc. Now add this to above found eulerian trail to further increase it.

share|improve this answer
1  
Welcome to Programmers. We encourage answers that explain the why along with the what or how. Given that the OP believes the problem to be NP-hard, it would be helpful if you edited your answer and further explain why this approach resolves any potential issues. –  GlenH7 Jun 25 at 21:30
    
@GlenH7 I solved a similar question on www.hackerearth/jda recently, there was relative marks with respect to best solution and I scored the highest marks with the following approch- –  user179793 Jul 3 at 16:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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