Overengineering FizzBuzz

FizzBuzz is a common programming exercise. You might encounter it in a technical test. I had it once. I suppose it’s quite useful as it checks a few things:

• The candidate can put a program together
• The candidate understands instructions and interprets them into code
• The candidate has used the modulus operator - or at least knows what it is

It’s also a pretty quick test to run, so you get an idea of a candidate’s skill and ability in the time put aside for an interview.

The most straight-forward FizzBuzz implementation in Rust would look like this:

fn fizzbuzz(n: u32) -> String {
    if n % 15 == 0 {
        "FizzBuzz".to_string()
    } else if n % 3 == 0 {
        "Fizz".to_string()
    } else if n % 5 == 0 {
        "Buzz".to_string()
    } else {
        n.to_string()
    }
}

This is all fine and good on the face of it, but you can argue that there are a couple of issues with it. Extending it to add a third case makes the code significantly more complicated, illustrated here by adding “Duzz” as a substitute for number 7:

fn fizzbuzz(n: u32) -> String {
    if n % 105 == 0 {
        "FizzBuzzDuzz".to_string()
    } else if n % 35 == 0 {
        "BuzzDuzz".to_string()
    } else if n % 21 == 0 {
        "FizzDuzz".to_string()
    } else if n % 15 == 0 {
        "FizzBuzz".to_string()
    } else if n % 7 == 0 {
        "Duzz".to_string()
    } else if n % 5 == 0 {
        "Buzz".to_string()
    } else if n % 3 == 0 {
        "Fizz".to_string()
    } else {
        n.to_string()
    }
}

The number of tests has increased from three to seven. Writing, reading and maintaining this code is a lot more difficult. I’m not even going to add another case to see what that would look like. So how would we go about improving the code’s maintainability so that adding new cases is simple? And can we address the second issue that could be identified with the traditional FizzBuzz implementation? That is, can we reduce the number of tests to match the number of substitutions we have? So, in a normal FizzBuzz we’d have two tests and in the second example above there would be three.

Motivation

During lockdown I came across an article (I’ve long forgotten where) describing how someone had come up with a two-test FizzBuzz solution in Python. I’m not a Python developer and never have been, but it seemed like a fun exercise to adapt it in Java.

import java.util.List;
import java.util.function.BiFunction;
import java.util.function.UnaryOperator;
import java.util.stream.Stream;

import static java.util.stream.IntStream.range;

public class FizzBuzz {

    private String fizzBuzz(final int n) {
        final List<UnaryOperator<UnaryOperator<String>>> tests = List.of(
            input -> test(n, 3, "Fizz", input),
            input -> test(n, 5, "Buzz", input)
        );
        final UnaryOperator<String> f = foldLeft(
            tests.stream(),
            string -> string,
            (acc, item) -> item.apply(acc)
        );
        return f.apply(String.valueOf(n));
    }

    private UnaryOperator<String> test(
        final int n,
        final int d,
        final String s,
        final UnaryOperator<String> function
    ) {
        return input -> n % d == 0
            ? function.apply("") + s
            : function.apply(input);
    }

    public static <T, U> U foldLeft(
        final Stream<T> stream,
        final U identity,
        final BiFunction<U, ? super T, U> accumulator
    ) {
        final class Box {
            private U value;

            private Box(final U value) {
                this.value = value;
            }
        }
        final var result = new Box(identity);
        stream.forEachOrdered(t -> result.value = accumulator.apply(result.value, t));
        return result.value;
    }
    
    public static void main(String[] args) {
        final var fb = new FizzBuzz();
        range(1, 501)
            .mapToObj(fb::fizzBuzz)
            .forEach(System.out::println);
    }
}

To explain this: Java doesn’t have a built-in fold operation, so this includes one which accounts for a third of the implementation. Essentially, this works by composing the two test functions together into a single function. You can probably see that the tests are in list, so adding more tests is as straight-forward as adding to this list.

What I wanted to do was reimplement it again in Rust as this was where I was doing my personal development. Would I be able to apply what I’d learned to implementing this solution? Well, I was already sure I could, but I did want to see how difficult it would be and how much it would stretch me.

The Case for an Overly Complicated Solution

Looking at the Java solution there are a number of functional techniques at play that come together to build the solution. Here I’m using UnaryOperator alongside higher-order functions to compose multiple calls to a reusable function into a single function. I like this technique and have used it a few times in Java, Kotlin and Rust previously. Being able to use functional composition to concatenate rules is a useful tool to have in your programming toolkit. You never know when you might be able to use this technique. Examples where I have include

• Building a query object from an HTTP request where headers and parameters may not be present and defaults provided
• Dynamically building a database query from a query object

These were done in multiple languages (Java, Kotlin and Rust) so not necessarily in the same project.

The Rust Solution

