Writing in the front

This article executes typescript in version 4.6.2Copy the code

background

Fibonacci in typescript I thought I was done with Fibonacci in typescript, but it turns out I didn’t have enough test examples to work on 12 computers!

The +1 operation is to push the array and get the length. All the addition is achieved by the recursive +1 operation.

Refactoring!!!!

refactoring

Think about it. How do I refactor? Fibonacci itself needs recursion, this can not be skipped, it seems that the focus of optimization is addition. Knock on the blackboard, the point is:

Refactoring additionCopy the code

The +1 operation is optimized for addition, because the addition mechanism is the sum of bits, and if there is a carry, it carries

Refactor the +1 operation

It’s pretty simple, actually, to do the +1 operation for the units digit, which is the basis of addition

type G_ADD_ONE<N extends string> = N extends '0' ? '1' :
    N extends '1' ? '2' :
    N extends '2' ? '3' :
    N extends '3' ? '4' :
    N extends '4' ? '5' :
    N extends '5' ? '6' :
    N extends '6' ? '7' :
    N extends '7' ? '8' :
    N extends '8' ? '9' :
    N extends '9' ? '10' :
    ' ';
Copy the code

The rule of addition is to add from the units digit, carry if there is a carry, so you need to recursively get a single number

// Get the trailing number
type GetEnd<N extends string> = N extends simpleNum ? N :
    N extends `The ${string}${infer P}` ? GetEnd<P> : ' ';

// Get the digits beyond the end
type GetEndPre<N extends string> = N extends simpleNum ? ' ' :
    N extends `${infer P}${GetEnd<N>}` ? P : ' ';

type end1 = GetEnd<'123'>; / / 3
type end2 = GetEndPre<'123'>; / / 12
Copy the code

The logic of the +1 operation is:

We can do any number of +1 operations after we get the digit bitsCopy the code

5+6 requires 11 +1 operations. Now, to do any +1, you only need to recurse the length of the number

/ / single digits
type simpleNum = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';

type ADD_ONE<N extends string> = N extends simpleNum ? G_ADD_ONE<N> :
    GetEnd<N> extends '9' ? `${ADD_ONE<GetEndPre<N>>}0 ` :
    `${GetEndPre<N>}${G_ADD_ONE<GetEnd<N>>}`;

type addOne0 = ADD_ONE<'7'>; / / 8
type addOne1 = ADD_ONE<'99'>; / / 100
type addOne2 = ADD_ONE<'299'>; / / 300
type addOne3 = ADD_ONE<'159'>; / / 160
Copy the code

Ok, so now the refactoring +1 is done

Refactoring addition

Now that the +1 operation is done, shouldn’t the +1 recursion be enough? Yes, but we’re still facing n recursions, so avoid recursion here! How to do this, like implementing the +1 operation, implementing the 99 addition table!

type CD_SIMPLE_ADD<X extends string, Y extends string> =  X extends ' ' ? Y :
    Y extends ' ' ? X :
    X extends '0' ? Y :
    Y extends '0' ? X :
    X extends '1' ? G_ADD_ONE<Y> :
    Y extends '1' ? G_ADD_ONE<X> :
    X extends '2' ?
        Y extends '2' ? '4' :
        Y extends '3' ? '5' :
        Y extends '4' ? '6' :
        Y extends '5' ? '7' :
        Y extends '6' ? '8' :
        Y extends '7' ? '9' :
        Y extends '8' ? '10' :
        Y extends '9' ? '11' :
        never :
    X extends '3' ?
        Y extends '2' ? '5' :
        Y extends '3' ? '6' :
        Y extends '4' ? '7' :
        Y extends '5' ? '8' :
        Y extends '6' ? '9' :
        Y extends '7' ? '10' :
        Y extends '8' ? '11' :
        Y extends '9' ? '12' :
        never :
    X extends '4' ?
        Y extends '2' ? '6' :
        Y extends '3' ? '7' :
        Y extends '4' ? '8' :
        Y extends '5' ? '9' :
        Y extends '6' ? '10' :
        Y extends '7' ? '11' :
        Y extends '8' ? '12' :
        Y extends '9' ? '13' :
        never :
    X extends '5' ?
        Y extends '2' ? '7' :
        Y extends '3' ? '8' :
        Y extends '4' ? '9' :
        Y extends '5' ? '10' :
        Y extends '6' ? '11' :
        Y extends '7' ? '12' :
        Y extends '8' ? '13' :
        Y extends '9' ? '14' :
        never :
    X extends '6' ?
        Y extends '2' ? '8' :
        Y extends '3' ? '9' :
        Y extends '4' ? '10' :
        Y extends '5' ? '11' :
        Y extends '6' ? '12' :
        Y extends '7' ? '13' :
        Y extends '8' ? '14' :
        Y extends '9' ? '15' :
        never :
    X extends '7' ?
        Y extends '2' ? '9' :
        Y extends '3' ? '10' :
        Y extends '4' ? '11' :
        Y extends '5' ? '12' :
        Y extends '6' ? '13' :
        Y extends '7' ? '14' :
        Y extends '8' ? '15' :
        Y extends '9' ? '16' :
        never :
    X extends '8' ?
        Y extends '2' ? '10' :
        Y extends '3' ? '11' :
        Y extends '4' ? '12' :
        Y extends '5' ? '13' :
        Y extends '6' ? '14' :
        Y extends '7' ? '15' :
        Y extends '8' ? '16' :
        Y extends '9' ? '17' :
        never :
    X extends '9' ?
        Y extends '2' ? '11' :
        Y extends '3' ? '12' :
        Y extends '4' ? '13' :
        Y extends '5' ? '14' :
        Y extends '6' ? '15' :
        Y extends '7' ? '16' :
        Y extends '8' ? '17' :
        Y extends '9' ? '18' :
    never : never;
