TopCoder, Math, and Game Programming

reiners writes "DevX.com has an interesting interview with David Arthur (dgarthur), the 2003 TopCoder Collegiate Challenge winner. Arthur discusses many interesting topics: the similarities between TopCoder problems and math problems, why TopCoder performance is positively correlated with 'real-life' programming performance, and why game programming is where the action is."

Comments

programming 3D rendering engine

[stonebeat.org]

programming 3D rendering engine. that is where all the action is. i learned more about linear algebra while writting 3D rendering libraries, then i did during the course of my degree. :)

Re:programming 3D rendering engine

[AndyRooney]

i learned more about linear algebra while writting 3D rendering libraries, then i did during the course of my degree.
Your major was Linear Algebra?

Re:programming 3D rendering engine

[NeuroKoan]

Same here. I remember more linear algebra from my 3d graphics class then I do from my linear algebra class. Then again, the 3d class was 9 months ago, the linear algebra classes were over 3 years ago. Still, I'll bet I'll rarely ever screw up normal vector computation due to all my texturing errors rather then due to missing 15 points on my LA final.

Re:programming 3D rendering engine

[RabidOverYou]

I would rather have majored in Glass Chewing than Linear Algebra. Numerical Analysis was bad, but Linear Algebra ... ooh I get the shakes.

Re:programming 3D rendering engine

[Junks Jerzey]

programming 3D rendering engine. that is where all the action is. i learned more about linear algebra while writting 3D rendering libraries, then i did during the course of my degree. :)

Although, in all honestly, most 3D rendering work is pretty cut and dried. After you've done it a few times, you realize how little there is to it, regardless of the fact the fanboys deify engine coders.

Re:programming 3D rendering engine

[insanecarbonbasedlif]

I would rather have majored in Glass Chewing than Linear Algebra.

If only... how cool would that be? "Yeah, I have a B.S. in Glass Chewing from Cal State Hayward. They have a very competative program, so I was lucky to get in. I graduated at the top of my class in the end."
"How many years experience do you have in the workfield?"
"I haven't had a formal glass chewing job yet. I did some side projects where I got to chew glass when I worked at the Oakland Waste Management facilities on Davis Street. Other than that, I have done it as a hobby for many years now, basically since I was twelve."

PHhb. All I got was a "Computer Science" degree. Most employers aren't even sure what I can do - "Are you looking to be a programmer or a network administrator or a crackaddict?"
"Okay, so I suck. I just like computers, and I want to program games, but I can't afford to live the rock star lifestyle, so I'm applying for your tedious IT job... thankyouverymuch."

beh

[Anonymous Coward]

game programming is where the action is

Then why do I always have rendering operations rather than second dates in my pipeline?

Re:beh

[allism]

If you weren't getting FIRST dates, the problem would lie in a lack of action in game programming.

Since you're not getting SECOND dates, the problem lies in...(completion is left as an exercise for the reader).

True "Top" Coders Dominate the "Bottom" Coders

[Nova Express]

Top Coder: "What? This isn't done yet?"

Bottom Coder: "No, your Code Mistressness!"

Top Coder: "You pathetic little worm! Get back in there and code until your hands bleed!"

Bottom Coder: "Right away your worshipfulness!"

Expect to see more ads for "Dominatrix" pop up in Silicon Valley...

Re:True "Top" Coders Dominate the "Bottom" Coders

[The Clockwork Troll]

Expect to see more ads for "Dominatrix" pop up in Silicon Valley...

Is Larry Ellison in the market for a new admin?

Language of Choice

[avdi]

I find it interesting that a math double-major, who's considering becoming a math professor, uses C++ as his language of choice, with Java coming second. Not Lisp, not Scheme, not Haskell - C++.

I'm not sure what conclusion to draw from that fact, I just find it interesting.

Re:Language of Choice

[Lairdsville]

a math double-major, who's considering becoming a math professor, uses C++ as his language of choice

A good friend of mine recently finished a PhD in Maths and decided to start his career in the IT industry. Having never done any computer science, he did a six month course in C++ and then a six month course in Java and found that Java was much easier for him. He said that he never felt that he fully understood C++, but he topped the class in Java. I am sure he could have done well in C++ if he had worked at it, but he has gone on to work as a very successful Java developer.

I think the Language of choice depends on the context, and the conclusion I draw from these annecdotes is that Java is good for industry and C++ is good for academia.

Re:Language of Choice

[Strudelkugel]

Someone I once new told me "If you really understand something, you can describe it mathematically."

If anything, maybe it's more interesting that that he doesn't prefer assembler. Hmmm... Maybe he will be drawn to quantum computing.

Re:Language of Choice

[larry bagina]

TopCoder cofirms it: functional programming is dieing. You don't need to be Eliza to predict functional programming's future: functional programming is dieing. Scheme is the most endangered of them all, having suffocated under a deluge of ()s. It was auctioned off to gnu/emacs, anoter charnel house, with an equally precarious future. Induction proves that the downward spiral will continue until termination.

Fact: functional programming is dead.

Re:Language of Choice

[Anonymous Coward]

you got that backwards. Academia is in love with Java.

Industry still relies on C/C++

Re:Language of Choice

[BJH]

Well, I don't know... he never mentioned that he's been exposed to anything else, just C++ and Java. Not much of a choice, if you ask me.

Re:Language of Choice

[Lairdsville]

The Universities I am involved with in Sydney (Macquarie and UNSW) seem very wary of Java. The undergraduates are generally taught C++ but not Java.

I agree that industry still relies on C/C++ and I am sure it will for a long time, but I would never recommend it over Java for general industry applications.

Re:Language of Choice

[Timesprout]

"If you really understand something, you can describe it mathematically." Exactly. Perfection = 36 24 34

Re:Language of Choice

[zatz]

TopCoder permits only Java, C++, and C#.

-- a red

Re:Language of Choice

[Billly Gates]

Well OpenGL and DirectX are both C++ based. We talking about game and graphics programming right? Its true that Java is offering some GL like libraries or wrappers but performance is not one of its strengths.

Re:Language of Choice

[g4dget]

Fact: functional programming is dead.

There seems to be a lot of life left in that corpse, given that Perl and Python have essentially become Lisp (lexical closures, dynamic typing, list comprehensions, etc.) and that O'CAML is thriving.

Re:Language of Choice

[White Shadow]

Did you read why C++ is his language of choice? The reason he gives is because it's the language he has the most experience in. In fact, most of top ranked competitors use C++ (you have a choice between C++, C# and Java). My theory on this isn't that most of them think that C++ is a better language, it's just that most of the top competitors went through school when C++ or C was being taught so they know it the best. Most (but not all) of the top ranked coders are at the ends of their undergraduate careers or older.

Re:Language of Choice

[mongbot]

Sydney Uni teaches Java *only* in the first year, and then less often in later years. Personally I think that a C++/Python (or some other scripting language) mix provides all the benefits of Java with none of the drawbacks, but I guess I'm still an undergraduate.

Re:Language of Choice

[devnull17]

Amen. In theory, C++ would be the worst of the three in a timed contest--too much housekeeping. Of course, Java's somewhat crippled by the time it takes to type in three explicit casts for every line of code you write... (:

Re:Language of Choice

[BitwizeGHC]

Well, sure. Coding C++'ll put hair on your chest. It's kinda like how athletes and Marines commit brutal hazing acts on one another to prove their manliness.

Re:Language of Choice

[Lairdsville]

If I ran the Uni I would teach Java (or Python) *only* in the last year and C++ before that.
Java hides a lot of complexity which a good programmer should understand and C++ is a good language to explore that complexity, so I would teach that first.

But you don't acually want all that flexibility when you are developing applications because it gets too complicated when you want focus on higher level issues.

C gives you just enough rope to hang yourself with and C++ gives you even more rope

Re:Language of Choice

[ethx1]

Its true that Java is offering some GL like libraries or wrappers

Do you mean OpenGL for Java?

Re:Language of Choice

[jgerman]

Kids aren't taught functional languages in college much anymore. You can go through all four years, get a degree and know very little about even imperative programming. Object Orienting caught on at schools when it was at the height of it's buzzword curve and hasn't let go yet.

I'm sure I'm not the only one working in the industry that's had to deal with poorly educated fresh out of college employees. Kids that only know one langauge, and one way of doing things.
OTOH I don't believe I learned much from college, it was the reading and coding I did on the side.

