30958-medium-pascals-triangle

Back

type ConvertCount2Number<
  N extends 1[][],
  R extends number[] = []
> = N extends [infer F extends 1[], ...infer Rest extends 1[][]]
  ? ConvertCount2Number<Rest, [...R, F['length']]>
  : R;

type MakeNextRow<
  NowRow extends 1[][],
  NextRow extends 1[][] = []
> = NowRow extends [infer F extends 1[], infer S extends 1[], ...infer Rest extends 1[][]]
  ? MakeNextRow<[S, ...Rest], [...NextRow, [...F, ...S]]>
  : [[1], ...NextRow, [1]]

type MakeTriangle<N extends number, NowRow extends any[][] = [], Rec extends 1[][][] = []> = 
  Rec['length'] extends N ? Rec : Rec['length'] extends 0 ? MakeTriangle<N, [[1],[1]], [...Rec, [[1]]]> : MakeTriangle<N, MakeNextRow<NowRow>, [...Rec, NowRow]>

type ConvertArray2Number<T extends 1[][][], R extends number[][] = []> =
 T extends [infer F extends 1[][], ...infer Rest extends 1[][][]] ? ConvertArray2Number<Rest, [...R, ConvertCount2Number<F>]> : R

type Pascal<N extends number> = ConvertArray2Number<MakeTriangle<N>>

We should count by using array, because Type System can't add.

In other words, Pascal's triangle can be expressed as...

[[1]]
[[1], [1]]
[[1], [1,1], [1]]
[[1], [1,1,1], [1,1,1], [1]]

The primary goal is to make this.

To create this, note the following That is, the second and subsequent lines are the (0,1),(1,2)... of the previous line. (n-1, n)th element with 1 on each end is the next line. For example, the next row of [1, 2, 1] is [1,3,3,1], which can be expressed this way if [1,2,1] is the array A.

[1, (T[0]+T[1]), (T[1]+T[2]), 1] = [1,3,3,1]

Then, for the first line, we can create a ready-made [[1], [1]] for the second line with [[1]] as the initial value, and generate lines after the second line in accordance with the above rules.

Therefore, the necessary process is as follows

Solution by ysknsid25 #35227

// produce new row from previous row T (number is represented as tuple length)
// e.g.
// NewRow<[[0]]>      -> [[0], [0]]         (represents [1] -> [1, 1])
// NewRow<[[0], [0]]> -> [[0], [0, 0], [0]] (represents [1, 1] -> [1, 2, 1])
type NewRow<T extends Num[], Result extends Num[] = []> = Result["length"] extends 0
  ? NewRow<T, [[0]]>
  : T["length"] extends 0
  ? Result
  : T extends [infer First extends Num, infer Second extends Num, ...infer Rest extends Num[]]
  ? NewRow<[Second, ...Rest], [...Result, [...First, ...Second]]>
  : [...Result, [0]];

// e.g.
// Convert<[[0], [0, 0], [0]]> -> [1, 2, 1]
type Convert<T extends Num[]> = T extends [infer First extends Num, ...infer Rest extends Num[]]
  ? [First["length"], ...Convert<Rest>]
  : [];

type Pascal<
  N extends number,
  Result extends unknown[] = [],
  Previous extends Num[] = []
> = Result["length"] extends N
  ? Result
  : NewRow<Previous> extends infer U extends Num[]
  ? Pascal<N, [...Result, Convert<U>], U>
  : never;

Solution by yukicountry #34451

the key point is get the next line

type GetNextLine<
  T extends number[][],
  Ret extends number[][] = []
> = T extends [
  infer A extends number[],
  infer B extends number[],
  ...infer Rest extends number[][]
]
  ? GetNextLine<[B, ...Rest], [...Ret, [...A, ...B]]>
  : Ret;

type Pascal<
  N extends number,
  Ret extends number[][][] = [[[1]]]
> = Ret["length"] extends N
  ? {
      [P in keyof Ret]: Help<Ret[P]>;
    }
  : Pascal<N, [...Ret, GetNextLine<[[], ...[[], ...Ret][Ret["length"]], []]>]>;

