UVA 100: “The 3n + 1 problem” take 2

Question

This is my second attempt to solve this problem, my first attempt is here: UVA 100: "The 3n + 1 problem"

This time I tried to take lessons from the failures and mistakes You pointed out in my first attempt.

• I resigned from packing multiple statements in one line. (This resulted in the code length balooning, though :( )
• I removed constructs that I had placed to “optimize” the code, but that were shown to be slowing it down instead, that is std::pow, std::log2 and most importantly, std::unordered_map.
• I did some actual benchmarking, and I think the code is reasonably fast now.
• I added comments whenever I thought my intent wasn’t obvious.
• However I fail to understand why, but OK, I’ve put away the using namespace std
• I still tried to make the code error proof, for example by checking input correctness.
• I’ve put assert macros.

Any comments for this code?

// This program solves UVA Online Judge Problem 100: "The 3n + 1 Problem"
// Problem specification:
// https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36

#ifdef ONLINE_JUDGE
  #define NDEBUG
#endif

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdint>
#include <cstdlib>
#include <cmath>
#include <limits>
#include <cassert>

// aoo = At Or Operator[]
template<class Container>
typename Container::reference
aoo(Container &cont, typename Container::size_type index) {
  #ifndef NDEBUG
    return cont.operator[](index);
  #else
    return cont.at(index);
  #endif
}

template<class Container>
typename Container::value_type::reference
aoo(Container &cont, typename Container::size_type i1,
    typename Container::value_type::size_type i2) {
  #ifndef NDEBUG
    return cont.operator[](i1).operator[](i2);
  #else
    return cont.at(i1).at(i2);
  #endif
}

using seqlen = std::uint_fast16_t;
using seqval = std::uint_fast32_t;

// As of now, the problem specification incorrectly states that all integers
// in the input will be less than 10.000. The correct boundaries, stating that
// integers will be less than 1.000.000, can be found in the archived version:
// web.archive.org/web/20161225044321/https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36
constexpr seqval input_max = 999999;

using cache_t = std::vector<std::vector<seqlen>>;
static_assert(std::numeric_limits<cache_t::size_type>::max() >= input_max,
    "This implementation cannot hold the cache.");

// cache[0] stores lengths of all values from 1 to input_max
// cache[1] stores maximums of lengths of 2-3, 4-5, etc
// cache[2] stores maximums of lengths of 4-7, 8-12, etc
// etc
cache_t cache = []()
{
  //Log2 and pow are slow, but hopefully it doesn't matter in the initialization
  cache_t ret(std::log2(input_max), cache_t::value_type{});

  // 0 means unknown
  for(cache_t::size_type i = 0; i < ret.size(); i++)
    aoo(ret, i) = cache_t::value_type(input_max / std::pow(2,i), 0);
  aoo(ret, 0, 0) = 1;

  return ret;
}();

seqlen calculate_collatz_length(seqval n)
{
  auto collatz_next = [](seqval n) 
  {
    assert(n >= 1);

    if(n%2 == 0)
      return n/2;
    else {
      // Problem specification guarantees us that
      // no operation overflows a 32bit integer.
      assert(n <= (UINT32_MAX-1)/3);
      return 3*n+1;
    }
  };

  seqlen excessive_length = 0;
  while(n > input_max)
  {
    n = collatz_next(n);
    ++excessive_length;
  }

  if(aoo(cache, 0, n-1)==0)
    aoo(cache, 0, n-1) = calculate_collatz_length(collatz_next(n)) + 1;

  return aoo(cache, 0, n-1) + excessive_length;
}

seqlen get_length_from_cache(seqval i, seqval j)
{
  assert(1 <= i && i <= j && j <= input_max+1);

  if(i == j)
    return 0;

  cache_t::size_type exponent;
  seqval adji, adjj, interval;

  auto adjust_bounds_to_multiplications_of_a_power_of_two = [&, i, j]()
  {
    assert(1 <= i && i < j && j <= input_max+1);

    exponent = 0;
    interval = 1;
    auto adjusted_j = [j](seqval interval)
      {return interval*(j/interval);};
    auto adjusted_i = [i,j,adjusted_j](seqval interval)
      {return adjusted_j(interval) - interval;};
    auto broadened_i = [i](seqval interval)
      {return i+interval;};

    while(j >= broadened_i(4*interval) ||
        adjusted_j(2*interval) >= broadened_i(2*interval))
    {
      interval *= 2;
      exponent++;
    }
    assert(interval <= j-i);
    assert(std::pow(2,exponent) == interval);

    adjj = adjusted_j(interval);
    adji = adjusted_i(interval);
    assert(
      adjj <= j &&
      adji >= i &&
      adjj % interval == 0 &&
      adji % interval == 0 &&
      adji + interval == adjj &&
      adjusted_j(interval*2) < broadened_i(interval*2));
  };

  adjust_bounds_to_multiplications_of_a_power_of_two();

  cache_t::value_type::size_type ind = adji/interval - 1;
  if(aoo(cache, exponent, ind) == 0) {
    if(exponent == 0)
      aoo(cache, exponent, ind) = calculate_collatz_length(adji);
    else {
      seqval mid = adji + interval/2;
      assert(mid+interval/2 == adjj);
      aoo(cache, exponent, ind) =
        std::max(get_length_from_cache(adji, mid),
            get_length_from_cache(mid, adjj));
    }
  }

  assert(
    aoo(cache, exponent, ind) ==
    *std::max_element(
      aoo(cache, 0).begin()+adji-1,
      aoo(cache, 0).begin()+adjj-1));

  return std::max({
    get_length_from_cache(i, adji),
    aoo(cache, exponent, ind),
    get_length_from_cache(adjj, j)
  });
}

struct test_case
{
  // long unsigned not seqval to avoid this:
  // https://codereview.stackexchange.com/questions/146669/enforcing-correct-input-output-of-integers
  long unsigned int i, j;

  // Sole purpose of this operator: Check input correctness
  friend std::istream &operator >> (std::istream &is, test_case &tc) try
  {
    std::string inpstr;
    std::getline(is, inpstr);
    if(!is.good()) {
      if(is.eof()) {
        // Either no characteres were read, in which case
        // failbit is set already, or the input didn't end with '\n',
        // which is invalid and we need to set failbit
        is.setstate(std::ios_base::failbit);
      }
      return is;
    }

    std::stringstream inp(inpstr+'\n');
    inp.exceptions(std::ios_base::badbit);

    inp >> tc.i >> tc.j;
    if(!inp.good()) {
      is.setstate(inp.rdstate());
      return is;
    }

    if(tc.i < 1 || tc.i > input_max || tc.j < 1 || tc.j > input_max) {
      is.setstate(std::ios_base::failbit);
      return is;
    }

    // No errors were detected, input is correct
    return is;
  } catch(...) {
    is.setstate(std::ios_base::badbit);
    return is;
  }
};

int main()
{
  #ifdef NDEBUG
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
  #endif
  std::cin.exceptions(std::ios_base::failbit | std::ios_base::badbit);
  std::cout.exceptions
    (std::ios_base::eofbit | std::ios_base::failbit | std::ios_base::badbit);

  while(std::cin.peek() != decltype(std::cin)::traits_type::eof())
  {
    test_case tc;
    std::cin >> tc;

    // Unary + to avoid this:
    // https://codereview.stackexchange.com/questions/146669/enforcing-correct-input-output-of-integers
    std::cout << tc.i << ' ' << tc.j << ' ' <<
        +get_length_from_cache(std::min(tc.i, tc.j),
            std::max(tc.i, tc.j)+1) << '\n';
  }

  // On any error an exception should've been thrown somewhere above, so here
  // we can announce SUCCESS
  return EXIT_SUCCESS;
}

Edit: The file I used for benchmarking: http://www.filedropper.com/100_3

Answer 1

1. A lot of variables have extremely weird names (like aoo. What does that even mean? "at or operator()", seriously?).

2. You define cache_t to be a vector of vectors and then create a bunch of huge unreadable functions to work with it (including initialization). The get_length_from_cache is really huge. I have no idea what's going on in there (and what's the point of creating a lot of lambda functions inside it? It seems to me that it only increases the confusion). Everything related to cache_t looks like a bunch of mess to me. I'd strongly recommend to create a properly documented class with a meaningful name that implements your cache with short, readable, properly named methods inside it. Another argument for making it a separate class is that it's not really a vector of vectors: it's some kind of data structure (I can't figure out what's going on exactly in your code) that uses a vector of vectors internally.

