StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><strong>new version</strong></p> <pre><code>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; } </code></pre> <p><strong>new new version</strong></p> <p>I've broken it down to three cases: </p> <p><em>Case 1</em>: length %3 = 0<br> 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.<br> 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.<br> 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. </p> <p><em>Case 2</em>: length %3 = 1<br> Just like the first case, but we can affect single changes at 0,2 mod 3, and thus squeeze the 1 mod 3 cases. </p> <p><em>Case 3</em>: length %3 = 2<br> 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.</p> <pre><code>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); } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload