Tokyo Westerns / MMA CTF 2nd 2016 [Warmup][PPC][100pts]Lights Out!

lights_out_100.py

# coding: utf-8

from operator import add
from itertools import chain, combinations
import json
from textwrap import wrap
import numpy as np
from scipy import ndimage

class GF2(object):

    def __init__(self, a=0):
        self.value = int(a) & 1

    def __add__(self, rhs):
        return GF2(self.value + GF2(rhs).value)

    def __mul__(self, rhs):
        return GF2(self.value * GF2(rhs).value)

    def __sub__(self, rhs):
        return GF2(self.value - GF2(rhs).value)

    def __div__(self, rhs):
        return GF2(self.value / GF2(rhs).value)

    def __repr__(self):
        return str(self.value)

    def __eq__(self, rhs):
        if isinstance(rhs, GF2):
            return self.value == rhs.value
        return self.value == rhs

    def __le__(self, rhs):
        if isinstance(rhs, GF2):
            return self.value <= rhs.value
        return self.value <= rhs

    def __lt__(self, rhs):
        if isinstance(rhs, GF2):
            return self.value < rhs.value
        return self.value < rhs

    def __int__(self):
        return self.value

    def __long__(self):
        return self.value


GF2array = np.vectorize(GF2)

def gjel(A):
    #Gauss-Jordan elimination
    nulldim = 0
    for i in xrange(len(A)):
        pivot = A[i:,i].argmax() + i
        if A[pivot,i] == 0:
            nulldim = len(A) - i
            break
        row = A[pivot] / A[pivot,i]
        A[pivot] = A[i]
        A[i] = row

        for j in xrange(len(A)):
            if j == i:
                continue
            A[j] -= row*A[j,i]
    return A, nulldim

def GF2inv(A):
    n = len(A)
    assert n == A.shape[1], "Matrix must be square"

    A = np.hstack([A, np.eye(n)])
    B, nulldim = gjel(GF2array(A))

    inverse = np.int_(B[-n:, -n:])
    E = B[:n, :n]
    null_vectors = []
    if nulldim > 0:
        null_vectors = E[:, -nulldim:]
        null_vectors[-nulldim:, :] = GF2array(np.eye(nulldim))
        null_vectors = np.int_(null_vectors.T)

    return inverse, null_vectors

def click(p, size, offsets):
    x, y = p
    for i, j in offsets:
        p, q = x + i, y + j
        if 0 <= p < size and 0 <= q < size:
            yield (p, q)

def pos2index(p, size):
    return p[0] * size + p[1]

