Guest User

VeryMuch

a guest
Feb 14th, 2011
200
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* Sums number of unique paths from A to B:
  2.  *
  3.  * A and B are diagonally opposed cornes of a square grid,
  4.  * each node connects south (S), south-east (SE), and east (E),
  5.  * if A is considered the north-west corner, and B the south-east.
  6.  *
  7.  * I consider each node a square, with the sum of unique paths to it.
  8.  *
  9.  * And calculations go from level 0 to level 'side'. When side is the
  10.  * length of each side of the grid.
  11.  *
  12.  * I start with level 0 and propogate to and through level 'side'.
  13.  * On each level paths are summed to the next level or to the sides of current level.
  14.  * Starting with the outermost squares of each level, ending in the middle square.
  15.  * This order of summation must be kept, else too low a sum is added to next level.
  16.  *
  17.  * The middle square of each level is saved, as that will eventually contain the final sum.
  18.  *
  19.  * Diagram:
  20.  *       A
  21.  * level   0 ... n ... side
  22.  *         . .   . .     .
  23.  *         .   . .   .   .
  24.  *         .    ..     . .
  25.  *         n ... n ... side
  26.  *         . .   . .     .
  27.  *         .   . .   .   .
  28.  *         .    ..    .  .
  29.  * level side ...n ... side  <-- final sum of unique paths
  30.  *                          B
  31.  *
  32.  *  Author: Arnþór Logi Arnarson
  33.  *     aka: arnthorla
  34.  */    
  35.  
  36. #include <stdio.h>
  37. #include<stdlib.h>
  38. #include<gmp.h>
  39.  
  40. int main( int argc, char** argv )
  41. {
  42.     int side = 100;
  43.     int maxlen = side*2+4;
  44.     int i, j, currentlen;
  45.  
  46.     mpz_t **currentlevel, **nextlevel, **templevel, result;
  47.     currentlevel = (mpz_t **)malloc(sizeof(mpz_t));
  48.     nextlevel = (mpz_t **)malloc(sizeof(mpz_t));
  49.     *currentlevel = (mpz_t *)malloc(maxlen*sizeof(mpz_t));
  50.     *nextlevel = (mpz_t *)malloc(maxlen*sizeof(mpz_t));
  51.  
  52.     // initialize mpz_t nums to zero
  53.     for( i = 0; i < maxlen ; i++ )
  54.     {
  55.         mpz_init( *(*currentlevel+i) );
  56.         mpz_init( *(*nextlevel+i) );
  57.     }
  58.     // initialization done!
  59.                    
  60.     mpz_set_ui( *(*currentlevel+0), 1 ); // set first node to 1
  61.     currentlen = 1;
  62.     while( currentlen/2 <= side ) // currentlen/2 == currentlevel
  63.     {
  64.         i = 0;
  65.         j = currentlen-1;
  66.         while( i != j )
  67.         {   // i
  68.             mpz_add( *(*nextlevel+i), *(*nextlevel+i), *(*currentlevel+i) ); // S
  69.             mpz_add( *(*nextlevel+(i+1)), *(*nextlevel+(i+1)), *(*currentlevel+i) ); // SE
  70.             mpz_add( *(*currentlevel+(i+1)), *(*currentlevel+(i+1)), *(*currentlevel+i) ); // E
  71.  
  72.             // j
  73.             mpz_add( *(*currentlevel+(j-1)), *(*currentlevel+(j-1)), *(*currentlevel+j) ); // S
  74.             mpz_add( *(*nextlevel+(j+1)), *(*nextlevel+(j+1)), *(*currentlevel+j) ); // SE
  75.             mpz_add( *(*nextlevel+(j+2)), *(*nextlevel+(j+2)), *(*currentlevel+j) ); // E
  76.             i++;
  77.             j--;
  78.         }
  79.         // middle
  80.         mpz_add( *(*nextlevel+i), *(*nextlevel+i), *(*currentlevel+i) ); // S
  81.         mpz_add( *(*nextlevel+(i+1)), *(*nextlevel+(i+1)), *(*currentlevel+i) ); // SE
  82.         mpz_add( *(*nextlevel+(i+2)), *(*nextlevel+(i+2)), *(*currentlevel+i) ); // E
  83.         mpz_set( result, *(*currentlevel+i) ); // save middle as possible result
  84.  
  85.         // swap levels, do not lose pointers to heap
  86.         templevel = currentlevel;
  87.         currentlevel = nextlevel;
  88.         nextlevel = templevel;
  89.  
  90.         // reset next level to zero
  91.         for( i = 0 ; i < maxlen ; i++ )
  92.         {
  93.             mpz_set_ui( *(*nextlevel+i), 0 );
  94.         }
  95.  
  96.         // increment currentlen
  97.         currentlen += 2;
  98.     }
  99.  
  100.     gmp_printf( "%Zd\n", result );
  101.  
  102.     // just for correctness not needed
  103.     free(*currentlevel);
  104.     free(currentlevel);
  105.     free(*nextlevel);
  106.     free(nextlevel);
  107.  
  108.     return 0;
  109. }
RAW Paste Data