Today at my current client, there was some disagreement over the scoring of job candidates’ FizzBin solutions in the code test portion of the interview. They are allowed to use whatever language they choose but almost everyone does the same thing. Grayson Koonce has a good explanation of the problem with his evolving solution in Go. I decided to do the exercise myself but with extra constraints. I wouldn’t use any conditionals.
What’s the problem with people’s solutions? First, they use if-else where they should use a series of plain ifs and they end up if one too many branches. They have this:
if divisible by 3 and 5 output FizzBin, newline else if divisible by 3 output Fizz, newline else if divisible by 5 output Bin, newline else output number, newline
That works and I’m not as demanding as my colleagues because I know I write things like that then refine later. The particular conceptual problem is that each branch is printing an entire line. That decision inattention (because it’s not really a decision) strongly influences the solution to create a branch for each type of line. It performs too many divisions and it duplicates the strings.
The underlying problem here is that this is a well-known problem and that people applying for anything other than a first job in programming should already have a refined answer ready to go. You should have already done this, and maybe multiple times. And, technical screeners know this. If you don’t know about this problem, you aren’t paying attention. If you are applying for their first programming job might understandably not know this, but after that you should.
Something like this has better parallel structure (one of the most important things for understandable code). It uses a buffer string to collect the response. If the string is empty at the end, it uses the default setting. There are many variations around this:
clear string if divisible by 3 Add Fizz to string if divisible by 5 Add Bin to string unless string Add number to string output string, newline
But, I wondered how I’d do it without an if at all. This isn’t something that I’d submit for a job interview (unless I didn’t want it), and I’m not trying to golf it or obscure the operation with odd syntax and curious variables. Sometimes it’s instructive to try a simple problem with different constraints to see what they afford (by how hard it is to avoid them) and perhaps see the problem in another way. I’d like to see more interview questions that remove features so you don’t get to do it in the refined way that you should have already prepared. After all, these questions mostly have three purposes: to see your code style, to see the sophistication of your answer, and to see what you do when you’re a bit out of your depth.
So I started on my own solution. I already know that FizzBin is essentially a repeating pattern (on the lowest common multiple of the numbers). If I can cycle through that pattern, all I need to know is the next thing to print without testing it. My first attempt looked like this:
use v5.24;
my $n = $ARGV[0] // 35;
my $count = 0;
my $array = [
map { /\./ ? \$count : \(my $a = $_) }
split //,
(map { $_ . reverse $_ } '..F.BF.')[0]
];
push $array->@*, \ 'FB';
while($count <= $n - 1){
say $array->[ $count++ % @$array]->$*;
}
I clumsily create an array to hold the pattern, and I have to add an element onto the end because it’s a combination. That’s not so good. I use the ..F.BF. string to denote the pattern (and it’s palindromic, so that’s the reverse. But, the single character doesn’t handle the ‘FB’ thing, which is two characters. Everything in the array is a reference so I can dereference it. That came up because I’d get the number through a deference to the $count variable. So, not so nice there. And, it doesn’t actually print Fizz of Bin (it’s F and B). I could fix that too, but by this time I’ve exceeded the threshold for “I can fix that too”.
But, put yourself in the role of the interviewer. Did I avoid the if? Nope. I have the conditional operator (?:) in the first map. That’s cheating.
So I had another idea. I can represent the same thing as a series of 15 two-bit numbers where 00 represents the basic number, 01 represents Fizz, 10 represents Bin, and 11 represents FizzBin. I’ll extract the right two bits from those 30 bits and use the numeric value to lookup the string in an array (which is references again):
use v5.24;
my $n = $ARGV[0] // 35;
my $count = 0;
while($count <= $n) {
state $a = [ \$count, \'Fizz', \'Bin', \'FizzBin' ];
say $a->[ (810092048>>((2*(++$count-1))%30)) & 0b11 ]->$*;
}
It looks ugly in the array index and I messed that up a few times, but the concept is simple (if you were a C programmer I guess). Start with the long bit pattern (the one that makes 810092048) and mask it with 0b11. The tricky part is that I don’t want to shift the mask up, get the number, then shift that down. So, I shift the big number down and mask it. Only the bottom two bits matter there to get the value because all the other positions are zeros.
The ->$* is merely a postfix dereference of a scalar. It’s the homologue of ->@* and ->%*. That’s there because I want one of the array elements to be a reference to a changing value.
But how did I know 810092048? I have a program for that (and it’s something I wrote about in Chapter 16 of Mastering Perl, which you can now read for free in Safari Online
I typed out the bit sequence and converted to decimal:
$ b2d 110000010010010000011000010000 810092048
It’s not really a program. It’s a bunch of shell aliases:
alias d2h="perl -e 'printf qq|%X\n|, int( shift )'" alias d2o="perl -e 'printf qq|%o\n|, int( shift )'" alias d2b="perl -e 'printf qq|%b\n|, int( shift )'" alias h2d="perl -e 'printf qq|%d\n|, hex( shift )'" alias h2o="perl -e 'printf qq|%o\n|, hex( shift )'" alias h2b="perl -e 'printf qq|%b\n|, hex( shift )'" alias o2h="perl -e 'printf qq|%X\n|, oct( shift )'" alias o2d="perl -e 'printf qq|%d\n|, oct( shift )'" alias o2b="perl -e 'printf qq|%b\n|, oct( shift )'" alias b2h="perl -e 'printf qq|%X\n|, oct( q(0b) . shift )'" alias b2o="perl -e 'printf qq|%o\n|, oct( q(0b) . shift )'" alias b2d="perl -e 'printf qq|%d\n|, oct( q(0b) . shift )'"
What really happened there? I solved the FizzBin problem on paper to get that 810092048 number. I literally wrote out the sequence and encoded it into a number then embedded that in a program. I knew special things about the mask and the length of the sequence If I reproduced that work in code I would have solved the problem already. Not only that, I quickly realized that I was going to need a lot of bits for even a small set of divisors. But, that wasn’t the point of the exercise really.
If I wanted to do this without knowing the divisors (or the count of the numbers) ahead of time, something like this might work:
my $n = 35;
my @numbers = qw(3 5 7);
my @strings = qw(Fizz Bin Buzz);
my $count = 0;
while( ++$count <= $n ) {
state $print_count = 1;
$print_count = 1;
foreach my $i ( 0 .. $#numbers ) {
next if $count % $numbers[$i];
print $strings[$i];
$print_count = 0;
}
print $count if $print_count;
print "\n";
}
And here’s a tip for you. Find out what the Fizzbin really is. Use the original technique to answer the problem anyway that you like.