It is bad practice bad practice, so please refrain from using it.
With a cache, I would say that using a cache will make the algorithm even faster. Also, you might want to read this question this question, as it explains what you can do to optimize the algorithm even further. For example, only caching odd numbers.
It is bad practice, so please refrain from using it.
With a cache, I would say that using a cache will make the algorithm even faster. Also, you might want to read this question, as it explains what you can do to optimize the algorithm even further. For example, only caching odd numbers.
It is bad practice, so please refrain from using it.
With a cache, I would say that using a cache will make the algorithm even faster. Also, you might want to read this question, as it explains what you can do to optimize the algorithm even further. For example, only caching odd numbers.
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 have to agree with the other "people" on this one: Even though you said that you tried to make it more readable, it is still a huge mess of unreadable code. It seems that you think that the less line your code has, the better. That's not the case though. It's true that less lines of code is better, but that doesn't mean you need to cram multiple statements on one line just to reduces the total count of lines:
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;
That part is especially unreadable, don't you think? Well, let's see if we can make your code readable :)
Don't use using namespace std;
It is bad practice, so please refrain from using it.
You don't need to return anything on success from main
You don't need to return EXIT_SUCCESS;, as the compiler will implicitly use it if you don't specify it. But that's pretty opinion based.
Use better naming
You have some i and j outside of loops. Those are very bad variable names, they don't tell what i and j do. I also find that getLength isn't an ideal name considering that getting the length of an integer doesn't make any sense.
Use proper indentation and don't stick lines together
As said before, you seem to like putting multiple statements in one line:
string inpstr; getline(is, inpstr); if(!is.good()) return is;
Those lines are really unreadable and hard to debug. Same thing goes for lines without indentation and/or whitespace:
if(!(inp>>ws).eof()) {is.setstate(ios_base::failbit); return is;}
Please use your Enter and Space keys :)
std::pow has poor performance
std::pow is (very) slow to calculate powers, that's because it can also calculate powers of floating point numbers, and thus can't use the traditional approach. It would be better (and faster!) if you made your own exponentiation function:
constexpr auto pow(unsigned long long base, unsigned long long exp) noexcept {
auto result = 1ull;
for (auto i = 0ull; i < exp; ++i)
result *= base;
return result;
}
Why use macros?
I don't see any reason to use macros, especially since you cannot debug your code easily. Also, for debugging purposes, it is not really important that stdio is synced, as you're not even using stdio. Same for tying std::cin and std::cout.
testCase is weird and complicated
Your testCase struct is very complicated and long and weird. I don't know why you don't use:
seqval num1 = 0;
seqval num2 = 0;
while(std::cin >> num1 >> num2)
std::cout << num1 << ' ' << num2 << ' ' << getRangeMax(std::min(num1, num2), std::max(num1, num2)+1) << '\n';
This will always get input from stdin until EOF is reached. Because online judges will pass input from a file (I can't imagine them doing something else - maybe they are, but that's the easy solution), it will behave as expected.
If you want to stop the input and see the output, just input anything that is not a number (except for a space or a newline of course).
If you tie std::cout and std::cin again, you'll see the output immediately, instead of at the end.
Your algorithm is unclear to me
The algorithm that you are using is very unclear from just looking at the code IMO, so I can't give you any tips on this one, just give you how I would solve the problem. This is the best examples where comments would really help out to understand the algorithm you are using.
The combination of striving to minimize code lines, bad naming, no comments is the reason why it is hard for me to understand it.
Here's how I would do it:
seqlen calculate_collatz(seqval number) noexcept {
seqlen length = 1;
while (number != 1) {
if (number % 2 == 0)
number /= 2;
else
number = 3 * number + 1;
++length;
}
return length;
}
seqlen max_collatz(seqval lower, seqval upper) noexcept {
seqlen largest_sequence = 0;
for (auto i = lower; i < upper + 1; ++i) {
auto curr_sequence = calculate_collatz(i);
if (curr_sequence > largest_sequence)
largest_sequence = curr_sequence;
}
return largest_sequence;
}
You might notice that I haven't used any cache. That's because even without a cache, my way is 0.6s faster than yours (0.2s vs. 0.8s)! Both were compiled using -O3 with gcc 6.3.1 on a i7-6700HQ.
With a cache, I would say that using a cache will make the algorithm even faster. Also, you might want to read this question, as it explains what you can do to optimize the algorithm even further. For example, only caching odd numbers.