Solving FizzBuzz with types

A ridiculous solution to a simple problem.

## The problem

You’ve probably heard of FizzBuzz by now. It’s a seemingly simple interview question that can tell you a lot about how a candidate approaches problems and what their coding style is. It is also really good at filtering out most candidates who have absolutely no clue what they are doing.

For those of you who have managed to avoid it all this time, here’s the problem statement:

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers that are multiples of both three and five print “FizzBuzz”.

FizzBuzz is an interesting problem because it’s simple yet can be approached in many different ways. There is a compilation of hundreds of different solutions in hundreds of languages on Rosetta Code, some more ridiculous than others. In this post, I’ll show you one of the more outlandish ways to solve FizzBuzz -- with types.

The idea for solving FizzBuzz with types isn’t an original one. It’s just one of the many problems in the collection of type challenges for TypeScript. I’ve been solving type challenges for quite a while now, and they’re great fun. They do a great job at showcasing all the tricks of TypeScript’s absolutely arcane type system, and I’ve already incorporated some of the techniques I’ve learned in production code. All of the type challenges I’ve solved can be found on GitHub.

This blog post assumes some basic knowledge of the TypeScript type system. I’ve done my best to break down the solution into fairly simple pieces, but if you’ve never written or seen a single conditional or recursive type in your life, this might not make much sense to you. If you’re new to all of this and it sounds interesting to you, start here.

Without further ado, let’s talk FizzBuzz:

## The solution

As advanced as TypeScript’s type system is, there are still some things that are very hard to do. Arithmetic is one of those things. The type challenges that concern arithmetic are classified as “extreme”. This is problematic because most FizzBuzz solutions (particularly in imperative programming languages) rely on the modulo operation to check if the current number is divisible by 3 and/or 5. Attempting to implement FizzBuzz with types this way would be very hard.

Let’s try solving a simpler version of the problem first. This is a great problem-solving technique that can often help you understand the original problem better. Let’s try solving just the “Fizz” part of FizzBuzz, i.e. let’s try to write a type Fizz<N> that returns an array containing “Fizz” in all the right places:

We know that we have to print “Fizz” for every number that is divisible by three. At first glance, this seems just as hard for the same reason mentioned above, but there’s a fairly obvious observation to be made: we know that every third number is divisible by three. Instead of going one number at a time and trying to check if it’s divisible, we can directly output three numbers at a time, as we know that the third of them will always be divisible by three:

[1, 2, *Fizz*, 4, 5, *Fizz*, 7, 8, *Fizz*, 10, 11, *Fizz*, …]

This is great because we don’t need any arithmetic operations for this. There’s still one thing to figure out though, and it’s when to stop, i.e. how to know if we’ve outputted enough elements. We need some way to subtract from N until it becomes zero. Surely this must require some arithmetic, right?

Thankfully, there’s a fairly easy way to deal with positive integers up to about $$10^3$$ (which should be sufficient for this problem), and it involves arrays. As we’ve already mentioned, we can’t directly manipulate numbers, but we can manipulate arrays, and arrays have a length. This allows us to represent any number T as an array with T elements in them. Here’s a type NumberToTuple<T> that takes a number T and produces an array with length T:

type NumberToTuple<
  T extends number,
  Acc extends readonly unknown[] = [],
> = Acc["length"] extends T
  ? Acc
  : NumberToTuple<T, [...Acc, unknown]>;  

NumberToTuple<T> is a fairly simple recursive type with a base case of Acc["length"] extends T, in which case Acc is returned, and a recursive case in which we append a new element to Acc. It should be reasonably obvious how and why this works -- we just keep appending to Acc until its length is equal to T. The value we append doesn’t matter, it could be anything. In this particular case, I’ve used unknown, but it could’ve also been absolutely any other type.

Now that we have a way to represent numbers in a form that we can manipulate, we can finally implement subtraction. Some of you might have already guessed that we’ll simply be recursively removing one element at a time from the array representation of our number. How can we know we’ve removed enough? Easy! We just use another array to keep track of that:

