274 - Integers Comparator

[Gelio]

Solution

TypeScript playground

The solution creates some custom digits that will be used for digit-by-digit comparison, and then, converts numbers to string literal types, comparing them digit-by-digit afterward.

There are additional early checks for number equality.

In case one number is negative and the other is positive, the result can be quickly concluded too.

In case both numbers are negative, the result is the inverse of the result for the reversed absolute arguments (compare(-5, -8) is the same as compare(8, 5))

The solution contains tests for each written type.

enum Comparison {
  Greater,
  Equal,
  Lower,
}

// Custom _Digits
type _Digit = {
  zero: boolean;
  prev?: any;
}
type _0 = {
  zero: true
}
type IsZero<T extends _Digit> = T['zero'];
type Next<P extends _Digit> = {
  zero: false,
  prev: P
};
type Prev<P extends _Digit> = P['prev'];

type _1 = Next<_0>;
type _2 = Next<_1>;
type _3 = Next<_2>;
type _4 = Next<_3>;
type _5 = Next<_4>;
type _6 = Next<_5>;
type _7 = Next<_6>;
type _8 = Next<_7>;
type _9 = Next<_8>;

type _Digits = [_0, _1, _2, _3, _4, _5, _6, _7, _8, _9];
type ConvertDigit<T extends Digit> = _Digits[T];

type ConvertDigitTest1 = Expect<Equal<ConvertDigit<0>, _0>>;
type ConvertDigitTest2 = Expect<Equal<ConvertDigit<1>, _1>>;
type ConvertDigitTest3 = Expect<Equal<ConvertDigit<9>, _9>>;
// @ts-expect-error
type ConvertDigitTest4 = Expect<Equal<ConvertDigit<10>, unknown>>;

type ConvertDigitString<T extends `${Digit}`> = _Digits[T];
type ConvertDigitStringTest1 = Expect<Equal<ConvertDigitString<'0'>, _0>>;
type ConvertDigitStringTest2 = Expect<Equal<ConvertDigitString<'1'>, _1>>;
type ConvertDigitStringTest3 = Expect<Equal<ConvertDigitString<'9'>, _9>>;
// @ts-expect-error
type ConvertDigitStringTest4 = Expect<Equal<ConvertDigitString<'10'>, unknown>>;

type IsZeroTest1 = Expect<Equal<IsZero<_0>, true>>;
type IsZeroTest2 = Expect<Equal<IsZero<_1>, false>>;
type IsZeroTest3 = Expect<Equal<IsZero<Prev<_1>>, true>>;
type IsZeroTest4 = Expect<Equal<IsZero<Next<_1>>, false>>;
type PrevNextTest5 = Expect<Equal<Prev<Next<_0>>, _0>>;
type PrevTest6 = Expect<Equal<Prev<_1>, _0>>;
type PrevTest7 = Expect<Equal<Prev<_0>, unknown>>;
type PrevTest8 = Expect<Equal<Prev<_5>, _4>>;
type PrevTest9 = Expect<Equal<Prev<_8>, _7>>;
type PrevTest10 = Expect<Equal<Prev<_5>, _4>>;

// CompareDigit
type CompareDigit<A extends _Digit, B extends _Digit> = IsZero<A> extends true
  ? IsZero<B> extends true
    ? Comparison.Equal
    : Comparison.Lower
  : IsZero<B> extends true
    ? Comparison.Greater
    : CompareDigit<Prev<A>, Prev<B>>;
      
