My solution to a competitive programming problem (UVA 10189, Minesweeper)

Question

This is one of my first competitive programming solutions. The problem it solves is described here; basically, you get a series of grids ("fields"), where . means "no mine" and * means "mine"; you have to compute how many mines are adjacent (8 adjacent squares) to each non-mine square. My solution is correct, but seems pretty complicated for such a simple problem. What could I have done better, taking into account that my only concern is to write the program as quickly and correctly as possible (readability/proper practices don't count here)? You may also separately critique readability/proper practices.

import sys
from itertools import *

data = sys.stdin.read().splitlines()

fields = []
import re
for i in range(0,len(data)):
    match = re.match('(\d+) (\d+)', data[i])
    if match:
        r = int(match.group(1))
        if r != 0:
            fields.append(data[i+1 : i+1+r])

for field in fields:
    for (x,y) in product(range(len(field)), range(len(field[0]))):

        if field[x][y] == '*':
            continue

        count = 0
        for (x_offset, y_offset) in product(range(-1,2), repeat=2):

            if x_offset == y_offset == 0 or x+x_offset < 0 or y_offset+y < 0:
                continue

            try:
                if field[x+x_offset][y+y_offset] == '*':
                    count += 1
            except IndexError:
                pass

        row = list(field[x])
        row[y] = str(count)
        field[x] = ''.join(row)

for i in range(0,len(fields)):
    print("Field #%i:" % (i+1))
    for row in fields[i]:
        print(row)

    if i < len(fields)-1:
        print()

Answer 1

Even in the case of timed contests, you should not sacrifice good practices for brievity. What you gain typing less is lost when debugging or re-reading code.

Using functions to separate logical units of code is the least you should do here as it help isolate, test and assert correctness of each step of the algorithm more easily.

You should take the habbit of starting to write/configure a template in your IDE:

# imports


def main():
    pass


if __name__ == '__main__':
    main()

Here you start by reading the entire input and then extract out tests cases afterwards. I see two issues with that:

• you may run into memory issues if the number of tests cases and/or their length is huge;
• you do not take advantage of the highly structured input spec.

I would define the following function:

def read_test_case(lines_amount):
    return [input() for _ in range(lines_amount)]

And call it like:

def main():
    while True:
        lines, columns = map(int, input().split())
        if not lines:
            return
        field = read_test_case(lines)
        # ...

You also perform a lot of for ... in range(len(...)) which is rather inefficient. Consider using direct iteration like you do with for field in fields or enumerate if you also need indices:

MINE = '*'


def build_hints(field, lines_max, columns_max):
    def count_mines(x, y):
        count = 0
        for x_offset, y_offset in itertools.product(range(-1,2), repeat=2):
            x_ = x + x_offset
            y_ = y + y_offset
            if x_offset == y_offset == 0 or not (0 <= x_ < columns_max and 0 <= y_ < lines_max):
                continue
            count += field[y_][x_] == MINE
        return count

    return [
        [
            MINE if square == MINE else str(count_mines(x, y))
            for x, square in enumerate(row)
        ]
        for y, row in enumerate(field)
    ]

All what is left is to put all pieces together and print elements. Which lead to:

import itertools


MINE = '*'


def build_hints(field, lines_max, columns_max):
    def count_mines(x, y):
        count = 0
        for x_offset, y_offset in itertools.product(range(-1,2), repeat=2):
            x_ = x + x_offset
            y_ = y + y_offset
            if x_offset == y_offset == 0 or not (0 <= x_ < columns_max and 0 <= y_ < lines_max):
                continue
            count += field[y_][x_] == MINE
        return count

    return [
        [
            MINE if square == MINE else str(count_mines(x, y))
            for x, square in enumerate(row)
        ]
        for y, row in enumerate(field)
    ]


def print_hints(hints):
    for row in hints:
        print(''.join(row))
    print()


def read_test_case(lines_amount):
    return [input() for _ in range(lines_amount)]


def main():
    for test_case in itertools.count(1):
        lines, columns = map(int, input().split())
        if not lines:
            return
        field = read_test_case(lines)
        hints = build_hints(field, lines, columns)
        print('Field #{}:'.format(test_case))
        print_hints(hints)


if __name__ == '__main__':
    main()