I wish when kids chose CompSci as a major, the first thing they got was a copy of Knuth, Godel Escher and Bach, the Planiverse, and the Turing Omnibus. (There are obviously others I'm leaving out for instance Programming Pearls, Hackers, ext.) I think it would go a long way towards a better Comp Sci education.

Re:Language of Choice

[sql*kitten]

I find it interesting that a math double-major, who's considering becoming a math professor, uses C++ as his language of choice, with Java coming second. Not Lisp, not Scheme, not Haskell - C++.

Clever programmers use Lisp, Scheme and Haskell.

Smart programmers use whatever language the market's hiring, and don't get caught up on language wars.

Re:Language of Choice

[Commutative Monoid]

Grueling death has a considerably larger deployment.

Re:Language of Choice

[zatz]

C++ is a terrible teaching language. A portable assembler that thinks it's an object system... what could be more confusing? Teaching systems programming is certainly apprpriate, but please, use C for that.

Re:Language of Choice

[zatz]

When TopCoder started it was Java only, and the C++ support was lousy when first introduced. I really learned Java for TC, but switched back to C++ once the environment was acceptable.

Re:Language of Choice

[zatz]

Java gets in your way a lot, compared to C++. It's only a contender in contests because of libraries like java.awt.geom.*. Also, debugging tends to be easier under Java, because of all the runtime bounds and type checking; but if you find yourself doing extensive debugging during a TC contest, you are probably screwed, whatever your choice of language.

Re:Language of Choice

[Anonymous Coward]

I think you can pretty safely assume that the reason he prefers c++ for the competition is because it's the language he knows best. In fact, he says exactly that in the article. You read the article, didn't you?

He's still pretty young and probably hasn't worked seriously in more than a couple of languages yet. Couple that with the obvious fact that he's a bright guy and it's reasonable to assume that he probably doesn't have any religious views about programming languages yet. Give him a few years and he'll probably have an opinion on the subject.

Re:Language of Choice

[richieb]

then definitely C/C++ is very appropriate as it is very fast with numerical calculations.

Well, they maybe fast but less likely to be correct. But then correctness is soooo overrated.

Re:Language of Choice

[Blakey Rat]

So, wait... I'm not entirely sure I'm following you here... are you saying that functional programming is dying?

Re:Language of Choice

[swillden]

In theory, C++ would be the worst of the three in a timed contest--too much housekeeping.

Absolute nonsense.

If you know C++ well, and use the language effectively, there is very, very little housekeeping. My C++ code probably has less housekeeping code than typical Java code, because destructors are an immensely useful tool. Toss in auto_ptr, a couple of other smart pointer types and a few design guidelines and C++ is very good at allowing you to focus on the problem, not the tool.

Plus, I never have to remember to call "close()".

Java has an edge not in the area of housekeeping (and, as you mentioned, Java is unpleasantly verbose, particularly with respect to all of the casting that is often required) but in the area of libraries. This gap isn't as large as some might think, though, because (a) many of the Java libs are rather poorly designed and make you work much harder than you should have to and (b) there are some decent libraries around for C++.

Re:Language of Choice

[kaworu-sama]

Propar grammer and speeling is DIEING! This be evan worsarer!

Re:Language of Choice

[Multiple Sanchez]

I find that LISP programmers tend to think more verbally than C++ programmers, who think more numerically. LISPies construct ideas verbally, parenthetically. C++ programmers think in a manner more closely in line with machines: operation, operation, operation. Am I making this up? In my C++/3D engine-type courses, the guys and occasional gals fit the compsci stereotype more closely: dungeons and dragons, late nights playing Quake. In my LISP courses, usually AI/GA/GP, there were a lot of guys/gals taking poetry minors.

I might add that nearly all of the C++ guys were x86ers. Among the prefix notation/parenthetical set of students, there were a lot of school-of-Jobs fanatics and I-*heart*-Woz shirts.

Or was I imagining it? Anyone else find this to be a reasonable thumbrule?

Re:Language of Choice

[AKAImBatman]

Psst... Dude, point to the live one.

Re:Language of Choice

[ZorbaTHut]

Hi. I'm one of the aforementioned top competitors ;) I use C++ because I like it better, but I've had no interest in Java because it doesn't do what I need in the contest - namely, it doesn't have any equivalent to the STL. The usual example I give for why STL rocks (and Java can't cut it) is "make an associative array from a string to an int, and make it default to 0". In C++, it's already provided - std::map does it. Java can't do it. You can't even put primitives into containers!

And I use big containers *all* the time.

Incidentally, I'm just going back to college - as an undergrad sophmore, so it's not like I'm an old fogie. :P

Re:Language of Choice

[pyrrho]

>A portable assembler that thinks it's an object system...

sounds like great praise!!!

physics is confusing, we still teach it to undergraduates.

Depends on your learning style. Personally, put me in a cloud of chaos and let the shifting forms resolve themselves.

But why C/C++ is a good learning language is because you are supposed to be learning about how computers work. As you point out, C/C++ is something like a portable assembler, this allows you to learn to think like the machine. Is it really better to learn how to think like a Virtual Machine (i.e. the machine software engineers would make if they were not too busy making software so they made it anyway)?

If the way computing machines work is confusing, well fsck, that's why you'll be around here four years child! And in fact, it's not that confusing. Confusing is being taught that computers behave like a virtual machine.

Give kids the cream niceness of high level safe scripting and interpreted languages when they have a framework to know what it's cost them. Then, they will still make that decision, but they won't try to code Corel Office in Java 1.

Re:Language of Choice

[haruchai]

And, truly intelligent programmers try to lead the market, not follow it. The market has momentum, not brains. It takes visionaries to see where the market should be led and smart, hardworking people to get it there.

Re:Language of Choice

[zatz]

Personally I don't think physics is that confusing. And it's not a fair comparison; we have a bit more control over language design than the laws of nature :)

If you read my post, I endorse C as a teaching language (although my more mathematically-inclined colleagues would doubtless prefer Lisp or Haskell). C++ doesn't model anything except itself, though. I've done a fair bit of development with it, and like Java, I mostly find it useful for the libraries. It's full of random gotchas, and doesn't possess the almost one-to-one mapping to machine instructions which C does.

Unless you do a lot of embedded or systems programming, you may as well think of the computer as a virtual machine. It certainly is one to a user process. Most software spends all its time waiting for the user, so "slow" languages are fine.

"C++: an octopus made by nailing extra legs onto a dog" -- Steve Taylor, 1998

"I *made up* the term 'object-oriented,' and I can tell you I did *not* have C++ in mind." -- Alan Kay, one of the inventors/designers of Smalltalk

Re:Language of Choice

[pyrrho]

good points. Dang it, I like the extra legs.

Also, I'm glad that C++ is open ended, it incorporated some of the ideas of OOP without becoming slave to them. It gave useful syntax for putting function pointers in structures which you can use in a very C like way. I'm glad it didn't force a whole rigid paradigm down.

Also, while I totally accept the idea that programs that wait a lot for human input (and all your other points, which are quite reasonable), I don't like the general argument that CPU time is cheap enough to waste. And I deal with people writing server applications that spend 0 time waiting for human input in Java.

Just to prove I'm not a low level cave dwelling device driver writer with no appreciation of high level solutions... I'm falling in love with Zope for quick intranet tool development.

In fact, at the risk of rambling, this is what I want... if someone wants to improve on languages like C/C++, use a different paradigm for the next higher level, something different. Creating Virtual Machines to run Imperative Languages is not the way to go, imo, except for niche products (like a Macro Language for a Word Processor, or scripting language for an extensible web server), the real problem with Imperative languages when considering general purpose development (which many think Java is ready for) for people is logic, not just memory manipulation or this or that, but logic in general, it's complicated, it gets convoluted by nature as it grows. Create systems which do not require imperitive demands. The quest for the perfect VM based language really strikes me as software engineers telling hardware engineers how hardware should work, but still sticking with the imperative methodologies they fear are the cause of our terrible track record as an industry when it comes to quality and lack of predictable development schedules.

Re:Language of Choice

[Carnivorous Carrot]

Ok, this "Topcoder" site should hire some of its own contestants to reprogram its site. Problems so far looking around:

1. Little popup that puts up the red button to enter the competition areas has the bottom line (warning about DON'T CLOSE THIS WINDOW!) chopped off.

2. Actual coding window when scrolling upward has graphic artifacts and you must highlight the scraggly area and dehighlight to make it look good.

3. Went back later, window with red button hasn't gotten as far as displaying the red button (only displaying "Java stuff loading" or whatever. Half an hour and counting.

And I'm not even looking for problems. They're leaping up and barfing in my face.

Re:Language of Choice

[zatz]

OK, I'll grant you that some modern physics seems very non-intuitive. But apparently, so was the true nature of gravity, until Galileo set us straight.

Re:Language of Choice

[zatz]

Java really isn't that slow. Also, for long-lived server processes, garbage collection is a big win.

I would like to see a native compiler offer the same sort of runtime guarantees that Java achieves with a VM, but that is a difficult task. And I agree about moving beyond imperative languages; but I think the problem is really more one of education than tools.

Re:Language of Choice

[The Cydonian]

In my LISP courses, usually AI/GA/GP, there were a lot of guys/gals taking poetry minors.

I agree.:-) (In particular, the bit about dulce and computatore. Oh, those were the days...*sigh*!)

Re:Language of Choice

[stonecypher]

> There seems to be a lot of life left in that
> corpse,

I would take that to a doctor. It seems to be a terminal lack of humor.

Things like the auctioning of languages to free software societies and the reference to Eliza as authority are generally key indicators. Also, the use of "charnel" on /. is a pretty big hint.

Also, perl and python haven't become Lisp. Lisp programmers are annoying in the same way that Perl and Java programmers are - they see all other languages in terms of their home turf.

OTOH, I'm a C++ programmer, and everyone knows why we're annoying - most of everything being broken the way it is is our fault.

"Ha, ha." - Nelson

Re:Language of Choice

[stonecypher]

> If you know C++ well, and use the language
> effectively, there is very, very little
> housekeeping

Whereas I agree with you in sentiment, because I'm a picky bastard, I would like to point out a semantic difference - it's not that there's less housekeeping, but that housekeeping can be done in most situations by the code doing the work in the first place, and therefore can be automated away when the original code is being written.

Then again, the same can be said for most modern languages, and IMNSHO, for good reason.

Re:Language of Choice

[stonecypher]

> Any language that I can't pick up in a day and
> master in a week isn't worth my time...

Which is probably why you say

> At this point they all look the same (just a
> little different syntax).

Perhaps you should consider trying a language that takes you more than a week. Or, maybe just putting more than a week into one. I've met a bunch of the Big Names, and none of them could master the hairiness of C++ in a week (this is going to draw a lot of flame; preemptive strike: you're not qualified to attack this until you've read at least the three big Meyers books (ec++, mec++, estl) ).

> Ever do OO in assembly.... it's a bitch....

Not really. Unless you're implementing polymorphism or something. Even so, though, it's not much more difficult than it would be in C; the reason it's a bitch is because you're making nontrivial mechanisms.

Also, if you're wasting your time recreating high level abstractions in low level languages and ignoring the years of optimization by hundreds of programmers in things like GCC, well, ... you can probably guess what I think of you.

Re:Language of Choice

[stonecypher]

> I'm sure you're not the only poorly-educated
> well-out-of-college employee that uses jargon
> he doesn't understand, that people with a
> genuine education in CS have had to deal with.

Oh, be careful. There are a lot of schools that have IS or usage curricula which pretend they're CS curricula; many CS graduates don't have the faintest clue what to do with Knuth. I know a bunch of degree-holders that don't realize that CS is basically a math degree.

In short, you're assuming a particular type of ignorance. There are many forms of ignorance this cat could be displaying.

Re:Language of Choice

[stonecypher]

> Clever programmers use Lisp, Scheme and Haskell.
>
> Smart programmers use whatever language the
> market's hiring, and don't get caught up on
> language wars.

Clever programmers use something new every eight months. Employed programmers use whatever's being hired for. Smart programmers use whatever language suits the job best.

Language wars may be stupid, but language selection isn't. You translate an unknown natural language with Prolog. You build web services with PHP, perl, lisp, xslt. You build embedded applications in C++, C, or in extreme cases assembly.

You do not write embedded Scheme, ml for the Web, or Prolog to keep simple databases.

And besides, there is Only One Truth (tm) to language wars: Java Sucks.

"During National Brotherhood Week..." - Tom Lehrer

Re:Language of Choice

[stonecypher]

> Anyone else find this to be a reasonable
> thumbrule?

Generally in the case of a programmer which knows one and not the other, yes. And to know a language isn't to be able to write it, manual in hand, but rather to have used it for four years to do things it wasn't meant to for a PHB that doesn't know dick.

(IE, to be my coworker. Grumble.)

If a programmer knows both, they'll use idioms from either in the other. What you're seeing are language tendencies being embodied in programmers which don't have alternatives, IMNSHO.

good thing

[Anonymous Coward]

I guess all this experience will really pay off when someone is looking for a coder to solve mundane problems over and over really really super fast. Or maybe they make game shows out of perl hacking. Oh wait, he says he may get a math career when he graduates. Those certainly are plentiful. Maybe there is some kind of speed math problem think tank that secretly controls the world around us. Well, lord knows whatever happens super fast programming competitions sure are great things, i mean, wow!

Re:good thing

[SamBeckett]

hehe you must have scored REALLY bad on the competitions to have this kind of attitude. From my experience, I have a relatively average score (~1400) and have nothing but the utmost respect for the true "top coders". Being fast is just one part of it, algorithm knoweldge and language mastery is a must-have to be competitive like these guys are.

Re:good thing

[zatz]

Speed is really just a tie-breaker after correctness in TopCoder and ACM contests. It's not a contest to write *crap* quickly... the fastest coders usually have the most readable and robust code (a couple C++ users in the TC top 10 excepted).

Re:good thing

[Anonymous Coward]

Yup. There wasn't a challenge. I did them for awhile. When they used to pay for all competitions, I learned it was better to stay in the bottom ranks. There you could take a room on one question, the easiest because all you needed were language tricks. When it was just Java, this basically meant that you learned all of java.util and java.lang packages. Basically my strategy boiled down to this:

1. Read the easy question.
2. Recall the Java class/method that shortcutted the problem.
3. Write 3-5 lines of code (not including the class and method header).
4. Score near max points and be done before everyone else and sit for the rest of the round.
5. Challenge round, slam the people that tried to finish as fast as you. Chances are these people made a mistake and if you knew the problem, you knew what to look for right away.

Most of the time I'd also just open the last two questions so I knew what to expect if someone did finish them, but the bulk of the people in the lower rooms would never even get to finish them in the allotted time, if they did, you could almost always count on it being wrong. So long as I didn't answer the big questions and let my scores inflate, I never moved out of those rooms and I never saw a point in it. The only point I saw in getting to the higher rooms was to make the invitational. Yeah I'd love to win $100,000 but at 1 in 64 kids (back a year and a half), my odds weren't that good anyway even if I thought I was talented enough to win (which I know I'm not).

This is not real world coding and I would NOT encourage colleges to become involved in Topcoder because most of their philosophies go directly against what professors are trying to instill in up and coming programmers. You are not encouraged to design, comment, test or even read the problem thoroughly in these competitions because it all costs you valuable points. Whether or not these are valuable skills in the real world, I'm still growing up and learning.

Re:good thing

[White Shadow]

Mundane problems? Topcoder problems are much more interesting than say, laying out a GUI for your application or programming some design specs that your boss created. Most people I know who compete in Topcoder do it because their day job or their classes don't provide interesting problems. Topcoder contests are fun to compete in. Have you tried competing before? You might find out you enjoy it. The next single round match is next Thurday.

Re:good thing

[ErroneousBee]

hehe you must have scored REALLY bad on the competitions to have this kind of attitude.

I did a 'sort of' competition thing (it was actually a study in how programmers program), and I found that the problem was nothing like what I meet in the real world:

• The spec was really watertight, not 'Uh, make it show birthdays, and, uh, see if the users like it'.
• There were no OSINTOTs or other gotchas like broken APIs or liscencing issues.
• The spec didnt change halfway through the task.
• No-one dumped a completely unrelated, but more urgent, task in my lap just as I was about to start coding.
• QA didnt suddenly start bitching about a feature thats been in the product for years, but theyve only just noticed, and no-one uses anyway.
• The problem was chosen for its elegant recursive solution. Most of my real world problems are solved by a tiny bit of iteration and masses of conditional logic/exception handling dealing with all the dumb things the user/system can get up to.

In general, I suspect these competitions reflect academic computing, producing nice and small programs. The real world is more like Google's pagerank software, a simple idea, but complicated by all sorts of issues like Bloggs and Googlebombers.

Re:good thing

[jgerman]

change halfway through the task

Wow you're being generous. My favorite is when it changes hourly.

Re:good thing

[DuckDodgers]

Hey... are you in the cube next to me? This sounds awfully accurate. :)

Re:good thing

[bestguruever]

It is much more fun when there are multiple specs each of which affect benefits different upper managers' metrics. Then you get to play process and business analyst while trying to figure out which of the managers is most likely to succeed in getting you canned

Real World vs. Top Coder...

[Xerithane]

Uh, you are asking a student who has held an Internship. His points are fairly valid:

• Test your code
  
• Make it readable
  
• Spend time designing
  

Those 3 don't happen as much in the real world as one would hope to think. Very few companies do code reviews correctly, nor do most programmers spend enough time testing their algorithms.

I would look at a Top Coder victor the same way I would look at someone who can answer trivia questions correctly. The experience is incredibly valuable, but I wouldn't say that they are parallel at all. Most of the questions and tests are biased against people who have experience doing competitions. A veteran programmer would probably perform 10x better in a real world environment, and is much more valuable than a TopCoder winner who is still in school... but I could be wrong.

Re:Real World vs. Top Coder...

[targo]

I would look at a Top Coder victor the same way I would look at someone who can answer trivia questions correctly. The experience is incredibly valuable, but I wouldn't say that they are parallel at all. Most of the questions and tests are biased against people who have experience doing competitions. A veteran programmer would probably perform 10x better in a real world environment, and is much more valuable than a TopCoder winner who is still in school... but I could be wrong.

Actually it's not as simple as that. In order to be successful in TopCoder competitions, one has to be a rather smart person (in fact the 2001 winner is "the smartest guy in the world"), with good analysis, generalization and abstraction skills, and above all, a quick thinker. The problems are not trivial to dissect, and time pressure is strong.
So for a long term employment (3+ years), I would rather hire a young successful TopCoder participant (one can always gain experience but not smarts) than a regular but experienced guy.

Re:Real World vs. Top Coder...

[Xerithane]

So for a long term employment (3+ years), I would rather hire a young successful TopCoder participant (one can always gain experience but not smarts) than a regular but experienced guy.

I'd agree, but I also wouldn't expect the TopCoder to stick around at a job for 3 years. Unless it was a very challenging job (Like game development, or scientific research in their area of interest.)

Re:Real World vs. Top Coder...

[Xerithane]

So for a long term employment (3+ years), I would rather hire a young successful TopCoder participant (one can always gain experience but not smarts) than a regular but experienced guy.

Sorry for responding twice, but I just had another thought... I would think a TopCoder participant/winner would be more apt to re-invent the wheel than find an existing solution. While often times, re-inventing the wheel is a good solution, it is still unnecessary and adds too much onto the development time.

Whether it's from A) Lack of experience, B) Arrogance, or C) the "Neat" factor it still is an undesired approach, unless their is something seriously lacking about the existing alternatives.

Re:Real World vs. Top Coder...

[zatz]

That guy did not, in fact, win the 2001 TCCC.

Re:Real World vs. Top Coder...

[zatz]

I've been working a relatively undemanding job in a shop full of scripters for a couple months now. The only thing that makes me want to leave is the condescending attitude they have towards their clients.

-- a topcoder

Re:Real World vs. Top Coder...

[zatz]

A coder who knows how things work all the way down to the bare metal is sometimes very valuable. And just because a person likes to rewrite things doesn't imply they cannot make an appropriate decision when a deadline is involved.

Also, there are some wheels out there that really *should* be reinvented.

Re:Real World vs. Top Coder...

[Wavicle]

After doing a quick (and probably inadequate) analysis the TopCoder problems and Java solutions from the web page... I'd say one primarily must be very good at un-learning much of what algorithm analysis has taught them to be successful in the TopCoder competitions.

Take for instance the Java solution to the DQuad problem... If I'm reading it correctly, it constructs a 2D array representing the directed edges and then does an exhaustive search against it to find the solutions. That's what I think the "return res/4;" at the end is for, when the code has reached that point it will have counted all valid solutions 4 times over. I believe also that the time complexity of this solution has a big-O of 2^n.

It may be that the problem is in NP, in which case all solutions would have that kind of time complexity, I haven't looked carefully enough at it yet. I'd find it rather ludicrous of those running the competition to introduce an NP problem though.

In the real world of computer science, we look for solutions that run in optimal time, not solutions found in optimal time. I'm not convinced that TopCoder translates well to the real world (yes that may be a bit hasty having seen only one example).

Re:Real World vs. Top Coder...

[jareds]

First, it's typical for the easy problem in TopCoder competitions to be brute-forceable. Harder problems usually aren't (there is a running time constraint).

Second, in the real world one does not look for solutions that run in optimal time, but rather for the appropriate trade-off between development time and running time.

Third, you really shouldn't be casting aspersions on others' ability to analyze algorithms. It should be obvious that four nested for loops do not take exponential time to run, and that there are not even an exponential number of possible quadrilaterals to test in the first place. Although the problem isn't NP-hard, as the given solution runs in time O(n^4), if you can do better than brute force on it, you can also do better than brute force at finding 4-cliques. (However, that may not imply anything interesting, though it is intuitively somewhat suggestive.)

Fourth, there's nothing ludicrous about having an NP-complete problem. I recall one competition where the hard problem was NP-complete, but given the problem constraints the way you could solve it was coming up with a O(2^(n/2)) solution rather than a O(2^n) solution.

At any rate, TopCoder is ultimately a coding competition, not a competition in asymptotic running time.

Re:Real World vs. Top Coder...

[doinky]

Damn straight; the first thing superstars need to learn out of college is that most of the time, there's a guy with pointy hair in the way of what they'd REALLY like to do with the code. That's why only companies run by idiots hire people who wouldn't be happy with jobs that only occasionally challenge them.

Re:Real World vs. Top Coder...

[Wavicle]

it's typical for the easy problem in TopCoder competitions to be brute-forceable

I'm assuming there is an assumption about the maximum input size the easy problem would be given? Even at "only" n^4, having just 100 nodes in the graph produces 100 million possible four-cycles that must be considered. I pick 100 because it seems like a fairly round number on the low end of what one might see in a network flow / flight path / circuit problem.

in the real world one does not look for solutions that run in optimal time, but rather for the appropriate trade-off between development time and running time

I think in the real world an n^4 solution would be placed on the back burner until time has been spent considering better ways, or pruning n^4 down with some small coefficient.

you really shouldn't be casting aspersions on others' ability to analyze algorithms

I didn't. Re-read what I wrote. I said they have to be good at unlearning what those classes teach. I don't know what Duke University teaches in those classes, but the ones I took were an exhaustive discourse on methods of finding optimal solutions, generally ones that run in n, log n, n log n or at worst n^2.

It should be obvious that four nested for loops do not take exponential time to run

True. At that late hour I was probably extrapolating the problem to how many n-cycles exist, which is 2^n, but in this case n=4.

there's nothing ludicrous about having an NP-complete problem

If your problem is truly np-complete, then you must have a small data set or your running time will get intolerably long.

At any rate, TopCoder is ultimately a coding competition, not a competition in asymptotic running time.

My interpretation of the intent of the parent posts was that TopCoder has applicability to the real world. Based on this example, and one of the parent posts, I was agreeing that the skill set one needs for TopCoder are significantly different because as this example showed a "good" solution for TopCoder should be a solution of last resort in professional programming.

You should be able to easily optimize the whole thing down to a theta of 0.25*n*m^3 where m is the average number of edges between nodes. In most cases m<<n, but in the worst case m=(n-1) and the algorithm will take n^4. There are probably better cases, but that's my "less than half an hour" stab at the problem.

Re:Real World vs. Top Coder...

[lars]

I didn't. Re-read what I wrote. I said they have to be good at unlearning what those classes teach.

I don't think there's any need to "unlearn" things. It's just common sense to implement the simplest algorithm that will do the job. Sometimes you do need a very efficient algorithm, other times you don't.

One of the first things you normally do before you begin to solve a contest problem is determine the worst time and space complexity you can get away with. Then you look for an algorithm with those complexities; hopefully a dumb one that's easy to implement. Sometimes the limits on the input even give you a clue about what kind of algorithms to consider.

I think TopCoder strikes a very nice balance between practice and theory. The problems are usually superficial and closer to what you'd see in an algorithms class. You have to be able to come up with a solution quickly. If you don't have an idea in mind when you've finished reading the problem then you're already playing catch-up. Then there's the matter of implementing your solution quickly! You have to make good decisions on the fly the whole time, and you can't afford to make mistakes. If you do have a bug, you have to find it and fix it within seconds. Every compile costs you points. And of course, you have to be very careful to consider all corner cases and test them, so that you don't lose your solution to some silly oversight.

At all the real-world places I've worked, good decisions, few errors, and being able to work under pressure are all considered highly desirable qualities in a developer.

If your problem is truly np-complete, then you must have a small data set or your running time will get intolerably long.

That's true for many problems in P, too, depending on your definition of "small". There are plenty of algorithms for NP-hard problems that can handle input sizes just as large as a low-order polynomial algorithm can in the 8 second time limit TC enforces. For instance, GSAT can solve difficult 3-SAT instances with several hundred variables in seconds.

Re:Real World vs. Top Coder...

[jareds]

I'm assuming there is an assumption about the maximum input size the easy problem would be given? Even at "only" n^4, having just 100 nodes in the graph produces 100 million possible four-cycles that must be considered. I pick 100 because it seems like a fairly round number on the low end of what one might see in a network flow / flight path / circuit problem.

If you read the problem, the constraint is 50. Consequently, it's a brute-forceable, easy problem, as I said. The point is that you have 8 seconds for the solution to run on any given input, so the input constraints will determine whether the problem is brute-forceable.

I didn't. Re-read what I wrote. I said they have to be good at unlearning what those classes teach. I don't know what Duke University teaches in those classes, but the ones I took were an exhaustive discourse on methods of finding optimal solutions, generally ones that run in n, log n, n log n or at worst n^2.

I claim that if you need to unlearn algorithms classes to write programs that run in worse than n^2 when no n^2 solution is feasible, you've really let the classes mess you up.

My interpretation of the intent of the parent posts was that TopCoder has applicability to the real world. Based on this example, and one of the parent posts, I was agreeing that the skill set one needs for TopCoder are significantly different because as this example showed a "good" solution for TopCoder should be a solution of last resort in professional programming.

The example showed a good solution to an easy problem. It doesn't show much about the skill set needed because you need to solve more than easy problems to do well. And yes, if a simple brute force solution will run in the time allotted, it is best in TopCoder to use that solution, but that's why the problem constraints are generally such that you can't brute force the harder problems.

You should be able to easily optimize the whole thing down to a theta of 0.25*n*m^3 where m is the average number of edges between nodes. In most cases m<<n, but in the worst case m=(n-1) and the algorithm will take n^4. There are probably better cases, but that's my "less than half an hour" stab at the problem.

What does "most cases" mean? In a graph selected uniformly at random from graphs of size n, m will be n/2 on average, and your algorithm will take time Theta(n^4). Your solution is brute force too, albeit one that's more efficient by a constant factor. You're just brute forcing using edges rather than vertices, if you're doing what I think. My stab at doing better than brute force showed that it's equivalent to counting 4-cliques.

Re:Real World vs. Top Coder...

[eglamkowski]

Unless it was a very challenging job (Like game development,

Um, there is a HUGE amount of grunt coding in game programming. Coding the GUI, writing a script parser, or processing keyboard clicks ain't challenging. But you only need just so many programmers on a given project to write the graphics engine or the AI or do other "challenging" work. (well, of course the AI will absorb as many programmers as you want to throw at it, but for a game that will actually ship...).

Having been a game programmer for five years, I have to say that Slashdotters seem to have some very strange ideas about game programming... :-p

Re:Real World vs. Top Coder...

[Xerithane]

Um, there is a HUGE amount of grunt coding in game programming. Coding the GUI, writing a script parser, or processing keyboard clicks ain't challenging.

I should have clarified this I guess... Game Development is not the Application Development. I think games have two pieces: The Application and the Game. Application is just application development.. it's not like you really have to work the phsyics of a button being clicked ;)

Having been a game programmer for five years, I have to say that Slashdotters seem to have some very strange ideas about game programming... :-p
Yes... it's kind of like this holy grail of programming for a lot of people. You interested in working on a sprite-based (think Chromium BSU) SDL/GLUT OpenGL game? Could use the extra help... got an artist on board who is freaking awesome.

Re:Real World vs. Top Coder...

[eglamkowski]

You interested in working on a sprite-based (think Chromium BSU) SDL/GLUT OpenGL game? Could use the extra help... got an artist on board who is freaking awesome.

I haven't worked with OpenGL, but I'd be willing to give it a shot :-)

Re:Real World vs. Top Coder...

[Xerithane]

I haven't worked with OpenGL, but I'd be willing to give it a shot :-)

