0

I'm a novice without any knowledge of algorithm optimization. I'm trying to write a code that counts the number of paths on a 20x20 grid, or lattice, from its top-left corner to its bottom-right one, only being able to move down and to the right. For example, the number of paths on a 2x2 grid would be 6:

My (very not optimal) idea is: any sequence of 2*20 moves such that I move down as many times as I move to the right, will get me to the final point. So I would generate any possible sequence of down and right moves, and then count those that respect that criteria.

I wanted to represent this sequence with a 40-bits binary number, where 0s and 1s represent the two possible moves. I code in C and didn't find a way to deal with binary numbers, so I use an array of 40 ints. So by starting from int n = {0,0,...,0} I check that number of zeros = number of ones, if so I increase a counter. I then "sum 1" to this array as I would do to a binary number, and I repeat until I get to {1,1,...,1}.

The code takes 7 seconds for 13x13 grids, up to 8 minutes for a 16x16 grid, and I'd need weeks to run it for a 20x20 grid. Is there any way that this code can be speeded up? Or is this an overall silly strategy to solve the problem? The code is the following:

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

int ispath(int* n, int siz){
  //returns 1 if n has number of 1s = number of 0s, returns 0 otherwise
  int n0,n1;
  n0=0; n1=0;
  for(int i=0;i<siz;i++){
    if(n[i]==0) n0++;
      else n1++;
  }
  if(n1==n0) return 1;
    else return 0;
}
int risen(int* n,int siz){
  //"sums" 1 to the binary number represented by n
  //returns just to break from function
  for(int i =siz-1;i>=0;i--){
    if(n[i]==0){
      n[i]=1; return 1;
    }else n[i]=0;
  }
}
int sumn(int* n, int siz){
  int sum=0;
  //sum elements of n, to check when n=11...1 and stop the while loop in main
  for(int i =0;i<siz;i++) sum+=n[i];
  return sum;
}

int main(){
  int n[] = {0,0,0,0};//NXN lattice requires n with 2N starting zeros. This n represents 2x2 lattice
  int sizen = sizeof(n)/sizeof(n[0]);
  long long cnt = 0;
  while(sumn(n,sizen)<sizen){
    if(ispath(n,sizen)){
      cnt++;
    }
    risen(n,sizen);
  }
  printf("Number of paths: %lli",cnt);
}
JuliusC
  • 1
  • 2
  • 1
    You have the right idea with the binary number. You have a 40-bit number with twenty 1's and twenty 0's. So the question is, how many ways can you select the positions of the 1's? That turns out to have a simple mathematical answer, which is known a [N choose K](https://en.wikipedia.org/wiki/Binomial_coefficient), otherwise known as a binomial coefficient. The calculation for 40 choose 20 is `40! / (20! * 20!)`. – user3386109 Nov 04 '22 at 19:36
  • With a grid of 20×20 boxes, you have an array of 21×21 points at the corners of those boxes. Create a 21×21 array, say `N`, indexed from 0 to 20 in one dimension and 0 to 20 in the other dimension. In `N[20][20]` put 1, because, if you are at the point (20, 20), there is only one way to get to the goal (which is point (20, 20)), and that is to do nothing. Now consider working backwards. If we were at point (20, 19), there is 1 way to get to (20, 20), and that is to go right (or down, depending on which dimension you call which), and then there is 1 thing to do (stop), so set `N[20][19]` to 1… – Eric Postpischil Nov 04 '22 at 19:40
  • [Here's an answer that I wrote](https://stackoverflow.com/a/28058811/3386109) that explains how to do that calculation without causing overflows. Note that the answer is about 1.4e11 so you'll need to use 64-bit math to get the exact answer. – user3386109 Nov 04 '22 at 19:40
  • … Similarly, `N[19][20]` should be set to 1. All the elements `N[i][20]` and `N[20][i]` should be set to 1. Now, what about `N[19][19]`. From point (19, 19), you can go to (19, 20), and then there is 1 way to get to (20, 20). But you can also go to (20, 19), and then there is 1 way to get to (20, 20). So set (19, 19) to 2. Next consider (18, 19). From there, you can go to (19, 19), and then there are 2 ways to get to (20, 20), which we know because `N[19][19]` is 2. Or you can go to (20, 19), and `N[20][19]` is set to 1. So set `N[18][19]` to 2. Continue working through the boxes… – Eric Postpischil Nov 04 '22 at 19:42
  • … Set each `N[i][j]` that is not on an edge to `N[i+1][j] + N[i][j+1]`. But do it in an order that uses `N[i+1][j]` and `N[i][j+1]` only after they have been set. (There are of course patterns in these numbers, so there are other ways to do this, but this is a good exercise to learn and build skills without taking too long to compute.) – Eric Postpischil Nov 04 '22 at 19:43
  • In the example with a 2x2 grid, you have `2*2 = 4` moves and 2 of them need to be down, so the answer is 4 choose 2 which is `4! / (2! * 2!) = 24 / (2 * 2) = 6` – user3386109 Nov 04 '22 at 19:44
  • Eric's method will also work. It computes all of the numbers in Pascal's triangle. Just be sure to declare the array as an array of `uint64_t` since the numbers grow rapidly, and will overflow 32-bit numbers. – user3386109 Nov 04 '22 at 19:49

0 Answers0