How to Attack a Programming Puzzle

If you want to get a lot better at a skill, you need a process for practicing it. When you follow a process, it encourages you to practice in a consistent way, rather than using whatever practice technique you happen to feel like using on a given day. As you get experience using your process, you can look for ways to improve it. In fact, improving your process should be a step in your process, since improvements makes your practice more effective every time you use the process. In this way, you can set up a virtuous cycle where your practice helps you improve your process, which in turn improves your practice. Here on Red-Green-Code, I’m working on a process for getting better at programming.

A Terse Barman, Mr. Leg Hop

About halfway through Chapter 1 of the uHunt Starred Problems, there are three anagram problems:

• UVa 156, Ananagrams: Given a dictionary, find the words that cannot be turned into other words by rearranging their letters.
• UVa 195, Anagram: Generate all anagrams (strings formed by rearranging the characters in a string) of each phrase in a list.
• UVa 454, Anagrams: Given a dictionary of phrases, find all anagram pairs (two phrases that can be turned into each other).

uHunt Chapter 1 contains problems that are described as ad-hoc problems. This just means that they don’t fit into any of the other chapters. For example, their solutions don’t require graph algorithms (Chapter 4) or any special mathematics (Chapter 5). You might argue that these anagram puzzles belong in Chapter 6 (String Processing). But many introductory competitive programming problems require some amount of string processing. So it’s best just to think of Chapter 1 as a collection of reasonably easy problems that are helpful in gaining experience in solving the type of puzzle that appears in a programming competition.

The UVa Online Judge

uHunt draws problems from the UVa Online Judge (UVa OJ), which can be quirky to use. Here are some tips on getting around its odd behavior so you can focus on problem-solving.

Tip #1: Use a browser that UVa OJ likes

If you visit UVa OJ using Chrome, you may get an error message: “This webpage has a redirect loop.” Firefox reports a similar error message: “The page isn’t redirecting properly.” Internet Explorer seems to work fine. In the forums, some people report that clearing their browser cookies solves the problem, but I find it easier just to keep an IE window open for reading problems and submitting solutions.

Tip #2: If you’re using Java, put your solution code in a class called Main

Main is the class that the submission engine looks for. If you use a different class name, your submission will fail. On your local machine, it’s best to create a subdirectory for each submission and name it using the problem ID. That will help you keep track of all of your Main.java files.

Tip #3: Use a template source code file

The standard UVa OJ problem framework is:

• Read lines of input
• Process them in some way
• Print lines of output

There are a few different ways the input can be formatted. It’s common for the number of tests cases to appear at the top of the input file. Other problems just want you to read to the end of the file, without telling you in advance how many cases there are. You may need to handle blank lines in the input in a particular way. But there’s enough in common between problems that it makes sense to start your problem-solving process with a Main.java that already contains the code to consume test cases. Then you can just insert your solution in the appropriate spot. You can take a look at my template file in GitHub.

Tip #4: If you get stuck, use all available resources

Since UVa OJ has been around for a while and doesn’t have a large maintenance budget, it has quirks that you have to put up with. On the other hand, there’s a long history of people who have solved the problems before you, some of whom have created useful resources. For example:

• uHunt makes it easier to navigate through the problems, decide which problem to solve next, and keep track of your problem-solving history.
• uDebug provides the correct output for a problem given input that you specify. For some problems, it also provides suggested or random input. uHunt links to the uDebug page for each problem. One note on uDebug: its output doesn’t always match the current UVa OJ accepted output. For example, right now when I open the uDebug page for Anagrams and click Critical Input and Go!, the “orchestra = orchestra” line is repeated three times. According to the problem description, “Each anagram pair should be printed exactly once.” The UVa judge agrees, and it has the final say. So use uDebug, but don’t spend too much time trying to get your output to match the uDebug output before you make your first submission.

[Update: uDebug fixed this issue as of 11 Jun 2015.]

• The UVa Online Judge discussion board is a place to discuss problems. uHunt has a handy search link for each problem, which returns discussions about that problem. You’ll often find hints about issues that others had trouble with.
• Some UVa problem-solvers use GitHub or blogs to preserve a record of their efforts. For example, searching the Web for UVa 454 returns some results with solution code for that problem. Obviously there’s not any learning benefit in submitting those solutions as-is, but you can learn a lot by studying the code and seeing how different programmers solved the same problem.

Tip #5: Make sure your output is clean

The UVa OJ solution checker is picky about exact formatting. Make sure your output exactly matches what is described in the problem statement. For example, UVa 454 has specific requirements about blank lines in both the input and output text. If you have too many or not enough in your output, you’ll get a Wrong Answer result.

Tip #6: Java performance may be tricky

UVa 195 is a standard problem given to Computer Science students: generate all permutations of the characters of a string. The only specific requirements in this version of the problem is that no duplicates are allowed in the output, and the output must be sorted in lexicographic order, with uppercase letters sorted before their lowercase equivalents. A recursive solution to a similar problem is provided on Princeton’s Intro to Computer Science site. However, submitting a solution like this to UVa OJ results in a Time Limit error, which means the running time exceeded three seconds. I found a different recursive solution, and a more complex solution that manages its own stack, but they both reported TL. A C++ solution, which can be implemented in few lines of code using the standard next_permutation function, completed in 0.292 seconds. Since I don’t see this degree of variation in runtime between the Java solution and the C++ solution on my local machine, there must be something about the online judge that is causing the Java solution to run slowly for this problem. So keep that in mind if you run into Time Limit errors when submitting Java solutions. It may not be a problem with your algorithm.

UVa 454: Anagrams

