Sum

Challenge

Implement a type Sum<A, B> that summing two non-negative integers and returns the sum as a string. Numbers can be specified as a string, number, or bigint.

For example,

type T0 = Sum<2, 3>; // '5'
type T1 = Sum<"13", "21">; // '34'
type T2 = Sum<"328", 7>; // '335'
type T3 = Sum<1_000_000_000_000n, "123">; // '1000000000123'

Solution

Eine erste Idee fuer die Loesung dieses Problems waere es, zwei Arrays / Tupeln so lange mit Zahlen / String etc. zu fuellen, bis einer die Laenge von A und der andere die Laenge von B hat, und diese in einem Array zu kombinieren und hiervon ueber den Lookup-Typ ‘length’ die Laenge zu erhalten.

type Computable = string | number | bigint;

// T = 4   => [1,1,1,1]
type NumberToTuple<
  T extends Computable,
  R extends any[] = []
> = `${T}` extends `${number}`
  ? `${T}` extends `${R["length"]}`
    ? R
    : NumberToTuple<T, [...R, 1]>
  : [];

type Sum<A extends Computable, B extends Computable> = [
  ...NumberToTuple<A>,
  ...NumberToTuple<B>
]["length"] extends number
  ? `${[...NumberToTuple<A>, ...NumberToTuple<B>]["length"]}`
  : never;

Das Problem hierbei ist, dass wir bei sehr grosen Zahlen folgende Fehlermedlung erhalten: Type instantiation is excessively deep and possibly infinite. TypeScript nutzt Heuristiken, um moeligcherweise nie endende rekusrive Aufrufe einzuschraenken. Daher muessen wir eine andere Loesung waehlen.

Aus den Grundschulzeiten kennt man noch das schriftliche Addieren, wobei hier immer zwei Zahlen miteinander addiert werden, und der Rest (was groser wie 10 ist, z.B. 4 + 7 = 11 Rest 1) bei der naechten Zehnerpotenz miteingerechnet wird. Dieser Verfahren weden wir hier nun an:

type Computable = string | number | bigint;

// 4 => [1,1,1,1]
type NumberToTuple<
  T extends Computable,
  R extends any[] = []
> = `${T}` extends `${number}`
  ? `${T}` extends `${R["length"]}`
    ? R
    : NumberToTuple<T, [...R, 1]>
  : [];

type Remaind10<T extends any[]> = T extends [
  1,
  1,
  1,
  1,
  1,
  1,
  1,
  1,
  1,
  1,
  ...infer R
]
  ? {
      number: R["length"];
      count: "1";
    }
  : {
      number: T["length"];
      count: "";
    };

type Reverse<T extends string> = T extends `${infer L}${infer R}`
  ? `${Reverse<R>}${L}`
  : "";

type CalcWithRest<
  A extends Computable,
  B extends Computable,
  count extends string = ""
> = Remaind10<
  [...NumberToTuple<A>, ...NumberToTuple<B>, ...(count extends "1" ? [1] : [])]
>;
type GG = CalcWithRest<4, 5>;

type StrAdd<
  A extends string,
  B extends string,
  count extends string = "0"
> = A extends `${infer AL}${infer AR}`
  ? B extends `${infer BL}${infer BR}`
    ? `${CalcWithRest<AL, BL, count>["number"] & number}${StrAdd<
        AR,
        BR,
        CalcWithRest<AL, BL, count>["count"]
      >}`
    : `${CalcWithRest<AL, count>["number"] & number}${StrAdd<
        AR,
        "0",
        CalcWithRest<AL, count>["count"]
      >}`
  : B extends `${infer BL}${infer BR}`
  ? `${CalcWithRest<BL, count>["number"] & number}${StrAdd<
      "",
      BR,
      CalcWithRest<BL, count>["count"]
    >}`
  : count;

type Sum<A extends Computable, B extends Computable> = Reverse<
  StrAdd<Reverse<`${A}`>, Reverse<`${B}`>>
>;

References