# How to find a minimum number of switch presses to shut down all lamps?

Is there a way to solve the following optimization problem in Sage given in https://www.ohjelmointiputka.net/post... :

The following is an example case.

I have $n=120$ lamps in a circle, and enumerated by $L_1,\ldots,L_{120}$. Some of them are switched on and some of them are switched off. I also have been given a positive integer $m=7.$ One every turn I choose one lamp $L_i$ and then the lamps $L_{i-m},\ldots,L_{i+m}$ will change their state, I mean if lamp $L_j$ was turned off then now it is turned on and vice versa. Indexes are modulo $n$ so the lamps $L_{118}, L_{119}, L_1,L_2$ are consecutive.

What is the minimum number of turns to shut off all lamps and which switches one must press, if the initial states of the lamps are (from $L_1$ to $L_{120}$)

 1010110110000100000101011001011111010111
1010011101001100000010001010011010110000
0000100110010100010010110111000000010110


where $1$ means that the corresponding lamp is on at the beginning and $0$ means that the corresponding lamp is off at the beginning.

EDIT 1:

It was wonderful to read the solutions given by dan_fulea and tmontell. I found that tmontell's solution works for some cases but are too brute force and too slow for harder cases, like

input ='1110111111101000100110011001100110100000001010001100011110110011111100000101000010101101100111001000100110110101111000110101101000010000100110111101001001011010110100100111011000110001101011110100110011010111110101010100'
m = 27
d = len(input)
F = GF(2)
L_init = vector(F,input)
M = matrix(F,d,d)
for i in range(d):
for j in range(-m,m+1):
M[i,(i+j) % d] = 1
I = M.solve_right(L_init)
K = M.right_kernel();
m = min([len((I+k).nonzero_positions()) for k in K])
print (m)


My laptop won't solve that case.

I tried the code by dan_fulea:

def A( N, M ):
F = GF(2)
R = range(N)

lists_for_M = [ [ (j+k) % N for k in range(M) ]
for j in R ]
return matrix( F, N, N, [ [ F(1) if k in lists_for_M[j]
else F(0)
for k in R ]
for j in R ] ).transpose()
N = 120
STR ="""
1010110110000100000101011001011111010111
1010011101001100000010001010011010110000
0000100110010100010010110111000000010110"""

A0 = A( 120, 15 )
v  = matrix( F, N, 1, [ F(int(s)) for s in STR if s in '01' ] )
w0 = vector( A0.solve_right( v ) )

def getString( vec, breakLength=40 ):
# s = ''.join( [ str(entry) for entry in vec ] )
s = ''
for count in range( len( vec ) ):
s += str( vec[count] )
if  (count+1) % breakLength == 0 and count < len(vec)-1 :
s += '\n'
return s

minOperations = N+1    # default, it will become smaller soon
solution = None        # we change it, finally it will be the solution
for u in A0.kernel():
vec = u + w0
nrOperations = len( vec.nonzero_positions() )
if nrOperations < minOperations:
minOperations = nrOperations
solution      = vec
print "New minOperations %s for\n%s\n" % ( minOperations, getString(vec) )

print "MINIMAL NUMBER OF OPERATIONS = %s" % minOperations
print "SOLUTION IS:\n%s" % getString( solution )

# we can search for all solutions
print "ALL SOLUTIONS:\n"
for u in A0.kernel():
vec = u + w0
if minOperations == len( vec.nonzero_positions() ):
print getString( vec )
print


The result was

TypeError: unable to find a common ring for all elements


All cases in this problem are given as

label,  n.o. lamps, how many lamps        original lamp states
a switch affects
per direction
================================================================================
B       6               1               101101
--------------------------------------------------------------------------------
C       10              2               1011010110
--------------------------------------------------------------------------------
D       20              1               11111011101010111111
--------------------------------------------------------------------------------
E       30              7               011100001010011011100001010011
--------------------------------------------------------------------------------
F       39              6               110100111111101000011000100110111100010
--------------------------------------------------------------------------------
G       53              9               0101100101111100100011100111101001001010
0010000010110
--------------------------------------------------------------------------------
H       120             7               1010110110000100000101011001011111010111
1010011101001100000010001010011010110000
0000100110010100010010110111000000010110
--------------------------------------------------------------------------------
I       220             27              1110111111101000100110011001100110100000
0010100011000111101100111111000001010000
1010110110011100100010011011010111100011
0101101000010000100110111101001001011010
1101001001110110001100011010111101001100
11010111110101010100
--------------------------------------------------------------------------------
J       500             87              1010001101101001110001101001000101010100
0001111111001101011000000011001111111011
1001110011010111111011010100010011011001
1001101110011011100001000111110101011111
1100111100001100110011101110101100001111
1100010010011010001111000000101110101101
1010100001100011111000111001000101101000
1011111111101111000000011111010001000000
1110011110111101010010011000000100010100
0011101011010011010110011110111000010010
0111100100011010010110001000011100101001
1110111010001001011001111011111011010110
10101101111011101110
--------------------------------------------------------------------------------
K       1002            83              0010100100100101000000110101111111101011
1101000101111110001110000110110110010101
1110110011011101100110111001110110010011
1101111010110011110101100001101010100011
1110001100011111110100011110100111111100
0011001011100110101100001101000001110010
0110100000100100100000011010000010111100
1110001110011110101001100111101101010000
0101010000011010011110101001001001000000
0011000100011011011001111010001101111000
0100001011010011001010111001111100110001
0011111110101101001100111101110000000000
1101100100000011000010010100010101001000
1100001000101001100110010100001000001101
1101000100001010011000101001101000100010
0011010001011101010100011101001101101100
0111110100110011001111000000001001001001
1001111001011111000010110000110010101000
1011001100111101000101000110000111010100
0010011011010111001101011001111000001011
1110101010101101111011111110100001100110
1000101100110011010000110000011011110011
0010000010000000111101101000001111101111
0100111110010101100011101001111101010000
1111100010011001110111111000101000000101
01
--------------------------------------------------------------------------------
L       2107            108             0111110100011000011111101110010101100011
1001111011101001001110111110001100011001
1001010100101011101101001000010111111111
1001101010111011110100100101000101100011
1110100010010010101110100000111100101000
0111101011111100010010110000100110100100
0100110101110010110011110010101101100111
1110010011000110110111010110010100101110
0111111101110000111001111100100010010001
1010110011000101100111111001011110101110
0111010110111110110101000101100100011000
1011000011011110001111100110100010100101
1101111100110011001110010010001010101111
1000001001000110011110010011011101110100
1011111100110010011000010110010110101010
0110101000011011110001010000010001000110
1001110101001001110110111111010011010111
1111011001000110111001000011101101110001
0000011111101000010101011111011011000011
1111000000011100010011011001011000110101
1101011111100001100010110010110011000000
0001001111100101110100100011011010011100
0000001111010101000111011000110110100001
1010110011100110111010111110110000010000
1000101001111001000110000101010000010111
1011100001000110001100010000001011101110
1001111110100010010000011000100101010101
1001001001110110101000001001001100001011
0011011100011111100111001110101101110001
0111010000010011110110011011000011101001
1111011010010000101111000010000001100110
1001011101001000010101001001011111111011
1000111000100001101100101110100011111100
1011001111101111110110101111101111011111
1001111100110101110101111110010010101101
1111111111000100100111100011101110110100
0100011011001010110100101101000000110010
0010010001001110110100011111100011111101
0100110111101101010101010100110110011011
0001111111000100000111011010101011000010
0011011110110110110100011001101111001000
1000000011110011100111100000001010010011
1000011101111100000101010101010010100101
1010001011010100011011001110110010100000
1000111101111000010111111101010110110111
0110001111100011001110000100100101001111
0000111111100010011001010000010110111000
1000110110001000001100110000001011000010
1000101101110000101100100010101111100011
1000010010111101000010000110011010000001
0010001100001000001100110111110100100111
1001100110001000100101011111001011001111
110001011111001101010101001
================================================================================


