Buscaminas Programming Challenges de la UTN-FRC en Python

Resolví 2 problemas basados en el buscaminas en Python para la competencia de programación de la UTN-FRC, aca esta el código y mas abajo esta un link al repo de mercurial para quien desee bajar el código mas la entrada.

Problema Fácil (Enunciado)

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# "THE BEER-WARE LICENSE" (Revision 42):
# <jbc.develop@gmail.com> wrote this file. As long as you retain this notice you
# can do whatever you want with this stuff. If we meet some day, and you think
# this stuff is worth it, you can buy me a beer in return Juan BC

#===============================================================================
# DOCS
#===============================================================================

"""Solucion al problema del buscaminas para la competencia de programación de la
UTN-FRC.

Objetivo: Ser legible y servir de instroduccion a python

Problema originalmente propuesto:

http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110102&format=html

Nota se simplifico para trabajar solo con matrices cuadradas

"""

#===============================================================================
# META
#===============================================================================

__author__ = "Juan BC"
__license__ = "BeerWare"
__date__ = "2011/10/26"
__version__ = "0.1"
__email__ = "jbc.develop@gmail.com"
__homepage__ = "http://jbcabral.wordpress.com/"
__twitter__ = "@juanbcabral"

#===============================================================================
# FUNCTIONS
#===============================================================================

def read_n_lines(n):
    """Esta funcion lee las siguientes n linea de la entrada y las retorna
    como una lista de listas.

    """
    lines = []
    for _ in range(n):
        line = list(raw_input())
        lines.append(line)
    return lines

def increment(board, row, col):
    """Funcion de soporte para resolve que incrementa en uno todas los vecinoa
    a una mina

    """
    for row_d in (-1, 0, 1):
        for col_d in (-1, 0, 1):
            rowp = row + row_d
            colp = col + col_d
            if rowp < 0 or colp < 0 
               or rowp >= len(board) or colp >= len(board[rowp]) 
               or board[rowp][colp] == "*":
                continue
            if board[rowp][colp] == ".":
               board[rowp][colp] = 0
            board[rowp][colp] += 1

def resolve(board):
    """Itera sobre cada celda y si encuentra una mina (*) incrementa todos
    sus cacilleros vacios en 1

    """
    for idx_row, row in enumerate(board):
        for idx_col, cell in enumerate(row):
            if cell == "*":
                increment(board, idx_row, idx_col)

def main():
    field = 0;
    while True:

        # leemos el tamaño de nuestro board
        n = int(raw_input())

        # si el tamaño de nuestro board es 0 salimos
        if n == 0:
            break

        # incrementamos el numero de field
        field += 1

        # leemos el tablero
        board = read_n_lines(n)

        # resolvemos el tablero
        resolve(board)

        # armamos la salida
        out = "n".join(["".join([str(c) for c in row]) for row in board])

        # imprimimos la salida con su decoradores
        # y si queda algun "." lo reemplazamos por un cero
        print "Field #{0}:".format(field)
        print out.replace(".", "0")
        print ""

#===============================================================================
# MAIN
#===============================================================================

if __name__ == "__main__":
    main()

Problema Menos Fácil (Enunciado)

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# "THE BEER-WARE LICENSE" (Revision 42):
# <jbc.develop@gmail.com> wrote this file. As long as you retain this notice you
# can do whatever you want with this stuff. If we meet some day, and you think
# this stuff is worth it, you can buy me a beer in return Juan BC

#===============================================================================
# DOCS
#===============================================================================

"""Solucion al problema del buscaminas para la competencia de programación de la
UTN-FRC.

Objetivo: Ser legible y servir de instroduccion a python

Problema originalmente propuesto: http://acm.tju.edu.cn/toj/showp1330.html

"""

#===============================================================================
# META
#===============================================================================

__author__ = "Juan BC"
__license__ = "BeerWare"
__date__ = "2011/10/26"
__version__ = "0.1"
__email__ = "jbc.develop@gmail.com"
__homepage__ = "http://jbcabral.wordpress.com/"
__twitter__ = "@juanbcabral"


#===============================================================================
# FUNCTIONS
#===============================================================================

def read_n_lines(n):
    """Esta funcion lee las siguientes n lineas del file pointer

    """
    lines = []
    for _ in range(n):
        line = list(raw_input())
        lines.append(line)
    return lines

def touch2coordinates(touch):
    """Combierte los "toques" a una lista de coordenadas (fila, columna)
    donde se toco.

    """
    coords = []
    for idx_row, row in enumerate(touch):
        for idx_col, cell in enumerate(row):
            if cell == ".":
                continue
            coords.append((idx_row, idx_col))
    return coords

def coord2mine(row, col, board):
    """Retorna un "*" si el lugar donde indica la cordenada tiene una mina
    en caso contrario retorna cuantas minas rodean a ese lugar.

    """
    # primero nos fijamos en el lugar
    if board[row][col] == "*":
        return "*"
    # sino exploramos
    mines = 0
    for row_d in (-1, 0, 1):
        for col_d in (-1, 0, 1):
            rowp = row + row_d
            colp = col + col_d
            if rowp < 0 or colp < 0 
               or rowp >= len(board) or colp >= len(board[rowp]):
                continue
            if board[rowp][colp] == "*":
                mines += 1
    return str(mines)

def main():
    """Lee desde un archivo un tablero y toques del buscaminas. Por defecto
    usa la salida estandar.

    """
    # leemos
    n = int(raw_input())
    board = read_n_lines(n)
    touchs = read_n_lines(n)

    # resolvemos
    for row, col in touch2coordinates(touchs):
        symbol = coord2mine(row, col, board)
        touchs[row][col] = symbol

    # convertimos a string para imprimir por pantalla
    print "n".join(["".join(1) for row in touchs])

#===============================================================================
# MAIN
#===============================================================================

if __name__ == "__main__":
    main()

Los archivos en formato archivo

One thought on “Buscaminas Programming Challenges de la UTN-FRC en Python

  1. Programming Challenges se puede hacer solamente en C, C++ y GCJ. Si buscás poder resolver ejercicios en Python y poder enviarlos a un juez podés entrar en SPOJ. La mayoría se pueden resolver en Python.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>