It's a FizzBuzz question designed to "separate the men from the boys", so don't cheat. :)
Write a program that prints 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”.
Nathan.
I posted this because I consider it a "trick question" to some extent. As we hone our "problem-solving" skills, it is natural for us to attempt a clever solution. All too often, however, clever means that we spend too much time on the issue and introduce more opportunities for bugs to creep into the code. Sometimes, we don't see the obvious, simple solution. And I believe that this question is really intended to test "basic skills" rather than discover brilliance.
Here is the FizzBuzz article:
http://imranontech.com/2007/01/24/using-fizzbuzz-to-find-developers-who-grok-coding/
Notice that most of the comments at the bottom present solutions using the modulus operation and other tricks? If you attack the issue using the KISS (Keep It Simple Smarty) principle, you'll see that simple subtraction is all that is necessary.
In Ruby:
fizz = 3
buzz = 5
1.upto( 100 ) do |i|
fizz -= 1
buzz -= 1
if fizz == 0 and buzz == 0
puts "fizzbuzz"
fizz = 3
buzz = 5
elsif fizz == 0
puts "fizz"
fizz = 3
elsif buzz == 0
puts "buzz"
buzz = 5
else
puts i
end
endNathan.
Here is my version of FizzBuss and it took me 2 1/2 hrs. I've read these little
blurbs about how this is used to test potential programmers and in fact the
overall method only took me 20 seconds to determine, but utilizing instructions
that are availiable in later CPU's took a little longer.
If there is interest in this thread I look forward to seeing others optimizations
that are tighter than mine (in ASM) and would probably work on my own version
that is better.
; Written using ML
.686P
.model flat, stdcall
option casemap:none
include windows.inc
include kernel32.inc
include user32.inc
includelib kernel32.lib
includelib user32.lib
Main proto
Print proto :DWORD
.data
Prompt1 db 13, 10, 13, 10, '3 & 5s Multiples', 13, 10
db '----------------', 13, 10, 0
Epilogue db 13, 10, '-- DONE --', 13, 10, 13, 10, 0
Prompt2 db 'Fiss', 0
Prompt3 db 'Buzz', 0
CRLF db 13, 10, 0
FMT db '%4d', 0
.data?
StdOut dd ?
.code
; =============================================================================
start: invoke GetStdHandle, STD_OUTPUT_HANDLE
mov StdOut, eax
invoke Print, offset Prompt1
invoke Main
invoke Print, offset Epilogue
ret
;------------------------------------------------------------------------------
Main proc
xor eax, eax ; Intiialize working registers
mov ecx, eax
xor cx, 801H
L1: inc eax ; bump counter
cmp al, 100
ja Done ; and process till 100
invoke Print, offset CRLF ; append CRLF to previous output
shl cx, 1 ; Shift mask bits for 3's & 5's
pushfd
btr ecx, 3 ; Test bit 3 and compliment if on
jnc @F ; NC if not divisible by 3
invoke Print, offset Prompt2 ; Print prompt 'Fiss'
or cl, 1 ; Reset mask
bts ecx, 31 ; and let remainder of loop know
@@: popfd ; Restore flag from previous condition
jnc @F ; and jump if bit hasn't shifted out
invoke Print, offset Prompt3
or ecx, 80000800H ; Reset orginal mask for 5's
@@: btr ecx, 31 ; Test and reset if 'Fiss' printed
jc L1 ; If bit was on skip printing number
; Print right justifed number that is not divisible by 3 or 5
push eax
push ecx
enter 20h, 0
mov edx, esp
invoke wsprintf, edx, ADDR FMT, eax
invoke Print, esp
leave
pop ecx
pop eax
jmp L1
Done: ret ; Done
Main endp
; -----------------------------------------------------------------------------
Print proc uses eax ecx lpszText:DWORD
LOCAL Written:DWORD
invoke lstrlen, lpszText
push NULL
lea ecx, Written
push ecx
push eax
push lpszText
push StdOut
call WriteFile
ret
Print endp
end startThe first rule of code optimization is:
Eliminate conditional branches. Use lookup-tables instead.
The second rule of code optimization is:
If possible, remove any loops.
So, keeping to the KISS philosophy, here is my quick code:
; For Windows:
; nasm -f win32 -o fizzbuzz.obj fizzbuzz.asm
; gcc -o fizzbuzz.exe fizzbuzz.obj
; For Linux: (remove all "_" underscores from this source)
; nasm -f elf -o fizzbuzz.o fizzbuzz.asm
; gcc -o fizzbuzz fizzbuzz.o
section .data
one: db '1',10,'2',10,'Fizz',10,'4',10,'Buzz',10,
db 'Fizz',10,'7',10,'8',10,'Fizz',10,'Buzz',10,'',0
two: db '11',10,'Fizz',10,'13',10,'14',10,'FizzBuzz',10,
db '16',10,'17',10,'Fizz',10,'19',10,'Buzz',10,'',0
three: db 'Fizz',10,'22',10,'23',10,'Fizz',10,'Buzz',10,
db '26',10,'Fizz',10,'28',10,'29',10,'FizzBuzz',10,'',0
four: db '31',10,'32',10,'Fizz',10,'34',10,'Buzz',10,
db 'Fizz',10,'37',10,'38',10,'Fizz',10,'Buzz',10,'',0
five: db '41',10,'Fizz',10,'43',10,'44',10,'FizzBuzz',10,
db '46',10,'47',10,'Fizz',10,'49',10,'Buzz',10,'',0
six: db 'Fizz',10,'52',10,'53',10,'Fizz',10,'Buzz',10,
db '56',10,'Fizz',10,'58',10,'59',10,'FizzBuzz',10,'',0
seven: db '61',10,'62',10,'Fizz',10,'64',10,'Buzz',10,
db 'Fizz',10,'67',10,'68',10,'Fizz',10,'Buzz',10,'',0
eight: db '71',10,'Fizz',10,'73',10,'74',10,'FizzBuzz',10,
db '76',10,'77',10,'Fizz',10,'79',10,'Buzz',10,'',0
nine: db 'Fizz',10,'82',10,'83',10,'Fizz',10,'Buzz',10,
db '86',10,'Fizz',10,'88',10,'89',10,'FizzBuzz',10,'',0
ten: db '91',10,'92',10,'Fizz',10,'94',10,'Buzz',10,
db 'Fizz',10,'97',10,'98',10,'Fizz',10,'Buzz',10,'',0
section .text
global _main
extern _printf
_main:
push one
call _printf
add esp, 4
push two
call _printf
add esp, 4
push three
call _printf
add esp, 4
push four
call _printf
add esp, 4
push five
call _printf
add esp, 4
push six
call _printf
add esp, 4
push seven
call _printf
add esp, 4
push eight
call _printf
add esp, 4
push nine
call _printf
add esp, 4
push ten
call _printf
add esp, 4
xor eax, eax
retNathan.
Interesting Nathan, however your example renders the computer redundant as you've already done the calculating, therefore a word processor would have been a better choice.
I do agree with your points of optimization and size should be included in there somewhere too, but at the end of the day examples should always exemplify the computers underlying premise, in that it does the computing.
Hypothetically, we are working in an IT department and now charged with modifying our applications to be dynamic in nature. IE: operator selectable range and pairs of factors (30,000 -> 200,000 & 8's and 18's). My application may increase in size to possibly 1500 bytes, yours would be 3.7 megs 2,500 times larger than mine.
I not beginning to suggest my code is the best or even better example, but rather optimization is far more encompassing and if I were to be in an interview and the recruiter was to evaluate my abilities based on "FIZZBUZZ", I would just simply get up and leave the room.
There doesn't seem to be much interest from others, but in the spirit of competition why don't we modify our applications to be dynamic as indicated above, post our examples and maybe if we are lucky we can have others critique them.
Criteria: User defined range
User defined factors to a maximum of 12
Tabbed output ie:
1
2
3 Fizz
4
5 Buzz
6 Fizz
7
8
9 Fizz
10 Buzz
11
12 Fizz
13
14
15 Fizz Buzz
Note: digits should be right justified, formatting is removing spaces I've entered.
Interesting Nathan, however your example renders the computer redundant as you've already done the calculating, therefore a word processor would have been a better choice.
Ah, but my example stays within the specs. The question said *nothing* about the data being pre-computed or not:
Write a program that prints 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”.I do agree with your points of optimization and size should be included in there somewhere too, but at the end of the day examples should always exemplify the computers underlying premise, in that it does the computing.
Oh, but it did do the computing. I simply used the output of my previous example (with a small bit of search-n-replace) to write the code for my last example. Making use of "code-writing tools" is also a good skill to possess.
I not beginning to suggest my code is the best or even better example, but rather optimization is far more encompassing and if I were to be in an interview and the recruiter was to evaluate my abilities based on "FIZZBUZZ", I would just simply get up and leave the room.
I imagine they wouldn't be interested in testing your code-optimization skills because they'd already know/expect you have them.
There doesn't seem to be much interest from others, but in the spirit of competition why don't we modify our applications to be dynamic as indicated above, post our examples and maybe if we are lucky we can have others critique them.
Criteria: User defined range
User defined factors to a maximum of 12
Now you have changed the specs! :)
I am not optimistic about people's interest in optimization. Heck, I once had an idea that list processing (parsing) would be easier and maybe faster if I used "repne scasd" provided all the words in the list were four characters or less. However, modern processors focus on optimizing discrete coded loops -- so the old "string" instructions are sluggish. Most of the time, one will be more "ahead of the ball" by concentrating on design issues like optimal data structures, overall data flow (paying attention to cache hit/miss), and reducing complexity.
Nathan.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.