Array Recursion

Question

I've got an assignment I can't figure out, any pointers will be much appreciated, it goes like so:

There's a series of light bulbs represented as an array of true/false, there's a switch for every light bulb, by clicking it for any light bulb, you toggle it as well as 2 adjacent ones (1 from left & another 1 from right; if clicked switch's bulb on edge -- only 1 adjacent toggled of course).

What is needed to accomplish is a method that accepts an array of a series of turned on/off light bulbs and another one representing another state of supposedly the 1st array after some switches have been clicked..! So recursion must be used to find out whether there's a combination of switch clicks that will transform array 1 to array 2.

Here's the signature of the method:

public static boolean disco(boolean[] init, boolean[] target)

Will return true if array init can be transformed to target, false otherwise. Method must be static and not use loops & any other static and global variables, only local.

Example:

boolean[] init = {true, false, true, false, true, false};
boolean[] target = {false, true, false, true, false, true};

For above 2 arrays, disco(init, target) will return true because toggling the 1st and 4th bulbs would yield the target state (remember adjacent bulbs being toggled as well).

Any help much appreciated..!!

Answer 1

So here's in words how I would do it:

If there are just less than or equal 3 bulbs left, it's quite easy to check wether they can be switched so that it's correct.

If there are more than three bulbs, do the following:

Check, if the first bulb is correct. If so, go on recursively with the subarray beginning at the second bulb.

If the first bulb is not correct, switch the second bulb (switching the first bulb won't work because previous bulbs are switched back then). Now, the first bulb is correct. Go on with the subarray beginning at the second bulb.

Answer 2

new version

public static boolean disco(boolean[] init, boolean[] target)  
{  
  return recurse(init,boolean,0);  
}  

public static boolean recurse(boolean[] init, boolean[] target, int min)  
{  
  if (min == init.length)  
    if (init == target)  
      return true;  
    else  
      return false;  
  boolean[] temp = "init with a change at min";  
  boolean a = recurse(init, target, min+1);  
  boolean b =   recurse(temp, target, min+1);  
  return a||b;
}  

new new version

I've broken it down to three cases:

Case 1: length %3 = 0
By changing the first bulb and the second bulb, you can affect a change on only the 3rd. Then a change to 4 and 5 will make the 6th the only one changed. We see that we can change every bulb with index divisible by 3.
Working backwards (starting at the end) we can do the same but this time it shows us we can change bulbs with indices (i+1) divisible by 3.
Combining the two, we see that if we want to change an index 0,1 mod 3 we can. But then to change a 2, we simply have to change a neighboring 0,1 pair and then do a change on the middle one. So in all cases these are solvable.

Case 2: length %3 = 1
Just like the first case, but we can affect single changes at 0,2 mod 3, and thus squeeze the 1 mod 3 cases.

Case 3: length %3 = 2
Working forward and backwards only yields cases 0 mod 3. The only remaining moves we have make two changes to the bulbs (since we can ignore any changes to positions 0). Changing a 1 or 2 will reverse the position surrounded by two 0's whereas changing a 0 will swap the parity in adjacent blocks of 1,2 which have a 0 between them (it's easier if you draw it). But what I've shown so far is that the 0's can all be corrected and in any adjacent 1,2 you can fix both if they are wrong without changing anything else. If one is wrong then you propagate a change to an adjacent pair of 1,2. This change can be moved if necessary. What this means is that any even number of errors in 1,2 positions can be fixed, but an odd number cannot. All errors at position 0's can be fixed.

public static boolean disco(boolean[] init, boolean[] target)  
{  
  if (init.length%3 == 0 || init.length%3 == 1)
    return true;
  return recurse(init,target,0, true);
}

public static boolean recurse(boolean[] init, boolean[] target, int index, boolean even)
{
  if (index = init.length)
    return even;
  if (init[index] != target[index] && index%3 != 0)
    even = !even;
  return recurse(init, target, index+1, even);
}

Answer 3

Hint: Let a1, a2, ..., ak, ..., an be the input and b1, b2, ..., bk, ..., bn be the desired output.

You can recursively test the left and right sides and then combine the result. The tricky part is combining the result.

Start with the left side.

1. Test a1, a2, ..., ak, true to b1, b2, ..., bk, true.
   1. if true, then test a1, a2, ..., ak to b1, b2, ..., bk.
      1. if true then the solution from a1, a2, ..., ak to b1, b2, ..., bk can not include toggling the kth switch
      2. if false then the solution from a1, a2, ..., ak to b1, b2, ..., !bk must include toggling the kth switch
   2. if false, then test a1, a2,...,ak to b1, b2,...,bk
      1. if true then the solution from a1,a2, ..., ak to b1, b2 ,.., bk must include toggling the kth switch
      2. if false, then the soluation from a1,a2,...,ak to b1, b2,...,!bk can not include toggling the kth switch

After two tests on the left side, you can perform similar tests on the right side. You will be able to combine the values of the test, because you will know whether the kth switch was toggled or not.

Answer 4

Thanks all for your help, this is what I came up with:

public static boolean disco(boolean[] init, boolean[] target)
{
    if (java.util.Arrays.equals(init, target)) {
        return true;
    } else {
        return disco(init, target, 0);
    }
}

private static boolean disco(boolean[] init, boolean[] target, int i)
{
    if (i > init.length-1) {
        return false;
    }

    disco(init, target, i+1);
    boolean t = false;

    if (init[i] != target[i]) {
        switchBulb(init, target, i);
    }

    if (java.util.Arrays.equals(init, target)) {
        t = true;
    }

    return t;
}

private static void switchBulb(boolean[] init, boolean[] target, int i)
{
    if ( (i > 1) && (init[i-1] != target[i-1]) && (init[i-2] != target[i-2]) ) {
        // If there's a series of 3 opposite-to-target bulbs, switch the middle one & from both sides
        init[i-1] = !init[i-1];
        init[i] = !init[i];
        init[i-2] = !init[i-2];
    } else if (i > 0 && i < init.length-1) {
        // There's only 1 bulb or 2 adjacent bulbs that are opposite of target.
        if (i == 1 && (init[0] != target[0]) ) {
            // First 2 bulbs are opposite of target's, so switch the 1st one.
            init[i-1] = !init[i-1];
            init[i] = !init[i];
        } else if ( (i == init.length-2) && (init[i+1] != target[i+1]) ) {
            init[i+1] = !init[i+1];
            init[i] = !init[i];
        } else {
            init[i] = !init[i];
            init[i-1] = !init[i-1];
            init[i+1] = !init[i+1];
        }
    } else {
        // First bulb or last bulb.
        init[i] = !init[i];
        if (i == 0) {
            init[i+1] = !init[i+1];
        } else {
            init[i-1] = !init[i-1];
        }
    }
}

I feel my use of recursion here is minimal, could be much cleaner if recursion was used properly. Any thoughts? I'm talking about the switchBulb function, it could be swapped with a little bit more sophisticated recursion logic, or am I wrong?

As in, if you simply iterate over the bulbs one by one and compare to the target array, you won't necessary get it right for ALL combinations of bulbs (see example), so how do you mimic random bulb switching with recursion? Or is there a pattern? There must be, if not, how would it know when to stop?

I think I got the solution, will post later if anyone's interested...