type Help<T extends number[][]> = {
  [P1 in keyof T]: T[P1]["length"];
};

Solution by sunupupup #33493

// your answers
type MakeTuple<Length extends number, Result extends 0[] = []> = Result extends { length: Length }
  ? Result
  : MakeTuple<Length, [...Result, 0]>;
type MakePascalLevel<LastLevel extends number[]> = LastLevel extends [infer N1 extends number, infer N2 extends number, ...infer Rest extends number[]]
  ? [[...MakeTuple<N1>, ...MakeTuple<N2>]['length'], ...MakePascalLevel<[N2, ...Rest]>]
  : [];
type Pascal<N extends number, Result extends number[][] = [[1]]> = Result['length'] extends N
  ? Result
  : Pascal<N, [...Result, [1, ...MakePascalLevel<[any,...Result][Result['length']]>, 1]]>;

Solution by DevilTea #33378

type Pascal<N extends number, P extends number[][] = [[1]], L extends number = 0> = N extends P['length'] ? P : Pascal<N, [...P, NewRow<P[L]>], SumAsNum<L, 1>>

type NewRow<R extends number[]> = [1, ...{[I in keyof R]: [I, Sum<I, 1>] extends [`${number}`, infer J extends keyof R & `${number}`] ? SumAsNum<R[I], R[J]> : R[I]}]

type SumAsNum<A extends string | number, B extends string | number> = Sum<A, B> extends `${infer N extends number}` ? N : never

type Sum<A extends string | number, B extends string | number, P extends string = `${A}+${B}`>
  = P extends Match<'00', infer C, infer D> ? `${Sum<C, D>}0`
  : P extends Match<'01', infer C, infer D> ? `${Sum<C, D>}1`
  : P extends Match<'02'|'11', infer C, infer D> ? `${Sum<C, D>}2`
  : P extends Match<'03'|'12', infer C, infer D> ? `${Sum<C, D>}3`
  : P extends Match<'04'|'13'|'22', infer C, infer D> ? `${Sum<C, D>}4`
  : P extends Match<'05'|'14'|'23', infer C, infer D> ? `${Sum<C, D>}5`
  : P extends Match<'06'|'15'|'24'|'33', infer C, infer D> ? `${Sum<C, D>}6`
  : P extends Match<'07'|'16'|'25'|'34', infer C, infer D> ? `${Sum<C, D>}7`
  : P extends Match<'08'|'17'|'26'|'35'|'44', infer C, infer D> ? `${Sum<C, D>}8`
  : P extends Match<'09'|'18'|'27'|'36'|'45', infer C, infer D> ? `${Sum<C, D>}9`
  : P extends Match<'19'|'28'|'37'|'46'|'55', infer C, infer D> ? `${Sum<1, Sum<C, D>>}0`
  : P extends Match<'29'|'38'|'47'|'56', infer C, infer D> ? `${Sum<1, Sum<C, D>>}1`
  : P extends Match<'39'|'48'|'57'|'66', infer C, infer D> ? `${Sum<1, Sum<C, D>>}2`
  : P extends Match<'49'|'58'|'67', infer C, infer D> ? `${Sum<1, Sum<C, D>>}3`
  : P extends Match<'59'|'68'|'77', infer C, infer D> ? `${Sum<1, Sum<C, D>>}4`
  : P extends Match<'69'|'78', infer C, infer D> ? `${Sum<1, Sum<C, D>>}5`
  : P extends Match<'79'|'88', infer C, infer D> ? `${Sum<1, Sum<C, D>>}6`
  : P extends Match<'89', infer C, infer D> ? `${Sum<1, Sum<C, D>>}7`
  : P extends Match<'99', infer C, infer D> ? `${Sum<1, Sum<C, D>>}8`
  : `${A}${B}`

type Match<P extends string, C extends string, D extends string> = P extends `${infer X}${infer Y}` ? `${C}${X}+${D}${Y}` | `${C}${Y}+${D}${X}` : never

Playground

Solution by teamchong #32991

