Type Challenges: 04182-medium-fibonacci-sequence Solution

// 基础类型工具：将数字转换为元组长度，用于模拟数字运算
type BuildArray<
  Length extends number,
  Ele = unknown,
  Arr extends unknown[] = []
> = Arr["length"] extends Length ? Arr : BuildArray<Length, Ele, [...Arr, Ele]>;

// 加法：通过合并元组并获取其长度来实现
type Add<A extends number, B extends number> = [
  ...BuildArray<A>,
  ...BuildArray<B>
]["length"];

// 减法：从元组A中截取B个元素后剩余的长度
type Subtract<A extends number, B extends number> = BuildArray<A> extends [
  ...infer U,
  ...BuildArray<B>
]
  ? U["length"]
  : never;

// 乘法：递归地添加A，共B次
type Multiply<A extends number, B extends number> = B extends 0
  ? 0
  : // @ts-ignore
    Add<A, Multiply<A, Subtract<B, 1>>>;

// 判断奇偶
type IsOdd<Num extends number> = BuildArray<Num> extends [
  ...infer _,
  infer Last
]
  ? Last extends never
    ? false
    : true
  : false;

// 矩阵类型：用包含4个数字的元组表示2x2矩阵 [[a, b], [c, d]]
type Matrix = [number, number, number, number];

// 矩阵乘法类型
type MatrixMultiply<A extends Matrix, B extends Matrix> = [
  // 新矩阵左上角: a11 * b11 + a12 * b21
  // @ts-ignore
  Add<Multiply<A[0], B[0]>, Multiply<A[1], B[2]>>,
  // 新矩阵右上角: a11 * b12 + a12 * b22
  // @ts-ignore
  Add<Multiply<A[0], B[1]>, Multiply<A[1], B[3]>>,
  // 新矩阵左下角: a21 * b11 + a22 * b21
  // @ts-ignore
  Add<Multiply<A[2], B[0]>, Multiply<A[3], B[2]>>,
  // 新矩阵右下角: a21 * b12 + a22 * b22
  // @ts-ignore
  Add<Multiply<A[2], B[1]>, Multiply<A[3], B[3]>>
];

// 矩阵快速幂核心类型
type MatrixPower<M extends Matrix, N extends number> = N extends 1
  ? M // 如果指数为1，返回矩阵本身
  : IsOdd<N> extends true
  ? // @ts-ignore
    MatrixMultiply<M, MatrixPower<M, Subtract<N, 1>>> // n为奇数: M * M^(n-1)
  : MatrixPower<M, Divide<N, 2>> extends infer HalfResult // n为偶数: (M^(n/2))^2
  ? HalfResult extends Matrix
    ? MatrixMultiply<HalfResult, HalfResult>
    : never
  : never;

// 除法：通过递归减法实现，结果向下取整
type Divide<
  A extends number,
  B extends number,
  Count extends number = 0
> = A extends 0
  ? Count
  : Subtract<A, B> extends never
  ? Count
  : // @ts-ignore
    Divide<Subtract<A, B>, B, Add<Count, 1>>;

// 计算斐波那契数的类型
type Fibonacci<N extends number> = N extends 0
  ? 0
  : N extends 1
  ? 1
  : MatrixPower<[1, 1, 1, 0], Subtract<N, 1>> extends infer Result // M^(n-1)
  ? Result extends Matrix
    ? Result[0] // 结果矩阵的左上角元素即为F(n)
    : never
  : never;

由腾讯元宝实现仅能最多正确输出第12项仅供整活

Solution by Barrenboat #37310

反正我写不出来这种天才代码 😩

type Fibonacci<
  T extends number,
  CurrentIndex extends any[] = [1],
  Prev extends any[] = [],
  Current extends any[] = [1]
> = CurrentIndex['length'] extends T
  ? Current['length']
  : Fibonacci<T, [...CurrentIndex, 1], Current, [...Prev, ...Current]>

Solution by djdidi #37197


type FibonacciSquence = [1,1,2,3,5,8,13,21,34,55,89,144]

type Decrement = [never, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11];

type Fibonacci<T extends number> = FibonacciSquence[Decrement[T]]

Solution by devshinthant #35262

type Fibonacci<
  T extends number,
  CurrentIndex extends any[] = [1],
  Prev extends any[] = [],
  Current extends any[] = [1]
> = T extends CurrentIndex['length'] ? Current['length'] : Fibonacci<T, [...CurrentIndex, 1], Current, [...Prev, ...Current]>;

Solution by wendao-liu #35066

