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

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 *

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


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
# ...


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

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

• Thanks for your detailed response! I'm not sure I see how using a main() could be useful in competitions; it's extremely unlikely that I would import code between problems. Each problem is solved by a single-file program that's usually under 100-200 lines. Anyway, I really like your two-dimensional list-comprehension syntax there at the end! Feb 13, 2017 at 0:30