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.
Language Fluency
When you work on ad-hoc programming puzzles, one of the outcomes is greater familiarity with your chosen programming language. Because the algorithms required to solve the problems are straightforward, you spend less time working out the algorithm and more time deciding how to express it in a programming language. This is a bit like learning a natural language. Imagine that you’re learning to speak French. When you first start out, you practice talking about simple matters, like how to find the restroom. You don’t have the skills yet to discuss whether or not Camus was an existentialist. But although your conversations in French won’t be complex, they will be numerous, since you’re eager to make progress. Similarly, when pursuing programming language fluency, you’ll want to solve a large number of ad-hoc puzzles rather than rushing ahead to more complicated problems like building a web server. By keeping the domain simple, you can make sure you have a good foundation in language fundamentals.
Knowing even a subset of a natural language can be useful for communicating in a restricted domain. For example, if you’re ordering lunch in a Paris restaurant, you’ll need mainly food and drink terms. That evening, if you’re at a party asking an astronomer about her research, a different vocabulary would come into play. In the programming world, ad-hoc problems require knowledge of the basic components of a programming language — for
loops, if
statements, where to put the curly brackets, and so on. It also requires a set of library functions for tasks such as reading lines of text, parsing space-delimited strings, and working with two-dimensional arrays. You won’t need to know about reading bytes from a socket or animating a sprite unless you’re participating in a networking or computer graphics competition. By solving enough ad-hoc problems, you’ll come across all of the language and library features for that domain. There’s a limited set of features available in a language, and the subset that you’ll actually need in competitive programming is even more limited. Therefore, as time goes on, you’ll spend less time thinking about syntax and more time thinking about algorithms and problem-solving. When you can implement the solution to any ad-hoc problem without stopping to think about how to express it, then you’ll know that you’re fluent in a language.
Parsing Strings in Java
I happen to be using Java for Project 462. I first learned Java over 10 years ago, but I have never used it professionally. (C# is my work language). So I often come across situations where I know the concept I need, but I can’t remember how to express it in Java. For example, programming puzzles often require getting a character from a string. In Java, you can’t use array syntax with strings. To get the third character from a string called line
, you would need to do something like this:
char c = line.charAt(2);
Since the same language idioms come up repeatedly in programming puzzles, they eventually become second nature. However, it could still take a number of problems to become fluent in a commonly-used language feature. To speed up this process, I find it useful to maintain a Java program containing a set of useful code snippets. Whenever I’m working on a puzzle and I need to look something up, or even if it takes me a few seconds to remember a piece of syntax, I add it to the list. My goal is to have all of the syntax I need at my fingertips, so I can focus on solving the problem. You can find my Java reference class on GitHub.
Fancy Editors
A perennial topic of debate among programmers is which editor or IDE to use. Quorans, of course, have a version of this debate that is specific to competitive programming. For the purpose of the ad-hoc stage of competitive programming training, I recommend using something simple. Programming editors are designed to shift some of the cognitive burden of programming away from the programmer. That’s why many of them have features like autocomplete, which remind the programmer how to use a language or framework feature. While a full-featured editor definitely improves productivity, it is somewhat at odds with the goals of increased language fluency. Like a native speaker who jumps in to finish your sentences, a programming editor can prevent you from ever becoming completely fluent in a language. This is what has happened to people who can program at a keyboard, but not in front of the whiteboard during an interview.
Coding on the Whiteboard
Taking the simple editor argument to an extreme could lead to the conclusion that programming puzzles should only be solved on a whiteboard. It is a good idea to do this on occasion, as recommended by interview preparation guides. But I’m going to use a less extreme approach and say that using an editor is fine in most cases for competitive programming practice. My reasoning: the primary measure of coding fluency is how well you can translate an algorithm idea into a real implementation. Whether the implementation happens on a whiteboard, a sheet of paper, or a basic text editor is less critical, assuming you’re reasonably good at typing. So while I like the idea of solving puzzles on a whiteboard once in a while in order to keep any whiteboard-specific mental and physical muscles in shape, in most cases I stick to a text editor. I happen to use UltraEdit because I’m familiar with it, but any editor will do as long as it can be configured not to provide too much help.
At work, I use Visual Studio, so I don’t have anything against fancy IDEs. They’re essential for working on complex projects. Similarly, for serious competitive programmers looking for ways to shorten their submission time, it makes sense to customize an editor for that purpose. Editor features like templates and compiler integration can speed up the competitive programming workflow. But at that point you’re past the point of working on language fluency.
The Benefits of Fluency
No one questions the benefits of natural language fluency. If you’re fluent in French, you can visit Paris and talk to the locals. When you’re in a conversation, you don’t have to think about the words you’re using. You just think about saying something, and it comes out of your mouth in French. The best way to get to this level of fluency: hang out with a lot of French people and say en français s’il vous plaît whenever they try to speak to you in some non-French language. I spent part of my youth in a French school, but since I didn’t follow this rule and my peers were bilingual, I didn’t get as much French practice out of the experience as I could have.
To get fluent in Java, you have to hang out with your computer a lot, and talk to it about algorithms. It’s surprisingly easy to avoid becoming fluent in a programming language, even if you use it a lot. Advanced editors, Stack Overflow code snippets, and looking at existing code from the product that you’re working on all contribute to that. As an antidote, you have programming puzzles. Repeatedly solving problems from scratch in an editor with all of the bells and whistles turned off is like being at a party where people keep asking you questions and expecting intelligent responses in their native language, which happens to be Java. Now that would be a great party. Eventually you get rather fluent at constructing sentences and paragraphs without referring to your pocket dictionary.
So what’s the benefit of being fluent in a programming language? For one thing, you won’t end up like the guy with the CS PhD who gets tripped up by the FizzBuzz test. As they say on the Internet, “Don’t be that guy.” But more importantly, being fluent in a programming language means one less thing to worry about when you’re in the middle of a programming project. Programming is complicated enough without having to think about fundamental language issues while you’re trying to solve conceptual problems. As Computer Science luminary Edsger Dijkstra said in his Turing Award lecture, “The competent programmer is fully aware of the strictly limited size of his own skull.” Free up some room in there by getting fluent.
(Image credit: Jimmy Baikovicius)