Anatomy of Yet Another Haskell FizzBuzz

A few days ago I was bored and stumbled across https://hackerrank.com. It’s a nice site for a programmer wanting to kill some time getting some rest from Serious Tasks. When I got even more tired and stupid, I found a task which perfectly suited my mood: FizzBuzz challenge.

Here it goes:

Write a program that prints (to STDOUT) 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”.

Pretty easy, huh? Not when you try to squeeze this task into as few characters as possible. Here comes fun!

First of all, the indefeasible winner at this task is Perl, a lot (hundreds!) of people on HackerRank managed to do FizzBuzz in a 48-character Perl one-liner. But we will not take the easy way out and I chose Haskell. Although its syntax is often used to frighten gullible imperative programmers, it definitely is not a language for code golf: strong static typing renders many implicit conversions unavailable, Prelude is quite decent, but a lot of functionality requires explicit import‘s eating precious characters, all the frobnitz with >>=, <+> and so on is just a bunch of functions that happen to have non-alphanumeric names.

My first idea was that possible options of output might be encoded with four values: the current number, “Fizz”, “Buzz”, “FizzBuzz”, so choosing a right index from [show n, "Fizz", "Buzz", "FizzBuzz"] might do the trick. So, we’ve drawn some oval, now let’s draw the owl.

A trivial implementation is to encode all checks into list comprehension. This does not play well, let’s be more creative. A quick examination reveals a pattern of 15 such values that are looping in infinite sequence. That’s what Prelude.cycle is for:

main = mapM putStrLn $ zipWith (\i -> (!!) [show i, "Fizz", "Buzz", "FizzBuzz"]) [1..100] (cycle [0,0,1,0,2,1,0,0,1,2,0,1,0,0,3])

-- the same, minified (115 symbols):
main=mapM putStrLn$zipWith(\i->(!!)[show i,"Fizz","Buzz","FizzBuzz"])[1..100]$cycle [0,0,1,0,2,1,0,0,1,2,0,1,0,0,3]

My efforts to minimize the sequence have failed: it may be represented as a string “001021001201003” – this is significantly shorter, but I have not found a short way to decode it into numbers. List comprehension are not shorter either, combining simpler sequences also does not gain anything.

Another approach was stolen from Rust’s FizzBuzz: let’s pattern-match everything:

f n = putStrLn $ case (n `rem` 5, n `rem` 3) of
    (0, 0) -> "FizzBuzz"
    (_, 0) -> "Fizz"
    (0, _) -> "Buzz" 
    _      -> show n
main = mapM f [1..100]

-- minified, 112 symbols:
main=mapM(\n->putStrLn$case(n`rem`5,n`rem`3)of{(0,0) ->"FizzBuzz";(_ ,0) ->"Fizz";(0, _) ->"Buzz"; _ ->show n})[1..100]

Not much better.

At this point I started to examine every function from Prelude to determine if it suits my needs. One of them was really what I’d been looking for: it’s Prelude.signum that returns -1 / 0 / 1 depending on the sign of its argument. That made conversion from rem result to index in the option list feasible:

-- minified original version of `signum` solution, 106 symbols:
main=mapM(\n->let s=(1-).signum.(rem n)in putStrLn$[show n,"Fizz","Buzz","FizzBuzz"]!!(2*s 5+s 3))[1..100]

-- with suggestions of danbst on Google+, 98 symbols:
s=(signum.).rem
main=mapM(\n->putStrLn$["FizzBuzz","Buzz","Fizz",show n]!!(2*s n 5+s n 3))[1..100]

At this point I hit 10.20 score at HackerRank, the only shorter solution was 97 symbols long, a single symbol less. Then I got worked-up, the mystery of the redundant symbol hooked me.

My another take was to cheat using some Unix terminal features: \r symbol moves cursor to the start of the line when printed on the terminal, so we can consequently print a current number, \r, then conditionally printing “Fizz” if the number is divisible by 3 (that overwrites the number, since we’re at the start of the line again), then conditionally print “Buzz” if it’s divisible by 5 and finally print \n. It’s a nice hack, I suppose, but that’s still a hack not acceptable on HackerRank: the server treats \r as newlines. No luck there: this piece of monad magic works in my terminal, but not on HackerRank:

-- minified, still 106 symbols:
p=putStr
w m n k=p$drop(9*rem n k)m
f n=do{p$show n;p"\r";w"Fizz"n 3;w"Buzz"n 5;p"\n"}
main=mapM f[1..100]

I spent a lot of time trying to minimize conditions: if ... then ... else is stunningly verbose, function guards require newlines and indentation. Finally I came to drop (some large-enough number * rem n k): it produces an empty string if the remainder is not 0, the whole string otherwise. I bet you could not beat this shortcut.

I had almost given up and googled other smart solutions, found this one on StackOverflow (that’s the 97 symbols solution, with proper main=). Its nifty usage of max to choose a string from show n and "Fizz"|"Buzz"|"FizzBuzz" is a real pearl which I stole shamelessly. Also I thought of avoiding “FizzBuzz” literal in my code. My previous \r-hack had shown that it’s quite possible. The drop shortcut was a real space-saver, so when I stuck it into my new effort with “FizzBuzz”-less expression I suddenly got an impressive result:

-- the winner, 89 symbols!
r n k=drop$9*rem n k
main=mapM(\n->putStrLn$max(show n)$r n 3"Fizz"++r n 5"Buzz")[1..100]

This solution is now the top Haskell solution for FizzBuzz on HackerRank with score 11.10 (which means “89 symbols”): https://www.hackerrank.com/challenges/fizzbuzz/leaderboard/filter/language=haskell

Advertisements

One thought on “Anatomy of Yet Another Haskell FizzBuzz

  1. danbst

    that is really interesting, what micro-technics are used to minimize source code

    Just to name a few:
    – pointfree transformation
    – point-semifree transformation
    – using $ instead of parentesis
    – using () instead of $ (because of priority)
    – using mapM, like “mapM(\x->putStrLn$…)LST” instead “map putStrlLn[…|x…”)

    that said, score on FizzBuzz is imporved just by copying someone else’s solution and minifiying it.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s