Cool :) I haven't worked with OpenGL since... 1997. My buddy wrote Chromium BSU, so I'm going to gracefully borrow his framework code for it. For a proof-of-concept/easier game I'm going to code up a quick little TankWars game with the framework. I need to abstract out a little bit of his code (It's already really clean/abstract, just want to touch up some points) so I'll setup a site (probably games.nerdfarm.org) for it as well... do you read journals?

Re:Real World vs. Top Coder...

[eglamkowski]

Xerithane you knob :-) You're on my friends list! Of course I read your journal :-D

Re:Real World vs. Top Coder...

[Xerithane]

Xerithane you knob :-) You're on my friends list! Of course I read your journal :-D

I knew that, I just wasn't sure if you actually read them or not :) A lot of people are on my fan list that don't read (or don't post... not sure which :))

how about encryption?

[qortra]

It really depends on how you define "action". Encryption seems to me to be even more exciting a field. It isn't as glamorous as game programming, but the math involved is amazingly interesting (advanced number theory, primality), and good encryption tends to last for longer than good game engines.

3D rendering is not entirely about math (probably a lot more to do with studying the brain and how people generally interpret images that they see). Encryption however is ALL math. Anyhow, that's my 2 cents.

Re:how about encryption?

[Ryu2]

Yes, it's actually quite math-heavy -- the obvious linear algebra, and geometry for the graphics part. And since a 3-D world wouldn't be very interesting without things that move about and obey the laws of physics, add calculus, differential equations, and numerical analysis to the mix.

There's lots of math to challenge any math lover -- it's just a different kind than that used in encryption. If you hate math, you won't be a good graphics programmer.

Re:how about encryption?

[plierhead]

Hah, encryption, I spit in your face !

Payroll processing is where the action is. COBOL rocks! And you'll score loadsa chicks.

Re:how about encryption?

[devnull17]

Have you read anything about 3D rendering? It's all math, at least in the mainstream areas of the field--perhaps in the old days, when techniques hadn't been perfected, math might not have been such an issue. I don't know much about ray tracing, but I can tell you that the polygonal engines used in virtually all games today are nothing but linear algebra and multivariate calculus. Stereoscopic rendering, which seems to be making a bit of a comeback (there's support for it in D3D as of a release or two ago), is slightly more neurological in nature, but I think that's about it.

