wu :: forums - Print Page


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

        riddles >> cs >> locks and switches
        
(Message started by: Aryabhatta on Mar 8^th, 2004, 5:04pm)

Title: locks and switches
Post by Aryabhatta on Mar 8^th, 2004, 5:04pm

There is a lock which is an N by N grid of switches. Each switch can be in one of two states (on/off). The lock is unlocked if all the switches are on. The lock is built in such a way that, if you toggle some switch, all the switches in its row and its column toggle too. Give an algorithm which, given N and a configuration of the N^2 switches, will tell you whether the lock can be unlocked by a sequence of switch toggles.

Note 1: Can be done in O(N^2) time and O(1) space.
Note 2: You just need to tell if a sequence which unlocks the lock exists (and not the actual sequence)

Title: Re: locks and switches
Post by John_Gaughan on Mar 8^th, 2004, 10:04pm

I believe that most combinations are possible to unlock. This reminds me of a Rubik's cube, in fact, I've seen puzzles similar to this before. I think the solution has to do with if there is an odd or even number of switches turned on and whether n² is even or odd, or maybe it is 2n-1... I don't remember...

Title: Re: locks and switches
Post by Aryabhatta on Mar 9^th, 2004, 11:53am

John_gaughan wrote:
>I believe that most combinations are possible to unlock. This
>reminds me of a Rubik's cube, in fact, I've seen puzzles
>similar to this before. I think the solution has to do with if
>there is an odd or even number of switches turned on and
>whether n2 is even or odd, or maybe it is 2n-1... I don't
>remember...

For odd N, a lot less than half the combinations are unlockable. This is similar (atleast in problem statement) to the lights out puzzle..

Title: Re: locks and switches
Post by kellys on Mar 9^th, 2004, 8:14pm

Some observations:
[hide]
Thinking of the question as adding matrices in the field with two elements:
1) It doesn't matter what order you toggle the switches in. So,
2) You might as well assume that you toggle a switch no more than once, since two toggles gets you right back to where you started.
3) You also should work backwards: start with all of the switches on, and see which configurations you can get to.
[/hide]

Title: Re: locks and switches
Post by NotMe on Mar 11^th, 2004, 12:24pm

It seems to me that if all switches in one row/column are unlocked, then there are two possibilities:
1. The rest are unlocked as well.
2. The rest is a mix of locked/unlocked.

Proposition 1: it's impossible in the case #2 to unlock the lock.

I think I have a proof of it in my head, but I may be wrong; OTOH, I'm too lazy to write it here.

Now, if you agree with the Proposition1, you have a solution to the problem right there.

Title: Re: locks and switches
Post by Aryabhatta on Mar 15^th, 2004, 11:41am

Hint: [hide] For N even we can always unlock the lock [/hide]

Title: Re: locks and switches
Post by NotMe on Mar 17^th, 2004, 6:24pm

I'm probably missing something here, but how do you unlock this one:
1 1
1 0

1=ON 0=OFF
?

Title: Re: locks and switches
Post by towr on Mar 18^th, 2004, 12:36am

11
10

10
01

11
11

Title: Re: locks and switches
Post by NotMe on Mar 18^th, 2004, 9:10am

Thank you, towr. You know what it means? - It means that my little theory falls apart!

Title: Re: locks and switches
Post by towr on Mar 18^th, 2004, 10:53am

You're welcome ;D

I'm still not quite sure how to handle this problem..
Obviously if you can (using a certain sequence) switch off/on any square without affecting the rest of the grid, then you can switch off the whole grid (on square at a time if you want to do it the slow way). So based on Aryabhatta's hint this should hold for even N, the question is whether that's any easier to prove..

Title: Re: locks and switches
Post by kraj on Mar 18^th, 2004, 11:45pm

Code:

//
// There is a lock which is an N by N grid of switches. Each switch can be in one of two states (on/off). The lock is unlocked if all the switches are on. The lock is built in such a way that, if you toggle some switch, all the switches in its row and its column toggle too. Give an algorithm which, given N and a configuration of the N^2 switches, will tell you whether the lock can be unlocked by a sequence of switch toggles.
//
//Note 1: Can be done in O(N^2) time and O(1) space.
//Note 2: You just need to tell if a sequence which unlocks the lock exists (and not the actual sequence)

using System;

