The Blog Chyernobog

An Enterprise Dev's Adventures in Computer Science

Some Fun Facts About the UVa Judge

| Comments

One of the biggest problems with ACM contest-type sites like the UVa Judge is that it’s hard for a newbie to determine the difficulty of any given question. That’s where Felix Halim’s uHunt has, for me, proven invaluable. It starts you out with the most trivial problems (seriously trivial – I’m talking fifteen minutes coding effort for some of these), and then works up through the more difficult. The big trick with this kind of programming, as with any skill, is consistency. Tackle 2-3 problems per week if you want to see results.

That said, here are some details about the site:

  • My current rank is 23,904. 16 AC, 80 submissions, for a submission/acceptance ratio of 5 to 1. There’s room for improvement here.
  • My rank when I started recording it was an even worse 33,450. 9 AC. 63 submissions. My ratio was a lot worse, averaging 7 submissions per AC.
  • Solving each problem, at least at the lower rungs, boosts your rank by about 1,000.
  • Number of current “authors”: 140,116 (The worst of these had 27 submissions with 0 AC. So fear not. There’s room at the bottom.)
  • Your rank, should you happen to get 100 problems correct: 5,649.
  • Your rank, should you happen to get 500 problems correct: 575.
  • There’s one guy with 18 problems solved, but 440 total submissions. You just know he’s hating his life.
  • The top guy on the site has 3930 problems solved, 3970 problems tried, and 13,981 submissions. That makes his ratio between 1 in 4 and 1 in 3 (actually, slightly more than 28 percent). One in three is good, but not nearly as good as some of his competition. On this site, solutions beat submissions any day.
  • SPOJ has a better ranking algorithm, where you are judged based on problem difficulty. They’re also more flexible about what language you use. I’ve had a lot of fun with Haskell problems on their site.
  • Java is less-used than C++, but so what? Any interview I’m in will probably favor Java. Once you get a solution in Java, porting it to C++ will be trivial. (Assuming you know C++, which I do.)

On the last point, I have noticed some problems that are a lot more suited to C++ than to Java. For instance, Problem 458 “The Decoder”. The problem is a simple substitution cypher, and can be solved by an absolutely trivial operation on each character. But here’s one place where Java’s I/O cruft causes more problems than it’s worth, because of one of the problem’s caveats:

Your program should accept all sets of characters that use the same encoding scheme and should print the actual message of each set of characters.

In Java, you don’t normally have to worry about character encoding, because Java assumes the universe is in the shape of UTF-16. Which means any other kind of character encoding scheme (e.g., UTF-8 or CP-1252) is going to be transformed into UTF-16 unless you specifically compile your code to respect a different character encoding. The very act of reading your input into a string in Java can change the character encoding. This caused a lot of headaches with wrong answers that I knew should be correct.

Fortunately, I know C.

It turns out that C doesn’t care about your silly encoding strategies. In C, every character looks like every other character, because characters are essentially identical to integers. In some ways, this makes C easy to deal with. The solution in C turned out to be trivial.

char c;
while ((c = getchar()) != EOF) {
    if (c == '\n') {
        putchar(c);
    } else  {
        // do the transformation, and call putchar on that
    }
}
return 0; 

The one thing I have to thank this problem for is how it forced me to come to grips with a bit of ignorance I wasn’t aware I had: I currently don’t know how to write character manipulation in Java that is absolutely agnostic as to its character encoding.

Introduction

| Comments

A few years ago I made a list of what I wanted to do with my programming career. I want to revisit that list here to make sure I’m getting what I want out of this profession. My goals were:

  • Learn algorithms to the point where I would be comfortable (even if not brilliant) competing in an algorithmic competition on something like Topcoder.
  • Learn at least one functional language (… that isn’t Javascript)
  • Learn Math
  • Learn enough theoretical CS to compensate for the fact that I didn’t major in CS in school
  • Learn game coding (because that’s where a lot of interesting CS challenges are)

In other words, I want to be a double-threat: a competent Computer Scientist who has degrees in Russian and Creative Writing. It’s a tall order, but I know what I’m like when I’m motivated. If it will get me where I want to go, I’ll take the long way around.

So I want to devote this article to a bit of self-assessment, so I can take stock of where I’ve been and where I need to improve.

Algorithms

