1 | initial version |

The same code from the other post,

https://ask.sagemath.org/question/39335/...

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

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.