Sum

Type-level addition that does not fall over at a trillion.

Sum<A, B> adds two non-negative integers and returns the result as a string. Either side may arrive as a string, a number or a bigint, in any combination.

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'

The usual type-level arithmetic trick, building a tuple of the right length and reading its ['length'], is no help here. Nothing recursive will ever count to a trillion. What does survive is the method you learned at school: work through the digits from the right, one column at a time, carrying the ten.

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'

/* _____________ Your Code Here _____________ */

type Sum<
  A extends string | number | bigint,
  B extends string | number | bigint,
> = string

/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '../helpers'

type cases = [
  Expect<Equal<Sum<2, 3>, '5'>>,
  Expect<Equal<Sum<'13', '21'>, '34'>>,
  Expect<Equal<Sum<'328', 7>, '335'>>,
  Expect<Equal<Sum<1_000_000_000_000n, '123'>, '1000000000123'>>,
  Expect<Equal<Sum<9999, 1>, '10000'>>,
  Expect<Equal<Sum<4325234, '39532'>, '4364766'>>,
  Expect<Equal<Sum<728, 0>, '728'>>,
  Expect<Equal<Sum<'0', 213>, '213'>>

Detailed Explanation

The solution in full:

type Digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
 
type Ones = {
  '0': []
  '1': [0]
  '2': [0, 0]
  '3': [0, 0, 0]
  '4': [0, 0, 0, 0]
  '5': [0, 0, 0, 0, 0]
  '6': [0, 0, 0, 0, 0, 0]
  '7': [0, 0, 0, 0, 0, 0, 0]
  '8': [0, 0, 0, 0, 0, 0, 0, 0]
  '9': [0, 0, 0, 0, 0, 0, 0, 0, 0]
}
 
type ColumnTotal<X extends Digit, Y extends Digit, C extends Digit> = [
  ...Ones[X],
  ...Ones[Y],
  ...Ones[C],
]['length']
 
type WrittenDown = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
                    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
 
type CarriedOver = ['0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
                    '1', '1', '1', '1', '1', '1', '1', '1', '1', '1']
 
type ColumnIndex = Extract<keyof WrittenDown, number>
 
type Write<X extends Digit, Y extends Digit, C extends Digit> =
  ColumnTotal<X, Y, C> extends infer N extends ColumnIndex
    ? WrittenDown[N]
    : never
 
type Carry<X extends Digit, Y extends Digit, C extends Digit> =
  ColumnTotal<X, Y, C> extends infer N extends ColumnIndex
    ? CarriedOver[N]
    : never
 
type Reverse<S extends string> = S extends `${infer Head}${infer Rest}`
  ? `${Reverse<Rest>}${Head}`
  : ''
 
type AddColumns<
  A extends string,
  B extends string,
  C extends Digit,
  Acc extends string,
> = A extends `${infer X extends Digit}${infer ARest}`
  ? B extends `${infer Y extends Digit}${infer BRest}`
    ? AddColumns<ARest, BRest, Carry<X, Y, C>, `${Write<X, Y, C>}${Acc}`>
    : AddColumns<A, '0', C, Acc>
  : B extends ''
    ? C extends '1'
      ? `1${Acc}`
      : Acc
    : AddColumns<'0', B, C, Acc>
 
type Sum<
  A extends string | number | bigint,
  B extends string | number | bigint,
> = AddColumns<Reverse<`${A}`>, Reverse<`${B}`>, '0', ''>

Two pieces: a single column of addition, and a walk that threads the carry from right to left.

Adding one column

A column is three digits, one from each operand plus the incoming carry, so the total is at most 9 + 9 + 1. Ones turns a digit character into a tuple of that length, and spreading three of them into one tuple lets ['length'] do the arithmetic. WrittenDown then maps that total to the digit you write under the line and CarriedOver to the digit you carry, both indexed by the same 20 positions:

// ColumnTotal<'8', '7', '0'> is 15
// Write<'8', '7', '0'> is '5',  Carry<'8', '7', '0'> is '1'
// Write<'9', '9', '1'> is '9',  Carry<'9', '9', '1'> is '1'

The extends infer N extends ColumnIndex step is what makes the lookup legal. Inside a generic body TypeScript only knows that ColumnTotal<X, Y, C> is some number, and a bare number cannot index a 20-element tuple. Re-inferring the result under a constraint gives the compiler that guarantee up front, while the value still resolves to an exact position once X, Y and C are known. ColumnIndex is Extract<keyof WrittenDown, number>, which keeps 0 through 19 and drops 'length' and the array methods that keyof also reports on a tuple.

Walking the columns from the right

Addition starts at the least significant digit, but template literal patterns only peel characters off the front, so both numbers are reversed first. `${A}` handles the three input forms in one step: a string, a number and a bigint all interpolate to the same digit string.

AddColumns then takes one character from each side with `${infer X extends Digit}${infer ARest}`. Two adjacent infer placeholders make the first match exactly one character, and the extends Digit constraint is what lets X be handed to Write and Carry.

The answer grows in Acc, and each new digit is prepended. The digit produced at step k is more significant than everything computed before it, so `${Write<X, Y, C>}${Acc}` builds the result in reading order and no second reversal is needed:

// Sum<9999, 1> walks '9999' against '1'
//   9 + 1 + 0 = 10  write '0', carry '1'   Acc = '0'
//   9 + 0 + 1 = 10  write '0', carry '1'   Acc = '00'
//   9 + 0 + 1 = 10  write '0', carry '1'   Acc = '000'
//   9 + 0 + 1 = 10  write '0', carry '1'   Acc = '0000'
//   both spent, carry is '1'               result '10000'

Running out of digits

The two numbers rarely have the same length, so one side empties first. Rather than padding up front, the exhausted side is refilled one zero at a time: AddColumns<A, '0', C, Acc> when B is gone, and AddColumns<'0', B, C, Acc> when A is gone.

That looks like it could spin forever, since one of the arguments is passed through unchanged. It cannot. The '0' is consumed by the very next step, which puts the same branch back with the other string one character shorter. Every two steps therefore remove a character, and the only exit is B extends '' reached with A empty too. The work is proportional to the number of digits, not to the size of the number, which is why thirteen digits cost no more than a shallow recursion.

Edge cases the tests cover

• Sum<1_000_000_000_000n, '123'>: a bigint literal interpolates into a template literal type without its n suffix, so `${1_000_000_000_000n}` is '1000000000000'. Thirteen columns, and nothing counts to a trillion.
• Sum<9999, 1> is '10000': the carry out of the last column has nowhere to go, and the C extends '1' branch prepends it once both strings are spent.
• Sum<0, '0'> is '0': one column totalling zero writes a '0', so the empty accumulator never reaches the surface.
• Sum<728, 0> and Sum<'0', 213>: the refill only ever feeds zeros into the shorter side, and the longer operand's leading digit is non-zero, so the answer cannot pick up a leading zero.
• Sum<'328', 7> mixes a string with a number, and Sum<4325234, '39532'> mixes lengths and carries. Both are stringified before anything else happens, so the accepted input forms meet in the same shape and the rest of the type never has to care.

Once the numbers are strings and the digits are tuple lengths, the compiler is doing exactly what a pencil does, one column at a time.