Գնահատել նախագիծը
← Բոլոր հրապարակումները

Առաջադեմ տիպային մակարդակի թվաբանության կառուցում TypeScript-ում, մաս 2

Սա TypeScript-ում առաջադեմ "Add" և "Subtract" տիպերի կառուցման մեր արկածի երկրորդ և վերջին փուլն է։

8 րոպե
Typescriptառաջադեմ TypeScriptտիպային մակարդակի ծրագրավորումթվաբանությունգումարում

Սա առաջադեմ Add և Subtract տիպերի կառուցման մեր արկածի երկրորդ և վերջին մասն է, որոնք աշխատում են և դրական, և բացասական ամբողջ թվերի հետ՝ մինչև բացարձակապես անհեթեթ վերին սահմանը՝ 9007199254740991 (Number.MAX_SAFE_INTEGER) 😅.

Add<-123, -52>; // -175
Add<123, -52>; // 71
Add<-123, 52> // -71
Add<123456789, 9988776655>; // 10112233444
Add<9007199254740989, 2>; // 9007199254740991

Մենք արդեն կառուցել ենք MinusOne և PlusOne տիպերը, որոնք թույլ են տալիս ավելացնել և նվազեցնել ցանկացած թվային լիտերալ տիպ.

MinusOne<42> // 41
MinusOne<0> // -1

PlusOne<10> // 11
// etc.

Լուծման ակնարկ

Կսկսենք լուծումը նկարագրելով կեղծկոդով։ Դրանից հետո այն կբաժանենք ավելի փոքր ենթախնդիրների և յուրաքանչյուրը կիրականացնենք որպես տիպային մակարդակի ալգորիթմ։

Որպեսզի հեշտ լինի հետևել, եզրային դեպքերը կթողնենք մի կողմ և կկենտրոնանք երկու դրական թվերի գումարման հիմնական խնդրի վրա.

123 + 42

Քանի որ արդեն ունենք PlusOne, առաջին ակնհայտ միտքն է PlusOne-ը ռեկուրսիվ կերպով կիրառել 123-ի վրա 42 անգամ։ Դա կաշխատեր վերևի օրինակի համար, բայց TypeScript-ը ռեկուրսիվ կանչերը սահմանափակում է 1000 խորությամբ, իսկ մենք ուզում ենք գումարել 1000-ից շատ ավելի մեծ թվեր։ Մեզ պետք է ավելի խելացի մոտեցում։

Եկեք գումարմանը նայենք այլ տեսանկյունից. որևէ թվին 123 գումարելը նշանակում է երեք անգամ գումարել 1, հետո երկու անգամ գումարել 10 և վերջում մեկ անգամ գումարել 100։ Ընդհանուր առմամբ, յուրաքանչյուր թիվ կարելի է գրել որպես 10-ի աստիճանների գումար, օրինակ.

|---------------------------------------|
| |---------------|                     |
| |               |                     |
1234 = 4 * 10^0 + 3 * 10^1 + 2 * 10^2 + 1 * 10^3
 | |---|                     |          
 |                           |
 |---------------------------|

Թվերը այսպես տրոհելը թույլ է տալիս գումարել կամայականորեն մեծ թվեր (քանի դեռ դրանք տեղավորվում են JavaScript-ի թվերի տիրույթում)՝ առանց TypeScript-ի ռեկուրսիայի սահմանին հասնելու։ Շատ մոտավոր հիմնավորումը հետևյալն է. MAX_SAFE_INTEGER-ն ունի քսանից մի քանի ավելի թվանշան, ասենք 30, որը սահմանափակում է «արտաքին ցիկլը»։ Ներքին ցիկլը սահմանափակված է 10-ով, քանի որ կա 10 թվանշան։ Այսպիսով, նույնիսկ ամենավատ դեպքում չպետք է գերազանցենք 30 * 10 = 300 (< 1000) ներդրված ռեկուրսիվ կանչերը։

Լուծման ուրվագիծը ձեռքի տակ ունենալով՝ եկեք այն կառուցենք քայլ առ քայլ։

