As you know if you’ve been following along, I’m currently working through a book called Competitive Programming 3. Each chapter has a set of practice problems, some of which are identified as “starred problems,” and are especially recommended. Chapter 1 contains 39 starred problems, categorized as “ad-hoc problems.” This generally means that they don’t focus on the standard algorithms that a beginning computer science student might learn. They only require some knowledge of a programming language, and the ability to turn a problem statement into an algorithm. This doesn’t mean these problems are trivial. A few are, but in general they do require some creative thinking. Some problems, such as How Many Knights, require almost no coding, but take some time to work out on paper. Others, such as Jollo, require a greater command of a programming language, and the ability to write and debug short programs (75-100 lines or so). And although these ad-hoc problems don’t involve implementing standard algorithms like binary search trees, some of them do involve well-known puzzles like finding all anagrams of a string.
As I mentioned in my post introducing Project 462, I have spent some time in the past working on historical CodeForces problems to get some idea of what their programming competitions are like. I thought it would be interesting to go through one of those problems, Hot Bath, from the perspective of a CodeForces beginner. In CodeForces Beta Round #93, Hot Bath was Problem C in the Division 2 contest, and Problem A in the Division 1 contest. In the CodeForces system, that means the problem is targeted at Division 1 (more experienced) contestants who are just getting their fingers warmed up at the beginning of a contest, and at Division 2 (less experienced) contestants who have finished a couple of easier problems, and are ready for something that requires more thinking. Based on the information in the standings report for that round, several top Division 1 contestants submitted an accepted solution in about ten minutes, so we can take that as a reasonable lower bound.
The Story So Far
Long ago (2008), I read a post on the “xkcd blag” (yes, Randall Munroe occasionally just writes regular blog posts) about “a site with a lot of math-oriented programming problems that you can solve in any language.” I like math and programming, so that seemed like fun. I spent a few years on and off working through the first 76 problems on Project Euler, at which point the problems started to require more math than I had at my disposal. Around that time (2011), I heard about a site called CodeEval that was coming out of beta. CodeEval also has programming puzzles, but with less of a math emphasis. As I’m writing this post (early 2015), I have finished 107 puzzles on CodeEval. Back in 2011, a site called CoderCharts (no longer online) was briefly popular. CoderCharts hosted contests that ran over several days, like the long contests on CodeChef. That was my first experience with contests that allowed participants to compete against each other during an event. However, the schedule allowed a day or so for each problem, so there was plenty of time to think.
In my deliberate practice plan for software developers, I suggested that aspiring programming experts find a source of programming problems to use as part of a deliberate practice routine. It turns out that there are more pre-packaged programming problems out there than you could get through in a lifetime. Many of them come from the world of competitive programming. Competitive programming is a “mind sport” like a quiz show or a chess tournament. Contestants are given a set of programming problems, and they have to write programs to solve them. In most cases, programs are submitted to an online judge, which verifies that they produce the correct answer and don’t run longer than a specified time limit. Participants are scored according to how quickly they submit a correct and sufficiently fast program. They may also have a chance to submit challenges to try to stump their colleagues’ programs. Competitive programming is most popular among high school and college students outside of the United States, but there are plenty of competitive programmers who don’t fit that profile. For a colorful description of one contest, the 2010 International Olympiad in Informatics, see the Wired article Teen Mathletes Do Battle at Algorithm Olympics. Regular online contests take place at TopCoder, CodeChef, and Codeforces. These sites also provide access to past problems, which can be used for practice.
In Making Sense of the Deliberate Practice Debate and Coding is Underrated, I introduced the concept of deliberate practice, and suggested a specific skill that aspiring software development experts can use as their practice target. I’m now going to go into detail on a deliberate practice process for this skill. Here’s the skill description again:
Write correct, efficient, and maintainable code for a software component given well-defined requirements.
Remember that we’re not just hoping that the requirements will be well-defined. At the instant that you sit down in front of your editor to implement a section of code, your requirements have to be well-defined. If they’re not, then the code that you write becomes the requirement, possibly the wrong one. If you’re not sure about a requirement, clear up any questions before you start coding. Defining requirements is another skill with its own deliberate practice process. For the purpose of the process explained below, I’m going to assume that an expert in that skill (maybe you) has clearly defined the requirements.
In Making Sense of the Deliberate Practice Debate, I argued that deliberate practice is the best way to get better at a skill, even if you believe that innate ability (talent) plays a significant role in how people become experts. In the next few posts, I’m going to start investigating how software developers can apply deliberate practice to a specific skill: Writing correct, efficient, and maintainable code for a software component given well-defined requirements. But first, let’s take a closer look at that skill.
The summer of 2014 was a busy time for online chatter about deliberate practice, the specific type of practice that is designed to improve performance of a complex skill. In July, the journal Psychological Science published a paper (summary, full text) by Brooke Macnamara and colleagues, arguing that practice, even deliberate practice, plays only a small role in explaining the difference between novice and expert performance. This contradicts the argument, made in an influential 1993 paper by K. Anders Ericsson and popularized in Malcolm Gladwell’s Outliers, that even talented people make it to the top of their fields mainly by spending enough time practicing in a particular way. The new result prompted a flurry of articles and blog posts. For example: