Author |
Topic: Maximum Rectangle (Read 1038 times) |
|
sateesp
Newbie
Gender: 
Posts: 35
|
 |
Maximum Rectangle
« on: Jul 31st, 2010, 5:19am » |
 Quote  Modify
|
Given two lists List1 & List2. List1 contains M word each of size x. List2 contains N words of size y. Give an Algorithm for constructing rectangle of size x*y, where each row in the rectangle is word from the List1 and each column in the rectangle is a word from List2.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Maximum Rectangle
« Reply #1 on: Jul 31st, 2010, 3:01pm » |
Quote Modify
|
A simple approach would be to alternately pick a word for a column and for a row, and backtrack if you get stuck.
You could first filter the set of words for each row/column for ones that for each letter have a word in the other list that matches on that position.
And in that line, you could for (say) each row, find for each word, for each character the set of all words from the column list that match in that position, and then find y such tuples of sets that have a non-empty intersection.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Maximum Rectangle
« Reply #2 on: Aug 1st, 2010, 3:11pm » |
Quote Modify
|
Maybe something like this:
1. Build for each row and each column the set of words that are possible (it starts with the full set). And call the following search() as a subroutine
search():
2. Build for each cell the set of characters that is still possible, meaning it appears at this position for a word in the row set and one in the columns set.
3. Remove from the row/column sets the words that are not compatible with all cells. (i.e. if they cannot cross any possible word in that position).
4. If any list becomes empty, return, there is no solution
5. If any word was removed in point 3, repeat from point 2.
6. If there is exactly 1 word left in each list, display the solution and return.
7. if not, take the list L that has the most words, and for each word w in L, create a new set of lists by copying the existing lists but replacing L by {w} and call search() on that.
It should work. It might be a bit heavy on storing word lists and copying them in each recursive call.
One obvious optimization is in the initial elimination, where the lists are identical for each row resp. each column.
|
| « Last Edit: Aug 1st, 2010, 3:17pm by Grimbal » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print