Author |
Topic: words in a grid (Read 1165 times) |
|
witee
Newbie
Posts: 48
|
 |
words in a grid
« on: Sep 22nd, 2010, 8:48am » |
 Quote  Modify
|
Given a dictionary of millions of words, write a program to find the largest possible rectangle of letters such that every row forms a word (reading left to right) and every column forms a word (reading top to bottom).
how to do this
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: words in a grid
« Reply #1 on: Sep 23rd, 2010, 2:34pm » |
Quote Modify
|
I think you have to try from the largest down until you manage to build one.
To try one size I'd try a first row and first column and fill by adding more rows and columns.
Obvious optimizations would be to split your dictionary by size and compute for each word size and position in the word the set of possible letters.
When trying to build a mxn rectangle, assign a full set of of possible words (of the proper size) to each row and column.
Start with a process of elimination: For each cell find which letter is possible according to the words of the corresponding row. Then remove any word from the column where any letter falls in a cells where it is not matched by a row word.
Repeat but exchanging the role of rows and columns.
Continue until no more word can be removed.
Then choose a word from the smallest list of words for any row and column (but with >1 word). Place that word and restart the whole process (elimination and choosing a word) recursively.
You end up either with one word in each row and column or with a row or column with zero words. In the first case you have a solution, in the second case you have to backtrack to the last choice you did. remove the word you chose from the list and try another word.
I have no idea if that is fast enough to try all sizes from the max size down to where there is a solution, but I believe it works.
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: words in a grid
« Reply #2 on: Sep 29th, 2010, 6:03am » |
Quote Modify
|
on Sep 22nd, 2010, 8:48am, witee wrote:Given a dictionary of millions of words, write a program to find the largest possible rectangle of letters such that every row forms a word (reading left to right) and every column forms a word (reading top to bottom).
how to do this |
|
Can you give an example, it will be helpful in under standing the problem.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print