I’m probably about a quarter of the way through this one. I took part one of Sedgwick’s Coursera course, and was surprised by how rigorous it was considering that most of the main algorithms covered were essentially review for me. I had already coded my own Quicksort and Merge Sort routines. I had done a Heapsort, so I knew how priority queues worked. Stacks and Queues were not difficult at all. But then the actual coursework forced me to take my coding chops up a notch. Binary Trees? Not challenging enough. KD-Trees, on the other hand, forced us to use binary trees in an interesting way. The assignment on sorts was warped into a check of colinearity of points on a plane. And along the way the quizzes and tests checked to make sure that you knew the underlying algorithms cold. Case in point: the question from the final exam where you were given ten lists of words which were at various stages of being sorted. We were asked to name which algorithm was sorting that list. It was one of the most thrilling courses I’ve ever taken, and I can easily see why it enrolls a quarter of all undergraduates in Princeton.

So now I have a certain amount of theory out of the way – though more from a programmer’s point of view than from the computer scientist’s. But I’m still not at the point of being comfortable going into something like Topcoder and churning out a solution in a few hours. I’m reasonably good at thinking my way through an algorithm, but I get turned around a lot while translating that algorithm into code. That’s why I’m solving my way through the UVa judge – I need to get my imperative coding chops up. I’ll know I’m there when I can go to something like InterviewStreet and dive right in.

Functional Programming

This one is a bright spot for me. I have learned Haskell to the point where I can now start building libraries that do interesting things. Thanks to the work I did for a now-defunct Haskell gaming company, monads are no longer mysterious, and I’m almost at the point where functional techniques make me feel like I’m a programmer with superpowers.

I now know Haskell at a reasonably intermediate level. If you asked me to code up my own monad, I would know how to do so. It’s at once not all that impressive, since monads aren’t all that difficult, but monads have such a scary reputation that it’s nice to have them down. It also puts me on a weird footing with math – I now know a bit more about Category theory than I do about Calculus.

The downside of this level of awesomeness is that, to get to this point, I’ve had to neglect my imperative programming. At a recent interview, this was my biggest liability. Given an array and asked to do manipulations on it, my mind immediately reaches for a fold operator. But the FP jobs just aren’t what they might be. There is as of yet no burgeoning economy for programmers versed in the ins and outs of applicative functors. But learning FP has revolutionized my mindset as a programmer, and has helped me stand out from the crowd.

Bottom line: I can now probably pull back from FP a little bit and focus on other areas. I can declare tentative victory here.

Caveat: I loved working through the beginning of the book Software Foundations. If I ever have a chance to go back and work through it further, I will do so.

Math

From “I haven’t taken any math since High School,” I’ve made some inroads here, though not enough. I have racked up over a million points on Khan Academy – specifically on the exercises, which are more important, I think, than the lectures. And I’ve almost exhausted the tree of possible subjects. But here’s the rub: KA stops right now at basic Differential Calculus. That’s not going to be anywhere near enough. But I do have a good handle on the basics, thanks to Sal Khan.

So, Math. Let me further sub-categorize this area:

  • Calculus- A bit of progress, but not much. At some point I’m going to swallow hard and take a class in Coursera.
  • Statistics – Again, some minor progress. I understand Standard Deviation and simple probabilities, but I’ll probably need more.
  • Linear Algebra – Very little. Just enough to get by with games programming.
  • Discrete Math – Not nearly enough. And unfortunately, nobody has really put a good free course online yet for this. On one hand, I’m not sure how much I’m going to get out of doing formal proofs on graphs.

This isn’t a satisfactory progress report by any means. This is quickly becoming the squeaky wheel.

Theoretical CS

This one may well take care of itself, given my other activities. I’ve already taken an Algorithms course, and am part of the way through Udacity’s Theoretical CS course (learning all about P vs NP). So here are the classes I would need for follow-up knowledge:

  • Compiler Theory
  • Languages (although, do I really need this? With everything else I’ve done)
  • Cryptography
  • Artificial Intelligence and/or Machine Learning
  • Big Data/Analytics – I’m adding this one because it’s obviously where the industry is headed.

I’ve always been more comfortable with my CS classes than with my Math classes, possibly because I’ve always gravitated toward the less math-oriented CS classes. But I’m not too worried about this category. It will almost take care of itself if I keep doing what I’m doing.

Game Programming

Well, on one hand, I now have a game project on my resume, so I can almost retire this one, except for two nagging desiderata:

  • Learning FRP to the point where I can write my own game in it, and
  • Using game programming as an excuse to learn HTML5 and Javascript.

Obviously, I’m OK on this category. My dream of building the next Half-Life 2 will obviously never be realized, because such an endeavor would take a team of over a hundred programmers, producers, and artists. But I can work up my indie chops on this one little by little.

In Conclusion So my two biggest priorities right now are Math and Algorithms. Ironically, both are heavy on the math. Is there anything else I’d like to add to this list? Maybe Android development, but I’m not too worried about that. It’ll take care of itself.