/**
 * This type is a helper that returns the next unknown array with the length of the next value in a row.
 * 
 * Small visualization (numbers are length of arrays)
 * Previous Row: [1, 6, 15, 20, 15, 6, 1]
 * CurrentRowIndex: [1, 7, 21] -> so CurrentRowIndex['length] = 3 and Tail['length'] = 2
 * So the next value is [...PreviousRow[3], ...PreviousRow[2]] so length of result array is 20 + 15 = 35
 * So the next value will be 35 => [1, 7, 21, 35]
 */
type NextValueInRow<
  CurrentRowIndex extends unknown[],
  PreviousRow extends unknown[][] 
> = CurrentRowIndex['length'] extends 0
  ? [unknown] // If the length is 0, return an array with one unknown element, so the value must be 1
  : [
      ...PreviousRow[CurrentRowIndex['length']], 
      // Append the next value in the row by decrementing the index by 1
      ...PreviousRow[CurrentRowIndex extends [infer _, ...infer Tail] ? Tail['length'] : 0]
    ];

// This is a helper type that converts Pascal Triangle represented by unknown arrays to numbers.
type ConvertToNumber<
  UnknownPascal extends unknown[][][],
  N extends unknown[] = [],
  K extends unknown[] = [],
  ConvertedPascalRow extends number[] = [],
  ConvertedPascal extends number[][] = [],
> = N['length'] extends UnknownPascal['length']
      ? ConvertedPascal
      : K['length'] extends UnknownPascal[N['length']]['length']
        ? ConvertToNumber<UnknownPascal, [...N, unknown], [], [], [...ConvertedPascal, ConvertedPascalRow]>
        : ConvertToNumber<UnknownPascal, N, [...K, unknown], [...ConvertedPascalRow, UnknownPascal[N['length']][K['length']]['length']], ConvertedPascal>

type Pascal<
  N extends number,
  RowCount extends unknown[] = [], 
  PreviousRow extends unknown[][] = [],
  CurrentRow extends unknown[][] = [],
  Acc extends unknown[][][] = []
> = 
  RowCount['length'] extends N
    ? ConvertToNumber<Acc>
    : CurrentRow['length'] extends RowCount['length']
      ? Pascal<N, [unknown, ...RowCount], [...CurrentRow, [unknown]], [], [...Acc, [...CurrentRow, [unknown]]]>
      : Pascal<N, RowCount, PreviousRow, [...CurrentRow, NextValueInRow<CurrentRow, PreviousRow>], Acc>;

Solution by user1808 #32609

type Arr<N extends number, R extends unknown[] = []> = R['length'] extends N ? R : Arr<N, [...R, never]>

type Sum<N extends number, M extends number> = [...Arr<N>, ...Arr<M>]['length']

type SumPairs<T extends number[]> =
  T extends [infer A extends number, infer B extends number, ...infer Rest extends number[]]
    ? [Sum<A, B>, ...SumPairs<[B, ...Rest]>]
    : []

type GenerateRow<PrevRow extends number[]> = [1, ...SumPairs<[...PrevRow, 0]>]

type GetLastRow<T extends unknown[][], Default = never> = T extends [...unknown[][], infer L] ? L : Default