Ստեղծել 10-ի k աստիճանը

Կսկսենք ավելի հեշտ ենթախնդրից։ Ահա 10-ի առաջին մի քանի աստիճանները.

10^0 = 1
10^1 = 10
10^2 = 100
10^3 = 1000
...

Սա մեզ ասում է, որ 10-ը k աստիճանով, բնական k-ի համար, պարզապես 1 է, որին հաջորդում են k զրոներ.

type Create10ToPower<Power extends number> 
    = ParseInt<`1${Repeat<"0", Power>}`>;

Դեկլարատիվ ծրագրավորումը հիանալի չէ՞։ Սակայն մենք դեռ չունենք Repeat ֆունկցիայի սահմանումը, ուստի եկեք գրենք այն.

type Repeat<
  T extends string,
  n extends number,
  acc extends string = ""
> = n extends 0 ? acc : Repeat<T, MinusOne<n>, `${acc}${T}`>;

Սկսում ենք դատարկ կուտակիչով (acc), և քանի դեռ n-ը մեծ է 0-ից, Repeat-ը կանչում ենք ռեկուրսիվ՝ նվազեցրած n-ով և կուտակիչին կցված T-ով (կրկնվող տողով)։ Երբ n-ը հասնում է 0-ի, պարզապես վերադարձնում ենք կուտակիչը։ Նկատեք, որ MinusOne-ն արդեն օգտակար է ապացուցվում նույնիսկ օժանդակ տիպերի ներսում։

Այնքան էլ դժվար չէ, չէ՞։ Հուսով եմ՝ սա ձեզ տաքացրեց, որովհետև կամայական թվին 10^k գումարելը բոլորովին այլ պատմություն է 😅

Կամայական թվին 10^k գումարելը

n թվին 10^k գումարելը պահանջում է երեք դեպքի մշակում.

  1. k-ն 0 է
  2. 10^k > n
  3. 10^k <= n

Երբ k-ն 0 է
Այս դեպքը աննշան է. 10^0-ն հավասար է 1-ի, ուստի պարզապես վերադարձնում ենք PlusOne<n>։

Երբ 10^k > n
Այս դեպքը նույնպես բավական պարզ է, ահա պատկերացումը.

1000000
+   123
-------
1000123

Թող d-ն նշանակի n-ի թվանշանների քանակը։ Այդ դեպքում 10^k + n-ը ներկայացնող տողը պարզապես 10^k-ն է՝ վերջին d զրոները փոխարինված n-ով։ Այլ կերպ ասած՝ 1, հետո k - d զրո, հետո n-ի տողային տեսքը.

1 000 000 <- 6 0s, so k is 6
+     123 <- 3 digits, so d is 3
---------
1 000 123
  ^^^ ^^^
  k-d  d

Որպեսզի իրականացման մեջ հանումի կարիք չունենանք, կընտրենք առաջին ձևակերպումը (վերջին d զրոները փոխարինված n-ով)։ Դա նշանակում է 10^k-ի վերջին d թվանշանները հեռացնել և դրանց տեղը դնել n-ը.

type AddBiggerPowerOf10ToN<
  PowerOf10 extends string,
  N extends string
> = `${ReverseString<Drop<ReverseString<PowerOf10>, LengthOfString<N>>>}${N}`;

Դրա համար մեզ պետք են երկու օժանդակ տիպ՝ LengthOfString և Drop.

export type LengthOfString<
  S extends string,
  len extends number = 0
> = S extends `${infer _}${infer rest}`
  ? LengthOfString<rest, PlusOne<len>>
  : len;

type Drop<S extends string, N extends number> = N extends 0
  ? S
  : S extends `${infer _}${infer Rest}`
  ? Drop<Rest, MinusOne<N>>
  : S;

Երբ 10^k <= n
Այս դեպքի իրականացումն ավելի զվարճալի է։ Կրկին մի քանի օրինակ կօգնեն պատկերացնել այն.

123 456         
+   100
------         
123 556

1234   56         
+  1   00
------         
1235   56

