Solution to the Google Hash Code Pizza practice problem, trying all shapes greedily along the antidiagonals. Score: 944730 = 12+38+48846+895834

pizza.py

import sys
import numpy as np


num_rows, num_cols, min_ingr, max_size = [int(x) for x in input().split(' ')]
pizza = np.array([[int(x == 'T') for x in input()] for i in range(num_rows)])

output = []
dead = np.zeros_like(pizza).astype(int)


# calc possible shapes
shapes = []
for h in range(max_size, 0, -1):
    for w in range(max_size, 0, -1):
        if 2 * min_ingr <= h*w <= max_size:
            shapes.append((h,w))

# try 'best' shapes first:  1. most compact (e.g. (3,4) is better than (1,12)) and 2. biggest
shapes.sort(key=lambda s: (min(s[0],s[1]), max(s[0],s[1])), reverse=True)
print('Shapes:', shapes, file=sys.stderr)  # print to stderr so we dont leak debug printing into output


# DIAGONALLY try to fit pizza slices; with top-left corners on successive anti-diagonals
for d in range(num_rows+num_cols+1):
    for i in range(d+1):
        j = d-i
        if i >= num_rows or j >= num_cols:
            continue

        for h,w in shapes:
            if i+h > num_rows or j+w > num_cols:
                continue
            if np.any(dead[i:i+h,j:j+w]):  # already used in another slice
                continue
            if not min_ingr <= np.sum(pizza[i:i+h,j:j+w]) <= h*w - min_ingr:  # not enough T or M
                continue
            dead[i:i+h,j:j+w] = 1
            output.append((i, j, i+h-1, j+w-1))
            break



print('Score:', np.sum(dead), file=sys.stderr)

print(len(output))
[print(' '.join(str(x) for x in e)) for e in output]