lights_solver.py

import binascii, sys

import psyco; psyco.full()

def main():
    # arr = [ord(x) for x in binascii.a2b_hex("C766FCD65CB60DE829633BA8D8B823526FF8239C1DD6DE73EB963536B3483346")]
    # print arr

    #data = open("data-original", "rb").read()[8:]


    # for i in xrange(256):
        # if data[i] == "\x00":
            # arr[i >> 3] ^= 1 << (7 - (i & 7))
            
    # print repr("".join([chr(x) for x in arr]))

    grid = open("data-original", "rb").read()[8:].replace("\x00", "0").replace("\x01", "1")
    grid = [int(x) for x in grid]

    #print grid

    sx = 128
    sy = 128
    sz = sx * sy
    eqs = []
    for y in xrange(sx):
        for x in xrange(sy):
            eq = 0
            for dx, dy in ((-2,0),(-1,-1),(0,-2),(1,-1),(2,0),(1,1),(0,2),(-1,1)):
                tx = x + dx
                ty = y + dy
                if tx >= 0 and tx < sx and ty >= 0 and ty < sy:
                    eq |= 1 << (tx+ty*sx)
                    
            eq = (eq << 1) | grid[x+y*sx]
            eqs.append(eq)
            
    for i in xrange(sz):
        if i % 128 == 0:
            sys.stderr.write(str(i / 128) + "\n")
        bit = 1 << (sz - i)
        found = None
        for j in xrange(sz):
            if eqs[j] & bit != 0 and eqs[j] < (bit << 1):
                found = j
                break
                
        for j in xrange(sz):
            if eqs[j] & bit != 0 and j != found:
                eqs[j] ^= eqs[found]
            

    for eq in eqs:
        if eq & 1 == 1:
            for i in xrange(sx*sy):
                if (eq >> i) & 2 == 2:
                    print "%3dx %3dy" % (i % sx, i / sy)
            

main()