Eight twins — one cheap, one expensive

The single most useful page in this book — eight lookalikes that distinguish "a sprint" from "a SaaS contract."

1. 01
   The eight pairs, encoded as types. Each pair has the same input shape and a different return shape — one falls to a one-line library call, the other needs a solver. Read the pair before sizing the ticket.

   // Cheap twin — Euler, visit every edge.  Linear time.
   fn inspect_every_road(roads: &[(usize, usize)]) -> Option<Vec<usize>> { todo!("Hierholzer") }
   // Expensive twin — Hamilton, visit every node.  NP-complete.
   fn visit_every_store(roads: &[(usize, usize)]) -> Option<Vec<usize>> { todo!("SAT or brute force") }
   
   // Cheap — 2-SAT.  Linear via SCC on the implication graph.
   fn two_piece_rules(clauses: &[(i32, i32)]) -> bool { todo!("tarjan_scc") }
   // Expensive — 3-SAT.  NP-complete.
   fn three_piece_rules(clauses: &[[i32; 3]]) -> bool { todo!("splr") }
   
   // Cheap — bipartite check.  Linear.
   fn two_categories(g: &[(usize, usize)]) -> bool { todo!("BFS two-coloring") }
   // Expensive — k-coloring for k ≥ 3.  NP-complete.
   fn three_categories(g: &[(usize, usize)]) -> Option<Vec<u8>> { todo!("splr") }
   
   // Cheap — shortest path with positive weights.  Dijkstra.
   fn shortest(g: &[(usize, usize, u32)]) -> u32 { todo!("petgraph::dijkstra") }
   // Expensive — longest simple path.  NP-complete.
   fn longest_no_repeat(g: &[(usize, usize, u32)]) -> u32 { todo!("brute force or ILP") }
   
   // Cheap — MST, connect every node.  Greedy.
   fn connect_all(sites: &[(usize, usize, u32)]) -> u32 { todo!("min_spanning_tree") }
   // Expensive — Steiner tree, connect a subset using relays.  NP-complete.
   fn connect_subset(sites: &[(usize, usize, u32)], terminals: &[usize]) -> u32 { todo!("ILP") }
   
   // Cheap — bipartite matching.  Hungarian.
   fn match_two_sides(cost: &[Vec<i32>]) -> Vec<usize> { todo!("kuhn_munkres") }
   // Expensive — 3-dimensional matching.  NP-complete.
   fn match_three_sides(triples: &[(usize, usize, usize)]) -> Vec<(usize, usize, usize)> { todo!("ILP") }
   
   // Cheap — LP, continuous variables.
   fn allocate_fractional(c: &[f64]) -> Vec<f64> { todo!("good_lp + HiGHS, continuous") }
   // Expensive — ILP, integer variables.
   fn allocate_whole(c: &[f64]) -> Vec<i32> { todo!("good_lp + HiGHS, binary or integer") }
   
   // Cheap — fractional knapsack.  Greedy by ratio.
   fn take_fractions(items: &[(u32, u32)], cap: u32) -> f64 { todo!("sort by value/weight, fill") }
   // Expensive — 0/1 knapsack.  DP for small budgets, ILP otherwise.
   fn take_whole_items(items: &[(u32, u32)], cap: u32) -> u32 { todo!("knapsack DP") }

2. 02
   todo! is one of Rust's placeholder macros. It compiles into any context that expects a value, but at runtime calling it panics with "not yet implemented." The trick is that todo! returns the never type ! — a type that has no values. Because ! can be coerced into any other type (a never-value can stand in for any value, since execution never actually reaches the coercion point), the compiler accepts todo!() as the body of a function with any return type, as one arm of a match expression, or anywhere else a value is expected. Page 38 uses todo!("...") and friends as executable annotations — the function signatures compile and document each twin's intended algorithm, and any code that actually calls one of them crashes with a useful message instead of silently producing a wrong answer. Three closely-related macros share the same family. todo!() says "I plan to implement this later" — the development-time TODO marker. unimplemented!() says "I have intentionally left this unimplemented" — typically for trait method stubs you do not want to fill in. unreachable!() is for code paths the programmer believes can never execute; if it ever fires, it indicates a logic bug in the surrounding code.

   // todo! — placeholder for code you'll write later.
   fn area_of_circle(radius: f64) -> f64 {
       todo!()
   }
   // Compiles.  Calling it panics with: "not yet implemented"
   //   thread 'main' panicked at 'not yet implemented'
   
   // With a message — gives the reader a hint about what's missing:
   fn area_of_circle(radius: f64) -> f64 {
       todo!("use std::f64::consts::PI * radius * radius")
   }
   
   
   // Why todo! fits any return type — the never type !
   //
   //   ! is the type of "this expression never produces a value."
   //   It can be coerced into any type, because a never-value can stand
   //   in for any value (no actual conversion happens — execution never
   //   reaches the coercion point).
   
   fn returns_string() -> String      { todo!() }       // ! → String  ✓
   fn returns_vec()    -> Vec<i32>    { todo!() }       // ! → Vec<i32> ✓
   fn returns_option() -> Option<u32> { todo!() }       // ! → Option   ✓
   
   // Same in a match arm — when one arm panics, the others decide the type:
   let label = match score {
       s if s >= 90 => "A",
       s if s >= 80 => "B",
       _            => todo!("rest of the grading scale"),
   };
   
   
   // Page 38's use — executable documentation of intent:
   //
   //   fn inspect_every_road(roads: &[(usize, usize)]) -> Option<Vec<usize>> {
   //       todo!("Hierholzer")            ← reader sees the planned algorithm
   //   }
   //
   // The compiler accepts the file; tests against any twin still fail
   // loudly with the algorithm hint, never producing a wrong answer silently.
   
   
   // Three placeholder macros — same shape, different intent:
   //
   //   todo!()           "I plan to implement this later."
   //                     Use during development as a TODO marker.
   //
   //   unimplemented!()  "I have intentionally left this unimplemented."
   //                     Use for trait method stubs you don't want to fill in.
   //
   //   unreachable!()    "Execution should never reach this point."
   //                     Use to assert invariants; firing means a logic bug.
   //
   // All three return !, so they fit in any expression slot.
   
   
   // One more relative — for hand-written runtime assertions:
   let n: i32 = read_input();
   if n < 0 {
       panic!("expected non-negative number, got {}", n);
   }
   // panic!() also returns ! and unconditionally crashes.  Use it when
   // you have a specific runtime check whose failure means "stop everything."