# 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