FizzBuzz from scratch or life without natural numbers

02/01/2022

At some point in time, recruiters working for American software development companies have discovered a peculiar and scary fact about the people they were trying to hire: while they were recent graduates from top colleges, they could not program. To quote a blog post from Imran Ghory:

Want to know something scary? - the majority of comp sci graduates can’t. I’ve also seen self-proclaimed senior programmers take more than 10-15 minutes to write a solution.

To identify those people who are supposed to be good programmers but actually aren’t, he suggested to use coding problems that are extremely simple. An example of such a problem is FizzBuzz:

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 which are multiples of both three and five print FizzBuzz.

There are of course many more problems like it, but this particular problem (maybe because of its simplicity) has become an internet meme. And as with all meme problems, people will often go way beyond simply solving them, but they will try solving them in the most creative ways possible.

Of course, there are many ways to get your creativity going. One such way is to restrict yourself in some interesting manner, and try to work around those restrictions. Problems like FizzBuzz lend themselves to this type of “spicing them up” pretty well, just because they are so simple to grasp the essence of (that is, if you actually can program).

For this post, I am going to do exactly that. For this post, we will deny ourselves the use of integers that are built into our programming language of choice. What does that mean exactly? Let’s outline the rules of the game in a bit more detail:

Use of any numeric values of variables containing them is not allowed
Use of any numeric operations (like taking lengths of arrays, using loops over numeric ranges etc) is not allowed
Non-numeric array operations (like appending to the end of an array, or going over its elements in a loop) are allowed
String operations are allowed
Boolean operations are allowed
Control flow is allowed

I should point out that FizzBuzz was already solved using these (or similar) rules many times. For example, here’s a very similar thing done in Ruby by Tom Stuart. There will, however, be some very important differences between this talk and the things I am going to do in this post.

First of all, Tom’s restrictions were much stricter than ours. This is part of the reason he was using lambda-calculus to do the things he was doing. In this post, I am not going to use lambda-calculus, but I am going to imagine that we have a Turing machine on our hands (which we kind of do actually). The third difference if that Tom was using Ruby, but we will be using Python, because it is a language that I know and love. I should point out that I will not be using any Python specific features in this post, and that this code should be more or less easy to translate into any (dynamic) programming language. Now we can finally start!

First, we need to ~~hit a blunt and~~ ask ourselves what actually is a number. By “number”, here and below I will mean “natural number”, that is, a whole number equal to or greater than zero. This is enough numbers to do FizzBuzz. This question was asked many years ago, and was answered in the end of the 19th century by Giuseppe Peano, an Italian mathematician. He came up with a series of postulates that captured the essence of number-ness. Here is one (not so rigorous) formulation of these postulates:

Zero is a natural number.
Every natural number has a successor (which is also a natural number).
Zero is not the successor of any natural number.
Different natural numbers have different successors.
If zero has X, and each natural number relays X to its successor, then all natural numbers get X.

I have copied them from here because this is a very succinct formulation of Peano postulates. I highly recommend reading GEB, which is the actual source of this formulation.

Together with these postulates, we can also introduce some common definitions for numeric operations:

Successor of a is S(a)
a = b if and only if S(a) = S(b)
a + S(b) = S(a + b)
a * S(b) = (a * b) + a

From these postulates and definitions we can see that to define a number system, we really need to come up with 3 things ( that satisfy the postulates):

Zero
Successor function
Some notion of equality

This can be done in many (infinitely many, in fact) ways. In actual mathematics, the most common way to construct natural numbers is by using set theory and the von Neumann construction. Other constructions include ones using lambda calculus (that’s what Tom did in his talk), and the Zermelo construction, which is the one I am going to use.

In this construction, zero is defined as the empty set ({}), and the successor of a number a is defined as a set containing the number (S(a) = {a}). For example:

0 = {}
1 = S(0) = {{}}
2 = S(1) = S(S(0)) = {{{}}}
3 = S(2) = S(S(S(0))) = {{{{}}}}
...

We are going to use this construction because it is extremely easy to translate into Python. Now, let’s write our first piece of python code defining zero, successor and equality.

ZERO = frozenset({})

def S(n):
    return frozenset({n})

def num_equals(a, b) -> bool:
    return a == b

For equality, we just use boolean equals given to us by Python. Zero and successor are just straight-up translations of the Zermelo construction into Python, with the only caveat being the fact that here we are forced to use frozensets instead of just sets. This is because sets are not hashable and thus cannot be members of other sets. Frozensets are an immutable and hashable version of sets (see lists vs tuples).

Now, here comes an interesting fact: these 3 things we have just defined (zero, successor, equality) are 3 only 3 things that need any internal knowledge of how the numbers are represented. All the other operations on natural numbers can be defined in terms of these three. We will then be alle to replace these 3 operations with other that behave similarly and the rest of our system won’t even notice. Isn’t that neat?

