Three Ways of Looking at FizzBuzz in J
May 30, 2018 by Seán Stickle
With apologies to Wallace Stevens' Thirteen Ways of Looking at a Blackbird.
1. The wycdd Way
From Fizzbuzz in J, Explained by Wayne Chang:
fb =: ('FizzBuzz';'Fizz';'Buzz';":){::0 i.15 3 5|]
Create the Lookup List
Create a list of boxed items that contain all the possible return values:
- “Fizzbuzz” when divided by both 3 and 5
- “Fizz” when divided by 3
- “Buzz” when divided by 5
- The input value when divided by none of the above
Use ; (link) to build the list of boxed items. To include the input value in the list of boxed items, use ": (default format) to convert the number to a string:
fb =: 'FizzBuzz' ; 'Fizz' ; 'Buzz' ; ":
input =: 10
fb input
+--------+----+----+--+
|FizzBuzz|Fizz|Buzz|10|
+--------+----+----+--+
Get the Residues
Take the input number and find out if it’s divisible by 3, 5, or 15. To do this, use | (residue), which returns the remainder when dividing by a given number:
n =: 9
15 3 5 | n
9 0 4
n =: 10
15 3 5 | n
10 1 0
n =: 30
15 3 5 | n
0 0 0
For 3 and 5, there’s only a single 0 returned. For 15, since all three numbers divide evenly, there are three 0s returned. If we find the index of the first 0, we’ll know which number was the greatest divisor with no residue.
Get the Index
Use i. (index of) to find the index of the first 0. Normally, i. operates like x i. y, returning the index of the first occurrence of y in x.
n =: 9
]residues =: 15 3 5 | n
9 0 4
residues i. 0
1
We can also use ~ (passive) to reverse the order, so that it operates like y. i. x, allowing us to be more concise:
n =: 9
]residues =: 15 3 5 | n
9 0 4
0 i.~ residues
1
0 i.~ 15 3 5 | n
1
Important note. If the value we’re looking for in the list doesn’t appear, i. returns an index that exceeds the size of the list we’re examining. For instance, try finding the index of the first occurrence of either 0 or 19 in the list 5 6 7:
0 i.~ 5 6 7
3
19 i.~ 5 6 7
3
In a list with only 3 items, index 3 does not exist. This will be useful in the next step.
Use the Index to Fetch From the Lookup List
We now have a lookup list:
fb =: 'FizzBuzz' ; 'Fizz' ; 'Buzz' ; ":
n =: 10
fb n
+--------+----+----+--+
|FizzBuzz|Fizz|Buzz|10|
+--------+----+----+--+
And an index based on the residues of dividing by 15, 3, and 5:
n =: 10
0 i.~ 15 3 5 | n
2
Use the index to fetch the appropriate value from the lookup list. To do this, use {:: (fetch):
n =: 3
NB. First occurence of `0` would be at index `1`
(0 i.~ 15 3 5 | input) {:: 'FizzBuzz' ; 'Fizz' ; 'Buzz' ; ": n
Fizz
n =: 5
NB. First occurence of `0` would be at index `2`
(0 i.~ 15 3 5 | input) {:: 'FizzBuzz' ; 'Fizz' ; 'Buzz' ; ": n
Buzz
n =: 15
NB. First occurence of `0` would be at index `0`
(0 i.~ 15 3 5 | input) {:: 'FizzBuzz' ; 'Fizz' ; 'Buzz' ; ": n
FizzBuzz
n =: 7
NB. No residues of `0`, so i. returns `3`
(0 i.~ 15 3 5 | input) {:: 'FizzBuzz' ; 'Fizz' ; 'Buzz' ; ": n
7
Simplify with a Fork
In J, there is a pattern called a fork, which looks like this:
f g h y
Where f is a verb, g is a verb, h is a verb, and y is a noun. Note: For those new to J, read “verb” as function and “noun” as “variable”.
Forks are evaluated like this:
(f y) g (h y)
The canonical example in J is calculating the mean of a set of numbers:
(+/ % #) y
Which is evaluated as:
(+/ y) % (# y)
Which is: the sum of y divided by the count of y.
In our example, we have this code:
(0 i.~ 15 3 5 | n) {:: 'FizzBuzz' ; 'Fizz' ; 'Buzz' ; ": n
Using a fork, we can extract the variable and rewrite this as:
fb =: (0 i.~ 15 3 5 | ]) {:: 'FizzBuzz' ; 'Fizz' ; 'Buzz' ; ":
Notice that we’ve introduced a new verb: ] (right). We extracted the variable n, and | (residue) expects two arguments (one on either side), so we had to put in ] as a placeholder for whatever value we pass to fb. There’s more nuance to this that I’ll explain in another post.
Reverse the Order
We could stop here, as the new verb works great:
fb 1
1
fb 3
Fizz
fb 5
Buzz
fb 15
FizzBuzz
To get to wycdd’s original version, we just need to use ~ (passive) again to reverse the order that {:: is applied:
fb =: ('FizzBuzz' ; 'Fizz' ; 'Buzz' ; ":) {::~ 0 i.~ 15 3 5 | ]
Run the Code
Our new verb fb only runs on single integers. If we want to apply it to the numbers 1 to 100, we’ll need to apply it to a whole list. To do that, use "0, which tells J to apply the verb to individual atoms of a list. And we’ll use i. (integers) to generate a list from 0 to 99 (and add 1 to get a list of 1 to 100):
fb"0 (1+i.100)
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
...
2. Rosetta Code Solution 0
From Solution 0 on Rosetta Code’s FizzBuzz page:
> }. (<'FizzBuzz') (I.0=15|n)} (<'Buzz') (I.0=5|n)} (<'Fizz') (I.0=3|n)} ":&.> n=: i.101
Start with the Input List
Create a list from 0 to 100 using i. (integers):
]n =: i.101
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88...
Box It Up
Turn the numeric list into a boxed list. To do this, use < (box). By default, < will act on the whole list:
< n =: i.101
+-----------------------+
|0 1 2 3 4 5 6 7 8 9 ...|
+-----------------------+
So we’ll use " (rank) to apply < to each atom (rank 0) of the list:
<"0 n =: i.101
+-+-+-+-+-+-+-+-+-+-+---+
|0|1|2|3|4|5|6|7|8|9|...|
+-+-+-+-+-+-+-+-+-+-+---+
Find Numbers Divisible by 3
Find the indexes of all the elements of n that are evenly divisible by 3.
To do this, use | (residue) to return the remainders of each number when divided by 3.
3 | n
0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1
Then, check whether each residues are equal to 0 using = (equal):
0 = 3 | n
1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0
Finally, find the index of every 1 in that boolean list:
I. 0 = 3 | n
0 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99
Amend the Boxed List
With the indexes of all the values that are evenly divisible by 3, we can update the values the corresponding boxes in our boxed list.
To do this, use } (amend). This takes three arguments: x m } y, where y is the list to update, m is an array of cell indexes to update, and x is the new value to use in those cells:
y =: <"0 n =: i.101
m =: I. 0 = 3 | n
x =: <'Fizz'
x m } y
+----+-+-+----+-+-+----+-+-+----+---+
|Fizz|1|2|Fizz|4|5|Fizz|7|8|Fizz|...|
+----+-+-+----+-+-+----+-+-+----+---+
Notice that, since we’re updating a boxed list, the value Fizz has to be boxed (<) as well.
We’ll put this all in one line like this:
(<'Fizz') (I. 0 = 3 | n) } <"0 n =: i.101
+----+-+-+----+-+-+----+-+-+----+---+
|Fizz|1|2|Fizz|4|5|Fizz|7|8|Fizz|...|
+----+-+-+----+-+-+----+-+-+----+---+
Repeat for 5 and 15
We can do the same “check and amend” process for both 5 and 15:
(<'Buzz') (I. 0 = 5 | n) } <"0 n =: i.101
+----+-+-+-+-+----+-+-+-+-+----+--+--+---+
|Buzz|1|2|3|4|Buzz|6|7|8|9|Buzz|11|12|...|
+----+-+-+-+-+----+-+-+-+-+----+--+--+---+
(<'FizzBuzz') (I. 0 = 15 | n) } <"0 n =: i.101
+--------+-+-+-+-+-+-+-+-+-+--+--+--+--+--+--------+--+--+---+
|FizzBuzz|1|2|3|4|5|6|7|8|9|10|11|12|13|14|FizzBuzz|16|17|...|
+--------+-+-+-+-+-+-+-+-+-+--+--+--+--+--+--------+--+--+---+
Combine the Amendments
J evaluates from right to left, the output of one phrase becoming the input of the next. A simple arithmetic example:
6 + 5 * 4 + 3
41
Which evaluates as:
6 + (5 * (4 + 3))
41
In the same way, we can chain our “check and amends” so that the output of one is the input of the next:
(<'FizzBuzz') (I. 0 = 15 | n) } (<'Buzz') (I. 0 = 5 | n) } (<'Fizz') (I. 0 = 3 | n) } <"0 n =: i.101
+--------+-+-+----+-+----+----+-+-+----+----+--+----+--+--+--------+---+
|FizzBuzz|1|2|Fizz|4|Buzz|Fizz|7|8|Fizz|Buzz|11|Fizz|13|14|FizzBuzz|...|
+--------+-+-+----+-+----+----+-+-+----+----+--+----+--+--+--------+---+
Cut Off the Head
Since we want the results for 1 to 100, we don’t want the first cell in the boxed list. To remove this, use }. (behead):
}. (<'FizzBuzz') (I. 0 = 15 | n) } (<'Buzz') (I. 0 = 5 | n) } (<'Fizz') (I. 0 = 3 | n) } <"0 n =: i.101
+-+-+----+-+----+----+-+-+----+----+--+----+--+--+--------+---+
|1|2|Fizz|4|Buzz|Fizz|7|8|Fizz|Buzz|11|Fizz|13|14|FizzBuzz|...|
+-+-+----+-+----+----+-+-+----+----+--+----+--+--+--------+---+
Unboxing Day
Now we’ll unbox everything so that we have a simple list. To do this, use > (open):
> }. (<'FizzBuzz') (I. 0 = 15 | n) } (<'Buzz') (I. 0 = 5 | n) } (<'Fizz') (I. 0 = 3 | n) } <"0 n =: i.101
|domain error
| >}.(<'FizzBuzz')(I.0=15|n)}(<'Buzz')(I.0=5|n)}(<'Fizz')(I.0=3|n)}<"0 n=:i.101
Uh oh. This problem is caused because the contents of the boxed list are a combination of literals (characters) and integers. We can’t create a simple list that contains both.
We’ll need to convert all the numbers to characters.
Convert to Characters
The easiest place to do that is when we boxed them up in the first place.
So, instead of doing this:
<"0 n =: i.101
We’ll do this:
":&.> n =: i.101
This uses &. (under), which takes three arguments: u &. v y, where u is a verb, v is a verb, and y is a variable.
For u, we’ll use ": (default format), which converts numbers to characters. For v, we’ll use > (open).
The order of operation is a little complicated:
- Executes
vonycell-by-cell - For each cell,
uis applied to the result ofv - Then
v^:_1(i.e. the obverse of v) is applied to the result ofu— giving the result for that cell.
So, for us, this means:
- Execute
>(open) on each cell ofy(i.101). These are already unboxed, so this doesn’t do anything. - Execute
":to the result, which converts the numbers to characters. - Execute
>^:1, that is, the inverse of>(open), which is the same as<(box).
":&.> n =: i.101
+-+-+-+-+-+-+-+-+-+-+---+
|0|1|2|3|4|5|6|7|8|9|...|
+-+-+-+-+-+-+-+-+-+-+---+
This looks the same as our original, but the values inside those boxes are different.
Here’s the original and the updated boxed lists:
original =: <"0 n =: i.101
updated =: ":&.> n =: i.101
If we use { (from) to take the first element of each boxed list, then use > (open) to unbox it, we can then use datatype to identify the contents:
> 1 { original
1
datatype > 1 { original
integer
> 1 { updated
1
datatype > 1 { original
literal
Unboxing Day, Take 2
Updating the code to ensure the contents of the boxed list are all converted to literals, we can now try to unbox the results again:
> }. (<'FizzBuzz') (I. 0 = 15 | n) } (<'Buzz') (I. 0 = 5 | n) } (<'Fizz') (I. 0 = 3 | n) } ":&.> n =: i.101
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
...
3. Rosetta Code Solution 1
From Solution 1 on Rosetta Code’s FizzBuzz page:
Fizz=: 'Fizz' #~ 0 = 3&|
Buzz=: 'Buzz' #~ 0 = 5&|
FizzBuzz=: ": [^:('' -: ]) Fizz,Buzz
Fizz for 3
For a number, see if it’s evenly divisible by 3. We can do this in the same way we’ve done previously, using | (residue) and then comparing the result to 0 using = (equal):
n =: 9
0 = 3 | n
1
If the result is 1, we’ll return Fizz; if the result is 0, we’ll return nothing.
We’ll do this by using # (copy), which takes two arguments: x # y, where y is the thing you want copied, and x is the number of copies you want. For example, we can create 10 copies of 1:
10 # 1
1 1 1 1 1 1 1 1 1 1
In our case, we’ll make either 0 or 1 copies of Fizz, depending on whether the residue is equal to 0 or not:
n =: 9
(0 = 3 | n) # 'Fizz'
Fizz
n =: 10
(0 = 3 | n) # 'Fizz'
To make this read a little easier, use ~ (passive) with # (copy) to flip the order or the arguments:
n =: 9
'Fizz' #~ 0 = 3 | n
Fizz
We can extract the variable and turn this into a standalone verb:
Fizz =: 'Fizz' #~ 0 = 3&|
Notice that to extract the variable, we used & (bond) to join an argument (3) to the primitive verb | (residue). This is how J implements currying, allowing us to pend the full evaluation of the verb until we receive the second argument.
If we don’t bond 3 to |, we’d get a syntax error when trying to define this verb:
Fizz =: 'Fizz' #~ 0 = 3 |
|syntax error
| Fizz=: 'Fizz'#~0=3|
Buzz for 5
We’ll do the same thing for 5:
Buzz =: 'Buzz' #~ 0 = 5&|
Easy!
Forking Fizz and Buzz
Let’s apply both Fizz and Buzz to a given input. We’ll use , (append) to create a list from the results of the two verbs:
n =: 3
(Fizz n) , (Buzz n)
Fizz
n =: 5
(Fizz n) , (Buzz n)
Buzz
n =: 15
(Fizz n) , (Buzz n)
FizzBuzz
n =: 17
(Fizz n) , (Buzz n)
Remember the fork pattern from above?
f g h y
Which evaluates to:
(f y) g (h y)
We can use the fork pattern to simplify our code. Instead of:
(Fizz n) , (Buzz n)
We can use:
(Fizz , Buzz) n
Is It Empty?
Executing (Fizz , Buzz) on the list of 1 to 100 gives us:
(Fizz , Buzz) "0 (1+i.100)
Fizz
Buzz
Fizz
Fizz
Buzz
Fizz
FizzBuzz
Fizz
...
We’re returning the right results for numbers divisible by 3, 5, and 15. We still need to return the input number when not divisible by 3, 5, and 15.
To do this, test to see if the value returned is blank. Use -: (match), which takes two arguments, x -: y, returning 1 if x and y match and returning 0 otherwise:
n =: 10
'' -: (Fizz , Buzz) n
0
n =: 7
'' -: (Fizz , Buzz) n
1
We can use this 1 or 0 to decide whether to return the input number or the result of (Fizz , Buzz).
To simplify the code, we ca turn this into a standalone verb by extracting the (Fizz , Buzz) n:
is_empty =: '' -: ]
is_empty (Fizz , Buzz) 10
0
is_empty (Fizz , Buzz) 7
1
Note that -: (match) expects two arguments, so we’re using ] (right) to stand in for what we’ll pass as input.
Fix the Power
We’ll do this by using ^: (fixed power). This verb takes three arguments, u ^: n y, where u is applied n times to y. It’s crucial to know that applying u zero times to y just returns the original value y.
For example, using *: (square):
square =: *:
square 5
25
(square^:1) 5
25
(square^:0) 5
5
We can combine this use of fixed power with another [ (left), a verb that takes two arguments, x [ y and always returns the left argument.
1 [ 2
1
Repeated applications of [ (left) do the same thing:
1 [ [ 2
1
And repeated applications is what ^: (fixed power) does:
1 [^:(1) 2
1
1 [^:(2) 2
1
But, using the crucial insight from above that raising a verb to the fixed power of 0 just returns the original input:
1 [^:(0) 2
2
This gives us a switch to select the left or the right input, depending on whether we raise [ (left) to 0 or 1:
1 [^:(1) 2
1
1 [^:(0) 2
2
This, along with the test we wrote for whether (Fizz , Buzz) returns a blank, allows us to write this:
n [ ^:('' -: ]) (Fizz , Buzz) n
If the result of (Fizz , Buzz) is blank, then ('' -: ]) returns 1, which raises [ to the 1 power, which returns what’s on the left, which is n, the input.
If the result of (Fizz , Buzz) is not blank (i.e., Fizz, Buzz, or FizzBuzz), then ('' -: ]) returns 0, which raises [ to the 0 power, which returns the original input, which is the output of (Fizz , Buzz).
Hook, Line, Sinker
Notice that our code:
n =: 10
n [ ^:('' -: ]) (Fizz , Buzz) n
Buzz
Can be rewritten as:
f =: [ ^:('' -: ])
g =: Fizz , Buzz
y =: n
y f g y
Buzz
In J, the y f g y pattern is known as a hook, and it can be written more simply as:
(f g) y
Buzz
In combinatory logic, this is known as the S combinator.
Rewriting the entire sentence using the hook structure, we get:
n =: 10
([ ^:('' -: ]) Fizz , Buzz) n
Buzz
We can define this as a standalone verb:
fb =: [ ^:('' -: ]) Fizz , Buzz
fb 3
Fizz
fb 5
Buzz
fb 15
FizzBuzz
fb 17
17
Apply to the List
Now apply fb to the list 1 to 100, using "0 (rank) to apply the verb to individual atoms of the list:
fb"0 (1+i.100)
|domain error
| fb"0(1+i.100)
Oops! This is the same error that we got back in the second way to look at FizzBuzz. We’re mixing literals and integers, which raises a domain error. To fix that, we need to convert all the results to literals.
Do that by applying ": (default format) to the results of our verb, which will convert the integers to literals:
fb =: ": [ ^:('' -: ]) Fizz , Buzz
Now we can try again:
fb"0 (1+i.100)
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
...
Perfect.
Coda
It’s interesting to observe that adding the ": (default format) to the verb:
fb =: ": [ ^:('' -: ]) Fizz , Buzz
Converted it from a hook into a fork:
f =: ":
g =: [ ^:('' -: ])
h =: Fizz , Buzz
(f g h) 15
FizzBuzz
(f g h) 17
17
Which is evaluated as:
(f 15) g (h 15)
FizzBuzz
(f 17) g (h 17)
17
EOF