IC-3002 Tarea corta 8

Suponga que estamos construyendo una aplicación de software para automatizar la selección de rutas para movilización en bicicleta a través de una ciudad.

Sabemos que la movilidad en bicicleta es peligrosa en nuestras ciudades,pues la mayoría no cuenta con infraestructura adecuada, y aún no se ha normalizado una cultura de respeto entre los distintos actores que comparten las vías. Después de un análisis hemos identificado una serie de intersecciones consideradas particularmente peligrosas para la movilidad en bicicleta, por ejemplo debido al alto tránsito, la falta de visibilidad, o la falta de espacio en la vía, entre otras posibles causas.

Considere el mapa de la ciudad modelado como una cuadrícula de tamaño , cada casilla de esta cuadrícula representa una intersección entre dos o más calles. La casilla contiene una bandera levantada (modelada con un 1) cuando se ha identificado como peligrosa, en cualquier otro caso la casilla contiene un 0.

Tomando en cuenta que sólo se admiten movimientos horizontales y verticales (mas no diagonales), sabemos que si en la cuadrícula de la ciudad no hubiera intersecciones peligrosas, la ruta más corta siempre sería de longitud y habrían muchas de estas rutas. El problema que queremos resolver es determinar cuántas rutas de longitud se pueden encontrar dada una matriz que puede contener cero o más intersecciones peligrosas.

En términos computacionales establecemos el problema:

Problema: Dada una matriz de tamaño tal que , encontrar cuántas rutas de longitud existen entre y

Entradas: La matriz .
Salidas: tal que

En el archivo rutas.py, implemente la función contar_rutas_mas_cortas(C) con un algoritmo que resuelva el problema planteado utilizando la técnica de programación dinámica en complejidad temporal .

Cómo instalar el ambiente de desarrollo y ejecutar las pruebas localmente

Este proyecto requiere python3. Asegúrese que esté instalado en su distribución de linux.

Si no lo ha hecho anteriormente, crear un ambiente virtual para las dependencias

python3 -m venv .venv

Activar el ambiente virtual

source .venv/bin/activate

Instalar las dependencias

pip3 install -r requirements.txt

pip3 install gnuplotlib

Ejecutar las pruebas

pytest -s -W ignore::DeprecationWarning

Rúbrica

Completitud (5 pts)

(5 pts) La producción cumple totalmente con los requerimientos solicitados.
(3 pts) La producción cumple parcialmente con los requerimientos solicitados.
(1 pts) La producción, en su mayor parte, no cumple con los requerimientos solicitados.

Correctitud (5 pts)

(5 pts) El código pasa exitosamente todas las pruebas automatizadas.
(3 pts) El código pasa la mayoría de las pruebas automatizadas.
(1 pts) El código no pasa la mayoría de las pruebas automatizadas.

Diseño del algoritmo (5 pts)