Slashdot Log In
TopCoder, Math, and Game Programming
Posted by
CowboyNeal
on Thu May 15, 2003 10:40 PM
from the racking-his-brain dept.
from the racking-his-brain dept.
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."
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
programming 3D rendering engine (Score:5, Interesting)
Re:programming 3D rendering engine (Score:2)
how about encryption? (Score:5, Interesting)
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.
Parent
Re:how about encryption? (Score:2)
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? (Score:5, Funny)
Payroll processing is where the action is. COBOL rocks! And you'll score loadsa chicks.
Parent
Re:programming 3D rendering engine (Score:4, Funny)
Parent
beh (Score:5, Funny)
True "Top" Coders Dominate the "Bottom" Coders (Score:5, Funny)
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 (Score:5, Interesting)
I'm not sure what conclusion to draw from that fact, I just find it interesting.
Re:Language of Choice (Score:2, Interesting)
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 w
Re:Language of Choice (Score:5, Funny)
Fact: functional programming is dead.
Parent
Re:Language of Choice (Score:3, Informative)
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 (Score:2, Informative)
-- a red
Re:Language of Choice (Score:3, Interesting)
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 (o
Re:Language of Choice (Score:2)
Re:Language of Choice (Score:5, Insightful)
Parent
Re:Language of Choice (Score:5, Insightful)
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++.
Parent
Occaml - Language of Choice for the Mathematicians (Score:3, Interesting)
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.
Re:Language of Choice (Score:4, Interesting)
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.
Parent
Re:Language of Choice (Score:3, Insightful)
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 (Score:3, Interesting)
Real World vs. Top Coder... (Score:5, Insightful)
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... (Score:3, Interesting)
Actually it's not as simple
Re:Real World vs. Top Coder... (Score:2, Informative)
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... (Score:2)
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 f
Top Coder (Score:5, Funny)
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? (Score:2)
Porno's where the action's at. Game programming? Who in the hell made that up.
Read the article again (Score:2)
Experience (Score:5, Insightful)
Just my $.02
Re:Experience (Score:2)
i still code, but on my own terms.
Well.. (Score:5, Insightful)
You'd be surprised if you knew how many educated and real world programmers love programming.
Parent
Game programming is definitely where it's at (Score:4, Insightful)
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 (Score:5, Insightful)
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.
Parent
Why am I not surprised ... (Score:5, Funny)
In other news, Microsoft says Windows is the most reliable, and George Bush says America is the best.
Translation... (Score:4, Funny)
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.
David Arthur (Score:2, Informative)
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 cont
Re:David Arthur (Score:3, Insightful)
nobody talks about the actual problems? (Score:5, 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
Re:nobody talks about the actual problems? (Score:4, 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.
Parent
Re:nobody talks about the actual problems? (Score:3, Informative)
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, fin
Re:nobody talks about the actual problems? (Score:3, Interesting)
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? (Score:4, Insightful)
"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?
Parent
Fascinating reading (Score:5, Insightful)
"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:good thing (Score:5, Insightful)
Parent
competition paradigm (Score:5, Insightful)
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. =)Parent
Re:good thing (Score:5, Insightful)
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.
Parent
Re:good thing (Score:3, Insightful)
change halfway through the task
Wow you're being generous. My favorite is when it changes hourly.
Re:good thing (Score:3, Interesting)
1. Read the easy question.
2. Recall the Java class/method that shortcutted the problem.
3. Write 3-5 lines
Re:With looks like those... (Score:2)
but yet so right on. heh heh heh
i guess we'll be sitting next to eachother on the bus to hell.
Re:Kid Programmer (Score:3, Insightful)
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