Type Challenges: 04182-medium-fibonacci-sequence Solution


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 ixiaolong2023 #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

// 你的答案
type FIArray<T extends number> = T extends 1
  ? [1]
  : T extends 2
    ? [1]
    : [...FIArray<MinusOne<T>>, ...FIArray<MinusOne<MinusOne<T>>>]
type Fibonacci<T extends number> = FIArray['length']

Solution by adoin #26223

 type Tuple<T extends number, R extends Array<1> = []> = R['length'] extends T
  ? R
  : Tuple<T, [...R, 1]>;

type MinusOne<T extends number, R = Tuple<T>> = R extends [infer Head, ...infer Tail]
    ? Tail['length']
    : never;

type Add<T extends number, K extends number> = [...Tuple<T>, ...Tuple<K>]['length'];

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

Solution by yungo1846 #25641