Algorithmic Cookbook & Idioms
This cookbook provides 10 self-contained, runnable Tinsel recipes for the most common algorithmic patterns encountered in competitive programming and Advent of Code.
Recipe 1: Multi-Section Input Ingestion (Grid + Instructions)
Problem: Parse a puzzle input divided by a blank line (\n\n) into a 2D map grid and a multi-line sequence of movement instructions, then simulate walking a robot @ across the grid.
let raw_input = "#####\n#@..#\n#...#\n#####\n\n>v<\n>^"
// 1. Split on blank lines with .sections()
let [map_sec, moves_sec] = raw_input.sections()
let g = map_sec.grid()
let mut pos = g.find('@')
g[pos] = '.'
// 2. Map movement characters to Vec2 deltas
let delta_of = {
['^']: vec2(0, -1),
['v']: vec2(0, 1),
['<']: vec2(-1, 0),
['>']: vec2(1, 0)
}
for ch in moves_sec.chars() {
if ch in delta_of {
let next = pos + delta_of[ch]
if g[next] != '#' {
pos = next
}
}
}
assert(pos == vec2(2, 1))
Recipe 2: 2D Connected Components & Flood Fill
Problem: Count the number of distinct connected regions on a 2D map and compute each region's area using g.flood_fill(pos, target_char).
import "std/set" as set
let garden = "AAAA\nBBCD\nBBCC\nEEEC".grid()
let seen = set()
let mut region_areas = []
for [pos, ch] in garden.cells() {
if pos !in seen {
let comp = garden.flood_fill(pos, ch)
for p in comp {
seen.add(p)
}
region_areas.push(comp.len())
}
}
assert(region_areas.sort_desc() == [4, 4, 4, 3, 1])
Recipe 3: Direction-Aware Maze Search (dijkstra with (pos, dir))
Problem: Find the minimum cost through a 2D grid where stepping forward costs 1 and rotating 90^\circ clockwise or counter-clockwise costs 1000.
import "std/grid" as grid
from "std/search" import dijkstra
let maze = "#####\n#..E#\n#.###\n#S..#\n#####".grid()
let start = maze.find('S')
let goal = maze.find('E')
let res = dijkstra({
start: (start, 0), // Facing East (0)
goal: ((pos, _)) -> pos == goal,
step: ((pos, dir)) -> {
let moves = [
[(pos, grid.turn_right(dir)), 1000],
[(pos, grid.turn_left(dir)), 1000]
]
let next_pos = grid.forward(pos, dir)
if maze.get(next_pos) != '#' {
moves.push([(next_pos, dir), 1])
}
moves
}
})
assert(res.found && res.cost == 2004)
Recipe 4: Polygon Area & Lattice Points (Shoelace + Pick's Theorem)
Problem: Given a sequence of trench dig instructions that trace a large rectilinear polygon, compute the total number of enclosed integer lattice points (boundary + interior) without rasterizing a giant grid (std/math shoelace and picks_theorem).
import "std/math" as math
// Dig instructions: (direction, distance)
let plan = [
(vec2(1, 0), 6),
(vec2(0, 1), 5),
(vec2(-1, 0), 2),
(vec2(0, 1), 2),
(vec2(1, 0), 2),
(vec2(0, 1), 2),
(vec2(-1, 0), 5),
(vec2(0, -1), 2),
(vec2(-1, 0), 1),
(vec2(0, -1), 2),
(vec2(1, 0), 2),
(vec2(0, -1), 3),
(vec2(-1, 0), 2),
(vec2(0, -1), 2)
]
let mut curr = vec2(0, 0)
let mut vertices = [curr]
let mut perimeter = 0
for (dir, dist) in plan {
curr += dir * dist
vertices.push(curr)
perimeter += dist
}
let double_area = math.shoelace(vertices)
let lagoon = math.picks_theorem(double_area, perimeter)
assert(lagoon.boundary == 38 && lagoon.interior == 24 && lagoon.total == 62)
Recipe 5: Chinese Remainder Theorem & 2 \times 2 Linear Systems
Problem A: Find the earliest timestamp t such that bus IDs at offsets satisfy t \equiv r_i \pmod{m_i} using math.crt.
Problem B: Solve a 2 \times 2 system of integer linear equations (a_1 x + b_1 y = c_1, a_2 x + b_2 y = c_2) using math.cramer_2x2 (e.g., AoC 2024 Day 13 Claw Contraption).
import "std/math" as math
// A. Chinese Remainder Theorem: x = 2 (mod 3), x = 3 (mod 5), x = 2 (mod 7)
let t = math.crt([2, 3, 2], [3, 5, 7])
assert(t == 23)
// B. 2x2 Linear System: 94*a + 22*b = 8400, 34*a + 67*b = 5400
let [a_presses, b_presses] = math.cramer_2x2([94, 22, 8400], [34, 67, 5400])
assert(a_presses == 80 && b_presses == 40)
Recipe 6: Top-Down Dynamic Programming with memoize
Problem: Count the total number of distinct ways to form a target string from a dictionary of towel patterns (AoC 2024 Day 19 style).
from "std/memo" import memoize
let patterns = ["r", "wr", "b", "g", "bwu", "rb", "gb", "br"]
let mut count_ways = nil
count_ways = memoize(design -> {
if design.len() == 0 {
return 1
}
let mut ways = 0
for pat in patterns {
if design.starts_with(pat) {
ways += count_ways(design[pat.len()..])
}
}
ways
})
assert(count_ways("brwrr") == 2)
assert(count_ways("rrbgbr") == 6)
assert(count_ways("ubwu") == 0)
Recipe 7: 3D Clustering with union_find (Kruskal's DSU)
Problem: Given 3D points, connect all pairs whose squared Euclidean distance is at most D^2 and count the resulting connected components.
from "std/search" import union_find
let pts = [
vec3(0, 0, 0),
vec3(1, 1, 0),
vec3(2, 1, 1),
vec3(10, 10, 10),
vec3(11, 10, 10)
]
let uf = union_find(0..pts.len())
for i in 0..pts.len() {
for j in (i + 1)..pts.len() {
let d = pts[i] - pts[j]
let dist_sq = d.x * d.x + d.y * d.y + d.z * d.z
if dist_sq <= 3 {
uf.union(i, j)
}
}
}
assert(uf.count() == 2)
assert(uf.size(0) == 3 && uf.size(3) == 2)
Recipe 8: Sliding Windows, Combinations & Frequency Counters
Problem: Detect the first 4-character window with all unique characters (AoC 2022 Day 6), count 2-element combinations, and find the most frequent item.
import "std/itertools" as it
from "std/collections" import counter
// 1. Sliding window packet marker detection:
let signal = "mjqjpqmgbljsphdztnvjfqwrcgsmlb".chars()
let windows = it.windows(signal, 4).enumerate()
let mut marker_pos = 0
for [idx, win] in windows {
if win.unique().len() == 4 {
marker_pos = idx + 4
break
}
}
assert(marker_pos == 7)
// 2. Combinations & frequency counter:
assert(it.combinations([10, 20, 30, 40], 2).len() == 6)
let freq = counter(["red", "blue", "red", "green", "red", "blue"])
assert(freq.most_common(1) == [["red", 3]])
Recipe 9: Lazy Infinite Sequences & Early Termination (std/iter)
Problem: Stream an infinite arithmetic progression with count_from(start, step) and short-circuit as soon as 4 primes-like candidates are transformed.
from "std/iter" import count_from
let selected = count_from(100, 7)
.filter(x -> x % 3 == 0 && x % 5 != 0)
.map(x -> x * 2)
.take(4)
.collect()
assert(selected == [228, 312, 354, 396])
Recipe 10: Bitwise State Masks & Arbitrary-Precision bigint
Problem: Toggle indicator bitmasks via XOR (^) and compute exact powers exceeding 64-bit integer limits.
// 1. Bitmask toggling:
let buttons = [0b0011, 0b0110, 0b1100]
let mask = buttons.fold(0, (acc, b) -> acc ^ b)
assert(mask == 0b1001 && mask.bin(4) == "1001")
// 2. Automatic BigInt promotion beyond 2^63 - 1:
let mut p = 1
for _ in 0..100 {
p *= 2
}
assert(type_of(p) == "bigint")
assert(to_string(p) == "1267650600228229401496703205376")