def index2pos(idx, size):
    return (idx // size, idx % size)

def lightsoutbase(n):
    #Base of the LightsOut problem of size (n,n) for normal
    a = np.eye(n*n)
    a = np.reshape(a, (n*n,n,n))
    a = np.array(map(ndimage.binary_dilation, a))
    return np.reshape(a, (n*n, n*n))

def lightsoutsbase(n):
    #Base of the LightsOut problem of size (n,n) for CTF
    slot_count = n*n
    click_offsets = [ (x, y) for x in range(-2, 3) for y in range(-2, 3) if abs(x) + abs(y) == 2 ]
    M = np.zeros((slot_count, slot_count), int)
    for i in range(slot_count):
        for p in click(index2pos(i, n), n, click_offsets):
            M[i, pos2index(p, n)] = 1
        x, y = index2pos(i, n)

    return M

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

class LightsOut(object):

    def __init__(self, size=5):
        self.n = size
        self.base = lightsoutsbase(self.n)
        self.invbase, self.null_vectors = GF2inv(self.base)

    def solve(self, b):
        b = np.asarray(b)
        assert b.shape[0] == b.shape[1] == self.n, "incompatible shape"

        if not self.issolvable(b):
            raise ValueError, "The given setup is not solvable"

        # Find the base solution.
        first = np.dot(self.invbase, b.ravel()) & 1

        # Given a solution, we can find more valid solutions
        # adding any combination of the null vectors.
        # Find the solution with the minimum number of 1's.
        solutions = [(first + reduce(add, nvs, 0))&1 for nvs in powerset(self.null_vectors)]
        final = min(solutions, key=lambda x: x.sum())
        return np.reshape(final, (self.n,self.n))

    def issolvable(self, b):
        b = np.asarray(b)
        assert b.shape[0] == b.shape[1] == self.n, "incompatible shape"
        b = b.ravel()
        p = map(lambda x: np.dot(x,b)&1, self.null_vectors)
        return not any(p)


def main():

    '''
    Print "Prase data and print it as array"
    data = '0111000001000110111100000101100111111001100111011000101001000000111110011000111011100111100100001000101000000100110100010110000001010001001110100111010010110000001100011011001101110100000110000111111010011111111000110000111110001000100000101011001100010000110001000110111010101011100001101111101010110100010011111011010100000100100011000111010100001011100001001101111010101010111011001011111010000001'
    data = wrap(data, int(len(data) ** 0.5))
    data = [ list(map(int, r)) for r in data ]
    data = np.array(json.dumps(data))
    print data
    '''



    print 'Easy'
    print 'Start Creating LightsOut Object'
    lo = LightsOut(5)
    print 'Created LightsOut Object'
    b = np.array([[1,1,0,1,1],
                  [1,0,0,0,1],
                  [0,0,0,0,0],
                  [1,0,0,0,1],
                  [1,1,0,1,1]])


    '''
        Solution 1 for Easy
        [[0 0 0 0 0]
        [1 1 0 1 1]
        [0 0 0 0 0]
        [1 1 0 1 1]
        [0 0 0 0 0]]

        Solution 2 for Easy
        [[1 1 1 1 1]
        [0 0 0 0 0]
        [0 0 0 0 0]
        [0 0 0 0 0]
        [1 1 1 1 1]]
    '''


    '''
    print 'Normal'
    print 'Start Creating LightsOut Object'
    lo = LightsOut(20)
    print 'Created LightsOut Object'
    b = np.array([[0,1,1,1,0,0,0,0,0,1,0,0,0,1,1,0,1,1,1,1],
                  [0,0,0,0,0,1,0,1,1,0,0,1,1,1,1,1,1,0,0,1],
                  [1,0,0,1,1,1,0,1,1,0,0,0,1,0,1,0,0,1,0,0],
                  [0,0,0,0,1,1,1,1,1,0,0,1,1,0,0,0,1,1,1,0],
                  [1,1,1,0,0,1,1,1,1,0,0,1,0,0,0,0,1,0,0,0],
                  [1,0,1,0,0,0,0,0,0,1,0,0,1,1,0,1,0,0,0,1],
                  [0,1,1,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,1,1],
                  [1,0,1,0,0,1,1,1,0,1,0,0,1,0,1,1,0,0,0,0],
                  [0,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,1],
                  [0,1,0,0,0,0,0,1,1,0,0,0,0,1,1,1,1,1,1,0],
                  [1,0,0,1,1,1,1,1,1,1,1,0,0,0,1,1,0,0,0,0],
                  [1,1,1,1,1,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0],
                  [1,0,1,1,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,0],
                  [0,1,0,0,0,1,1,0,1,1,1,0,1,0,1,0,1,0,1,1],
                  [1,0,0,0,0,1,1,0,1,1,1,1,1,0,1,0,1,0,1,1],
                  [0,1,0,0,0,1,0,0,1,1,1,1,1,0,1,1,0,1,0,1],
                  [0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,0,0,1,1,1],
                  [0,1,0,1,0,0,0,0,1,0,1,1,1,0,0,0,0,1,0,0],
                  [1,1,0,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0],
                  [1,1,0,0,1,0,1,1,1,1,1,0,1,0,0,0,0,0,0,1]])
    '''
    '''
        Solution for Normal
        [[1 0 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1]
        [0 0 0 1 1 0 1 0 0 1 0 1 1 0 0 1 0 1 1 1]
        [0 1 0 1 0 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1]
        [1 0 1 1 1 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0]
        [0 1 0 1 0 0 1 0 0 1 1 0 0 1 0 0 1 0 1 1]
        [1 1 0 1 1 0 0 0 1 1 1 1 0 0 1 0 1 0 1 0]
        [0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0]
        [1 1 1 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 0 1]
        [0 0 0 0 1 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1]
        [1 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0]
        [1 1 1 1 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 1]
        [0 1 0 1 0 1 0 1 0 1 1 0 1 1 1 0 0 0 1 1]
        [1 0 0 1 0 1 1 0 1 1 1 1 0 0 1 0 1 0 0 0]
        [1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 0 0]
        [0 1 1 0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 1 0]
        [1 1 0 1 1 0 1 1 1 0 1 1 0 0 1 1 0 0 0 0]
        [1 0 1 1 1 1 0 0 1 1 0 1 0 0 0 0 0 0 1 1]
        [0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 1 0 1 1]
        [0 1 1 1 0 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0]
        [0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 0 0]]
    '''

    bsol = lo.solve(b)
    print "The solution of"
    print b
    print "is"
    print bsol

if __name__ == '__main__':
    main()