03_cheese_rec.py

crude cheese solution

'''
# for debugging
def print_cells():
    for y in range(n):
        for x in range(m):
            if cells[y][x] == -1:
                print(" . ", end="")
            elif cells[y][x] == 1:
                print(" 1 ", end="")
            else:
                print(" 0 ", end="")
        print()
    print()
'''

# get input filename
import sys
args = sys.argv
if len(args) == 1:
    input_file = "03_input.txt"
else:
    input_file = args[1]

# open input file and get lines (no error-handling)
with open(input_file, "r") as f:
    lines = f.read().splitlines()

# n, m input validity check
a = lines[0].split(' ')
if not a[0].isdigit() or len(a) == 1 or not a[1].isdigit():
    print('both n and m should be numbers')
    quit()

n, m = int(a[0]), int(a[1])
if n < 5 or n > 100 or m < 5 or m > 100:
    print('both n and m should be >= 5 and <= 100')
    quit()

# get cells from input lines
cells = [[0 for m2 in range(m)] for n2 in range(n)]
for y in range(n):
    a = lines[y + 1].split(' ')
    if len(a) < m:
        print('one line should be consist of m elements')
        quit()

    cells[y] = a

# elements validity check
for y in range(n):
    for x in range(m):
        a = cells[y][x]
        if not a.isdigit():
            print('elements should be a number')
            quit()

        a = int(a)
        cells[y][x] = a
        if (x == 0 or y == 0 or x == m-1 or y == n-1) and a != 0:
            print('elements at the four outer edges should be 0')
            quit()
        elif a > 1 or a < 0:
            print('elements should be 0 or 1')
            quit()


# apply flood-fill(change 0 to -1) on the surrounding four edges clockwise
# after this, closed cells remains 0 and surrounding cells are set to -1
def apply_flood_fill():
    def flood_fill(x, y):
        if cells[y][x] == 0:
            cells[y][x] = -1
            if x > 0:                flood_fill(x-1, y)
            if x < len(cells[y])-1:  flood_fill(x+1, y)
            if y > 0:                flood_fill(x, y-1)
            if y < len(cells)-1:     flood_fill(x, y+1)

    # fill the four outer edges first (to reduce recursion depth)
    for y in range(n):
        if y == 0 or y == n-1:
            for x in range(m):
                cells[y][x] = -1
        else:
            cells[y][0] = -1
            cells[y][m-1] = -1

    # [1][1] -> [1][m-2]
    for x in range(1, m-1):  flood_fill(x, 1)

    # [1][m-2] -> [n-2][m-2]
    for y in range(1, n-1):  flood_fill(m-2, y)

    # [n-2][m-2] -> [n-2][1]
    for x in range(m-2, 0, -1):  flood_fill(x, n-2)

    # [n-2][1] -> [1][1]
    for y in range(n-2, 0, -1):  flood_fill(1, y)

    return


# simulation starts
turn = 0
apply_flood_fill()
sum_to_end = -n * m

while turn < 100:  # maximum turn to wait
    turn += 1

    # update and remove contacted cells
    contacted_cells_xy = []
    for y in range(1, n - 1):
        for x in range(1, m - 1):
            if cells[y][x] == 1:
                count = 0
                if cells[y - 1][x] == -1:  count += 1
                if cells[y + 1][x] == -1:  count += 1
                if cells[y][x - 1] == -1:  count += 1
                if cells[y][x + 1] == -1:  count += 1

                if count >= 2:  contacted_cells_xy.append((y, x))

    for i in range(len(contacted_cells_xy)):
        cells[contacted_cells_xy[i][0]][contacted_cells_xy[i][1]] = -1

    # reset surrounding cells and then apply flood-fill
    for y in range(n):
        for x in range(m):
            if cells[y][x] == -1:  cells[y][x] = 0

    apply_flood_fill()

    # get sum of cells to check if no cell is left
    cells_sum = sum([item for sublist in cells for item in sublist])
    if cells_sum == sum_to_end:
        print('hour: {0}'.format(turn))
        break