EDIT 2:

There is some approach on https://artofproblemsolving.com/commu... by the nickname TZF:

Turns out this is a straight-up linear algebra problem over the field ${0,1}$. Addition in this field is equivalent to XOR.

Let basis vector $i$ be the length-$n$ binary vector with elements $i-m,\ldots,i+m$ (all mod $n$) as 1's and the rest as 0's. When $(2m+1)$ is relatively prime with $n$, these vectors span the full space.

The problem of finding the optimal set of switches to press is then equivalent to finding a representation of the original binary state vector in the above basis, which can be done using Gaussian elimination.

I haven't explored the runtime of doing Gaussian elimination on the particular binary circulant basis in this problem (it benefits from sparsity and a clean structure), but if it's suboptimal runtime-wise, I'd imagine there might be a way to employ an FFT to speed up the solution.

Would this approach be a fast enough for this problem?

edit retag close merge delete

First, thanks for providing a link to the initial question ! Unfortunately, i do not speak Finnish, and the translation toos did not help me to answer the following questions:

1. Are you looking to the actual minimal number of interrupters to be switched (over all the possibilities), or are you looking for a number of interrupters to be switched as small as possible ? This is actually a different question, since we could use other "approximating" tools then.
2. At the end of the page, there are some names with numbers: "Metabolix (1721), os (1721), Touho (1721), ...", to what correspond the numbers ? Are there the sum of switched interruptors over all the museums ?
( 2017-11-01 07:20:20 -0600 )edit
1. I'm looking for how small number of interrupters will turn of all the lamps so the second opinion of your question if I understood correctly.
2. Let $n_x$ denote the number of switch presses that is required to turn all the lamps off in a room $x$. Then Metabolix and os have found switch presses such that $n_B+n_C+n_D+n_E+n_F+\ldots+n_L=1721$. The scoring system has also the property that the site adds $3600$ to the score if the given switches won't turn off all the lamps. Minimal score is better.
( 2017-11-01 07:36:33 -0600 )edit

F = GF(2)


at the beginning of all was done in my post... Sorry for not isolating the minimal code. I'll try to edit and give the minimal code working for the posted new cases...

( 2017-11-01 22:00:23 -0600 )edit

Sort by » oldest newest most voted

[Note that i started to write my answer before the numbers changed, so let me start with 2107 lamps and then deal with the 120 lamps]

First, it should be clear that testing all the $2^{2107}$ possibilities is not possible, so brute force (which is the first technique to be considered) is not an option.

The situation you describe can be modeled as follows:

• the pressing of some of the 2107 lamps (viewed as interrupters) can be seen as a vecror $I$ in $F^d$, where $F$ is the finite field with two elements (a 1 at position i tells that the interrupter i is pressed).

• the state of the 2107 lamps can also be seen as a vecror $L$ in $F^d$ (a 1 at position i tells that the lamp i is turned on).

The situation you describe is linear: if we start from a completely off position (zero vector), if we press the interrupters encoded as a vector $I$, we get some lamps turned on as a vector $L$ with the following relation: $L=M*I$, where $M$ is the matrix over $F$ where $M_{i,j}=1$ iff $j$ is between $i-108$ and $i+108$ (zero otherwise), where indices have to be understood modulo 2107.

In your question, you start with some lamps open (represented by a vector $L_{init}$) and want to press some interuptors in order to turn them all off. So, you want to find a pressing of interruptors $I$ such that $L_{init}+MI = 0$ This is equivalent to $MI = L_{init}$ (remember that in $F$ we have $1=-1$).

Here is a way to encode the situation in Sage (the input is given as a string of 0's and 1's):

sage: input = '0111110100011000011111101110010101100011100111101110100100111011111000110001100110010101001010111011010010000101111111111001101010111011110100100101000101100011111010001001001010111010000011110010100001111010111111000100101100001001101001000100110101110010110011110010101101100111111001001100011011011101011001010010111001111111011100001110011111001000100100011010110011000101100111111001011110101110011101011011111011010100010110010001100010110000110111100011111001101000101001011101111100110011001110010010001010101111100000100100011001111001001101110111010010111111001100100110000101100101101010100110101000011011110001010000010001000110100111010100100111011011111101001101011111110110010001101110010000111011011100010000011111101000010101011111011011000011111100000001110001001101100101100011010111010111111000011000101100101100110000000001001111100101110100100011011010011100000000111101010100011101100011011010000110101100111001101110101111101100000100001000101001111001000110000101010000010111101110000100011000110001000000101110111010011111101000100100000110001001010101011001001001110110101000001001001100001011001101110001111110011100111010110111000101110100000100111101100110110000111010011111011010010000101111000010000001100110100101110100100001010100100101111111101110001110001000011011001011101000111111001011001111101111110110101111101111011111100111110011010111010111111001001010110111111111110001001001111000111011101101000100011011001010110100101101000000110010001001000100111011010001111110001111110101001101111011010101010101001101100110110001111111000100000111011010101011000010001101111011011011010001100110111100100010000000111100111001111000000010100100111000011101111100000101010101010010100101101000101101010001101100111011001010000010001111011110000101111111010101101101110110001111100011001110000100100101001111000011111110001001100101000001011011100010001101100010000011001100000010110000101000101101110000101100100010101111100011100001001011110100001000011001101000000100100011000010000011001101111101001001111001100110001000100101011111001011001111110001011111001101010101001'

sage: d = 2107
sage: m = 108
sage: F = GF(2)

sage: L_init = vector(F,input)

sage: M = matrix(F,d,d)
....: for i in range(d):
....:     for j in range(-m,m+1):
....:         M[i,(i+j) % d] = 1

sage: M
2107 x 2107 dense matrix over Finite Field of size 2 (use the '.str()' method to see the entries)


We get a solution of the problem by solving the equation $M*I = L_{init}$:

sage: I = M.solve_right(L_init)


We can see that this particular solution has 1035 solutions

sage: len(I.nonzero_positions())
1035


But there might be better solutions. The set of solutions is an affine space, a classical way to find small vectors where the base ring is $\mathbb{Z}$ is with lattice reduction. Integer linear programming can be used too. But here (where we have cancellations $1+1=0$), it seems hard to use.

Since we are in a linear situation, the set of solitions can be easily described as $I+K$, where $K$ is the kernel of $M$: indeed $S$ is a solution iff $MS=L_{init}$ iff $M(S+I)=0$ iff $S+I\in Ker(M)$.

Let us look at that kernel:

sage: K = M.right_kernel() ; K
Vector space of degree 2107 and dimension 6 over Finite Field of size 2
Basis matrix:
6 x 2107 dense matrix over Finite Field of size 2


