FizzBuzz solved using only bit twiddling | Hacker News Reader

FizzBuzz solved using only bit twiddling

gist.github.com

65 pointsgamegoblin67 comments

Another way to freak interviewers out is to calculate mod5 implement a nice circular linked list with 5 nodes, one node containing "Buzz" and the other four nodes containing null and call mod5(86) means you dance around the circular linked list 86 times and whatever string you stop on you output either Buzz 1/5 the time or null string/nothing 4/5 the time. This is hilarious if you run fizzbuzz from 0 to 100 but even funnier if you try 1000000 to 1000100

Also there's a pretty obvious conversion to recursion.

Either implementation can be even funnier if you memoize results in an array cache (so if you've already figured out the hard way that 999999mod3=0 then next time around when you check 1000000 you need not cycle all the way down to 0 for 1000000 because once you hit 999999 you already know from last time around how 999999 turned out. Bonus points for making your "cache" smaller, like implementing a LRU (or simpler) algorithm for the last several lookups rather than memoizing all one million results.

There's also a devilish way of (ab)using IEEE float arithmetic rounding errors which I forget at this moment.

If your language or a library attached to it handles arbitrary bases, there's a certain pattern to the last digit WRT multiples of 5 when expressing the number in base 5... so just to be a jerk you do the math for 3-mults in base 3, 5-mults in base 5, and your 0 to 100decimal counter in base 7 for the pure hell of it. OR amuse the interviewer because the base wasn't spec'd by running up to 100base7 (which is probably going to be a new ethernet standard soon enough).

Another fun form of rebellion is to implement an emulator for any machine language machine you can remember running simple BCD math. So here's a lame little Z80 emulator and a Z80 assembly routine to solve this using simple BCD math.

Deviant forms of trig obfuscation can be funny, essentially you rely on the trig libraries overflow behavior to dance 1/5 of the way around a unit circle each time, and when you're all done, if your angle is close enough to zero, I guess its divisible by 5. This is much funnier if you implement essentially a pentagon and then rotate it using quaternions

I think programmer brain puzzles are kind of dumb, when I was younger I would have just walked out of the room, but as I age the likelihood of a total smartass answer like above increases over time.

FizzBuzz is not a brain puzzle. It's a pass/fail weedout question. It's purpose is to determine if you are worth spending more time interviewing. If you don't know enough math to understand multiples or you don't know enough programming to write a "for" loop then that's the end of the interview. If you pass, you should then get the better and more relevant questions. Writing a Z80 emulator at that stage of the interview is a waste of time, and may itself constitute a fail depending on the interviewer.

If FizzBuzz is ever considered that humorless, I'd just walk out. Pointless questions deserve pointless but correct answers.

Not entirely pointless, assuming you don't completely screw up FizzBuzz 2.0 or whatever you want to call it, the next question was probably going to be along the lines of "tell me about a problem using recursion other than boring old factorial" or "can you do much of anything with an array" or "show me a data structure more interesting than Int X, like, say, a linked list?" or "Tell me about your time in the 3-d graphics rendering world" or "tell me about memoization and/or caching strategies" or "tell me how to use a library and its API in language XYZ where it could be an arbitrary numerical base library".

(edited to add a hilarious one: Using a unit testing framework only permit proper fizzbuzz, then feed with with 10e3 monkeys on typewriters trying to generate Shakespeare technology and trust the testing framework...)

I suppose for a low level CRUD app job knowing what modular math is and how to run a loop, aka fizzbuzz, is probably massive skill overkill but there are higher level jobs out there...

I'm racking my brain right now trying to think of a "funny" way to do fizzbuzz for a high freq trading interview as in another story on HN today. So to test mod3 you'd submit a buy order followed by two half sized sell orders repetitively all in a couple milliseconds and let the market maker routine clear the market, and orders left over, if any, would tell you if you submitted a multiple of 3 orders so you could print "fizz"?

I don't think FizzBuzz leads into interesting interview questions. That would be too dependent on the hope that the candidate does implement an overkill solution for fizzbuzz. Much more interesting questions can be derived from the problems the company is actually working on.

FizzBuzz is a simple "can you code at all" filter. If you write the obvious solution, you move on to the actual interview. If you write an elegant and amusing solution, you move on to the actual interview.

Surprisingly most applicants for programming positions cannot write any code that uses a for loop or an if statement at all, and fizzbuzz is a 3-minute test to prevent everyone from wasting their time.

    echo 1 10 Fizz 100

It's just meant as a joke. If I saw this in an interview, I would find it hilarious and impressive, but I would probably cut it off pretty early.

I had to try the linked list idea

http://pastebin.com/3rUk6yS1

Nice! I cleaned it up a little, shortened it down, got it down from 7 to 4 for loops. It is inspired by yours of course!

https://gist.github.com/euank/7206859

I've also seen people memorize a random seed that produces FizzBuzz procedurally, then use it as the basis for their program.

Also, I don't think I could write a z80 emulator on a whiteboard ;)

Completely unrelated, but are you the same Sir Cmpwn who posts on cemetech.net?

I used to, yeah.

Ah. I thought I recognized your handle. I'm Pseudoprogrammer on there. I was pretty active back in middle school many years ago. Mainly lurk, now.

Ah, fun stuff. I still work on TI stuff [1], but I don't really participate in the community anymore.

[1] https://github.com/KnightSoft/KnightOS

The main reason I wrote this was after seeing a comment on HN about unusual FizzBuzz solutions.

The f[0-4] and t[0-2] functions emulate the state of a deterministic finite automata which determine divisibility of binary strings. The bits represent the binary strings. The left shift operator is used to "eat" bits.

See these two DFAs for an explanation:

http://stackoverflow.com/questions/15330027/regular-expressi...

http://ugccomputerscience.blogspot.com/2012/02/dfa-of-binary...

EDIT:

For those showing ways to do it with just addition and the like, I originally titled this "FizzBuzz using only bit twiddling" but a mod appears to have changed it...

  fizz = [nil,nil,'Fizz'].cycle
  buzz = [nil,nil,nil,nil,'Buzz'].cycle
  (1..100).zip(fizz,buzz) {|a| n,*fb=a.compact; puts fb.empty? ? n : fb.join }

I can't claim credit for this one. Very elegant, I thought when I saw it.

One line version in Perl:

    perl -e 'print $_ + 1 . " " . ((("") x 2, "Fizz") x 34)[$_] . ((("") x 4, "Buzz") x 20)[$_] . "\n" foreach (0..99)'

Edit: unnecessary complexity removed.

python -c 'print "\n".join(w or str(i) for w, i in zip(10*[None, None, "Fizz", None, "Buzz", "Fizz", None, None, "Fizz", "Buzz", None, "Fizz", None, None, "FizzBuzz"], xrange(1, 101)))'

Not sure I appreciate a total skipping of actually doing modulus by pre-creating the repeating 15 values but oh well, I do love me some python.

python -c 'print "\n".join(w or str(i+1) for i, w in enumerate(("..Fizz..Buzz.Fizz...Fizz.Buzz..Fizz...FizzBuzz."*7).split(".")[:100]))'

If you actually want to do the math, you can make your python shorter: http://stackoverflow.com/a/6890045

  import sys
  n = 1000
  modthree = 0
  modfive = 0
  
  for i in range(n):
      if modthree == 3:
         modthree = 0; sys.stdout.write("fizz")
      if modfive == 5:
         modfive = 0; sys.stdout.write("buzz")
      if modthree and modfive:
         sys.stdout.write(i)
      sys.stdout.write("\n")
      modthree += 1; modfive += 1

That sys.stdout.write usage is interesting.

Any reason for not just using print? Or if you want all of them on the same line, you can put a comma at the end of print, like...

    for q in range(10):
        print q,

This is Python 2, not Python 3.

I wanted to get everything on the same line; didn't realize the comma would do that.

Understood. Now that I think of it, I did the same thing until someone told me about the comma. Still though, the comma-trick puts spaces in between the numbers. I don't know how to get rid of that.

You can hack the internals like this:

    print q,
    sys.stdout.softspace = 0

But really, this wart is one of the reasons Python 3 has a new way of printing.

Writing a fizzbuzz without modulo or division operators (and if-statements for that matter) isn't terribly hard when you use the fact that the fizzbuzz pattern repeats every 15 items.

https://gist.github.com/ginkgo/7201708

Also using ++ only:

https://news.ycombinator.com/item?id=1383978

I did FizzBuzz at an interview, years ago, using only addition and comparison. I mentioned, at the time, that years of 6502 assembler when I was a kid conditioned me to avoid multiplication and division whenever possible. My interviewers looked at me like I was crazy. Oh, well... >smile<

I prefer the Enterprise Edition[1], this looks like it doesn't have enough boiler plate code.

[1] - https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpris...

    .say for (('' xx 2, 'Fizz') xx * Z~ ('' xx 4, 'Buzz') xx *) Z|| 1 .. 100;

Yet another way, this time in Perl 6. It generates two infinite lists, one containing two empty strings and Fizz repeated forever. Second contains four empty strings and Buzz repeated forever. They are concatenated. Next, everything is zipped with `1..100` range using `||` operator. The `||` operator returns first argument if it's true, false otherwise. Because the range is finite, the list ends.

Functional programming for the win.

    fizz = cycle ["","","Fizz"]
    buzz = cycle ["","","","","Buzz"]
    fizzbuzz = zipWith (++) fizz buzz
    fb = zipWith (\n cs -> if cs == "" then show n else cs) [1..] fizzbuzz
    mapM_ putStrLn fb

Very cool. This really makes me want to get better at Haskell. I know enough of it to understand what's going on here, but not enough to be able to come up with something like this.

I love this answer. It's like "yes I know and hate fizzbuzz, also you don't know crap", but in code.

Poetry.

In python:

  from itertools import *
  fizz = cycle(["", "", "fizz"])
  buzz = cycle([""] * 4 + ["buzz"])
  fizzbuzz = izip(fizz, buzz, xrange(1,100))
  print "\n".join(map(lambda (x,y,z): x+y if x or y else str(z), fizzbuzz))

(bugs found by marekmroz fixed)

Can you do [1,2,3] * 4 in haskell as well ?

Funny thing is, as soon as I saw OP's solution I fired up IPython to do the same thing in Python. :)

Admittedly mine was not as elegant as I haven't thought of using izip with 3 iterables. Still, I don't think that lambda and islice is really needed... xrange(100) guarantees a finite number of iterations already.

   from itertools import *
   fizzer = cycle(['Fizz','',''])
   buzzer = cycle(['Buzz','','','',''])
   fizzbuzzer = izip(xrange(100), fizzer, buzzer)
   for f in fizzbuzzer:
       print f[1] + f[2] if f[1] or f[2] else f[0]

EDIT: the output from your version does not look right. "Fizz" and "Buzz" are on the wrong index positions. 0 1 fizz 3 buzz fizz 6 7 fizz buzz ...

heh you're right. Now I feel so dumb. Off by one error. I needed to use xrange(1, 100) instead of just xrange.

You're also correct islice is not needed.

I more gray-bearded haskell wizard than I might have a better solution, but to me the direct haskell equivalent of python's [1,2,3]*4 is

  concat $ replicate 4 [1,2,3]

Aren't those bitwise operators doing the same as dividing?

http://stackoverflow.com/questions/5284898/implement-divisio...

essentially, but the author only claimed to solve it without division or modulo operators.

I actually originally titled it "FizzBuzz using only bit twiddling" but a mod changed it...

The functions emulate deterministic finite automata that read binary strings and determine divisibility.

See:

http://stackoverflow.com/questions/15330027/regular-expressi...

http://ugccomputerscience.blogspot.com/2012/02/dfa-of-binary...

To check if a number is divisible by 3, you can sum the digits of your number. If the sum of the digits is divisible by 3, then so was the original number. (e.g. 5832 -> 5+8+3+2=18) Therefore, if you recursively sum the digits of your number until you get a single-digit number and that digit is 3, 6, or 9, then the original number was divisible by 3. (e.g. 5832 -> 18 -> 9 so 5832 is divisible by 3)

To check if a number is divisible by 5, just check if the last digit is 0 or 5.

I thought about this, but there isn't a super efficient way to extract the individual digits without modulus or division or casting to a string, unless I am missing something obvious.

Maybe you can look at in hexadecimal. Let's see. The proof for sum-of-numbers = divisibility by 3 goes as follows.

  1 % 3 = 1
  10 % 3 = 1
  100 % 3 = 1
  ...

since things congruent modulo 3 are either both divisable by 3 or neither we can do this (because 10 and 3 are relatively prime):

  (a * 1000 + b * 100 + c * 10 + d) % 3 = (a + b + c + d) % 3

Hmmm 16 and 3 are relatively prime as well, and:

  16 % 3 = 1
  256 % 3 = 1
  4096 % 3 = 1
  ...

Ergo the sum of hexadecimal digits follows the same rule in hexadecimal ! Hurray !

So :

  def divby3(x):
    s = 0
    while x != 0:
      s += x & 15
      x = x >> 4
    if s >= 16:
      return divby3(s)
    return s in [0,3,6,9,12,15]

Also, 5 works "like 3" in hexadecimal:

  def divby5(x):
    s = 0
    while x != 0:
      s += x & 15
      x = x >> 4
    if s >= 16:
      return divby5(s)
    return s in [0,5,0xa,0xf]

Ah, clever! But I think >> does constitute division!

I've posted this before on HN (see https://news.ycombinator.com/item?id=608927)

    use List::Enumerator qw/E/;

    my $fizzbuzz =
        E(1)->countup
            ->zip(
                E("", "", "Fizz")->cycle,
                E("", "", "", "", "Buzz")->cycle
            )
            ->map( sub {
                my ($n, $fizz, $buzz) = @$_;
                $fizz . $buzz || $n;
            });

    $fizzbuzz->take(20)->each(sub {
        say $_;
    });

The Fizzbuzz solution comes from the author of List::Enumerator CPAN module - https://metacpan.org/pod/List::Enumerator

Another way (using flip-flops):

    a=b=c=(1..100).each do |num|
      print num, ?\r,
        ("Fizz" unless (a = !a) .. (a = !a)),
        ("Buzz" unless (b = !b) ... !((c = !c) .. (c = !c))),
      ?\n
    end

The actual effort put in the article is reduced by this title. There are so many ways you can do this without using modulo and division. The article solved this using bit manipulation that is the main point.

I originally titled it "FizzBuzz solved using only bit twiddling" but a moderator changed it.

Addition and comparison will suffice: https://gist.github.com/garethjwilliams/7202128

Awesome solution, but it breaks if you change the iteration range.

Yeah, you're stuck with counting up from 1, although you could tweak it to suppress the output prior to a starting point.

Here is my C solution for arbitrary positive range: http://ideone.com/a0EdtS

Nice, I get it. Here's mine tweaked - not so clever: https://gist.github.com/garethjwilliams/7210264

My FizzBuzz in CSS: http://codepen.io/lelf/pen/jCwdq

A year ago a similar challenge did the rounds on Twitter but just restricting the modulo operator (not division). My solution was essentially based around b = i * 8 / 5 & 7 and (i + 2) * 6 / 9 & 1 == 1: https://gist.github.com/peterc/2060adac0f9cf5fb9cf3

This inspired me to explore FizzBuzz using generators in Python: https://gist.github.com/ipartola/7207829.

I generally hate FizzBuzz, as it seems like a waste of everyone's time in most cases. Then again, it's fun to see how you can abuse your development environment to produce it.

Now, onto seeing if I can create FizzBuzz using bash + sleep, a la sleep sort http://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort#UN...

This is perhaps the most elaborate "fuck you" to asnine interview questions. Fizzbuzz was a great acid test but now a days people who can't solve `a = 1+2; a == ?` know fizzbuz somehow.

How about solution without any explicit mathematical operations, just pattern matching on decimal notation?

  #!/usr/bin/env rc


  for (i in `{seq 100}) {
  	toPrint = $i
  	toPost = ''

  	if (~ $i *5 || ~ $i *0 ) {
  		toPrint = Buzz
  		toPost = Buzz }

  	if (~ $i ([369] [147][258] [258][147] [369][0369]))
  		toPrint = Fizz ^ $toPost

  	echo $toPrint
  }

  fizzBuzz x = if null str then show x else str
    where str  = concat [tag | (n,tag) <- tags, x `rem` n == 0]
          tags = [(3,"Fizz"), (5,"Buzz")]

  main = mapM_ (putStrLn . fizzBuzz) [1..100]

Extendable.

rem is identical to modulus for positive numbers.

Or a little more parameterized: http://www.cydeweys.com/blog/2008/07/02/better-fizzbuzz-solu...

Use a macro to generate the fully unrolled loop with only addition and iteration. Claim efficiency under conditions of branch prediction and speculative execution on IA64.

Technically, he uses modulus. Technically.

http://codon.com/programming-with-nothing

There are lots of ways to do this.

https://gist.github.com/tomtheisen/7203110

Does the ternary operator count as "if/then"?

Now write that in Malbolge =D

With this kind of self sacrifice and strive for perfection, we could see Javascript achieve VB6-like performance! The future of the web is here.

Reply on news.ycombinator.com