While engines themselves might not last long, that has more to do with the capabilities of computer hardware than anything else--vector transforms, quaternions and the like haven't changed since they were first discovered long before the era of modern computing.

Re:how about encryption?

[grazzy]

and not just that! you have a raise every month!

Re:how about encryption?

[kaworu-sama]

...and good encryption tends to last for longer than good game engines.

Thats because game programming is a field that develops much faster than encryption. It has more of a market, compared to encryption.

Why am I not surprised ...

[1in10]

Wow, someone who won top coder is saying it's a good indication of real world ability.

In other news, Microsoft says Windows is the most reliable, and George Bush says America is the best.

Re:Why am I not surprised ...

[zatz]

Well, it measures *something*. I would love to have most of the people I know from TC onsites as coworkers. Keeping them motivated on dull projects would be difficult, of course.

Re:Why am I not surprised ...

[tankdilla]

it's a good indication of real world ability.

After being in the real world for a year, some people act like they don't know how to think on their feet. All of those analytical skills do come in handy when dealing with people who find it hard to just think about stuff for a minute.

Translation...

[Duncan3]

In other words he's smart enough to know even he can't get a job programming, and so it's a waste of his time to try.

A friend of mine hired two AMERICAN programmers for 6$/hr last week. I told him he could get them for $4/hr in India, but he doesn't like remote workers.

