How quickly can you code this?

[Evenbit]

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.

[Evenbit]

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
end

Nathan.

[Tight_Coder_Ex]

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 start

[Evenbit]

The 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
	ret

Nathan.

[Tight_Coder_Ex]

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.

[Evenbit]

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.