wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Maximum Rectangle
        
(Message started by: sateesp on Jul 31^st, 2010, 5:19am)

Title: Maximum Rectangle
Post by sateesp on Jul 31^st, 2010, 5:19am

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.

Title: Re: Maximum Rectangle
Post by towr on Jul 31^st, 2010, 3:01pm

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.

Title: Re: Maximum Rectangle
Post by Grimbal on Aug 1^st, 2010, 3:11pm

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.