Slashdot Mirror
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."
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.
Dacels Jewelers can't be trusted.
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.
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.
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:
the cool thing is thisanyway... 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. =)My life in the land of the rising sun.
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 . . . )
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.
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?
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:
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.
**TODO** Steal someone elses sig.
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.
change halfway through the task
Wow you're being generous. My favorite is when it changes hourly.
I'm the big fish in the big pond bitch.
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.
Java: the COBOL of the new millenium.
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.
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
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++.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
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.
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
Java: the COBOL of the new millenium.