FizzBuzz Lightyear: to `Infinity` and beyond!

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, along with JavaScript’s 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.

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:

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:

 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 to make our code a bit more readable — pipe(val, fn1, fn2) is equivalent to fn2(fn1(val)):

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.

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:

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:

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:

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.