type Pascal<N extends number, R extends number[][] = []> =
  R['length'] extends N
    ? R
    : Pascal<N, [...R, GenerateRow<GetLastRow<R, []>>]>
    ```

Solution by Hekumok #32308

type Sum<N extends number, M extends number, CN extends any[] = [], CM extends any[] = []> = 
  CN['length'] extends N 
  ? CM['length'] extends M 
    ? [...CN, ...CM]['length'] 
    : Sum<N, M, CN, [...CM, any]> 
  : Sum<N, M, [...CN, any], CM> 

// AdjacentSum<[1, 2, 3]> -> [3, 5]
type AdjacentSum<T extends number[], R extends number[] = []> =
  T extends [infer X extends number, infer Y extends number, ...infer Z extends number[]]
  ? AdjacentSum<[Y, ...Z], [...R, Sum<X, Y>]>
  : R

type Pascal<N extends number, R extends number[][] = [[1]]> = R['length'] extends N ? R :
  Pascal<
    N,
    [...R, AdjacentSum<[0, ...[any, ...R][R['length']], 0]>]
  >

Solution by kyanagi #31975

type IdxNext<Arr extends 0[][] = [],  Head extends 0[][] = [[0]] > =
  Arr extends [ infer A extends 0[], infer B extends 0[], ...infer Rest extends 0[][] ]
    ? [ ...Head, [ ...A, ...B ], ...IdxNext<[B, ...Rest], []> ]
    : Arr extends []
      ? []
      : [ ...Head, [0] ]

type IdxNextByNumber<N extends number, Counter extends 0[] = [], Last extends 0[][] = [[0]]> =
  N extends Counter['length']
    ? Last
    : IdxNextByNumber<N, [ ...Counter, 0 ], IdxNext<Last extends [] ? [[0]] : Last>>

type IdxArr<N extends number, Arr = IdxNextByNumber<N>> =
  Arr extends [ infer A extends 0[], ...infer Rest extends 0[][] ]
    ? [ A['length'], ...IdxArr<0, Rest> ]
    : []

type Pascal<N extends number, Counter extends 0[] = []> =
  N extends Counter['length']
    ? []
    : [ IdxArr<Counter['length']>, ...Pascal<N, [ ...Counter, 0 ]> ]

Solution by lvjiaxuan #31965

type Last<T extends any[]> = T extends [...any, infer L] ? L : [];
type Counter<N extends number, _Result extends 1[] = []> = _Result[`length`] extends N | 999 /*max*/ ? _Result :
  Counter<N, [1, ..._Result]>;
type Add<A extends number, B extends number> = [...Counter<A>, ...Counter<B>][`length`];
type PileUp<T extends number[], _Result extends any[] = [T[0]]> = T extends [infer F extends number, infer S extends number, ...infer R extends number[]] ? PileUp<[S, ...R], [..._Result, Add<F, S>]> :
  [..._Result, T[0]] /*return*/;

type Pascal<N extends number, _Result extends any[][] = [[1]]> = _Result[`length`] extends N | 999 /*max*/ ? _Result :
  Pascal<N, [..._Result, PileUp<Last<_Result>>]>;

Solution by E-uler #31541

// Create the part of the row between the first and last 1s, but as tuples of that length.
// i.e the [3, 3] in [1, 3, 3, 1], but as [[x, x, x], [x, x, x]]
// I use tuples so I can easily sum them like `[...t1, ...t2]`
type RowMiddle<PrevRow extends any[][]> = PrevRow extends [
  infer H extends any[],
  infer H2 extends any[],
  ...infer R extends any[][],
]
  ? [[...H, ...H2], ...RowMiddle<[H2, ...R]>]
  : [];

type Lengths<Counters extends any[][]> = Counters extends [
  infer H extends any[],
  ...infer R extends any[][],
]
  ? [H["length"], ...Lengths<R>]
  : [];

type Pascal<
  N extends number,
  Result extends number[][] = [],
  PrevRow extends any[][] = [],
> = Result["length"] extends N
  ? Result
  : Result extends []
    ? Pascal<N, [[1]], [[any]]>
    : [[any], ...RowMiddle<PrevRow>, [any]] extends infer newRow extends any[][]
      ? Pascal<N, [...Result, Lengths<newRow>], newRow>
      : never;

Solution by StavNoyAkur8 #31537

type GetLast<T extends number[][]> = T extends [...any,infer L extends number[]]?L:never;

type ToTuple<T extends number,R extends number[] = []> = R['length'] extends T? R: ToTuple<T,[...R,0]>

type Sum<T extends number,U extends number> = [...ToTuple<T>,...ToTuple<U>]['length']

type GenRow<
  T extends number[],
  R extends number[] = [1]
> = 
  T extends [infer F extends number,infer S extends number,...infer L extends number[]]?
    [Sum<F,S>] extends [infer A extends number]?

      GenRow<[S,...L],[...R,A]>:never
    :[...R,1]

type Pascal<
  N extends number, 
  R extends number[][] = [[1]]
> = 
  R['length'] extends N?
    R:
    Pascal<N,[...R,GenRow<GetLast<R>>]>

Solution by jiangshanmeta #31455