How is it possible to write fizzbuzz in 73 bytes of C?

October 19, 2011 4:57 AM

A number of people have posted undisclosed 73-byte C solutions to the fizzbuzz code golf challenge. How on earth are they doing that?

The shortest C solution I can find with Google is the 75-byte one on Scott Gasch's site. I have been trying to do better but at this point would rather just marvel at somebody else's cunning than let this obsession run its course :-)

Answers via memail are fine if you're squeamish about spoiling somebody else's fun.

posted by flabdablet to Computers & Internet (19 answers total)

Does it maybe have something to do with the fact that "fizz" and "buzz" both end in "zz"? Is there any optimization there?
/randomguess
posted by jozxyqk at 5:20 AM on October 19, 2011

Response by poster: Taking breadbox's beautiful 75-byte solution

main(i){for(;i<101;puts(i++%5?"":"Buzz"))printf(i%3?i%5?"%d":"":"Fizz",i);}

as a starting point, it's hard to see how splitting out the zz's would save more than it costs.
posted by flabdablet at 5:28 AM on October 19, 2011

Dropping the explicit ",i" argument to the printf, as in

main(i){for(;i<101;puts(i++%5?"":"Buzz"))printf(i%3?i%5?"%d":"":"Fizz");}

works on Xubuntu 10.10, gcc version 4.6.1 (Ubuntu/Linaro 4.6.1-9ubuntu3).

I have been a "warnings are errors" type guy for enough years that I don't remember enough about the specifics of the C specs for the stack layout, and I strongly suspect that I could make it not work with the right combination of optimization options. But that shaves off two chars.
posted by straw at 7:54 AM on October 19, 2011

Just a clarification on my disclaimer above there: I strongly suspected that dropping the explicit parameter would work, based on what I know about C and x86 assembly and the architecture in question. I would have to go back to K&R and re-read some stuff to convince myself that there was a possibility that that would work on other platforms. Like knowing how the va* macros are implemented on my platform vs thinking that that code is valid on every platform.
posted by straw at 8:09 AM on October 19, 2011

dropping the ,i doesn't work on fedora 15 (gcc (GCC) 4.6.1 20110908 (Red Hat 4.6.1-9))

(I can see how this gets maddening! Argh!)
posted by gjc at 8:30 AM on October 19, 2011

Hmmm... now I'm wondering if I was hallucinating, because I tried again and it's failing. Nevermind.
posted by straw at 8:58 AM on October 19, 2011

I have to stop now, but there might be a way to increment i more than once within the loop to eliminate the puts() statement and avoid an OR comparison. Logic is failing me at the moment on how to construct it though. We know FizzBuzz is always followed by a number, and we also know that a newline after Buzz is always right.
posted by gjc at 9:16 AM on October 19, 2011

Response by poster: That's a lovely thought, straw, but dropping ,i fails on the code golf site as well; first few lines of resulting output are

-1217253388\n
-1217253388\n
Fizz\n
-1217253388\n
Buzz\n

posted by flabdablet at 4:05 PM on October 19, 2011

A hint: according to the web site, most of the 73-character solutions are "0B / 40B / 33B" as opposed to the 74-byte solution's 39 alphanumeric and 35 symbol characters. So they have one more alphanumeric character and two fewer symbol characters.
posted by grouse at 4:39 PM on October 19, 2011

Response by poster: That's interesting. On my own Debian Squeeze amd64 box, printf(0) quietly produces no output; puts(0) segfaults as I'd expect.
posted by flabdablet at 6:28 PM on October 19, 2011

Response by poster: Just verified that submitting main(){printf(0);} to the golf server also runs with no output, while main(){puts(0);} segfaults and reports the following to stderr:

*** Segmentation fault
Register dump:

 EAX: 00000000   EBX: b7754ff4   ECX: 14089019   EDX: 00000000
 ESI: 00000000   EDI: 00000000   EBP: bfa4ff88   ESP: bfa4ff64

 EIP: b766fb11   EFLAGS: 00010246

 CS: 0073   DS: 007b   ES: 007b   FS: 0000   GS: 0033   SS: 007b

 Trap: 0000000e   Error: 00000004   OldMask: 00000000
 ESP/signal: bfa4ff64   CR2: 00000000

Backtrace:
/lib/i386-linux-gnu/libSegFault.so(+0x208f)[0xb778c08f]
[0xb7793400]
./a.out[0x8048429]
/lib/i386-linux-gnu/i686/nosegneg/libc.so.6(__libc_start_main+0xe6)[0xb7612e46]
./a.out[0x8048381]

Memory map:

