Either-or constraints

Two-piece logical constraints are in the cheap category. Three-piece are not. The boundary is sharp.

1. 01
   2-SAT reduces to strongly-connected components on the graph" data-term="implication graph">implication graph. Each clause (a ∨ b) becomes two implication edges (¬a → b and ¬b → a). A variable and its negation in the same SCC mean unsatisfiable — otherwise the SCC order gives a satisfying assignment.

   use petgraph::algo::tarjan_scc;
   use petgraph::graph::DiGraph;
   
   fn two_sat_feasible(n: usize, clauses: &[(i32, i32)]) -> bool {
       let mut g = DiGraph::<(), ()>::new();
       let nodes: Vec<_> = (0..2 * n).map(|_| g.add_node(())).collect();
       let idx = |lit: i32| {
           let v = lit.unsigned_abs() as usize - 1;
           if lit > 0 { 2 * v } else { 2 * v + 1 }
       };
       for &(a, b) in clauses {
           g.add_edge(nodes[idx(-a)], nodes[idx(b)], ());
           g.add_edge(nodes[idx(-b)], nodes[idx(a)], ());
       }
       let sccs = tarjan_scc(&g);
       let mut comp = vec![0usize; 2 * n];
       for (i, c) in sccs.iter().enumerate() {
           for &n in c { comp[n.index()] = i; }
       }
       (0..n).all(|v| comp[2 * v] != comp[2 * v + 1])
   }

2. 02
   Now that the turbofish primer is on page 11, here is a real use of it. DiGraph::new() returns a DiGraph<N, E> whose node and edge types are inferred from how the graph is later used. But this graph starts empty — there is nothing yet for the compiler to infer from, and Rust's type inference is mostly local (it does not look across the whole function). Plain DiGraph::new() would error with "type annotations needed." The turbofish ::<(), ()> pins the type at the construction site: both nodes and edges carry the unit type () (page 14) because the graph structure itself carries all the information — no payloads needed. The alternative is to annotate the binding instead of the call.

   // Empty graph — compiler has nothing to infer from.
   let mut g = DiGraph::new();                  // error: type annotations needed
   
   // Two ways to give inference what it needs — pick one:
   let mut g = DiGraph::<(), ()>::new();        // turbofish at the call site
   let mut g: DiGraph<(), ()> = DiGraph::new(); // annotate the binding
   
   // Once nodes are added with concrete types, no annotation is needed:
   let mut g = DiGraph::new();
   let a = g.add_node("Alice");                  // ← N inferred as &str here
   let b = g.add_node("Bob");
   g.add_edge(a, b, 5u32);                       // ← E inferred as u32 here

3. 03
   let nodes: Vec<_> = … — the underscore in Vec<_> is the type-inference placeholder: "compiler, fill this in for me." It is NOT the unit type (); the unit type already shows up nearby as the argument to add_node(()). Two unrelated underscores live on the same line: the _ inside Vec<_> asks the compiler to infer the element type (which is NodeIndex, what add_node returns), and the |_| is a closure parameter that discards its input. Writing Vec<NodeIndex> would also work but is more brittle — Vec<_> says "give me the right thing, whatever it is."

   let nodes: Vec<_> = (0..2 * n)
       .map(|_| g.add_node(()))
       .collect();
   //   │       │         │
   //   │       │         └── () the unit VALUE — the empty payload our nodes carry
   //   │       └──────────── |_| closure ignores its input; we want add_node's
   //   │                     side effect 2n times, not the integer it was given
   //   └──────────────────── Vec<_> — infer the element type
   
   // Types in this chain:
   //   (0..2*n)                  Range<usize>          iter of usize
   //   .map(|_| g.add_node(()))  Map<…>                iter of NodeIndex
   //   .collect()                                       Vec<NodeIndex>
   
   // Vec<_> vs Vec<()>:
   let xs: Vec<_>  = vec![1, 2, 3];     // compiler infers Vec<i32>
   let ys: Vec<()> = vec![(), (), ()];  // a Vec of zero-byte units — explicit, rare

4. 04
   if lit > 0 { 2 * v } else { 2 * v + 1 } is if as an expression. In Rust if/else is not a statement that produces no value — it is an expression that evaluates to whichever branch ran, and both branches must produce the same type. Rust has no ternary operator (?:) because if already fills that role. The last expression in any block is its value as long as you do not end it with a semicolon.

   // if/else as a value-producing expression:
   let v: usize = if lit > 0 { 2 * v } else { 2 * v + 1 };
   //                          ─────         ───────────
   //                          both branches produce usize → the whole expression is usize
   
   // Equivalent to other languages' ternary:
   //   v = (lit > 0) ? (2 * v) : (2 * v + 1);
   
   // Chains with else if:
   let label = if score >= 90      { "A" }
               else if score >= 80 { "B" }
               else if score >= 70 { "C" }
               else                { "F" };
   
   // As a function return — last expression, no semicolon:
   fn parity(n: i32) -> &'static str {
       if n % 2 == 0 { "even" } else { "odd" }
   }
   
   // Both branches must agree on type:
   let x = if cond { 1 } else { "two" };   // error: i32 vs &str