Թող m-ը լինի այն թիվը, որ ստանում ենք n-ից վերջին k թվանշանները հեռացնելով։ Վերևի պատկերացումները ցույց են տալիս, որ արդյունքը պարզապես PlusOne<m> է՝ n-ի վերջին երկու թվանշաններով կցված.

type AddSmallerPowerOf10ToN<Power extends number, N extends number> = ParseInt<
  ReverseString<`${Take<ReverseString<`${N}`>, Power>}${InternalPlusOne<
    Drop<ReverseString<`${N}`>, Power>
  >}`>
>;

Թվից տող ավելորդ փոխակերպումներից խուսափելու համար մենք կրկին օգտագործում ենք InternalPlusOne օժանդակ տիպը։

Greater-ի իրականացումը

Մնում է մեկ ենթախնդիր. ինչպե՞ս համեմատել 10^k-ն n-ի հետ՝ պարզելու համար, թե 10^k-ն մեծ է, փոքր է թե հավասար է n-ին։ Դրա համար կգրենք Greater<A extends number, B extends number> տիպը, որը հավասար է true, երբ A-ն մեծ է B-ից։

Այս պահին հավանաբար չեք զարմանա, որ տողերը կրկին մեր գործիքը կլինեն 😅։ Ահա պլանը.

  • Երկու թվերը դիտարկել որպես տողեր։
  • Երբ A-ն ավելի կարճ է, քան B-ն, վերադարձնել false։
  • Երբ B-ն ավելի կարճ է, քան A-ն, վերադարձնել true։
  • Երբ երկուսն էլ նույն երկարությունն ունեն.
    • Ձախից սկսելով՝ գտնել առաջին դիրքը, որտեղ A-ն և B-ն տարբերվում են՝ a և b թվանշաններով։
    • Երբ a > b, վերադարձնել true։
    • Երբ b > a, վերադարձնել false։

isShorter տիպը բավական պարզ է.

type isShorter<
  A extends string,
  B extends String
> = A extends `${infer Head}${infer Rest}`
  ? B extends `${infer Head2}${infer Rest2}`
    ? isShorter<Rest, Rest2>
    : false
  : B extends `${infer Head2}${infer Rest2}`
  ? true
  : false;

Նույն երկարության երկու թվերի համեմատությունն ավելի բարդ է։ Մեր բարձր մակարդակի ալգորիթմի համաձայն՝ մենք պետք է կարողանանք համեմատել թվանշանների ցանկացած զույգ։ Ես սա լուծեցի համեմատման աղյուսակով.

type GTTable = [
  ["=", "<", "<", "<", "<", "<", "<", "<", "<", "<"],
  [">", "=", "<", "<", "<", "<", "<", "<", "<", "<"],
  [">", ">", "=", "<", "<", "<", "<", "<", "<", "<"],
  [">", ">", ">", "=", "<", "<", "<", "<", "<", "<"],
  [">", ">", ">", ">", "=", "<", "<", "<", "<", "<"],
  [">", ">", ">", ">", ">", "=", "<", "<", "<", "<"],
  [">", ">", ">", ">", ">", ">", "=", "<", "<", "<"],
  [">", ">", ">", ">", ">", ">", ">", "=", "<", "<"],
  [">", ">", ">", ">", ">", ">", ">", ">", "=", "<"],
  [">", ">", ">", ">", ">", ">", ">", ">", ">", "="]
];

type GTSameLength<
  A extends string,
  B extends string
> = A extends `${infer DigitA extends number}${infer RestA}`
  ? B extends `${infer DigitB extends number}${infer RestB}`
    ? GTTable[DigitA][DigitB] extends ">"
      ? true
      : GTTable[DigitA][DigitB] extends "<"
      ? false
      : GTSameLength<RestA, RestB>
    : false
  : false;

Ցանկացած a և b թվանշանների համար GTTable[a][b]-ին նայելը տալիս է “>”, “=” կամ “<”։

Ամեն ինչ համադրելով՝ ստանում ենք.