It has dimension 6, so the number of solutions is $2^6$, which is much smaller than $2^{2107}$. So, here we, can consider brute force to conclude: it suffice to look at the number of pressed interrupters for all the solutions and take the minimum:

sage: min([len((I+k).nonzero_positions()) for k in K])
1007


So, the minimum number of turns to shut off all lamps is 1007.

For the smaller problem, it suffice to do the same:

sage: input = '101011011000010000010101100101111101011110100111010011000000100010100110101100000000100110010100010010110111000000010110'
sage: F = GF(2)
sage: L_init = vector(F,input)
sage: d = len(L_init)
sage: m = 7
sage: M = matrix(F,d,d)
....: for i in range(d):
....:     for j in range(-m,m+1):
....:         M[i,(i+j) % d] = 1
sage: I = M.solve_right(L_init)
sage: K = M.right_kernel() ; K.dimension()
14
sage: min([len((I+k).nonzero_positions()) for k in K])
46


So, the minimum number of turns to shut off all lamps is 46.

Note that this problem is actually harder sinc Sage has to test $2^{14}=16384$ solutions.

more

It is a wonderful pleasure to read such a structural solution. Also, a big compliment goes to the philosophy of sage, since it simply supports mathematical thinking. (Two people with completely different paths through mathematics - i suppose - give the same solution... )

For me, one of the great benefits of asksage is to show solutions, by transforming structure and human common intelligence into quick compact code.

( 2017-10-30 17:43:46 -0600 )edit

SOLVED

(...had to solve it with the own devices, the source of the problems was not helpful, neither was the link to Art of Problem Solving (which should have been rather done of the sister site Start of Problem Solving).)

For the reader in hurry and only the solution, please go directly to the string final solution below. (The already typed code still remains, since it shows the trials and errors on the road. They support the solution, and document somehow the search. It also remains because of my experience with maths books that give only the cosmetic last mirror of a solution on minimum of space. This was the reason to have a hard time with simple structures that are best understood by examples.)

The first post was given with $N=2107=7^2\cdot 43$, and there were $M=108+1+108=317=7\cdot31$ consecutive lamps to be changed in the same time.

Then we finally have more posted cases to test the code, and even the source. This is here and generally very helpful! The mathematical model is as follows.

• Let $F=\mathbb F_2$ be the field with two elements.
• Let $N=120$, and let $V=F^N$ be the vector space over $F$ of dimension $N$.
• On $V$ we have a canonical basis, the vectors $v_j$ with components $(\dots,0,0,1,0,0,\dots)$, where the one is on position $j$.
• Let $m=7$. We define now an other system of vectors, $w_j$, where $w_j$ has the components on positions $j-m, \dots,j,\dots,j+m$ equal to one, else zero on the other components. Indices are taken modulo $N$, and we prefer to use $0,1,\dots,(N-1)$ for the representatives of the classes modulo $N$. It is also simpler to implement it in python. So there are $M=2m+1$ components equal to one in each of the vectors.
• The first question is, if $w_0,w_1,\dots$ form a generating system for $V$. We will always display vectors as column vectors. We compute the determinant of the matrix

$$A = [\; w_0\; w_1\; w_2\; \dots\; ]$$

• For this, we replace the "zeroth" column $w_0$ with $w_0-w_1$, get a matrix with the same determinant, then column $w_1$ with $w_1-w_2$, and so on. The forelast columns still can be changed, using the last one. But the last one remains. We get a matrix

$$\det A =\det[\; (w_0-w_1)\; (w_1-w_2)\; (w_2-w_3)\; \dots\; (w_{N-2}-w_{N-1})\; w_{N-1}\;]\ .$$

• Note that all resulted columns have exactly two entries equal to $1$, all but the last one.
• Now we replace one of the lines by the sum of all lines.

Let us write code for this. It is better to use $M=2m+1$ in code for the number of consecutive entries $=1$ in each column.

def A( N, M ):
F = GF(2)
R = range(N)

lists_for_M = [ [ (j+k) % N for k in range(M) ]
for j in R ]
return matrix( F, N, N, [ [ F(1) if k in lists_for_M[j]
else F(0)
for k in R ]
for j in R ] ).transpose()
print A( 12, 5 )
print "The determinant of the above matrix is:"
print A( 12, 5 ).det()


And we get:

[1 0 0 0 0 0 0 0 1 1 1 1]
[1 1 0 0 0 0 0 0 0 1 1 1]
[1 1 1 0 0 0 0 0 0 0 1 1]
[1 1 1 1 0 0 0 0 0 0 0 1]
[1 1 1 1 1 0 0 0 0 0 0 0]
[0 1 1 1 1 1 0 0 0 0 0 0]
[0 0 1 1 1 1 1 0 0 0 0 0]
[0 0 0 1 1 1 1 1 0 0 0 0]
[0 0 0 0 1 1 1 1 1 0 0 0]
[0 0 0 0 0 1 1 1 1 1 0 0]
[0 0 0 0 0 0 1 1 1 1 1 0]
[0 0 0 0 0 0 0 1 1 1 1 1]
The determinant of the above matrix is:
1


(This may seem irrelevant. Then please skip. But there is some structure, it is maybe important to look for the kernel. Here, computing the determinant, we get some feeling about the possible column relations.) For A( 120, 15 ) the det is zero. Our strategy to compute the determinant, was to replace the above matrix with other matrices with same determinant:

sage: A0 = A(12, 5 )
sage: A0
[1 0 0 0 0 0 0 0 1 1 1 1]
[0 1 0 0 0 0 0 0 0 1 1 1]
[0 1 1 0 0 0 0 0 0 0 1 1]
[0 1 1 1 0 0 0 0 0 0 0 1]
[0 1 1 1 1 0 0 0 0 0 0 0]
[1 1 1 1 1 1 0 0 0 0 0 0]
[0 0 1 1 1 1 1 0 0 0 0 0]
[0 0 0 1 1 1 1 1 0 0 0 0]
[0 0 0 0 1 1 1 1 1 0 0 0]
[0 0 0 0 0 1 1 1 1 1 0 0]
[0 0 0 0 0 0 1 1 1 1 1 0]
[0 0 0 0 0 0 0 1 1 1 1 1]
sage: A0
[1 0 0 0 0 0 0 0 1 1 1 1]
[0 1 0 0 0 0 0 0 0 1 1 1]
[0 0 1 0 0 0 0 0 0 0 1 1]
[0 0 1 1 0 0 0 0 0 0 0 1]
[0 0 1 1 1 0 0 0 0 0 0 0]
[1 0 1 1 1 1 0 0 0 0 0 0]
[0 1 1 1 1 1 1 0 0 0 0 0]
[0 0 0 1 1 1 1 1 0 0 0 0]
[0 0 0 0 1 1 1 1 1 0 0 0]
[0 0 0 0 0 1 1 1 1 1 0 0]
[0 0 0 0 0 0 1 1 1 1 1 0]
[0 0 0 0 0 0 0 1 1 1 1 1]


If we perform all operations, then we get finally:

A0 = A( 12, 5 )
for j in range( 11 ):


and we get:

