In [21]:

    

import numpy as np
import pandas as pd
import time as time
import operator
import matplotlib.pyplot as plt
%matplotlib inline
from IPython.display import display, Image, clear_output
from scipy.spatial.distance import pdist, squareform
from collections import defaultdict


    

In [22]:

    

def discrete_kernel(center, minsize):
    dist = np.empty((2*minsize+1,2*minsize+1))
    decay = np.logspace(0,1,minsize+1 )
    
    for xstep in range(-minsize,minsize+1):
        for ystep in range(-minsize,minsize+1):
            dist[1+xstep][1+ystep] = 1 * paint[center[0]+xstep][center[1]+ystep]
            
    return (dist.sum()+0.0)/np.array(dist.shape).prod()


    

In [23]:

    

def paint_square(center, minsize):
    for xstep in range(-minsize,minsize+1):
        for ystep in range(-minsize,minsize+1):
            paint[center[0]+xstep][center[1]+ystep] = 0.0


    

In [24]:

    

def check_line(line):
    row = line[1]
    col = line[2]
    vline = 0
    hline = 0 
    if paint[row][col]:
        for bit in paint[row, col:]:
            if bit:
                hline += 1
            else:
                break
        for bit in paint[row:, col]:
            if bit:
                vline += 1
            else:
                break
    if hline < lthresh:
        hline = 0;
    if vline < lthresh:
        vline = 0;
    newline = (line[0], line[1], line[2], hline, vline)
    return newline


    

In [25]:

    

def paint_line(line):
    cmds = 0;
    if line[3] > line[4]:
        paint[line[1],range(line[2], line[3] + line[2])] = 0.0
        cmds += 1
    elif line[3] == line[4]:
        paint[line[1] , range(line[2], line[3] + line[2])] = 0.0
        paint[range(line[1], line[1] + line[4]) , line[2]] = 0.0
        if line[3] == 1:
            cmds += 1
        else:
            cmds += 2
    else:
        paint[range(line[1], line[1] + line[4]) , line[2]] = 0.0
        cmds += 1
    return cmds


    

In [26]:

    

filepath = '/Users/alfredogarbuno/github-repos/hashcode-2015/data/learn_and_teach.in'
f = open(filepath, "r+")
dimstr = f.readline().split()
paint = np.empty([int(dimstr[0]), int(dimstr[1])])

for i in range(int(dimstr[0])):
    paint[i] = np.array(list(f.readline().split()[0].replace(".", "0").replace("#", "1")), np.int32)
    
f.close()


    

In [27]:

    

plt.figure(figsize=(10,10))
plt.imshow(paint)
fig = plt.gca()
fig.axes.get_xaxis().set_visible(False)
fig.axes.get_yaxis().set_visible(False)


    

In [28]:

    

dim = np.array(dimstr, np.int32)
density = paint.sum() / dim.prod()
minsize = int(dim.min() * density)
print minsize
# Parameters
minsize = 8
threshold = 0.9
linecmds = []
print minsize
indices = np.arange(1,dim.prod()+1).reshape(dim)


    

    




32
8

In [29]:

    

# This paints with squares

paints = defaultdict(list)
zeros = 0;
plt.figure(figsize=(10,10))