3. Adding the comments doesn't magically make your code more readable. Ideally, the code should be self-documenting. It's definitely not the case here. As I have said before, I have no idea what the cache does.

4. I don't see that point of having the test_case struct and doing all that complicated IO stuff. The problem statement guarantees that the input is correct. It could be just something like:

   cin >> i >> j;
   cout << get_length_from_cache(...) << '\n';
   

5. If you want to make the code readable, you should:

   • structure it properly (if something is a separate entity, like you cache, it should be implemented as a separate class)
   • Avoid making the code complex whenever possible. A simpler way to do the same thing is usually a better one.

Answer 2

The below notes might be slightly out of order or may have some typos. Sorry in advance, and I hope my notes help you out in the long run.

NDEBUG

I usually prefer to avoid negative logic when I can, meaning I would prefer to use DO_DEBUG instead of NDEBUG and rewrite the #ifdef as:

#ifndef ONLINE_JUDGE
    #define DO_DEBUG
#endif

Saying DO_DEBUG reads easier to me, however this is of my own preference. There's definitely some debate on which to use however. Some info here.

Many, Many Headers

A lot of the headers you included are unnecessary. I'll explain this later in the "Variable cache_t" section.

Function aoo

From the looks of it, your motivation for both aoo functions is to easily switch between using [] and at for debugging.