[1 0 0 0 0 0 0 1 0 0 0 1]
[0 1 0 0 0 0 0 0 1 0 0 1]
[0 0 1 0 0 0 0 0 0 1 0 1]
[0 0 0 1 0 0 0 0 0 0 1 1]
[0 0 0 0 1 0 0 0 0 0 0 0]
[1 0 0 0 0 1 0 0 0 0 0 0]
[0 1 0 0 0 0 1 0 0 0 0 0]
[0 0 1 0 0 0 0 1 0 0 0 0]
[0 0 0 1 0 0 0 0 1 0 0 0]
[0 0 0 0 1 0 0 0 0 1 0 0]
[0 0 0 0 0 1 0 0 0 0 1 0]
[0 0 0 0 0 0 1 0 0 0 0 1]


Now we add all rows to the last one. The last row will have only one entry equal to $1$, the diagonal one, we can expand using Leibniz rule for it, and get the minor obtained by removing the last row, and the last column.

Now we start a process of deleting rows and columns for the last removed $1$ entries (in the last removed lines and columns).

Let us stop here. At any rate, we get a zero determinant in case we have a common divisor of $M$ and $N$. (One direction is easy to show.)

Back to our problem. We have to deal with the matrix

sage: A( 120, 15 )
120 x 120 dense matrix over Finite Field of size 2 (use the '.str()' method to see the entries)
sage: A( 120, 15 ).det()
0
sage: A( 120, 15 ).rank()
106


of rank $106$. First of all, let us see if the given vector is in the vector space spanned by the columns of $A$.

N = 120
STR ="""
1010110110000100000101011001011111010111
1010011101001100000010001010011010110000
0000100110010100010010110111000000010110"""

A0 = A( 120, 15 )
v = matrix( F, N, 1, [ F(int(s)) for s in STR if s in '01' ] )
B = block_matrix( 1, 2, [ A0, v ] )
print "The rank of the extended matrix is %s" % B.rank()


OK, we get:

The rank of the extended matrix is 106


Then we need a solution, any particular one. Here is it:

sage: w0 = A0.solve_right(v)
sage: A0*w0 == v
True


(There is no place here to show all $N=120$ components of it.)

Any other solution of the same equation is of the form $w_0+u$, where $u$ is an element in the kernel of the matrix A0 = A( 120, 15 ).

This kernel has dimension equal to gcd( M, N ) - 1, which is in our case

sage: A0.kernel().dimension()
14


This is a space of dimension $14$, and there are $2^{14}$ vectors in it. This is rather a small number. We can iterate through it, for each of the $2^{14}$ vectors of shape $w_0+u$ we record the number of the "lamp operation" needed, i.e. the number of entries equal to $1$, and search for the one, for some vector where the minimum is reached.

The code would be:

N = 120
STR ="""
1010110110000100000101011001011111010111
1010011101001100000010001010011010110000
0000100110010100010010110111000000010110"""

A0 = A( 120, 15 )
v  = matrix( F, N, 1, [ F(int(s)) for s in STR if s in '01' ] )
w0 = vector( A0.solve_right( v ) )

def getString( vec, breakLength=40 ):
# s = ''.join( [ str(entry) for entry in vec ] )
s = ''
for count in range( len( vec ) ):
s += str( vec[count] )
if  (count+1) % breakLength == 0 and count < len(vec)-1 :
s += '\n'
return s

minOperations = N+1    # default, it will become smaller soon
solution = None        # we change it, finally it will be the solution
for u in A0.kernel():
vec = u + w0
nrOperations = len( vec.nonzero_positions() )
if nrOperations < minOperations:
minOperations = nrOperations
solution      = vec
print "New minOperations %s for\n%s\n" % ( minOperations, getString(vec) )

print "MINIMAL NUMBER OF OPERATIONS = %s" % minOperations
print "SOLUTION IS:\n%s" % getString( solution )

# we can search for all solutions
print "ALL SOLUTIONS:\n"
for u in A0.kernel():
vec = u + w0
if minOperations == len( vec.nonzero_positions() ):
print getString( vec )
print


It gives:

New minOperations 60 for
1111101101000111111010011101001111101111
1101001100110101101010101001111010111101
0011000000100100000011101000000000000000

New minOperations 58 for
0111101101000100111010011101010111101111
1101111100110101101100101001111010001101
0011000001000100000011100100000000000001

New minOperations 54 for
0011101101000110011010011101000011101111
1101010100110101101001101001111010100101
0011000000010100000011101110000000000000

New minOperations 52 for
0101101101000110101010011101000101101111
1101011000110101101000001001111010101001
0011000000001100000011101101000000000000

New minOperations 50 for
0000101101000110000010011101000000101111
1101010010110101101001011001111010100011
0011000000011000000011101111100000000000

New minOperations 48 for
0001101111000110001010001101000001101101
1101010000110001101001001001011010100001
0010000000011100001011101111000001000000

New minOperations 46 for
0000101111100110000010001001000000101101
0101010010110000101001011001010010100011
0010010000011000001001101111100001010000

MINIMAL NUMBER OF OPERATIONS = 46
SOLUTION IS:
0000101111100110000010001001000000101101
0101010010110000101001011001010010100011
0010010000011000001001101111100001010000
ALL SOLUTIONS:

0000101111100110000010001001000000101101
0101010010110000101001011001010010100011
0010010000011000001001101111100001010000

0001001111100110001110001001000001001101
0101010001110000101001000001010010100000
0010010000011110001001101111010001010000

0001101011100110001010101001000001101001
0101010000111000101001001000010010100001
0000010000011100011001101111000011010000

0000001011100110000110101001000000001001
0101010011111000101001010000010010100010
0000010000011010011001101111110011010000

0001101110100110001010000001000001101100
0101010000110010101001001001000010100001
0010110000011100001101101111000001110000

0000001110100110000110000001000000001100
0101010011110010101001010001000010100010
0010110000011010001101101111110001110000

0000101010100110000010100001000000101000
0101010010111010101001011000000010100011
0000110000011000011101101111100011110000

0001001010100110001110100001000001001000
0101010001111010101001000000000010100000
0000110000011110011101101111010011110000


A last check:

sage: A0 * matrix( F, N, 1, list(solution) ) == v
True


It is possible, that something went wrong on the road. But the principle is simple, we need one special solution, then generating elements of the kernel of the corresponding lamp matrix, the kernel should have a small dimension, we loop, for each element in the kernel, solution of the homogenous system for the kenel matrix, we associate a solution of the inhomogenous system for the lamp matrix and the state that should be reached. The problem wants the vector in this space which has a minimal amount of nonzero entries. (This is of course a human, non-structural requirement. For a structural question i would have invested more effort, so that the code should have worked also for "bigger" kernels.)

Note:

To "see" the kernel, and imagine how would it look like "in general", try:

sage: print K.matrix().transpose().str()


(Then complete the proof about the rank of the matrix...)

New edit after seeing the new cases and the new problems The above discussion was only searching for the optimal number of switches, i had no idea that we need an algorithm for the whole industry of cases...

I'll post some working code, but it works of course with limitations, let us have the code and its output, then the limitations are clear:

# # # PUTTING ALL IN ONE...
F = GF(2)

def getA( N, M ):
R = range(N)
lists_for_M = [ [ (j+k) % N for k in range(M) ]
for j in R ]
return matrix( F, N, N, [ [ F(1) if k in lists_for_M[j]
else F(0)
for k in R ]
for j in R ] ).transpose()

def getString( vec, breakLength=80 ):
# s = ''.join( [ str(entry) for entry in vec ] )
s = ''
for count in range( len( vec ) ):
s += str( vec[count] )
if  (count+1) % breakLength == 0 and count < len(vec)-1 :
s += '\n'
return s

