Getting Started With UVa Online Judge: The 3n+1 Problem

LotharCollatz

If you’re interested in competitive programming, or you just like solving programming puzzles, UVa Online Judge is not a bad place to start. During the many years that it has been active, people have written books, supporting web sites, and sample code to help programmers get more out of it.

As my contribution to the ongoing commentary on UVa OJ problems, I have been working through and writing about the CP3 starred problems, a subset of UVa OJ problems recommended by the authors of a companion textbook called Competitive Programming 3.

But this week I’m picking a problem that is not on that list: the popular problem #100, also known as The 3n+1 Problem. The origin of problem #100 is the Collatz conjecture, a mathematical conjecture posed by the German mathematician Lothar Collatz, pictured above.

Since I want my friends to keep calling me, I won’t be trying to prove this conjecture (which remains an open problem as of this writing). Instead, I’ll just be writing a short program to count the elements in the sequences generated by the $3n+1$ algorithm. Along the way, I’ll explain a process that you can use when you’re solving other UVa OJ problems.

Solving a UVa OJ Problem

If you’re planning to solve more than a few programming puzzles, I would recommend developing a problem-solving process. That way you’re not just solving each problem in isolation. You’re also working on the larger meta-problem of how to solve programming problems. That will be more useful in the long run.

Here’s the quick-start version of the process I use:

Read the problem

Before you start thinking too hard about the problem, it’s worthwhile to read the problem statement carefully. Competitive programming problems have a reputation for including extraneous information and confusing language in their descriptions. One way to get through this is to take notes about key ideas as you read. That way you can refer to your notes as you solve the problem, rather than re-reading the confusing description.

When I first read the problem statement for UVa 100, it reminded me of Project Euler Problem #14, which I had solved before. Nevertheless, when I came across this statement in the description, I found it puzzling:

For any two numbers $i$ and $j$ you are to determine the maximum cycle length over all numbers between and including both $i$ and $j$.

When I read that, I got hung up on the “over all numbers” wording and thought it had something to do with the length of a cycle beginning with $i$ and ending with $j$. But of course it just means:

for each integer x between i and j (inclusive)
    calculate the length of the Collatz sequence that starts with x
return the maximum of these lengths

If you’re confused by the wording of a problem, it often helps to skip to the example input and output to clear things up. Some people even recommend reading problems from the bottom up: start with the sample data and end with the introduction.

Solve it on paper

After reading the problem statement carefully, the next step in solving a programming problem is to “solve the problem on paper.” That’s similar to what I did in the previous paragraph. The steps listed above aren’t the complete solution (e.g., they don’t print anything), but they cover the key idea of the problem. You could even be less formal with your paper-based solution, and just write: “Generate the Collatz sequences that start with each integer between i and j, and return the length of the longest one.”

Whether it is written precisely or casually, I find that it’s useful to come up with a big-picture solution before digging into the details of a problem. For difficult problems, what you come up with in this step may not even turn out to be a correct solution. But it provides a starting point and ensures that you have at least some idea of what is being asked before you move on to coding.

Write pseudocode

Once you have a paper solution, you can write a pseudocode solution. The purpose of pseudocode is to express a complete step-by-step solution without worrying about syntax. Translating a solution in your head directly into a real programming language means doing two complex tasks at the same time: breaking down the solution into steps, and expressing those steps in a programming language. It’s generally more effective to get the solution steps out of your head first, and worry about the language details later.

Here’s one way you could express the pseudocode solution for UVa 100:

for each test case
    read i and j from input
    set lo = min of i and j
    set hi = max of i and j
    for each x from lo to hi
        set len = cycle(x)
        if len > maxlen, maxlen = len
    print i j maxlen

cycle(n)
    set len = 1
    while n > 1
        if n is odd, set n = 3*n+1
        else set n = n/2
        increment len
    return len

The style of pseudocode syntax you use is up to you. Since you won’t be feeding it into a compiler, you can use any syntax that helps you clarify the solution. Here are some language features that are often missing from pseudocode:

  • Unnecessary punctuation (parentheses, curly brackets, semicolons)
  • Variable declarations
  • Implementation details like the names of library methods

The key is to avoid anything that will distract you from expressing the logical steps of the solution. If you have to look up any syntax, then it doesn’t belong in pseudocode. Once you have spent a lot of time on competitive programming, you may reach a level of expertise where you are so fluent in a programming language that you don’t have to think about syntax. At that point you’ll probably skip the pseudocode step. But until then, it makes sense to think about the problem independently of the implementation language.

Implement the solution

Once you have pseudocode written and you think it’s correct, it’s time to translate it into real code. Since UVa OJ can be picky about details, it’s best to start with a template containing the code that is common to all solutions (e.g., functions for reading input and writing output). You can find templates for the supported languages on the UVa OJ submission specification page. If you’re using Java, I maintain a template that I use for my solutions. It’s overkill for this problem, but it contains some functions that will save you some headaches for other problems, especially when it comes to input and output performance.

I’ll mention two details about implementing the solution to UVa 100. First, it’s helpful to know that the modulo operator (the % symbol in C-like languages) returns the remainder of a division operation. For example, if n % 2 == 0 then you know that n is even. Modulo is also useful to know about if you find yourself having to solve the FizzBuzz problem, which is sometimes used as an interview question.

The second detail has to do with runtime errors. A runtime error verdict means that an unhandled error occurred while your program was executing, and resulted in an exception or segmentation fault. One way this can happen is when you try to process input in a format you didn’t expect. Although my first attempt at this problem gave the correct answer for all of the uDebug random input, I got a runtime error when I submitted it to UVa OJ. I tried modifying my code to ignore any lines containing only whitespace, and my submission was accepted. This is a good reminder that you shouldn’t trust the input from the online judge.

For Further Reading

So there you have it: a process to get you started solving UVa 100 and other problems on UVa Online Judge. If you’re planning on trying other UVa OJ problems, you may be interested in some of my other articles. Here are a few suggestions:

  • How to Attack a Programming Puzzle: an extended version of the process described above, using UVa 454: Anagrams as an example. It contains more hints on dealing with UVA OJ’s quirks.
  • Project 462: the story of how I got started solving the starred problems. Maybe you’re interested in working on a similar project.
  • The Puzzle Approach to Coding Mastery: the benefits of using programming puzzles to get better at programming.
  • Summer Review: a summary of the first thirty articles on this site. This is a quick way to find other topics that you might be interested in.

(Image credit: Konrad Jacobs)