public class ToggleSwitch
{
public static void PrintSwitches( int[][] switches, int x, int y)
{
for(int i=0 ; i <x ; i++ )
{
for(int j=0; j < y; j++ )
{
Console.Write( switches[i][j] + " " );
}
Console.WriteLine();
}
}

public void Toggle(int[][] switches, int x, int y , int size )
{
int state = switches[x][y];

for( int i=0; i< size; i++ )
switches[i][y] = ( switches[i][y] == 1 ? 0 : 1 );

for( int j=0; j< size; j++ )
switches[x][j] = ( switches[x][j] == 1 ? 0 : 1 );

switches[x][y] = ( state == 1 ? 0 : 1 );
}

public static void Main(string[] args)
{
int max = 5;

int[][] switches = new int[max][];
int i,j;

ToggleSwitch ts = new ToggleSwitch();

for(i=0;i<max;i++) switches[i] = new int[max];

for(i=0;i<max;i++)
for (j=0;j<max;j++) switches[i][j] = 0;

PrintSwitches( switches, max, max );

Console.WriteLine();

for ( i=0 ; i <max ; i++ )
for ( j=0; j <max; j++ )
ts.Toggle( switches, i , j, max );

PrintSwitches( switches, max, max );
}
}

Title: Re: locks and switches
Post by towr on Mar 19^th, 2004, 12:40am

What's that supposed to do?

Title: Re: locks and switches
Post by kraj on Mar 19^th, 2004, 1:38am

It starts with a N x N array assigned with 0. The algorithm just toggles each cell once. The end result is every cell as 1.

Title: Re: locks and switches
Post by towr on Mar 19^th, 2004, 2:17am

ah..
Well, at least that means that it doesn't matter wether we get to all unlocked or all locked state. So if a certain state is solvable, the inverse is as well.

To solve the grid when N is even, you can switch off any single square by toggling every square in the same column and row.
This means the square itself gets flipped 2N-1 times, each other square in the same row or column N times (which is even, so they are in their original state), and every other square twice.

That still leaves the case for odd N

Title: Re: locks and switches
Post by Aryabhatta on Mar 19^th, 2004, 4:11pm

Right towr. So for even N, we have an O(1) algorithm ;D

Hint for odd n: [hide] X = n-1 can be cOnsideRed. [/hide]

Title: Re: locks and switches
Post by kraj on Mar 19^th, 2004, 9:06pm

For N being odd, we can just flip any row or column

Title: Re: locks and switches
Post by hsp246 on Apr 1^st, 2004, 10:28pm

Answer:

For n odd, say n=2k+1, first ignore the first row and first column. That leaves us a 2k by 2k square which we know we can always unlock.

Also, note that when we toggle any of the switch in the 2k by 2k square by the aforementioned operation (toggling all the switches in its row and column in the 2k by 2k square), the state of the switch on the first row and column remains unchanged, since they are either toggled 2k times or not toggled at all.

So the question is whether we can turn off all the switches on the frist row and first column. If we can do that, we can take care of the remaining 2k times 2k switches without affecting the state of those in the first row and column.

We can assume the corner element is off, since otherwise we just toggle it.

Now count the number of switches that are "on" at the first row and column. The claim is that if their (odd/even) parity matches,
it can be unlocked, otherwise, it cannot.

Therefore, the algorithm is the check the parity of the "on" switches on the first row and column. Repeat that for all the four corners of the matrix. If the check passes for one of the cases, output "YES". Otherwise, output "NO"

The claim is true because the odd/even parity relationship is preserved no matter which switch you toggle. Since to unlock you need to reach a state where the parity is the same, you have to start with the same relationship.

If their parity is the same, we can always find a sequence. Consider two cases:

i) If the number of "on" swithces is the same on both row and column, we can simultaneously turn a row-switch and column-switch off by toggling their "common affecting" switch.

ii) If the number on the row is greater than column, then we can turn the one light on the row off and turn on one light on the column simultaneously. Since the row-column parity is the same, eventually they will have the same number of "on" switches.

Therefore the algorithm is simply parity checking

Title: Re: locks and switches
Post by Aryabhatta on Apr 2^nd, 2004, 11:53am

hsp246 wrote:
>For n odd, say n=2k+1, first ignore the first row and first
>column. That leaves us a 2k by 2k square which we know
>we can always unlock.
>
>Also, note that when we toggle any of the switch in the 2k
>by 2k square by the aforementioned operation (toggling all
>the switches in its row and column in the 2k by 2k square),
>the state of the switch on the first row and column remains
>unchanged, since they are either toggled 2k times or not
>toggled at all.

Not true.

For instance, n = 3.

0 0 0
0 0 0
0 0 1

Flipping the middle switch changes it to

0 1 0
1 1 1
0 1 1

Note that the bottom right 2x2 is unlocked now. While the first row and column have changed. (It does not matter how you switch the 2x2 on, you will always end up with the above matrix)
In fact the above cannot be unlocked, while your algorithm returns YES for this.

You are on the right lines though...

Title: Re: locks and switches
Post by hsp246 on Apr 3^rd, 2004, 10:24am

oops you caught me. ;) Let me give it another try:

