Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

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:

What would be the suitable algorithm for this one?

I have $n=2107$ lamps in a circle, and enumerated by $L_1,\ldots,L_{2107}$. Some of them are switched on and some of them are switched off. I also have been given a positive integer $m=108.$ One every turn I choose one lamp $L_i$ and then the lamps $L_{i-m},\ldots,L_{l+m}$ will change their state, I mean if lamp $L_j$ was turned off then now it is turned on and vice versa. 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_{2107}$)

                                        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

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:

What would be the suitable algorithm for this one?

I have $n=2107$ $n=120$ lamps in a circle, and enumerated by $L_1,\ldots,L_{2107}$. $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=108.$ $m=7.$ One every turn I choose one lamp $L_i$ and then the lamps $L_{i-m},\ldots,L_{l+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_{2107}$)$L_{120}$)

 1010110110000100000101011001011111010111
 1010011101001100000010001010011010110000
                                      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
0000100110010100010010110111000000010110

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:

What would be the suitable algorithm for this one?

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_{l+m}$ $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

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:

What would be the suitable algorithm for this one?

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.

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:

What would be the suitable algorithm for this one?

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:

I tried the algorithm given by tmontell. It works but it is 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.

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:

What would be the suitable algorithm for this one?the problem given in https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=muslam

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:

I tried the algorithm given by tmontell. It works but it is 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.

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:

What would be the suitable algorithm for the problem given in https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=muslam

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:

I tried the algorithm given by tmontell. It works but it is 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.

All cases 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
================================================================================

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:

What would be the suitable algorithm for the problem Sage given in https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=muslamhttps://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=muslam :

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:

I tried the algorithm given by tmontell. It works but it is 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.

All cases 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
================================================================================

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/postit/tehtava.php?tunnus=muslam :

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:

I tried It was wonderful to read the algorithm solutions given by dan_fulea and tmontell. It Those works but it is 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.

All cases 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
================================================================================

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/postit/tehtava.php?tunnus=muslam :

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:

It was wonderful to read the solutions given by dan_fulea and tmontell. Those 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.

All cases 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
================================================================================

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/postit/tehtava.php?tunnus=muslam :

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:

It was wonderful to read the solutions given by dan_fulea and tmontell. Those 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
================================================================================

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/postit/tehtava.php?tunnus=muslam :

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:

It was wonderful to read the solutions given by dan_fulea and tmontell. Those 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
================================================================================

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/postit/tehtava.php?tunnus=muslam :

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:

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
================================================================================

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/postit/tehtava.php?tunnus=muslam :

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: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/community/c163h564755_shutting_down_all_lamps 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?