Lessons and the learning game

Dynamic programming and optimization

Solve a space mission's hardest choices with tables, on a Raspberry Pi 4: from a docking ladder to a route planner between space stations.

The course

Dynamic programming and optimization is an advanced Coding course in seven lessons, after Recursion and backtracking. Every lesson is plain Python on the Pi, with the gallery's two-LED build and the traffic light module where something should light up. Every step is checked against what the Pi prints or what its pins do, and every number in the lessons is one the program really prints.

  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. Knapsack: 10 kg of rocket cargo for the most science. Brute force over 256 loads, the 0/1 knapsack table, the load walked back, the one-row version with the classic forwards bug, and 30 crates solved in 3,030 cells.
  4. Edit distance: garbled probe commands. Why counting positions fails, the Levenshtein table printed in full, the edits walked back, and a command line that answers "did you mean DEPLOY?"
  5. Greedy vs DP: satellite passes by earliest end (provably right) against shortest first (wrong), split fuel against whole tanks, and a check of which coin systems greedy can handle.
  6. Scheduling: passes that carry different amounts of data. Greedy gets 105 MB, a DP with bisect gets 120, the schedule is walked back and played on the red LED, and a sweep line counts antennas.
  7. Project: a route planner: the finale.

The finale

A planner for ferries between eight space stations. Shortest times come from a DP in station order (the map only flies outward, so it is a directed acyclic graph): Earth to Titan in 45 hours. The route is walked back from came_from, a second table answers the best route with at most k legs (Bellman-Ford rounds, 49 hours in four legs), and a kiosk takes a destination over the Serial Monitor and lights the traffic lights: green for a route, red for a station that does not exist.

What the Pi engine does differently

The Pi runs MicroPython 1.29, not CPython:

  • There is no numpy, so every table is a list or a list of lists, which is how DP is taught anyway.
  • Dicts do not keep the order keys went in. The planner reads its dicts only by key, and everything printed comes from lists.
  • Recursion stops near 1,000 calls, so a top-down memo cannot climb a 1000-rung ladder. The course uses that to show why bottom-up tables matter.
  • str.rjust is missing, so the edit distance table pads numbers with "%2d" % v. bisect, functools and big integers work as in CPython.