Copy the code

The logic of addition is:

Also according to the length of the recursive number to achieve the addition of any number of counterpointsCopy the code
type ADD_Check<X extends string, Y extends string> = X extends simpleNum ?
    Y extends simpleNum ?
    CD_SIMPLE_ADD<X, Y> : ADD_ALL<X, Y> : ADD_ALL<X, Y>;

type ADD_ALL<
    X extends string,
    Y extends string.// Save the result
    Z extends string = ' '.// Whether to carry, '1' is carried, '0' is not carried
    pre extends string = '0'.// Calculate the new round value
    data extends string = CD_SIMPLE_ADD<GetEnd<X>, GetEnd<Y>>,
    // The new round of values + carry
    preData extends string = ADD_Check<data, pre>,
    // To export when x or y is empty, ['data']
    Q extends string = `${X}${Y}`> = {['loop']: ADD_ALL<
                X extends ' ' ? ' ' : GetEndPre<X>,
                Y extends ' ' ? ' ' : GetEndPre<Y>,
                preData extends simpleNum ?
                    `${preData}${Z}` :
                    `${GetEnd<preData>}${Z}`,
                preData extends simpleNum ? '0' : '1'
            >;
    ['data'] :`${ADD_Check<Q, pre>}${Z}`;
    ['result']: pre extends '1' ? ` 1${Z}`: Z;
}[X extends ' ' ? Y extends ' ' ? 'result' : 'data' : 'loop'];

type addall1 = ADD_Check<'111'.'999'>; / / 1110
type addall2 = ADD_Check<'555'.'445'>; / / 1000
type addall3 = ADD_Check<'1123'.'456'>; / / 1579
Copy the code

Fibonacci calculation

Add has been refactored, so recursive addition is ready to write Fibonacci!

type FIB2<
    T extends string,
    A extends string = '0',
    B extends string = '1',
    N extends string = '1'
> = T extends '0' | '1' ? T :
    {
        ['loop']: FIB2<T, B, ADD_Check<A, B>, ADD_ONE<N>>;
        ['result']: B;
}[T extends N ? 'result' : 'loop'];

type FIv0 = FIB2<'0'> / / 0
type FIv1 = FIB2<'1'>; / / 1
type FIv2 = FIB2<'2'>; / / 1
type FIv3 = FIB2<'3'>; / / 2
type FIv4 = FIB2<'4'>; / / 3
type FIv5 = FIB2<'5'>; / / 5
type FIv6 = FIB2<'6'>; / / 8
type FIv7 = FIB2<'7'>; / / 13
type FIv8 = FIB2<'8'>; / / 21
type FIv9 = FIB2<'9'>; / / 34
type FIv10 = FIB2<'10'>; / / 55
type FIv11 = FIB2<'11'>; / / 89
type FIv12 = FIB2<'12'>; / / 144
type FIv22 = FIB2<'22'>; / / 17711
type FIv23 = FIB2<'23'>; / / 28657
type FIv24 = FIB2<'24'>; / / 46368
type FIv25 = FIB2<'25'>; / / 75025
type FIv26 = FIB2<'26'>; / / 121393
type FIv27 = FIB2<'27'>; / / 196418
type FIv28 = FIB2<'28'>; / / 317811
type FIv33 = FIB2<'33'>; / / 3524578
type FIv42 = FIB2<The '42'>; / / 267914296
Copy the code

Some people may ask, why does not give an example to the 42nd place, because the computer strikes again to the 43rd place!

Is really a headache ah, this problem to stay next time optimization ~