The part of the original puzzle that made it difficult for me to envision a computer solution to was where they give arbitrary topics. For example, "US States". Obviously, this has 51 possible answers (ok, really 50 - I'm including Canada :-P), a subset of which would be valid depending on the maximum length of the word. Programmatically solving that would be a challenge unto itself. Now, if you're going to generate categories yourself, you could define it to be solvable.
In the original post, my wife had looked for answers in each category trying to maximise the count of 'a's, thinking that would get the best possible score. We don't know if 'e' would have been a better choice, since we didn't try to optimise that. However, a more general application could possibly handle many more answers by having categories with all possible answers in some sort of database. For example, if there is an on-line crossword dictionary, crossword clues make great categories, which is fitting since the original problem came from a puzzle book including crosswords, and then querying from said dictionary should be a relatively solvable problem. Of course, this blows "maximum words in a category" out of the water :-) Then again, even a crossword dictionary won't have every possible answer - just ones used in crosswords. I wouldn't expect a category of "historical English Monarch" to have every monarch ever in the dictionary...
Your assumption about points is correct. Every letter in all words counts.
Of course, you're free to define your own puzzle that is loosely based on the above. You could define your own categories as groups of words in each category (having overlapping words where they can only be used in one category does make it more interesting). Or, for example, you could try varying the score for each letter, especially since a computer is doing the addition anyway. For example, what happens if each letter counts for double the previous? How about each letter counts for its position in the Fibonacci sequence? Maybe each letter gets its own fibonacci sequence, and the last number for each letter counts (e.g., if there are 2 a's and 3 b's, the a's get 1 point as the second number in the sequence, and the b's get 2 points as the third number in the sequence)? Do these variations really make for any difference in tactic? I doubt it, but that'd be like a premature optimisation that'd need benchmarking :-)
| [reply] |
Tanktalus,
I agree that writing a program to find words that fit a category is a bigger challenge all unto itself. That's why I took your approach of assuming the words that fit were already known. My categories will just be cat 1 .. N. I just want variation to test the robustness of any possible solution. Using an existing database is also a possible approach but goes beyond the scope of what I am intending to do.
Regarding the "maximum words in a category". That is a configurable parameter that I envision being used to bound a given puzzle so that an implementation has a realistic chance of solving for the "best" combination of words. On the other hand, if you are going to go with a heuristic approach then it may not matter - but being configurable allows the user to make that decision.
Regarding making variations on the rules for the purposes of exploration - sure, but I wanted to make sure I had the basic idea since your original post left me more than a little confused. Now that I know I am on the right track I can think about it further. Thanks!
| [reply] |