Skip to content

Instantly share code, notes, and snippets.

@mdciotti
Created October 16, 2015 06:39
Show Gist options
  • Save mdciotti/9d59075669bc5bb4103a to your computer and use it in GitHub Desktop.
Save mdciotti/9d59075669bc5bb4103a to your computer and use it in GitHub Desktop.
Calculates the number of paths in a n*n (square) lattice
#import <stdio.h>
#import <stdlib.h>
#import <math.h>
// Retuns the number of paths in a n*n (square) lattice
// Paths can only move rightward or downward
// Paths start at top left and end at bottom right
// Receives an argument `n` which is the length of one side of the square lattice
/* Visual examples:
2x2 lattice
######----+ ######----+
| # | | # |
+----###### +----#----+
| | # | # |
+----+----# +----######
R D R D R D D R
0 1 0 1 0 1 1 0
3x3 lattice:
######----+----+ ######----+----+
| # | | | # | |
+----########### +----#----+----+
| | | # | # | |
+----+----+----# +----#----+----+
| | | # | # | |
+----+----+----# +----###########
R D R R D D R D D D R R
0 1 0 0 1 1 0 1 1 1 0 0
*/
unsigned long long int latticePaths(unsigned int n)
{
// Paths can be represented as permutations of R and D (right and down).
// We only want paths that have the same number of rightward
// and downward movements (they end up at the opposite corner).
// Therefore, we only want permutations of R and D where
// the count of R is equal to the count of D.
// We express R as 0 and D as 1.
// Length of each permutation
unsigned int len = n + n;
// Number of downward moves (maximum n)
unsigned int ones;
// Number of paths found (might be big)
unsigned long long int count = 0;
// Where to start permutations
// (we will not find any valid permutations before 2^n - 1)
unsigned int start = (1 << n) - 1;
// Where to end permutations
// should stop at halfway through permutations: 2^(len-1)
// We only need to check half, since the other half
// are just flipped versions of the first half.
unsigned int end = (1 << (len - 1)) - (1 << (n - 1)) + 1;
// Main counting loop
unsigned int i;
for (i = start; i < end; i++)
{
// Count the number of ones in the binary representation of this number
// int num = i;
// for (ones = 0; num > 0; ones++) num &= num - 1;
// Wow this is fast: (GCC only, compile with -O3 for optimizations)
ones = __builtin_popcount(i);
// Increase count if no. of ones is exactly n
// (equal amounts of zeros and ones)
if (ones == n) count++;
}
// We only found half, the other half are just inverses
// so we return twice the number we counted
return count << 1;
}
int main(int argc, char const *argv[])
{
// The counted paths
unsigned long long int count;
// The total number of permutations for this lattice
unsigned long long int permutations;
// The fraction of permutations which are valid paths in this lattice
float fraction;
// Read the size of the lattice from arguments list
unsigned int size = atoi(argv[1]);;
// total permutations = 2^(size + size)
permutations = 1 << (size << 1);
// Count the valid paths
count = latticePaths(size);
fraction = (float) count / permutations;
printf("latticePaths(%d) = %llu\n", size, count);
printf("fraction (%llu / %llu) = %f\n", count, permutations, fraction);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment