FizzBuzz Lightyear: to `Infinity` and beyond!
Tags: typescript, javascript, algorithms
Published: 2021-02-12 17:36:25

Perhaps the most famous of all coding interview questions is FizzBuzz. For the uninitiated, the algorithm is as follows:
* For multiples of 3, print “Fizz”.
* For multiples of 5, print “Buzz”.
* The multiples of both 3 and 5, print “FizzBuzz”.
* For all remaining numbers, print the number as-is. 
 
Any fresh bootcamp grad should be able to solve it without too much trouble, but the challenge (or so the rationale goes) is in how they implement it.
 
> _**With that in mind, let’s over-engineer the crap out of it! 🚀🚀🚀**_
 
Usually, the question only asks for output for the numbers 1 to 100, but we’d be remiss if we didn’t go all the way up to Infinity — or at least as close as we can get before hardware  limitations get in the way.
 
To do that, let’s first build a `range` data structure that can be logically infinite in size. We’ll do this using an [iterator](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols), along with JavaScript’s [`bigint`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt) data type. The range increments by 1 each iteration, so we allow the upper bound to be positive Infinity, but we don’t allow the lower bound to be negative Infinity, because incrementing an Infinity is meaningless.
 
```ts
const range = (min: bigint, max: bigint | typeof Infinity) => {
    max = max === Infinity
        ? max
        : BigInt(max)
 
    if (min > max) {
        throw new RangeError('min cannot exceed max')
    }
 
    return {
        *[Symbol.iterator]() {
            for (let n = min; n <= max; n++) yield n
        },
        min,
        max,
        toString: () => `${min}..${max}`,
        includes: (n: bigint) => n >= min && n <= max,
    }
}
```
 
Next, we create our `format` function:
 
```ts
const format = (n: bigint) => [
    !(n % 3n) && 'Fizz',
    !(n % 5n) && 'Buzz',
].filter(Boolean).join('') || n.toString() 
```

Here, we’re checking the remainder from 3 and 5 and joining the truthy items of the array. If the resulting string has length zero, we simply return the number itself (as a string, for type safety).

We’ll also need a `map` function to map over our iterable. For small ranges, we could simply convert the iterable to an array and then use `Array#map`, but this would cause problems for  infinite or very large ranges, which need to be mapped over lazily. With that in mind, here’s `map`:
 
```ts
 const map = <TArg, TReturn>(fn: (arg: TArg) => TReturn) => (
    iter: Iterable<TArg>,
): Iterable<TReturn> => ({
    *[Symbol.iterator]() {
        for (const x of iter) yield fn(x)
    },
})
```
 
Great! Now we can already start consuming our infinite FizzBuzz with a `for...of` loop. We’re using [`pipe` from `fp-ts`](https://gcanti.github.io/fp-ts/modules/function.ts.html#pipe) to make our code a bit more readable — `pipe(val, fn1, fn2)` is equivalent to `fn2(fn1(val))`:
 
```ts
import { pipe } from 'fp-ts/function'
 
const fizzBuzz = pipe(
    range(1n, Infinity),
    map(n => ({ n, formatted: format(n) })),
)
 
for (const { n, formatted } of fizzBuzz) { 
    console.log(formatted)
 
    if (n === 100n) break
}
```
 
The logic is somewhat brittle here, though — if we’d accidentally written `100` instead of `100n`, our code would have got stuck in an infinite loop, because a `number` will never be strictly equal to a `bigint`. To remedy this, let’s create a `take` function that grabs the first `n` elements of an iterable and spits them out as an array.
 
```ts
const take = <T>(n: number) => (
    iter: Iterable<T>,
): Array<T> => {
    const arr: Array<T> = []
 
    for (const x of iter) {
        arr.push(x)
 
        if (arr.length >= n) break
    }
 
    return arr
}
```
 
Now, we can be sure our code is safe from infinite loops, as long as we remember to call `take`:
 
```ts
const fizzBuzz100 = pipe(
    range(1n, Infinity),
    map(format),
    take(100),
)
 
fizzBuzz100.forEach(x => console.log(x))
```
 
Much better!
 
We can also consume our infinite `fizzBuzz` asynchronously, using `setInterval`:
 
```ts
const iterator = fizzBuzz[Symbol.iterator]()
 
setInterval(() => {
    console.log(iterator.next().value.formatted)
}, 1000)
```
 
This will keep on spitting out values every second until the process crashes, the integers get too big to be operated on or stored in memory, or the heat death of the universe, whichever comes first.
 
For a slightly more ergonomic version of this, we can use async/await with a custom `sleep` function:
 
```ts
const sleep = (ms: number) => new Promise(res => setTimeout(res, ms))
 
;(async () => {
    for (const { formatted } of fizzBuzz) { 
        await sleep(1000)
        console.log(formatted)
    }
})()
```
 
And with that, we’re done! The interviewer politely thanks us for our time and shows us out of the building. A few days later, the long awaited email arrives. “We regret to inform you...” Our heart sinks. It turns out they were looking for a candidate who doesn’t over-engineer things.
 
_But in our heart, we know it was worth it._