VeryMuch

/* Sums number of unique paths from A to B:
 *
 * A and B are diagonally opposed cornes of a square grid,
 * each node connects south (S), south-east (SE), and east (E),
 * if A is considered the north-west corner, and B the south-east.
 *
 * I consider each node a square, with the sum of unique paths to it.
 *
 * And calculations go from level 0 to level 'side'. When side is the
 * length of each side of the grid.
 *
 * I start with level 0 and propogate to and through level 'side'.
 * On each level paths are summed to the next level or to the sides of current level.
 * Starting with the outermost squares of each level, ending in the middle square.
 * This order of summation must be kept, else too low a sum is added to next level.
 *
 * The middle square of each level is saved, as that will eventually contain the final sum.
 *
 * Diagram:
 *       A
 * level   0 ... n ... side
 *         . .   . .     .
 *         .   . .   .   .
 *         .    ..     . .
 *         n ... n ... side
 *         . .   . .     .
 *         .   . .   .   .
 *         .    ..    .  .
 * level side ...n ... side  <-- final sum of unique paths
 *                          B
 *
 *  Author: Arnþór Logi Arnarson
 *     aka: arnthorla
 */

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

int main( int argc, char** argv )
{
    int side = 100;
    int maxlen = side*2+4;
    int i, j, currentlen;

    mpz_t **currentlevel, **nextlevel, **templevel, result;
    currentlevel = (mpz_t **)malloc(sizeof(mpz_t));
    nextlevel = (mpz_t **)malloc(sizeof(mpz_t));
    *currentlevel = (mpz_t *)malloc(maxlen*sizeof(mpz_t));
    *nextlevel = (mpz_t *)malloc(maxlen*sizeof(mpz_t));

    // initialize mpz_t nums to zero
    for( i = 0; i < maxlen ; i++ )
    {
        mpz_init( *(*currentlevel+i) );
        mpz_init( *(*nextlevel+i) );
    }
    // initialization done!

    mpz_set_ui( *(*currentlevel+0), 1 ); // set first node to 1
    currentlen = 1;
    while( currentlen/2 <= side ) // currentlen/2 == currentlevel
    {
        i = 0;
        j = currentlen-1;
        while( i != j )
        {   // i
            mpz_add( *(*nextlevel+i), *(*nextlevel+i), *(*currentlevel+i) ); // S
            mpz_add( *(*nextlevel+(i+1)), *(*nextlevel+(i+1)), *(*currentlevel+i) ); // SE
            mpz_add( *(*currentlevel+(i+1)), *(*currentlevel+(i+1)), *(*currentlevel+i) ); // E

            // j
            mpz_add( *(*currentlevel+(j-1)), *(*currentlevel+(j-1)), *(*currentlevel+j) ); // S
            mpz_add( *(*nextlevel+(j+1)), *(*nextlevel+(j+1)), *(*currentlevel+j) ); // SE
            mpz_add( *(*nextlevel+(j+2)), *(*nextlevel+(j+2)), *(*currentlevel+j) ); // E
            i++;
            j--;
        }
        // middle
        mpz_add( *(*nextlevel+i), *(*nextlevel+i), *(*currentlevel+i) ); // S
        mpz_add( *(*nextlevel+(i+1)), *(*nextlevel+(i+1)), *(*currentlevel+i) ); // SE
        mpz_add( *(*nextlevel+(i+2)), *(*nextlevel+(i+2)), *(*currentlevel+i) ); // E
        mpz_set( result, *(*currentlevel+i) ); // save middle as possible result

        // swap levels, do not lose pointers to heap
        templevel = currentlevel;
        currentlevel = nextlevel;
        nextlevel = templevel;

        // reset next level to zero
        for( i = 0 ; i < maxlen ; i++ )
        {
            mpz_set_ui( *(*nextlevel+i), 0 );
        }

        // increment currentlen
        currentlen += 2;
    }

    gmp_printf( "%Zd\n", result );

    // just for correctness not needed
    free(*currentlevel);
    free(currentlevel);
    free(*nextlevel);
    free(nextlevel);

    return 0;
}