Lesson 08: State-Space Search, Graphs, DP & Modules

In the final lesson of the tutorial course, we explore Tinsel's high-level algorithmic libraries—declarative state-space search (std/search), dynamic programming memoization (std/memo), specialized collections (std/collections), and multi-file module architecture.

1. Learning Objectives

By the end of this lesson, you will be able to:

• Solve unweighted, weighted, and heuristic shortest-path problems with bfs, dfs, dijkstra, and astar (std/search).
• Order DAG dependencies with toposort and track connected components with union_find (dsu).
• Turn exponential recursive functions into linear-time dynamic programming with memoize (std/memo).
• Group and count data with defaultdict and counter (std/collections).
• Organize multi-file Tinsel projects with import, export, and _ module privacy.

2. Declarative State-Space Search (std/search)

Instead of manually wiring priority queues (std/heap), distance maps, visited sets, and parent pointers for every graph problem, std/search provides four unified search functions:

Every search function returns { found: bool, cost: int, path: [state] }:

from "std/search" import bfs, dijkstra, astar

// 1. Unweighted BFS: step returns [next_state, ...]
let bfs_res = bfs({
    start: 1,
    goal: 12,
    step: x -> [x + 1, x * 2].filter(n -> n <= 15)
})
assert(bfs_res.found && bfs_res.cost == 4) // 1 -> 2 -> 3 -> 6 -> 12

// 2. Weighted Dijkstra: step returns [[next_state, edge_cost], ...]
let dj_res = dijkstra({
    start: 0,
    goal: 10,
    step: x -> [[x + 1, 2], [x + 3, 5]].filter(([n, _]) -> n <= 10)
})
assert(dj_res.found && dj_res.cost == 17)

// 3. A* with Manhattan distance heuristic on a 2D grid:
let target = vec2(4, 4)
let astar_res = astar({
    start: vec2(0, 0),
    goal: target,
    step: p -> p.adj4().filter(n -> n.x in 0..=4 && n.y in 0..=4),
    h: p -> p <-> target
})
assert(astar_res.found && astar_res.cost == 8 && astar_res.path.len() == 9)

Composite Search States

Because tuples and structs have native structural hashing, start can be any composite state such as (pos, direction, keys_bitmask), and goal can be a predicate closure state -> bool:

from "std/search" import dijkstra

let res = dijkstra({
    start: (vec2(0, 0), 0), // (position, heading)
    goal: ((pos, _)) -> pos == vec2(2, 1),
    step: ((pos, dir)) -> [
        [(pos + [vec2(1, 0), vec2(0, 1), vec2(-1, 0), vec2(0, -1)][dir], dir), 1],
        [(pos, (dir + 1) % 4), 10]
    ].filter(([(p, _), _]) -> p.x in 0..=3 && p.y in 0..=3)
})
assert(res.found && res.cost == 13) // 2 East (2) + turn South (10) + 1 South (1) = 13

3. DAG Topological Sort & Disjoint-Set Union (std/search)

Topological Sort (toposort)

toposort(edges_or_adj_map, [less]) computes a valid dependency ordering using Kahn's algorithm (returning nil if the graph contains a cycle). Pass an optional comparator less when ties among ready nodes must be broken deterministically:

from "std/search" import toposort

let edges = [["C", "A"], ["C", "F"], ["A", "B"], ["A", "D"], ["B", "E"], ["D", "E"], ["F", "E"]]
// Break ties alphabetically:
let order = toposort(edges, (a, b) -> a < b)
assert(order == ["C", "A", "B", "D", "F", "E"])

Disjoint-Set Union / Union-Find (union_find / dsu)

union_find([items]) returns a UnionFind struct with path compression and union-by-size:

from "std/search" import union_find

let uf = union_find([1, 2, 3, 4, 5])
assert(uf.union(1, 2))
assert(uf.union(2, 3))
assert(!uf.union(1, 3)) // Already in the same component!

assert(uf.connected(1, 3) && !uf.connected(1, 4))
assert(uf.size(1) == 3 && uf.count() == 3)

4. Dynamic Programming (std/memo) & Collections (std/collections)

Automatic Memoization (memoize)

memoize(closure) caches return values across 1 or more arguments automatically:

from "std/memo" import memoize