For odd case, do the following:

For each entry (i,j), sum up all the entries in row i and column j (not counting the entry (i,j) itself), check its parity.

If the parity is even for all (i,j) return YES, otherwise return NO

It works because such parity is always preserved for each (i,j) no matter which switch you toggle every time.

The naive algorithm will do that in O(n^3) time. To do it in O(n^2), we compute the total sum for each row and each column, which takes O(n^2) time. To compute the parity info for each (i,j), just add up total sum of row i and column j and it will give the parity info, since the entry is added twice and will be toggled to 0

Title: Re: locks and switches
Post by grimbal on May 21^st, 2004, 8:14pm

If you need to sum rows for every (i,j), the method is O(N³).

In fact, you only need to check that every row and every column has an even number of switches on.

Title: Re: locks and switches
Post by Aryabhatta on May 22^nd, 2004, 12:53am

on 04/03/04 at 10:24:30, hsp246 wrote:

Sorry hsp246, I had completely forgotten that I had posted this one. ~~Your solution seems right.~~

You need to prove the sufficiency of the condition you state. i.e if the value for each (i,j) is even, the lock is unlockable. What you have shown is that if the lock is unlockable then the value for each (i,j) must be even.

Also, the algorithm you gave uses O(N^2) space.

Again, sorry for not responding earlier.

Title: Re: locks and switches
Post by Aryabhatta on May 22^nd, 2004, 12:56am

on 05/21/04 at 20:14:20, grimbal wrote:

If you need to sum rows for every (i,j), the method is O(N³).

In fact, you only need to check that every row and every column has an even number of switches on.

For N odd:

Consider the case when all are on. Every row and every column has an odd number of switches on..

And consider the case when all are off. Every row and every column has an even number of switches on..

Either case, the lock is unlockable..

Also, hsp246's solution can be done in O(N^2) time, the way he/she described it.

The space usage is more though.

Title: Re: locks and switches
Post by grimbal on May 22^nd, 2004, 9:41am

Hm... that happens when you post at 5:41. Just a small correction, for N odd:

Either all rows and columns must be even or all rows and columns must be odd. [1]

The condition is necessary because every action will toggle an odd number of switches in each row and each column.

Is the condition sufficient? If the condition [1] is met, we can assume every row and column is odd. If they are all even, just press any switch, and they all become odd.

Then consider what happens when you switch 4 switches at the corners of a rectangle. The result is that only these 4 switches change state. Note also that it does not change the parity of any row or column.

So, from a state where every row is odd (and therefore where the number of OFF switches is always even), you can turn a pair of switches ON if you toggle the same switches in the last row. Working by pairs, you can turn on all switches in the top row. Then, doing the same for all other row, you can turn ON each switch in every row, except the last row. But when you have done all but the last row, the condition of the columns being odd implies that the switch on the last row are all ON.

So, if the condition [1] is met, you can turn all switches ON and unlock the lock.

Title: Re: locks and switches
Post by Aryabhatta on May 22^nd, 2004, 11:27am

on 05/22/04 at 09:41:03, grimbal wrote:

N is odd.

The condition [1] you described is necessary and sufficient.

Let me rephrase the condition:
[1] If R_i is the parity of row i and C_j is the parity of row j, the condition is R_i = C_j for any i,j.

That the condition is necessary, you noted.
It is also sufficient. This can be seen from hsp246's post.

Here is another proof that the condition is sufficient.

Toggling any switch causes all the R_i's and C_j's to flip simultaneously. This means that condition [1] is invariant under switch toggles. (i.e if it was true before a toggle, it remains true after a toggle)

Now consider the (N-1)x(N-1) sub-grid. All the switches in this grid can be turned on since N-1 is even. We are left with the bottom row and the rightmost column. The value of R_i is the state of the ith switch in the last row. The value of C_j is the state of the jth switch in the righmost column (except possibly R_N and C_N). Now if condition [1] was satisfied for the original grid it must be satisfied for this grid too. It implies that either the switches of the last row and column are all on or the switches of the last row and column are all off. In the former case, the lock is unlocked. In the latter case you can unlock the lock by flipping the bottom right switch.

This proves that the condition is sufficient too.

Title: Re: locks and switches
Post by Aryabhatta on May 22^nd, 2004, 5:11pm

on 05/22/04 at 11:27:35, Aryabhatta wrote:

It is also sufficient. This can be seen from hsp246's post.

I just reread hsp246's post.. I don't think the sufficiency of the condition is proved.

Sorry for the confusion. It's been a long time since i thought about this problem.

hsp246, you have only proved the necessity of the the condition that you state. Not the sufficiency, which is required. (otherwise you may be saying YES to inputs for which the answer is actually no).