Fizz buzz

Fizz buzz is a group word game for children to teach them about division. Players take turns to count incrementally, replacing any number divisible by three with the word fizz, and any number divisible by five with the word buzz. — Wikipedia

Fizz buzz is fun for programmers as well as children, and has been implemented in a host of languages.¹

Here is a simple solution in Python for the first hundred numbers.

for i in range(1, 101):
    if i%3 == 0 and i%5 == 0:
        my_list.append("fizzbuzz")
    elif i%3 == 0:
        my_list.append("fizz")
    elif i%5 == 0:
        my_list.append("buzz")
    else:
        my_list.append(i)

Since it constructs its results as an array, it could claim to be an array solution. But it employs a for-loop and an if/then/else construct.

Snaky q

How might we write the Python solution in q?

is:(1;()) / initial state
step{[(x;y)]
  (x+1;y,$[0=x mod 15;`fizzbuzz;
           0=x mod  5;`buzz;
           0=x mod  3;`fizz;
           `$string x]) }

q)last 20 step/is
`1`2`fizz`4`buzz`fizz`7`8`fizz`buzz`11`fizz`13`14`fizzbuzz`16`17`fizz`19`buzz

Here we have a step function – the lambda – applied to an initial state – a 1 and and an empty list. The if/then/else is replaced by Cond $, and the loop by the Do form of the Over iterator.

Lose control

A brief inspection lands on the repeated 0=x mod. Could we not test all the moduli at once?

q)last 20{[(x;y)](x+1;y,(`fizzbuzz`buzz`fizz,`$string x)mod[x;15 5 3]?0)}/(1;())
`1`2`fizz`4`buzz`fizz`7`8`fizz`buzz`11`fizz`13`14`fizzbuzz`16`17`fizz`19`buzz

This looks more like vector programming: mod[x;15 5 3]?0 maps a number to [0,3], which indexes (`fizzbuzz`buzz`fizz,`$string x). The control word Cond has gone. We pay a little in ‘overcomputing’: we evaluate mod[x;5 3] and string[x] whether we need to or not, but we have less code to parse.

Lose the loop

The lambda replaced the control structure, but the loop is not really gone. It‘s there in the form of the Do iteration.

Let’s start again with a vector of numbers.

q)show x:1+til 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Test against the moduli.

q)x mod\:15 5 3
1  1 1
2  2 2
3  3 0
4  4 1
5  0 2
6  1 0
7  2 1
8  3 2
9  4 0
10 0 1
11 1 2
12 2 0
13 3 1
14 4 2
0  0 0
1  1 1
2  2 2
3  3 0
4  4 1
5  0 2

Find the first 0s

q)(x mod\:15 5 3)?'0
3 3 2 3 1 2 3 3 2 1 3 2 3 3 0 3 3 2 3 1

and we have all the substitutions.

q)`fizzbuzz`buzz`fizz`(x mod\:15 5 3)?'0
```fizz``buzz`fizz```fizz`buzz``fizz```fizzbuzz```fizz``buzz

Replace the null symbols with the corresponding numbers and we’re done.

q)(`$string x)^`fizzbuzz`buzz`fizz`(x mod\:15 5 3)?'0
`1`2`fizz`4`buzz`fizz`7`8`fizz`buzz`11`fizz`13`14`fizzbuzz`16`17`fizz`19`buzz

Map map map

Notice that the solution is a sequence of mappings.

fb:{                       /fizzbuzz
  ^[`$string x]            / nulls to numbers
  `fizzbuzz`buzz`fizz`     / => symbols
  ?'[;0]                   / => til 4
  mod\:[;15 5 3] x }       / => (til 15; til 3; til 5)

We notice that `fizzbuzz`buzz`fizz corresponds to 15 5 3.

The mappings are a projection, a vector, and two projections.

Of course, written out as above, the mappings are applied from bottom to top. (Not recommended.)

Semantic density

Notice how much of the expression simply states the problem.

`$string x represents the numbers.
`fizzbuzz`buzz`fizz` lists the substitutions.
(x mod\:15 5 3)?'0 tests for divisibility by 15, 5 and 3.