CASES = (
( 6, 1, '101101' ),
( 10, 2, '1011010110' ),
( 20, 1, '11111011101010111111' ),
( 30, 7, '011100001010011011100001010011' ),
( 39, 6, '110100111111101000011000100110111100010' ),
( 53, 9,
'''0101100101111100100011100111101001001010
0010000010110''' ),
( 120, 7,
'''1010110110000100000101011001011111010111
1010011101001100000010001010011010110000
0000100110010100010010110111000000010110''' ),
( 220, 27,
'''1110111111101000100110011001100110100000
0010100011000111101100111111000001010000
1010110110011100100010011011010111100011
0101101000010000100110111101001001011010
1101001001110110001100011010111101001100
11010111110101010100''' ),
( 500, 87,
'''1010001101101001110001101001000101010100
0001111111001101011000000011001111111011
1001110011010111111011010100010011011001
1001101110011011100001000111110101011111
1100111100001100110011101110101100001111
1100010010011010001111000000101110101101
1010100001100011111000111001000101101000
1011111111101111000000011111010001000000
1110011110111101010010011000000100010100
0011101011010011010110011110111000010010
0111100100011010010110001000011100101001
1110111010001001011001111011111011010110
10101101111011101110''' ),
( 1002, 83,
'''0010100100100101000000110101111111101011
1101000101111110001110000110110110010101
1110110011011101100110111001110110010011
1101111010110011110101100001101010100011
1110001100011111110100011110100111111100
0011001011100110101100001101000001110010
0110100000100100100000011010000010111100
1110001110011110101001100111101101010000
0101010000011010011110101001001001000000
0011000100011011011001111010001101111000
0100001011010011001010111001111100110001
0011111110101101001100111101110000000000
1101100100000011000010010100010101001000
1100001000101001100110010100001000001101
1101000100001010011000101001101000100010
0011010001011101010100011101001101101100
0111110100110011001111000000001001001001
1001111001011111000010110000110010101000
1011001100111101000101000110000111010100
0010011011010111001101011001111000001011
1110101010101101111011111110100001100110
1000101100110011010000110000011011110011
0010000010000000111101101000001111101111
0100111110010101100011101001111101010000
1111100010011001110111111000101000000101
01''' )
)

def info( N, M, lamps ):
d = gcd( M, len(lamps) )
print "N=%s :: The vector space has dim = 2**(%s-1) = %s" % ( N, d, 2**(d-1) )
return 2**(d-1)

def search( M, lampsVector, verbose=False ):
N = len( lampsVector )
A = getA( N, M )
v = matrix( F, N, 1, lampsVector )
w = A.solve_right(v)

if verbose:
print "possible switches (maybe not minimal):\n%s" % getString( vector(w) )
print "kernel vectors that can be used:"
for u in A.kernel().basis():    print getString(u)

minOperations = N+1
solution = None

for u in A.kernel():
vec = u + vector(w)
nrOperations = len( vec.nonzero_positions() )
if nrOperations < minOperations:
minOperations = nrOperations
solution      = vec
if verbose:
print "New minOperations %s for\n%s\n" % ( minOperations, getString(vec) )

# print "Minimal number of operations is %s" % minOperations
return minOperations, solution

for N, m, case in CASES:
M = 2*m+1
lamps = [ F(int(s)) for s in case if s in '01' ]
if N != len(lamps):
print "Invalidated case: N=%s" % N
continue
# else:
if info( N, M, lamps ) > 10000:
print "*** Too many cases, an other algorithm is needed...\n"
continue

nr, solution = search( M, lamps )
print ( "N=%s M=%s SOLUTION: %s switches as follows:\n%s\n\n"
% ( N, M, nr, getString( solution ) ) )


This delivers:

N=6 :: The vector space has dim = 2**(3-1) = 4
N=6 M=3 SOLUTION: 2 switches as follows:
010001

N=10 :: The vector space has dim = 2**(5-1) = 16
N=10 M=5 SOLUTION: 4 switches as follows:
1110100000

N=20 :: The vector space has dim = 2**(1-1) = 1
N=20 M=3 SOLUTION: 8 switches as follows:
10010100111000100100

N=30 :: The vector space has dim = 2**(15-1) = 16384
*** Too many cases, an other algorithm is needed...

N=39 :: The vector space has dim = 2**(13-1) = 4096
N=39 M=13 SOLUTION: 9 switches as follows:
101000100000001000000100110001100000000

N=53 :: The vector space has dim = 2**(1-1) = 1
N=53 M=19 SOLUTION: 25 switches as follows:
11110010100010100111011100010110001000011101001000101

N=120 :: The vector space has dim = 2**(15-1) = 16384
*** Too many cases, an other algorithm is needed...

N=220 :: The vector space has dim = 2**(55-1) = 18014398509481984
*** Too many cases, an other algorithm is needed...

N=500 :: The vector space has dim = 2**(25-1) = 16777216
*** Too many cases, an other algorithm is needed...

N=1002 :: The vector space has dim = 2**(167-1) = 93536104789177786765035829293842113257979682750464
*** Too many cases, an other algorithm is needed...


So we really need to improve the search. How? Let us consider:

sage: N, m, c = CASES[4]
sage: search( 2*m+1, [ F(int(s)) for s in c if s in '01' ], verbose=1 )
possible switches (maybe not minimal):
101110100000001011000100110000000000000
kernel vectors that can be used:
100000000000110000000000011000000000001
010000000000101000000000010100000000001
001000000000100100000000010010000000001
000100000000100010000000010001000000001
000010000000100001000000010000100000001
000001000000100000100000010000010000001
000000100000100000010000010000001000001
000000010000100000001000010000000100001
000000001000100000000100010000000010001
000000000100100000000010010000000001001
000000000010100000000001010000000000101
000000000001100000000000110000000000011
New minOperations 11 for
101110100000001011000100110000000000000

New minOperations 9 for
101000100000001000000100110001100000000


So we get a particular solution, need then its minimal distance to some (linear) code... I think i have to come back...

Continuation

The algorithm described by example

Let us consider the particular solution of the inhomogenous system from above:

New minOperations 11 for
101110100000001011000100110000000000000


In our case, the key invariant is $d$, the gcd for $N$ and $M=2m+1$. The dimension of the kernel of $A$ is $d-1$, and the simplest way to describe the kernel is as follows.

Let us consider the vectors having $N/d$ components equal to $1$, all of them placed at same cyclic distance from each other. In our case, we may take the rows in

100000000000010000000000001000000000000
010000000000001000000000000100000000000
001000000000000100000000000010000000000
000100000000000010000000000001000000000
000010000000000001000000000000100000000
000001000000000000100000000000010000000
000000100000000000010000000000001000000
000000010000000000001000000000000100000
000000001000000000000100000000000010000
000000000100000000000010000000000001000
000000000010000000000001000000000000100
000000000001000000000000100000000000010
000000000000100000000000010000000000001


These rows are not in the kernel, but the difference (or the sum in characteristic two) of any two of them is in the kernel. So we may use such differences to "move lamps switch solutions" from one solution to the other one, hoping for a progress in reducing the number of the one entries used.

For this purpose, let us start with a particular solution, the above one:

101110100000001011000100110000000000000


