hashcode2014 painting

sol.py

import numpy as np
import sys
import random

MAX_ERASE_RATIO = 30  # 10 => 27 500
DILLATE_SIZE = 0

ERASED = -8
EXTRA = -6

def load(input):
    with open(input, 'rb') as f:
        l = f.readline().strip()
        size = tuple(int(i) for i in l.split(' '))

        painting = []
        for l in f:
            line = list(l.strip())
            painting.append([0 if v == '.' else 1 for v in line])
        return size, np.asarray(painting)

def dillate(painting, S):
    new = np.copy(painting)
    for r in xrange(painting.shape[0]):
        for c in xrange(painting.shape[1]):
            if painting[r,c] == 1:
                new[r-S:r+S+1, c-S:c+S+1] = 1
    return new

def square_stats(painting, r, c, S):
    shape = painting.shape
    to_fill = to_overlap = 0
    to_erase = []
    valid = False
    if r-S >= 0 and r+S < shape[0] and c-S >= 0 and c+S < shape[1]:
        valid = True
        sub = painting[r-S:r+S+1, c-S:c+S+1]
        for i in xrange(sub.shape[0]):
            for j in xrange(sub.shape[1]):
                if sub[i,j] == 1:
                    to_fill += 1
                if sub[i,j] < 0:
                    to_overlap += 1
                if sub[i,j] == 0:
                    to_erase.append((r-S+i,c-S+j))
        valid = to_fill != len(to_erase)
    return valid,to_fill,to_overlap,to_erase

def max_size(mat):
    nrows, ncols = mat.shape[0], mat.shape[1]
    counts = [[0]*ncols for _ in xrange(nrows)]
    maxx = 0
    for i in reversed(xrange(nrows)):
        for j in reversed(xrange(ncols)):
            if mat[i][j] == 1:
                v = (1 + min(
                    counts[i][j+1],  # east
                    counts[i+1][j],  # south
                    counts[i+1][j+1] # south-east
                    )) if i < (nrows - 1) and j < (ncols - 1) else 1 # edges
                counts[i][j] = v
                if v % 2 == 1:
                    maxx = max(maxx,v)
    return counts,maxx

def largest_squares(mat):
    counts, maxx = max_size(mat)
    counts = [(v,r,c) for r,rows in enumerate(counts) for c,v in enumerate(rows)]
    print "largest squares %d [%d]" % (len(counts), maxx)
    random.shuffle(counts[:100])
    return sorted(counts, key=lambda x:-x[0])

def solve(painting, output):
    dillated = dillate(np.copy(painting), DILLATE_SIZE)
    print_painting(painting, 'painting_original')
    print_painting(dillated, 'painting_dillated')
    count = 0
    while True:
        max_L_used = None
        squares = list(largest_squares(dillated))
        minus = 0 #try smaller square if biggers ones didn't work
        while max_L_used == None:
            for L, x, y in squares:
                L = L - minus
                if L == 0:
                    break
                if max_L_used and L < max_L_used:
                    break
                S = L/2
                r = x + S
                c = y + S
                valid,to_fill,to_overlap,to_erase = square_stats(painting, r, c, S)
                if valid:
                    if len(to_erase) == 0 or len(to_erase) < to_fill/2:
                        #print erase_ratio
                        if max_L_used == None:
                            max_L_used = L
                        painting[r-S:r+S+1, c-S:c+S+1] = -(S+1)
                        ins = "PAINTSQ %d %d %d\n" % (r,c,S)
                        output.write(ins)
                        count += 1
                        for i,j in to_erase:
                            painting[i,j] = ERASED
                            ins = "ERASE %d %d \n" % (i,j)
                            #print ins
                            output.write(ins)
                            count += 1
            minus -= 1

        print count
        dillated = dillate(np.copy(painting), DILLATE_SIZE)
        print "dillated"
        #print_painting(painting, 'painting_pass_%d' % count)
        if L == 0:
            break
    print_painting(painting, 'painting_base')
    print "count before correction",count

    for r in xrange(painting.shape[0]):
        for c in xrange(painting.shape[1]):
            if painting[r,c] == 1:
                output.write('PAINTSQ %d %d 0\n' % (r, c))
                painting[r, c] = EXTRA
                count += 1
    print_painting(painting, 'painting_corrected')

    print "final count", count
        

def print_painting(painting, out_file):
    out = open("out/"+out_file,'w')
    for r in xrange(painting.shape[0]):
        for c in xrange(painting.shape[1]):
            l = "."
            val = painting[r,c]
            if val > 0:
                l = "X"
            elif val == ERASED:
                l = "E"
            elif val == EXTRA:
                l = "O"
            elif val < 0:
                l = chr(ord("0")-val)
            out.write(l)
        out.write('\n')
    out.close()


def main():
    size, painting = load(sys.argv[1])
    assert painting.shape == size

    print size
    output = open('out/output.txt', 'wb')
    solve(painting, output)
    output.close()


if __name__ == '__main__':
    main()