type Drop<
  T extends readonly unknown[],
  N extends number,
  Acc extends readonly unknown[] = [],
> = Acc["length"] extends N
  ? T
  : T extends [unknown, ...infer Rest]
  ? Drop<Rest, N, [...Acc, unknown]>
  : T;  

Drop<T, N> removes N elements from the front of T, which in essence is a subtraction operation for our “array numbers”. This is the first time we’ve seen the infer keyword in this post. If you’ve never heard of it before, it basically does what the name suggests: it allows us to infer from types we compare against. It could be used to infer the return type of a function, the type of the elements of an array, or as in this case, it could be used to infer a specific part of an array. T extends [unknown, ...infer Rest] essentially infers the type of every element in the array except the first one, effectively removing it.

If none of this makes sense, this is the time to take a break from this blog post and research this further, as understanding it is crucial for the rest of the solution.

For those who are still following my train of thought, it’s time to put the pieces together and define the Fizz<N> type:

type Fizz<
  N extends readonly unknown[],
  Acc extends readonly unknown[] = [],
> = N["length"] extends 0
  ? Acc
  : Fizz<Drop<N, 3>, [...Acc, never, never, "Fizz"]>;  

Fizz<N> takes a “number array” N and recursively subtracts three from it until it’s empty and adds three elements to Acc, the third one being “Fizz”. This type should successfully solve the “Fizz” part of the problem, so let’s test it:

type Foo = Fizz<NumberToTuple<6>>;  

We expect Foo to be [never, never, "Fizz", never, never, "Fizz"], and it is. Great!

The keen-eyed ones of you have definitely already spotted yet another problem we have though -- our Fizz type always outputs an array with a length that is a multiple of three. In other words, Fizz<NumberToTuple<5>> will output the exact same thing as Fizz<NumberToTuple<6>> and so on. This is completely intentional though, as it keeps our Fizz type simple and straightforward. We “overshoot” on purpose, as dealing with the edge cases in the Fizz type itself is very complicated. It is much simpler to take the exact amount of elements we want afterwards, with the help of a type like this:

type Take<
  T extends readonly unknown[],
  N extends number,
> = T['length'] extends N
  ? T
  : T extends [...infer Init, unknown]
  ? Take<Init, N>
  : T;  

Take<T, N> uses the same infer technique to remove elements from T, this time from the right, until the length of T is N. Now, we can simply wrap our result with Take and the overshooting problem will be solved. With this, the solution for the simpler version of the problem is complete. Oh, yeah, if you’ve forgotten, this isn’t even the original problem we are trying to solve. Thankfully, we’re pretty close now.

It should be trivial to notice that we can implement Buzz in an equivalent way:

type Buzz<
  N extends readonly unknown[],
  Acc extends readonly unknown[] = [],
> = N["length"] extends 0
  ? Acc
  : Buzz<Drop<N, 5>, [...Acc, never, never, never, never, "Buzz"]>;  

But why is any of this helpful? Well, let’s look at the outputs for Fizz, Buzz, and the expected output of FizzBuzz for some value of N, e.g. 20:

For those of you who already knew where I was going from the beginning, you’re very clever, have a cookie: 🍪. Either way, it is easy to notice that FizzBuzz<N> is an element-wise concatenation of Fizz<N> and Buzz<N>, ignoring never values and if both elements are never, the index is taken as the value. It should be obvious why the element-wise concatenation satisfies all cases of the problem statement.

We’re still left with implementing this concatenation/merging step though. There are many different ways to approach it, but the one I like the most involves a matrix operation called “transpose”, as this approach can be scaled trivially to other extensions of this problem which involve adding extra divisibility cases.

Here’s a way to implement Transpose<T>:

type Transpose<T extends ReadonlyArray<readonly unknown[]>> = (
  T["length"] extends 0 ? [] : T[0]
) extends infer First extends readonly unknown[]
  ? {
      [X in keyof First]: {
        [Y in keyof T]: X extends keyof T[Y] ? T[Y][X] : never;
      };
    }
  : never;  

