CH206INT - Crop

crop.py

import math


crop = []
width = 0
height = 0
diameter = 0
total_cache = []
offset_cache = []


def calculate(x, y):
    if x == 0:
        if y == 0:
            return covered_crop()
        return calculate_from_below(x, y)
    return calculate_from_left(x, y)


def calculate_from_below(x, y):
    total = total_cache[y - 1][x]
    for i in range(int(diameter)):
        total += crop_val(y + offset_cache[i], x + i - half_d())
        total -= crop_val(y - offset_cache[i] - 1, x + i - half_d())

    return total


def calculate_from_left(x, y):
    total = total_cache[y][x - 1]
    for i in range(int(diameter)):
        total += crop_val(y + i - half_d(), x + offset_cache[i])
        total -= crop_val(y + i - half_d(), x - offset_cache[i] - 1)

    return total


def cache_offsets():
    for i in range(-half_d(), half_d() + 1):
        offset_cache.append(int(math.floor(math.sqrt((diameter / 2) ** 2 - i ** 2))))


def crop_val(y, x):
    return 0 if x < 0 or y < 0 or y >= height or x >= width else crop[y][x]


def half_d():
    return int(math.floor((diameter - 1) / 2))


def covered_crop():
    total = 0
    for y in range(int(diameter)):
        current_dist = offset_cache[y]
        j = y - half_d()
        for i in range(-current_dist, current_dist + 1):
            total += crop_val(j, i)
    return total


if __name__ == "__main__":
    f = open('crop.txt', 'r')
    s = f.readline()
    heightRaw, widthRaw, diameterRaw = s.split(' ')
    width = int(widthRaw)
    height = int(heightRaw)
    diameter = float(diameterRaw)

    for i in range(height):
        cropRow = []
        total_cache.append([])
        line = f.readline()
        for j in range(width):
            cropRow.append(1 if line[j] == 'x' else 0)
            total_cache[i].append(0)
        crop.append(cropRow)

    cache_offsets()

    max_total = 0
    for y in range(height):
        for x in range(width):
            current_total = calculate(x, y)
            total_cache[y][x] = current_total

            if current_total > max_total:
                print(y, x)
                print(current_total)

            max_total = max(current_total, max_total)

    # print(max_total)
    # for row in total_cache:
    #     print row