5. 05
   lit.unsigned_abs() as usize - 1 does three things in one line. unsigned_abs() is an i32 method that returns the absolute value as u32 — handling i32::MIN correctly (whose true absolute value does not fit in i32, which is why plain .abs() would overflow there). as usize is an explicit cast from u32 to usize. And - 1 adjusts for the 1-based indexing convention in CNF format — variable 1 becomes array index 0. usize is the pointer-sized unsigned integer — 64 bits on a 64-bit machine, 32 bits on a 32-bit machine. It is the type used for array indexing, lengths, and counts because it can always represent any valid index into memory. Rust never implicitly converts between integer types; you write as explicitly every time.

   // lit.unsigned_abs() as usize - 1
   //     ─────────────   ───────  ───
   //        method        cast    1-based → 0-based offset
   
   let lit: i32 = -3;
   let abs: u32 = lit.unsigned_abs();    // 3   (works even for i32::MIN)
   let v:   usize = abs as usize - 1;    // 2   (variable 3 → array index 2)
   
   // usize compared to the fixed-width integers:
   //
   //   usize     pointer-sized unsigned — the type for indexes, lengths, counts.
   //             64 bits on 64-bit machines, 32 bits on 32-bit machines.
   //   u32, u64  fixed-width unsigned integers; use when the wire format
   //             or domain requires a specific size.
   //   i32       signed 32-bit integer.  Default for arithmetic when no
   //             domain constraint says otherwise.
   
   let len: usize = vec.len();           // .len() always returns usize
   let first      = vec[0];              // indexing expects usize
   
   // No implicit conversion — the compiler refuses without an explicit cast:
   let n: u32 = 5;
   let i: usize = n;                     // error: expected usize, found u32
   let i: usize = n as usize;            // explicit — fine

6. 06
   for &(a, b) in clauses is two things at once. First, for x in iterable is Rust's loop syntax — it calls iterable.into_iter() (or .iter() for a &slice), binds each yielded value to the pattern on the left, runs the body, and stops when the iterator yields None. Second, the pattern &(a, b) is destructuring through a reference. Iterating clauses (which is &[(i32, i32)]) yields &(i32, i32) references; the pattern &(a, b) reaches past the reference and copies the two i32 values out into a and b. This is only legal because i32 is Copy — a type whose values are cheap to duplicate.

   let clauses: &[(i32, i32)] = &[(1, -2), (-1, 3)];
   
   // Three equivalent ways to walk the slice:
   
   // 1. Bind each element to a reference:
   for pair in clauses {
       let (a, b) = pair;           // a, b are &i32 (references)
   }
   
   // 2. Destructure but bind to references:
   for (a, b) in clauses {
       // a, b are &i32 — works, but every use of a or b needs *a or *b
   }
   
   // 3. Destructure AND copy the inner values out — the page 15 pattern:
   for &(a, b) in clauses {
       // a, b are i32 — clean to use; only works if the inner type is Copy
   }
   
   // What for/in expands to:
   //
   //   for x in collection { body }
   //
   //   ≡   let mut it = collection.into_iter();   // .iter() if collection is &T
   //       while let Some(x) = it.next() { body }
   //
   // Anything implementing IntoIterator works — Vec, slice, HashMap, Range,
   // your own type, channels, file lines, anything.

7. 07
   (0..n) is a range — Rust's lightweight iterator that yields 0, 1, 2, …, n-1 (half-open; the end is not included). 0..=n is the inclusive version. Ranges implement Iterator, so every iterator combinator works on them. .all(predicate) is a terminal combinator: it returns true if every yielded value satisfies the predicate, and false as soon as it sees one that fails (short-circuiting — it stops asking the iterator for more). Together, (0..n).all(|v| comp[2*v] != comp[2*v+1]) reads as "for every variable v in 0..n, the literal and its negation live in different strongly-connected components." If even one variable violates that, the 2-SAT formula is unsatisfiable.

   // Ranges:
   let r = 0..5;                          // half-open: 0, 1, 2, 3, 4   (NOT 5)
   let s = 0..=5;                         // inclusive: 0, 1, 2, 3, 4, 5
   
   // Ranges are iterators — every combinator from page 14 works:
   let sum: i32 = (1..=10).sum();                          // 55
   let evens: Vec<i32> = (1..=10).filter(|n| n % 2 == 0).collect();
   
   // .all(predicate) — true iff every element satisfies it; short-circuits.
   let all_positive = (1..=10).all(|n| n > 0);             // true
   let all_even     = (1..=10).all(|n| n % 2 == 0);        // false (stops at 1)
   
   // Companion: .any(predicate) — true if at least one element satisfies it.
   let any_huge = (1..=10).any(|n| n > 5);                 // true
   
   // Page 15's usage:
   //
   //     (0..n).all(|v| comp[2 * v] != comp[2 * v + 1])
   //      ──── ───  ────────────────────────────────────
   //      iter of   for every v, the literal v and its negation ¬v
   //      0..n      must live in different strongly-connected components
   //
   // If ANY variable has both in the same SCC, .all() returns false
   // and the function returns false — the formula is unsatisfiable.