// ============= Test Cases =============
import type { Equal, Expect } from './test-utils'

type A1 = Fibonacci<1>;
type B1 = 1;
type C1 = Expect<Equal<A1, B1>>;

type A2 = Fibonacci<2>;
type B2 = 1;
type C2 = Expect<Equal<A2, B2>>;

type A3 = Fibonacci<3>;
type B3 = 2;
type C3 = Expect<Equal<A3, B3>>;

type A4 = Fibonacci<8>;
type B4 = 21;
type C4 = Expect<Equal<A4, B4>>;

// Input:  0, 1, 2, 3, 4, 5, 6,  7,  8,  9, 10, 12, ...
// Output: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

// ============= Your Code Here =============
type Fibonacci<
  T extends number,
  CurrentIndex extends any[] = ['🧮'],
  Prev extends any[] = [],
  Current extends any[] = ['🧮']
> =
  CurrentIndex['length'] extends T
  ? Current['length']
  : Fibonacci<
      T,
      [...CurrentIndex, '🧮'],
      Current,
      [...Prev, ...Current]
    >;

// ============== Alternatives ==============
// credit @NtsDK
type Fibonacci<
  T extends number,
  Result extends '🧮'[][] = [['🧮'], ['🧮']]
> =
  T extends 1 | 2
  ? 1
  : T extends Result['length']
    ? Result[0]['length']
    : Fibonacci<T, [
        [
          ...Result[0],
          ...Result[1]
        ],
        ...Result
      ]>;

type Fibonacci<
  T extends number,
  U extends unknown[] = ['🧮'],
  V extends unknown[] = [],
  W extends unknown[] = ['🧮']
> =
  W['length'] extends T
  ? U['length']
  : Fibonacci<
      T,
      [...U, ...V],
      U,
      ['🧮', ...W]
    >;

// credit: @ethereal-sheep
type Arrayify<N, Acc extends '🧮'[] = []> =
  Acc['length'] extends N
  ? Acc
  : Arrayify<N, ['🧮', ...Acc]>;
type Add<L, R> =
  [...Arrayify<L>, ...Arrayify<R>]['length'];
type Subtract<
  L,
  R,
  Acc extends '🧮'[] = []
> =
  L extends R
  ? Acc['length']
  : Subtract<L, Add<R, 1>, ['🧮', ...Acc]>;
type Fibonacci<T> = 
  T extends 0
  ? 0
  : T extends 1
    ? 1
    : Add<
        Fibonacci<Subtract<T, 2>>,
        Fibonacci<Subtract<T, 1>>
      >;