I’ve written a solution for “The 3n+1 problem”, the first task in the Universidad de Valladolid programming contest.
My weapon of choice was C. I’ve got a ranking beneath the first 550 contestants with a cpu time of 0.084 and ‘minimal’ memory usage.
I tried different technologies:
- full blown hash tables
- simple caching per direct adressing
- iterative implementation
- recursive implementation
- precalculated values
My fastest solution uses a recursive implementation and a direct addressing cache. Precalculated values suprisingly caused a performance drop.
The guys on the first ranks have cpu times of 0.000 and ‘minimal’ memory usage. I’m very interested in how this is done. If you have a faster solution, please comment or write me! Or feel free to improve my code.
Also, there may be some mathematical tricks, I don’t know.
Here’s the code:
#include <stdio.h>
#define SIZE 1000001
static unsigned short table[SIZE];
unsigned short calcCycleLength( register unsigned long n )
{
if(n < SIZE && table[n])
return table[n];
if(n & 1){ /* if n is odd */
if( n < SIZE) {
table[n] = 2 + calcCycleLength( (3*n+1) >> 1 ); /* calc two steps at one */
return table[n];
}
else
return 2 + calcCycleLength( (3*n+1) >> 1 );
}
else {
if( n < SIZE) {
table[n] = 1 + calcCycleLength( n >> 1 ); /* n/2 */
return table[n];
}
else
return 1 + calcCycleLength( n >> 1 );
}
}
int main()
{
unsigned long i, fstIn, sndIn;
short out = 0, temp;
table[1] = 1;
while ( scanf("%lu %lu", &fstIn, &sndIn ) != EOF )
{
if( fstIn > sndIn) {
for( i = sndIn; i <= fstIn; ++i )
{
temp = calcCycleLength( i );
if( temp > out)
out = temp;
}
}
else {
for( i = fstIn; i <= sndIn; ++i )
{
temp = calcCycleLength( i );
if( temp > out)
out = temp;
}
}
printf("%lu %lu %hdn", fstIn, sndIn, out);
out = 0;
}
return 0;
}
When thinking about this problem, I thought how I would solve it in haskell. I came up with the following one-liner:
(maximum . map ((+1) . length . takeWhile (/=1) . iterate (\n -> if n `mod` 2 == 0 then n `div` 2 else 3*n+1) ) . uncurry enumFromTo)
This takes a pair (the range) and gives the right answer. Looks like haskell is to such problems what perl is to system administration.
(I’m not claiming that is’s fast, though. Just fast to write.)
Just a thought: Might it be faster to make your recursive function tail-recursive, or just wrap it in a while loop?
Hmm. Probably not possible, as you also write the results to the table. Nevermind
I’ve tried a complete iterative solution (the while loop), and also a tail-recursive one by implementing the n/2 in a while loop and recursing only the ‘odd’ part. Both solutions were significantly slower than this one.
The full hashtable performed somewhat slower. I used a bad hash function (x mod n), which wasn’t uniformley distributed. Furthermore, the malloc calls costs some performance.
So, getting rid of the malloc (perhaps with alloca or a complete preallocation) and inventing a better hash function could boost the performance.
something similar in c++…
#include
using namespace std;
const unsigned long int MAX=1000000;
unsigned long int lengths[MAX];
unsigned long int clength(unsigned long int inp);
int main()
{
unsigned long int a,b;
while (cin>>a>>b)
{
unsigned long int cycleLength=0, maxLength=0;
for(unsigned long int i=a;imaxLength)
maxLength=cycleLength;
}
cout>1);
else
lengths[inp] = 2 + clength((3*inp + 1)>>1);
return lengths[inp];
}
I was looking around to see who has solved this, I get the right answers on my PC based on 110101.inp but when I submit it online, the judge system keeps telling me wrong answer. Any ideas why? It’s in C++.
#include
#include
using namespace std;
int main(int argc, char **argv) {
int first = 0, last = 0, maxCycleLength = 0;
while(cin >> first >> last) {
if ( first > last ) {
int temp = first;
first = last;
last = temp;
}
maxCycleLength = 0;
for (int x = first; x maxCycleLength)
maxCycleLength = cycleLength;
}
cout << first << ” ” << last << ” ” << maxCycleLength << “\n”;
}
exit(0);
}
BTW, I submitted this to programming-challenges.com website.
Niraj
I figured it out, when I swapped the inputs if first was larger than the other, I printed them in swapped output.
Niraj
Hi Niraj!
Thank you for your comments. How fast is your solution?
Tante, the time was 6.328 secs, pretty slow. I needed to get it working first. Reading this thread, I realized type of changes I need to make to make it more optimal solution, such as caching data, hopefully without running out of memory.
Niraj
By using C++ map objects to cache, the time came down slightly to 4.688 secs.
Hm, the version I posted runs in 0.084 secs …
fantastic!!!!!
try this too: cycle of power nth of n is n+1
or if you init 10 or 20 elements of your table, maybe make it faster
i submitted this program, and it has wrong answer:
i adapted u in using bitwise operators :p
#include
int main(void)
{
unsigned long i,j;
while(scanf(“%lu %lu”,&i,&j)!= EOF)
{
short max=0;
register int loop;
if(i>j)
{
unsigned long temp=i;
i=j;
i = temp;
}
for( loop = i;loop>1);
}
max = (max>il)?max:il;
}
printf(“%lu %lu %hd\n”,i,j,max);
}
return 0;
}
#include
int main(void)
{
unsigned long i,j;
while(scanf(“%lu %lu”,&i,&j)!= EOF)
{
short max=0;
register int loop;
if(i>j)
{
unsigned long temp=i;
i=j;
i = temp;
}
for( loop = i;loop>1);
}
max = (max>il)?max:il;
}
printf(“%lu %lu %hd\n”,i,j,max);
}
return 0;
}
for( loop = i;loop>1);
}
I tackled the problem in the same way you did, though I used C++, I first tried pre-calculated values and then I settled on filling in the max cycles for other values as I came across them while I was calculating the current max cycle value… I believe this is right on par with you… Anyway the code is tightened up a bit more and I created less array elements on the magnitude of 10 than your example and with it I recieved an Accepted Verdict with a runtime of 0.030. Here’s the code…
#include
#define SIZE 100001
static unsigned short table[SIZE];
unsigned short FindMaxCycle(register unsigned int n)
{
if(n > 1);
else table[n] = 1 + FindMaxCycle(n >> 1);
return table[n];
}
if(n & 1) return 2 + FindMaxCycle((3 * n + 1) >> 1);
return 1 + FindMaxCycle(n >> 1);
}
int main()
{
unsigned int i, j;
unsigned short hCnt, cnt;
table[1] = 1;
while(std::cin >> i >> j)
{
hCnt = 1;
std::cout << i << ” ” << j < j)
{
for( ; j hCnt) hCnt = cnt;
}
}
else
{
for( ; i hCnt) hCnt = cnt;
}
}
std::cout << hCnt << std::endl;
}
}
Anyway I still think that there is something I am missing, I don’t know if I am spending too much time calculating unecessary values that won’t be used on future calculations. Also I agree with you that there may be a potential mathimatical algorithm that can estimate the values without a recursive calculation, but these are just thougts, I would love to see some more examples with the running time posted.
Thanx,
Jay
Thanks Jay! Interesting stuff!
I’m not working on this problem any more (at the moment…). But I have some half-baked stuff not posted yet:
There’s a nice site with “bit hacks” (http://graphics.stanford.edu/~seander/bithacks.html). Maybe, one can use one of these to short circuit the bit shifts. Especially the deBruijn method to find the log base 2 of an N-bit integer looks promising.
If you plot the input integer against the corresponding cycle length, you will notice some sort of a noisy pattern. In general, such a pattern stands for hidden information. So I trained a neural network to estimate the probability distribution for a given integer to result in a specific cycle length. Don’t no how to use this yet. Maybe consider a “probabilistic” solution throwing away the less probable cycle lengthes etc.
I’ve also tried “cheating”. Waiting some seconds and then dividing by zero can be used to extract information out of the judge. The judge seems to use many, many input pairs with small intervalls. No investigated any further.
Furthermore to calculate EVERY thinkable input, you have to use 64bit arithmetic. Since the judge also accepets the faulty 32bit solution, it doesn’t use these dangerous inputs. This gives us information about the maximum interval between the two input integers (it nevers spans across one of the bad values).
Here is my solution in Common Lisp. No memoization, no type declarations, no compiler optimization hacks; just a tail recursive function implementation.
(defun cycle-length (n &optional (l 1))
(if (< 1 n)
(cycle-length (if (oddp n) (1+ (* 3 n)) (/ n 2)) (1+ l))
l))
(defun maximum-cycle-length (i j &optional (l 0))
(if (< i j)
(maximum-cycle-length i (1- j) (max l (cycle-length j)))
l))
(time
(loop for (i j) in ‘((1 10) (100 200) (201 210) (900 1000))
collect (maximum-cycle-length i j)))
Evaluation took:
0.002 seconds of real time
0.000000 seconds of total run time (0.000000 user, 0.000000 system)
0.00% CPU
1,689,109 processor cycles
0 bytes consed
(20 125 89 174)
I submitted your solution to the online judge and got the verdict wrong answer.
The Common Lisp guy doesn’t realize that the judge will run the program on a larger set of numbers, thus vastly increasing the run time. Try 1…999999 instead.
when ever I submitted this problem…
I got wrong ans…
cn any one help me to get rid of the porb…
plssssssssssssssss…
#include
unsigned short length(unsigned long n);
int main()
{
unsigned long i,a,b,x,y;
int max = 0;
int temp = 0;
while(scanf(“%lu %lu”,&a,&b)==2)
{
x = a;
y = b;
if(a > b)
{
a = y;
b = x;
}
for(i = a;imax)
{
max = temp;
}
}
printf(“%lu %lu %d\n”,a,b,max);
max = 0;
}
return 0;
}
int length(unsigned long n)
{
int len = 1;
while(n!=1)
{
if(n%2==1)
{
n = 3*n + 1;
}
else
{
n = n/2;
}
len++;
}
return len;
}
#include
unsigned short length(unsigned long n);
int main()
{
unsigned long i,a,b,x,y;
int max = 0;
int temp = 0;
while(scanf(“%lu %lu”,&a,&b)==2)
{
x = a;
y = b;
if(a > b)
{
a = y;
b = x;
}
for(i = a;imax)
{
max = temp;
}
}
printf(“%lu %lu %d\n”,a,b,max);
max = 0;
}
return 0;
}
int length(unsigned long n)
{
int len = 1;
while(n!=1)
{
if(n%2==1)
{
n = 3*n + 1;
}
else
{
n = n/2;
}
len++;
}
return len;
}
It is a good solution:
#include
#include
using namespace std;
long cycleLen(unsigned long n)
{
int len=1;
while(n!=1)
{
if(n%2==1)
{
n=3*n+1;
}
else
{
n=n/2;
}
len=len+1;
}
return len;
}
void swap(unsigned long& i, unsigned long& j)
{
unsigned long tmp=0;
tmp=i;
i=j;
j=tmp;
}
int main()
{
unsigned long i=0,oldi=0;
unsigned long j=0,oldj=0;
unsigned long max=0;
unsigned long tmp=0;
while(cin>>i && cin>>j)
{
oldi=i;
oldj=j;
if(i>j)
{
swap(i,j);
}
for(unsigned long p=i;p<=j;p++)
{
tmp=cycleLen(p);
if(max<tmp)
{
max=tmp;
}
}
cout<<oldi<<" "<<oldj<<" "<<max<<"\n";
max=0;
}
return 0;
}
if input is
10 1
output should be
1 10 20
hello
i submit this program but i get (Time limit exceeded) error.
my program run in 3.000 sec.
Pleas help me to correct that.
my code:
#include “iostream”
using namespace std;
int main(){
unsigned int inI,
inJ;
int counter,MaxCounter;
do{
MaxCounter=0;
cin>>inI>>inJ;
cout<<inI<<" "<<inJ<1){
curpos=(curpos%2)?(3*curpos)+1:curpos/2;
counter++;
}
if (counter>MaxCounter) MaxCounter=counter;
inI++;
}while(inI<=inJ);
cout<<MaxCounter<<"\n";
}while(inI);
return 0;
}
how can I use this code but in Java???
#include
int main (int argc, char *argv[])
{
int i, j, ii, n, size, max;
while (scanf (“%d %d”, &i, &j) == 2)
{
ii = i;
max = 0;
for (i; i 1)
{
size++;
if (n%2 == 0)
n = n/2;
else
n = 3*n + 1;
}
if (size > max)
max = size;
}
printf (“%d %d %d\n”, ii, j, max);
}
}
This is the fastest one I can get:
Run Time: 0.020
#include
#define MAX(x, y) (x) > (y) ? (x) : (y)
#define SWAP(a, b) {a ^= b; b ^= a; a ^= b;}
#define SIZE 1000000
static unsigned table[SIZE];
unsigned _get_cycle_len(unsigned n, unsigned *cycle_len_counter)
{
if (n 1)
{
if (n & 1)
{
n = 3 * n + 1;
}
else
{
n >>= 1;
}
if (n j)
{
SWAP(i, j);
}
while (i max)
{
max = table[i];
}
}
else
{
*cycle_len_counter = 0; // Must initialize to zero.
table[i] = _get_cycle_len(i, cycle_len_counter); // Get the cycle length of the number.
if (table[i] > max)
{
max = table[i];
}
}
//printf(“table[%u]: %u\n”, i, table[i]);
i++;
}
return max;
}
int main(void)
{
unsigned i = 0, j = 0;
// ### Use this block to Find the max cycle length in a range of number.
while(scanf(“%u %u”, &i, &j) != EOF)
{
printf(“%u %u %u\n”, i, j, _get_max_cycle_len(i, j));
}
// ### Use this block to see one number only.
//while(scanf(“%u”, &i) != EOF)
//{
//*cycle_len_counter = 0;
//table[i] = _get_cycle_len(i, cycle_len_counter);
//printf(“table[%u] = %u\n”, i, table[i]);
//printf(“\n”);
//}
return 0;
}