type CompareDigitTest1 = Expect<Equal<CompareDigit<_0, _0>, Comparison.Equal>>;
type CompareDigitTest2 = Expect<Equal<CompareDigit<_0, _1>, Comparison.Lower>>;
type CompareDigitTest3 = Expect<Equal<CompareDigit<_1, _1>, Comparison.Equal>>;
type CompareDigitTest4 = Expect<Equal<CompareDigit<_9, _9>, Comparison.Equal>>;
type CompareDigitTest5 = Expect<Equal<CompareDigit<_9, _1>, Comparison.Greater>>;
type CompareDigitTest6 = Expect<Equal<CompareDigit<_1, _2>, Comparison.Lower>>;
type CompareDigitTest7 = Expect<Equal<CompareDigit<_5, _8>, Comparison.Lower>>;
type CompareDigitTest8 = Expect<Equal<CompareDigit<_4, _8>, Comparison.Lower>>;
type CompareDigitTest9 = Expect<Equal<CompareDigit<_8, _5>, Comparison.Greater>>;
type CompareDigitTest10 = Expect<Equal<CompareDigit<_6, _8>, Comparison.Lower>>;
type CompareDigitTest11 = Expect<Equal<CompareDigit<_7, _8>, Comparison.Lower>>;
type CompareDigitTest12 = Expect<Equal<CompareDigit<_7, _9>, Comparison.Lower>>;



type NumberLike = string;
type IsNegative<A extends NumberLike> = A extends `-${infer X}` ? true : false;

type IsNegativeTest1 = Expect<Equal<IsNegative<'-5'>, true>>;
type IsNegativeTest2 = Expect<Equal<IsNegative<'0'>, false>>;
type IsNegativeTest3 = Expect<Equal<IsNegative<'10'>, false>>;

type Absolute<A extends NumberLike> = A extends `-${infer X}` ? X : A;
type AbsoluteTest1 = Expect<Equal<Absolute<'-5'>, '5'>>;
type AbsoluteTest2 = Expect<Equal<Absolute<'0'>, '0'>>;
type AbsoluteTest3 = Expect<Equal<Absolute<'10'>, '10'>>;

type IsEmpty<T extends string> = T extends '' ? true : false;

type IsEmptyTest1 = Expect<Equal<IsEmpty<'-5'>, false>>;
type IsEmptyTest2 = Expect<Equal<IsEmpty<''>, true>>;


type Digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9;

type FirstDigit<A extends NumberLike> = A extends `${infer First}${Digit}${infer Rest}`
  ? First extends `${Digit}`
    ? First
    : A extends `${Digit}`
      ? A
      : never
  : never;

type FirstDigitTest1 = Expect<Equal<FirstDigit<'10'>, '1'>>;
type FirstDigitTest2 = Expect<Equal<FirstDigit<'1'>, '1'>>;
type FirstDigitTest3 = Expect<Equal<FirstDigit<''>, never>>;

type RestDigits<A extends NumberLike> = A extends `${Digit}${infer Rest}`
  ? Rest
  : never;

type RestDigitsTest1 = Expect<Equal<RestDigits<'10'>, '0'>>;
type RestDigitsTest2 = Expect<Equal<RestDigits<'1'>, ''>>;
type RestDigitsTest3 = Expect<Equal<RestDigits<''>, never>>;

type CompareByAbsoluteDigits<A extends NumberLike, B extends NumberLike> = IsEmpty<A> extends true
  ? IsEmpty<B> extends true
    ? Comparison.Equal
    : Comparison.Lower
  : IsEmpty<B> extends true
    ? Comparison.Greater
    : CompareDigit<ConvertDigitString<FirstDigit<A>>, ConvertDigitString<FirstDigit<B>>> extends Comparison.Equal
      ? CompareByAbsoluteDigits<RestDigits<A>, RestDigits<B>>
      : CompareDigit<ConvertDigitString<FirstDigit<A>>, ConvertDigitString<FirstDigit<B>>>;

type CompareByAbsoluteDigitsTest1 = Expect<Equal<CompareByAbsoluteDigits<'123', '0'>, Comparison.Greater>>;
type CompareByAbsoluteDigitsTest2 = Expect<Equal<CompareByAbsoluteDigits<'123', '123'>, Comparison.Equal>>;
type CompareByAbsoluteDigitsTest3 = Expect<Equal<CompareByAbsoluteDigits<'0', '123'>, Comparison.Lower>>;
type CompareByAbsoluteDigitsTest4 = Expect<Equal<CompareByAbsoluteDigits<'04565648979', '04565648979'>, Comparison.Equal>>;
type CompareByAbsoluteDigitsTest5 = Expect<Equal<CompareByAbsoluteDigits<'5', '8'>, Comparison.Lower>>;

type CompareByDigits<A extends NumberLike, B extends NumberLike> = IsNegative<A> extends true
  ? IsNegative<B> extends true
    ? CompareByAbsoluteDigits<Absolute<B>, Absolute<A>>
    : Comparison.Lower
  : IsNegative<B> extends true
    ? Comparison.Greater
    : CompareByAbsoluteDigits<A, B>;

type CompareByDigitsTest1 = Expect<Equal<CompareByDigits<'1', '1'>, Comparison.Equal>>;
type CompareByDigitsTest2 = Expect<Equal<CompareByDigits<'1', '0'>, Comparison.Greater>>;
type CompareByDigitsTest3 = Expect<Equal<CompareByDigits<'-1', '0'>, Comparison.Lower>>;
type CompareByDigitsTest4 = Expect<Equal<CompareByDigits<'-1', '-2'>, Comparison.Greater>>;
type CompareByDigitsTest5 = Expect<Equal<CompareByDigits<'-25', '-30'>, Comparison.Greater>>;
type CompareByDigitsTest6 = Expect<Equal<CompareByDigits<'-5', '-3'>, Comparison.Lower>>;
type CompareByDigitsTest7 = Expect<Equal<CompareByDigits<'5', '8'>, Comparison.Lower>>;

type Comparator<A extends number, B extends number> = Equal<A, B> extends true
  ? Comparison.Equal
  : CompareByDigits<`${A}`, `${B}`>;

Test cases

They are the same as in the challenge

/* _____________ Test Cases _____________ */
import { Equal, Expect } from '@type-challenges/utils'

type cases = [
  Expect<Equal<Comparator<5, 5>, Comparison.Equal>>,
  Expect<Equal<Comparator<5, 6>, Comparison.Lower>>,
  Expect<Equal<Comparator<5, 8>, Comparison.Lower>>,
  Expect<Equal<Comparator<5, 0>, Comparison.Greater>>,
  Expect<Equal<Comparator<-5, 0>, Comparison.Lower>>,
  Expect<Equal<Comparator<0, 0>, Comparison.Equal>>,
  Expect<Equal<Comparator<0, -5>, Comparison.Greater>>,
  Expect<Equal<Comparator<5, -3>, Comparison.Greater>>,
  Expect<Equal<Comparator<5, -7>, Comparison.Greater>>,
  Expect<Equal<Comparator<-5, -7>, Comparison.Greater>>,
  Expect<Equal<Comparator<-5, -3>, Comparison.Lower>>,
  Expect<Equal<Comparator<-25, -30>, Comparison.Greater>>,
  Expect<Equal<Comparator<15, -23>, Comparison.Greater>>,
  Expect<Equal<Comparator<40, 37>, Comparison.Greater>>,
  Expect<Equal<Comparator<-36, 36>, Comparison.Lower>>,
  Expect<Equal<Comparator<27, 27>, Comparison.Equal>>,
  Expect<Equal<Comparator<-38, -38>, Comparison.Equal>>,
]

[g-plane]

@Gelio Wow, so long code! Will your solution hit TS recursive depth limitation?

[Gelio]

@Gelio Wow, so long code! Will your solution hit TS recursive depth limitation?

That was the best I could come up with that works with large integers 🙂 It depends on the number of digits, so it hits the recursive depth limit only when both numbers contain more than 3 same leading digits.

For example, numbers with the same 3 leading digits work fine:

Expect<Equal<Comparator<3809, 3805>, Comparison.Greater>>

Numbers with the same 4 leading digits hit the depth limit:

Expect<Equal<Comparator<38009, 38005>, Comparison.Greater>>