wu :: forums
« wu :: forums - Maximum Rectangle »

Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 4:16am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: Grimbal, ThudnBlunder, william wu, Eigenray, SMQ, towr, Icarus)
   Maximum Rectangle
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Maximum Rectangle  (Read 1028 times)
sateesp
Newbie
*





   


Gender: male
Posts: 35
Maximum Rectangle  
« on: Jul 31st, 2010, 5:19am »
Quote Quote Modify 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: male
Posts: 13730
Re: Maximum Rectangle  
« Reply #1 on: Jul 31st, 2010, 3:01pm »
Quote Quote Modify 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: male
Posts: 7526
Re: Maximum Rectangle  
« Reply #2 on: Aug 1st, 2010, 3:11pm »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board