The party is over. Move along.

Re:Translation...

[DigiShaman]

"Wow $6/hour is the going rate huh. Guess i'll stay at McDonalds where the money's at." Face it! Competition is nasty out there. If all jobs pay the same shit wage, might as well do what you like. I would rather work on PCs and trouble shoot them at minimum wage then get payed 6 bucks an hour at Micky Ds.

Re:Translation...

[stanmann]

If I'm just making $6 an hour w/ no benefits, I'm going to find someplace where I'm doing $6 an hour of work, and thats flipping burgers... no mental strain, and I stay in decent shape on my feet. As long as I shower twice a day, I will even smell presentable. I love programming and hardware tinkering, but doing that for someone else with vague requirements and lack of understanding of the problem and solution, NOT worth $6 an hour

First day on the job:

[eidechse]

DevLead: Make a dialog with a tab control.

SuperFastAlgorithmProblemSolver: Huh?

;)

Re:First day on the job:

[zatz]

What a waste of a good programmer that would be. "Write the underlying code for all dialog boxes" or "make a tool that lets average developers crank out GUI code faster" might be more fitting uses of her time.

Nope...

[Anonymous Coward]

You now know matrix and vector arithmetic, not linear algebra. Can you explain how a vector normal computation relates to an operator's spectrum? Linear algebra is not about matrices and vectors but rather the mathematical structure they follow. Vectors are a nice, simple example. Another example is the continuous real functions on a compact set. Another is real functions whose measure obey certain properties. These all behave similarly, and that is linear algebra.

Re:Nope...

[NeuroKoan]

You now know matrix and vector arithmetic, not linear algebra. Can you explain how a vector normal computation relates to an operator's spectrum? Linear algebra is not about matrices and vectors but rather the mathematical structure they follow. Vectors are a nice, simple example. Another example is the continuous real functions on a compact set. Another is real functions whose measure obey certain properties. These all behave similarly, and that is linear algebra.

Good point. I guess what I was really trying to get at was, its hard for me to learn something conceptually without pratical application. Learning a pratical application for vector and matrix multiplication has helped me far more then any book work, lecture or test. I guess I'm just too much of a utilitarian engineer for my own good.

Re:Nope...

[Pig Bodine]

True for sufficiently broad definitions of "linear algebra". People who favor a narrower definition might reasonably say that what you are talking about is operator theory or functional analysis. For a lot of people "linear algebra" implies finite dimensional.

Re:Nope...

[Carnivorous Carrot]

> Good point. I guess what I was really trying to
> get at was, its hard for me to learn something
> conceptually without pratical application.

Oh, I don't know. Most Slashdotters pick up on masturbation readily enough.

David Arthur

[Anonymous Coward]

David went to my highschool, Upper Canada College (Canadian version of Exeter/Eton), and he was a couple grades below me.

Sadly, he had the misfortune to be at the school while the Canadian High School Math champion was there so he didn't get much glory in the math department.

He is a smart dude, but was incredibly socially inept :) i.e. No girlfriends. Maybe university has changed him now, I dunno.

Anyways, he wrote a complete 3d FPS game in ~ grade 10 . He also crushed everyone in the Waterloo CS contests.

Re:David Arthur

[zatz]

I spent a little time in person with him at ICPC 2002. He seemed perfectly sociable to me.

Re:David Arthur

[HoldenCaulfield]

hmm, I spent some time with him at the top coder thing, and "perfectly sociable" isn't quite how I'd describe . . . not socially inept, but there are just a bunch of little things (weird laugh, some odd comments, very techie, etc) that make him stand out a bit . . . take that how you may . . .

Arguably though, we all have those little things that someone doesn't like about us, so perhaps David and I were just slightly opposed . . .

Re:David Arthur

[zatz]

I am probably also guilty of having a weird laugh and making odd comments :) Dave was memorable, but didn't seem particularly impaired socially. The party was usually in his team's hotel room, as I recall.

Re:David Arthur

[lars]

I agree; this thread is ridiculous and kind of sad. A lot of people confuse having social skills with fitting in. It is well known that people who are very intelligent also tend to have excellent social skills and a good sense of humour. If anything, too good -- that's the real reason they might not fit in so well. Both times I've met Dave I've found him to be outgoing and impossible not to get along with. Socially awkward is me or most of the fellow grad students and profs I work with.

Re:David Arthur

[GlassHeart]

It is well known that people who are very intelligent also tend to have excellent social skills and a good sense of humour. If anything, too good -- that's the real reason they might not fit in so well.

Hmm?

Social skills are measured by how many human situations one can harmoniously fit into. For example, if you're well liked among geeks, jocks, and bikers, then you might have good social skills. If you're only accepted among geeks who play a particular board game, then you might not have very good social skills. I don't understand how or why you are separating the two.

(I don't know who David Arthur is, and I'm not talking about him.)

nobody talks about the actual problems?

[lingqi]

well after 69 comments (hehe), there has not been a SINGLE one discussing the competition problems, all three of which are quite interesting.

especially the hard one, probably, because my mind is drawing a blank on how to have it implemented... (no i didn't cheat and look at the solution).

heh, actually they go like this:

*easy* - okay, i can think of a algorithm. probably not the fastest thing in the world, but it should work out.
*medium* - have a haze of an idea on what an algorithm might look like. with enough caffine it MIGHT solidify.
*hard* - at least I understand the problem, but curses on the restrictions of a binary tree =)... no idea on algorithm that would finish executing before the end of the universe. (granted, only 50 elements, so maybe it's possible brute-force)

Damn; this is exactly how /. lowers productivity. making people spending way too much brain power on stuff that's completely unrelated and time consuming. heck; i might lose sleep over this.

Re:nobody talks about the actual problems?

[cpeikert]

well after 69 comments (hehe), there has not been a SINGLE one discussing the competition problems, all three of which are quite interesting.

I'll take a shot.

Ironically, I find the "easiest" one the hardest. I can think of a brute-force O(n^4) algorithm, but it's not pretty.

The medium problem seems to be straight-up dynamic programming.

Sadly, the "hard" problem is also straight-up dynamic programming, and is well-known. It's very lame that they chose this problem -- I'm pretty sure it's in CLR (Cormen, Leiserson, Rivest "Introduction to Algorithms"), and it's definitely considered in many other sources.

Overall, these questions don't seem to be testing for breadth of knowledge, or even ability to think creatively. They all have essentially cookie-cutter answers.

Coding up correct answers under time pressure is another matter, of course. I give all the credit in the world to someone who can crank out the code and test out all the corner cases properly.

Re:nobody talks about the actual problems?

[White Shadow]

Actually, you're right, these problems weren't that hard. In fact, three of the four finalists finished all the problems in about 40 minutes.

There was actually a problem (a switch died, then the backup switch died) during the final round and they had to cancel the match. The question here are actually a second batch of problems.

The hard problem from the first back was a get the animals across the river problem. Given a set of up to 16 animals and what animals can't be placed on a boat together, find the minimum number of trips it takes to get all the animals across the river. Oh yeah, the animals also have weights and if the weight of the animals on the boat exceeds a certain threashold, you can't transport them.

Re:nobody talks about the actual problems?

[cpeikert]

Given a set of up to 16 animals and what animals can't be placed on a boat together, find the minimum number of trips it takes to get all the animals across the river. Oh yeah, the animals also have weights and if the weight of the animals on the boat exceeds a certain threashold, you can't transport them.

Neat - when you say "what animals can't be placed on a boat together," do you mean "what animals can't be left alone together?" I'm thinking of the classic problem of the farmer with the chicken, grain, and fox. The farmer can only take 1 item with him at a time... but if he leaves the chicken and grain together, the chicken eats the grain, etc.

If that isn't what you mean, that one would make a nice problem too :).

Re:nobody talks about the actual problems?

[lingqi]

i don't think you need O(n^4) - though i must say, since it's limited to 50 nodes, even at n^4 it's pathetically small.

anyway, I think it's probably faster to (for every node n)

1) compile a list of nodes going out of n
2) compile a list of nodes coming into n
3) for every node m not associated to n (complement of (1)+(2), find its list nodes that it has relations with, and find the intersection of the sets
4) profit!

well, 250 points only, but i think the above should get you on your way at a lot less than O(n^4). unless i got some costs wrong for some of the operations (i am having doubts about the intersect).

Re:nobody talks about the actual problems?

[White Shadow]

Yeah, that's the problem. Except there is no farmer and the restriction on what animals can be left alone together only applied to the boat (so you could lave a bad combination on either shore).

Oh, BTW, you get 8 seconds for your solution to run, so brute forcing all combinations would take way too long. In more concrete terms, this means you want something with a time complexity less than about 50 million.

Re:nobody talks about the actual problems?

[cpeikert]

Summarizing your algorithm: for every pair of nodes that are not connected, do the proper intersections of their in/out-neighborhoods. (Note however that the pair of nodes in the other corners must be checked for connectedness too.)

"For every pair" => O(n^2)
"intersect neighborhoods" => O(n log n)
(by sorting the entries in the neighborhoods and comparing from there)
But as for checking connectedness of pairs in the two intersections, that's again O(n^2).

So we're back at O(n^4) (not to mention the work that goes into preventing double-counting of cycles that are found in several different ways).

Which solution would you rather code up? :)

Re:nobody talks about the actual problems?

[lingqi]

Since you already have every pair of nodes that are not connected, checking for the connectedness of intersects should be a walk in the park beacuse you are checking against list the first. I don't think that's O(n^2). It's more like O(however many intersect pairs you got)...

Unless the list of intersects (however many intersect pairs you got) is bound by n^2... hmmmmmmm...

haha, alright. I concede. you see why I am only the rank of "armchair computer programming contest participant."

p.s. I have to say, though, that the amount of connectedness amongst the nodes do tricky things - because if very few nodes are connected to eachother, that would give you a huge list to check previously (near n^2), but you would have nearly no neighbors, and vice versa. Even in the middle case (which I assume the worst), this should still limit the algorithm's O down. a little.

or so my gut tells me. heh.

Re:nobody talks about the actual problems?

[jareds]

Ironically, I find the "easiest" one the hardest. I can think of a brute-force O(n^4) algorithm, but it's not pretty.

In the context of the competition, brute force is clearly the way to go.

Incidentally, if you can do better than brute force on DQuads, I can do better than brute force on finding 4-cliques in an undirected graph. I doubt there are any good lower bounds on 4-CLIQUE, but it does make it intuitively plausible that brute force is the best possible solution.

Re:nobody talks about the actual problems?

[jareds]

I meant "counting 4-cliques", not "finding 4-cliques".

Re:nobody talks about the actual problems?

[ponos]

Regarding the hard problem: it looks a lot
like creating a Huffman coding tree.

You need a binary tree where the
weight (information = -log propability)
influences the depth. Rare things go
deeper and need more bits to find.
Common things go higher. Therefore
if, say, you want to describe something
common you know it is at 01 (2 bits
instead of 8) while something rare
is at 1001111101 (11 bits instead of 8).
Bits describe the path on the tree.

This is not particularly hard and you
can construct an optimal solution
VERY quickly.

Anway, the problem is a bit different
(Huffman trees store information only
at the leaf nodes and they are not
ordered)
but I'm sure that the same principles
apply.

The general idea is that you progressively
built subtrees starting from the less
propable (less weight) items, combining
them two at a time while preserving
ordering[1]. You then treat each subtree
as a single item (classical dynamic
programming) and see if you can build
any further using it.

Many problems in such competitions
are solved with dynamic programming.

P.

[1] This is possible because you can
always choose between left and right
at the same depth. Depth is based
on weights and left-right ordering
on key values.

P.S. Could be much harder, though. I
just read the problem description and I
might be saying a load of crap.
Sometimes a small change can transform
a O(N) problem to an NP-hard problem.

Re:nobody talks about the actual problems?

[CognitivelyDistorted]

I read the problem too quickly so I just thought, "Oh, Huffmann encoding."

The key to this problem is that in the optimal tree, the subtrees of the root are optimal. To solve, you can consider each element in turn as a candidate root, and then compute the optimal left and right subtrees. Pick the best candidate.

To turn it into dynamic programming, start by computing all N optimal 1-element trees, then all N-1 2-adjacent-element trees, and so on: O(N^2). The solution in the article is a bit different because the problem only wants the optimal cost.

Re:nobody talks about the actual problems?

[CognitivelyDistorted]

That hard problem is more interesting. Isn't it NP-hard? If you can solve this problem, I think I can solve MAX-CLIQUE. Use the graph as the animal incompatibility graph, set all animal weights to 1 and the boat capacity really big. The solution to the animals problem is the solution to MAX-CLIQUE.

Re:nobody talks about the actual problems?

[cpeikert]

That hard problem is more interesting. Isn't it NP-hard?

Yeah, it's NP-hard, for the reason you gave (in fact, this is also an integer knapsack problem, which is also NP-hard).

However, the number of animals is limited to 16. This means that it ought to be feasible to iterate over all subsets of animals (there are 2^16 such). For example, it should be feasible to compute (in a couple of seconds) whether each subset of animals can occupy a boat together.

Re:nobody talks about the actual problems?

[Carnivorous Carrot]

> The farmer can only take 1 item with him at a
> time... but if he leaves the chicken and grain
> together, the chicken eats the grain, etc.

Take chicken across the river, leaving the fox and grain. Go back and get the fox (or grain) and take it over. Take the chicken back and leave it, taking the grain. Take grain back over to fox. Go back and get the chicken and bring it over.

Never heard this question before, 6 seconds to solve it in my head.

2 hours and still can't get that damned interface at Top Coder working. Buggy as hell, it is.

Topcoder

[dmh20002]

The top level guys competing in topcoder are some of the smartest guys you will ever meet. Whoever thinks they are a coder, go ahead and try a competition. Its free and they do it a couple of times a week. See if you can even get the easy problem right. I dare you.

p.s. Topcoder also has the best Java client side applications going. Their competition arena application/applet is a masterpiece.

no i don't work for them. Yes I have competed.

Kid Programmer

[Mooncaller]

When are they goining to start teach good coding practices in school? Most grads have to unlearn tons of bad habits. This kids code is no exception. If he submited this stuff for inclusion on any of my projects, I would end up rewriting it as an example of what is exceptable. Fortunatly, every university grad that I have worked with had a love of coding, and assumed that they would be doing a lot of their learning after graduating. These type quickly pick up the practices needed for real world programming. On the other hand, there are those that got into programming for the money ( ha big laugh!) This type usualy can not get passed what they learned in school. If the prof tells them "This is the way to do it", by golly thats how their gonna do it and no one is going to tell them different. I've seen this type but have not had to work with any. It is quite obvious that Dave is of the first type. His logic is also impecible. ... oh never mind, I just finishe reading the interview. He does already understand that his competition code is not what he would use in real world programming. I'll submit anyways because I think it is important and has been a bit of a gripe of mine for awhile.

Re:Kid Programmer

[HoldenCaulfield]

hmm . . . with topcoder being a timed contest, where points are awarded dependent on speed, and the coding phase being 75 minutes for three questions, that quick and dirty serves a need? We're not talking large scale projects here . . .

I had a competitor comment to me once that while lots of others don't mess with objects, he does, just because he likes the structure and makes his debugging easier, even for tournaments . . . most others skip them because it's a level of conceptualization that can be skipped . . . modular code doesn't serve much benefit in 75 minutes . . . (well, unless you're referring to STL . . . )

Re:Kid Programmer

[White Shadow]

When are they goining to start teach good coding practices in school?

They try to, but there just isn't enough time. Really, most after you take data structures (maybe a sophmore level class) you never get any formal programming training. Instead you move on to more specialized stuff like graphics or AI or theory or compilers or whatever.

And really, should the university be responsible for teaching you that stuff? In my experience, the best way to become a better programmer is to program and have other (more experience) people examine your code and give you feedback, and to look and learn from other people's code. If you're smart, you learn very quickly how to program for "the real world" when put in a job environment.

Re:Kid Programmer

[Mooncaller]

I have to say that I mostly agree with you. My main gripe is not with what is not taught, but rather by what is. Students are instructed to use techniques and practices that have no place in large projects. I've seen Introductory Programming textbooks that gave me the shivers. As I said in my post, most of the real programmers get past all this rather quickly. That is because they know that they have only just started to learn how to program. The only way to learn to program is to program as you said. I've been doing it for 30 years and I'm still learning and loving it.

Re:Kid Programmer

[Mooncaller]

