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> = CountBananas<GrowBananaTree<N>>;
// For a banana tuple representing a number
type Bananas = readonly '🍌'[]
// To build the tree with N rows
type GrowBananaTree<N extends number, Tree extends Array<Bananas[]> = [[['🍌']]], PrevIndex extends number = 0> =
Tree['length'] extends N
? Tree
: GrowBananaTree<N, [...Tree, NextBananaRow<Tree[PrevIndex]>], Tree['length']>
;
// To generate the next row in Pascal's Triangle using a recursive template literal type
type NextBananaRow<PreviousRow extends Bananas[], NewRow extends Bananas[] = [['🍌']], PrevIndex extends number = 0> =
NewRow['length'] extends PreviousRow['length']
// Append a single '🍌' at the end of the row, completing the row as the last element in the rows is always 1
? [...NewRow, ['🍌']]
: [PreviousRow[PrevIndex], PreviousRow[NewRow['length']]] extends [infer Left extends Bananas, infer Right extends Bananas]
// Combine the 'bananas' from the adjacent positions of the previous row
? NextBananaRow<PreviousRow, [...NewRow, [...Left, ...Right]], NewRow['length']>
// Append a single '🍌' at the beginning of the row, as the first element in the rows is always 1
: NextBananaRow<PreviousRow, [...NewRow, ['🍌']], NewRow['length']>
;
// To count the bananas in each position of the tree (transforming banana turples into number of bananas)
type CountBananas<Tree extends unknown[][]> =
{
[R in keyof Tree]:
Tree[R] extends infer Row extends Bananas[]
? { [I in keyof Row]: Row[I]['length'] }
: Tree[R]
}
;
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