Build with the connections

These are course projects for the learner, not already implemented applications. Build small command-line Python versions first. The course’s Astro interface can later host their traces and exercises.

Before coding a feature, write its state sentence and one tiny expected result. Afterward, compare it against a deliberately simple exhaustive solution on small inputs where practical. Each project should explain its algorithm choices, not merely display results.

1. Route laboratory

Build one tool that answers different questions about the same small map.

1. Represent four-neighbor movement implicitly from a board. Show connected open regions.
2. Return one shortest route under uniform move costs, including a parent-based reconstruction.
3. Restrict moves to right/down and count routes. Add a wall-removal budget and explain why the state grows.
4. Restore four-direction movement and find fewest moves with that budget. Reuse the state idea while changing evaluation to BFS.
5. Add nonnegative edge costs and return a cheapest route with Dijkstra.

Use [[0,1,0],[0,0,0]], top-left to bottom-right, as an initial fixture. With right/down movement there is one route with budget zero and three routes with budget one. The shortest four-direction route has three moves with either budget. A one-cell blocked board needs one removal under the course’s entry-cost convention.

Acceptance: returned paths follow legal moves and resource rules; unreachable differs from a zero-length valid route; the distance equals the path’s measured cost; token status appears in the explanation when it affects legality. Include a case where reaching a cell with no token must not erase a later route that still has one.

Main transfer: the representation can persist while objective, state, and frontier policy change independently. Related cards: 10, 11, 23, 26, 32.

2. Word workbench

Build a small dictionary tool with exact lookup, prefix completion, a one-character wildcard, and board search.

Use car, cart, cat, cr, and catr. Prefix car should return car and cart. The literal prefix ca exists even if ca is not itself a word. On board [["c","a"],["r","t"]], four-neighbor search finds cat, catr, and cr; it does not find car through a diagonal move.

Start with a set-based exact lookup, then introduce a trie when prefix queries demand the shared structure. Store a terminal marker, add wildcard branching, then combine trie position with board location and active-route cells. Preserve the original board after each search.

Acceptance: duplicate dictionary entries do not duplicate distinct-word output; empty/no-match queries follow an explicit contract; repeated board letters do not permit cell reuse; a word that is another word’s prefix can still be returned. Explain output cost for large completion sets.

Main transfer: a data structure and a search technique cooperate; the trie narrows choices while backtracking manages the route. Related cards: 14, 16, 17, 45, 46.

3. Planner with changing rules

Build a planner whose objective can change, and make that change visible in the reasoning.

Start with appointments (0,2,2), (2,4,2), (0,4,10), where fields are start, finish, reward. Maximizing count chooses two appointments. Maximizing reward chooses the long one for 10. Show the exchange argument that applies to the first objective and the take/skip recurrence needed for the second.

Then add project selection under a budget using single-use items. Finally add a tree of conflicting parent-child invitations, where root value 5 and two child values 4 yield best value 8. Present these as different constraints on selection; do not force them through one unsupported greedy rule.

Acceptance: boundary-touching appointments are compatible; chosen items are each used at most once; infeasible exact-fill cases differ from valid zero-value results; negative values respect whether an empty selection is allowed; selected tree nodes never contain both ends of an edge. Compare tiny cases against enumeration.

Main transfer: an algorithm is justified by feasibility and objective together; keeping the story while changing either can require a new method. Related cards: 20, 25, 30, 31, 34.

Show that it transferred

For the finished project, record one prediction you got wrong, the missing assumption, the counterexample that exposed it, and the revised model. Then describe a new problem with the same structure but different nouns. That explanation is part of the deliverable alongside the Python code.