There's more than one way to do things | |
PerlMonks |
Re: Multi-token word chains (was The Threeve Game)by blokhead (Monsignor) |
on Feb 11, 2010 at 00:53 UTC ( [id://822554]=note: print w/replies, xml ) | Need Help?? |
FYI: The problem of finding the longest "chain" is NP-complete, even in the case of just 2-word phrases, as can be seen from a reduction from the longest path problem in directed graphs.
Each single word is a vertex, and there is an edge from word A to word B if "A B" is a valid 2-word phrase. A path in the graph corresponds to a "chain" of valid 2-word phrases in this game, and we want to find the longest one. blokhead
In Section
Meditations
|
|