EduPython: Sphere Online Judge

Introducción

Hace algo de tiempo publiqué en este blog una entrada que presentaba al Proyecto Euler. Como lo expliqué en ese momento, Project Euler es un sitio web que contiene centenas de problemas de tipo matemático que pueden ser resueltos escribiendo un programa de computadora. En esta ocasión quiero presentar otro sitio web que personalmente me parece más interesante: el Sphere Online Judge (SPOJ).

En el Proyecto Euler se describe un problema y el usuario debe proveer un resultado que comúnmente es un simple número. Realmente no importa cómo se llegue al resultado final. Puede ser que el usuario resuelva el problema con lápiz y papel, o puede ser que escriba un programa de computadora que tarde varios días en llegar al resultado. En el SPOJ, por otro lado, se proporciona la descripción de un problema y el usuario debe escribir y subir un programa completo que lo resuelva. En unos cuantos segundos el juez en línea del SPOJ ejecuta y evalúa de manera automática dicho programa para finalmente proporcionar un veredicto que puede ser de aceptación o de rechazo. Los programas que se suben al SPOJ deben cumplir con ciertos requerimientos en cuanto al tamaño del código fuente, a la memoria que utilizan y al tiempo en que tardan en correr.

El SPOJ resulta un excelente recurso de preparación para estudiantes interesados en participar en competencias de programación, como son la Olimpiada Internacional de Informática (IOI) y el Concurso Internacional Universitario de Programación de la ACM (ACM-ICPC).

Equipo de programación competitiva del
Tec de Monterrey, Campus Estado de México,
en la final mundial del ACM-ICPC en la
Technische Universiteit Eindhoven (TUE),
Países Bajos, abril 1999.

El SPOJ cuenta con una base de datos con más de diez mil problemas. Las soluciones pueden ser programadas en más de cuarenta lenguajes diferentes, incluyendo Python por supuesto. Al momento en el que escribo estas líneas, el juez en línea acepta soluciones escritas en Python versiones 2.7 y 3.2.3.

En mi experiencia la mayor parte de los problemas publicados en el SPOJ se pueden resolver usando Python. Sin embargo, sí existen algunos problemas que no pueden ser resueltos en Python debido a que las implementaciones disponibles del lenguaje no son suficientemente rápidas para cumplir con los límites impuestos en cuanto a los tiempos de ejecución. También, en raras ocasiones, algunos problemas explícitamente prohíben utilizar Python.

Usando Python en el SPOJ

El primer paso para comenzar a usar el SPOJ consiste en registrarse en el sitio. Dicho registro es gratis y no toma más que unos cinco minutos en completarse: https://www.spoj.com/register/

La gran mayoría de los problemas del SPOJ se resuelven en tres pasos:

Leer datos de la entrada.
Transformar dichos datos utilizando algún algoritmo.
Producir una salida con los resultados del paso anterior.

La redacción de cada problema incluye siempre al menos un caso de prueba.

La entrada de los programas solución se debe leer desde stdin (standard input o entrada estándar) y la salida se debe escribir a stdout (standard output o salida estándar). Normalmente stdin y stdout están asociados al teclado y a la pantalla de la computadora. En Python 3 las acciones de lectura y escritura se pueden llevar a cabo con las funciones input y print, respectivamente. En Python 2 en lugar de usar la función input se debe usar la función raw_input.

Tomemos como ejemplo al primer problema del SPOJ. Este problema, el cual sirve primordialmente para familiarizarse con el mecanismo de envío de programas solución, requiere leer una secuencia de números enteros. Dichos números se deben imprimir en la salida hasta que se lea el número 42. Cuando eso ocurra el programa debe terminar. El 42 no se debe imprimir, ni tampoco ninguno de los número subsecuentes de la entrada. Por tanto, dado la siguiente entrada:

La salida esperada es:

1
2
88

El siguiente programa en Python 3 resuelve el problema:

# Programa: TEST.py

while True:
    n = int(input())
    if n == 42: break
    print(n)

Es posible correr el programa e ir tecleando manualmente los números conforme el programa los vaya requiriendo. Sin embargo esta forma de probar el programa es susceptible a que se cometan errores de captura. Adicionalmente, las líneas de entrada y salida aparecen intercaladas, lo que hace difícil corroborar que la salida del programa sea efectivamente la esperada.

Lo más recomendable es correr el programa desde una terminal (también conocida como “línea de comando” o “símbolo del sistema”) y redireccionar stdin para que la entrada se reciba desde un archivo. Para ello primeramente se debe crear un archivo de texto con el contenido de la entrada a probar. A este archivo yo normalmente le llamo in.txt. Se puede simplemente “copiar y pegar” el texto deseado desde la página del SPOJ al lugar donde se está editando el archivo in.txt.

