Transposed Matrix

A square matrix flips in about four lines. The ragged ones are the actual challenge.

Transposition turns rows into columns. A 2d tuple models a matrix well enough, but tuples in TypeScript are not required to be rectangular: rows can be shorter than their neighbours, and any row (or the matrix itself) can be written with a rest element standing for an unknown number of entries. Transposed<T> has to stay as accurate as the input allows.

type SomeMatrix = [
  [1, 2, 3],
  [4, 5],
  [6]
]
type TransposedSomeMatrix = [
  [1, 4, 6],
  [2, 5],
  [3]
]

Notice what happened to the short rows. Column 2 is [3] and not [3, undefined, undefined], because nothing follows the gap. A gap sitting between two real values does become undefined, which the tests check separately.

type SomeMatrix = [
[1, 2, 3],
[4, 5],
[6]
]
type TransposedSomeMatrix = [
[1, 4, 6],
[2, 5],
[3]
]

/* _____________ Your Code Here _____________ */

type Matrix = readonly (readonly any[])[]
type Transposed<T extends Matrix> = any

/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '../helpers'

type cases = [
  Expect<
    Equal<
      Transposed<[[1, 2, 3], [4, 5, 6], [7, 8, 9]]>,
      [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
    >
  >,
  Expect<
    Equal<
      Transposed<
        [['a', 'b', 'c', 'd'], ['e', 'f', 'g', 'h'], ['i', 'j', 'k', 'l']]
      >,
      [['a', 'e', 'i'], ['b', 'f', 'j'], ['c', 'g', 'k'], ['d', 'h', 'l']]
    >
  >,
  Expect<Equal<Transpose

Detailed Explanation

The solution in full:

type Eq<X, Y> = (<T>() => T extends X ? 1 : 2) extends <T>() => T extends Y ? 1 : 2 ? true : false
 
type Mutable<T> = T extends readonly [...infer U] ? U : never
 
type TakeFront<T extends any[], H extends any[] = []> =
  T extends [infer F, ...infer R] ? TakeFront<R, [...H, F]> : [H, T]
 
type TakeBack<T extends any[], S extends any[] = []> =
  T extends [...infer R, infer L] ? TakeBack<R, [L, ...S]> : [T, S]
 
type Shape = { head: any[]; rest: unknown; open: boolean; tail: any[] }
 
type Split<T> =
  Mutable<T> extends infer M extends any[]
    ? TakeFront<M> extends [infer H extends any[], infer Mid extends any[]]
      ? TakeBack<Mid> extends [infer C extends any[], infer S extends any[]]
        ? { head: H; rest: C[number]; open: number extends C['length'] ? true : false; tail: S }
        : never
      : never
    : never
 
type FromTail<S extends any[], I extends any[]> =
  S extends [infer F, ...infer R]
    ? I extends [any, ...infer J] ? F | FromTail<R, J> : F
    : undefined
 
type Walk<H extends any[], R extends Shape, I extends any[]> =
  H extends [infer F, ...infer G]
    ? I extends [any, ...infer J] ? Walk<G, R, J> : F
    : R['open'] extends true ? R['rest'] | FromTail<R['tail'], I> : undefined
 
type At<R extends Shape, I> =
  I extends any[]
    ? Walk<R['head'], R, I>
    : R['open'] extends true ? R['rest'] | R['tail'][number] | undefined : undefined
 
type MapAt<R extends Shape[], I> = { [K in keyof R]: At<R[K], I> }
 
type Slots<T extends any[]> = { [K in keyof T]: 0 }
 
type Wider<A extends 0[], B extends 0[]> = A extends [...B, ...0[]] ? A : B
 
type Width<R extends Shape[], W extends 0[] = []> =
  R extends [infer F extends Shape, ...infer Rest extends Shape[]]
    ? Width<Rest, Wider<W, Slots<[...F['head'], ...F['tail']]>>>
    : W
 
type Ragged<R extends Shape[]> =
  R extends [infer F extends Shape, ...infer Rest extends Shape[]]
    ? F['open'] extends true ? true : Ragged<Rest>
    : false
 
type Weave<P extends any[], R, Open extends boolean, S extends any[]> =
  Open extends true ? [...P, ...R[], ...S] : [...P, ...S]
 
type DropEnd<P extends any[]> =
  P extends [...infer H extends any[], infer L]
    ? Eq<L, undefined> extends true ? DropEnd<H> : P
    : P
 
type Trim<P extends any[], R, Open extends boolean, S extends any[]> =
  S extends [...infer SH extends any[], infer L]
    ? Eq<L, undefined> extends true ? Trim<P, R, Open, SH> : Weave<P, R, Open, S>
    : Open extends true
      ? [Exclude<R, undefined>] extends [never]
        ? DropEnd<P>
        : Weave<P, Exclude<R, undefined>, true, []>
      : DropEnd<P>
 
type Column<F extends Shape[], Mid, B extends Shape[], I> =
  Mid extends Shape
    ? Trim<MapAt<F, I>, At<Mid, I>, true, MapAt<B, I>>
    : Trim<MapAt<F, I>, never, false, MapAt<B, I>>
 
type Columns<F extends Shape[], Mid, B extends Shape[], W extends 0[], I extends 0[] = []> =
  I extends [...W, ...0[]] ? [] : [Column<F, Mid, B, I>, ...Columns<F, Mid, B, W, [...I, 0]>]
 
type Lay<F extends Shape[], Mid, B extends Shape[],
  R extends Shape[] = Mid extends Shape ? [...F, Mid, ...B] : [...F, ...B]> =
  Ragged<R> extends true
    ? [...Columns<F, Mid, B, Width<R>>, ...Column<F, Mid, B, 'end'>[]]
    : Columns<F, Mid, B, Width<R>>
 
type Transposed<T extends Matrix> =
  Mutable<T> extends infer M extends any[]
    ? TakeFront<M> extends [infer F extends any[], infer Mid extends any[]]
      ? TakeBack<Mid> extends [infer C extends any[], infer B extends any[]]
        ? Lay<
            { [K in keyof F]: Split<F[K]> },
            number extends C['length'] ? Split<C[number]> : null,
            { [K in keyof B]: Split<B[K]> }
          >
        : never
      : never
    : never

Everything rests on one observation: a tuple holds at most one rest element, so any row is a fixed front part, an optional repeated middle, and a fixed back part. The matrix is a tuple of rows, so it splits exactly the same way.

Every tuple splits into head, rest and tail

TakeFront peels elements off the start, TakeBack off the end. Both stop on their own, because TypeScript refuses to match [infer F, ...infer R] against a tuple whose first element is a rest element, and refuses [...infer R, infer L] when the last one is. The leftovers in the middle are therefore either empty or the rest element itself.

type S1 = Split<[1, 2, 3]>
// { head: [1, 2, 3]; rest: never; open: false; tail: [] }
type S2 = Split<[4, 5, ...6[], 7, 8]>
// { head: [4, 5]; rest: 6; open: true; tail: [7, 8] }

Only an unbounded array reports number as its length, which is what number extends C['length'] asks, and open keeps that answer around. Mutable is there because the given Matrix constraint allows readonly rows.

Reading one index out of a row

There is no arithmetic at the type level, so an index travels as a tuple of 0 whose length is the number: [0, 0] means index 2. Walk removes one head element per index step. When the head runs out the index has landed in the open part, where the answer is a union of everything the row could be holding. Think of [4, 5, ...6[], 7, 8] concretely: length 4 is [4, 5, 7, 8], length 5 is [4, 5, 6, 7, 8], and so on. At offset j past the head the row holds the rest element, or one of the first j + 1 tail elements, or nothing at all once j runs past the tail.

type A1 = At<Split<[4, 5, ...6[], 7, 8]>, [0, 0]> // 6 | 7
type A2 = At<Split<[4, 5, ...6[], 7, 8]>, [0, 0, 0]> // 6 | 7 | 8
type A3 = At<Split<[1, 2]>, [0, 0]> // undefined

At<R, 'end'> is the same question asked about every index past the fixed ones at once, which is what the trailing column of a ragged result needs.

How many columns there are

A row guarantees head plus tail entries, and the widest guarantee decides how many fixed columns the result gets. Slots rewrites a tuple as all 0 first, so that Wider compares lengths and not element types: [1, 2] extends [3, ...any[]] is false for reasons that have nothing to do with width.

[object Object]

If any row is open, nobody knows where the matrix ends, and Lay appends one more column as a rest element: [...Columns<...>, ...Column<..., 'end'>[]].

A column keeps the shape of the matrix

Because the matrix was split the same way as a row, a column is built from the fixed rows at the front, the repeated row in the middle, and the fixed rows at the back. Weave puts that back together as [...P, ...R[], ...S], so a repeated row becomes a repeated entry in every column.

type C2 = Column<[Split<[1, 2]>, Split<[3]>], Split<[4, 5, 6]>, [], [0]>
// [2, undefined, ...5[]]

The undefined is the row [3] having nothing at index 1. It stays because 5 values follow it.

Padding only survives when something follows it

Trim walks the column from the back. An exact undefined at the end falls off, and the walk continues. A value such as 2 | undefined is not padding and stops it, which is why the comparison uses Eq rather than extends undefined.

[object Object]

When the trailing entry is the repeated row, Exclude<R, undefined> takes the padding out of the repeated entry instead. If nothing is left of it the whole rest element disappears, and DropEnd keeps trimming into the fixed part.

Edge cases the tests cover

• number[][] → number[][]: no fixed rows, no guaranteed width, and the padding is excluded from the one repeated column.
• [1, 2, 3][] → [1[], 2[], 3[]]: the repeated row is closed, so the result is three closed columns, each an array.
• [[1, 2, 3], [4, 5]] → the third column is [3], with the gap trimmed away.
• [[1, 2], [3], [4, 5]] → [2, undefined, 5], the same gap kept because a value follows it.
• [[1, 2, 3], [4], ...[5][], [6, 7]] → ...undefined[] survives in the middle column and the last column collapses to [3].
• [[1, ...2[], 3], [4, 5, ...6[], 7, 8], [...9[], 0]] → every entry is a union of what that row could hold, down to 9 | 0 | undefined.