Re: The Threeve Game
by planetscape (Chancellor) on Feb 10, 2010 at 01:19 UTC
|
I like "Christmas tree frogs", which I combined ~10 years ago when making a holiday card for a friend, and which came true last Christmas!
| [reply] [Watch: Dir/Any] |
Multi-token word chains (was The Threeve Game)
by Limbic~Region (Chancellor) on Feb 10, 2010 at 01:40 UTC
|
pileofrogs,
This really isn't on topic, so let me suggest turning it into a challenge that is.
Assume we have a list of multi-token words. In fact, assume that it is obtained using the following code:
#!/usr/bin/perl
use strict;
use warnings;
use WWW::Mechanize;
my $mech = WWW::Mechanize->new(autocheck => 1);
for ('a' .. 'z') {
my $url = "http://wordlist.com/index-$_.htm";
eval { $mech->get($url) };
if ($@) {
warn "Unable to get link for letter '$_': $@\n";
next;
}
for my $link ($mech->links) {
my $word = $link->text;
next if ! $word || index($word, ' ') == -1;
print "$word\n";
}
}
The challenge is to make the longest chain of multi-token words where the end of one word overlaps the beginning of the next word by at least one token. Each word may only be used once in the chain. Here is an example:
area code
code of ethics
ethics committee
Here are some (likely not all) edge cases that I thought of.
- Overlapping tokens must match exactly - for instance, 'area code' can't be followed by 'coded message' because 'code' ne 'coded'
- Each new word must increase the chain length by at least 1 token. For instance, you can't claim 'bloody murder' follows 'yell bloody murder' because 'bloody murder' is completely within the preceding word
I realize that this particular list stinks but I couldn't find a better one. If you use an alternate source, please link to it so that others may compete using the same list. Oh, I am pretty sure there is a fairly well known computer science problem hidden within so heuristics solutions are likely necessary.
It should be fairly obvious, but here is a hint if you are having a hard time dealing with such a large list:
| [reply] [Watch: Dir/Any] [d/l] [select] |
|
| [reply] [Watch: Dir/Any] |
|
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.
| [reply] [Watch: Dir/Any] |
|
blokhead,
FYI: The problem of finding the longest "chain" is NP-complete
Yes, I know which is why I said "Oh, I am pretty sure there is a fairly well known computer science problem hidden within so heuristics solutions are likely necessary." See for instance, Not Quite Longest Path Problem. I am really not interested in someone finding the longest path but someone who can find a long path that is longer than everyone else and examine their heuristic solution.
| [reply] [Watch: Dir/Any] |
|
Add one more level to this by creating the largest loop that you can.
The basic framework above, but also have the last token of the last set overlap with the first token of the first set.
Not thinking of any right off the bat. Perhaps after my coffee I will update this node. Oh wait - "implementation is left as an exercise for the reader." ;-)
It is said that "only perl can parse Perl." I don't even come close until my 3rd cup of coffee. --MidLifeXis
| [reply] [Watch: Dir/Any] |
Re: The Threeve Game
by zentara (Archbishop) on Feb 10, 2010 at 10:51 UTC
|
I'm sure this game has been invented by a thousand other folks beforeA recent tv commercial, is reminiscent of your game...it uses chars in words rather than words in phrases. Google for Scrabble Slam if you are interested. Can you imagine if programmers were in charge of common word usage? :-) We would have words like choc_ic. The underscore chars in the game are like wild cards. ;-)
| [reply] [Watch: Dir/Any] |
|
Can you imagine if programmers were in charge of common word usage?
...
<truth>programmers are in charge of everything.</truth>
$,=qq.\n.;print q.\/\/____\/.,q./\ \ / / \\.,q. /_/__.,q..
Happy, sober, smart: pick two.
| [reply] [Watch: Dir/Any] [d/l] [select] |
Re: The Threeve Game
by wabewalker (Initiate) on Feb 15, 2010 at 12:57 UTC
|
Here in the UK, a common variant is to display words 1 and 3 and let you guess word 2. For example, Chris Maslanka's puzzles (known as "Missing Links") in last Saturday's Guardian has "crying hound", the solution being "wolf" (crying wolf and wolf hound.) More cunningly, the standard example "bat man" has the solution "he" for "bathe" and "he-man" so he allows concatenations.
I love puzzles and often I find more pleasure coding Perl snippets to solve them than I would solving the puzzle directly, particularly if they involve anything tedious :-). I am sure many fellow monks feel likewise. | [reply] [Watch: Dir/Any] |
Re: The Threeve Game
by jdporter (Paladin) on Feb 12, 2010 at 16:14 UTC
|
They use this device on the tv game show "Wheel Of Fortune" fairly often; they call it "Before And After".
| [reply] [Watch: Dir/Any] |
Re: The Threeve Game
by Lady_Aleena (Priest) on Feb 25, 2010 at 20:54 UTC
|
Just adding a few to the list, though some actually make sense.
- broken heart throb
- cell phone book
- evil eye doctor
- fool's gold mine
- glass ceiling fan
- land mine shaft
- stock market place
- style sheet music
- tabbed browsing habits
- tire iron ore
I need a life.
Have a nice day!
Lady Aleena
| [reply] [Watch: Dir/Any] |
|
| [reply] [Watch: Dir/Any] |
|
Here are a few more, pileofrogs.
- baby shower curtain
- boxed lunch date
-
- curling iron ore (more iron ore)
- down payment options
- dryer sheet music (more sheet music)
- hair dryer sheet (more dryer sheet)
- online auction house
- pool table tennis
- race track ball
- thermal curtain rod
I have another one, but it is a bit risque. Guh! I am a dork tonight. So, how is the database of these coming? :)
Have a nice day!
Lady Aleena
| [reply] [Watch: Dir/Any] |
Re: The Threeve Game
by McDarren (Abbot) on Feb 27, 2010 at 06:04 UTC
|
heh... this is quite fun :)
- slap stick insect
- bachelors party animal
- light house warming
- fast car sick
- golf ball bearing
- dining chair person
- hair cut corners
| [reply] [Watch: Dir/Any] |