5
\$\begingroup\$

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()
\$\endgroup\$
4
\$\begingroup\$

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()
\$\endgroup\$
  • \$\begingroup\$ 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! \$\endgroup\$ – Elliot Gorokhovsky Feb 13 '17 at 0:30
  • 1
    \$\begingroup\$ @RenéG It doesn't matter that much here, but sometimes it can be useful to be able to define some parameters (possibly with default values). And thus testing different values will be made easier in an interactive session. \$\endgroup\$ – 301_Moved_Permanently Feb 13 '17 at 0:41
  • \$\begingroup\$ I don't know if this is the case, but on some of these platforms you can't really read one test case, print the output, read another test case and so on. Sometimes the output is not considered until all the input has been sent, at which point you're only outputting the last case and the test will fail, even if it's actually correct. So if something fails, just store the input and print the output after that. \$\endgroup\$ – ChatterOne Feb 13 '17 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.