Painting

painting.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()

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 not start:
                start = col
            elif c == "." and start:
                if not transponowana:
                    linie.append((row, start, row, col-1))
                else:
                    linie.append((start, row, col-1, row))
                start = None
        if start:
            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)

for line in poziome:
    r1, c1, r2, c2 = line
    #print("(POZ) PAINT_LINE {} {} {} {}".format(r1, c1, r2, c2))

for line in pionowe:
    r1, c1, r2, c2 = line
    #print("(PION) PAINT_LINE {} {} {} {}".format(r1, c1, r2, c2))

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
        return score
    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 y >= H or x >= W:
                    print(x, W, y, H, sz)
                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 = []

print(len(poziome))
print(len(pionowe))
print(len(kwadraty))

while polaczone:
    linia = polaczone.pop()
    if ile_by_pokryla(linia) == 0:
        break

    instrukcje.append(linia)
    print(len(instrukcje))

    pokryj(linia)

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

"""
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))
"""
print(len(instrukcje))
"""
for line in board:
    print("".join(".#"[c] for c in line))
"""
print("koniec")