while minsize > 0:
    # Create centers
    row, col = np.indices((dim[0]-2*minsize, dim[1]-2*minsize))
    centers = indices[row+minsize, col+minsize]
    # Create candidate list
    cands = []
    cands = [ (ycoord, discrete_kernel([row+minsize, ycoord%dim[1]-1], minsize)) for row in range(centers.shape[0]) 
            for ycoord in centers[row]]
    # Filter candidates
    cands = [(key, value) for (key,value) in cands if value >= threshold]
    cands = sorted(cands, key=lambda element: (-element[1], element[0]))
    # Begin drawing with squares
    for cand in cands:
        center = ( cand[0] // dim[1], cand[0] % dim[1] - 1)
        if cand[0] == cands[0][0]:
            zeros += (1-cand[1]) * (2*minsize + 1)**2
            paint_square(center, minsize)
            paints[minsize].append(center)
#            plt.imshow(paint)
#            clear_output(wait=True)
#            display(plt.gcf())
#            time.sleep(0.0001)
        else:
            if discrete_kernel(center, minsize) >= threshold:
                zeros += (1-cand[1]) * (2*minsize + 1)**2
                paint_square(center, minsize)
                paints[minsize].append(center)
#                plt.imshow(paint)
#                clear_output(wait=True)
#                display(plt.gcf())
#                time.sleep(0.0001)
                
    minsize += -1

clear_output(wait=True)


    

    






<matplotlib.figure.Figure at 0x119336d50>

In [30]:

    

# Total square paints
print np.array([v for (k, v) in paints.items()]).sum()


    

    




[(2, 643), (3, 788), (4, 410), (4, 518), (4, 667), (4, 791), (5, 453), (5, 548), (5, 578), (5, 610), (6, 697), (6, 740), (8, 609), (9, 579), (10, 517), (11, 420), (11, 454), (13, 271), (13, 766), (17, 52), (17, 234), (17, 642), (17, 650), (17, 655), (18, 139), (18, 289), (18, 316), (18, 331), (19, 109), (20, 635), (22, 630), (24, 228), (24, 789), (25, 625), (28, 619), (28, 706), (29, 703), (31, 613), (31, 656), (32, 14), (32, 17), (32, 24), (32, 153), (33, 245), (33, 263), (34, 608), (34, 683), (35, 153), (35, 542), (35, 645), (35, 765), (36, 245), (36, 263), (36, 539), (36, 637), (36, 677), (37, 607), (37, 630), (38, 65), (38, 153), (38, 669), (38, 765), (39, 624), (40, 8), (40, 608), (40, 613), (41, 66), (41, 153), (42, 71), (42, 81), (43, 7), (43, 47), (43, 781), (44, 38), (44, 153), (50, 45), (51, 342), (52, 31), (52, 34), (52, 41), (52, 479), (54, 342), (54, 675), (55, 152), (55, 436), (55, 479), (56, 283), (56, 318), (56, 393), (56, 439), (57, 367), (57, 677), (58, 390), (58, 464), (58, 559), (58, 779), (59, 18), (59, 283), (60, 680), (60, 767), (61, 759), (61, 789), (62, 743), (62, 783), (63, 33), (63, 588), (63, 682), (63, 771), (64, 580), (64, 762), (65, 743), (65, 752), (65, 783), (66, 17), (66, 33), (66, 571), (66, 684), (66, 746), (66, 772), (66, 778), (67, 580), (67, 763), (68, 152), (68, 710), (68, 754), (68, 766), (69, 33), (69, 571), (69, 725), (69, 747), (69, 758), (70, 17), (70, 687), (70, 750), (70, 780), (71, 712), (71, 743), (72, 690), (72, 726), (73, 291), (73, 782), (74, 8), (74, 715), (74, 775), (75, 367), (75, 656), (75, 692), (75, 718), (75, 753), (76, 28), (76, 54), (76, 464), (76, 560), (76, 607), (76, 745), (77, 404), (77, 733), (78, 85), (78, 336), (78, 694), (78, 748), (80, 404), (80, 735), (81, 336), (81, 533), (81, 536), (81, 539), (81, 542), (81, 696), (81, 726), (82, 768), (83, 750), (84, 14), (84, 17), (84, 57), (84, 60), (84, 82), (84, 89), (84, 758), (84, 761), (85, 48), (85, 51), (85, 54), (85, 65), (85, 92), (85, 699), (86, 42), (86, 45), (86, 97), (87, 102), (88, 106), (88, 701), (88, 779), (89, 109), (89, 461), (89, 748), (89, 782), (91, 115), (91, 702), (92, 491), (92, 749), (93, 118), (93, 739), (93, 742), (94, 642), (95, 71), (95, 229), (95, 491), (95, 777), (96, 221), (96, 410), (96, 744), (97, 22), (97, 25), (97, 285), (97, 352), (97, 642), (98, 12), (98, 71), (98, 127), (98, 231), (98, 766), (98, 778), (99, 223), (99, 746), (99, 769), (100, 8), (100, 130), (100, 294), (100, 340), (100, 363), (100, 390), (100, 393), (101, 72), (101, 109), (101, 233), (101, 374), (101, 378), (102, 215), (102, 225), (102, 239), (102, 306), (102, 746), (102, 749), (102, 757), (103, 5), (103, 49), (104, 71), (104, 235), (104, 242), (105, 217), (105, 227), (106, 3), (106, 48), (106, 209), (106, 353), (106, 438), (107, 71), (107, 236), (107, 244), (107, 797), (108, 58), (108, 94), (108, 228), (108, 343), (109, 1), (109, 210), (109, 219), (110, 97), (110, 121), (110, 138), (110, 237), (110, 246), (111, 72), (111, 228), (111, 263), (111, 361), (111, 407), (111, 413), (111, 416), (111, 419), (111, 422), (112, 219), (112, 259), (112, 314), (112, 672), (113, 99), (113, 140), (113, 237), (114, 229), (114, 320), (114, 332), (114, 348), (114, 391), (114, 394), (114, 397), (114, 425), (115, 1), (115, 57), (115, 315), (115, 371), (115, 382), (115, 657), (116, 101), (116, 141), (116, 237), (116, 379), (116, 667), (116, 685), (117, 67), (117, 229), (117, 414), (117, 672), (117, 688), (118, 1), (118, 56), (118, 675), (118, 691), (119, 71), (119, 101), (119, 679), (120, 231), (120, 251), (120, 662), (120, 694), (121, 46), (121, 56), (121, 193), (121, 625), (121, 682), (122, 170), (122, 507), (122, 651), (123, 222), (123, 252), (123, 488), (123, 639), (123, 696), (124, 46), (124, 56), (124, 193), (124, 492), (124, 616), (124, 699), (125, 212), (125, 358), (125, 361), (125, 364), (125, 407), (125, 410), (126, 64), (126, 252), (126, 499), (127, 57), (127, 123), (127, 194), (127, 493), (127, 701), (127, 782), (128, 72), (128, 418), (128, 604), (128, 646), (129, 91), (129, 369), (129, 488), (129, 499), (129, 791), (130, 121), (130, 139), (130, 375), (130, 378), (130, 493), (130, 676), (131, 647), (131, 670), (132, 393), (132, 396), (132, 507), (132, 689), (133, 138), (133, 361), (133, 600), (134, 70), (134, 253), (134, 697), (135, 135), (135, 370), (135, 373), (135, 415), (135, 418), (135, 451), (135, 454), (135, 610), (136, 61), (137, 71), (137, 253), (137, 407), (137, 696), (138, 364), (138, 367), (138, 528), (139, 11), (139, 63), (140, 110), (140, 230), (140, 699), (141, 199), (141, 375), (141, 601), (141, 764), (142, 16), (142, 103), (142, 209), (142, 251), (143, 228), (143, 630), (143, 709), (145, 207), (145, 216), (145, 506), (145, 675), (145, 712), (146, 592), (146, 630), (147, 77), (147, 128), (147, 153), (147, 159), (147, 180), (147, 229), (147, 540), (147, 716), (147, 759), (148, 248), (148, 506), (148, 673), (149, 71), (149, 108), (149, 543), (149, 607), (150, 377), (150, 393), (150, 396), (151, 90), (151, 93), (151, 96), (151, 99), (151, 182), (151, 506), (151, 610), (151, 646), (151, 658), (152, 62), (152, 71), (153, 84), (153, 87), (153, 155), (153, 227), (154, 55), (154, 74), (154, 77), (154, 80), (154, 104), (154, 182), (154, 577), (154, 582), (155, 507), (155, 624), (155, 656), (155, 755), (156, 128), (156, 155), (156, 211), (156, 214), (156, 229), (2, 696), (16, 778), (21, 778), (26, 778), (35, 535), (38, 673), (47, 91), (47, 96), (47, 208), (52, 591), (53, 331), (55, 432), (56, 363), (56, 468), (56, 564), (60, 608), (64, 584), (66, 576), (68, 796), (69, 209), (73, 796), (74, 287), (75, 391), (75, 439), (75, 771), (76, 363), (77, 469), (78, 263), (78, 796), (79, 495), (83, 796), (88, 797), (91, 759), (93, 797), (95, 706), (98, 796), (103, 796), (107, 349), (117, 46), (120, 493), (122, 500), (127, 168), (128, 690), (129, 45), (129, 213), (130, 254), (131, 705), (134, 213), (138, 16), (141, 215), (142, 127), (143, 223), (148, 113), (150, 56), (150, 409), (151, 622), (2, 742), (31, 778), (38, 283), (41, 730), (47, 7), (63, 592), (74, 14), (74, 58), (76, 765), (79, 722), (85, 743), (87, 516), (94, 753), (98, 51), (98, 757), (118, 632), (120, 141), (121, 213), (124, 71), (133, 411), (137, 600), (139, 132), (147, 655), (150, 104), (150, 381), (152, 223), (11, 778), (23, 663), (36, 778), (40, 649), (43, 34), (46, 65), (66, 24), (69, 739), (74, 32), (76, 318), (77, 564), (81, 78), (84, 731), (87, 754), (89, 737), (98, 213), (98, 406), (99, 332), (101, 207), (101, 318), (104, 443), (106, 135), (112, 45), (115, 212), (115, 407), (124, 2), (126, 141), (132, 59), (133, 488), (135, 676), (139, 114), (140, 673), (141, 416), (141, 485), (141, 796), (143, 99), (145, 71), (145, 604), (146, 120), (151, 720), (151, 756), (155, 789), (34, 251), (35, 240), (35, 258), (36, 268), (38, 277), (53, 348), (53, 412), (53, 419), (53, 485), (53, 492), (53, 578), (53, 585), (55, 357), (55, 570), (56, 398), (56, 474), (58, 257), (58, 264), (58, 271), (58, 278), (58, 534), (58, 541), (76, 433), (77, 357), (78, 236), (78, 270), (78, 475), (78, 570), (79, 243), (79, 250), (79, 257), (80, 342), (80, 410), (80, 482), (80, 489), (94, 486), (138, 516), (138, 523), (143, 22), (54, 426), (77, 324), (78, 501), (79, 759), (137, 47), (138, 706), (148, 793), (149, 37), (151, 214), (53, 337), (55, 325), (79, 350), (79, 592), (80, 417), (146, 29), (54, 405), (79, 331), (97, 17), (154, 247), (39, 224), (78, 426), (79, 577), (80, 584), (95, 785), (115, 251), (150, 567), (76, 228), (91, 469), (125, 187), (37, 232), (75, 280), (94, 478), (62, 151), (66, 62), (77, 601), (54, 500), (77, 398), (93, 498), (126, 177), (58, 600), (132, 8), (90, 508), (72, 218), (44, 216), (81, 781), (147, 47), (66, 390), (90, 769), (67, 465), (66, 366), (66, 316), (67, 562), (65, 440), (76, 513), (59, 513), (58, 209), (71, 538), (63, 293), (46, 537)]

In [31]:

    

[ (key,len(paints[key])) for key in paints.keys() ]


    

    
Out[31]:





[(1, 476), (2, 124), (3, 65), (4, 12), (5, 7), (6, 3), (7, 5), (8, 6)]

In [32]:

    

commands = []
for key in paints.keys():
    for center in paints[key]:
        commands.append((key, center[0], center[1]))


    

In [33]:

    

def write_squares(n, commands, path):
    with open(path, 'w') as fh:
        fh.write('{}\n'.format(n))
        for command in commands:
            if command[0] > 0:
                fh.write('PAINT_SQUARE '+str(command[2])+ ' ' + str(command[1])+ ' ' + str(command[0]) + '\n')
            else:
                # fh.write('ERASE_CELL {} {}\n'.format(*command[1:3]))
                print 'hello'


    

In [34]:

    

def write_lines(commands, path):
    with open(path, 'a') as fh:
        for command in commands:
            fh.write('PAINT_LINE '+str(command[2])+ ' ' + str(command[1])+ ' ' + str(command[0]) + '\n')


    

In [35]:

    

plt.figure(figsize=(10,10))
plt.imshow(paint)
fig = plt.gca()
fig.axes.get_xaxis().set_visible(False)
fig.axes.get_yaxis().set_visible(False)


    

In [36]:

    

lines = []
for row in range(indices.shape[0]):
    for col in range(indices.shape[1]):
        if paint[row][col]:
            vline = 0
            hline = 0 
            for bit in paint[row, col:]:
                if bit:
                    hline += 1
                else:
                    break
            for bit in paint[row:, col]:
                if bit:
                    vline += 1
                else:
                    break
            lines.append( (indices[row,col], row, col, hline, vline) )
                    
lines = sorted(lines, key=lambda element: (-max(element[3], element[4]), element[0]))


    

In [37]:

    

plt.figure(figsize=(10,10))
lthresh = 0;
for line in lines:
    nwline = check_line(line)
    if max(nwline[3],nwline[4]) > 0:
        cmds = paint_line(line)
        linecmds.append(cmds)
#        plt.imshow(paint)
#        clear_output(wait=True)
#        display(plt.gcf())
#        time.sleep(0.001)


    

    






<matplotlib.figure.Figure at 0x11919c710>

In [38]:

    

# Total pixels
print "Free pixels: ", paint.sum()
# Total erases
print "Erase commands: ", zeros
# Total squares
print "Square commands: ", sum([ v for (k,v) in [ (key,len(paints[key])) for key in paints.keys() ]])
# Total of line commands
print "Line commands: ", len(linecmds)


    

    




Free pixels:  0.0
Erase commands:  506.0
Square commands:  698
Line commands:  2781

In [39]:

    

len(linecmds)


    

    
Out[39]:





2781

In [40]:

    

outpath = '/Users/alfredogarbuno/github-repos/hashcode-2015/data/output.in'
write_squares(10, commands, outpath)
write_lines(commands,outpath)


    

In [ ]:

    




    

In [ ]: