Lecciones y el juego de aprendizaje

Programación dinámica y optimización

Resuelve las decisiones más difíciles de una misión espacial con tablas, en una Raspberry Pi 4: desde una escalera de acoplamiento hasta un planificador de rutas entre estaciones espaciales.

El curso

Programación dinámica y optimización es un curso avanzado de Programación en siete lecciones, después de Recursión y retroceso. Cada lección es Python puro en la Pi, con el montaje de dos LEDs de la galería y el módulo de semáforo donde algo debería encenderse. Cada paso se verifica contra lo que la Pi imprime o lo que hacen sus pines, y cada número de las lecciones es uno que el programa realmente imprime.

  1. Overlapping subproblems: a 16-rung docking ladder climbed 1, 2 or 3 rungs at a time. The slow recursion makes 37,921 calls and works out rung 2 3,136 times; a memo cuts it to 49 calls, a table fills it bottom up, and three rolling numbers climb 1000 rungs.
  2. Coin change: thruster burns of 9, 6, 5 and 1 m/s. Greedy uses three burns for 11 m/s where DP finds two (5 and 6), a pick table says which, a second table counts the 6 mixes, and reachability lists the speeds 4 and 7 m/s burns can never make.
  3. Mochila: 10 kg de carga de cohete para la mayor ciencia. Fuerza bruta sobre 256 cargas, la tabla de la mochila 0/1, la carga reconstruida hacia atrás, la versión de una fila con el error clásico de ir hacia adelante, y 30 cajas resueltas en 3,030 celdas.
  4. Distancia de edición: comandos de sonda garabateados. Por qué contar posiciones falla, la tabla de Levenshtein impresa completa, las ediciones reconstruidas hacia atrás, y una línea de comandos que responde "quisiste decir DEPLOY?"
  5. Voraz contra PD: pases de satélite por fin más temprano (demostrablemente correcto) contra el más corto primero (incorrecto), combustible dividido contra tanques enteros, y una verificación de qué sistemas de monedas puede manejar el voraz.
  6. Planificación: pases que transportan distintas cantidades de datos. El voraz obtiene 105 MB, una PD con bisect obtiene 120, el horario se reconstruye y se reproduce en el LED rojo, y una línea de barrido cuenta antenas.
  7. Proyecto: un planificador de rutas: el final.

El gran final

Un planificador de ferris entre ocho estaciones espaciales. Los tiempos más cortos salen de una PD en orden de estación (el mapa solo vuela hacia afuera, así que es un grafo acíclico dirigido): de la Tierra a Titán en 45 horas. La ruta se reconstruye desde came_from, una segunda tabla responde la mejor ruta con a lo más k tramos (rondas de Bellman-Ford, 49 horas en cuatro tramos), y un kiosco recibe un destino por el monitor serie y enciende los semáforos: verde para una ruta, rojo para una estación que no existe.

Qué hace distinto el motor de la Pi

La Pi corre MicroPython 1.29, no CPython:

  • No hay numpy, así que cada tabla es una lista o una lista de listas, que es como se enseña la PD de todos modos.
  • Los dicts no conservan el orden en que entraron las llaves. El planificador lee sus dicts solo por llave, y todo lo impreso sale de listas.
  • La recursión se detiene cerca de 1,000 llamadas, así que una memo de arriba hacia abajo no puede subir una escalera de 1000 peldaños. El curso usa eso para mostrar por qué importan las tablas de abajo hacia arriba.
  • str.rjust falta, así que la tabla de distancia de edición rellena números con "%2d" % v. bisect, functools y los enteros grandes funcionan como en CPython.