Here is the solution that I eventually landed on in Rust. It’s quite good because it covers a number of techniques, including two of Rust’s “hard” ones, namely

• Borrowing
• Lifetimes
• Functional composition (chaining functions together into a single function, where the output of one function becomes the input of the next)
• Higher-order functions (functions that can take other functions as arguments or return functions as results)
• One test per substitution
• Easy to extend with new rules

static SUBSTITUTIONS: &'static [(i32, &str)] = &[
    (3, "Fizz"),
    (5, "Buzz")
];

type UnaryOperator<'a, T> = Box<dyn Fn(T) -> T + 'a>;

fn test<'a>(
    to_test: &'a i32,
    to_substitute: &'a i32,
    substitute: &'a str,
    next_function: UnaryOperator<'a, String>,
) -> UnaryOperator<'a, String> {
    Box::from(move |input| {
        if to_test % to_substitute == 0 {
            let mut result = next_function(String::from(""));
            result.push_str(substitute);
            result
        } else {
            next_function(input)
        }
    })
}

fn fizzbuzz(n: i32) -> String {
    let function: UnaryOperator<String> = SUBSTITUTIONS.into_iter()
        .map(|(to_substitute, substitute)| {
            Box::from(|input| test(&n, to_substitute, substitute, input))
        })
        .fold(Box::from(|input| input), |acc, item| item(acc));
    function(n.to_string())
}

Walkthrough of the Solution

So let’s go through this bit by bit because there are a few things to explain here.

static SUBSTITUTIONS: &'static [(i32, &str)] = &[
    (3, "Fizz"),
    (5, "Buzz")
];

This defines the substitutions. Fizz for 3, Buzz for 5. New rules can be added to this array.

type UnaryOperator<'a, T> = Box<dyn Fn(T) -> T + 'a>;

It might be obvious I’m a Java developer. Maybe I could have come up with a shorter name, but I needed it in order for the rest of the code to be a bit more readable. It defines a dynamic function of type T that returns a T. The lifetime of 'a is necessary.

fn test<'a>(
    to_test: &'a i32,
    to_substitute: &'a i32,
    substitute: &'a str,
    next_function: UnaryOperator<'a, String>,
) -> UnaryOperator<'a, String> {
    Box::from(move |input| {
        if to_test % to_substitute == 0 {
            let mut result = next_function(String::from(""));
            result.push_str(substitute);
            result
        } else {
            next_function(input)
        }
    })
}

This one has a few things to explain. Let’s start with the parameters:

• to_test — This is the number that we are testing.
• to_substitute — This is a number we are substituting. For example, a 3.
• substitute — The word to substitute to_substitute with. For example, Buzz.
• next_function — The next function in the chain. The function is a UnaryOperator<'a, String>.

The function returns a UnaryOperator<'a, String>, so it’s a function that returns a function and takes a function as a parameter. It’s a higher-order function!

Next, let’s take a look at the closure inside the Box which forms the function we return.

move |input| {
    if to_test % to_substitute == 0 {
        let mut result = next_function(String::from(""));
        result.push_str(substitute);
        result
    } else {
        next_function(input)
    }
}

input is a String, so it needs to return a String. If the modulus test fails we call and return next_function with input as the parameter. If the test passes then we call next_function with an empty String as a parameter, append our substitution to the end and return it.

It’s the composition of this function multiple times that powers this solution and that is covered in the next method:

fn fizzbuzz(n: i32) -> String {
    let function: UnaryOperator<String> = SUBSTITUTIONS.into_iter()
        .map(|(to_substitute, substitute)| {
            Box::from(|input| test(&n, to_substitute, substitute, input))
        })
        .fold(Box::from(|input| input), |acc, item| item(acc));
    function(n.to_string())
}

This is quite a bit more complicated that in looks and is why UnaryOperator<'a, T> is generic and not of type String. You see, input is a UnaryOperator<String>, therefore the map function returns a UnaryOperator<UnaryOperator<String>> as illustrated more clearly in the Java example. This list of UnaryOperator<UnaryOperator<String>> is then folded into a single UnaryOperator<String> which is called with the value of n converted to a String as a parameter. The initial value of the accumulator is defined as a function that takes the String it has been given and simply returns it. This is how when all tests fail the number is returned.

Running the Code

Here is a quick main method for printing the fizzbuzz value for numbers between 1 and 500.

fn main() {
    for i in 1..=500 {
        println!("{}", fizzbuzz(i));
    }
}

Conclusion

In conclusion, this overly complicated FizzBuzz solution is perhaps unnecessary, but certainly a good learning tool. While it may not be the most practical approach for a simple coding challenge, it showcases the power and flexibility of functional programming techniques and how they can be used in Rust. There can be room for a little over-engineering in software development. After all, pushing the boundaries is where we learn the most.

Banner image by Alan De La Cruz on Unsplash