We define its pattern as an element in $$\mathbb Z_{\ge 0}^d$$ as follows. We split it in groups of $d$ digits:

1011101000000 0101100010011 0000000000000


We put the groups in a table:

1011101000000
0101100010011
0000000000000


Then we count the number of ones in each column, getting the pattern

1112201010011


We then immediately detect the two positions with 22 as suboptimal, and use the one against the other one to reduce the number of operations. We explicitly use the difference of the two vectors

0001000000000 0001000000000 0001000000000
0000100000000 0000100000000 0000100000000


So that the new pattern is

1111101010011


and we cannot exploit any other situation. An other example is the one with $(N,m,M,d)=(120,7,15,15)$. We obtained a particular solution with a total of $60$ "switch operations". This was:

111110110100011
111101001110100
111110111111010
011001101011010
101010011110101
111010011000000
100100000011101
000000000000000

656442345453333


Its pattern was displayed below the $d$--groups. I am editing here with bare hands. Let me check that we get that \verb+60+:

sage: sum( [ int(s) for s in '656442345453333' ] )
60


Now we immediately see the problematic columns. The 6 on the first place can be exchanged (against some other column(s)) to its opposite. We can use the other 6 for this purpose. Also, the appearences of 5 are not welcome, everything strictly bigger than the half of the column length, $4$ in our case, is not welcome. So, applying simplifications with vectors in the kernel of the matrix A we can successively reduce then number of switches as follows:

656442345453333
6 6                   66 replaced with 22
252442345453333
5      5             55 replaced with 33
232442343453333
45           45 replaced with 43
232442343433333


And there is no progress any longer. Of course, we can "exchange an even number of 4, passing to the complementary 4", the relevant positions are

232442343433333
**  * *


this is the reason for the numerous, i.e. 2^(4-1) solutions. Let us write code that finds the pattern.

def pattern( d, solution, verbose=False ):
# d must divide the lenght of solution
n = len( solution )
if n % d:
return
blocks = [ [ solution[ j + d*k ] for j in range(d) ]
for k in range(n/d) ]
if verbose:
for block in blocks:
print ''.join( [ str(b) for b in block ] )

if type( solution ) == str:
return [ sum( [ 1 for block in blocks if int( block[k] ) ] )
for k in range(d) ]

return [ sum( [ 1 for block in blocks if block[k] ] )
for k in range(d) ]


Then we have for the one particular, not optimal solution the following pattern:

bad = """
111110110100011
111101001110100
111110111111010
011001101011010
101010011110101
111010011000000
100100000011101
000000000000000"""
sol = """
000010111110011
000001000100100
000010110101010
100101100001010
010110010100101
000110010010000
011000001001101
111100001010000"""

bad = ''.join( [ s for s in bad if s in '01' ] )
sol = ''.join( [ s for s in sol if s in '01' ] )

d = 15
print pattern( d, sol )


This gives:

[6, 5, 6, 4, 4, 2, 3, 4, 5, 4, 5, 3, 3, 3, 3]
[2, 3, 2, 4, 4, 2, 3, 4, 3, 4, 3, 3, 3, 3, 3]


One can also observe exactly what happens by comparing the columns in bad (a non optimal lamps switch operations), and sol (an optimal solution).

From this, we have only to write the algorithm that performs the search. Sage will do it quickly for all cases.

FINAL SOLUTION

F = GF(2)

CASES = (
( 6, 1, '101101' ),
( 10, 2, '1011010110' ),
( 20, 1, '11111011101010111111' ),
( 30, 7, '011100001010011011100001010011' ),
( 39, 6, '110100111111101000011000100110111100010' ),
( 53, 9,
'''01011001011111001000111001111010010010100010000010110''' ),
( 120, 7,
'''10101101100001000001010110010111110101111010011101001100000010001010011010110000
0000100110010100010010110111000000010110''' ),
( 220, 27,
'''11101111111010001001100110011001101000000010100011000111101100111111000001010000
10101101100111001000100110110101111000110101101000010000100110111101001001011010
110100100111011000110001101011110100110011010111110101010100''' ),
( 500, 87,
'''10100011011010011100011010010001010101000001111111001101011000000011001111111011
10011100110101111110110101000100110110011001101110011011100001000111110101011111
11001111000011001100111011101011000011111100010010011010001111000000101110101101
10101000011000111110001110010001011010001011111111101111000000011111010001000000
11100111101111010100100110000001000101000011101011010011010110011110111000010010
01111001000110100101100010000111001010011110111010001001011001111011111011010110
10101101111011101110''' ),
( 1002, 83,
'''00101001001001010000001101011111111010111101000101111110001110000110110110010101
11101100110111011001101110011101100100111101111010110011110101100001101010100011
11100011000111111101000111101001111111000011001011100110101100001101000001110010
01101000001001001000000110100000101111001110001110011110101001100111101101010000
01010100000110100111101010010010010000000011000100011011011001111010001101111000
01000010110100110010101110011111001100010011111110101101001100111101110000000000
11011001000000110000100101000101010010001100001000101001100110010100001000001101
11010001000010100110001010011010001000100011010001011101010100011101001101101100
01111101001100110011110000000010010010011001111001011111000010110000110010101000
10110011001111010001010001100001110101000010011011010111001101011001111000001011
11101010101011011110111111101000011001101000101100110011010000110000011011110011
00100000100000001111011010000011111011110100111110010101100011101001111101010000
111110001001100111011111100010100000010101''' ),
( 2107, 108,
"""01111101000110000111111011100101011000111001111011101001001110111110001100011001
10010101001010111011010010000101111111111001101010111011110100100101000101100011
11101000100100101011101000001111001010000111101011111100010010110000100110100100
01001101011100101100111100101011011001111110010011000110110111010110010100101110
01111111011100001110011111001000100100011010110011000101100111111001011110101110
01110101101111101101010001011001000110001011000011011110001111100110100010100101
11011111001100110011100100100010101011111000001001000110011110010011011101110100
10111111001100100110000101100101101010100110101000011011110001010000010001000110
10011101010010011101101111110100110101111111011001000110111001000011101101110001
00000111111010000101010111110110110000111111000000011100010011011001011000110101
11010111111000011000101100101100110000000001001111100101110100100011011010011100
00000011110101010001110110001101101000011010110011100110111010111110110000010000
10001010011110010001100001010100000101111011100001000110001100010000001011101110
10011111101000100100000110001001010101011001001001110110101000001001001100001011
00110111000111111001110011101011011100010111010000010011110110011011000011101001
11110110100100001011110000100000011001101001011101001000010101001001011111111011
10001110001000011011001011101000111111001011001111101111110110101111101111011111
10011111001101011101011111100100101011011111111111000100100111100011101110110100
01000110110010101101001011010000001100100010010001001110110100011111100011111101
01001101111011010101010101001101100110110001111111000100000111011010101011000010
00110111101101101101000110011011110010001000000011110011100111100000001010010011
10000111011111000001010101010100101001011010001011010100011011001110110010100000
10001111011110000101111111010101101101110110001111100011001110000100100101001111
00001111111000100110010100000101101110001000110110001000001100110000001011000010
10001011011100001011001000101011111000111000010010111101000010000110011010000001
00100011000010000011001101111101001001111001100110001000100101011111001011001111
110001011111001101010101001""" )
)