export type Greater<A extends number, B extends number> = InternalGT<
  `${A}`,
  `${B}`
>;

type InternalGT<A extends string, B extends string> = isShorter<
  A,
  B
> extends true
  ? false
  : isShorter<B, A> extends true
  ? true
  : GTSameLength<A, B>;

Plus10ToPower-ի իրականացումը

Այժմ վերևի տիպերը կարելի է միավորել մեկ Plus10ToPower տիպի մեջ, որը ցանկացած N թվին գումարում է 10-ը Power աստիճանով։

type Plus10ToPower<N extends number, Power extends number> = Power extends 0
  ? PlusOne<N>
  : Greater<Create10ToPower<Power>, N> extends true
  ? ParseInt<AddBiggerPowerOf10ToN<`${Create10ToPower<Power>}`, `${N}`>>
  : AddSmallerPowerOf10ToN<Power, N>;

Գումարման ալգորիթմի համար ամեն ինչ պատրաստ է։ Կարճ հիշեցում, թե ինչպես է այն աշխատում.

A-ին B գումարելու համար մենք անցնում ենք B թվի շրջված տեսքի (այսինքն՝ հետ գնալով) յուրաքանչյուր d թվանշանով և նրա i ինդեքսով և հաշվում sum += Plus10ToPower<A, i> * d։ d-ով բազմապատկելու փոխարեն մենք ռեկուրսիվ կերպով կգումարենք Plus10ToPower<A, i>-ը d անգամ։ Փոքր օժանդակ ֆունկցիան սա հեշտացնում է.

type AddPowerOf10NTimes<
  sum extends number,
  power extends number,
  N extends number
> = N extends 0
  ? sum
  : AddPowerOf10NTimes<Plus10ToPower<sum, power>, power, MinusOne<N>>;

Եվ ահա ամեն ինչը միասին.

type Adder<
  sum extends number,
  reversedDigits,
  currentPower extends number = 0
> = reversedDigits extends `${infer d extends number}${infer rest}`
  ? Adder<AddPowerOf10NTimes<sum, currentPower, d>, rest, PlusOne<currentPower>>
  : sum;

type res = Adder<50, "24">; // 92, bacause "24" is reversed "42".

Շրջված տողերի անհարմարությունը թաքցնելու համար սահմանենք SimpleAdd.

type SimpleAdd<A extends number, B extends number> 
 = Adder<A, ReverseString<`${B}`>>;

type res1 = SimpleAdd<42, 50>; // 92

Ինչո՞ւ SimpleAdd անունը, այլ ոչ թե պարզապես Add։ Ինչպես հիշում եք, մինչ այժմ մենք աջակցում ենք միայն երկու դրական թվերի գումարմանը։ SimpleAdd-ը բացասական թվերի հետ աշխատեցնելը հիանալի վարժություն է, և ես այն թողնում եմ ձեզ որպես մարտահրավեր։

Սկսելուն օգնելու համար ահա անհրաժեշտ քայլերի ուրվագիծը.

  • Գրեք Subtract տիպը՝ ընդօրինակելով Adder-ը։

  • Գրեք isNonNegative և Abs տիպերը։

  • Գրեք իրական Add-ը՝ ըստ այս կեղծկոդի.

    Add<a, b> =
    if a < 0 and b < 0 then `-{SimpleAdd<Abs<a>, Abs<b>>}`
    if a < 0 and b > 0 then Subtract<b, Abs<a>>
    if < > 0 and b > 0 then Subtract<a, Abs<b>>
    if a > 0 and b > 0 then SimpleAdd<a, b>

Շատ շնորհակալություն ընթերցելու համար։ Եթե հասել եք մինչև այստեղ, ուրախ կլինեմ կարդալ այս հոդվածի մասին ձեր կարծիքը մեկնաբանություններում։ Եվ ինչպես միշտ, եթե գրառումը ձեզ դուր եկավ, մտածեք մեր տեղեկագրին բաժանորդագրվելու և այն ձեր ընկերներին ու գործընկերներին փոխանցելու մասին։