8
3
Johnny is trying to create crossword puzzles, but he is having difficulty making words match each other.
He has come up with several simple word rectangles: that is, groups of words that form a rectangle where all horizontal and vertical paths form a word.
//2x2
PA
AM
//2x3
GOB
ORE
//3x3
BAG
AGO
RED
//3x4
MACE
AGES
WEES
However, to make a good puzzle, he needs some word rectangles that are somewhat larger than 3x4. Instead of agonizing over the arrangement letters for hours, Johnny would prefer to have a program that does this for him--and in as few characters as possible, because long blocks of code are extremely intimidating for casual programmers like Johnny.
Given
- a text file dictionary where words are separated by newlines in alphabetical order,
- input specifying the number of rows and columns in the words rectangle (which can be provided however is most convenient in your programming language of choice)
generate at least one word rectangle. If it is not possible to generate a word rectangle with the given lexicon and dimensions, the program need not have defined behaviour. It is not necessary for the program to be able to generate rectangles which contain more than 64 letters or have dimensions that exceed 8 in either direction. The program should be able to complete in a reasonable amount of time, say, in thirty minutes or less.
EDIT: If you are doing an NxN rectangle, you are permitted to use a smaller dictionary file that only contains words that have a length of N letters.
I may be able to adapt the code I wrote for a Java4k game.
– Peter Taylor – 2011-05-12T07:03:24.8301I'm curious if anyone has an implementation that can generate an 8x8 from that word list in under ½ hour. – MtnViewMark – 2011-05-14T06:05:54.177
@MtnViewMark If not, I'll be willing to lower the size requirement. Even so, I think that Keith's implementation could be made quite a bit faster if he could do some checking to reduce the number of possiblities. – Peter Olson – 2011-05-14T14:44:42.760
and all words must be different? – Ming-Tang – 2011-05-14T23:27:43.360
@shinkirou No, there can be duplicate words in the rectangle. – Peter Olson – 2011-05-15T04:10:37.567
Did anyone manage to generate a solution grid greater than 6x6 in under ½ hour? – MtnViewMark – 2011-05-15T16:07:08.683
@MtnViewMark, 7x6 in 21 seconds. But I left it running for 5 hours looking for 8x8 without finding anything. I have an idea for a reduction to exact set cover which I want to try. – Peter Taylor – 2011-05-15T21:46:22.837
@Peter - That's fast.. or do you just a blazing computer on your desk? What is the implementation in? And are you using something other than one of the two algorithms represented here? – MtnViewMark – 2011-05-15T22:52:20.180
@MtnViewMark, 2.5GHz probably doesn't count as "blazing" nowadays. Implementation in Java. Prefix-based with heuristics; I think it's a bit more complex than the algorithms posted, although I can't decipher the Python one entirely. – Peter Taylor – 2011-05-16T06:04:58.997
@Peter - the Python one is the same algorithm as the awk one: Recursive enumeration of all possible rows combinations, pruning on if the columns are viable prefixes. My Haskell solution enumerates by alternating filling out rows and columns, and now prunes by viable prefixes as well. Can you share your method? – MtnViewMark – 2011-05-17T04:17:21.987
1@MtnViewMark, rather than testing merely whether a prefix is viable I use a trie which stores the number of children under each node to give a heuristic for which continuations are most likely to give a solution. (I then pick one at random weighted by the heuristic - I should probably try just picking the best candidate, since variability of results isn't explicitly in the spec). I'm testing the reduction to set cover, solving with Knuth's dancing links, on the basis that it applies heuristics globally rather than to prefixes, but so far not promising. Maybe there's a better reduction. – Peter Taylor – 2011-05-17T08:42:57.157