covering holes

covering.py

# http://www.reddit.com/r/dailyprogrammer/comments/1g7gyi/061213_challenge_128_intermediate_covering/
# attemp to use scipy.optimize to do this
import numpy as np
from StringIO import StringIO
from scipy.optimize import minimize

def solve(s):
    f = StringIO(s)
    data = np.loadtxt(f, dtype=np.uint8, skiprows=1)
    n = data.shape[0]

    # [ row1 ... rown, col1 ... coln]
    guess = np.ones(2*n, dtype=np.uint8)
    objective = np.sum

    constraints = []
    # all holes must be filled
    it = np.nditer(data, flags=['multi_index'])
    while not it.finished:
        value = it[0]
        i, j = it.multi_index
        if value <= 0:
            constraints.append({
                'type' : 'ineq',
                # i=i, j=j is the only way to capture the value rather than the variable
                'fun'  : lambda x, i=i, j=j : x[i] + x[n+j] - 1 # shift the limit
            })
        it.iternext()

    bounds = [(0, 1.01)] * (2 * n)

    res = minimize(objective, guess, bounds=bounds, constraints=constraints, method='SLSQP')

    print data
    x = map(round, res.x) # use round for simplicity but it's not optimal nor right all the time
    rows = x[0:len(x)/2]
    cols = x[len(x)/2:]
    for ix, val in enumerate(rows):
        if val != 0:
            print 'Row %d repaired.' % ix
    for ix, val in enumerate(cols):
        if val != 0:
            print 'Column %d repaired.' % ix
    print

if __name__ == '__main__':
    s1 = '''x
0 4 0 2 2    
1 4 0 5 3    
2 0 0 0 1    
2 4 0 5 2    
2 0 0 4 0
'''

    s2 = '''x
1 1 1 0 1 1 1
2 2 2 0 2 2 2
3 3 3 0 3 3 3
4 0 4 0 4 0 4 
5 5 5 0 5 5 5
6 6 6 0 6 6 6 
7 0 7 0 7 0 0
'''

    s3 = '''x
1 1 1
1 0 0
0 0 1
'''

    s4 = '''x
0 1 0 1 1
0 0 1 1 1
0 1 1 1 0
1 1 1 0 1
1 1 1 0 1
'''
    solve(s1)
    solve(s2)
    solve(s3)
    solve(s4)