Laboratorio: entorno de trabajo

Todo el curso se trabaja en un mismo entorno, con g++, gdb, valgrind, make, Git y minisat. También trae Python 3.14, que solo sirve para correr el juez y las pruebas automáticas. Hay dos formas de abrirlo.

Cada semana hay una sesión de laboratorio de 2 horas, con un problema: programar una de las construcciones que se demostraron en clase. Los laboratorios sirven para practicar con la respuesta inmediata del juez, y preparan las prácticas y los exámenes. En las semanas 4, 6, 11 y 14 la sesión es para la práctica, y el problema queda como ejercicio opcional.

Opción 1: GitHub Codespaces

Solo requiere un navegador, internet y una cuenta de GitHub, así que funciona en las computadoras de la universidad. Sin internet no funciona: en ese caso, Docker (opción 2) trabaja sin conexión una vez construida la imagen.

  1. Crear una cuenta en GitHub, con el correo de la universidad si es posible.
  2. Abrir el repositorio del curso que indique el docente.
  3. Elegir Code → Codespaces → Create codespace. La primera vez tarda unos minutos.
  4. En la terminal de abajo, correr env/check.sh. Todas las líneas deben decir ok.

Al terminar, cierren la pestaña y detengan el codespace desde https://github.com/codespaces. Revisen la cuota gratuita de su cuenta en esa misma página, porque se consume rápido.

Opción 2: Docker en una laptop

  1. Instalar Docker.
  2. En la carpeta del curso, correr env/run.sh. La primera vez construye la imagen.
  3. Dentro del contenedor, correr env/check.sh. Todas las líneas deben decir ok.

Se edita con cualquier editor en la laptop, porque la carpeta es la misma dentro y fuera del contenedor.

Resolver un problema con el juez

Cada problema trae un enunciado, un esqueleto solution.cpp y una carpeta casos/.

make            # compila
make test       # corre el juez con todos los casos

El juez imprime una línea por caso:

Veredicto Qué significa Qué revisar
AC Respuesta correcta Nada
WA Respuesta incorrecta Copiar el caso y correrlo a mano: ./build/solution < casos/03.in
TLE Se pasó del límite de tiempo Contar cuántos estados o configuraciones recorre su programa con ese caso
RE El programa terminó con error Compilar con sanitizers para ver dónde

Los programas leen de la entrada estándar y escriben en la salida estándar, sin mensajes como “Ingrese una cadena”, porque el juez los toma como parte de la respuesta.

Cuando un problema pide construir una máquina (por ejemplo, un DFA equivalente a un NFA), hay muchas respuestas correctas: los estados pueden tener otros nombres u otro orden. En esos problemas el juez usa un verificador, que comprueba que la máquina entregada reconoce el lenguaje pedido, y no que sea idéntica a la de casos/NN.out.

Las máquinas como archivos

Los autómatas, las gramáticas y las máquinas de Turing de los ejemplos y de los casos se escriben en archivos de texto. Cada formato se define la semana en que aparece su modelo y queda descrito en code/formats.md: es el mismo en todos los laboratorios posteriores, así que el simulador que escriban en una semana sirve para probar sus máquinas en las siguientes.

Depurar

Para desarrollar, compilen con sanitizers. Encuentran accesos fuera de un arreglo, que dan respuestas raras sin ningún error visible:

g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined solution.cpp -o solution
./solution < casos/01.in

El juez compila con -O2 y sin sanitizers, porque son mucho más lentos. Valgrind y gdb se usan sin sanitizers: compilen con -g -O0.

Para depurar una máquina y no el programa, lo más útil es imprimir su traza: la secuencia de estados o de configuraciones con una cadena corta, y compararla con la que hicieron a mano.

Problemas frecuentes

Síntoma Causa Qué hacer
El codespace no abre o se desconecta Conexión o cuota agotada Revisar la conexión y el uso en https://github.com/codespaces; avisar al docente
permission denied al ejecutar El archivo no es ejecutable o se llamó sin ./ chmod +x archivo o usar ./programa
command not found Están fuera del entorno Comprobar que la terminal es la del codespace o del contenedor
WA solo con la cadena vacía La entrada tiene una línea vacía que el programa se salta Leer con std::getline, no con >>
WA en un autómata sin estados de aceptación Se asumió que siempre hay alguno Probar el caso a mano: el lenguaje es vacío
El programa no termina con una máquina de Turing La máquina no se detiene con esa entrada Respetar el límite de pasos del enunciado
TLE en la construcción de subconjuntos Se generan los 2n2^n subconjuntos Construir solo los alcanzables desde el inicial
valgrind da errores raros o se niega a correr El programa se compiló con sanitizers Compilar sin -fsanitize
dubious ownership de Git Carpeta de otro usuario Abrir la carpeta desde env/run.sh
El programa parece colgado Espera datos de la entrada, o hay un ciclo infinito Escribir los datos, o Ctrl+D para terminar la entrada y Ctrl+C para cortarlo