type Fibonacci<T extends number, L extends number[]=[], R extends number[] = [], N extends number[]=[0]> = T extends N['length']
? R extends [] ? 1 :[...L, ...R]['length']
: Fibonacci<T, [...R], R extends [] ? [0] :[...L, ...R], [0, ...N]>

Solution by hrc1457 #34853

// 你的答案

solution 1:面向结果编程
type FbArr = [1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144];
type Fibonacci<T extends number> = FbArr[T];


solution 2:利用数组长度实现加法
type Fibonacci<T extends number, CurrentIndex extends any[] = [1], Prev extends any[] = [], Current extends any[] = [1]> =
 CurrentIndex['length'] extends T
  ? Current
  : Fibonacci<T, [...CurrentIndex, 1], Current, [...Prev, ...Current]>

Solution by Jayce-liang #34791

type Fibonacci<T extends number, CurrentIndex extends any[] = [any], Previous extends any[] = [], Current extends any[] = [any] > =
  T extends 0
    ? 0
    : T extends CurrentIndex["length"]
      ? Current["length"]
      : Fibonacci<T, [...CurrentIndex, any], Current, [...Previous, ...Current]>

Solution by maximallain #34789

// 你的答案
type Fibonacci<T extends number, N extends any[] = [null], Current extends any[] = [null], Prev extends any[] = []> = 
  N['length'] extends T ? Current['length'] : Fibonacci<T, [...N, null], [...Current, ...Prev], Current>

Solution by heyuelan #34720


// 递减
type Decrement<T extends number, U extends any[] = []> = U['length'] extends T ? 
  U extends [infer _, ...infer Rest] ? 
    Rest['length'] 
  : 
    never 
: 
  Decrement<T, [unknown, ...U]>;
// 累加
type Add<A extends number, B extends number,L extends number[] = []> = A extends 0 ? B extends 0 ? L['length'] : Add<A,Decrement<B>,[...L,1]>  : Add<Decrement<A>,B,[...L,1]> 

type Fibonacci<T extends number, F extends number = 1,S extends number = 1, L extends number[] = []> = T extends 1 | 2 ? 
  1 
: 
  L['length'] extends Decrement<T> ? F :  Fibonacci<T, S, Add<F,S>,[...L,1]>

Solution by Zhang-LuBin #34206

type BuildArray<
	T extends number,
	SUM extends unknown[] = []
> = T extends SUM['length'] ? SUM : BuildArray<T, [...SUM, unknown]>
type Add<N1 extends number, N2 extends number> = [
	...BuildArray<N1>,
	...BuildArray<N2>
]['length'] & number

type Fibonacci<
	T extends number,
	I1 extends number = 1,
	I2 extends number = 1,
	S extends unknown[] = [unknown,unknown]
> = T extends 1
	? I1
	: T extends S['length']
	? I2
  : Fibonacci<T, I2, Add<I1, I2>, [...S, unknown]>

Solution by WAGFS #34087

type Fibonacci<T extends number, CurIdx extends number[] = [1], Prev extends number[] = [], Cur extends number[] = [1]> = CurIdx['length'] extends T ? Cur['length'] :
Fibonacci<T, [...CurIdx, 1], Cur, [...Prev, ...Cur]>

Solution by ouzexi #34067

type Fibonacci<
  T extends number, 
  Pre extends number[] = [],
  Cur extends number[] = [1],
  Index extends number[] = [1]
> = T extends Index['length'] ? Cur['length'] : Fibonacci<T, Cur, [...Pre, ...Cur], [1, ...Index]>;

Solution by ZhipengYang0605 #33404

type Fibonacci<
  T extends number,
  U extends number[] = [1], 
  PRE extends number[] = [],
  SUF extends number[] = [1],
> = U['length'] extends T
  ? U extends [...infer _, infer Last]
    ? Last
    : never
  : Fibonacci<T, [...U, [...SUF, ...PRE]['length']], SUF, [...PRE, ...SUF]>;

Solution by Shaocang #31748

// your answers

type NumToArr<T extends number, A extends number[] = []> = A["length"] extends T
  ? A
  : NumToArr<T, [...A, 0]>;
type MergeArr<A extends number[], B extends number[]> = [...A, ...B];
type Add<
  A extends number,
  B extends number,
  Res = MergeArr<NumToArr<A>, NumToArr<B>>
> = Res extends any[] ? Res["length"] : 0;
type GetLastItem<T extends any[]> = T extends [...infer R, infer L] ? L : never;
type GetBeforeLastItem<T extends any[]> = T extends [
  ...infer R,
  infer T1,
  infer T2
]
  ? T1
  : never;
type Fibonacci<T extends number, Rec extends any[] = [1, 1, 2]> = T extends 1
  ? 1
  : T extends 2
  ? 1
  : Rec["length"] extends T
  ? GetLastItem<Rec>
  : Fibonacci<T, [...Rec, Add<GetLastItem<Rec>, GetBeforeLastItem<Rec>>]>;

Solution by chenqy-yh #31231

type Fibonacci<T extends number, CurrentIndex extends any[] = [1], Prev extends any[] = [], Current extends any[] = [1]> = CurrentIndex['length'] extends T
  ? Current['length']
  : Fibonacci<T, [...CurrentIndex, 1], Current, [...Prev, ...Current]>

Solution by MyeonghoonNam #31063

type Fibonacci<T extends number, Current extends never[] = [never, never, never], Minus1 extends never[] = [never], Minus2 extends never[] = [never]> = 
  T extends 1 | 2
    ? 1
    : Current['length'] extends T
      ? [...Minus1, ...Minus2]['length']
      : Fibonacci<T, [never, ...Current], [...Minus1, ...Minus2], Minus1>

Solution by GodAraden #30797


type Push<T extends any[], U> = T extends [infer F, ...infer O] ? [F, ...O,  U] : [U];

type NumberToArray<T extends number, U extends any[] = []> = U['length'] extends T ?
  U : NumberToArray<T, Push<U, 0>>

type MinusOne<T extends number> = NumberToArray<T> extends [infer F, ...infer O] ? O['length'] : never;

type Plus<T extends number, U extends number> = [...NumberToArray<T>, ...NumberToArray<U>]['length']

type Fibonacci<T extends number> = T extends 1
  ? 1
  : T extends 2
    ? 1
    : Plus<Fibonacci<MinusOne<MinusOne<T>>>, Fibonacci<MinusOne<T>>>

Solution by 8471919 #30236

为什么这么写不对？

type Plus<A extends number, B extends number, AA extends any[] = [], BB extends any[] = []> =
    AA['length'] extends A ?
        BB['length'] extends B ?
            [...AA, ...BB]['length']:
            Plus<A, B, AA, [...BB, 0]>:
        Plus<A, B, [...AA, 0], BB>;


type plus = Plus<4, 5>;
const p: plus = 3;

type Fibonacci<T extends number, A extends number = 1, B extends number = 1> =
    T extends 0 ? A :
        Fibonacci<MinusOne<T>, Plus<A, B>, A>;

type Fib = Fibonacci<4>;

Solution by sundial-dreams #29500

type Fibonacci<
  T extends number,
  Cur extends number[] = [1],
  Prev extends number[] = [],
  Index extends number[] = [1]
> = Index["length"] extends T
  ? Cur["length"]
  : Fibonacci<T, [...Prev, ...Cur], Cur, [...Index, 1]>;

Solution by DoubleWoodLin #28736

// 你的答案
// type 中数字的累加往往利用[]进栈，在通过['length']实现累增计数操作
// 递归的2个基本条件
1.出口
2.递归表达试

type Fibonacci<
  T extends number,
  U extends any[] = [1],
  S1 extends any[] = [],
  S2 extends any[] = [1],
  SUM extends any[] = [1],
> = T extends U['length']
  ? S2['length']
  : Fibonacci<T, [...U, 1], [...S2], [...S1, ...S2], [...SUM, ...S1, ...S2]>

Solution by xpbsm #28456

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

type MinusOne<
  N extends number,
  Acc extends number[] = []
> = Acc["length"] extends N ? Pop<Acc>["length"] : MinusOne<N, [...Acc, 0]>;

type MinusTwo<N extends number> = MinusOne<MinusOne<N>>;

type PlusTwo<
  N1 extends number,
  N2 extends number,
  Acc1 extends number[] = [],
  Acc2 extends number[] = []
> = Acc1["length"] extends N1
  ? Acc2["length"] extends N2
    ? [...Acc1, ...Acc2]["length"]
    : PlusTwo<N1, N2, Acc1, [...Acc2, 0]>
  : PlusTwo<N1, N2, [...Acc1, 0], Acc2>;

type Fibonacci<T extends number> = T extends 1
  ? 1
  : T extends 0
  ? 0
  : PlusTwo<Fibonacci<MinusOne<T>>, Fibonacci<MinusTwo<T>>>;

Solution by idebbarh #28441

