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."

programming 3D rendering engine

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

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

how about encryption?

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?

Hah, encryption, I spit in your face !

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

beh

game programming is where the action is

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

True "Top" Coders Dominate the "Bottom" Coders

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...

Language of Choice

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

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

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

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

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.

good thing

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

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.

competition paradigm

I personally think this [inria.fr] 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. =)

Re:good thing

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.

Real World vs. Top Coder...

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.

Top Coder

Top Coder (top côder)
n.

1. Winner of the Collegiate Challenge
2. The one person on this Earth in which the act of procreaction will be the most difficult to engage in.
See also: "employment lost to Indian national"

*ducks*

Game programming?

Uhhh.. I read the whole article.. After I got done, I re-read the /. story, saw the reference to game programming being where the action's at - went back to the article, searched for 'game', and found nothing. WTF? ..

Porno's where the action's at. Game programming? Who in the hell made that up.

Experience

It is my firm belief that people have a 'love' for programming do a lot better than educated and real world programmers. It really all comes down to whether the task is being done because of PERSONAL motivation, versus /having/ to do it for class or work.

Just my $.02

Well..

It is my firm belief that people have a 'love' for programming do a lot better than educated and real world programmers.

You'd be surprised if you knew how many educated and real world programmers love programming.

Game programming is definitely where it's at

I like to think of game programming vs. other fields of software like flying fighter planes vs. flying airliners. The airlines are much more prevalent, make a lot more money for the pilots, and probably benefit society far greater than the fighter pilot.

But the fighter pilot is one of an elite few, is much more well-trained and on the cutting edge of technology, and sure has that sex appeal and WOW factor as well.

So it is with game programming. Gamers always strive to push the cutting edge, not just get a job done but to try new things always with each iteration, unlike the business programmer who solves a task to be solved rather than invents new problems just to see what's possible, and it's really no coincidence that the needs of games is what drives a lot of PC hardware technology forward. While game programmers may not make as much money or benefit society as the suits, it's sure fun, and I have no regrets about being in the field.

Re:Game programming is definitely where it's at

Graphics and games (which along with movie SFX are probably the most visible applications of graphics) are cool to me, because any layperson can appreciate the results of your work. This is probably not true of any other area in practical or theorectical CS.

Just show them your cool real time renderings, and they go wow! Your average Joe Blow will not appreciate your proof that P=NP, your RDBMS that sets new records in a TPC benchmark, or your preemptive, reentrant OS kernel. But people like and understand visual things, and so it's easy for them to appreciate the fruits of your labor.

Get a Job

If these guys wanted real competition, they would try to get a job as a coder in the US. Try competing with talented coders in the Third World who are willing to work for half your pay. Frankly, I don't blame the Top Coder for looking into other fields (tenured math professor = job security).

With looks like those...

it's no surprise he has nothing better to do.

Why am I not surprised ...

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.

Translation...

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.

First day on the job:

DevLead: Make a dialog with a tab control.

SuperFastAlgorithmProblemSolver: Huh?

;)

David Arthur

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.

nobody talks about the actual problems?

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?

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?

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? :)

Topcoder

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

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.

Basis Transforms

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.

And the Espy goes to...

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.

Where did this guy work again?

"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).

if only...

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

Game programming

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

TopCoder High School

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

Fascinating reading

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

Geeklympics.

'Nuff said.

My first time

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.

Interview

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:Isn't regular "top" good enough?

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