Universal Base Conversion

Convert<N, M, S> reads the string S as a number written in base N and returns the same number written in base M. Both bases are integers from 2 to 16, and bases above 10 use the lowercase letters a through f, so '3e8' in base 16 is 1000 in base 10.

type a = Convert<10, 2, '255'> // expected to be '11111111'
type b = Convert<16, 10, '3e8'> // expected to be '1000'

The generalization is what makes this one hard. A fixed pair of bases lets you precompute a lookup table, the way DecimalToBinary keys twenty half-steps by carry + digit. Here the bases arrive as type parameters, so every multiplication and division has to be computed rather than looked up.

type a = Convert<10, 2, '255'> // expected to be '11111111'
type b = Convert<16, 10, '3e8'> // expected to be '1000'

/* _____________ Your Code Here _____________ */

type Convert<N extends number, M extends number, S extends string> = any

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

type cases = [
  Expect<Equal<Convert<10, 9, '10'>, '11'>>,
  Expect<Equal<Convert<3, 2, '21'>, '111'>>,
  Expect<Equal<Convert<5, 10, '100'>, '25'>>,
  Expect<Equal<Convert<10, 2, '128'>, '10000000'>>,
  Expect<Equal<Convert<10, 2, '255'>, '11111111'>>,
  Expect<Equal<Convert<10, 16, '256'>, '100'>>,
  Expect<Equal<Convert<10, 16, '1000'>, '3e8'>>,
  Expect<Equal<Convert<16, 10,

Detailed Explanation

The solution in full:

type Digits = ['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f']
 
type Tuple<N extends number, Acc extends 1[] = []> = Acc['length'] extends N
  ? Acc
  : Tuple<N, [...Acc, 1]>
 
type DigitValue<C extends string, Rest extends string[] = Digits, Acc extends 1[] = []> =
  Rest extends [infer Head, ...infer Tail extends string[]]
    ? Head extends C ? Acc : DigitValue<C, Tail, [...Acc, 1]>
    : never
 
type Repeat<T extends 1[], Times extends 1[], Acc extends 1[] = []> =
  Times extends [1, ...infer Rest extends 1[]] ? Repeat<T, Rest, [...Acc, ...T]> : Acc
 
type Sub<A extends 1[], B extends 1[]> =
  B extends [1, ...infer BTail extends 1[]]
    ? A extends [1, ...infer ATail extends 1[]] ? Sub<ATail, BTail> : false
    : A
 
type DivMod<T extends 1[], D extends 1[], Q extends 1[] = []> =
  Sub<T, D> extends infer R extends 1[] ? DivMod<R, D, [...Q, 1]> : [Q, T]
 
type Spill<Carry extends 1[], To extends 1[], Out extends 1[][]> = Carry extends []
  ? Out
  : DivMod<Carry, To> extends [infer Q extends 1[], infer R extends 1[]]
    ? Spill<Q, To, [...Out, R]>
    : never
 
type Step<Acc extends 1[][], From extends 1[], To extends 1[], Carry extends 1[], Out extends 1[][] = []> =
  Acc extends [infer D extends 1[], ...infer Rest extends 1[][]]
    ? DivMod<[...Repeat<D, From>, ...Carry], To> extends [infer Q extends 1[], infer R extends 1[]]
      ? Step<Rest, From, To, Q, [...Out, R]>
      : never
    : Spill<Carry, To, Out>
 
type Horner<S extends string, From extends 1[], To extends 1[], Acc extends 1[][] = []> =
  S extends `${infer C}${infer Rest}`
    ? Horner<Rest, From, To, Step<Acc, From, To, DigitValue<C>>>
    : Acc
 
type Render<Acc extends 1[][], Out extends string = ''> =
  Acc extends [infer D extends 1[], ...infer Rest extends 1[][]]
    ? Render<Rest, `${Digits[D['length']]}${Out}`>
    : Out extends '' ? '0' : Out
 
type Convert<N extends number, M extends number, S extends string> =
  Render<Horner<S, Tuple<N>, Tuple<M>>>

Horner instead of two conversions

The obvious plan, parse base N into a number and then print that number in base M, needs a number in the middle, and the type system has no numbers you can add. Horner's method skips the middle entirely. Read the input left to right and keep a running total:

// '3e8' in base 16, running total kept in base 10
// digit '3':    0 * 16 + 3  = 3
// digit 'e':    3 * 16 + 14 = 62
// digit '8':   62 * 16 + 8  = 1000

The running total never leaves base M. It lives as 1[][], an array of digits where each digit is a tuple whose length is its value, stored least significant first. So 62 in base 10 is [[1,1], [1,1,1,1,1,1]]: a 2 followed by a 6, read right to left.

Counting with tuple lengths

Tuples are the only thing in the type system that can be added. Tuple<16> builds a tuple of sixteen 1s, [...A, ...B] concatenates, which is addition, and Repeat<T, Times> appends T once per element of Times, which is multiplication: Repeat<[1, 1, 1], Tuple<4>> has length 12.

Subtraction is the mirror image. Sub<A, B> peels one element off each side until B runs out and returns what is left of A. If A runs out first the result is false, and that failure signal is the whole trick behind division:

// Sub<Tuple<7>, Tuple<2>> is a tuple of length 5
// Sub<Tuple<1>, Tuple<2>> is false

DivMod<T, D> subtracts D from T as often as it fits, counting the subtractions in Q, so DivMod<Tuple<62>, Tuple<10>> is [Tuple<6>, Tuple<2>]. The guard Sub<T, D> extends infer R extends 1[] does double duty: it names the result R so the recursion can continue without recomputing it, and the extends 1[] constraint fails when R is false, which ends the loop with the remainder sitting in T.

One Horner step

Step multiplies the whole running total by From and adds one new digit, in a single pass over the digit array. It walks from the least significant digit, and because the array is stored least significant first, that is just the usual [infer D, ...infer Rest] destructuring.

For each digit it forms D * From + Carry, splits that with DivMod by the target base, keeps the remainder as the output digit and passes the quotient on as the next carry. The new input digit enters as the initial carry, which is why multiply and add fold into one walk. Tracing Step for the 'e' in '3e8', with the total at [Tuple<3>], From = Tuple<16>, To = Tuple<10> and the incoming carry Tuple<14>:

// digit 3:  3 * 16 + 14 = 62 -> DivMod by 10 -> quotient 6, remainder 2
//           output so far [Tuple<2>], carry Tuple<6>
// no digits left -> Spill flushes the carry
//           output [Tuple<2>, Tuple<6>], which reads as 62

Spill exists because the leftover carry can be larger than a single digit. Converting to base 2, a carry of 6 has to become three separate bits, so Spill keeps dividing it by the target base and emitting remainders until nothing is left. A carry of zero produces no digits, which is what keeps leading zeros out of the answer.

Reading the result back

Horner is the outer loop: pull one character off S with `${infer C}${infer Rest}`, turn it into a value, run Step, recurse. DigitValue does the character lookup by walking the Digits tuple and growing an accumulator until the character matches, so 'e' returns a tuple of length 14 regardless of which base it came from.

Render reverses the trip. It walks the least significant first array and prepends each digit's character to the output string, so the digits come out most significant first. Digits[D['length']] indexes the tuple type by a numeric literal, turning a length back into a character.

Every recursion sits in tail position inside its conditional type, and none goes deep: Sub is bounded by the base, DivMod by how often the base fits into one digit product, Horner by the length of the input.

Edge cases the tests cover

• Convert<16, 2, '100'> gives '100000000'. The input shrinks to three characters while the output grows to nine, so Spill has to split carries across several bits on almost every step.
• Convert<10, 16, '1000'> gives '3e8'. Going the other way, Render has to produce letters, which is where indexing Digits past position 9 matters.
• Convert<16, 2, 'ff'> gives '11111111'. DigitValue resolves 'f' to 15 without any base-specific special casing.
• Convert<10, 16, '256'> gives '100'. The low digits land on exact multiples of 16, so two zero digits have to be emitted rather than dropped, unlike the zero carry that Spill discards.