Shutting down all lamps with minimum number of switch presses












0












$begingroup$


I found an optimization problem. The following is an example case.




I have n=120 lamps in a circle, and enumerated by L1,…,L120. 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 Li
and then the lamps Li−m,…,Li+m will change their state, I mean if lamp
Lj was turned off then now it is turned on and vice versa. Indexes are
modulo n so the lamps L118,L119,L1,L2 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
L1 to L120)



1010110110000100000101011001011111010111

                                        1010011101001100000010001010011010110000

                                        0000100110010100010010110111000000010110


The list of cases is as follows:



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

================================================================================



I was wondering how to solve the case I. I tried to solve it by Sage but my algorithm seems to be too slow. How can I make the program such that it finds the optimal solution and stops the computing as it find it?



Current code:



room = 

input = 

m = 

room.append('I')

input.append('1110111111101000100110011001100110100000001010001100011110110011111100000101000010101101100111001000100110110101111000110101101000010000100110111101001001011010110100100111011000110001101011110100110011010111110101010100')

m.append(27)

F = GF(2)

L_init = vector(F,input[0])

d = len(L_init)

M = matrix(F,d,d)

for i in range(d):

   for j in range(-m[0],m[0]+1 ):

       M[i,(i+j) % d] = 1

I = M.solve_right(L_init)

K = M.right_kernel()

best = None

for k in K:

    A = (I+k).nonzero_positions()

    B= 

    if len((I+k).nonzero_positions()) < best or best == None:

        S = room[0] + ' '

        best = len((I+k).nonzero_positions())

        for i in range(len(A)):

            S +=str(int(A[i])+1) + ' '

        print(S)

print("Optimal:")


Output thus far:



I 1 2 4 6 8 10 11 12 13 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 55 56 62 65 66 67 68 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 112 114 115 119 120 121 123 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 165 

I 1 2 4 6 8 11 12 13 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 56 62 66 67 68 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 110 112 114 115 119 121 123 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 175 220 

I 1 2 4 6 8 12 13 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 55 56 62 67 68 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 112 114 115 119 123 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 165 175 176 

I 1 2 4 6 8 12 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 56 62 67 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 110 112 114 115 119 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 175 176 178 220 

I 1 2 4 6 8 12 18 19 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 55 56 62 67 70 71 72 74 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 112 114 115 119 124 126 127 128 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 165 175 176 178 185





python mathematics







share|improve this question









New contributor




sagemathematician is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$

















    0












    $begingroup$


    I found an optimization problem. The following is an example case.




    I have n=120 lamps in a circle, and enumerated by L1,…,L120. 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 Li
    and then the lamps Li−m,…,Li+m will change their state, I mean if lamp
    Lj was turned off then now it is turned on and vice versa. Indexes are
    modulo n so the lamps L118,L119,L1,L2 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
    L1 to L120)



    1010110110000100000101011001011111010111
    
                                        1010011101001100000010001010011010110000
    
                                        0000100110010100010010110111000000010110


    The list of cases is as follows:



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



    I was wondering how to solve the case I. I tried to solve it by Sage but my algorithm seems to be too slow. How can I make the program such that it finds the optimal solution and stops the computing as it find it?



    Current code:



    room = 
    
input = 
    
m = 
    
room.append('I')
    
input.append('1110111111101000100110011001100110100000001010001100011110110011111100000101000010101101100111001000100110110101111000110101101000010000100110111101001001011010110100100111011000110001101011110100110011010111110101010100')
    
m.append(27)
    
F = GF(2)
    
L_init = vector(F,input[0])
    
d = len(L_init)
    
M = matrix(F,d,d)
    
for i in range(d):
    
   for j in range(-m[0],m[0]+1 ):
    
       M[i,(i+j) % d] = 1
    
I = M.solve_right(L_init)
    
K = M.right_kernel()
    
best = None
    
for k in K:
    
    A = (I+k).nonzero_positions()
    
    B= 
    
    if len((I+k).nonzero_positions()) < best or best == None:
    
        S = room[0] + ' '
    
        best = len((I+k).nonzero_positions())
    
        for i in range(len(A)):
    
            S +=str(int(A[i])+1) + ' '
    
        print(S)
    
print("Optimal:")


    Output thus far:



    I 1 2 4 6 8 10 11 12 13 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 55 56 62 65 66 67 68 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 112 114 115 119 120 121 123 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 165 
    
I 1 2 4 6 8 11 12 13 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 56 62 66 67 68 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 110 112 114 115 119 121 123 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 175 220 
    
I 1 2 4 6 8 12 13 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 55 56 62 67 68 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 112 114 115 119 123 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 165 175 176 
    
I 1 2 4 6 8 12 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 56 62 67 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 110 112 114 115 119 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 175 176 178 220 
    
