Lesson 07: Interval Algebra & Orbit Cycle Detection

A classic Advent of Code design pattern is the "Part 2 Scale Explosion": Part 1 asks you to process 20 numbers or 1,000 simulation steps, while Part 2 scales the exact same logic to billions of coordinate points (10^{10}) or one trillion simulation steps (10^{12}).

In this lesson, you will master Tinsel's two specialized engines for defeating scale explosions:

1. std/intervals (RangeSet & .remap()): Sweep-line interval algebra and piecewise range trisection.
2. std/orbit (orbit): Automatic cycle detection and O(1) modulo fast-forwarding.

1. Learning Objectives

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

• Construct half-open (start..end) and inclusive (start..=end) ranges and test intersection/membership.
• Normalize overlapping intervals automatically with range_set (std/intervals).
• Split intervals with split(src, cutter) and translate entire RangeSet collections across multi-layer rules with .remap(rules).
• Fast-forward deterministic state machines across 10^{12} iterations using orbit({ initial, steps, step, hash }) (std/orbit).

2. Canonical Half-Open Ranges (a..b and a..=b)

Tinsel normalizes all range values to half-open intervals [start, end):

• 10..20 represents [10, 20) (start = 10, end = 20, .len() == 10).
• 10..=20 (inclusive) automatically normalizes to [10, 21) (start = 10, end = 21, .len() == 11).

Half-open intervals eliminate off-by-one fencepost errors:

1. Span length is always r.end - r.start.
2. Adjacent ranges [10, 15) and [15, 20) touch at 15 without overlap or gap.

let r1 = 10..20
let r2 = 15..=25 // [15, 26)

assert(r1.len() == 10 && r2.len() == 11)
assert(10 in r1 && 20 !in r1 && 25 in r2)
assert(r1.intersects(r2))
assert(r1[3] == 13) // 0-based offset indexing into the range

3. Sweep-Line RangeSet & Piecewise .remap() (std/intervals)

Disjoint Normalization with range_set

When you construct a RangeSet via range_set([r1, r2, ...]) (from std/intervals), Tinsel sorts the intervals and merges any overlapping or abutting segments in a single sweep-line pass:

from "std/intervals" import range_set

// [10..20) and [15..30) overlap -> merged into [10..30)
// [30..40) abuts [10..30) -> merged into [10..40)
let rs = range_set([10..20, 50..60, 15..30, 30..40])

assert(rs.ranges() == [10..40, 50..60])
assert(rs.len() == 40) // 30 + 10
assert(rs.min() == 10)
assert(25 in rs && 45 !in rs)

Interval Trisection (split) & Piecewise Translation (.remap)

Suppose you have an interval [10, 30) and a translation rule [dest=100, src=15, len=10] that shifts points in [15, 25) by +85 to [100, 110).

Instead of looping over millions of individual integers, split(src, cutter) trisects the source range into at most three parts in O(1) time:

Source [10, 30):   [10======15==========25======30)
Cutter [15, 25):            [15=========25)
                   --------------------------------
Prefix (unmapped): [10======15)
Overlap (shifted):          [100=======110)
Suffix (unmapped):                      [25=====30)

Calling rs.remap(rules) applies an entire layer of [[dest_start, src_start, length], ...] rules to every interval in rs and returns a newly normalized RangeSet:

from "std/intervals" import range_set, split

let [prefix, overlap, suffix] = split(10..30, 15..25)
assert(prefix == 10..15 && overlap == 15..25 && suffix == 25..30)

let rs = range_set([10..30])
let remapped = rs.remap([[100, 15, 10]])
assert(remapped.ranges() == [10..15, 25..30, 100..110])
assert(remapped.min() == 10 && remapped.len() == 20)

4. Periodicity & Orbit Fast-Forwarding (std/orbit)

When a puzzle asks you to simulate a deterministic state transition S_{t+1} = f(S_t) for N = 1,000,000,000,000 steps over a finite state space, the trajectory must eventually revisit a state seen at an earlier step:

Step:    0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 ...
State:   A    B    C    D    E    F    C    D ...
                        ^              ^
                  first_seen = 2    i = 6 (cycle_len = 6 - 2 = 4)

Once a repeat is detected at step i, the state at step N is simply history[first_seen + ((N - i) % cycle_len)]!

Using orbit

orbit (from std/orbit) tracks state history automatically and jumps directly to the final state as soon as a cycle repeats:

from "std/orbit" import orbit

let final_val = orbit({
    initial: 5,
    steps: 1_000_000_000_000,
    step: x -> (x * 3 + 1) % 100
})

assert(final_val == 5)

Custom State Hashing (hash:)

Because Tinsel hashes numbers, strings, tuples, arrays, vectors, and structs natively, hash: is optional for most states. When simulating a mutable 2D grid (remembering to .clone() or build a new grid on each step so history entries remain distinct!), you can provide hash: g -> g.to_string():

from "std/orbit" import orbit

let final_grid = orbit({
    initial: ".#.\n.#.\n.#.".grid(),
    steps: 1_000_000_001, // Odd number of blinker flips
    step: g -> g.transpose(),
    hash: g -> g.to_string()
})

assert(final_grid.to_string() == "...\n###\n...")

5. Common Pitfalls & Gotchas

6. Hands-On Exercises

Exercise 7.1: Merging Overlapping Sensor Intervals (Warmup)

Given inclusive horizontal coverage spans [[2, 14], [10, 20], [-2, 3], [25, 30]], build a RangeSet of lo..=hi ranges and compute the total number of covered integer coordinates.

from "std/intervals" import range_set

let raw_spans = [[2, 14], [10, 20], [-2, 3], [25, 30]]
let rs = range_set(raw_spans.map(([lo, hi]) -> lo..=hi))

// [-2..=3] U [2..=14] U [10..=20] merges into [-2, 21) (23 pts) + [25, 31) (6 pts) = 29
assert(rs.len() == 29)
assert(rs.min() == -2)
println("Total covered points:", rs.len())

Exercise 7.2: Multi-Layer Seed Remapping (Practice)

Start with range_set([100..200]) and thread it sequentially through three remap layers: [[200, 100, 50]], [[10, 200, 30]], and [[500, 150, 50]]. Find the minimum coordinate after all three layers.

from "std/intervals" import range_set

let layers = [
    [[200, 100, 50]],
    [[10, 200, 30]],
    [[500, 150, 50]]
]

let final_rs = layers.fold(range_set([100..200]), (curr, layer) -> curr.remap(layer))
assert(final_rs.min() == 10 && final_rs.len() == 100)
println("Min location:", final_rs.min())

Exercise 7.3: Billion-Step Token Ring (Challenge)

A ring of 4 counters [1, 2, 3, 4] updates on each step to [(a + b) % 10, (b + c) % 10, (c + d) % 10, (d + a) % 10]. Use orbit to compute the array state after 1_000_000_000 steps.

from "std/orbit" import orbit

let state = orbit({
    initial: [1, 2, 3, 4],
    steps: 1_000_000_000,
    step: ([a, b, c, d]) -> [
        (a + b) % 10,
        (b + c) % 10,
        (c + d) % 10,
        (d + a) % 10
    ]
})

assert(state == [4, 4, 6, 6])
println("State at 1B steps:", state)

Next Steps

In our final tutorial lesson, Lesson 08: State-Space Search, Graphs, DP & Modules, you will master declarative pathfinding (bfs, dijkstra, astar), graph connectivity (toposort, union_find), memoize, and multi-file project organization.