7 ms·

FizzBuzz solved using only bit twiddling

65 points by gamegoblin 13y ago

robinduckett 13y ago
Aren't those bitwise operators doing the same as dividing? http://stackoverflow.com/questions/5284898/implement-division-with-bit-wise-operator http://stackoverflow.com/questions/5284898/implement-divisio...
- mcmillhj 13y ago
  essentially, but the author only claimed to solve it without division or modulo operators.
  - gamegoblin 13y ago
    I actually originally titled it "FizzBuzz using only bit twiddling" but a mod changed it...
- gamegoblin 13y ago
  The functions emulate deterministic finite automata that read binary strings and determine divisibility. See: http://stackoverflow.com/questions/15330027/regular-expression-for-binary-numbers-divisible-by-3 http://stackoverflow.com/questions/15330027/regular-expressi... http://ugccomputerscience.blogspot.com/2012/02/dfa-of-binary-number-divisible-by-5.html http://ugccomputerscience.blogspot.com/2012/02/dfa-of-binary...
petercooper 13y ago
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 https://gist.github.com/peterc/2060adac0f9cf5fb9cf3
deleted 13y ago
[deleted]
ginko 13y ago
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 https://gist.github.com/ginkgo/7201708
- jonsen 13y ago
  Also using ++ only: https://news.ycombinator.com/item?id=1383978 https://news.ycombinator.com/item?id=1383978
gmantastic 13y ago
Addition and comparison will suffice: https://gist.github.com/garethjwilliams/7202128 https://gist.github.com/garethjwilliams/7202128
- deletes 13y ago
  Awesome solution, but it breaks if you change the iteration range.
  - gmantastic 13y ago
    Yeah, you're stuck with counting up from 1, although you could tweak it to suppress the output prior to a starting point.
    - deletes 13y ago
      Here is my C solution for arbitrary positive range: http://ideone.com/a0EdtS http://ideone.com/a0EdtS
      - gmantastic 13y ago
        Nice, I get it. Here's mine tweaked - not so clever: https://gist.github.com/garethjwilliams/7210264 https://gist.github.com/garethjwilliams/7210264
gamegoblin 13y ago
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-expression-for-binary-numbers-divisible-by-3 http://stackoverflow.com/questions/15330027/regular-expressi... http://ugccomputerscience.blogspot.com/2012/02/dfa-of-binary-number-divisible-by-5.html 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...
joeblau 13y ago
I prefer the Enterprise Edition[1], this looks like it doesn't have enough boiler plate code. [1] - https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpriseEdition https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpris...
madcaptenor 13y ago
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
- smtddr 13y ago
  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,
  - GlitchMr 13y ago
    This is Python 2, not Python 3.
  - madcaptenor 13y ago
    I wanted to get everything on the same line; didn't realize the comma would do that.
    - smtddr 13y ago
      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.
      - michaelhoffman 13y ago
        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.
bloaf 13y ago
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.
- gamegoblin 13y ago
  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.
  - waps 13y ago
    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]
    - gamegoblin 13y ago
      Ah, clever! But I think >> does constitute division!
EvanAnderson 13y ago
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<
tylerkahn 13y ago
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
- GyrosOfWar 13y ago
  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.
- waps 13y ago
  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 ?
  - marekmroz 13y ago
    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 ...
    - waps 13y ago
      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.
JulianMorrison 13y ago
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.
- eCa 13y ago
  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.
  - adamtj 13y ago
    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)))'
    - pudquick 13y ago
      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 http://stackoverflow.com/a/6890045
      - deleted 13y ago
        [deleted]
draegtun 13y ago
I've posted this before on HN (see https://news.ycombinator.com/item?id=608927 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 https://metacpan.org/pod/List::Enumerator
recursive 13y ago
There are lots of ways to do this. https://gist.github.com/tomtheisen/7203110 https://gist.github.com/tomtheisen/7203110
judofyr 13y ago
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
nu2ycombinator 13y ago
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.
- gamegoblin 13y ago
  I originally titled it "FizzBuzz solved using only bit twiddling" but a moderator changed it.
GlitchMr 13y ago
.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.
- deleted 13y ago
  [deleted]
VLM 13y ago
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.
- adamtj 13y ago
  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.
jloughry 13y ago
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.
lelf 13y ago
My FizzBuzz in CSS: http://codepen.io/lelf/pen/jCwdq http://codepen.io/lelf/pen/jCwdq
dexen 13y ago
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 }
rollo 13y ago
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.
- gamegoblin 13y ago
  rem is identical to modulus for positive numbers.