def getA( N, M, delay=0 ):
R = range(N)
lists_for_M = [ [ (j+k+delay) % N for k in range(M) ]
for j in R ]
return matrix( F, N, N, [ [ F(1) if k in lists_for_M[j]    else F(0)
for k in R ]
for j in R ] ).transpose()

def showVector( vec, separator='' ):
return separator.join( [ str( entry ) for entry in vec ] )

def exchange( wblocks, wpattern, b, k1, k2 ):
blocks, pattern = wblocks[:], wpattern[:]    # copy the information

for block in blocks:
block[k1] = F(1) - block[k1]
block[k2] = F(1) - block[k2]

pattern[k1] = b - pattern[k1]
pattern[k2] = b - pattern[k2]

return blocks, pattern

def blocksInformation( blocks ):
print "Blocks:"
for block in blocks:
print showVector( block )
print

# main search for all cases...
def searchLampSwitches( N, m, lamps
, showBlocks=False
, returnSolution=False ):
"""N, m, lamps is an entry in CASES..."""
print N, m, lamps

M = 2*m+1
d = gcd( N, M )
R = range( d )           # we will often loop using R
b = ZZ( N/d )            # number of blocks
bound = (b/2).floor()    # critical bound for the entries in pattern

print "N=%s M=%s d=gcd(N,M)=%s b=N/d=%s bound=%s" % ( N, M, d, b, bound )

A = getA( N, M, delay=-m )
v = matrix( F, N, 1, [ F(int(s)) for s in lamps if s in '01' ] )
w = vector( A.solve_right( v ) )

if d == 1:
# then w is already the (unique, thus optimal) solution
print "UNIQUE SOLUTION"
print sum( [ 1 for entry in w if entry ] )
print showVector( w )

return w if returnSolution else None

# else we build blocks
wblocks = [ [ w[ j + d*k ] for j in R ]
for k in range(N/d) ]

wpattern = [ sum( [ 1 for wblock in wblocks if wblock[k] ] )
for k in R ]
print "Initial pattern:",
print showVector( wpattern, separator = '' if b<10 else ',' )

if showBlocks:
blocksInformation( wblocks )

wplaces = [ k for k in R if wpattern[k] > bound ]    # suboptimal places in wpattern
wplaces . sort( lambda k1, k2:    cmp( -wpattern[k1], -wpattern[k2] ) )
print "Suboptimal places:", wplaces

while len( wplaces ) > 1:
k1, k2  = wplaces[:2]
wplaces = wplaces[2:]
wblocks, wpattern = exchange( wblocks, wpattern, b, k1, k2 )
print "New pattern:",
print showVector( wpattern, separator = '' if b<10 else ',' )
if showBlocks:
blocksInformation( wblocks )

# we count solutions, last changes can be done - but the   in case...
if wplaces:
k, = wplaces
# one last move is possible, if there are places with entries > then opposite of k'th place
# examples:
# b = 8 or 9, bound = 4, and
# ---> wpattern is 00011122233349 - then exchange 49
# ---> wpattern is 00011122233339 - then exchange 39
# ---> wpattern is 00011122222225 - no good exchange, 5 becomes 3 or 4, but the 2 (best choice) becomes > 5

goodoppositeplaces = [ kk for kk in R if kk != k and wpattern[kk] > b - wpattern[k] ]
if goodoppositeplaces:
goodoppositeplaces.sort( lambda k1, k2:    -cmp( wpattern[k1], wpattern[k2] ) )
# we can still get an optimization...
kk = goodoppositeplaces[0]
print "Last exchange possible, place %s can be moved (using place %s)" % ( k, kk )
wblocks, wpattern = exchange( wblocks, wpattern, b, k, kk )
wplaces = [ kk, ] if kk > bound else []
print "New pattern:",
print showVector( wpattern, separator = '' if b<10 else ',' )
if showBlocks:
blocksInformation( wblocks )

if wplaces:
k, = wplaces
oppositeplaces = [ kk for kk in R if wpattern[kk] + wpattern[k] == b ]
if not oppositeplaces:
print "UNIQUE SOLUTION, place %s cannot be moved" % k
else:
L = len( oppositeplaces )
print ( "%s = 2^%s SOLUTIONS, obtained by interchanging even number of positions in %s"
% ( 2**L, L, str( [k, ] + oppositeplaces ) ) )
else:
if b == 2*bound+1:
print "UNIQUE SOLUTION, all suboptimal places could be paired"
else:
midplaces = [ kk for kk in R if wpattern[kk] == bound ]
L = len( midplaces )
if L == 0 :
print "UNIQUE SOLUTION, all suboptimal places could be paired, none equal %s remained" % bound
elif L == 1:
print "UNIQUE SOLUTION, one middle place remained"
else:
print ( "%s = 2^%s SOLUTIONS, obtained by interchanging even number of middle positions in %s"
% ( 2**(L-1), L-1, str(midplaces) ) )

print "OPTIMAL NUMBER OF SWITCHES: %s" % sum(wpattern)
if not returnSolution:
return

sol = []
for wblock in wblocks:
sol += wblock
return sol

for N, m, lamps in CASES:
searchLampSwitches( N, m, lamps )
print 60*'.'


This delivers the solutions. I hope there are no problems with the above search logic (in some other particular cases).

case (0) For this, let us take the cases one by one...

sage: searchLampSwitches( *CASES[0], showBlocks=1, returnSolution=1 )
6 1 101101
N=6 M=3 d=gcd(N,M)=3 b=N/d=2 bound=1
Initial pattern: 101
Blocks:
101
000

Suboptimal places: []
2 = 2^1 SOLUTIONS, obtained by interchanging even number of middle positions in [0, 2]
OPTIMAL NUMBER OF SWITCHES: 2
[1, 0, 1, 0, 0, 0]


Here, the code solves the linear system, the first solution is 101 000 - splitted in two blocks - and writing the blocks over each other it is easy to see the pattern 101. All entries in the pattern are $\le$ bound, so this is already a solution.

Is there any other solution? Yes, the two places with the reached bound can be inverted in the same time, so we pass from

101
000
* *


to 000 101

The printed solution is simply the concatenation of the blocks (of the first solution found).

case (1)

sage: searchLampSwitches( *CASES[1], showBlocks=1 )
10 2 1011010110
N=10 M=5 d=gcd(N,M)=5 b=N/d=2 bound=1
Initial pattern: 21111
Blocks:
11111
10000

Suboptimal places: [0]
Last exchange possible, place 0 can be moved (using place 1)
New pattern: 01111
Blocks:
00111
01000

8 = 2^3 SOLUTIONS, obtained by interchanging even number of middle positions in [1, 2, 3, 4]
OPTIMAL NUMBER OF SWITCHES: 4


So the first solution given by a sage solve had the pattern 21111 and the sum of the entries is 6. We can do better, e.g. inverting the places 0 and 1. (Or 0 and 2, or 0 and 3, or...) Doing this the pattern moves from

21111
*        to
01111


which is better, the number of switches is 4, the sum of the entries in this pattern.

case (2)

sage: searchLampSwitches( *CASES[2], showBlocks=1 )
20 1 11111011101010111111
N=20 M=3 d=gcd(N,M)=1 b=N/d=20 bound=10
UNIQUE SOLUTION
8
01001010011100010010


case (3)

