wu :: forums - Print Page


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

        riddles >> cs >> GRID Problem
        
(Message started by: witee on Jul 22^nd, 2010, 11:55am)

Title: GRID Problem
Post by witee on Jul 22^nd, 2010, 11:55am

Each cell of an N x N grid is either a 0 or a 1. Given two such N x N grids, the initial grid and the final grid. There is a button against each row and each column of the initial N x N grid. Pressing a row-button toggles the values of all the cells in that row, and pressing a column-button toggles the values of all the cells in that column. You are required to find the minimum number of button presses required to transform the grid from the initial configuration to the final configuration, and the buttons that must be pressed in order to make this transformation.
Most efficient solution is required

Title: Re: GRID Problem
Post by singh_sukhu on Jul 22^nd, 2010, 8:43pm

I don't think all initial configurations can be necessarily converted to final configurations.
Consider changing

1	0
0	0

0	0
0	0

Title: Re: GRID Problem
Post by towr on Jul 23^rd, 2010, 12:32am

XOR the starting state with the desired end state, then apply http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1253641163;start=2#2

Title: Re: GRID Problem
Post by witee on Jul 23^rd, 2010, 6:00am

I m not getting the solution..can u provide some more explanation or Pseudo code??

Title: Re: GRID Problem
Post by Grimbal on Jul 23^rd, 2010, 12:19pm

Given a[i,j] is the starting grid, b[i,j] is the ending grid.
compute c: c[i,j] = a[i,j] xor b[i,j].

for j=0 to max
if c[0,j]=1, reverse column j
for i=1 to max
if c[i,0]=1, reverse row i

That is one way. If that amounts to reversing more than max times, then you should start with reversing row 0.

This is based on the fact that just setting the first row and the first column right determines almost completely what rows and column to reverse. The only choice is whether or not to reverse the first row.

Title: Re: GRID Problem
Post by birbal on Jul 24^th, 2010, 3:57am

on 07/22/10 at 20:43:17, singh_sukhu wrote:

I don't think all initial configurations can be necessarily converted to final configurations.
Consider changing

1	0
0	0

0	0
0	0

Yes, its not possible to convert every configuration to every other configuration.
And as Grimbal has explained, if it is not possible, you will come to know before 2*max steps.

Title: Re: GRID Problem
Post by witee on Aug 1^st, 2010, 10:02pm

@grimbal

what is the max in ur algo??

Title: Re: GRID Problem
Post by birbal on Aug 1^st, 2010, 11:19pm

on 08/01/10 at 22:02:46, witee wrote:

what is the max in ur algo??

max is N, the dimension of the grid.

Title: Re: GRID Problem
Post by Grimbal on Aug 2^nd, 2010, 1:00pm

Uh, yes, sorry for the confusion.

Title: Re: GRID Problem
Post by newb on Aug 7^th, 2010, 6:08am

It may sound dumb.
But still I am not able to get it full extent.

:-/

Please anyone help me out.
at least with a example.
say for ex:
0 0 0
1 1 0
1 1 0
to
1 1 0
1 1 1
1 1 1

Title: Re: GRID Problem
Post by Grimbal on Aug 8^th, 2010, 2:02pm

First establish what you need to change (xor the two):
1 1 0
0 0 1
0 0 1

Case A: you don't toggle row 1
1 1 0
0 0 1
0 0 1
To clear the 1st row, you need to toggle columns 1 and 2. (2 moves)
0 0 0
1 1 1
1 1 1
To clear the 1st column, you need to toggle rows 2 and 3. (2 moves)
0 0 0
0 0 0
0 0 0
All cells are 0, so it is a solution. The solution: (c1, c2, r2, r3) in 4 moves.

Case B: you do toggle row 1 (count 1 move)
0 0 1
0 0 1
0 0 1
To clear the 1st row, you need to toggle columns 3 only. (1 move)
0 0 0
0 0 0
0 0 0
To clear the 1st column, you don't need to toggle anything.
0 0 0
0 0 0
0 0 0
All cells are 0, so it is a solution. The solution: (r1, c3) in 2 moves.

B is shorter than A, so retain solution B: (r1, c3).

Actually case B is the complemennt of case A (i.e. in B you toggle the rows/columns you don't toggle in case A). B is preferable to A when the number of moves in A is >N.