import type { Equal, Expect } from '@type-challenges/utils'

type casesGreaterThan = [
  Expect<Equal<GreaterThan<1, 0>, true>>,
  Expect<Equal<GreaterThan<5, 4>, true>>,
  Expect<Equal<GreaterThan<4, 5>, false>>,
  Expect<Equal<GreaterThan<0, 0>, false>>,
  Expect<Equal<GreaterThan<10, 9>, true>>,
  Expect<Equal<GreaterThan<20, 20>, false>>,
  Expect<Equal<GreaterThan<10, 100>, false>>,
  Expect<Equal<GreaterThan<111, 11>, true>>,
  Expect<Equal<GreaterThan<1234567891011, 1234567891010>, true>>,
]

type casesGreaterDigit = [
    Expect<Equal<GreaterDigit<'0', '1'>, false>>,
    Expect<Equal<GreaterDigit<'1', '1'>, false>>,
    Expect<Equal<GreaterDigit<'2', '1'>, true>>,
    Expect<Equal<GreaterDigit<'7', '1'>, true>>,
    Expect<Equal<GreaterDigit<'5', '3'>, true>>,
    Expect<Equal<GreaterDigit<'9', '6'>, true>>,
    Expect<Equal<GreaterDigit<'4', '8'>, false>>,
    Expect<Equal<GreaterDigit<'6', '6'>, false>>,
]

type casesExclusiveRange = [
    Expect<Equal<ExclusiveRange<0>, []>>,
    Expect<Equal<ExclusiveRange<1>, [0]>>,
    Expect<Equal<ExclusiveRange<10>, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]>>,
    Expect<Equal<ExclusiveRange<5>, [0, 1, 2, 3, 4]>>,
]

type casesExcludeDigitsUntil = [
    Expect<Equal<ExcludeDigitsUntil<3>, '3' | '4' | '5' | '6' | '7' | '8' | '9'>>,
    Expect<Equal<ExcludeDigitsUntil<8>, '8' | '9'>>,
    Expect<Equal<ExcludeDigitsUntil<10>, never>>,
]

// Naive implementation of GreaterThan,
// runs in O(N) where N is the smaller number
// because of the recursion limit,
// it can't handle numbers larger than 999
type NaiveGreaterThan<
    T extends number,
    U extends number,
    Acc extends 1[] = []
> = 
// Check if Acc is same as T
Acc['length'] extends T
    // Check if T is U
    ? Acc['length'] extends U
        // T == U
        ? false
        // T < U
        : false
    // Check if Acc is first at U
    : Acc['length'] extends U
        // T > U
        ? true
        // Recurse to the next number
        : NaiveGreaterThan<T, U, [1, ...Acc]>
;

// Digits as string union
type Digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';

// Create an exclusive range/tuple up until T
// Runs in O(N)
type ExclusiveRange<
    N extends number,
    Range extends number[] = [],
    Acc extends 1[] =[],
> =
Range['length'] extends N
    ? Range
    : ExclusiveRange<
        N,
        [...Range, Acc['length']],
        [...Acc, 1]
    >
;

// Digit type without the numbers 0 up until but not including U
type ExcludeDigitsUntil<
    N extends number,
    Digits extends Digit = Digit,
    Range extends number[] = ExclusiveRange<N>,
> = Digits extends `${Range[number]}` ? never : Digits

// Check T is greater than U
type GreaterDigit<
    T extends Digit,
    U extends Digit,
> =
T extends '0'
    ? false
: T extends '1'
    ? U extends ExcludeDigitsUntil<1> ? false : true
: T extends '2'
    ? U extends ExcludeDigitsUntil<2> ? false : true
: T extends '3'
    ? U extends ExcludeDigitsUntil<3> ? false : true
: T extends '4'
    ? U extends ExcludeDigitsUntil<4> ? false : true
: T extends '5'
    ? U extends ExcludeDigitsUntil<5> ? false : true
: T extends '6'
    ? U extends ExcludeDigitsUntil<6> ? false : true
: T extends '7'
    ? U extends ExcludeDigitsUntil<7> ? false : true
: T extends '8'
    ? U extends ExcludeDigitsUntil<8> ? false : true
: T extends '9'
    ? U extends ExcludeDigitsUntil<9> ? false : true
    : never
;

// Compare each digit until there is one digit that is greater or smaller
type GreaterString<
    T extends string,
    U extends string
> = 
T extends `${infer THead}${infer TTail}`
    ? U extends `${infer UHead}${infer UTail}`
        // If both T and U have a Digit in front, compare it
        ? GreaterDigit<THead & Digit, UHead  & Digit> extends false
            // If not greater, compare the rest of the digits
            ? GreaterString<TTail, UTail>
            : true
        : false
    : false
;

// Compare the length of both strings,
// if they have the same length compare each digit
type GreaterStringLength<
    T extends string,
    U extends string
> = 
T extends `${Digit}${infer R1}`
    // T has another digit in front
    ? U extends `${Digit}${infer R2}`
        // U has another digit in front
        ? GreaterStringLength<R1, R2>
        // U ran out of digits
        : true
    // T ran out of digits, either U runs out too or U has more digits,
    // either way GreaterThan returns false
    : false
;

// Runs in O(log(min(N, M)) because it needs to check every digit of the smaller number
type GreaterThan<
    N extends number,
    M extends number
> =
GreaterStringLength<`${N}`, `${M}`> extends true
    ? true
    : GreaterString<`${N}`, `${M}`>
;