Type Gymnastic - Part 9

This is part 9 of the series “Type Gymnastic”. If you haven’t already, go check out part 8. Let’s continue with more challenges today!

Table of contents

Intro

In this series of type challenges we do a walk through of all challenges that I used in my advent calender. We will continue from where we left off - challenge 24 - which is also the last challenge!!

The end 🤸

The advent calender contains 24 different type challenges, and we are now at the end of the calender - challenge 24.

Challenge 24

You are given the type

type SumBinary = any;

And you want to construct a type which takes two binary numbers as strings, convert them to numbers and return to sum of them as decimal. An example would be:

type Example = SumBinary<"0001", "0010">; // Example = 3

This might seem like a lot, but if you have been doing the previous challenges you already know how to get the sum of two numbers using types (if not check out part 8). So really the challenge here is how does one convert a binary number into a decimal number.

With a lot of these challenge we use arrays and their lengths to our advantage. We can insert elements into an array based on some condition and get its length when we are ready and it can be used for i.e. the sum of two numbers. For this challenge we have one conditional: 0 or 1. The binary number is either a 0 or a 1. If we encounter a 0 we have to do X, and if we encounter a 1 we have to do Y. Let’s start off with that, and create a helper type which only deals with one binary number:

type BinaryToDecimal<T extends string> = T extends `${infer F}${infer L}`
  ? F extends "0"
    ? "Do X"
    : "Do Y"
  : "Do Z";

We are using template literal types to extract the first character of the binary string, for example:

type T0 = BinaryToDecimal<"0111">; // T0 = "Do X"
type T1 = BinaryToDecimal<"1000">; // T1 = "Do Y"

Since we are extracting character by character, we want to make this type recursive:

type BinaryToDecimal<T extends string> = T extends `${infer F}${infer L}`
  ? F extends "0"
    ? BinaryToDecimal<L>
    : BinaryToDecimal<L>
  : "Do Z";

Right now this type is just iterating over all characters in the string T and will return “Do Z” when there are no more characters left. We now want to use arrays to our advantage, let’s introduce a new generic that will store some information for us:

type BinaryToDecimal<
  T extends string,
  Acc extends any[] = [],
> = T extends `${infer F}${infer L}`
  ? F extends "0"
    ? BinaryToDecimal<L>
    : BinaryToDecimal<L>
  : Acc["length"];

When we finish iterating over all the characters in the string, we want to return the length of Acc. What’s left for us to do is the tricky part: What do we want to insert into the generic Acc when the binary character is 0 and 1? Maybe a refresher on binary numbers will help:

And how do we do this with types..? Surpisingly the solution is really not that advanced. If we encounter a “0” we push the existing Acc array twice, and if we encounter a “1” we push the existing Acc array twice and and extra element:

type BinaryToDecimal<
  T extends string,
  Acc extends any[] = [],
> = T extends `${infer F}${infer L}`
  ? F extends "0"
    ? BinaryToDecimal<L, [...Acc, ...Acc]>
    : BinaryToDecimal<L, [...Acc, ...Acc, 1]>
  : Acc["length"];

Imagine we have the binary 1010 and we use the type above. The different iterations will look like:

Since we already know how to sum two numbers, I will not walk through that type. Meaning we have the current types:

type BinaryToDecimal<
  T extends string,
  Acc extends any[] = [],
> = T extends `${infer F}${infer L}`
  ? F extends "0"
    ? BinaryToDecimal<L, [...Acc, ...Acc]>
    : BinaryToDecimal<L, [...Acc, ...Acc, 1]>
  : Acc["length"];

type Enumerate<T extends number, Acc extends number[] = []> = Acc extends {
  length: infer L;
}
  ? T extends L
    ? Acc
    : Enumerate<T, [...Acc, 1]>
  : never;
type ConcatLength<T extends any[], D extends any[]> = [...T, ...D]["length"];

type Sum<A extends number, B extends number> = ConcatLength<
  Enumerate<A>,
  Enumerate<B>
>;

type SumBinary<A extends string, B extends string> = Sum<
  BinaryToDecimal<A>,
  BinaryToDecimal<B>
>;

Which is the solution to this challenge!