08048000-08049000 r-xp 00000000 00:16 2492504    /run/shm/a.out
08049000-0804a000 rw-p 00000000 00:16 2492504    /run/shm/a.out
0822b000-0824c000 rw-p 00000000 00:00 0          [heap]
b75dd000-b75f9000 r-xp 00000000 ca:02 509292     /lib/i386-linux-gnu/libgcc_s.so.1
b75f9000-b75fa000 rw-p 0001b000 ca:02 509292     /lib/i386-linux-gnu/libgcc_s.so.1
b75fa000-b75fc000 rw-p 00000000 00:00 0 
b75fc000-b7752000 r-xp 00000000 ca:02 516115     /lib/i386-linux-gnu/i686/nosegneg/libc-2.13.so
b7752000-b7753000 ---p 00156000 ca:02 516115     /lib/i386-linux-gnu/i686/nosegneg/libc-2.13.so
b7753000-b7755000 r--p 00156000 ca:02 516115     /lib/i386-linux-gnu/i686/nosegneg/libc-2.13.so
b7755000-b7756000 rw-p 00158000 ca:02 516115     /lib/i386-linux-gnu/i686/nosegneg/libc-2.13.so
b7756000-b7759000 rw-p 00000000 00:00 0 
b7759000-b777d000 r-xp 00000000 ca:02 516110     /lib/i386-linux-gnu/i686/nosegneg/libm-2.13.so
b777d000-b777e000 r--p 00023000 ca:02 516110     /lib/i386-linux-gnu/i686/nosegneg/libm-2.13.so
b777e000-b777f000 rw-p 00024000 ca:02 516110     /lib/i386-linux-gnu/i686/nosegneg/libm-2.13.so
b778a000-b778d000 r-xp 00000000 ca:02 509369     /lib/i386-linux-gnu/libSegFault.so
b778d000-b778e000 r--p 00002000 ca:02 509369     /lib/i386-linux-gnu/libSegFault.so
b778e000-b778f000 rw-p 00003000 ca:02 509369     /lib/i386-linux-gnu/libSegFault.so
b778f000-b7793000 rw-p 00000000 00:00 0 
b7793000-b7794000 r-xp 00000000 00:00 0          [vdso]
b7794000-b77af000 r-xp 00000000 ca:02 509379     /lib/i386-linux-gnu/ld-2.13.so
b77af000-b77b0000 r--p 0001b000 ca:02 509379     /lib/i386-linux-gnu/ld-2.13.so
b77b0000-b77b1000 rw-p 0001c000 ca:02 509379     /lib/i386-linux-gnu/ld-2.13.so
bfa3d000-bfa52000 rw-p 00000000 00:00 0          [stack]

So it looks like the i386 linux libc printf() routine is explicitly coded to treat a null pointer to the format string as if it were a pointer to a null string, while its puts() is not. Also, there's no memory mapped at any address that would give puts(1) through puts(9) any hope of encountering a workable null string by accident.
posted by flabdablet at 6:48 PM on October 19, 2011

Response by poster: straw, I'd expect leaving ,i out of the printf() parameter list to work just beautifully if the compiler could be persuaded not to optimize i out of the stack frame and into a register. I have yet to find a way to convince gcc that this would be a good idea, which is a pity because combined with breadbox's null pointer to format string trick it would admit of a 72-byte solution:

main(i){for(;i<101;puts(i++%5?"":"Buzz"))printf(i%3?i%5?"%d":0:"Fizz");}

In any case, I can't see a way to specify what optimization flags the golf server should use, so that can't be what the 73-byte solutions have done.
posted by flabdablet at 7:00 PM on October 19, 2011

Yeah, I tried the puts(0) thing too, and was actually shocked that printf(0) does that. Based on grouse's suggestion I have to believe that getting rid of second %5 is the key. I've been thinking about adding something to a "FizzBuzz" string, but whatever it is hasn't popped out at me yet.
posted by straw at 7:26 AM on October 20, 2011

Response by poster: More testing reveals that printf(0) returns -1, which means that a null address for the format string is one of the errors it tests for.
posted by flabdablet at 8:30 AM on October 20, 2011

Response by poster: printf("Fizz%") outputs Fizz and returns -1. Perhaps useful?
posted by flabdablet at 8:40 AM on October 20, 2011

Response by poster: Ah! Thank you, breadbox!

Having convinced myself via endless labyrinthine wanderings that the general shape of the shortest solution absolutely had to be similar to your 74-byte one, I'd been experimenting with "Buzz"-$expr but had not yet stumbled on a workable -$expr shorter than ?:"". Having eventually twigged that precedence limited my choices of operator to / * % + - it's gratifying to learn that I was on the right track.

Using gcc (Debian 4.4.5-4) 4.4.5 at home, the 73-byte solution fails with default compilation options but works if compiled with -O3. If I use -S and look at the first few lines of assembly source, with default options I get

        .file   "argh.c"
        .section        .rodata
.LC0:
        .string "%d"
.LC1:
        .string "Fizz"
.LC2:
        .string "Buzz"

but with -O3 that changes to

        .file   "argh.c"
        .section        .rodata.str1.1,"aMS",@progbits,1
.LC0:
        .string "Fizz"
.LC1:
        .string "%d"
.LC2:
        .string "Buzz"

I wouldn't be surprised to find that the golf server uses a similar compiler.

Once again, AskMe comes up trumps... I love this site. Thanks to all who responded.
posted by flabdablet at 8:16 PM on October 22, 2011

Response by poster: Oh, and since -i* is no shorter than ?0: it's not worth pursuing a similar shortening for the printf() arguments.
posted by flabdablet at 8:19 PM on October 22, 2011

Hmmm... When I rule the world build a code golf server, there will be enough mucking about with optimization flags that tricks like this get smacked down...
posted by straw at 3:22 PM on October 24, 2011

Response by poster: Oh, come now. The whole point of having C as one of the available languages is that it's about the only one in which that particular kind of inspired hideousness is even possible.
posted by flabdablet at 8:31 AM on October 26, 2011 [1 favorite]