2257 - MinusOne with 2 versions and explanatations

[zhaoyao91]

Interesting challenge.

中文笔记：https://juejin.cn/post/7167664060547203108/

Short Version with Error ❌

type MinusOne<T extends number, Tuple extends unknown[] = []> =
  T extends 0
    ? -1
    : [unknown, ...Tuple]['length'] extends T
      ? Tuple['length']
      : MinusOne<T, [unknown, ...Tuple]>

This version passes all cases but the Expect<Equal<MinusOne<1101>, 1100>>. Though it's a good start to reason.

We increase the tuple items one by one to check if the length matches. When it does, we returns it's length.

It is tail-recursive indeed, so it passes the test for 50 items, but it fails the test for 1101 items, since there is also a limit of 1000 for tail-recursive case.

I noticed some anwser uses 0 extends 1 to bypass this limitation. It says it's for tail-recursive optimization, but it's not indeed, it's just a hack or bug for now, so I'll not consider this way for the moment.

We could try to increase the steps in each recursion to reduce the times of recursion.

Short Version

With the hint above, I made the following enhanced solution:

type MinusOne<T extends number, Tuple extends unknown[] = []> =
  T extends 0
    ? -1
    : [unknown, unknown, ...Tuple]['length'] extends T
      ? [unknown, ...Tuple]['length']
      : [unknown, ...Tuple]['length'] extends T
        ? Tuple['length']
        : MinusOne<T, [unknown, unknown, ...Tuple]>

It just checks and increases two items instead one in each recursion, so to compute 1101, now it only needs 1101/2=551 recursions, which is less than 1000 limititation.

Long Version

Think it further, the step of <2> is hard coded into the solution. Can we parameterize it so we can easily change it to the max limitation of the typescript compiler without writing 999 extra lines of hard code?

The solution below is just for this purpose.

// normal tuple of given size with linear complexity
type Tuple<L extends number, T extends unknown[] = []> = T["length"] extends L
  ? T
  : Tuple<L, [...T, unknown]>;

// find the tuple of given size between From and To tuples
// if not found, return never
type FromToTuple<L extends number, From extends unknown[] = [], To extends unknown[] = []> = From['length'] extends L
  ? From
  : From['length'] extends To['length']
    ? never
    : FromToTuple<L, [unknown, ...From], To>

// prepare a tuple as increament of each recursion
type TupleMax = Tuple<999>

// build a tuple of given size
// it use a large step in each recursion, so it can reach the target with less recursions
type SuperTuple<L extends number, C extends unknown[] = [], P extends unknown[] = []> = C["length"] extends L
  ? C
  : FromToTuple<L, P, C> extends never
    ? SuperTuple<L, [...TupleMax, ...C], C>
    : FromToTuple<L, P, C>

// this is just a middle abstraction to make the final algorithm more clear
type Minus<A extends number, B extends number> = SuperTuple<A> extends [ ...SuperTuple<B>, ... infer R extends unknown[]] ? R['length'] : never

type MinusOne<T extends number> =
  T extends 0
    ? -1
    : Minus<T, 1>

Other idea

The core idea of my solutions and similar solutions are to count items in tuple. There is another branch of idea for this challenge. Look at this issue: #2586

The core idea of that is to map a single number literal to a tuple of size of that number, and multiple it 10 times to match the level of the number.

It's more effective and not that difficult to understand. What a colorful world.

More, I found this issue: #13507 it is the most fast and supports the biggest number.

[YqxLzx]

good boy ! i got you technique , by the way i see your comments all the time lately, very helpful