gistfile1.txt

80
PAINT_LINE 24 63 24 87
PAINT_LINE 29 113 32 113
PAINT_SQUARE 32 171 1
PAINT_LINE 14 116 23 116
PAINT_SQUARE 19 101 5
PAINT_SQUARE 27 138 2
PAINT_SQUARE 28 60 3
PAINT_LINE 25 191 28 191
PAINT_SQUARE 27 175 2
PAINT_SQUARE 21 33 10
PAINT_LINE 6 187 6 194
PAINT_LINE 13 64 13 87
PAINT_LINE 12 91 12 95
PAINT_LINE 12 21 12 58
PAINT_LINE 17 52 17 87
PAINT_SQUARE 19 161 5
PAINT_SQUARE 10 161 5
PAINT_SQUARE 24 18 2
PAINT_LINE 25 4 25 63
PAINT_LINE 23 10 26 10
PAINT_LINE 13 21 13 57
PAINT_LINE 13 5 13 8
PAINT_SQUARE 30 171 1
PAINT_LINE 13 93 13 94
PAINT_SQUARE 25 145 4
PAINT_LINE 7 183 7 194
PAINT_LINE 28 105 28 112
PAINT_SQUARE 31 115 1
PAINT_SQUARE 27 178 2
PAINT_SQUARE 16 175 2
PAINT_SQUARE 16 178 2
PAINT_SQUARE 15 123 6
PAINT_LINE 5 13 5 16
PAINT_LINE 10 17 10 58
PAINT_SQUARE 15 130 6
PAINT_SQUARE 19 82 5
PAINT_LINE 13 11 13 12
PAINT_SQUARE 27 125 2
PAINT_SQUARE 7 15 1
PAINT_SQUARE 28 53 3
PAINT_LINE 11 92 11 94
PAINT_LINE 5 13 8 13
PAINT_SQUARE 26 110 1
PAINT_LINE 29 169 36 169
PAINT_SQUARE 18 69 5
PAINT_LINE 8 183 8 186
PAINT_LINE 22 20 27 20
PAINT_SQUARE 10 7 1
PAINT_SQUARE 15 143 6
PAINT_LINE 14 5 14 8
PAINT_LINE 11 5 11 58
PAINT_LINE 13 174 13 190
PAINT_LINE 9 16 9 57
PAINT_LINE 26 4 26 63
PAINT_SQUARE 27 111 1
PAINT_LINE 27 105 27 112
PAINT_SQUARE 10 6 1
PAINT_LINE 5 187 5 194
PAINT_SQUARE 24 13 2
PAINT_LINE 25 109 25 112
PAINT_SQUARE 27 188 2
PAINT_LINE 7 76 7 82
PAINT_SQUARE 35 171 1
PAINT_SQUARE 16 188 2
PAINT_SQUARE 19 110 5
PAINT_LINE 19 51 19 87
PAINT_SQUARE 25 144 4
PAINT_SQUARE 19 71 5
PAINT_SQUARE 27 183 2
PAINT_LINE 33 173 34 173
PAINT_LINE 12 9 12 16
PAINT_LINE 29 113 29 116
PAINT_SQUARE 27 133 2
PAINT_LINE 8 75 8 83
PAINT_SQUARE 28 47 3
PAINT_LINE 20 52 20 87
PAINT_LINE 18 51 18 87
PAINT_SQUARE 27 128 2
PAINT_SQUARE 16 183 2
PAINT_SQUARE 21 31 10

main.py

import time

#wh, *macierz = open("logo.in").read().splitlines()
#wh, *macierz = open("right_angle.in").read().splitlines()
#wh, *macierz = open("learn_and_teach.in").read().splitlines()
wh_macierz = open("right_angle.in").read().splitlines()
wh = wh_macierz[0]
macierz = wh_macierz[1:]

H, W = map(int, wh.split())

def banalny(macierz, transponowana=False):
    if transponowana:
        macierz = [[macierz[y][x] for y in range(H)] for x in range(W)]
    linie = []

    for row, line in enumerate(macierz):
        start = None
        for col, c in enumerate(line):
            if c == "#" and start is None:
                start = col
            elif c == "." and start is not None:
                if not transponowana:
                    linie.append((row, start, row, col-1))
                else:
                    linie.append((start, row, col-1, row))
                start = None
        if start is not None:
            if not transponowana:
                linie.append((row, start, row, W-1))
            else:
                linie.append((start, row, H-1, row))
    def dlugosc(linia):
        _, start, _, end = linia
        return end-start+1
    linie.sort(key=dlugosc)
    return linie

def fits_square(x, y, sz):
    for ny in range(y, y+sz):
        for nx in range(x, x+sz):
            if ny >= H or nx >= W:
                return False
            if macierz[ny][nx] == ".":
                return False
    return True

def kwadraty(macierz):
    kwadraty = []
    for row, line in enumerate(macierz):
        for col, c in enumerate(line):
            if c == ".":
                continue
            for sz in reversed([3, 5, 7, 9, 11, 13, 15, 17, 19, 21]):
                if fits_square(col, row, sz):
                    half = sz // 2
                    kwadraty.append((row+half, col+half, half))
                    break
    return kwadraty

poziome = banalny(macierz)
pionowe = banalny(macierz, transponowana=True)
kwadraty = kwadraty(macierz)

board = [[0 for x in range(W)] for y in range(H)]

def ile_by_pokryla(instr):
    score = 0
    if len(instr) == 4: # linia
        r1, c1, r2, c2 = instr
        for y in range(r1, r2+1):
            for x in range(c1, c2+1):
                score += board[y][x] == 0
    else: # kwadrat
        r, c, sz = instr
        for y in range(r-sz, r+sz+1):
            for x in range(c-sz, c+sz+1):
                score += board[y][x] == 0
    return score

def cos_by_pokryla(instr):
    if len(instr) == 4: # linia
        r1, c1, r2, c2 = instr
        for y in range(r1, r2+1):
            for x in range(c1, c2+1):
                if board[y][x] == 0:
                    return True
    else: # kwadrat
        r, c, sz = instr
        for y in range(r-sz, r+sz+1):
            for x in range(c-sz, c+sz+1):
                if board[y][x] == 0:
                    return True
    return False

def pokryj(instr):
    if len(instr) == 4: # linia
        r1, c1, r2, c2 = instr
        for y in range(r1, r2+1):
            for x in range(c1, c2+1):
                board[y][x] = 1
    else:
        r, c, sz = instr
        for y in range(r-sz, r+sz+1):
            for x in range(c-sz, c+sz+1):
                board[y][x] = 1

polaczone = pionowe + poziome + kwadraty
polaczone.sort(key=ile_by_pokryla)

instrukcje = []

while polaczone:
    linia = polaczone.pop()
    if not cos_by_pokryla(linia):
        break

    instrukcje.append(linia)

    pokryj(linia)

    polaczone.sort(key=ile_by_pokryla)

    for i, line in enumerate(polaczone):
        if cos_by_pokryla(line):
            polaczone = polaczone[i:]
            break

import random
for i in range(50):
    for row in board:
        for x in range(len(row)):
            row[x] = 0

    random.shuffle(instrukcje)

    nowe = []
    for linia in instrukcje:
        if cos_by_pokryla(linia):
            pokryj(linia)
            nowe.append(linia)
    instrukcje = nowe


print(len(instrukcje))
for line in instrukcje:
    if len(line) == 4:
        r1, c1, r2, c2 = line
        print("PAINT_LINE {} {} {} {}".format(r1, c1, r2, c2))
    else:
        r, c, sz = line
        print("PAINT_SQUARE {} {} {}".format(r, c, sz))