En Windows la funcionalidad de una terminal se obtiene corriendo el programa cmd.exe. Una vez abierta la ventana correspondiente, hay que cambiarse al directorio donde se guardaron los archivos TEST.py e in.txt, por ejemplo:

cd \Users\MiCuenta\Documents

Posteriormente se ejecuta el programa así:

python TEST.py < in.txt

La salida debe ser la que se indicó arriba. Sin embargo, si el sistema indica que no puede encontrar el programa ejecutable python, entonces probablemente se pueda corregir esta situación indicando la ruta completa donde está instalado Python 3, algo así como:

c:\Python33\python TEST.py < in.txt

Si se está usando Mac o Linux, los pasos son similares. En la terminal se debe uno primero cambiar al directorio donde están los archivos TEST.py e in.txt, por ejemplo:

cd /home/MiCuenta/Documents

Luego, el programa se debe ejecutar así:

python3 TEST.py < in.txt

El símbolo de “menor que” (<) utilizado al momento de correr un programa en una terminal sirve para redireccionar stdin. Esto es, en lugar de recibir la entrada desde el teclado, la entrada será tomada del archivo cuyo nombre viene inmediatamente después del símbolo “menor que”.

Si deseamos que la salida del programa se vaya a un archivo (en lugar de irse a la pantalla de la terminal) podemos redireccionar también stdout. En este caso usamos el símbolo de “mayor que” (>) seguido del nombre del archivo de salida, tal como se muestra a continuación:

python3 TEST.py < in.txt > out.txt

Dejar la salida del programa en un archivo puede resultar útil si deseamos comparar cuidadosamente dicha salida con la salida esperada según la especificación del problema. Dicha salida esperada debe colocarse en otro archivo. Luego, desde la terminal se pueden usar los comandos fc (en Windows) o diff (en Mac y Linux) para comparar de manera automática los dos archivos de texto (el que tiene la salida esperada y el producido por nuestro programa). El uso de una herramienta para realizar la comparación de archivos, en lugar de hacerlo “a ojo del buen cubero”, es indispensable cuando el tamaño de los contenidos es de más de unas cuantas líneas de texto.

Una vez que tenemos la certeza de que nuestro programa funciona correctamente, podemos entonces subirlo al SPOJ para que sea evaluado por el juez en línea. La página de cada problema tiene una liga de submit en la parte superior izquierda. El código del programa se puede “copiar y pegar” directamente en un área de texto dentro del formulario que aparece, o alternativamente se puede usar el botón de “Examinar...” para seleccionar el archivo guardado en alguna parte de nuestro equipo. Es importante verificar que los campos de Language (Python 3.2.3) y Problem code or id (TEST) sean los correctos. Si todo está bien, presionamos el botón “Send”.

Después de un instante aparece en la página el estado del juez en línea indicando su veredicto:

El primer renglón tiene la evaluación de nuestro programa recién enviado. Si aparece el renglón en gris significa que está aún en proceso de evaluación. Si el renglón está en naranja significa que el programa tuvo algún problema y fue rechazado. Si el renglón está en verde quiere decir que fue aceptado. ¡Yupi!

Sin embargo, si un problema es rechazado, es posible corregirlo y volverlo a enviar tantas veces como sea necesario.

Un problema puede ser rechazado por diversos motivos:

CE compilation error: El programa contiene uno o más errores sintácticos.
WA wrong answer: El programa se ejecutó con éxito, pero los resultados son incorrectos. Probablemente se está interpretando el problema de manera incorrecta o incompleta, o simplemente el programa tiene un error de lógica.
TLE time limit exceeded: El programa se tarda en ejecutar más tiempo que lo que tiene permitido. Esto puede ser causado debido a que el algoritmo está mal diseñado y resulta muy lento, o que el programa contiene un ciclo infinito, o incluso se puede deber a que el programa se detiene por estar esperando datos de entrada inexistentes. También, como ya mencioné anteriormente, puede deberse a que el intérprete de Python resulta muy lento para resolver el problema en cuestión. Si ese es el caso, puede ser que el mismo algoritmo implementado en un lenguaje como C sí corra dentro del tiempo límite.
RE runtime error: El programa produjo algún error a tiempo de ejecución. Cuando se utiliza Python la causa más comunes es un NZEC (non-zero exit code). Esto quiere decir que el programa abortó debido a que se generó una excepción que no fue atrapada. Por ejemplo, se intentó dividir un entero entre cero o acceder a un elemento de una lista usando un índice fuera de rango. Normalmente estos son producidos por errores de lógica en nuestro programa.