As noted by others already, aoo is a weird way to name this function. Identifiers should be able to self-document themselves. Calling this function get or get_element instead might prove more helpful to the reader. Just make sure to not include std::get if you choose get.

You only ever use at if you're uncertain about what value you'll be sending to your ADT (e.g. std::vector) as an index. As long as we prepare index boundaries right, I think it's safe to assume that using at is unnecessary (even if we're debugging the program).

I would default to just using the [] operator, unless you wholeheartedly believe you need the exceptions-handling.

Why use cont.operator[](index) when you can simply use cont[index]? Makes it easier to read (and quicker to type).

You can also move the Container:: stuff out of here into a using declaration (or not have them at all, which is what the final version at the bottom will have).

An example revision for all I said in this section so far (with some extra cleanup):

template<class Container>
using IndexType = typename Container::size_type;

template<class Container>
using RefType = typename Container::reference;

template<class Container>
RefType<Container> get(Container &c, IndexType<Container> i)
{
    return c[i]; // I changed this to c (since `cont` reminded me of continue) and i, but index works fine
}

Although apparent, returning just cont[i] means making a function is unnecessary.

If you really think you need at, change the return statement to something like the following:

#ifdef DO_DEBUG
    return c.at(i);
#else
    return c[i];
#endif

You should do the same for your other aoo function, e.g.

template<class Container>
using RefRefType = typename Container::value_type::reference; // unsure what to name this

// ... same code as above ...

template<class Container>
RefRefType<Container> get(Container &c, IndexType<Container> i, IndexType<Container> j)
{
    return c[i][j]; // or c.at(i).at(j) with `#ifdef DEBUG`
}

The using Statements

Having the names seqlen and seqval seem to obfuscate the code. In the final version of the revised code, I decided not to have these in the code.

I only ever really use using whenever I have ridiculously long types (e.g. vector<vector<vector<T>>>) or it definitely has a benefit in readability.

Variable cache_t

Lambdas are cool to use, but aren't always necessary. This especially holds for your initialization of cache, where it should be within a function (main if anything) and initialized there. Something like:

int main()
{
    cache_t cache;

    // initialization code here

    // etc.
}

This also fixes the issue of cache being global, which is considered code smell. Note that this also means you'll need to pass your cache variable by reference to each function that uses it (to keep it consistently-updating), but that isn't really an issue.

I'm not sure what the ADT or method of initializing/elements in your cache is officially called (segment tree, reduction tree, or something else, as noted in your response to @kraskevich), but it isn't necessary. Here's why:

DISCLAIMER: From this point on within this section I'm going to be talking about alternative ways to cache results. If you want to stick with your current caching system, it might be best to throw it in a class, e.g.

MyCache c(INPUT_MAX); // can pass debug flag here too
c.get(i); // all the work will be done behind the scenes, abstracted
//... etc. ...

Your code looks like it has a lot of overhead from compensating for how you map lengths in your vector. That could just be me interpreting your code incorrectly, but there are definitely ways to make things simpler.

Basing off your input_max constraint, declaring a vector (or uint array) of 1,000,000 elements isn't too crazy of a request to the operating system. This means you can remove a lot of the lambda expressions and pow work.

Your cache could look like one of the following:

const uint INPUT_MAX = 1000000;

