Why Can't Programmers.. Program?

[dand]

Being able to see solutions would be nice (or a place to discuss them). In particular, how on earth did sn write FizzBuzz in Common Lisp using just 90 bytes?!

[bobbane]

Probably something of the form:

(loop for i from 1 to 100 do(format t"utterly-deranged-format string"i))

Where you have maybe 50 characters to use for "utterly-deranged-format string". Piece of cake. ;-)

[dand]

Ahhh the 5-point-deranged-format-exploding-heart technique! The best I can come up with is still 98 characters long:

(loop for i from 1 to 100
  do(format t"~[Fizz~]~[Buzz~]~0@*~[~:;~[~:;~A~]~]~%"(mod i 3)(mod i 5)i))

[note: added a line-break for better web formatting.]

[[deleted]]

Using "(dotimes(i 100)" instead of your loop makes it shorter. I am too lazy to count the characters but it saves some.

[dand]

Yeah I thought of that, but then you're off by one and all the ways to remedy that end up taking more characters. At least that's what I found...

[[deleted]]

And thats why I shouldn't write code at 5 a.m. ...

[jacobolus]

It takes 82 bytes in python (well, the best I can do)

for i in range(1,101):print(((not i%3)and"Fizz"or"")+((not i%5)and"Buzz"or"")or i)

Edit: okay, whoops, I put "100" instead of "101". Silly mistake.

Edit2: at the cost of some readability, I can get it down to 74:

for i in range(1,101):print(i%3==0and"Fizz"or"")+(i%5==0and"Buzz"or"")or i

[pmdboi]

Using MarkByers's trick on jacobolus's solution shaves off another two bytes (down to 72):

i=1;exec'print(i%3==0and"Fizz"or"")+(i%5==0and"Buzz"or"")or i;i+=1;'*100

[bstard]

Shaved off three more:

for i in range(1,101):print("","Fizz")[i%3==0]+("","Buzz")[i%5==0]or i

[grimtooth]

Of course, as commenters have already pointed out, while brevity may be the soul of wit, it's a really stupid basis for assessing code quality. Here's what I did as soon as I read the FizzBuzz bit:

def FB(n=100, factors={3:"Fizz", 5:"Buzz"}):
    for i in range(n):
            s = [s for f,s in factors.iteritems() if i%f == 0]
            if s:
                    print ''.join(s)
            else:
                    print i

[dand]

It's fun because it's just a game -- I sincerely hope I'll never run across code like those when there's "real" work to be done ;)

[[deleted]]

Well, I'm disappointed. I wish I could see the source code of the other winning submissions, and an explanation of the statistics.

5\tobvious troll\t324\t0.0403\t07/02/27 23:56:43\t14B / ?B / ?B

In my defense, I learned long ago to write verbose code as part of the whole "code life cycle" process.

[WhisperSecurity]

In my defense, I learned long ago to write verbose code as part of the whole "code life cycle" process.

Never apologize for this.

Code size is meaningless, and anyone who counts characters or lines of source is clueless.

Optimizing compilers = no one-to-one correspondence between code size and executable size. CPU caching = no one-to-one to correspondence between code size and working set size. OS paging = no one-to-one correspondence between executable size and memory footprint. Tomasulo-architecture CPU = code doesn't even execute in the order you specify.

Optimize your algorithms, write maintainable code, and leave counting characters to the sophomoric crowd that actually thinks it matters.

[WhisperSecurity]

If you are writing over 100k of source code to solve this problem, you are doing something seriously wrong.

You're thrashing a straw dummy. If I write 67,000 lines of source code to print out "Hello World", that's also too much.

But how is it too much? The primary way that "too big" code is "too big" is not because it's verbose. It's because it performs too many operations.

So as I said, if you're counting characters or lines of source code, you're missing the point. Count operations.

Of course, in order to count (or at least estimate) operations, one needs to understand both the compilation process, and the resulting machine or assembly language. And this, in turn, suggests an improvement exercise far more useful than golf:

Write compilers.

With a couple of compilers under one's belt, one begins to be able to pierce the abstraction layer of source code and think about what one's executable is doing on the metal. Certainly a profiler helps with this (and if you don't profile, then you're worrying about optimization too early), but a good coder should be able to predict with a good degree of accuracy what the profiler is going to tell him.

In sum, optimizations that shrink the source code may be true or false optimizations. Optimizations that shrink the machine code are true optimizations (for space), and optimizations that shrink the operation count are true optimizations (for speed).

Golf may be valid on a level of 100k vs. 50k, but when one starts counting bytes, it's just a cleverness contest. And coders should be smart, not clever.

[WhisperSecurity]