// Count lattice paths from (x, y) to (0, 0) moving only left or up:
let mut paths = nil
paths = memoize((x, y) -> {
    if x == 0 || y == 0 { 1 } else { paths(x - 1, y) + paths(x, y - 1) }
})
assert(paths(10, 10) == 184756)

Auto-Vivifying defaultdict & Frequency counter (std/collections)

• defaultdict(factory): Automatically initializes missing keys on access, and supports .push(key, item) for building adjacency lists and .inc(key, delta) for counters.
• counter(items_or_string): Counts element frequencies and supports .most_common([n]) and .total().

from "std/collections" import defaultdict, counter

let adj = defaultdict([])
adj.push("start", "A")
adj.push("start", "B")
assert(adj["start"] == ["A", "B"] && adj["missing"] == [])

let freq = counter("mississippi")
assert(freq['i'] == 4 && freq['s'] == 4)
assert(freq.most_common(1)[0][1] == 4)

5. Multi-File Modules, Imports & Privacy (_)

Every .tin file is an isolated module.

• Public Exports: Top-level functions, structs, and let variables whose names do not start with _ are automatically exported (you can also annotate them with export for clarity).
• Private Internals (_): Any top-level binding starting with _ (such as _cache or _helper) is strictly private to that file and excluded from module exports.

Import Variants

// 1. Import standard or relative module (binds to `math` or alias):
import "std/math"
import "std/itertools" as it

// 2. Destructured imports:
from "std/math" import gcd, lcm
import { combinations, windows } from "std/itertools"

assert(math.gcd(24, 36) == 12 && lcm(12, 18) == 36)
assert(combinations([1, 2, 3, 4], 2).len() == 6)
assert(it.windows([10, 20, 30], 2) == [[10, 20], [20, 30]])

6. Common Pitfalls & Gotchas

7. Hands-On Exercises

Exercise 8.1: Obstacle Grid Shortest Path (Warmup)

Parse "S.#..\n..#..\n..#..\n....E".grid() and use bfs to find the shortest path length from 'S' to 'E' avoiding '#'.

from "std/search" import bfs

let g = "S.#..\n..#..\n..#..\n....E".grid()
let start = g.find('S')
let goal = g.find('E')

let res = bfs({
    start: start,
    goal: goal,
    step: p -> g.adj4(p).filter(n -> g[n] != '#')
})

assert(res.found && res.cost == 7)
println("Shortest path steps:", res.cost)

Exercise 8.2: Coin Change with memoize (Practice)

Given coin denominations [1, 3, 4], write a memoized recursive function min_coins(amount) that returns the fewest coins needed to make amount = 30.

from "std/memo" import memoize

let coins = [1, 3, 4]
let mut min_coins = nil
min_coins = memoize(rem -> {
    if rem == 0 { return 0 }
    let mut best = 999999
    for c in coins {
        if c <= rem {
            best = min(best, 1 + min_coins(rem - c))
        }
    }
    best
})

// 30 = 4*7 + 1*2 (9 coins) or 4*6 + 3*2 (8 coins)
assert(min_coins(30) == 8)
println("Min coins for 30:", min_coins(30))

Exercise 8.3: Largest Connected Clusters with union_find (Challenge)

Given 6 nodes 0..6 and edges [[0, 1], [1, 2], [3, 4]], merge each edge in a union_find, collect the sizes of all disjoint groups, sort them descending, and compute the product of the top 3 component sizes.

from "std/search" import union_find

let uf = union_find([0, 1, 2, 3, 4, 5])
for [u, v] in [[0, 1], [1, 2], [3, 4]] {
    uf.union(u, v)
}

let groups = uf.groups()
let sizes = groups.keys().map(root -> groups[root].len()).sort_desc()

// Component sizes are [3, 2, 1] -> product = 6
assert(sizes == [3, 2, 1] && sizes.product() == 6)
println("Component sizes:", sizes)

Congratulations & Next Steps!

You have completed the 8-lesson Tinsel Step-by-Step Tutorial! From here:

• Explore the Algorithmic Cookbook for 10 copy-pasteable puzzle recipes.
• Walk through complete real-world puzzle solutions in Canonical AoC Walkthroughs.
• Bookmark the Technical Reference for fast lookups while solving puzzles.