In Deliberate Practice for Software Developers, I outlined a process for solving competitive programming problems. Here’s how I used that process when solving UVa 454, the anagram pairs problem.

Start a timer

There are several advantages to keeping track of time spent solving puzzles. First, solving 462 problems is a long-term project, and keeping track of time helps me estimate when I’m going to finish. Second, I can set goals for practice time, which I find is a good way to ensure consistent progress. Third, looking for parts of the process that take more time than others helps pinpoint areas I need to focus on. Recently I have started timing each step of the process — for example, time spent writing pseudocode vs. time spent writing real code. I use a free tool called Grindstone that makes it easy to set up and track multiple tasks.

Select a problem

I’m just going in order through my uHunt page, so this step is easy.

Make a fresh copy of your template code

I have a shell script that that copies all of the appropriate files into place. So for this step, I just type:

uva 454

This creates a directory named 454 containing a new Main.java file with template code, an input.txt, and various other files. It also opens them in an editor.

Read through the problem statement, making notes about requirements and potential difficulties. Re-read the problem statement if necessary until you understand the requirements, or at least until you can make an assumption for each unclear requirement.

I use this step to take notes on the details of the problem, so I don’t have to re-read it while I’m working on the solution. The problem statement for 454 isn’t too complex, so I mostly noted requirements for the input and output text:

ignore blanks in phrases

input
    # of cases (n)
    (blank line)
    some number of phrases
    blank line
    some number of phrases
    blank line
    ...
    some number of phrases
    blank line

output
    phrase1 = phrase2 if phrase1 and phrase2 are anagrams
    ...

output rules
    only print each pair once
    lexicographic order within a pair and within the list
    blank line between output sets

Solve the problem on paper

After thinking about the problem for a few minutes, I decided to use a character counting approach. An anagram is formed by rearranging characters. Therefore, two phrases are anagrams of each other if and only if they have exactly the same number of each character in the target character set.

Here’s how I expressed that solution idea in note form:

remove spaces
store character counts
if character counts match, then anagram

Expand the solution into pseudocode

The advantage of pseudocode is that it allows you to work out the steps of a solution without getting hung up on the syntactical details of your language. Top competitive programmers generally don’t use pseudocode, at least for easy problems. I use it unless the problem is very easy. For problems where I decided to use it, I have been spending about 10-20% of my total time on this step. This would be too much extra time to spend in a competitive event. But I’m not worrying about competitive events yet. If you’re completely fluent in a language (you never have to stop and think about syntax), and you can also hold the details of a solution in your head as you are coding it, then you can probably skip this step. If you find yourself forgetting what part of an algorithm to implement next, having pseudocode to refer to can help keep you on track.

Here’s my pseudocode for this problem, as written before I implemented the real code:

read number of cases
read blank line
for each case
    until blank line
        read phrase string
    sort phrases
    for each phrase
        create int array counts
        for each char in phrase
            if blank, skip
            else increment char count
        add counts to list
        for each item in list
            for each other item in list
                check each char count
                    if not equal, break
                    else continue
                if all matching, add output row to list
    for each item in output list
        print unless equal to previous item

Translate the pseudocode into real code, making note of any parts that you find difficult to translate

At this point in my trip through the starred problems, I still have to think about Java syntax. When I run into syntax problems, I make a note of them. For this problem, I noted these syntax tips:

• To sort a primitive array, use Arrays.sort(name). To sort a collection, use Collections.sort(name).
• List<String> output = new List<String>(); is not valid, since List is an abstract class. Instead, use List<String> output = new ArrayList<String>();
• String str = output[0] doesn’t work. Instead, use String str = output.get(0)

Test locally and debug if necessary until you’re satisfied with your answer

This step includes testing your code against the test input provided in the problem statement, and any other test input you come up with. My implementation didn’t work the first time, so I had to do some debugging.

Check your answer by submitting your solution or, if you’re using an offline source of problems, looking up the answer. Debug and recheck as necessary until you have a correct solution.

Since this is a UVa OJ problem, it can be checked by submitting through UVa OJ Quick Submit and then looking at the uHunt dashboard for the submission status. In my case, this led to more debugging, including the blank line issue I mentioned above. Since UVa OJ doesn’t provide any clues about which test cases failed, this is also a good time to use uDebug or GitHub. For 454, both uDebug and a submission on GitHub printed answers with multiple identical output lines, which is prohibited by the problem statement. This leads me to believe that this problem may have changed in the years since it was originally published. Eventually I got it working. You can find my solution in GitHub.

Stop the timer and record the elapsed time

Here are the timing statistics I calculated as I worked through the steps. I expect the absolute times as well as the relative time taken up by each step to change as I work through more problems.

Read problem                      0:11:30    8%
Solve on paper                    0:08:40    6%
Write pseudocode                  0:15:15   11%
Write real code and test locally  1:01:05   44%
Test online                       0:40:50   30%
Total                             2:17:20 

A Deliberate Practice Reminder

Much of the power of deliberate practice (see elements #3 and #4) derives from observing your performance and looking for ways to improve. As you solve programming problems using the process explained above, you can continually be writing yourself notes on what seems difficult. If the compiler catches a syntax error, copy and paste it into your notes document so you can review it later. If you need to consult the language documentation to find out how to call a particular method, make a note to create an exercise that allows you to practice the method call. If your testing exposes a problem with your algorithm, think about whether the problem is specific to this puzzle, or whether there’s an underlying pattern you need to learn better. Although improvement always requires repetition, a little metacognition goes a long way as you’re doing those repetitions.

(Image credits: hillman54, Radosław Cetra)