turrini 13y ago
Now write that in Malbolge =D
CptCodeMonkey 13y ago
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.
nullc 13y ago
Or a little more parameterized: http://www.cydeweys.com/blog/2008/07/02/better-fizzbuzz-solution/ http://www.cydeweys.com/blog/2008/07/02/better-fizzbuzz-solu...
dnautics 13y ago
Does the ternary operator count as "if/then"?
AsymetricCom 13y ago
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.
saraid216 13y ago
Technically, he uses modulus. Technically. http://codon.com/programming-with-nothing http://codon.com/programming-with-nothing
IgorPartola 13y ago
This inspired me to explore FizzBuzz using generators in Python: https://gist.github.com/ipartola/7207829 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#UNIX_Shell http://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort#UN...

65 points by gamegoblin 13y ago

Aren't those bitwise operators doing the same as dividing? http://stackoverflow.com/questions/5284898/implement-division-with-bit-wise-operator http://stackoverflow.com/questions/5284898/implement-divisio...

mcmillhj 13y ago
essentially, but the author only claimed to solve it without division or modulo operators.
- gamegoblin 13y ago
  I actually originally titled it "FizzBuzz using only bit twiddling" but a mod changed it...
gamegoblin 13y ago
The functions emulate deterministic finite automata that read binary strings and determine divisibility. See: http://stackoverflow.com/questions/15330027/regular-expression-for-binary-numbers-divisible-by-3 http://stackoverflow.com/questions/15330027/regular-expressi... http://ugccomputerscience.blogspot.com/2012/02/dfa-of-binary-number-divisible-by-5.html http://ugccomputerscience.blogspot.com/2012/02/dfa-of-binary...

petercooper 13y ago

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 https://gist.github.com/peterc/2060adac0f9cf5fb9cf3

deleted 13y ago

[deleted]

ginko 13y ago

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 https://gist.github.com/ginkgo/7201708

jonsen 13y ago
Also using ++ only: https://news.ycombinator.com/item?id=1383978 https://news.ycombinator.com/item?id=1383978

gmantastic 13y ago

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

deletes 13y ago
Awesome solution, but it breaks if you change the iteration range.
- gmantastic 13y ago
  Yeah, you're stuck with counting up from 1, although you could tweak it to suppress the output prior to a starting point.
  - deletes 13y ago
    Here is my C solution for arbitrary positive range: http://ideone.com/a0EdtS http://ideone.com/a0EdtS
    - gmantastic 13y ago
      Nice, I get it. Here's mine tweaked - not so clever: https://gist.github.com/garethjwilliams/7210264 https://gist.github.com/garethjwilliams/7210264

gamegoblin 13y ago

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-expression-for-binary-numbers-divisible-by-3 http://stackoverflow.com/questions/15330027/regular-expressi... http://ugccomputerscience.blogspot.com/2012/02/dfa-of-binary-number-divisible-by-5.html 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...

joeblau 13y ago

I prefer the Enterprise Edition[1], this looks like it doesn't have enough boiler plate code. [1] - https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpriseEdition https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpris...

madcaptenor 13y ago

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

smtddr 13y ago
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,
- GlitchMr 13y ago
  This is Python 2, not Python 3.
- madcaptenor 13y ago
  I wanted to get everything on the same line; didn't realize the comma would do that.
  - smtddr 13y ago
    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.
    - michaelhoffman 13y ago
      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.

bloaf 13y ago

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.

gamegoblin 13y ago
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.
- waps 13y ago
  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]
  - gamegoblin 13y ago
    Ah, clever! But I think >> does constitute division!

EvanAnderson 13y ago

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<

tylerkahn 13y ago

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

GyrosOfWar 13y ago
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.
waps 13y ago
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 ?
- marekmroz 13y ago
  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 ...
  - waps 13y ago
    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.

JulianMorrison 13y ago

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.

eCa 13y ago
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.
- adamtj 13y ago
  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)))'
  - pudquick 13y ago
    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 http://stackoverflow.com/a/6890045
    - deleted 13y ago
      [deleted]

draegtun 13y ago

I've posted this before on HN (see https://news.ycombinator.com/item?id=608927 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 https://metacpan.org/pod/List::Enumerator

recursive 13y ago

There are lots of ways to do this. https://gist.github.com/tomtheisen/7203110 https://gist.github.com/tomtheisen/7203110

judofyr 13y ago

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

nu2ycombinator 13y ago

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.

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

GlitchMr 13y ago

.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.

deleted 13y ago
[deleted]

VLM 13y ago

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.

adamtj 13y ago
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.

jloughry 13y ago

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.

lelf 13y ago

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

dexen 13y ago

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 }

rollo 13y ago

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.

gamegoblin 13y ago
rem is identical to modulus for positive numbers.

turrini 13y ago

Now write that in Malbolge =D

CptCodeMonkey 13y ago

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.

nullc 13y ago

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

dnautics 13y ago

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

AsymetricCom 13y ago

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.

saraid216 13y ago

Technically, he uses modulus. Technically. http://codon.com/programming-with-nothing http://codon.com/programming-with-nothing

IgorPartola 13y ago

This inspired me to explore FizzBuzz using generators in Python: https://gist.github.com/ipartola/7207829 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#UNIX_Shell http://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort#UN...