# An Over-Engineered FizzBuzz Type in TypeScript

I’m sure we’re all familiar with the famous fizz buzz problem, it goes something like this:

Counting from 1 to 100, print either

1.`fizz`

,

2.`buzz`

,

3.`fizzbuzz`

,

4. or the number itself

depending on the current iteration

Today we’ll build this in TypeScript, and no, I don’t mean a JavaScript function annotated with types.

I mean ** this**:

A ** type** that can be used to check the output of a fizzbuzz call.

**No… this is not really useful **but this exercise will hopefully help us learn a bit more about how to ** think in TypeScript**.

## Regular FizzBuzz:

The original fizzbuzz code looks something like:

We’ll want to recreate a lot of these pieces in TypeScript.

# 🥣 Basic Ingredients:

- TypeScript 4.1
- Numbers
- Arithmetic
- Loops
- String Concatenation

It’s technically somewhat possible to have done fizzbuzz as early as TypeScript 3.0, but 4.1 made things **a lot** easier (and more elegant).

## 🔢 Numbers

TypeScript has always supported number literal types like so:

Whereby a `5`

is an extension (more specific type) of the `number`

type:

But did you know that tuples have had a typed `length`

property since version 2.7?

This property is particularly useful because we’re going to encode numbers into tuple types and pave the way to performing arithmetic.

—

## 🧮 Arithmetic

TypeScript 4.0 added a feature called ** variadic tuples** —

*var*, meaning variable, and

*aradic*, referring to

*arity*, the number of arguments a function takes. Basically, we’re able to manipulate variable/generic length tuples.

More specifically, the **spread operator** (`...`

) was added to allow us to manipulate **tuple types**. We are able to build types that **combine** and **split** other tuple types like so:

And most importantly, we can see that the `length`

property of these types are being calculated, so voila — *arithmetic*.

**Note:** when we perform subtraction, you’ll see that we will (predictably) run into issues if the elements aren’t all the same type. For example, if I try to subtract `[true, false]`

from `[any, string, boolean]`

:

We get `never`

because it’s impossible. To avoid this, we’ll just always type our tuple elements as `any`

.

**🥂 Great!**

We can manipulate numbers, but an interface that takes in tuples isn’t particularly *user friendly* right? What we *really* want to be able to do is something like

. To do that, we need to be able to dynamically build tuples sized to a given number literal type like **Subtract**<5,4>`5`

, and for that we actually need… **recursion**.

(Further reading on tuple arithmetic in TypeScript.)

—

## 🔁 Loops (Recursive)

TypeScript 4.1 added support for something that was already commonly being used through various hacks— **recursive conditional types**. We can now define **conditional** types that reference themselves, allowing us to define loops **that end** because we can define the **end condition**.

So if I wanted to build a tuple factory I can recursively increase it’s size by 1 until it’s the right size:

But one problem we’ll have is TypeScript’s recursion depth limit. It’s hardcoded to be about **45** (though this limit has been increased to about **1000** in TypeScript 4.5.4), so we can’t build anything bigger than 45 elements:

We can get around this issue through some hacks.

**1: Wrapping recursive calls in an object**

First, we can create infinitely deep types if we wrap results in objects:

Here we are able to avoid the error because the calculation is being deferred. The depth is actually 46 but TypeScript doesn’t evaluate all the way down, at least not until we use the type for something, that’s why for now the summary is showing `any`

.

TypeScript is allowing this functionality so there’s no risk of crashing things when the developer defines an infinitely recursively deep object type like a JSON object that can be infinitely deep.

This hack gives us *practically* *limitless* depth, but we’ll get stuck with a deep object that isn’t evaluated and so we won’t get our result. We’ll need to **unwrap**. Unwrapping, however, would take the same number of steps and… we’re trying to cut down on that, so we’ll need to be a bit clever here.

**2: Halving/Logarithmic Reduction**

We can define a helper that uses *wrapping* to have a limitless depth, *but* cuts the overall depth in half by consolidating sets of 2 wrappings into 1:

Using this should cut the depth of 8 to 4 in this case:

With this, we’ll only need to run **_Unwrap**** **3 times (8 → 4 → 2 → 1), this is sort of like the divide and conquer we do in binary search, we’re cutting the number of wrappings to it’s log₂.

This should *technically* allow us to reach a depth of something like 2⁴⁵ but it’s a bit more complicated than that and instead we’re stuck with a limit of about 3000, but that’s enough for our exercise.

(There are ways to boost this limit to 150,000+, by using doubling to keep the depth of recursion below 50, unfortunately the TypeScript team clamped down a *hardcoded limit of about 10,000 in version 4.2**)*

—

## 📝 String Concatenation

The final ingredient we’ll need is a way to combine strings together. This was also introduced in TypeScript 4.1. It’s pretty straightforward, we can now do this:

We’ll use this to build our output.

# 🔪 Preparation

With our ingredients we can now set up some basic helpers to define our ultimate type.

## ❓ Conditional Types

Since we’re relying on a TypeScript hack to defer evaluation, everything has to defer-safe. So rather than setting ** hard type parameter rules** like this:

We’re going to rely on ** conditional types**:

Remember how the summary of the 46 deep object wasn’t actually being evaluated? With deferrals, TypeScript will try to avoid evaluation as much as possible and will use `unknown`

as a placeholder instead. With hard parameter rules, `unknown`

would instantly fail constraints like `<`

because **Size **extends number>`unknown`

doesn’t extend `number`

. Conditionals don’t have this problem because they handle both cases of passing and failing the constraint.

—

## 📏 Length

This will let us get the length of any tuple:

—

## 🎁 Unwrap

This will let us unwrap the result of any deep recursive loops:

**Note**: Defining a complementary

would make sense but it seems to run into a bunch of issues.**Wrap**<**Inside**> = {result: **Inside**}

—

## 🏭 Tuple Factory

This will basically be similar to what we had before:

We’ll want to create a friendlier interface that takes in a `number`

as a parameter. However, we’ll also need to add a few additional conditionals because of an issue that gets fixed in 4.2.

Take a look at this:

Basically, when we use a conditional to check the

parameter, it doesn’t get applied downstream, so TypeScript can’t figure out that **Number**

results in **Tupleize**<**Number**>`any[]`

.

But if you use a parameter constraint it works:

But we don’t want parameter constraints instead what we’ll do is *guarantee* that the output will be `any[]`

:

First, we **assign the result to a variable**

using **Tuple**

, then we check that *infers*

before outputting it.**Tuple** extends any[]

—

## ➕ Add

We can use the tuple factory to help us here:

—

## ➖ Subtract

Same here:

—

## ➗ Modulo

A modulo is the **remainder **after performing division and division is just *repeated subtraction*. So we’ll attempt to **Subtract**** **until it comes back as `never`

which tells us that we’ve subtracted too far. Since we couldn’t subtract further it means we **already had the remainder** on hand, so we’ll just return that. We’ll also need to use **halving** to prevent issues with recursion limits:

# Let’s Bake this 🥐

Finally! We can build our type.

First, let’s define a basic for loop, but using recursion. Normally we would achieve this with something like:

where running `forLoop(5)`

would get us a result of `1 2 3 4 5`

.

The type will be basically the same:

But we don’t want to print out the number for every number, we want to print “fizz”, “buzz”, “fizzbuzz”, or the number. Let’s build some helpers here.

**FizzText****BuzzText****Coalesce**`""`

)**FizzBuzzText**

Putting it all together:

**🎉 It works!**

**🔗 ****Here’s a link to the playground**

But it’s extremely slow and starts croaking when we try something like **500**. Let’s fix that.

# 📈 Optimization

We wrote the code in a way that matches the way we wrote it in regular JavaScript, but some of the operations are really *suboptimal*.

**Repeat Tupleization**

To actually advance the index, in every iteration we call

which will build a tuple of size **Add**<**Index**, 1>

. Building tuples takes a long time and we do this for every iteration (this is a time complexity of **Index**** O(N²)**).

We do even worse when we use

which uses **FizzBuzzText**

which repeatedly uses **Modulo**

which **Subtract***itself* builds tuples (this means

by itself has a time complexity of **Modulo**** O(N²)** and using

**Modulo**

on every iteration ends with a complexity of **).**

*O(N³)*The problem stems from **converting in and out of tuples**. We can avoid this by only converting numbers into tuples once and using tuple specific operators.

Let’s first rework all helpers to function on tuples:

That covers all the arithmetic, next the text helpers:

Lastly, our function only needs to be tweaked slightly to use a tuple as a counter:

## ⏱ Results (in seconds):

`╔══════╦══════════╦════════════╗`

║ size ║ original ║ **faster **║

╠══════╬══════════╬════════════╣

║ 500 ║ 29 ║ **3** ║

║ 1000 ║ error ║ **9** ║

║ 2000 ║ error ║ **33 **║

║ 3000 ║ error ║ **56(error)** ║

╚══════╩══════════╩════════════╝

## 🚅 Fast!

But can we do better?

## Linear Time

Though this is faster (at a time complexity of ** O(N²)**), we can go faster. We’re still using

**Modulo**

which uses repeated subtraction to get us a result, but we can actually avoid using **Modulo**

with a bit of ingenuity.What we’ll do is basically **count up to 3 and 5** using tuples, and **reset back to one** on every cycle. These mini cycle trackers will take the place of using

. We’ll need to modify our text helpers first, assuming we’ll never exceed 3 or 5:**Modulo**

With these helpers, we just need to track 3s and 5s:

Now it should run at about the same speed as it takes to build a single tuple with the size of the loop.

## ⏱ Results (in seconds):

`╔══════╦══════════╦════════════╦═══════════╗`

║ size ║ original ║ faster ║ **fastest** ║

╠══════╬══════════╬════════════╬═══════════╣

║ 500 ║ 29 ║ 3 ║ **1** ║

║ 1000 ║ error ║ 9 ║ **3** ║

║ 2000 ║ error ║ 33 ║ **14** ║

║ 3000 ║ error ║ 56(error) ║ **41** ║

╚══════╩══════════╩════════════╩═══════════╝