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."
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. :)
Consensus is good, but informed dictatorship is better
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...
Lawrence Person (lawrencepersonh@gmailh.com (remove all "h"s to mail)
http://www.lawrenceperson.com/
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.
--
CPAN rules. - Guido van Rossum
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!
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.
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.
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.
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.
- Adam L. Beberg - The Cosm Project - http://www.mithral.com/
DevLead: Make a dialog with a tab control.
;)
SuperFastAlgorithmProblemSolver: Huh?
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.
David went to my highschool, Upper Canada College (Canadian version of Exeter/Eton), and he was a couple grades below me.
:) i.e. No girlfriends. Maybe university has changed him now, I dunno.
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
Anyways, he wrote a complete 3d FPS game in ~ grade 10 . He also crushed everyone in the Waterloo CS contests.
well after 69 comments (hehe), there has not been a SINGLE one discussing the competition problems, all three of which are quite interesting.
/. 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.
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
My life in the land of the rising sun.
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.
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.
Why is this a troll? I think it's funny.
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.
You see, that wasn't funny either.
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.
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.
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."
"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?
My numerical analysis class, on the other hand, was less fun than smoking saw dust.
"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).
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.
Muchas Gracias, Señor Edward Snowden !
game programming is where it's at... it is of course the chicks. awwwwwwwwwwwww yeah, it's all about the cs babes.
I'm against picketing but I don't know how to show it.
Could somebody point me to the bit where he talks about game programming? I can't find it.
I only scanned the article and problem descriptions, but isn't the final problem a similar idea to Huffman coding?
If you disagree, post your argument. (-1, Overrated) isn't your personal censorship tool for views you don't like.
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.
Cue The Sun...
APL is the only way to fly.
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
So this guy is telling us he makes this for the money and he will become a math professor?
I do not know what you consider as being a professor, but normally you do not *decide* to become a professor (and winning programming competition where you solve some known problems every CS student should be expected to have seen at least once in his life isn't really enough to become one), and well if he just means he wants to go teaching in high school, then you do not make this for the money either...
I do not know, but all this just leaves a very bad impression. In particular with respect to some other serious, more difficult, competitions like the ACM programming contest, where you do not normally go to win money... you can do that just to be there. I think every wanna-be-professor should understand this. I hope so.
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).
If you disagree, post your argument. (-1, Overrated) isn't your personal censorship tool for views you don't like.
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
Could happen. The Pro Dominatrix convention is in San Francisco next week.
(Disclaimer: a friend of mine is putting on this event.)
If you`re between the ages of ten and sixteen you think games programming is where the action is. Then you grow up and do something useful with your life.
'Nuff said.
IAALS.
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.
OK, reading in detail the problems aren't the same after all.
If you disagree, post your argument. (-1, Overrated) isn't your personal censorship tool for views you don't like.
Payroll? That be a whack azz gig. Accountz Reeceevable be where it's at, yo.
How come everyone (almost) believes that there's some secred truth to be found in math and algorithms?
And the problems presented? Well, they might be interesting at the university but what about real world stuff?
I've earned my living as a software developer for 15 years and I've never implemented that B*tree we had to write in our 3rd (out of 4.5) year.
Most real world stuff is not solved by those fancy algorythms. I've never touched discreet mathamatics or Turing machines since I left the univ and I'm still doing pretty good.
One more crippling bombshell hit the already beleaguered *BSD community when IDC confirmed that *BSD market share has dropped yet again, now down to less than a fraction of 1 percent of all servers. Coming on the heels of a recent Netcraft survey which plainly states that *BSD has lost more market share, this news serves to reinforce what we've known all along. *BSD is collapsing in complete disarray, as fittingly exemplified by failing dead last in the recent Sys Admin comprehensive networking test.
You don't need to be a Kreskin to predict *BSD's future. The hand writing is on the wall: *BSD faces a bleak future. In fact there won't be any future at all for *BSD because *BSD is dying. Things are looking very bad for *BSD. As many of us are already aware, *BSD continues to lose market share. Red ink flows like a river of blood.
FreeBSD is the most endangered of them all, having lost 93% of its core developers. The sudden and unpleasant departures of long time FreeBSD developers Jordan Hubbard and Mike Smith only serve to underscore the point more clearly. There can no longer be any doubt: FreeBSD is dying.
Let's keep to the facts and look at the numbers.
OpenBSD leader Theo states that there are 7000 users of OpenBSD. How many users of NetBSD are there? Let's see. The number of OpenBSD versus NetBSD posts on Usenet is roughly in ratio of 5 to 1. Therefore there are about 7000/5 = 1400 NetBSD users. BSD/OS posts on Usenet are about half of the volume of NetBSD posts. Therefore there are about 700 users of BSD/OS. A recent article put FreeBSD at about 80 percent of the *BSD market. Therefore there are (7000+1400+700)*4 = 36400 FreeBSD users. This is consistent with the number of FreeBSD Usenet posts.
Due to the troubles of Walnut Creek, abysmal sales and so on, FreeBSD went out of business and was taken over by BSDI who sell another troubled OS. Now BSDI is also dead, its corpse turned over to yet another charnel house.
All major surveys show that *BSD has steadily declined in market share. *BSD is very sick and its long term survival prospects are very dim. If *BSD is to survive at all it will be among OS dilettante dabblers. *BSD continues to decay. Nothing short of a miracle could save it at this point in time. For all practical purposes, *BSD is dead.
Fact: *BSD is dying
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.
Hold up, wait a minute, let me put some pimpin in it
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.
ad logicam Claiming a proposition is false because it was presented as the conclusion of a fallacious argument.
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
Breaking Into the Industry - A development log about starting a game studio.
> 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.
StoneCypher is Full of BS