python - Implementing a game

Question

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.

"I didn't want to post my code because I wanted to start over." -- Why not? — Mr. Polywhirl
– Mr. Polywhirl, Commented Dec 26, 2013 at 11:38
possible duplicate of Longest chain of elements from list in Python — Jongware
– Jongware, Commented Dec 26, 2013 at 11:43
What about cycles? What happens if there is a chain of rabbit tiger rabbit tiger ...? — rlms
– rlms, Commented Dec 26, 2013 at 12:03
why the downvote? Apart from the uninformative title, the question is all right IMO. — Krab
– Krab, Commented Dec 26, 2013 at 12:06

Krab · Accepted Answer · 2013-12-26 12:00:22Z

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.

answered Dec 26, 2013 at 12:00

Krab

2,14812 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Krab Over a year ago

And this seems to be a duplicate of this answer: stackoverflow.com/a/10576639/218508

Collectives™ on Stack Overflow

python - Implementing a game

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related