// 你的答案
type ParseInt<T extends string> = T extends `${infer F extends number}` ? F : never;
// 反转
type ReverseString<T extends string> = T extends `${infer F}${infer R}` ? `${ReverseString<R>}${F}` : T;
// 移除头部 0
type RemoveLeadingZero<T extends string> = T extends '0' ? T : T extends `${'0'}${infer R}` ? RemoveLeadingZero<R> : T;
// 减一
type InternalMinusOne<T extends string> = T extends `${infer F extends number}${infer R}`
  ? F extends 0
  ? `9${InternalMinusOne<R>}`
  : `${[9, 0, 1, 2, 3, 4, 5, 6, 7, 8][F]}${R}`
  : never;

type MinusOne<T extends number> = T extends 0 ? -1 : ParseInt<RemoveLeadingZero<ReverseString<InternalMinusOne<ReverseString<`${T}`>>>>>

// 1 1 2 3 5 8 13 21
type Plus<F, S, R extends any[] = [], FN extends any[] = [], SN extends any[] = []> = FN['length'] extends F
? SN['length'] extends S
  ? R['length']
  : Plus<F, S, [...R, 0], FN, [...SN, any]>
: Plus<F, S, [...R, 0], [...FN, any]>

type Fibonacci<T extends number> = T extends 2 | 1
? 1 : Plus<Fibonacci<MinusOne<T>>, Fibonacci<MinusOne<MinusOne<T>>>>;

Solution by mysterious-sudo #27835

type numberToArr<T extends number, U extends Array<any> = []> = U['length'] extends T ? U : numberToArr<T, [...U, any]>
type Add<T extends number, U extends number> = [...numberToArr<T>, ...numberToArr<U>]['length']

type Fibonacci<T extends number, U extends number = 3, Z extends any[] = [any], Y extends any[] = [any]> = T extends 1 ? 1 : T extends 2 ? 1 : 
  T extends U ? [...Z, ...Y]['length'] : Add<U, 1> extends number ?  Fibonacci<T, Add<U, 1>, [...Z, ...Y], Z> : -1

Solution by workkk98 #27372

// 你的答案

type Fibonacci<T extends number,L extends any[] = [],R extends any[] = [1],S extends any[] = []> = ${T} extends -${infer Z} ? 0 : [1,...S]['length'] extends T ? R['length'] : Fibonacci<T,R,[...L,...R],[1,...S]>

Solution by biubiuWang931111 #27266

// type Fibonacci<T extends number> = T extends 0 ? 0 : T extends 1 ? 1 : T extends 2 ? 1 : Fibonacci<T-1> + Fibonacci<T-2>

Solution by jsujeong #27037

type Fibonacci<T extends number, Index extends any[] = [1], Prev extends any[] = [], Curr extends any[] = [1]> =
  Index['length'] extends T ? Curr["length"] : Fibonacci<T, [...Index, 1], Curr, [...Curr, ...Prev]>

Solution by smileboyi #26994

// your answers

type Fibonacci<T extends number, Index extends number[] = [1], Prev extends number[] = [], Current extends number[] = [1]> =
Index['length'] extends T 
  ? Current['length']
  : Fibonacci<T, [...Index, 1], Current, [...Prev, ...Current]>

Solution by hhk9292 #26924

type Fibonacci<T extends number, Acc extends never[][] = [[never], [never]]>
  = T extends 0 ? 0
    : T extends 1 ? 1
      : Acc['length'] extends T
        ? Acc[0]['length']
        : Fibonacci<T, [[...Acc[0], ...Acc[1]], ...Acc]>

Solution by tokyo9pm #26732

type Fibonacci<T extends number,arr extends number[] = [1],num1 extends number[] = [],num2 extends number[] = [0]> = T extends 1 ? 1 : [...arr,0]['length'] extends T ? [...num1,...num2]['length'] : Fibonacci<T,[...arr,0],num2,[...num2,...num1]>

Solution by WangZiChu199910252255 #26598

type Length<T extends any[]> = T['length'];
type Push<T extends any[], V> = [...T, V];
type NTuple<N extends number, T extends any[] = []> = Length<T> extends N ? T : NTuple<N, Push<T, any>>;

type Sub<N1 extends number, N2 extends number> = NTuple<N1> extends [...NTuple<N2>, ...infer Rest] ? Length<Rest> : never;
type Add<N1 extends number, N2 extends number> = Length<[...NTuple<N1>, ...NTuple<N2>]>;


type Fibonacci<T extends number> = 
  T extends 1 ?
  1 :
  T extends 2 ?
  1 :
  Add<Fibonacci<Sub<T, 1>>, Fibonacci<Sub<T, 2>>>

Solution by kakasoo #26578