In this way the solution exhibits high semantic density² – most terms in the code correspond to terms in the problem domain.

Exercises

If we evaluate mod 5 3 we do not need also to evaluate mod 15. Remove mod 15 from the solution.

Answer

0=x mod/:5 3 maps each item of x to a pair of booleans. Treating these as binary numbers we can decode them to [0,3].

q)0=x mod/:5 3
00001000010000100001b
00100100100100100100b

q)2 sv 0=x mod/:5 3
0 0 1 0 2 1 0 0 1 2 0 1 0 0 3 0 0 1 0 2

q)(`$string x)^``fizz`buzz`fizzbuzz 2 sv 0=x mod/:5 3
`1`2`fizz`4`buzz`fizz`7`8`fizz`buzz`11`fizz`13`14`fizzbuzz`16`17`fizz`19`buzz

Because x is (the beginning of) the natural numbers $\mathbb{N}$ we don’t actually need to test any numbers. Every third item is a multiple of 3; every fifth, of 5.

Write a version that does not use mod or div.
Answer
```
(`$string x)^``fizz`buzz`fizzbuzz 2 sv count[x]#'(00001b;001b)
```
Instead of Fill ^, use the Case iterator '.
Answer
```
(2 sv(count x)#'(00001b;001b))'[`$string x;`fizz;`buzz;`fizzbuzz]
```
Notice scalar extension allows us to use atoms as the right arguments.
Or one could could write "fizz" for multiples of 3, "buzz" for multiples of 5, and join them for multiples of 15.
Answer
```
(`$string x)^`$raze each("";"fizz";"buzz")1 2*/:flip 0=x mod/:3 5
```
Or one could make three substitutions.
```
rm/[`$string x;3 5 15;`fizz`buzz`fizzbuzz]  / replace multiples
```
Write the ternary function rm.
Answer

Some solutions for rm:
```
{@[x;;:;z] (y-1)+y*til floor%[count x;y]}
{@[x;;:;z] -1_(count[x]>)(y+)\y}
{@[x;;:;z] where 0=(1+til count x)mod y}
```
It is evident above from the Amend At projection @[x;;:;z] that the only difference between the solutions is the expression for generating the indices.

Replace the expression rm/[`$string x;3 5 15;`fizz`buzz`fizzbuzz] with a composition rmc that takes x as its argument.

Answer

We do not want to compose a ternary such as rm/, so we project Apply to get a unary .[rm/].

q).[rm/] (`$string x;3 5 15;`fizz`buzz`fizzbuzz)
`1`2`fizz`4`buzz`fizz`7`8`fizz`buzz`11`fizz`13`14`fizzbuzz`16`17`fizz`19`buzz

Omitting an item from a list makes it a unary projection of enlist.

q).[rm/] (;3 5 15;`fizz`buzz`fizzbuzz) `$string x
`1`2`fizz`4`buzz`fizz`7`8`fizz`buzz`11`fizz`13`14`fizzbuzz`16`17`fizz`19`buzz

That gives us a sequence of unaries, which we can easily compose.

q)rmc:.[rm/] (;3 5 15;`fizz`buzz`fizzbuzz) `$ string ::
q)rmc x
`1`2`fizz`4`buzz`fizz`7`8`fizz`buzz`11`fizz`13`14`fizzbuzz`16`17`fizz`19`buzz

More approaches (in Python) in Joel Grus’ excellent meditation, Ten Essays on Fizz Buzz.

Contributors

Cillian Reilly, Javier Sabio, Stephen Taylor

An earlier version of this article appeared on code.kx.com. ↩
On semantic density:
“Three Principles of Code Clarity”, Vector 18:4
“Pair programming With The Users, Vector 22:1 ↩