/* The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.
 *
 * 73167176531330624919225119674426574742355349194934
 * 96983520312774506326239578318016984801869478851843
 * 85861560789112949495459501737958331952853208805511
 * 12540698747158523863050715693290963295227443043557
 * 66896648950445244523161731856403098711121722383113
 * 62229893423380308135336276614282806444486645238749
 * 30358907296290491560440772390713810515859307960866
 * 70172427121883998797908792274921901699720888093776
 * 65727333001053367881220235421809751254540594752243
 * 52584907711670556013604839586446706324415722155397
 * 53697817977846174064955149290862569321978468622482
 * 83972241375657056057490261407972968652414535100474
 * 82166370484403199890008895243450658541227588666881
 * 16427171479924442928230863465674813919123162824586
 * 17866458359124566529476545682848912883142607690042
 * 24219022671055626321111109370544217506941658960408
 * 07198403850962455444362981230987879927244284909188
 * 84580156166097919133875499200524063689912560717606
 * 05886116467109405077541002256983155200055935729725
 * 71636269561882670428252483600823257530420752963450
 *
 * Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?*/

#define _POSIX_C_SOURCE 199309L

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(int argc, char **argv)
{
    char string[] = "73167176531330624919225119674426574742355349"
                    "19493496983520312774506326239578318016984801"
                    "86947885184385861560789112949495459501737958"
                    "33195285320880551112540698747158523863050715"
                    "69329096329522744304355766896648950445244523"
                    "16173185640309871112172238311362229893423380"
                    "30813533627661428280644448664523874930358907"
                    "29629049156044077239071381051585930796086670"
                    "17242712188399879790879227492190169972088809"
                    "37766572733300105336788122023542180975125454"
                    "05947522435258490771167055601360483958644670"
                    "63244157221553975369781797784617406495514929"
                    "08625693219784686224828397224137565705605749"
                    "02614079729686524145351004748216637048440319"
                    "98900088952434506585412275886668811642717147"
                    "99244429282308634656748139191231628245861786"
                    "64583591245665294765456828489128831426076900"
                    "42242190226710556263211111093705442175069416"
                    "58960408071984038509624554443629812309878799"
                    "27244284909188845801561660979191338754992005"
                    "24063689912560717606058861164671094050775410"
                    "02256983155200055935729725716362695618826704"
                    "28252483600823257530420752963450";
    char cur, out;
    long int max = 0, tmp = 1;
    int i, j;
    double elapsed;
    struct timespec start, end;

    clock_gettime(CLOCK_MONOTONIC, &start);

    for(i = 0; i < 1000; i++)
    {
        /* For the first 13 digits, just multiply them.*/
        if(i < 13)
        {
            cur = string[i] - '0';
            tmp *= (long int)cur;
        }
        else
        {
            /* If the current product is greater than the maximum, save the current as maximum.*/
            if(tmp > max)
            {
                max = tmp;
            }
            /* Check the value of the first digit of the previous sequence, which will not be part
             * of the next sequence.*/
            out = string[i-13] - '0';
            /* If the digit is zero, multiply all the 13 digits of the new sequence.*/
            if(out == 0)
            {
                tmp = 1;
                for(j = i - 12; j <= i; j++)
                {
                    cur = string[j] - '0';
                    tmp *= (long int)cur;
                }
            }
            /* If the digit not zero, instead of multiplying all the 13 digits of the new sequence,
             * divide the current product by the remove digit and multiply it by the new digit.*/
            else
            {
                cur = string[i] - '0';
                tmp /= (long int)out;
                tmp *= (long int)cur;
            }
        }
    }

    clock_gettime(CLOCK_MONOTONIC, &end);

    elapsed = (end.tv_sec - start.tv_sec) + (double)(end.tv_nsec - start.tv_nsec) / 1000000000;

    printf("Project Euler, Problem 8\n");
    printf("Answer: %ld\n", max);

    printf("Elapsed time: %.9lf seconds\n", elapsed);

    return 0;
}