// Project Euler 14

#include "stdafx.h"
#include <iostream>
#include <time.h>
using namespace std;

#define UPPERLIMIT 1000000                           //the main number
#define DRAWDOTEVERY 100000                          //this number is 10 times smaller than UPPERLIMIT,
#define DICSIZE (UPPERLIMIT * 10)                    // so 10 dots are drawn
#define ul unsigned long

ul startingNumber, maxValue = 0, currentResult, result, i, x;
ul dic[DICSIZE] = {0};
clock_t t1;

ul getChainSlow(ul n) {                              //this might actually be faster than getChainFast:
    result = 0;                                      // compilers tend to optimize code
    while(true) {
        result++;
        if (n == 1) break;
        else if (n%2 == 0) n /= 2;
        else n = n*3 + 1;
    }
    return result;
}

ul getChainFast(ul n) {                              //bitwise operations are much faster than math
    result = 0;
    while(true) {
        result++;
        if (n == 1) break;
        else if (n&1) n = (n<<1) + n + 1;            //n ends with 1  ->  n*2 + n + 1 = 3*n + 1
        else n>>=1;                                  //n ends with 0  ->  n/2 (n = (n>>1))
    }
    return result;
}

ul getChainUltraFast(ul n) {
    result = 0;
    x = n;                                           //n needs to be preserved in this function
    while(true) {                                    //we could do without the while if x couldn't go up
        result++;
        if (x == 1) break;
        else if (x&1) x = (x<<1) + x + 1;
        else x>>=1;
        if ((x<DICSIZE) && dic[x]) {                 //if the current x is in the dictionary,
            result += dic[x];                        // use this chain number instead of iterating
            break;
        }
    }
    dic[n] = result;                                 //store the new value. as n only gets bigger,
    return result;                                   // this will never owerwrite anything
}

void calculate(ul (*func)(ul)) {                     //"ul (*func)(ul)" is the way to define a pointer to a function
    t1 = clock();                                    // that takes one ul (unsigned long) param and returns one ul number
    for(i=1; i<UPPERLIMIT; i++) {
        if (i%DRAWDOTEVERY == 0) cout << ".";        //this loop actually prints 9 dots for 100000->900000
        currentResult = func(i);                     // there is one dot printed before these 9 dots, so
        if (currentResult > maxValue) {              // there are 10 dots after all
            maxValue = currentResult;                // NOTE that outputting dots slows the execution significantly
            startingNumber = i;                      // such output shouldn't be used often
        }
    }
    cout << "\nStarting number that produces maximum chain = " << startingNumber;
    cout << "\nRuntime = " << ((ul)clock()-(ul)t1) << " clock ticks\n";

}

int _tmain(int argc, _TCHAR* argv[]) {
    cout << "This program searches for the number chain of maximum length,\n";
    cout << "where the starting number is less than " << UPPERLIMIT << "\n";

    cout << "\nCalculating using the slow function.";
    calculate(&getChainSlow);                        //we pass pointers to functions as arguments
                                                     // calculate will use these functions
    cout << "\nCalculating using the function that does bitwise operations.";
    calculate(&getChainFast);                        // in it's loop

    cout << "\nCalculating using the function that uses an array.";
    calculate(&getChainUltraFast);

    cin >> maxValue;                                 //wait for input. the only dirty hack
    return 0;
}