Lights out
A puzzle: a field of r × c lights, some of them on. Pressing a light toggles it and its side neighbours, up to four of them: lights that were on go off, lights that were off come on. All the lights have to be switched off. What is the smallest number of presses that does it?
The first example is the classic 5 × 5 field with everything on.
Input
The first line holds r and c (1 ≤ r, c ≤ 20). Then come r lines of c characters: 1 means the light is on, 0 that it is off.
Output
The smallest number of presses after which no light is on, or -1 if it cannot be done.
Examples
Example 1
5 5 11111 11111 11111 11111 11111
15
Example 2
2 3 100 110
1
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 11 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Does the order of presses matter? What happens if one light is pressed twice?
2Hint 2
Each light is toggled in the end as many times as it and its neighbours were pressed. It goes off if this number has the same parity as its initial state. Write this as equations where addition is exclusive or.
3Hint 3
There may be many solutions. How do two solutions differ from each other?
4The idea
Presses commute, and a double press changes nothing, so a solution is a set of pressed lights, one unknown xk ∈ {0, 1} per cell. For each light: the sum of x over it and its neighbours modulo 2 equals its initial state. This is a system of rc linear equations over the field of two elements, where addition is XOR and multiplication is AND, and Gaussian elimination works in it word for word: subtracting a row means doing an XOR, and there is no need to divide by the pivot, which is always 1.
If a row “0 = 1” remains at the end, it is impossible to switch everything off. Otherwise the solutions form a shift of the kernel: a particular solution plus any sum of the kernel’s basis vectors, one for each column without a pivot. The number of presses is the number of ones in the solution, and the smallest is found by going over all 2k combinations of the kernel. For fields up to 20 × 20 the dimension of the kernel is at most 16 (that of the 19 × 19 field), so there are at most 65,536 combinations.
5Walkthrough
Store a row of an equation as a bit mask of rc + 1 bits: which presses affect the light and, in the last bit, whether it is on. Gauss–Jordan elimination: for each column find a row with a one, put it in place and use XOR to clear this column in all the other rows, above and below. The particular solution: the free variables are zero, the variable of each pivot column equals the last bit of its row. The kernel basis vector for a free column f: a one in f and in those pivot columns whose rows have a one in column f.
The search: go through the combinations in Gray code order, where neighbours differ by one vector, so each step is one XOR and a count of ones. On the 5 × 5 field with everything on the kernel is two-dimensional, there are four solutions, and the shortest is 15 presses.
Why not “chase the lights”: press under each lit light, going down row by row. This switches off everything except the last row, and the last row too only with lucky presses in the first row. On the 5 × 5 field with no presses in the first row the last row stays lit, although a solution exists.
5+Solution
6Complexity
Elimination is O((rc)³/64) operations on 64-bit words: with 400 cells this is less than a million. Going over the kernel is O(2k·rc/64), where k ≤ 16.
7Common mistakes
- Chasing the lights from top to bottom. Finds a solution only with a lucky choice of the first row and does not look for the shortest: the first test.
- Any solution instead of the smallest. The particular solution from Gaussian elimination is almost never the shortest: on the 19 × 19 field one and the same picture has 65,536 solutions.
- Fractions and division. Over ordinary numbers the system is different: presses give a sum, not a parity. Everything is computed modulo 2.