I 1 2 4 6 8 12 18 19 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 55 56 62 67 70 71 72 74 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 112 114 115 119 124 126 127 128 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 165 175 176 178 185





    python mathematics







    share|improve this question









    New contributor




    sagemathematician is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.







    $endgroup$















      0












      0








      0





      $begingroup$


      I found an optimization problem. The following is an example case.




      I have n=120 lamps in a circle, and enumerated by L1,…,L120. 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 Li
      and then the lamps Li−m,…,Li+m will change their state, I mean if lamp
      Lj was turned off then now it is turned on and vice versa. Indexes are
      modulo n so the lamps L118,L119,L1,L2 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
      L1 to L120)



      1010110110000100000101011001011111010111
      
                                        1010011101001100000010001010011010110000
      
                                        0000100110010100010010110111000000010110


      The list of cases is as follows:



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



      I was wondering how to solve the case I. I tried to solve it by Sage but my algorithm seems to be too slow. How can I make the program such that it finds the optimal solution and stops the computing as it find it?



      Current code:



      room = 
      
input = 
      
m = 
      
room.append('I')
      
input.append('1110111111101000100110011001100110100000001010001100011110110011111100000101000010101101100111001000100110110101111000110101101000010000100110111101001001011010110100100111011000110001101011110100110011010111110101010100')
      
m.append(27)
      
F = GF(2)
      
L_init = vector(F,input[0])
      
d = len(L_init)
      
M = matrix(F,d,d)
      
for i in range(d):
      
   for j in range(-m[0],m[0]+1 ):
      
       M[i,(i+j) % d] = 1
      
I = M.solve_right(L_init)
      
K = M.right_kernel()
      
best = None
      
for k in K:
      
    A = (I+k).nonzero_positions()
      
    B= 
      
    if len((I+k).nonzero_positions()) < best or best == None:
      
        S = room[0] + ' '
      
        best = len((I+k).nonzero_positions())
      
        for i in range(len(A)):
      
            S +=str(int(A[i])+1) + ' '
      
        print(S)
      
print("Optimal:")


      Output thus far:



      I 1 2 4 6 8 10 11 12 13 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 55 56 62 65 66 67 68 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 112 114 115 119 120 121 123 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 165 
      
I 1 2 4 6 8 11 12 13 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 56 62 66 67 68 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 110 112 114 115 119 121 123 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 175 220 
      
I 1 2 4 6 8 12 13 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 55 56 62 67 68 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 112 114 115 119 123 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 165 175 176 
      
I 1 2 4 6 8 12 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 56 62 67 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 110 112 114 115 119 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 175 176 178 220 
      
I 1 2 4 6 8 12 18 19 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 55 56 62 67 70 71 72 74 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 112 114 115 119 124 126 127 128 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 165 175 176 178 185





      python mathematics







      share|improve this question









      New contributor




      sagemathematician is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.







      $endgroup$




      I found an optimization problem. The following is an example case.




      I have n=120 lamps in a circle, and enumerated by L1,…,L120. 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 Li
      and then the lamps Li−m,…,Li+m will change their state, I mean if lamp
      Lj was turned off then now it is turned on and vice versa. Indexes are
      modulo n so the lamps L118,L119,L1,L2 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
      L1 to L120)



      1010110110000100000101011001011111010111
      
                                        1010011101001100000010001010011010110000
      
                                        0000100110010100010010110111000000010110


      The list of cases is as follows:



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



      I was wondering how to solve the case I. I tried to solve it by Sage but my algorithm seems to be too slow. How can I make the program such that it finds the optimal solution and stops the computing as it find it?



      Current code:



      room = 
      
input = 
      
m = 
      
room.append('I')
      
input.append('1110111111101000100110011001100110100000001010001100011110110011111100000101000010101101100111001000100110110101111000110101101000010000100110111101001001011010110100100111011000110001101011110100110011010111110101010100')
      
m.append(27)
      
F = GF(2)
      
L_init = vector(F,input[0])
      
d = len(L_init)
      
M = matrix(F,d,d)
      
for i in range(d):
      
   for j in range(-m[0],m[0]+1 ):
      
       M[i,(i+j) % d] = 1
      
I = M.solve_right(L_init)
      
K = M.right_kernel()
      
best = None
      
for k in K:
      
    A = (I+k).nonzero_positions()
      
    B= 
      
    if len((I+k).nonzero_positions()) < best or best == None:
      
        S = room[0] + ' '
      
        best = len((I+k).nonzero_positions())
      
        for i in range(len(A)):
      
            S +=str(int(A[i])+1) + ' '
      
        print(S)
      
print("Optimal:")


      Output thus far:



      I 1 2 4 6 8 10 11 12 13 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 55 56 62 65 66 67 68 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 112 114 115 119 120 121 123 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 165 
      
I 1 2 4 6 8 11 12 13 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 56 62 66 67 68 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 110 112 114 115 119 121 123 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 175 220 
      
I 1 2 4 6 8 12 13 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 55 56 62 67 68 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 112 114 115 119 123 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 165 175 176 
      
I 1 2 4 6 8 12 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 56 62 67 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 110 112 114 115 119 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 175 176 178 220 
      
