4
As I'm sure many of you know, synonyms can range from very similar to not-so-similar-but-I-can-see-how-it's-similar. It's common for dictionaries to use "See also" to denote occurrences of words that have especially good synonyms. Thesauruses (Thesauri?), on the other hand, list every word that is remotely close in definition. It got me thinking: Is it possible to construct one single "See also" loop that encompasses an entire dictionary?
Of course, you'd have to stretch definitions at some point. Switches between parts of speech would also have to happen if you intend to make your loop large. The only rules are that each must reference EXACTLY the word after it only with respect to spelling, and the final word must reference the first word. For example:
- Huge: See also Giant
- Giant: See also Titan
- Titan: See also Behemoth
- Behemoth: See also Beast
- Beast: See also Creature
- Creature: See also Pig
- Pig: See also Gorge
- Gorge: See also Void
- Void: See also Free
- Free: See also Unrestricted
- Unrestricted: See also Huge
That was just thrown together, but I think it gets the idea across. You can go for "words" that are really multiple words, so long as it is the type of thing you'd find in a dictionary.
Some helpful resources (let me know of any others):
And that's it! As for going above and beyond, it would be cool to see some kind of visualisation of your loop, possibly making each part of speech a different color or something. Use your imagination! It will be interesting to see what kind of stuff you might come up with.
Winning criteria: The program which produces a loop that contains the largest number of unique words will be deemed the winner.
John O.
Posted 2014-04-19T11:41:10.777
Reputation: 41
so, we're asked to fetch an online resource (which probably won't like us to do so), parse it into a huge graph, and find a hamiltonian cycle or prove there is none (which will take a lot of time)? What are the winning criteria? Popularity? Even if so, what should we strive for? – John Dvorak – 2014-04-19T11:47:31.817
Winning criteria is the longest loop, as long as it follows the rules. I'm going to be honest that I don't know much about fetching information from online resources, but I didn't think it would be too much of any issue. I'm willing to bet that tons of websites and programs already scour spelling/definition databases constantly. – John O. – 2014-04-19T11:52:14.803
2
I don't think there have been questions about the largest cycle in a graph before; and the issue of getting a source graph is fixable using the Moby thesaurus, but there are two major issues: one, any complete solution is unlikely to finish running in your lifetime; and two, that means that your proposed scoring system is hard to evaluate. You could perhaps ask for the longest cycle found within a time limit, but then you run into problems with non-determinacy and with different performance charactistics on different computers.
– Peter Taylor – 2014-04-19T11:54:29.500I expected there to be issues like this... I wanted people to try and come up with solutions that would actually be possible with the equipment they might have. I know there's probably a "perfect" way of doing this that would require crazy amounts of computing and time, but I'd just ask that people use their best judgment about the solution they choose. I agree that there's no good way of normalizing the score for computer speed, but I can't think of any other good way to choose a winner besides simple length of the loop. – John O. – 2014-04-19T12:04:02.720
2This question appears to be off-topic because it is an English contest, not a programming contest. – user12205 – 2014-04-19T12:23:08.030
1Is it necessary to specify that the challenge is to "Create a program that will..."? I figured that was heavily implied. – John O. – 2014-04-19T12:24:32.077
2"Of course, you'd have to stretch definitions at some point." Is it even possible to create a program that can stretch definitions? – user12205 – 2014-04-19T15:56:24.027