Anyway, now we can define some more numbers for ourselves using the successor function and zero.

ONE = S(ZERO)
TWO = S(ONE)
THREE = S(TWO)
FOUR = S(THREE)
FIVE = S(FOUR)
SIX = S(FIVE)
SEVEN = S(SIX)
EIGHT = S(SEVEN)
NINE = S(EIGHT)
TEN = S(NINE)

This is very straightforward. We can just iteratively apply our (now opaque) successor function to generate new numbers. Now, let’s write some more code and define comparison operators (less and more):

def num_less(a, b) -> bool:
    """Is a less than b (a < b)"""
    if num_equals(a, b):
        return False
    u = ZERO
    while True:
        if num_equals(u, a):
            return True
        if num_equals(u, b):
            return False
        u = S(u)

def num_greater(a, b) -> bool:
    """Is a greater than b (a > b)"""
    return (not num_less(a, b)) and (not num_equals(a, b))

The code can seem confusing at first, but it is pretty simple in essence. What we do here is we first check if the numbers are equal (if they are equal one can’t be less than the other). Then, we just start counting up from zero, and if we reach a (but not b), then a is less than b. If we reach b (but not a), than a is not less than b. When we have both equals and less, greater becomes trivially easy to define as “not less and not equal.” From this text you can probably see how much I struggle not to use numeric words like “first”, “second” and so on. I think that at this point it may be a good exercise to get a piece of paper and play with some checkmarks to see how this code works.

We can now define addition using a similar technique:

def num_add(a, b):
    """Add numbers a and b (a + b)"""
    r = a
    u = ZERO
    while not num_equals(u, b):
        r = S(r)
        u = S(u)
    return r

As I already said, this function works in a very similar fashion to comparison. We start with one of the input numbers (a), and then, essentially, count up from a``btimes. Multiplication can be defined in an extremely similar fashion:

def num_multiply(a, b):
    """Multiply numbers a and b (a * b)"""
    r = ZERO
    u = ZERO
    while not num_equals(u, b):
        r = num_add(r, a)
        u = S(u)
    return r

We start with 0, and then add a to it b times. It should be noted that at this point, the complexity of our multiplication algorithm is O(n²), which is not that bad. But wait, we will reach new frontiers of inefficiency with this.

Now, we can write a function to subtract 2 numbers:

def num_subtract(a, b):
    """Subtract number b from a (a - b)"""
    if num_less(a, b):
        raise ValueError("We should stay within natural numbers")
    if num_equals(a, b):
        return ZERO
    x = ZERO
    while not num_equals(num_add(x, b), a):
        x = S(x)
    return x

Since we do not have (or rather are not guaranteed to have, see below) the notion of previous number, we have to be inventive and again sacrifice efficiency here. The basic idea for this function is essentially that if we have x = a - b, we can find x such that a = x + b by brute force, that is, by trying all x starting from 0 and going up.

This is again, super inefficient, but otherwise (I believe), we will need to have a way to find a previous number (a predecessor function). This is possible with what we use for our numbers now, but we will introduce another way to represent numbers down below.

Now, we will approach the final boss of arithmetic operations: division. We will define division in a single function divmod that will take 2 numbers and return the integer division result and remainder of their division (remember, we do not have fractions here)

def num_divmod(a, b):
    """Return the quotient and the remainder a divided by b (a // b, a % b)"""
    if num_equals(b, ZERO):
        raise ValueError("Division by zero")
    u = ZERO
    while num_less(num_multiply(b, S(u)), a):
        u = S(u)
    if num_equals(num_multiply(b, S(u)), a):
        return S(u), ZERO
    return u, num_subtract(a, num_multiply(b, u))

This function can be a lot to take in, but the basic idea is simple and close to what we do with subtraction. We start at zero, and then go up until we find the smallest number u so that either a = b * S(u) or a < b * S(u). If a = b * u, we just return S(u) as integer division result and 0 as remainder. In the other case we return u and a - b * u as remainder. This function is EXTREMELY optimized as it’s complexity is O(n³). This will have to do however.

We can also define a small helper function that will determine if a number is divisible by another number. Of course, this will be immediately useful for FizzBuzz.

def is_divisible(a, b) -> bool:
    _, r = num_divmod(a, b)
    return num_equals(r, ZERO)

What we do here is essentially return a % b == 0, only using the functions we have defined before for the numbers we have defined before.

Now, we have one more thing to take care of before we can actually do FizzBuzz. You might have noticed that up until that point (both in the post and in the code) we were using numbers that we have defined manually using the successor function. We can of course define numbers from 1 to 100 using this approach and maybe some code generation, but we will go for a more general solution here. We will define functions that will allow us to convert between our numbers in number system and strings containing decimal integers. First, let’s define a couple maps that will link single digit decimal strings and the numbers they represent:

