How is it possible to write fizzbuzz in 73 bytes of C?
October 19, 2011 4:57 AM   Subscribe

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 (21 answers total) 9 users marked this as a favorite
 
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


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


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


Posting on behalf of breadbox, via IRC just now:
Now I kinda want to post my 74-byte solution to the metafilter thread, just to share it.
main(i){for(;i<101;puts(i++%5?"":"Buzz"))printf(i%3?i%5?"%d":0:"Fizz",i);}
The difference from the 75-byte solution is replacing the "" with 0 inside the printf.
(An absolutely hideous thing to do, but it happens to work on the test machine.)
And I would be forever grateful to anyone who figures out the 73-byte solution.
(Er, and shares it.)
posted by hades at 4:20 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


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


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


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


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


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


A solution, from breadbox:
Hey -- if you like you can put your fellow metafilter minds to rest. I finally got the 73-byte fizzbuzz solution. Here it is, along with an accompanying explanation. Thanks again for pointing me at that metafilter page. I've very much enjoyed revisiting this problem.
main(i){for(;i<101;puts("Buzz"-i*i++%5))printf(i%3?i%5?"%d":0:"Fizz",i);}
The difference from the 74-byte solution is the puts argument. Years ago I experimented with the idea of replacing puts(i++%5?"":"Buzz") with puts("Buzz"-i++%5). Of course, this idea would only work if the four bytes preceding the "Buzz" string are all zeroes. As it happens, on the anarchy golf server the "Buzz" string is preceded by the string "%d", and in turn is preceded by "Fuzz". Thus the first and fourth bytes preceding "Buzz" are zero, but not the second and third bytes.

The expression (i^4)%5 will always equal 1 when i is not divisible by 5. (This is a general rule that holds when taking the modulus of a prime.) Sadly C does not have a native exponent operation, so this in itself doesn't help us. But it so happens that (i^2)%5 will always equal either 1 or 4 (when not divisible by 5, that is), which just happens to be the offsets of the zero bytes. And so we have our 73-byte solution.
NB: As he says, this is entirely dependent on how the compiler arranges the strings in the binary. It doesn't work for me on either of the systems I tried it on, but does indeed work at the code golf server.
posted by hades at 5:39 PM on October 22, 2011 [1 favorite]


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


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


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]


« Older Blogging: talk about yourself, but don't talk...   |   Rental Company Changing Their Mind on Lease Break Newer »
This thread is closed to new comments.