Revision history [back]

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