35191 · Trace

Challenge Link

Problem

Implement Trace<T> for a square matrix (2D tuple) that returns the union of all diagonal elements — i.e., T[0][0] | T[1][1] | T[2][2] | ...

type cases = [
  Expect<Equal<Trace<[[1, 2], [3, 4]]>, 1 | 4>>,
  Expect<Equal<Trace<[[0, 1, 1], [2, 0, 2], [3, 3, 0]]>, 0>>,
  Expect<Equal<Trace<[['a', 'b', ''], ['c', '', ''], ['d', 'e', 'f']]>, 'a' | '' | 'f'>>,
]

Solution

type Trace<T extends any[][], Idx extends any[] = []> =
  Idx['length'] extends T['length']
    ? never
    : T[Idx['length']][Idx['length']] | Trace<T, [...Idx, any]>

Explanation

The solution uses a counter tuple Idx to track the current index and collect diagonal elements.

Step by step:

1. Idx extends any[] = [] — starts as an empty tuple (length 0), used as a type-level counter.

2. Idx['length'] extends T['length'] — base case: when the counter reaches the number of rows, stop and return never (no more diagonal elements).

3. T[Idx['length']][Idx['length']] — accesses the element at position [i][i] where i = Idx['length'].

   • Idx['length'] is a numeric literal type (0, 1, 2, ...) that can index into tuple types.

4. Trace<T, [...Idx, any]> — recurse with Idx grown by one element, incrementing the counter.

5. The union | accumulates all diagonal values across iterations.

Why use a tuple as counter?

TypeScript doesn't support arithmetic on numeric literal types directly. The standard trick is to use a tuple whose length property gives the current count. Adding any to the tuple increments the counter by 1.

Example: For [[1,2],[3,4]]:

• Idx=[] (length 0): T[0][0] = 1, recurse
• Idx=[any] (length 1): T[1][1] = 4, recurse
• Idx=[any,any] (length 2): equals T['length'] (2), return never
• Result: 1 | 4 | never = 1 | 4

Key Concepts

• Tuple-as-counter pattern — [...Idx, any] increments a type-level counter
• Numeric indexing of tuples — T[N] where N is a literal number type accesses the Nth element
• Recursive union building — A | Recurse<...> accumulates a union type across iterations