If you read all of my post, you would see that I conceed this point. Being a prorammer, I was more interessted in his code then his interview so that is what I started with. I was reading the interview while composing my post ( and yes, I'm highly multitasking). That is why I did not get to this point to the very end.

Re:Kid Programmer

[Mooncaller]

Funny, this is perfect. What I wrote, appears to be an example of what I was talking about. The only difference is that it is in english and not C. It is grammaticaly correct. The problem is that my sentence is sylisticly atrocious. I am kinda afraid of rereading the rest of what I wrote, so late at night. I think I will be writing farther posts in VIM. That way I can more easily read and edit what I'm writing. I might even attempt to use correct spelling ... naw.

Re:Isn't regular "top" good enough?

[gantrep]

Why is this a troll? I think it's funny.

competition paradigm

[lingqi]

I personally think this is a better programming competition paradigm than TopCoder.

in case people will probably not bother to click, it goes something like this:

you have three days to do the programming task (72 hours), and you submit it via email. you can use whatever language you want, etc etc. here is an official quote:

Programming should be about correctness and elegance, not about writing something in a hurry. Correctness is more and more important, for example in life-support systems and drive-by-wire automobiles, where there is no room for error.

There is no room for error in this contest either. The first thing the judges will do is test the programs and eliminate any entry that does not give correct results on all tests. Besides, the task will be simple enough that 3 days will be enough time to write, debug, and do some tweaking on your program, and get a normal amount of sleep. It was already the case for the previous years, and we see no reason to change.

the cool thing is this

[for the 1st place] Finally, the contest judges agree to state at least once during the presentation of the awards that the winning team's programming language is "the programming tool of choice for discriminating hackers."

[for 2nd place] The contest judges agree to state at least once during the presentation of the awards that the winning team's programming language is "a fine programming tool for many applications."

[for special judges prize] The contest judges agree to state at least once during the presentation of the awards that the winning team is comprised of a group of "extremely cool hackers."

anyway... the money isn't as good, but I like it much better. btw the winner for the 2001 one used haskell, and second place used Dylan, ha! eat my (shorts), Arthur. =)

Basis Transforms

[emarkp]

Funny, as a freshman at UC Berkeley, I took Linear Algebra (and took another course on it later), but it wasn't until my graphics programming course that I understood the details of basis transforms. It was as if my profs were working hard to produce a concrete example.

Re:Basis Transforms

[Mooncaller]

If students were taught how to visualise the math they are suppose to be learning, they would pick it up much faster. You will find that ALL people who are good with math have a natural capability for visualizing the concepts. It is my firm belief that visualization technique can be taught. I have done just this while tutoring. I found Linear Algebra extremely easy because it was so visual.

Re:Basis Transforms

[zatz]

I can visualize some things, but often I must resort to pure symbol manipulation. If I am picturing anything when writing a complex SQL statement (relational algebra is math, and this comes to mind just because I've done it a lot lately), I'm not conscious of it. I would say that a join looks like a zipper, but I have to forget any pretty pictures and just think about subsets of cartesian products when I am doing anything really complex.

Likewise for devising algorithms, describing a language with a regex or grammar... it's abstracted to an essentially non-visual, non-spatial domain.

I acknowledge the value of visual metaphors, but I am not convinced this kind of thinking can be taught effectively to everyone, or that it applies to all of mathematics.

Re:Basis Transforms

[weston]

It is my firm belief that visualization technique can be taught.

You wanna go into some details?

Re:Basis Transforms

[Mindjiver]

Sure it's good to visualize math. But some stuff in linear algebra ain't so easy to visualize, like rooms in R^5 and such.

Re:Basis Transforms

[Mooncaller]

This headline is dead, but I'll respond anyways. I don't think anyone will read it. I find that pure symbolic manipulations is a visual task. I find writing regex to be very visual. I think it is a matter of visual abstraction. I often visualize sets of abstractions to solve math and programming problems. Another commentor wanted an example. Its kinda lame but does demonstrate the use of sets of abstraction. Most people have little problem visualizing conic sections. Most people can visualize 3D quadratic surfaces. It is not too hard to visualize the conic section produced by the intersection of a plane with a quadratic surface. By abstraction, I think people generaly will be able to visualize quadratic surfaces as the intersection of a 4D "cone" with a "cube". 4D Quadratic surfaces can be visualized by passing a "cube" through the surface. Treating the direction of the pass as time, one gets a changing 3D quadratic surface. Combining the "movies" produced by different selections for the "time" direction creates a set of abstractions. And this set can be used to represent the 4D quadratic surface.

Re:Basis Transforms

[Mooncaller]

I concede that my belief is theoretical. I have imperical evidence that it can be done for some things. But I just tried to figure out how to teach someone how I visualize an abstract ring. I don't think I can do it. BTW. I use abstract algebra and related concepts to map problem spaces onto systems to be implimented in software. By starting with such a map, I am less likely to put funcionality in the wrong place. I am also more likely to spot things that are missing in the original problem defination. The result is code that is easier to maintain and to adapt to changes in the targeted problem space. It also produces more generalized software that can often be reused. I sure wish I could show people how I do this. It would have saved me many many hours spent explaining things to team members that I see so easily. It would have also have saved the entire team many more hours in fixing code produced by some boneheaded programmers that ignored my ( and other team members) advice. I am also sure that some of my coworkes, who also use visualization techniques, wish they could explain what they do. As none of use have done it, maybe it is imposible.

Re:Basis Transforms

[weston]

Drop me an email if you wouldn't mind discussing this further -- I'm interested, studied Math in college myself, though I often wondered if that did me the good I was hoping for... and it sounds like you're describing.

And the Espy goes to...

[tuxathon]

Mr. TopCoder could very easily be a pro athlete. He sure answers questions like one. I'm sure DevX is very proud to get the interview, but it amounted to, "I really like math, so I might do that. But I really like CS, so I might do that. Oh, by the way, gaming."

"So Shaq, what do you need to do to win the game?"

"We need to go out and give it a hundred percent, leave it all on the floor. We have to make shots to win and work as a team. Oh, by the way, Shaqalicious."

Very insightful.

Actually....

[gantrep]

I've actually considered such a thing, and I'm sure that they do in fact exist.
Just because many people who are big fans of computers and math and science don't like English doesn't mean that none do. I've got ACT scores of 36 reading, 35 english, 34 math and 34 science reasoning, and SAT scores of 760 verbal and 680 math. If I had the time and money, there is no reason I couldn't pursue a humanities degree on the side. Unfortunately, my scholarship money only covers so much and computer engineering is what I want to DO with my life; Even though I might be a little better at something else, I would absolutely hate a career in English.
The issue is one of the practicality of double majoring in unrelated fields, not of any lack of double interest.
And yes I know you were just making fun of his spelling of the word "knew."

Re:Actually....

[gantrep]

Maybe I should rethink things considering that I apparently am unable to properly close an html tag or use the preview button.

:=/

Re:Actually....

[Carnivorous Carrot]

ACT has reading? It was English (note the capital E), math, science, and history.

I recall one particularly dimwitted guy at my school who couldn't get a 17 average on the ACT, the minimum so he could go play baseball at some low-level college. I got 17 average just on my math and science if I got a complete, perfect 0 on the English and history.

Re:Isn't regular "top" good enough?

[gantrep]

"It's a troll because it guards a bridge and steals children.

You see, that wasn't funny either."

Is there something wrong with me if I thought that was funny as well?

Linear Algebra rocks

[kindofblue]

I must say my linear algebra experience was awesome, mostly because I never went to class. One day I finally made an appearance and saw my TA handing back graded tests; one that I never knew about. My TA politely informed me that I didn't take it, and asked when could I come in to make it up. Eventually, I took it after I had taken the final, and my TA was literally making up the questions on the spot, one by one, while I was working on the previous questions.

My numerical analysis class, on the other hand, was less fun than smoking saw dust.

Re:Linear Algebra rocks

[HanzoSan]

You should have failed that class.

Consider yourself lucky.

Where did this guy work again?

[the_duke_of_hazzard]

"In the real word (sic) you think a lot about design, you want to have nice code that other people can understand." Clearly he doesn't have what it takes to make it in the "real" word (sic).

Occaml - Language of Choice for the Mathematicians

[Taco Cowboy]

Say what you want, but for the math gifted, most of them will code in Occaml, or one of the Meta Languages (ML), if they ever come across them.

if only...

[carrett]

game programming is where it's at... it is of course the chicks. awwwwwwwwwwwww yeah, it's all about the cs babes.

Game programming

[peterpi]

Could somebody point me to the bit where he talks about game programming? I can't find it.

Re:Game programming

[Tubetti]

>>>Could somebody point me to the bit where he talks about game programming? I can't find it. "There seem to be a fair number of things I could go into that would do that, one of them being gaming programming simply because the problems they have to deal with are certainly as hard as anything out there. "

Third last para.

Re:Game programming

[peterpi]

oh, thanks.
I was expecting more :\

The hard problem

[Anonymous Brave Guy]

*hard* - at least I understand the problem, but curses on the restrictions of a binary tree =)... no idea on algorithm that would finish executing before the end of the universe.

I only scanned the article and problem descriptions, but isn't the final problem a similar idea to Huffman coding?

DSC 110

[BSDevil]

Yeah UCC...Home of both the smartest and stupiest High School kids I've ever seen (yes, I went there too). Dave was brilliant, and when around fellow computer people, quite sociable - I had meetings in the room next to the computer club, and would drop in when I was waiting for them to start. Put him in a room full of non-geeks, and it was a different story. But wasn't that a fair number of us then?

Anyways, I remember seeing the game he wrote and being blown away by it. Granted, it wasn't the most amazing thing, but when you consider that he had to use BGI (the Borland built-in graphics systems) for everything, it was quite a feat. Especially compared to some of the other projects that came out of that class (Slemon's DSC 110).

He was a nice enough guy, and he definatley deserved this. Well donne, Dave.

Re:Occaml - Language of Choice for the Mathematici

[thrillseeker]

Say what you want, but for the math gifted, most of them will code in Occaml

APL is the only way to fly.

TopCoder High School

[gabeman-o]