sage: searchLampSwitches( *CASES[3], showBlocks=1 )
30 7 011100001010011011100001010011
N=30 M=15 d=gcd(N,M)=15 b=N/d=2 bound=1
Initial pattern: 111101011001000
Blocks:
111101011001000
000000000000000

Suboptimal places: []
128 = 2^7 SOLUTIONS, obtained by interchanging even number of middle positions in [0, 1, 2, 3, 5, 7, 8, 11]
OPTIMAL NUMBER OF SWITCHES: 8


case (4)

sage: searchLampSwitches( *CASES[4] )
39 6 110100111111101000011000100110111100010
N=39 M=13 d=gcd(N,M)=13 b=N/d=3 bound=1
Initial pattern: 3200221112201
Suboptimal places: [0, 1, 4, 5, 9, 10]
New pattern: 0100221112201
New pattern: 0100111112201
New pattern: 0100111111101
UNIQUE SOLUTION, all suboptimal places could be paired
OPTIMAL NUMBER OF SWITCHES: 9


The initial pattern was changed as follows:

**  **   **
3200221112201
||
0100221112201
||
0100111112201
||
0100111111101


and each change was moving an entry to the opposite one, entry -> 3-entry where 3 is the value of b. To see the blocks from one step to the next one, use searchLampSwitches( *CASES[4], showBlocks=True ) .

case (5)

sage: searchLampSwitches( *CASES[5] )
53 9 01011001011111001000111001111010010010100010000010110
N=53 M=19 d=gcd(N,M)=1 b=N/d=53 bound=26
UNIQUE SOLUTION
25
00100010111110010100010100111011100010110001000011101


case (6)

sage: searchLampSwitches( *CASES[6] )
120 7 10101101100001000001010110010111110101111010011101001100000010001010011010110000
0000100110010100010010110111000000010110
N=120 M=15 d=gcd(N,M)=15 b=N/d=8 bound=4
Initial pattern: 543553565644234
Suboptimal places: [7, 9, 0, 3, 4, 6, 8]
New pattern: 543553525244234
New pattern: 343353525244234
New pattern: 343333325244234
Last exchange possible, place 8 can be moved (using place 1)
New pattern: 343333323244234
8 = 2^3 SOLUTIONS, obtained by interchanging even number of middle positions in [1, 10, 11, 14]
OPTIMAL NUMBER OF SWITCHES: 46


case (7)

sage: searchLampSwitches( *CASES[7] )
220 27 11101111111010001001100110011001101000000010100011000111101100111111000001010000
10101101100111001000100110110101111000110101101000010000100110111101001001011010
110100100111011000110001101011110100110011010111110101010100
N=220 M=55 d=gcd(N,M)=55 b=N/d=4 bound=2
Initial pattern: 2202111113323112222323223212121310210122201222122130112
Suboptimal places: [9, 10, 12, 19, 21, 24, 31, 50]
New pattern: 2202111111123112222323223212121310210122201222122130112
New pattern: 2202111111121112222123223212121310210122201222122130112
New pattern: 2202111111121112222121221212121310210122201222122130112
New pattern: 2202111111121112222121221212121110210122201222122110112
8388608 = 2^23 SOLUTIONS, obtained by interchanging even number of middle positions in [0, 1, 3, 11, 15, 16, 17, 18, 20, 22, 23, 25, 27, 29, 34, 38, 39, 40, 43, 44, 45, 47, 48, 54]
OPTIMAL NUMBER OF SWITCHES: 74


case (8)

sage: searchLampSwitches( *CASES[8] )
500 87 10100011011010011100011010010001010101000001111111001101011000000011001111111011
10011100110101111110110101000100110110011001101110011011100001000111110101011111
11001111000011001100111011101011000011111100010010011010001111000000101110101101
10101000011000111110001110010001011010001011111111101111000000011111010001000000
11100111101111010100100110000001000101000011101011010011010110011110111000010010
01111001000110100101100010000111001010011110111010001001011001111011111011010110
10101101111011101110
N=500 M=175 d=gcd(N,M)=25 b=N/d=20 bound=10
Initial pattern: 12,7,11,11,6,7,2,7,10,7,10,11,8,11,9,11,12,9,10,8,11,9,8,8,9
Suboptimal places: [0, 16, 2, 3, 11, 13, 15, 20]
New pattern: 8,7,11,11,6,7,2,7,10,7,10,11,8,11,9,11,8,9,10,8,11,9,8,8,9
New pattern: 8,7,9,9,6,7,2,7,10,7,10,11,8,11,9,11,8,9,10,8,11,9,8,8,9
New pattern: 8,7,9,9,6,7,2,7,10,7,10,9,8,9,9,11,8,9,10,8,11,9,8,8,9
New pattern: 8,7,9,9,6,7,2,7,10,7,10,9,8,9,9,9,8,9,10,8,9,9,8,8,9
4 = 2^2 SOLUTIONS, obtained by interchanging even number of middle positions in [8, 10, 18]
OPTIMAL NUMBER OF SWITCHES: 204


case (9)

The output needs a different width, but searchLampSwitches( *CASES[9] ) returns with no problems a long mess ending with:

New pattern: 23323322012222322331131122211213222333221213322223312122223212221213222322132131212212332123223232223021321133122121221223122322233222122132231331101333212232123243212
Last exchange possible, place 162 can be moved (using place 1)
New pattern: 23323322012222322331131122211213222333221213322223312122223212221213222322132131212212332123223232223021321133122121221223122322233222122132231331101333212232123223212
8796093022208 = 2^43 SOLUTIONS, obtained by interchanging even number of middle positions in [1, 2, 4, 5, 14, 17, 18, 21, 31, 35, 36, 37, 43, 44, 49, 50, 58, 67, 71, 75, 78, 86, 87, 91, 94, 96, 100, 104, 108, 109, 121, 125, 129, 130, 138, 141, 143, 144, 149, 150, 151, 156, 160, 163]
OPTIMAL NUMBER OF SWITCHES: 334


case (10)

The call of searchLampSwitches( *CASES[10] ) returns after computing the solution...

N=2107 M=217 d=gcd(N,M)=7 b=N/d=301 bound=150
Initial pattern: 142,160,145,155,153,142,138
Suboptimal places: [1, 3, 4]
New pattern: 142,141,145,146,153,142,138
UNIQUE SOLUTION, place 4 cannot be moved
OPTIMAL NUMBER OF SWITCHES: 1007


That is all so far.

more

Apparently, we proposed very similar solutions. I see you take a transpose, note that the matrix is symmetric.

( 2017-10-30 15:43:58 -0600 )edit

Yes, i would say it is the same solution.

Above, i am taking the transpose of the basis of the kernel, since it is simpler to display. The "beginning" is

sage: print K.matrix().transpose().str()
[1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 1 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 1 0 0 0 0 0 0]
[0 0 ...
(more)
( 2017-10-30 17:43:01 -0600 )edit

( 2017-10-31 05:32:05 -0600 )edit

Oh, i also saw now, after re-edit an other transposition while building the matrix A. It was in order to "see" the first column vector in A as the one i had on the paper. My matrix is slightly shifted...

( 2017-11-02 05:01:28 -0600 )edit

Thanks for that! I had problems to run the code. I just copied and pasted it directly to the Sage. I got TypeError: unable to find a common ring for all elements The same error appears if I run the code by sage lamps.sage

( 2017-11-07 10:08:19 -0600 )edit