// first option, fastest since it's just an array
uintcycle_length_cache[INPUT_MAX];
std::fill_n(cycle_length_cache, INPUT_MAX, 0); // initialize cache with 0's

// second option, still fairly fast as long as you don't use `at`
std::vector<uint> cycle_length_cache(INPUT_MAX, 0);

// third option, slowest but easiest to write out since off-by-one issues aren't a worry
unordered_map<uint> cycle_length_cache;

Later, if you want to store the length of a cycle within the cycle_length_cache, you can do:

// you might need to do cycle_length_cache[n-1] to cover off-by-one issues
cycle_length_cache[n] = CYCLE_LENGTH_OF_N;

Function calculate_collatz_length

As you mentioned in a comment to the post by @kraskevich, you're familiar with functional languages. Although recursion is amazing in these languages (due to tail-call optimization), in languages like C++ there is no such thing unfortunately. Thus, it's typically best to convert your recursive function to an iterative one.

Luckily for us this is an extremely easy thing to do (namely because the prompt on UVA Judge has nearly all the code written out for us):

uint get_cycle_length(uint n)
{
    uint cycle_length = 1;

    while(n != 1)
    {
        if(n % 2 == 0)
        {
            n = n/2;
        }
        else
        {
            n = 3*n + 1;
        }

        cycle_length++;
    }

    return cycle_length;
}

Finally, tweaking this to utilize our cache yields something such as:

// this assumes you're using a std::vector<uint> with default values of 0
void cache_cycle_length(uint n, std::vector<uint>& cycle_length_cache)
{
    uint input_n = n, cycle_length = 1;

    while(n != 1)
    {
        // found sub-term cycle length; update cache and leave early
        // NOTE: must do `n < cap` since `n` can exceed cycle_length_cache.size()
        if(n < cycle_length_cache.size() && cycle_length_cache[n-1] != 0)
        {
            // length of collatz seq for `n` = current length computed + sub-term cycle length
            cycle_length_cache[original_n-1] = cycle_length_cache[n-1] + cycle_length - 1;
            return;
        }
        // sub-term cycle not found, perform regular collatz sequence computation
        else if(n % 2 == 0)
        {
            n = n / 2;
        }
        else
        {
            n = 3*n + 1;
        }

        cycle_length++;
    }

    // sub-term not yet found, add to cache
    cycle_length_cache[original_n-1] = cycle_length;
}

If you want to circumvent all the n-1 stuff, initialize your cache with INPUT_MAX + 1.

In the above I'm certain you can remove n != 1 and say while(true). I'm leaving the above code as is as a means to be easier to read.

Function get_length_from_cache

Since I have an alternative clean up version for avoiding this function altogether (and this post is getting fairly long), I'm not going to touch-up too much on this. Three suggestions:

1. Either find an alternative to having lambdas (since lambdas should only be used for small methods or if you absolutely need a closure) or make the lambdas static so you don't keep recreating them each time you call this function. More info here.

2. pow is expensive. You can probably get away with using bitshift operators instead for your std::pow(2,x) call. More info here.

3. This small note is from PEP8 (more info here), but I've found it nicer to write multi-line arithmetic/conditionals with the operator on the left side.

Structure test_case

Overloading operators is pretty cool, but again it's unnecessary here. An easy way to grab input is in a while loop and have temporary variables for the lower bound and higher bound:

int main()
{
    std::vector<std::uint_fast32_t> cache(INPUT_MAX, 0);

    std::uint_fast32_t i, j, low, high, k;

    // while there are cases left
    while(std::cin >> i >> j)
    {
        // std::max and std::min from algorithm library
        low = std::min(i, j);
        high = std::max(i, j);

        for(k = low; k <= high; ++k)
        {
            // rest of code here
        }
    }
}

The above thus obsoletes test_case.

General Cleanups and Optimizations

Some other optimizations you can make:

1. Have consistency in your syntax! I know this might sound pedantic, but you need to make sure all your curly braces are either Egyptian-style (e.g. lines 80-85), new-line (e.g. lines 89-93), or same-line (e.g. lines 117-118). For explaining stuff or showing my code to others I find new line to work best, however Egyptian should be fine too. Same thing goes for space counts (2 or 4, although I find 4 to be easier to read).

NOTE: You can probably get away with same-line as long as you put the code on the same line (pun intended) as whatever is attached to it, e.g.

auto adjusted_j = [j](seqval interval){ return interval*(j/interval); };