STRING_TO_NUM_MAP = {
    "0": ZERO,
    "1": ONE,
    "2": TWO,
    "3": THREE,
    "4": FOUR,
    "5": FIVE,
    "6": SIX,
    "7": SEVEN,
    "8": EIGHT,
    "9": NINE
}

NUM_TO_STRING_MAP = dict()
for k, v in STRING_TO_NUM_MAP.items():
    NUM_TO_STRING_MAP[v] = k

Now, these maps are not very useful on their own. Let’s define a function that converts between strings and our numbers.

def string_to_num(string: str):
    nums = list(string)
    nums.reverse()
    u = ZERO
    p = ONE
    for n in nums:
        d = STRING_TO_NUM_MAP[n]
        d = num_multiply(d, p)
        u = num_add(u, d)
        p = num_multiply(p, TEN)
    return u

The main idea behind this function is the following. We have a string of digits, let’s say "123". We then separate it into individual digits, as strings, and reverse this list: ["3", "2", "1"]. We then convert each of the digits in to a number using our map, and multiply it by 10 to the power of it’s position (we do use explicit positions though). We then sum up all the numbers we obtained this way: 3 * 1 + 2 * 10 + 1 * 100, which is equal to the numeric representation of our number. We have defined all these operations for our number system, so we can do all this using them. Let’s define a function that does the reverse operation:

def num_to_string(num) -> str:
    out_string = ""
    while num_greater(num, ZERO):
        num, d = num_divmod(num, TEN)
        out_string = NUM_TO_STRING_MAP[d] + out_string
    return out_string

This function is very similar to the string to number function. We use the divmod operation to separate the last digit of a number and the rest of it (123 // 10 = 12and 123 % 10 = 3). We then convert digits to their string representation using our maps. We can then use these to build our final string.

We now actually have enough defined to write FizzBuzz! But let’s define another convenience function that will make out code for FizzBuzz much more readable:

def num_range(a, b):
    if num_less(b, a):
        raise ValueError("b must not be less than a")
    u = a
    while u != b:
        yield u
        u = S(u)

This is a simplistic implementation of the range() function/object from Python. It works by staring at number a, and yielding all numbers from a to b (not including b). Finally, we can now write out code for FizzBuzz:

if __name__ == "__main__":
    for n in num_range(ONE, string_to_num("101")):
        div3 = is_divisible(n, THREE)
        div5 = is_divisible(n, FIVE)
        if div5 and div3:
            print("FizzBuzz")
        elif div3:
            print("Fizz")
        elif div5:
            print("Buzz")
        else:
            print(num_to_string(n))

As you can see, with all the definitions we have made, the code is not that far from your typical FizzBuzz implementation. We use the range generator we have defined, string conversion functions and the divisibility check. The code actually works!

Now, so far we have only worked with Zermelo’s construction of natural numbers. It is a fine choice, but let’s do something that is more fun. In computing, theres’s a whole family of functions that almost guarantee that the postulates outlined above will work with them: cryptographic hash functions. Here I am saying almost because of course they have a fixed output length and thus are bound to have collisions somewhere. But that said, they still should work well enough for our example. Let’s take our file, and replace the 3 initial definitions at the top with:

ZERO = b"THIS IS ZERO"

def S(n):
    return sha256(n).digest()

def num_equals(a, b) -> bool:
    return a == b

We are now using SHA256 as our successor function! This, last version of the code using SHA256 is available here. On my computer, the script takes about ~0.3 seconds to run, which in an indication of how optimal it is. Another interesting thing to look at will be to see how many times SHA256 was used to create the output. For this, we can our script with pprofile (command: pprofile --include fizzbuzz_SHA256.py fizzbuzz_SHA256.py), and it will show:

Line #|      Hits|         Time| Time per hit|      %|Source code
------+----------+-------------+-------------+-------+-----------
.....
    13|    804256|     0.602877|  7.49608e-07|  6.46%|def S(n):
    14|    804255|      1.19257|  1.48283e-06| 12.78%|    return sha256(n).digest()
    15|         0|            0|            0|  0.00%|
    16|    777289|     0.596777|  7.67767e-07|  6.40%|def num_equals(a, b) -> bool:
    17|    777288|     0.912943|  1.17452e-06|  9.79%|    return a == b
    18|         0|            0|            0|  0.00%|
.....

So SHA256 was called 804255 times, and equality 777288 times in total.

Did we learn anything from this? Well, I have learned a little bit about hiw numbers work (and how to create them out of nothing). I also think that doing all these operations in an inefficient manner can help us appreciate the insane amount of engineering that went into modern physical computers and into how optimized they are. And the main purpose of the whole thing was, as always, having fun, which I certainly did :)!