Pascal's triangle

Challenge Link

Challenge

Given a number N, construct the Pascal's triangle with N rows.
Wikipedia

Solution

This solution constructs Pascal's triangle entirely at the type level by emulating arithmetic through tuple length manipulation. The core insight mirrors how you'd build Pascal's triangle by hand: each row is derived from the previous one by summing adjacent pairs of elements.

The algorithm works in layers:

1. Number-to-tuple conversion (FromLength): Since TypeScript's type system has no native arithmetic, we represent numbers as tuples of 1s. FromLength<3> produces [1, 1, 1]. This is the foundational primitive that enables all "math" at the type level.

2. Type-level addition (Sum): To add two numbers, convert each to a tuple, spread both into a single tuple, and read its length. Sum<2, 3> becomes [...{1,1}, ...{1,1,1}]["length"] = 5.

3. Pairwise row summation (SumArr): This is where the Pascal's triangle logic lives. Given two number arrays of equal length, it produces a new array where each element is the sum of the corresponding elements. It uses recursive head/tail decomposition — extracting the first element of each array, summing them, appending to an accumulator, and recursing on the tails.

4. Deriving the next row (GetNextRow): The elegant trick here is: given row [1, 3, 3, 1], pad it as [0, 1, 3, 3, 1] and [1, 3, 3, 1, 0], then sum element-wise to get [1, 4, 6, 4, 1]. This single operation perfectly captures Pascal's rule that each entry is the sum of the two entries above it.

5. Building the full triangle (PascalArr): Starting from [[1]], it repeatedly appends GetNextRow of the last row. The counter N is a tuple that shrinks by one element each iteration, stopping when its length is 1.

6. Entry point (Pascal): Converts the numeric input N to a tuple, then delegates to PascalArr.

Deep Dive

Tuple-based Arithmetic

TypeScript's type system is not designed for arithmetic, but tuple types provide a backdoor. A tuple's ["length"] property is a numeric literal type, and the spread operator [...A, ...B] concatenates tuples. Together, these two features let us encode addition: [...FromLength<A>, ...FromLength<B>]["length"] computes A + B. This pattern is the backbone of nearly every type-level math challenge.

Recursive Conditional Types with infer

SumArr showcases a powerful pattern: recursive structural decomposition. The conditional type [A, B] extends [[infer HeadA, ...infer TailA], [infer HeadB, ...infer TailB]] simultaneously destructures two arrays in a single check. This is more robust than checking A and B separately, because it guarantees both arrays are non-empty in the true branch.

The infer ... extends number[] syntax (introduced in TypeScript 4.7) is used throughout to narrow inferred types inline, avoiding extra conditional checks.

The GetLast Trick

GetLast<T> uses a brilliant indexing trick: [never, ...T][T["length"]]. If T = [a, b, c] (length 3), then [never, ...T] is [never, a, b, c], and indexing at position 3 yields c. This avoids a recursive implementation entirely — a single indexed access replaces what would otherwise be a full traversal.

The Sliding Window via Padding

GetNextRow<[1, 3, 3, 1]> computes SumArr<[0, 1, 3, 3, 1], [1, 3, 3, 1, 0]>. By offsetting the same row with a leading and trailing zero, the element-wise sum naturally produces the next row of Pascal's triangle. This is the same "sliding window" technique used in imperative implementations, elegantly adapted to a purely declarative type-level context.

Counter Decrement via Tuple Shrinking

Since there's no N - 1 at the type level, the solution converts N to a tuple and peels off one element per iteration with N extends [1, ...infer Tail]. When the tuple's length reaches 1, recursion stops. This is the standard pattern for type-level countdown loops.

Key Takeaways

• Tuple length is the universal arithmetic primitive in TypeScript's type system. Converting numbers to tuples, manipulating them with spreads, and reading back .length is the canonical way to perform addition.
• Recursive conditional types with simultaneous multi-array destructuring ([A, B] extends [[infer ...], [infer ...]]) enable parallel traversal of multiple structures in a single recursion.
• Clever indexing like [never, ...T][T["length"]] can replace entire recursive utilities with a single expression — always look for index-based shortcuts.
• The padding trick ([0, ...row] and [...row, 0]) transforms a complex "sum of adjacent pairs" operation into a simple element-wise sum, demonstrating that the right data transformation can drastically simplify type-level logic.
• Type-level loops are driven by tuple shrinking rather than numeric decrement — convert your counter to a tuple, peel elements, and check length to terminate.