// your answers
type Add<X extends number, Y extends number, T extends number[] = [], U extends number[] = []> = T['length'] extends X
? U['length'] extends Y
? [...T,...U]['length']
: Add<X, Y, T, [...U, 1]>
: Add<X, Y, [...T, 1], U>
type getNext<T extends number[], R extends number[] = []> = T extends [infer x extends number, infer y extends number, ...infer H extends number[]]
? getNext<[y, ...H], [...R, Add<x, y>]>
: R
type Pascal<T extends number, U extends number[][]= [[1]]> = U['length'] extends T
? U
: Pascal<T, [...U, getNext<[0, ...[any, ...U][U['length']], 0]>]>
Solution by BruceYuj #35470
type NextLine<
A,
P extends 1[] = [],
R extends 1[][] = []
> = A extends [infer F extends 1[], ...infer T]
? NextLine<T, F, [...R, [...P, ...F]]>
: [...R, [1]];
type Pascal<
N extends number,
L extends 1[][] = [],
C extends 1[] = [],
R extends unknown[] = [],
F extends 1[][] = NextLine<L>
> = C['length'] extends N
? R
: Pascal<N, F, [...C, 1], [...R, {[K in keyof F]: F[K]['length']}]>;
Solution by alexandroppolus #35306
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]>], Sum<L, 1>>
type NewRow<R extends number[]> = [1, ...{[I in keyof R]: [I, `${Sum<I, 1>}`] extends [`${number}`, infer J extends keyof R & `${number}`] ? Sum<R[I], R[J]> : R[I]}]
type Sum<A extends number | string, B extends number | string, Carry extends 1[] = [], O extends string = ''>
= [ExtractLast<A>, ExtractLast<B>] extends [[`${infer C}`, [...infer I]], [`${infer D}`, [...infer J]]]
? [...I, ...J, ...Carry] extends [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...infer Rest]
? Sum<C, D, [1], `${Rest['length']}${O}`>
: Sum<C, D, [], `${[...I, ...J, ...Carry]['length']}${O}`>
: Carry extends [1]
? Sum<`${A}${B}`, 1, [], O>
: `${A}${B}${O}` extends `${infer N extends number}` ? N : never
type ExtractLast<N extends number | string | bigint, D extends 1[][] = [[], [1], [1, 1], [1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1]]>
= `${N}` extends `${any}${keyof D & `${number}`}`
? {[I in keyof D]: `${N}` extends `${infer L}${I}` ? [L, D[I]] : never}[number]
: []
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