Deliberate practice techniques for software developers
Last week I wrote about solving UVa 11085 using the recursive backtracking search technique. This week, I’m going to outline a more general approach to recursive backtracking problems. Then I’ll show how it can be adapted to solve UVa 574.
UVa 574 asks us to solve this problem:
Given a multiset $S$ of integers and a target sum $t$, find all subsets of $S$ that sum to $t$.
The uHunt Chapter 1 starred problems contain three examples of chess problems. In Chapter 3, we get back to chess with a variation on the classic eight queens puzzle. UVa 11085 is used to illustrate the algorithmic technique known as recursive backtracking.
Some programming puzzles can be solved by simulating a game or process. For example:
UVa 11553 may seem like a classic simulation problem: a board game between two players. But it soon becomes clear that this problem can’t be solved by simulating the players’ moves.
When they select their tools, programmers have a choice between command-line and GUI options. Most people use both. For example, I prefer to use GUI tools for diffing a set of files I’m preparing to commit to a source repository. I also like my editor to be graphical, though I use a lot of keyboard shortcuts. But command-line tools are preferable when I’ll be repeating the same action multiple times. It’s a lot more efficient to retrieve a typed command from the shell history than to do the same steps repeatedly using mouse clicks or even keyboard shortcuts. Today I’ll be explaining some commands that are useful for programming puzzles.
UVa 11236: Grocery Store is an unusual problem for UVa Online Judge: it takes no input! There’s just a problem statement explaining the rules for finding the output. The lack of input and the mathematical nature of the problem reminds me of the problems on Project Euler. And as with Project Euler, you could cheat the time limit by calculating the output offline and just having your program print it. But if you would rather write a program to solve this problem quickly, keep reading for ideas.
If you practice programming puzzles regularly, you probably keep an archive of your solutions. This can be useful for reference when you encounter similar problems. And even if you never look at some of them again, disk space is cheap and source code is small, so why not?
The simplest way to save your solutions is to put all of the files related to each solution (source code, input text, sample output text, etc.) in a directory on your local disk. I suggest going one step beyond that, and using a source control system to keep track of your solution files. These days, it makes sense to use Git.
For many years, Cal Newport has been writing about ways to get better at doing difficult things. His first three books were manuals for students, advice on learning techniques and where to focus one’s efforts during high school and college. In 2012, he wrote So Good They Can’t Ignore You, about building career capital by mastering valuable skills. While he was writing these four books, he also published the Study Hacks blog, which covers similar topics on a weekly basis.
Cal’s latest book, published last week, is Deep Work: Rules for Focused Success in a Distracted World. This one offers the following challenge: to improve your ability to do what is difficult, you first have to spend less time doing what is easy.
Combinations and permutations are worth learning about for programming puzzles, and for programming in general. UVa 735: Dart-a-Mania provides a basic introduction.
One year ago, I started writing here on the topic of deliberate practice techniques for software developers. This is my 52nd weekly post for 2015. With the year coming to an end, let’s review the story so far.
From time to time, I’ll run across a UVa problem description that makes liberal use of mathematical notation. UVa 927, the first starred problem in uHunt Chapter 3, is one of those. uHunt classifies it as a Level 4 problem, but most of the challenge is in interpreting the problem description. Once you figure out what it’s asking for, the problem itself is straightforward.