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 <vector>
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <string>
#include <sstream>
#include <cmath>
#include <cassert>
#include <cstdint>
#include <cstdlib>
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 <= (UINT32_MAX-1)/3);
static unordered_map<seqval,seqlen> 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 <= j);
assert(i >= inputMin && j <= inputMax+1);
using cache_t = vector<unordered_map<seqval,seqlen>>;
static cache_t cache;
if(i == j) return 0;
auto exponent = static_cast<cache_t::size_type>(floor(log2(j-i)));
auto interval = static_cast<seqval>(pow(2,exponent));
seqval lb, ub;
while((lb = (ub = interval * (j/interval)) - interval) < i)
interval = static_cast<seqval>(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<ios_base::iostate>(0))
); return is;}
if(tc.i < inputMin || tc.j < inputMin || 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::sync_with_stdio(false);
cin.tie(nullptr);
#endif
cin.exceptions(ios_base::failbit | ios_base::badbit);
cout.exceptions(ios_base::eofbit | ios_base::failbit | ios_base::badbit);
testCase tc; while(!(cin >> tc).eof())
cout << tc.i << ' ' << tc.j << ' ' <<
getRangeMax(min(tc.i,tc.j), max(tc.i,tc.j)+1) << '\n';
if(tc.noInput()) cout << '\n';
return EXIT_SUCCESS;
}
Notes:
- 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.
- My goals I tried to meet as a self-imposed challenge:
- I tried to achieve sound time complexity even despite the judge’s lax requirements do not force me to do so.
- I also tried to write error safe code, in particular I wanted to make the program fail on input that is invalid as per the problem specification.
- Problem #1: This means I needed to distinguish the cases of lack of further input and the presence of an invalid input line. To meet this I broke conventions set up by the Standard Library by making
operator>>(istream&,testCase&)
only seteofbit
on lack of input but notfailbit
. I guess this is bad, but as of now I have no better idea. - Problem #2: I still cannot prevent UB in case of a stack overflow and I don’t think it is even possible in general. Maybe I should’ve refrained from using recursion?
- Problem #1: This means I needed to distinguish the cases of lack of further input and the presence of an invalid input line. To meet this I broke conventions set up by the Standard Library by making
- I tried to refrain from making use of any unnecessary implementation-specific guarantees, and instead make the program have to produce correct results as per the C++ Standard. As of now I can’t see where could I fail in here, but I’ve already learned that there are unobvious issues on this matter.
- As of now, the problem specification gives incorrect input boundaries, claiming that all numbers will be less than 10,000. The correct bound seems to be 1,000,000 instead, which is present in the archived version of the problem specification.
while((lb = (ub = interval * (j/interval)) - interval) < i)
actually saves me from having to define a whole function. Err, the code is already 100 lines long… \$\endgroup\$ – gaazkam Mar 2 '17 at 19:38