Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

2257 - MinusOne with 2 versions and explanatations #19437

Open
zhaoyao91 opened this issue Nov 18, 2022 · 1 comment
Open

2257 - MinusOne with 2 versions and explanatations #19437

zhaoyao91 opened this issue Nov 18, 2022 · 1 comment
Labels
2257 answer Share answers/solutions to a question en in English

Comments

@zhaoyao91
Copy link

zhaoyao91 commented Nov 18, 2022

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.

@zhaoyao91 zhaoyao91 added answer Share answers/solutions to a question en in English labels Nov 18, 2022
@github-actions github-actions bot added the 2257 label Nov 18, 2022
@zhaoyao91 zhaoyao91 changed the title 2257 - MinusOne 2257 - MinusOne with 2 versions and explanatations Nov 18, 2022
@YqxLzx
Copy link

YqxLzx commented Nov 22, 2022

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
2257 answer Share answers/solutions to a question en in English
Projects
None yet
Development

No branches or pull requests

2 participants