It may look scary, but all it really does is take a two-dimensional array/matrix T, iterate over each column X and each row Y and produce a new matrix where each element is T[Y][X], essentially flipping T over its diagonal.

Transpose<T> allows us to group each element of the two Fizz and Buzz arrays, after which we can concatenate them. For example, let’s say we transpose the outputs of Fizz<6> and Buzz<6>, which look like this:

type PreTranspose = [
  [never, never, "Fizz", never, never, "Fizz"],
  [never, never, never, never, "Buzz", never],
];  

After the transposition, we’ll get something like this:

type PostTranspose = [
  [never, never],
  [never, never],
  ["Fizz", never],
  [never, never],
  [never, "Buzz"],
  ["Fizz", never],
];  

This allows us to convert what would’ve been column-wise operations into row-wise operations, which just makes the implementation of the Merge type easier. Now that we know how to “group” our Fizzes and Buzzes with the help of Transpose, let’s first implement a type MergeRow that can handle the concatenation of a single grouped row:

type MergeRow<
  Row extends readonly string[],
  Acc extends string = ``,
> = Row extends [
  infer Head extends string,
  ...infer Rest extends readonly string[],
]
  ? MergeRow<Rest, [Head] extends [never] ? Acc : `${Acc}${Head}`>
  : Acc;  

MergeRow<Row> takes a row out of our new transposed matrix of Fizzes and Buzzes, recurses over each element, and appends it to Acc if it’s not never. We can now implement a Merge type that does the full concatenation/merge process:

type Merge<Parts extends ReadonlyArray<readonly string[]>> =
  Transpose<Parts> extends infer Rows extends ReadonlyArray<
    readonly string[]
  >
    ? {
        [Key in keyof Rows]: MergeRow<Rows[Key]> extends infer Result
          ? Result extends ""
            ? Key
            : Result
          : never;
      }
    : never;  

Merge<Parts> takes an array of Fizzes and Buzzes (and potentially more) and returns the final FizzBuzz array. As already mentioned, it first transposes Parts, then iterates over each row and merges it individually. If the row merge results in an empty string, it returns the Key, as it means that all elements in the row were never.

We now have all the pieces we need to write a final FizzBuzz<N> type:

type FizzBuzz<N extends number> =
  NumberToTuple<N> extends infer T extends readonly unknown[]
    ? Merge<[Fizz<T>, Buzz<T>]> extends infer Merged extends
        readonly unknown[]
      ? Take<Merged, N>
      : never
    : never;  

FizzBuzz<N> first converts the number N to an “array number”, then computes Fizz and Buzz individually in order to pass them on to Merge, and in the end, the merged result is passed through Take to trim it down to the exact length. Let’s test it:

type Bar = FizzBuzz<5>;  

When we test our FizzBuzz<N> type, we notice something obvious: arrays are zero-indexed. Duh! We get the following result:["0", "1", "Fizz", "3", "Buzz"].

Thankfully, this is an easy fix. We can just pad the results of our Fizz and Buzz types to contain a 0-th element, then drop it at the end. Let’s modify the Fizz and Buzz types like this:

type Fizz<
  N extends readonly unknown[],
  Acc extends readonly unknown[] = [never],
> = N["length"] extends 0
  ? Acc
  : Fizz<Drop<N, 3>, [...Acc, never, never, "Fizz"]>;

type Buzz<
  N extends readonly unknown[],
  Acc extends readonly unknown[] = [never],
> = N["length"] extends 0
  ? Acc
  : Buzz<Drop<N, 5>, [...Acc, never, never, never, never, "Buzz"]>;  

Now, to drop the element we added for padding, let’s modify the FizzBuzz type as well:

type FizzBuzz<N extends number> =
  NumberToTuple<N> extends infer T extends readonly unknown[]
    ? Merge<[Fizz<T>, Buzz<T>]> extends infer Merged extends
        readonly unknown[]
      ? Take<Drop<Merged, 1>, N>
      : never
    : never;  

With these changes, our FizzBuzz type finally works! For the whole thing, check here.