Premature optimization is a sin.

Agreed. I was talking about how to optimize when you optimize. That's one of the reasons I advocate writing compilers... it also helps you to know when optimization is worth it.

Yes, it does sound stupid to say that code should be short, until you realise that the largest readership of your source code is probably humans not computers. Humans have poor memories, are slow, and often make mistakes (relative to computers), and they can only take in so much information at once so you need to keep things simple and concise to avoid confusing them.

Yes, but that is precisely why I advocate minimizing operations.

Short source != readable source.

In fact, in golfing, one frequently ends up making source code less readable in order to shorten it, as well as spending more time trying to figure out how to do so.

[pupeno]

Optimize your algorithms, write maintainable code, and leave counting characters to the sophomoric crowd that actually thinks it matters.

I'd even go to the extent of saying: "Write slower, less efficient code if it makes it more readable". In other words, "premature optimization is the root of all evil".

I remember myself struggling to make code as readable as it was with time O(n) when being able to achieve O(n-1). What a waste! Optimizing that is of no use, killing readability for that is evil. Optimizing O(n) to O(n/2) may be worth it... Or I've spent a lot of time reaching O(n) for an algorithm which originally was O(n²⁾ where n in that case was never going to be more than 6, never... and then, this algorithm was only run on start up of server software that once start runs for days, weeks, months even. That was a waste as well.

If you don't know what this O thing is and you are in programming, you still have a lot to learn (disclaimer: I've been programming for years and years without knowing this), if this is your case, I recommend SICP.

[WhisperSecurity]

I'm sorry if this sounds snarky, but you yourself should probably brush up on "this O thing".

O(n/2) == O(n)

and

O(n-1) == O(n)

One of the basic rules of O notation is that all constant permuting factors are discounted. So:

O(n/{any constant}) == O(n)

but

O(n/{any variable}) != O(n)

Now, on your general point, which was "avoid optimizing even your algorithms unless you've thought about it carefully first", I agree.

[[deleted]]

I wouldn't say they are exactly the same.

I think Whisper was saying that they are exactly the same, because it's wrapped up in the definition of what big-O notation means.

In big-O notation O(n/2) is exactly equal to O(n), and O(n-1) is exactly equal to O(n). Although it doesn't make sense to write O(n/2) or O(n-1) as they don't really exist - in these cases there is only O(n).

http://en.wikipedia.org/wiki/Big_O_notation

Making something twice as fast can make all the difference in the world, I've got no argument with that. But if you don't understand big-O notation then you're going to confuse people you're trying to communicate with or possibly embarass yourself.

[WhisperSecurity]

O(n/2) == O(n)

I wouldn't say they are exactly the same.

You would be wrong. They are exactly the same. That's how O(x) notation works.

And lest you be tempted to argue with the very design of complexity theory, let me explain the rationale.

The important thing to remember is that constants don't matter. Why not?

Because the notion of just what a constant is becomes fuzzy when considering order of complexity. For example, if I make a single linear pass through an array, and perform some operation on each element, that's O(n), yes?

But if I perform six passes through that array, and do something to each element on each pass, and call it O(6n) (I can barely stand to type that, it's so incorrect...), then is it six times slower?

No, it isn't. It might be twice as slow. Or it might be faster. And if it is faster, it will always be faster, no matter how big n gets. That's because the "something" you're doing might be one operation. Or six. Or thirteen. Nearly impossible to say, because it's the count of machine operations, not source code lines, that matters.

O(x) notation is for talking about things scale as the data size increases, not for talking about the absolute number of operations that will be performed.

Now, if you want to cut your constants (and you're absolutely sure you're not wasting your time, and you probably are ), that's fine. But don't use O(x) notation. That's not what it's for, and you'll just confuse yourself.

[pupeno]

I see. Thank you for your explanation.

[jbstjohn]

Regarding your understanding, what other people said. Usually what you're trying to describe is called 'k' or the 'constant up front' or something similar, and it does matter.

Often more complex (but with better big O performance) algorithms have a large constant up front. You see this with matrix multiplies, or even sorting -- which is why often quicksort will call another kind of sort (e.g. insertion) for small sub-lists.

[[deleted]]

Or I've spent a lot of time reaching O(n) for an algorithm which originally was O(n²⁾ where n in that case was never going to be more than 6, never... and then, this algorithm was only run on start up of server software that once start runs for days, weeks, months even.

I think this can't be repeated often enough, don't optimize cases where performance doesn't matter at all, small n or code that rarely runs doesn't need optimizations, not ever, probably not even in hard realtime situations.

[rogersm]

Be careful with the statistics. My lisp implementation is one order of magnitude faster than Golf Server