UVA 100: "The 3n + 1 problem"

I’ve solved UVA Problem 100: The 3n + 1 problem . In short, the task was to write a program that calculates a maximum of Collatz sequence lengths for any given range of starting values.

My program:

```
#ifdef ONLINE_JUDGE
#define NODEBUG
#endif

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

using seqlen = unsigned short;
using seqval = unsigned long;

constexpr seqval inputMax = 999999;
constexpr seqval inputMin = 1;

seqlen getLength(seqval n)
{
assert(n%2 == 0 || n cache {{1,1}};

if(cache.count(n)) return cache[n];
return cache[n] = getLength(n%2==0 ? n/2 : 3*n+1) + 1;
}

seqlen getRangeMax(seqval i, seqval j)
{
assert(i = inputMin && j >;
static cache_t cache;

if(i == j) return 0;

auto exponent = static_cast(floor(log2(j-i)));
auto interval = static_cast(pow(2,exponent));

seqval lb, ub;
while((lb = (ub = interval * (j/interval)) - interval) (pow(2,--exponent));

if(exponent == 0) return getLength(lb);

cache.resize(max(cache.size(), exponent));
return max(
max(getRangeMax(i, lb), getRangeMax(ub, j)),
cache[exponent-1].count(lb) ?
cache[exponent-1][lb] :
cache[exponent-1][lb] =
max(getRangeMax(lb, lb+interval/2), getRangeMax(lb+interval/2, ub)));
}

struct testCase
{
seqval i=0, j=0;

friend istream &operator >> (istream &is, testCase &tc)
{
if((is>>ws).eof()) {return is;}
string inpstr; getline(is, inpstr); if(!is.good()) return is;
stringstream inp(inpstr+'\n'); inp >> tc.i >> tc.j;
if(!inp.good()) {is.setstate(inp.rdstate() |
((inp.rdstate()&ios_base::eofbit) != 0 ?
ios_base::failbit : static_cast(0))
); return is;}
if(tc.i inputMax || tc.j > inputMax)
{is.setstate(ios_base::failbit); return is;}
if(!(inp>>ws).eof()) {is.setstate(ios_base::failbit); return is;}
return is;
}

bool noInput() {return i==0 || j==0;}
};

int main()
{
#ifdef NODEBUG
ios_base::sy

People tell me my code tends to be ugly and unreadable; I tried to make this one reasonably readable, and I’d especially like to hear comments on this matter.

I'll do my best to keep this kind. People are right, and I'd like to explain why. In the comments, tinstaafl wrote:


All those inline statements make it much harder to see what your code is doing.

To which you reply:


But I was only trying to make the code more concise.

You didn't. Concise code is not code that has as few lines as possible. It is code which expresses exactly what it needs to without any extraneous statements. You haven't reduced the number of statements, just the number of lines. The number of lines of code is relatively unimportant, so long as the code is organized well, easy to understand, and performs well.

For example, you have this:

return max(
    max(getRangeMax(i, lb), getRangeMax(ub, j)),
    cache[exponent-1].count(lb) ?
       cache[exponent-1][lb] :
       cache[exponent-1][lb] =
        max(getRangeMax(lb, lb+interval/2), getRangeMax(lb+interval/2, ub)));

This is not concise. And it's worse than not being concise. It has a very unexpected assignment in the middle of it which will cause it to be misunderstood by nearly every person besides you who tries to read it. It's a bunch of conditionals, assignments, calculations, and branches all crammed into a function call which is also a return statement. The compiler will generate the same results if you write it as:

seqlen result;
seqlen max1 = max(getRangeMax(i, lb), getRangeMax(ub, j));

if (cache[exponent - 1].count[lb] != 0) 
{
    result = max(max1, cache [ exponent - 1 ][ lb ];
}
else
{
    seqlen max2 = max(getRangeMax(lb, lb+interval/2), getRangeMax(lb+interval/2, ub));
    result = max(max1, max2);
    cache [ exponent - 1 ][ lb ] = max2;
}

return result;

Now other people can also read it at a glance and understand what it does without having to first untangle a bunch of other stuff. (Although you should use more descriptive variable names than I've used. I don't know this particular mathematical construct well enough to name things properly.)

Debugging

Your stream operator is particularly egregious. If there's an error in it, how will you debug it? Try stepping through it in a debugger. When you get to, say, this line:

string inpstr; getline(is, inpstr); if(!is.good()) return is;

and find an error in it, how do you know which of those 3 statements contains the error? You can't step over one to the other because it's all one line. That doesn't help anyone.

Are you sure this statement is correct?

if(!inp.good()) {is.setstate(inp.rdstate() | 
  ((inp.rdstate()&ios_base::eofbit) != 0 ?
  ios_base::failbit : static_cast(0))
); return is;}

Is the operator precedence correct? Does logical or come before not equal? I don't remember and if I have to edit that line in the future, I'm likely to screw it up because it's all crammed together and uses minimal parentheses.

Also, you seem concerned about having too many lines, but I count 5... no wait... 6 return is; statements. The flow control of that function is terrible.

One way you could improve it is by having an error variable that you check for whether you should continue or not. For example, this would be one common way to write it:

friend istream &operator >> (istream &is, testCase &tc)
{
    bool error = false;
    if((is>>ws).eof()) {
        error = true;
    }

    if (!error) {
        string inpstr; 
        getline(is, inpstr); 
        if (!is.good()) {
            error = true;
        }
    }

    if (!error) {
        stringstream inp(inpstr+'\n'); 
        inp >> tc.i >> tc.j;

        if(!inp.good()) {
            is.setstate(inp.rdstate() | 
                ((inp.rdstate()&ios_base::eofbit) != 0 ?
                ios_base::failbit : static_cast(0))); 
            error = true;
        }
    }

    if (!error) {
        if(tc.i  inputMax || tc.j > inputMax) {
            is.setstate(ios_base::failbit); 
            error = true;
        }
    }

    if (!error) {
        if (!(inp>>ws).eof()) {
            is.setstate(ios_base::failbit); 
            error = true;
        }
    }

    return is;
}

The reason this is better than returning on error is because it's easy to see at a glance the flow of control. If you needed to allocate a resource at the beginning of the function and release it on return, you now only have a single place you need to do it. (Granted C++ has some good tools for making that much easier, but it can still come up in real-world use.) With your version, I can't tell quickly if there are non-error returns or if all returns but the last are for error cases.

If you want to write concise code learn how to express your ideas with fewer statements rather than fewer lines. And also remember that there's a difference between concise and densely packed. It can be easy to write a very short statement or set of statements which do

StackExchange Code Review Q#156724, answer score: 5