FYI, TopCoder is starting a high school level. Right now it is only in Connecticut (my home state, yay! I'm the Top Coder in my school). The final competition is on Tuesday at the University of Connecticut, which I will be attending :D. More info is @ http://highschool.topcoder.com

Sense of perspective

[Anonymous Brave Guy]

I agree that the standard of coding you see in the examples is pretty low by pro standards, and that you'd expect any reasonably experienced pro to come up with better. Then again, as we've all agreed, the nature of this competition does not encourage industrial strength coding. And of course, I don't know about you, but I certainly wrote similar code sometimes when I was a student. The entrants for this sort of competition are young and inexperienced, and you have to look for potential, not results today, if you're going to draw any meaningful conclusions.

What's more concerning, if anything, is that all of the illustrative solutions are basically brute force approaches. If these are the best algorithms available in a sensible timeframe, perhaps the problems set weren't such a good choice. If there are significantly better algorithms available and the coders weren't finding them, maybe either the time constraints were too restrictive or maybe even the top guys in a competition like this are still quite a way behind the "serious coder" standard (professional or otherwise).

Re:Sense of perspective

[zatz]

The example solution to SkewTree is dynamic programming, not brute force.

Re:Sense of perspective

[jareds]

The problems they used were too easy, in that 3 of the 4 finalists finished all the problems in 40 out of 75 minutes. That's because when they first ran the final round a switch died and they had to cancel the round. The problems in the article were their backup problems.

However, the solutions were not all brute force.

Re:Sense of perspective

[Anonymous Brave Guy]

Sorry, I stand corrected. That's what I get for posting after a 30s scan of the example solutions while at work. :o)

The first two solutions are both pretty much brute force, though.

Re:Sense of perspective

[CognitivelyDistorted]

What's more concerning, if anything, is that all of the illustrative solutions are basically brute force approaches.

Really? For practical programming, when I need an algorithm to solve a problem like these, I go in order of preference:

1. Find a library that does it.
2. Steal some source code that does it.
3. Implement obvious algorithm (greedy/exhaustive)
4. Look in CLR
5. Ask a friend
Last resort. Think up clever algorithm.

I'd guess that most coders spend 1-10% of their work time doing the type of programming in this contest. But I'd bet the contest winners are pretty smart and I think most of them would make great programmers after a year of work experience.

Re:Sense of perspective

[Anonymous Brave Guy]

For practical programming, when I need an algorithm to solve a problem like these, I go in order of preference: [...] Last resort. Think up clever algorithm.

Sure, but the ability to work out clever algorithms when appropriate is one of the key things that separates a good developer from a code monkey. Is this competition supposed to identify code monkeys or good developers?

But I'd bet the contest winners are pretty smart and I think most of them would make great programmers after a year of work experience.

Yes. I'm not taking anything away from them at all. As the thread title says, I'm just trying to keep the thing in perspective.

Re:Sense of perspective

[Anonymous Brave Guy]

But the thing some people don't realise is that the top competitors can also decide to write "industrial-strength" code whenever they want to, with all the meaningful variable names, comments, indenting, reusability, documentation, etc. that you like, and will still beat the pants off of all the regular "real-world" programmers.

That may be true, but I'm not convinced any sort of competition like this proves it. I've met plenty of young, die-hard hackers who could write cute code themselves, but had no teamworking skills whatsoever, including in their coding style. The ability to design and/or implement algorithms that work is not in any way equivalent to the ability to write clean, well-structured, maintainable code. Obviously there's a correlation between the people who have these abilities, but neither implies the other.

They may be young, but they're not inexperienced.

You know, it's funny. When I was a student, I knew everything about coding, too. When I started my first job, I was better than all the other guys there; the older ones got paid way more than me, but wasted loads of time doing pointless things.

I'm reminded of two old aphorisms that are oh-so-true here.

• The most important thing you learn as you get older is how much you still have to learn.
• Young men believe old men to be fools, but old men know young men to be fools.

Fascinating reading

[Anonymous Coward]

I don't normally read SlashDot, but after a friend pointed out this post to me, I had to check it out. Having done so, I couldn't resist making a couple comments.

"I find it interesting that a math double-major, who's considering becoming a math professor, uses C++"

I don't see much use for computer programming at all in mathematics, except in applied areas that don't interest me. I learned C++ because it was ideal for game programming, and I learned Java because it was taught in college and used at the company where I worked.

"Maybe there is some kind of speed math problem think tank that secretly controls the world around us"

Amazingly enough, it is actually possible for certain people to do more than one thing, including math research and contests. For example, I once met this guy who could walk and talk at - get this - the same time. It was pretty crazy.

"With looks like those... it's no surprise he has nothing better to do."

Yeah, screw you too. At least I have better things to do than flame college students on SlashDot. In fact, I spend no more than two hours a week on TopCoder, often less. I almost never practice, and I have not competed very many times.

"someone who won top coder is saying it's a good indication of real world ability"

I believe I said that it is not completely irrelevant. That would be different. Since I did this interview for some internet thing that neither I nor my friends read, and since I am not even looking for a job right now, I didn't really have a vested interest.

"(tenured math professor = job security)"
"he's smart enough to know even he can't get a job programming"

If you guys think it is easier to get and maintain a good programming job than it is to get and maintain a math professorship at, say, Harvard, you are very much mistaken.

"So this guy is telling us he makes this for the money and he will become a math professor?"

I believe I mentioned that money is no longer my primary reason for doing TopCoder. Furthermore, just because I choose to spend minimal time making lots of money given the opportunity, does not mean I can't live with a bad-paying job.

"normally you do not *decide* to become a professor"

Really? I actually think this is precisely what happens.

"other serious, more difficult, competitions like the ACM"

You don't know what you're talking about. Everybody in the TopCoder top 10 has done extremely well on some or all of the ACM, the IOI, the Putnam, and the IMO. Of these contests, I'd say the ACM is actually the most worthless (straightforward problems, missing constraints, ridiculous 3-person 1-computer dynamic, ridiculous 2-year limit).

"Mr. TopCoder could very easily be a pro athlete. He sure answers questions like one."

What do you want me to say? Maybe I should have answered questions like "Have you thought about how you want to apply your computer skills after graduation?" with "Actually, since I'm a super-genius, I thought I would show P != NP, and then maybe move on to the Riemann hypothesis, and then maybe I'd see if I could fly just by thinking really hard, like that dude in the Matrix". Certain questions will get lame answers every time.

To those of you who aren't asses, good day.

-- David Arthur

Re:Fascinating reading

[Anonymous Coward]

This is about the first time I've read slashdot in about 2 years, but I just wanted to say that you all should be ashamed of yourselves for saying anything but the highest praises for dgarthur.

As a fellow Duke student, I can tell you from personal experience that I don't think anyone has seen David without a smile for the past three years, so you guys REALLY have done an amazing job to piss him off. Congratulations, losers.

But it's okay--I'm sure dgarthur will be laughing all the way to the bank.

Re:Fascinating reading

[CognitivelyDistorted]

Hi, David. Congratulations on your win. Don't worry about Slashdotters, they're like this to everybody, out of envy. Hell, everyone who knows me considers me an excellent programmer, I'm not interested in contests, and I'm not an asshole, but I still felt urges to put you down. I'm just mature enough to recognize the source of those urges and suppress them.

I'm sure you know that the skills you demonstrated in the contest are only a small part of the skills needed by a professional coder. I'm also pretty sure you'd make a great coder. On the other hand, based on what I've heard about you, I suspect you're too smart to be just a game programmer or something like that, and that better things are in store for you. Of course, coding is still a lot of fun, good preparation for management or research, and a decent profession. Whatever you decide to do, thanks for stopping by on Slashdot, and best wishes.

Re:Fascinating reading

[ZorbaTHut]

Everybody in the TopCoder top 10 has done extremely well on some or all of the ACM, the IOI, the Putnam, and the IMO

As much as I agree with everything else you said, you got that one wrong - I've never done any of those, and right now I'm ranked #6 :P

On the other hand, looking at the people, I think I'm the only exception in the top ten, and I wouldn't be surprised at all if I was the only exception in the top twenty or more.

Geeklympics.

[Lane.exe]

'Nuff said.

MPU!

[bkw]

Mod parent up!
8 years of contract coding, and not a single project that wasn't like this.
My code is cluttered with commented out blocks showing the Real Solution[tm], which over time had to be replaced by ugly special case logic making the whole algorithm a pain to look at.

I get really nostalgic when I think about the puzzles they presented us in the university that you could chew on until you had a slick, clean an elegant solution. Almost never happened to me since.

Scratch that...

[Anonymous Brave Guy]

OK, reading in detail the problems aren't the same after all.

My first time

[jlechem]

Well I just entered my first top coder competition yesterday and it was a learning experience. I thought I did well until the challenge phase but got slammed on 2 of my 3 answers that had me in the top 3 places when i finished the coding phase. There is no time for comments, good coding practices, etc. Just get the problem done in the smalles amount of time possible. I agree with what someone else said this is great for diversionary fun but it doens't reflect real world programming practices at all.

Recursion

[SatanicPuppy]

Heh. Recursion.

I did a lot of scheme during undergrad, and ended up being a master of recursion of the most esoteric types. It is seriously elegant stuff, makes all my peers go, "Woooow man, that rocks."

However, in the place where I now live, the "real" world, recursion sucks. First it was people constantly calling me saying, "Hey I found this weird line of code what the hell does it do?" over and over, and THEN, I found an even more awful truth: the memory utilization becomes prohibitive whenever you have to recurse more than 10 or 20 levels.

Iteration is ugly, but it's easy to read, and it doesn't use half as much memory.

Just my 2 cents worth.

Interview

[ZorbaTHut]

No idea if anyone would be interested in the least on this, but I'm ranked #6 in Topcoder, one of the longest-competing and highest-ranked members. I'm actually ranked above dgarthur, but I have horrible luck in the onsites and aren't currently in college anyway, so I wasn't eligable for the 2003 Collegiate (though I went to the 2002 Invitational - dgarthur's way too good at Super Smash Bros, and SnapDragon's even better.) So if somebody (I was thinking Slashdot-related, but otherwise would be fine also) wants to interview me, I'm up for it - toss me an email at zorbathut at uswest dot net, and use a subject that doesn't look like spam, since otherwise it will probably get deleted unread :P

Re:Occaml - Language of Choice for the Mathematici

[stonecypher]

> but for the math gifted, most of them will code
> in Occaml

That's mighty presumptuous, especially considering the lambda calculus, OCaml's not so great history with parallelization, and Eiffel.

Besides, they're all gonna program in C++. Why? Because nobody has a choice, that's why. Otherwise, we'd all be up to our necks in Ruby and Lua.