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

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.
• 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.

// 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;

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;
{return interval*(j/interval);};
{return i+interval;};

{
interval *= 2;
exponent++;
}
assert(interval <= j-i);
assert(std::pow(2,exponent) == interval);

assert(
adjj % interval == 0 &&
adji % interval == 0 &&
};

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

assert(
aoo(cache, exponent, ind) ==
*std::max_element(

return std::max({
aoo(cache, exponent, ind),
});
}

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 >> 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(...) {
return is;
}
};

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

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

• I recommend adding your other post as a reference link (or an image briefly describing how it works), i.e. stackoverflow.com/questions/42874883/… . That way others might be able to follow along your code easier. – Joe Greene Mar 23 '17 at 23:09

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.
• Thank you. As per 1: How should I call this function? Use_at_if_debugging_or_bracket_operator_if_not_debugging_because_its_faster is not a good name, I’m afraid. I could call this function get, but alas, there already is std::get, so this could be confusing even without using namespace std. Any better ideas? As per 2: I meant these lambdas to serve as local functions, to avoid polluting global namespace. I guess I’m somehow influenced by the let … in syntax known from functional languages and sometimes try weird stuff to bend C++ to sth similar. – gaazkam Mar 18 '17 at 12:08
• @gaazkam get would be definitely better than aoo. It's not that confusing because that's what namespaces are for. You can declare functions in an anonymous namespace (it would be available for this file only) if you don't want to pollute the global namespace. It's not common to use local function in C++. I don't think it's a good idea to write C++ as it were Haskell because to it leads to weird and hard to read constructs. – kraskevich Mar 18 '17 at 12:39
• As per 4, well… I guess this is just pedantism. FOr an online judge, sure, you can assume input is correct. For real life applications, definitely no. Well, if my only goal was to please the judge, I wouldn’t even try to optimise it, since this particular problem has really lax time constraints. My whole point is to solve this problem in a really nice way, because then I think I can learn. Writing pretty code, checking input correctness and optimising the code are all self-imposed challenges, not required by the judge. – gaazkam Mar 18 '17 at 13:18
• As per cache_t… I suppose I must’ve screwed really hard. Conceptually this is so simple, yet no one understand what I mean when I try to implement this concept: stackoverflow.com/q/42874883/4385532 – gaazkam Mar 18 '17 at 13:26
• @gaazkam, I think you meant "pedantry" :-p – Toby Speight Mar 23 '17 at 10:53

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.

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;
}
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); };


1. 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.

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

3. 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.

1. 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;
}
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;
}

• I disagree with you on NDEBUG, but much kudos for supplying the link so that readers can make their own informed decisions! +1. – Toby Speight Mar 23 '17 at 10:58
• Sorry for responding that late. First of all, many thanks for Your answer! However, I must say I have a problem with some of Your recommendations. • NDEBUG: I choose this name simply because I was using the assert macro, and whether I like it or not, this macro relies on NDEBUG, not on DO_DEBUG. • at vs []: I wasn’t sure MYSELF if I wasn’t violating constraints. Code generated by g++ can be fairly tolerant for constraint violations, so the fact that my program wasn’t crashing didn’t yet prove anything. The only way I saw to easily check if constraints weren’t violated was ’at’. – gaazkam Mar 30 '17 at 14:49
• • Why ’indexType and refType? To save ourselves from Container::size_type we resort to IndexType<Container>. Tbh I can’t see any improvement here. • IndexType<Container> j is wrong, as it binds to Container::size_type, while it should bind to Container::value_type::size_type. In practice, this is doesn’t matter. In theory, these might be distinct types. (correct me if I’m wrong here). If we insist to stick to only this what should work in practice we’d actually abandon Container::size_type at all, and instead we’d simply write size_t or even int. – gaazkam Mar 30 '17 at 14:55
• seqlen and seqval: Alternatively I should write uint_fast16_t whenever I’d mean length of the sequence, and uint_fast32_t whenever I’d mean value of the sequence. THis is close to having unnamed, literal constants at different places of code, which is considered code smell. • – gaazkam Mar 30 '17 at 14:59
• • cache being global: Yep, ikr, globals are considered harmful. While I understand they should probably be avoided in large programs, I can’t help but in programs as small as this one I think they can only simplify things. (similarly to using namespace std;`) Yep, certainly many programmers will call me a heretic here. – gaazkam Mar 30 '17 at 15:02