Una descripción más detallada del uso del SPOJ se puede consultar en la siguiente liga: How to cope with SPOJ?

Consejos para usar el SPOJ

Al intentar resolver un problema del SPOJ es muy importante leer detenidamente la especificación correspondiente. Cuando el juez en línea marca un WA (wrong answer) muy a menudo resulta que se pasó por alto algún pequeño detalle contenido en la redacción del problema.

Es posible que el programa genere los resultados correctos, pero la salida producida no está en el formato solicitado. Incluso puede ser que un carácter de espacio no solicitado al final de una línea en la salida sea suficiente para que la solución sea rechazada. Por tanto, es muy importante cuidar esos pequeños detalles.

Al estar usando Python, conviene leer la entrada una línea completa a la vez. Por ejemplo, si la descripción de problema dice que una línea de la entrada contiene los números enteros a, b y c separados entre sí por un espacio en blanco, una forma muy sencilla de leer dichos números en Python 3 sería así:

datos = input().split()
a = int(datos[0])
b = int(datos[1])
c = int(datos[2])

Alternativamente, usando una asignación paralela y una list comprehension, podemos reducir el código anterior a una sola línea:

a, b, c = [int(x) for x in input().split()]

Otra recomendación es probar nuestros programas con más casos que los que se incluyen como ejemplo en la redacción del problema. Casi siempre los casos de ejemplo son muy sencillos, pero los casos de prueba que usa el juez en línea son mucho más grandes y exhaustivos. Hay que probar siempre los casos extremos. Por ejemplo, si el problema establece que el programa debe recibir un número entre 0 y 1,000,000, es importante hacer pruebas con varios números incluyendo 0 y 1,000,000.

Al final de la redacción de cada problema viene una sección de comentarios de usuarios. A veces se pueden encontrar ahí algunas pistas o casos adicionales que pueden ayudarnos a entender los motivos por los que el juez en línea está rechazando nuestra solución.

Problema sugeridos

A continuación listo una decena de problemas del SPOJ que se pueden resolver usando unas cuantas líneas de código en Python. Algunos de estos problemas son relativamente fáciles, otros son más retadores.

Desventajas del SPOJ

Como educadores, es importante tener en cuenta las siguientes limitaciones del SPOJ al momento de usarlo con nuestros alumnos:

Casi todos los problemas del SPOJ están redactados en inglés, lo cual puede reducir su utilidad para aquellas personas que no se les facilita leer en este idioma.
Por diseño, la retroalimentación que brinda el juez en línea es bastante limitada. Esto no es problema cuando un programa es aceptado. Sin embargo, cuando el programa es rechazado con WA (wrong answer) no hay más información para conocer el origen del error. Esto puede resultar bastante frustrante. El SPOJ busca que los usuarios diagnostiquen y corrijan sus propios errores.
El SPOJ solo evalúa que un programa funcione correctamente de acuerdo a la especificación dada y dentro de las restricciones estipuladas referentes a tiempo de ejecución, tamaño del código fuente y uso de memoria. Otros atributos que son muy importantes al momento de programar (legibilidad del código, diseño, documentación, uso de buenas prácticas, etc.) no figuran en absoluto al momento en el que el juez en línea emite su veredicto. Aunque relevantes, estos atributos pueden considerarse un tanto subjetivos, por lo que resulta en principio complicado que pudieran evaluarse efectivamente de forma automatizada.

Otros Jueces en Línea

El SPOJ se originó en Polonia a mediados de la década pasada. Probablemente hoy en día es el juez en línea más popular del mundo. Sin embargo no es el único. Otros dos sitios que funcionan de manera similar al SPOJ (y que aceptan soluciones escritas en Python) son:

Caribbean Online Judge: Juez en línea de la Universidad de las Ciencias Informáticas (UCI) de Cuba. Acepta soluciones en Python versión 2.6.5.
Timus Online Judge: Juez en línea de la Universidad Ural Federal de Rusia. Acepta soluciones en Python versiones 2.7.3 y 3.3.0.

El primer juez en línea fue el UVa Online Judge. Éste fue desarrollado por la Universidad de Valladolid en España y se abrió al público en el año de 1997. Su principal limitación es que solamente acepta soluciones en C/C++, Java y Pascal.

Conclusión

La práctica hace al maestro. Si se quiere dominar el arte de resolver problemas a través de la programación es indispensable practicar, practicar y practicar. Y después, hay que seguir practicando todavía más. Con un acervo de miles de problemas y un mecanismo que permite obtener una retroalimentación instantánea, el SPOJ es una de las mejores herramientas que tenemos disponibles para este fin.

26 de octubre de 2013

Sphere Online Judge