I 1 2 4 6 8 12 18 19 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 55 56 62 67 70 71 72 74 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 112 114 115 119 124 126 127 128 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 165 175 176 178 185





      python mathematics




      python mathematics






      share|improve this question









      New contributor




      sagemathematician is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.











      share|improve this question









      New contributor




      sagemathematician is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      share|improve this question




      share|improve this question








      edited 8 mins ago







      sagemathematician













      New contributor




      sagemathematician is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      asked 12 hours ago









      sagemathematiciansagemathematician

      11




      11




      New contributor




      sagemathematician is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.





      New contributor





      sagemathematician is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






      sagemathematician is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






















          0






          active

          oldest

          votes











          Your Answer





          StackExchange.ifUsing("editor", function () {
          return StackExchange.using("mathjaxEditing", function () {
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
          });
          });
          }, "mathjax-editing");

          StackExchange.ifUsing("editor", function () {
          StackExchange.using("externalEditor", function () {
          StackExchange.using("snippets", function () {
          StackExchange.snippets.init();
          });
          });
          }, "code-snippets");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "196"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });






          sagemathematician is a new contributor. Be nice, and check out our Code of Conduct.










          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f215764%2fshutting-down-all-lamps-with-minimum-number-of-switch-presses%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          0






          active

          oldest

          votes








          0






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes








          sagemathematician is a new contributor. Be nice, and check out our Code of Conduct.










          draft saved

          draft discarded


















          sagemathematician is a new contributor. Be nice, and check out our Code of Conduct.













          sagemathematician is a new contributor. Be nice, and check out our Code of Conduct.












          sagemathematician is a new contributor. Be nice, and check out our Code of Conduct.
















          Thanks for contributing an answer to Code Review Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid …



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f215764%2fshutting-down-all-lamps-with-minimum-number-of-switch-presses%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          -

          Popular posts from this blog

          Сан-Квентин

          Image
          Сан-Квентин Местоположение Сан-Квентин, Калифорния Координаты 37°56′13″ с. ш. 122°29′20″ з. д. H G Я O L Текущий статус Действует Режим безопасности минимальный и максимальный Количество мест 3 302 Открытие Июнь 1852 Находится в ведомстве California Department of Corrections and Rehabilitation Начальник Mike Martel, начальник  Сан-Квентин на Викискладе Сан-Квентин (англ.  San Quentin ) — тюрьма, располагающаяся на 432 акрах (около 1,7 км²), на мысе Сан-Квентин, в округе Марин, штат Калифорния, США. Тюрьма штата Калифорния Сан-Квентин была открыта в июле 1852 года и является старейшей в штате. Она была построена заключёнными, которые проживали в течение строительства на тюремном судне Вабан. В Сан-Квентине отбывали наказание и мужчины, и женщины до 1934 года, когда построили женскую тюрьму в Техачапи и туда перевели всех заключённых женщин. В Сан-Квентине приводятся в исполнение смертные казни, для этого имеется газовая камера, но...
          Read more

          8-я гвардейская общевойсковая армия

          Image
          8-я гвардейская общевойсковая ордена Ленина армия Награды: Войска: РККА → Советская армия → СВ России Род войск: Формирование: 1943 Расформирование (преобразование): 1992 Предшественник: 62-я армия (1942—43) → 8-я гвардейская общевойсковая армия (1943—92) → 8-й гвардейский армейский корпус (1992—98) Боевой путь Изюм-Барвенковская операция Донбасская операция Запорожская операция Битва за Днепр Днепропетровская операция Березнеговато-Снигирёвская операция Одесская операция Люблин-Брестская операция Варшавско-Познанская операция Восточно-Померанская операция Берлинская наступательная операция У этого термина существуют и другие значения, см. 8-я армия. Фотография Гвардейского Красного Знамени (лицевая сторона) 8-й гвардейской армии , образца 1943 года. Фотография Гвардейского Красного Знамени (оборотная сторона) 8-й гвардейской армии , образца 1943 года. 8-я гвардейская общевойсковая ордена Ленина армия  — гвардейское фор...
          Read more

          Алькесар

          Image
          Муниципалитет Алькесар Alquézar Герб 42°10′16″ с. ш. 0°01′27″ в. д. H G Я O L Страна Испания   Испания Автономное сообщество Арагон Провинция Уэска Комарка Сомонтано-де-Барбастро Алькальд Хосе Марияно Альтемир Ласкорс (ИСРП) История и география Площадь 32,36 км² Высота НУМ 660 м Часовой пояс UTC+1, летом UTC+2 Население Население 313 человек ( 2010 ) Плотность 9,92 чел./км² Этнохороним alquezarano/-a Цифровые идентификаторы Телефонный код +34 974 Почтовые индексы 22112 Автомобильный код HU alquezar.org   (исп.) Показать/скрыть карты Алькесар Алькесар Алькесар  Аудио, фото и видео на Викискладе Алькесар (исп.  Alquézar ) — муниципалитет в Испании, входит в провинцию Уэска, в составе автономного сообщества Арагон. Муниципалитет находится в составе района (комарки) Сомонтано-де-Барбастро. Занимает площадь 32,36 км². Население — 321 челове...
          Read more