When you start solving programming puzzles like those on uHunt Chapter 1, what are you learning about? The obvious answer is that you’re learning about competitive programming. After all, uHunt has a companion textbook called Competitive Programming, and many programming puzzle sites are associated with the competitive programming community, or even run their own contests. But I don’t think that’s the right way to look at it. First of all, there’s not much competition happening when you’re first getting started. You may be using a site where the only rating is the number of problems submitted. Or if you are participating in real-time contests, you may not be making it through many problems before time runs out.
Speed and algorithms
Besides the minimal competition, the other characteristic of beginning programming puzzle solving is that you don’t need to know the gigantic list of algorithms that people associate with competitive programming. Take a look at how that Quora question is phrased: “What all basic data structures and algorithms should one learn before starting competitive programming?” The question implies that before you can even start, you need to learn some canonical list of algorithms. But beginning competitive programming problems generally don’t require any particular algorithms to solve.
Why does all of this matter? First, you can learn more effectively when you have an accurate idea of the nature of a subject. If you think that you’re going to need to know about algorithms, then you’ll focus on learning them. You might even get overwhelmed by all of the algorithms you need to know, which could prevent you from making progress. Another problem with this view of competitive programming is that it leads some people to dismiss it. It’s just “a fun hobby,” is one opinion. Other people go even farther, and claim that “it won’t help you get a job” (despite the similarity between competitive programming problems and technical interview problems). Even some programmers who have trained for major competitive programming events are skeptical about its real-world utility. Competitive programming, a simplified argument goes, is all about speed and algorithms, which programmers rarely need in their day jobs. Therefore, it has little relation to job skills.
Mathematical thinking and coding fluency
I agree that the longer someone trains for competitive programming contests, the more the skills they learn diverge from real-world programming skills. But in the early stages, competitive programming training can help programmers work on two useful skills:
“Mathematical thinking” (a term I’m borrowing from Keith Devlin) doesn’t require knowing a lot of math. With the exception of the problems on Project Euler, ad-hoc competitive programming problems don’t require specialized math knowledge any more than they require specialized algorithms knowledge. What they do require is being comfortable with solving problems quantitatively. This is true for almost all problems, even those that don’t at first seem to be about math. Here’s an example:
One of the requirements in UVa 403 – Postscript is to center a string of text on a 60-column grid. If the string can’t be centered exactly (i.e., so that there are the same number of empty columns to the left and right of the string) then the larger amount of space must be placed to the left of the string. Or as the problem statement puts it, “the string should be centered equally on either side of the 31st column.” And by the way, you have to support two fonts, one that has a width of one column per character, and the other that has a width of six columns per character.
Arithmetic is the most advanced math required to solve this publishing problem. And yet it requires some thinking: What does “centered equally on either side of the 31st column” mean numerically? How does it apply to the large font? This is where the “solve the problem on paper” step of the problem-solving process comes into play. You want to make sure that the mathematical parts of the problem are clear in your mind before you start implementation. Or at least before you start implementing a particular part of the puzzle. I found that UVa 403 as a whole was complicated enough that it made sense to implement it in pieces, like a real software project, rather than solving the whole thing on paper before beginning the implementation step.
It’s tempting to describe this process using the more general term problem-solving rather than mathematical thinking. But programming puzzles do tend to be specifically about mathematical problem-solving, probably because those are the kinds of problems that lend themselves to a programming solution, and to evaluation by an automated judge. Programming contests can’t use interview-type problems about moving Mount Fuji or testing an elevator, since those problems don’t have a single correct answer, and therefore they depend on a human judge for evaluation. Even when a contest includes problems that could be described as “word play” (like finding anagrams), they must be solved in a mathematical context (generating all permutations of a set).
The second thing that beginning competitive programming is about is coding fluency. In my experience, this is the easier of the two components to learn. Ad-hoc problems make only moderate demands on a programmer’s language knowledge. To solve these problems, it is sufficient to know:
- A standard template for your online judge. For UVa, this means being able to read from stdin, write to stdout, and wrap the whole thing in a program. For Java, the program is a
Mainclass containing a
public static void mainmethod. Once you submit your first problem, you have a basic version of this template.
- Language basics: curly braces,
while, data types, and so on. In other words, what you learn from a beginning language tutorial.
- A small subset of the standard libraries provided by your language. In modern languages, these will provide conveniences such as string processing functions, container classes, and mathematical operations. You’ll be able to ignore many other libraries involving features such as networking, graphics, and database access.
Since the set of features that you need to learn for ad-hoc problems is limited, you’ll soon find yourself repeatedly going back to the same ones. Once you get to that point, the goal is fluency. If you don’t have to look up the definition of the second argument to the substring function (is it length or position? inclusive or exclusive?), you’ll be able to move through problems faster and focus on the more difficult parts. This applies both to puzzles and real-world projects in that language.
Discussion of competitive programming often focuses on the top contestants. This is understandable. Professional athletes get more attention than weekend softball tournament players or the people playing foosball down the hall from your office. But this focus can obscure the fact that the beginning stages of learning competitive programming can be useful for average developers looking to improve their coding fluency and quantitative thinking skills. It’s true that there are eventually diminishing returns to practicing the same type of problem. Eventually a competitive programming hobbyist needs to decide whether to get serious about the competitive aspects of the sport. But programmers who don’t do any competitive programming practice, maybe because they have heard negative things about it, are giving up easy returns from the first few hundred hours of practice.
(Image credit: Nicolas Raymond, freestock.ca)