CODEWITHSUNDEEP
python
sorted
sorted

Reputation: 19

python - Implementing a game

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:

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.

Upvotes: 0

Views: 469

Answers (1)

Krab
Krab

Reputation: 2148

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.

Upvotes: 3

Related Questions