# How to find swich presses on lamp shutting problem?

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

The following is an example case.

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

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.

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


I know there is a solution that compputes the minimum number of switch presses in https://ask.sagemath.org/question/393... . But the next task is to list those switches I need to press.

I tried

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")


but this seems to be too slow. It has printed only

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


after couple of days computation. So how can I found the optimal solution faster?

edit retag close merge delete

Sort by » oldest newest most voted

The same code from the other post,

was copied here again in the final P.S.

It delivers details on the computation done, and the solution. One only has to set correspondingly the optional parameters showBlocks and returnSolution in the final call

sol = searchLampSwitches( N, m, lamps
, showBlocks=True
, returnSolution=True )


(The way to get the solution was explained in detail in some small cases in loc. cit.. The title of that post is How to find a minimum number of switch presses to shut down all lamps? - there are two answers showing how to do this, including thoughts, algorithm, and code, however still after years there is no answer accepted. Anyway...)

In this case:

120 7 101011011000010000010101100101111101011110100111010011000000100010100110101100000000100110010100010010110111000000010110
N=120 M=15 d=gcd(N,M)=15 b=N/d=8 bound=4
Initial pattern: 543553565644234
Blocks:
001110111111011
011111011110100
110100111111011
110011101100110
100011110101001
110100011101001
101110110010000
000000000000000

Suboptimal places: [7, 9, 0, 3, 4, 6, 8]
New pattern: 543553525244234
Blocks:
001110101011011
011111001010100
110100101011011
110011111000110
100011100001001
110100001001001
101110100110000
000000010100000

New pattern: 343353525244234
Blocks:
101010101011011
111011001010100
010000101011011
010111111000110
000111100001001
010000001001001
001010100110000
100100010100000

New pattern: 343333325244234
Blocks:
101000001011011
111001101010100
010010001011011
010101011000110
000101000001001
010010101001001
001000000110000
100110110100000

Last exchange possible, place 8 can be moved (using place 1)
New pattern: 343333323244234
Blocks:
111000000011011
101001100010100
000010000011011
000101010000110
010101001001001
000010100001001
011000001110000
110110111100000

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


P.S. The solution was produced as follows:

F = GF(2)

N = 120
m = 7
lamps = ''.join( [ s for s in """
1010110110000100000101011001011111010111
1010011101001100000010001010011010110000
0000100110010100010010110111000000010110
""".split('\n') if s ] )

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

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

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

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

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

return blocks, pattern

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

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

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

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

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

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

return w if returnSolution else None

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

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

if showBlocks:
blocksInformation( wblocks )

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

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

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

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

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

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

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

sol = searchLampSwitches( N, m, lamps
, showBlocks=True
, returnSolution=True )

print sol

more