Array recursion

Question

I have a task that I cannot understand, any pointers will be very appreciated, it will look like this:

There, a series of bulbs, presented as an array of true / false, there is a switch for each bulb, clicking it for any bulb, you switch it the same way as two neighboring ones (1 on the left and 1 on the right, if you clicked the switch on the edge - only 1 adjacent, of course).

What is needed for execution is a method that takes an array from a series of on / off bulbs, and the other represents a different state, presumably, of the 1st array after some switches have been pressed ..! Therefore, recursion should be used to find out if there is a combination of switch clicks that convert array 1 to array 2.

Here is the method signature:

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

Returns true if the init array can be converted to a target, otherwise false. The method should be static and not use loops and any other static and global variables, only local ones.

Example:

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

For 2 arrays, the disco (init, target) will return true, because switching the 1st and 4th bulbs will give the target state (remember that neighboring bulbs also switch).

Answer 1

a 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 broke it into three cases:

Case 1: Length% 3 = 0
Changing the first lamp and the second lamp, you can affect the change only on the 3rd. Then a change to 4 and 5 will make the 6th, only one will change. We see that we can change each lamp with an index divisible by 3.
Working backward (starting from the end), we can do the same, but this time it shows us that we can change bulbs with an index (i + 1) divisible by 3.
Combining the two, we see that if we want to change the index of 0.1 mod 3, we can. But then, to change 2, we just have to change the neighboring 0.1 pairs, and then make the change on average. Therefore, in all cases they are decidable.

Case 2: Length% 3 = 1
As in the first case, but we can influence individual changes at 0.2 mod 3 and, thus, compress 1 mod 3.

Case 3: Length% 3 = 2
Working back and forth only leads to cases of 0 mod 3. The only remaining moves we make are two changes in the bulbs (since we can ignore any changes in positions 0). A change of 1 or 2 will result in a change in position surrounded by two 0s, while a change in 0 will lead to a change in parity in neighboring blocks 1,2, which have 0 in between (this is easier if you draw it). But what I have shown so far is that 0 can be fixed, and in any neighboring 1,2 you can fix both if they are wrong without changing anything. If you are mistaken, you propagate the change to a neighboring pair of 1.2. If necessary, this change can be moved. This means that any even number of errors in 1.2 positions can be fixed, but an odd number cannot. All errors at position 0 can be corrected.

 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 2

So, in words, how would I do it:

If there are less than or equal to 3 bulbs, it is enough to check whether they can be switched so that they are corrected.

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

Check the correctness of the first lamp. If so, continue recursively with a subarray starting with the second lamp.

If the first lamp is wrong, switch the second lamp (switching the first lamp will not work, because the previous lamps switch then). Now the first lamp is correct. Continue with the subarray starting with the second lamp.

Answer 3

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

You can recursively test the left and right sides and then combine the result. The hard part combines the result.

Start on the left side.

• Check a1, a2, ..., ak, true for b1, b2, ..., bk, true.
  • if true, then check a1, a2, ..., ak for b1, b2, ..., bk.
    • if true, then the solution from a1, a2, ..., ak to b1, b2, ..., bk cannot include the inclusion of the kth switch
    • if false, then the solution is from a1, a2, ..., ak to b1, b2, ...,! bk should include the kth switch
  • if false then check a1, a2, ..., ak on b1, b2, ..., bk
    • if true, then the solution from a1, a2, ..., ak to b1, b2, .., bk should include the inclusion of the k-th switch
    • if false, then deviation from a1, a2, ..., ak to b1, b2, ...,! bk cannot enable 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 test values ​​because you will know if the k-th switch has been switched or not.

Answer 4

Thanks to everyone for your help, here 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 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 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 that my use of recursion here is minimal, it could be much cleaner if recursion was used properly. Any thoughts? I'm talking about the switchBulb function, can it be changed using a slightly more complex recursion logic, or am I mistaken?

As in the case where you simply iterate over the bulbs one by one and compare them with the target array, you do not need to use it correctly for ALL lamp combinations (see example), since you simulate random switching of lamps using recursion? Or is there a pattern? It must be, if not, how will he know when to stop?

I think I got a decision, I will publish it later if someone is interested ...