A couple of months ago, I wrote an article about a type of unit test called a learning test. The goal of learning tests is improving your understanding of how code works, rather than verifying functionality or influencing design, the traditional goals of unit testing. This week, I’m going to discuss those traditional goals of unit testing, but in a less familiar context: testing solutions to programming puzzles.
As I wrote in the previous unit testing article, unit testing is a way to improve the design of your code, while giving you the freedom to refactor with less risk of regression. Some programmers question that these benefits are worth the cost of writing test code. But even programmers who are on board with unit testing in general might be skeptical about using the practice for puzzle solutions. Here are some reasons why it might seem difficult to justify:
- In a competitive programming scenario, you’re on a tight schedule. You might only have a couple of hours to solve several problems in a contest. Writing test code is extra coding work that isn’t required.
- Puzzle code has a short lifetime. The benefits of units tests are often realized as code is modified over time. When you’re solving a puzzle, you generally forget about the code after your solution is accepted.
- When you’re writing a puzzle solution, you often need to emphasize different design goals than those promoted by unit testing. The critical design goals for puzzle solutions are: 1) Can be implemented quickly, and 2) Executes under the time limit. Unit tests encourage designs that make it easy to verify correctness while making changes to the code. Sometimes those goals conflict with each other.
There’s nothing wrong with these three objections, but they mainly apply in a competition where your main goal is winning rather than gaining experience. You may sometimes find yourself in that situation, but even experienced competitive programmers spend considerable time practicing outside of competition. So for most people, it’s worth considering the best practice methods, not just the best competition methods. For beginning and intermediate students of competitive programming, or those using it for purposes like preparing for an interview or attaining fluency in a programming language, it’s even more important to think beyond the competition mindset. For those scenarios, the objections listed above are less relevant. Instead, you can think like this:
- You can spend as long as you want on a solution, as long as you’re still deriving learning benefits from the process.
- After you finish a solution, it’s useful to keep your puzzle code for reference when you encounter similar puzzles. One of the talents that experienced competitive programmers develop is learning to spot recurring patterns across problems.
- Although experienced competitive programmers use a design style intended to squeeze every second out of their implementation time, it’s more effective for most puzzle solvers to code in a way that is easy to understand and debug. Unless a puzzle is very easy for you, it’s unlikely that you’ll get it right on your first attempt. Clearly-written code will speed up the inevitable debugging work.
The one constraint that you can’t get away from is program runtime. If your solution runs significantly outside the time limit, your only option is to try a new design. This isn’t a bad thing: it’s the point of programming contests. You wouldn’t want to be able to solve every puzzle by brute force, since that would bypass much of the learning benefit that you get from looking for the right algorithms and data structures to solve a problem. So regardless of the design that your unit tests lead you toward, you do need to keep runtime performance in mind.
Unit Testing Tips
If you decide to use unit testing as part of your programming puzzle practice, here are some suggestions on how to approach it.
Include it in your template
You’re more likely to write unit tests if your template code supports them. That way you don’t have to write any unit testing boilerplate code, or think about how to set up your test class. It will just be there as you start to implement your solution. See next week’s article for an example of such a template.
Don’t use it for every problem
Despite its benefits, unit testing is overkill for easy problems. What is “easy” depends on your experience level. But if you can solve the problem with one short function, the unit test is basically the sample input. If you’re using uHunt, you can use the problem level as an indication of whether you should start with unit tests, or just code the solution directly.
Use a text file for test input
In standard unit testing, test data is often hard-coded in the test methods, and passed directly to the class under test. This improves test performance by avoiding disk access, and can make test code easier to read by keeping the data with the code. However, there are also times when it makes sense to read test data from a file. A test that requires XML data might use this approach.
Programming puzzles almost all use stdin/stdout for retrieving test data and printing results. In a unit testing environment, it’s easy to substitute a text file for stdin. For output, the approach is a bit different. Your unit tests will be testing intermediate results returned from functions. So you don’t necessarily need to verify the contents of an output file in your unit test code. When you get to the point where you’re writing to stdout, the rest of your solution should be tested already. As a final verification, you can diff the output of your program against a file containing the results that you expect. This is the standard way of testing puzzle solutions without unit tests, but the tests that you wrote for intermediate results make it less likely that you’ll find any major problems in the final diff.
Prefer public members
There’s a debate in unit testing circles about whether private methods should be tested, and a related debate about whether using private methods is even a good practice. For the purpose of puzzle solution unit testing, you don’t have to worry too much about those debates. In most cases, you should just make your class methods and instance variables public. If you have a very simple method that is called by other methods, you could make it private. But a public method is usually best. Public methods can be called from your test class and tested directly. Similarly, public instance variables are easy to examine in test code. The risk of inadvertently altering these variables, which is important to consider in programming projects, is not much of an issue with puzzle solution code.
Refine your test data as you go
Unit tests help you test your solution as you build it. For puzzle solutions, the input data that you use is key to validating whether your implementation is correct. As you write test code and solution code, you’ll have to come up with input data that properly verifies the portion of the solution that you’re working on. The sample data provided in the problem description generally provides only a basic test. uDebug has comprehensive test data for many UVa OJ problems. This can be used to verify your complete solution. But with the unit test approach, you also need to come up with data to verify individual methods. Usually this means manually calculating what a method result should be, and then asserting that result in a test. If you do this for each method you implement, it’s more likely that your entire program will pass when you run it against uDebug test data and then against the official judge. This can result in less overall debugging time.
Unit Testing Challenges
You may find the unit testing approach to be challenging at first, especially if you’re new to unit testing in general. Unit testing certainly requires a different kind of thinking compared to solving a problem directly. Here are some difficulties that you may run into, along with some ideas for overcoming them.
Experimentation
Solving a programming puzzle often requires experimentation. You’ll have false starts that require you to throw out code. If you’re writing tests at the same time as your solution, you’ll be discarding even more code. There’s no way to avoid this problem completely, but you can reduce its impact by being flexible about when you write tests. The key is to use a balanced approach. If you always write tests before writing any code, you may find it hard to brainstorm potential solutions. But if you wait too long to write tests, you may get locked into a less testable design, or end up not writing tests at all. This is not as big a deal with puzzle solutions as it is with software projects, but it can still lead to excessive debugging time.
Coding Velocity
Although you aren’t under strict time pressure if you’re just practicing puzzles, you may still feel like you could get more experience by solving problems faster, and therefore solving more problems, without writing unit tests. Whether this is true depends a lot on how much time you spend debugging your solutions. If the time you spend debugging is small compared to the time you spend on implementation, then you may be able to move up to harder problems. If you spend a lot of time debugging, the unit testing approach can reduce your overall time per problem. But even if tests do slow you down a bit, the goal of practice is not to get through as many problems as possible, but to learn as much as possible from each one. Tests can make you think through a solution in a way that helps you understand it better.
Designing for runtime performance
When you’re writing and unit testing components of a solution individually, you have to be aware of how the solution will perform when these components are combined. For example, consider a solution that you have decomposed into the following method calls:
results1 = GetStep1Results(input);
results2 = GetStep2Results(results1);
PrintFinalResults(results2);
The advantage of splitting the solution into three steps is that you can implement and test each one individually. Your unit test code can examine the contents of results1 to ensure that it’s correct before moving on to Step 2. The code that prints the final results is isolated in its own method so that the unit test code doesn’t have to deal with console output.
From a performance point of view, this design might be fine. The solution algorithm might inherently require creating a complete set of intermediate data before operating on any of it. This is the case with the number line segments from last week’s UVa 11572 editorial. However, it’s possible that the optimal solution for the problem that you’re working on allows Step 1 and Step 2 results to be processed concurrently within the same loop. If your implementation is close to the time limit, the extra overhead of writing to results1, reading it back, writing to results2, and then reading from it to print the final output, might push you over the limit. In that situation, you probably won’t find out that you have a performance problem until you make a submission to the online judge, at which point you’ll have to refactor your code. However, refactoring might just mean combining the three methods, which shouldn’t take long. And meanwhile you will have saved some time in debugging.
If you’re way over the time limit, then you are using the wrong algorithm, in which case you’ll have to throw out a lot of code and tests. But learning to select the right algorithm is a big part of competitive programming practice, so there’s no getting around that.
Benefits of the Unit Testing Approach
A difficult programming puzzle remains difficult when you tackle it with the unit testing approach. But unit tests encourage you to decompose the solution into pieces that you can test individually. Tests also ensure that as you add and modify code, you don’t break anything that was previously working. You could accomplish the same thing by running your program against test data as you build it, and inspecting the output. But this becomes cumbersome as your program gets larger, and it’s easy to miss subtle changes in the output.
Approaching a hard puzzle as a series of individually tested pieces helps you focus on the right part of the problem at the right time. At some point you still need to deal with the core of the problem, the challenge that the problem setters came up with to make it hard. But if you test as you go along, you’ll be more likely to spend time on the real problem, and not an off-by-one error or a misunderstanding about how a library function works.
Having a process for solving programming puzzles can help you focus on getting better at completing each step. Reading and understanding a problem statement requires different skills from solving a problem on paper, writing out the solution in pseudocode, or coding it in a programming language. By thinking about how you approach each step, you can come up with ideas for improving your process. Unit testing is an enhancement to the coding step. It helps ensure that you understand why you are writing each line of code, and what that line contributes to the solution. It requires discipline and an up-front time investment. But you may appreciate the results. Give it a try and find out.
An Example
Next week, I’ll take a problem from uHunt and illustrate how to solve it with the unit testing approach.
(Image credit: Doran)