More info here.

2. The canonical way to write indentifiers that mark constants is by writing them in capitals. In your code, change input_max to INPUT_MAX. This makes distinguishing it from variables much easier.

3. The modulus operation is expensive. You can check to see if a number is odd number by doing n & 1.

4. You mentioned in your main post you didn't understand why people suggest to not use using namespace std;. You probably already got the hint from talking to @kraskevich (i.e. distinguishing between std::get and get), however for more info check here.

An alternative to using namespace std; is to be picky with which namespace item you want to include:

using std::cout;
using std::cin;
using std::vector;
// etc.

For a program like this (where std::cout and std::vector are used only in a few places), it's quick enough to just type out the std:: part.

5. Choosing to have a million-element std::vector is definitely a trade-off between memory usage and speed. If you want to sacrifice run-time for less memory usage, you can probably clear your cache every time you compute a test case.

End Result

With the previously-mentioned recommendations and some more tweaks of my own (e.g. using DO_DEBUG for printing stuff), here's what I came up with:

// This program solves UVA Online Judge Problem 100: "The 3n + 1 Problem"
// Problem specification:
// https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36

// uncomment this section if you want to include it
//#ifndef ONLINE_JUDGE
//    #define DO_DEBUG
//#endif

// leaving these comments here for reference
#include <iostream>   // std::cout, std::cin
#include <vector>     // std::vector
#include <algorithm>  // std::max, std::min
#include <cstdint>    // std::uint_fast32_t
#include <limits>     // numeric_limits
#include <cassert>    // static_assert

// As of now, the problem specification incorrectly states that all integers
// in the input will be less than 10.000. The correct boundaries, stating that
// integers will be less than 1.000.000, can be found in the archived version:
// web.archive.org/web/20161225044321/https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36
constexpr std::uint_fast32_t INPUT_MAX = 1000000;

// this assumes you're using a std::vector<ulong> with default values of 0
void cache_cycle_length(std::uint_fast32_t n, std::vector<std::uint_fast32_t>& cycle_length_cache)
{
    std::uint_fast32_t input_n = n, cycle_length = 1;

    #ifdef DO_DEBUG
        std::cout << "input_n: " << input_n << "\n";
    #endif

    while(n != 1)
    {
        #ifdef DO_DEBUG
          std::cout << "n: " << n << "\n";
        #endif

        // found sub-term cycle length; update cache and leave early
        // NOTE: must do `n < INPUT_MAX` since `n` can exceed INPUT_MAX (which is an invalid index in the cache)
        if(n < INPUT_MAX && cycle_length_cache[n-1] != 0)
        {
            #ifdef DO_DEBUG
                std::cout << "hit cache with cache[n] = " << cycle_length_cache[n-1] << "\n\n";
            #endif

            // length of collatz seq for `n` = current length computed + sub-term cycle length
            cycle_length_cache[input_n-1] = cycle_length_cache[n-1] + cycle_length - 1;
            return;
        }
        // sub-term cycle not found, perform regular collatz sequence computation
        else if(n & 1)
        {
            n = 3*n+1;
        }
        else
        {
            n = n / 2;
        }

        cycle_length++;
    }

    #ifdef DO_DEBUG
        std::cout << "never hit cache" << "\n\n";
    #endif

    // sub-term not yet found, add to cache
    cycle_length_cache[input_n-1] = cycle_length;
}

int main()
{
    // see if cache can be made
    static_assert(std::numeric_limits<std::uint_fast32_t>::max() >= INPUT_MAX,
                  "This implementation cannot hold the cache.");

    std::vector<std::uint_fast32_t> cycle_length_cache(INPUT_MAX, 0);

    std::uint_fast32_t i, j, low, high, k, max_cycle_length;

    // while there are cases left
    while(std::cin >> i >> j)
    {
        // need to set max_cycle to 0 every iteration (or else we may get conflicting results)
        max_cycle_length = 0;

        // std::max and std::min from algorithm library
        low = std::min(i, j);
        high = std::max(i, j);

        for(k = low; k <= high; ++k)
        {
            // cache cycle length of k, then see if it's the newest max cycle length
            cache_cycle_length(k, cycle_length_cache);
            max_cycle_length = std::max(max_cycle_length, cycle_length_cache[k-1]);
        }

        // print like the prompt demanded us to
        std::cout << i << " " << j << " " << max_cycle_length << "\n";
    }

    return 0;
}