0

Here's a game that I'm trying to implement. A kids game where they name an object in a selected category ( say animals! ) such that the first letter of the player's word is the same as the last letter of the previous player's word.

An example would be:

  • Player 1: giraffee
  • Player 2: elephant
  • Player 3: tiger
  • Player 4: raccoon

and so on!

Now, I want to write a code that given a list of words it will find the longest possible chain of words.

A possible list:

['giraffe', 'elephant', 'ant', 'tiger', 'raccoon', 'cat', 'hedgehog', 'mouse']

The longest will have to be: ['hedgehog', 'giraffe', 'elephant', 'tiger', 'raccoon']

The bug in my code is if I change the order of the original list the longest chain will differ!!! :(

Here's the pseudo code:

function longest-chain(chain, V , longest) #Recursively return the longest chain in V
    extended = False
    for word in V do
        if chain + word is a legal chain then
            longest = longest-chain(chain + word, V / {word})
            extended = True
    if extended is False then # No word in V could extend chain
        if chain is longer than longest then
            longest = chain
    return longest

(The / indicates the set difference operator)

Could somebody help me implement it correctly? I didn't want to post my code because I wanted to start over.

Mr. Polywhirl
  • 42,981
  • 12
  • 84
  • 132
sorted
  • 19
  • 2
  • 2
    `"I didn't want to post my code because I wanted to start over."` -- Why not? – Mr. Polywhirl Dec 26 '13 at 11:38
  • 2
    possible duplicate of [Longest chain of elements from list in Python](http://stackoverflow.com/questions/10548712/longest-chain-of-elements-from-list-in-python) – Jongware Dec 26 '13 at 11:43
  • What about cycles? What happens if there is a chain of `rabbit tiger rabbit tiger ...`? – rlms Dec 26 '13 at 12:03
  • 1
    why the downvote? Apart from the uninformative title, the question is all right IMO. – Krab Dec 26 '13 at 12:06

1 Answers1

3

If you think of your words as vertices of a graph, then the edges of this graph are between the words which can be connected together.

                                    cat
                                       \
                   giraffe - elephant - tiger - raccoon
                 /          /          /
         hedgehog      mouse        ant

You're then trying to find the longest path in a directed and potentially cyclic graph. It can have multiple correct solutions. The brute-force approach which may work for small-enough sets is to enumerate all possible paths and pick one of the longest. This can be optimized with dynamic programming, which is a fancy name for caching already computed parts.

Krab
  • 2,118
  • 12
  • 23
  • And this seems to be a duplicate of this answer: http://stackoverflow.com/a/10576639/218508 – Krab Dec 26 '13 at 12:03