Number of unique paths in square lattice

Created:14 Feb 2020 21:45:36 , in  Maths

Suppose that you have a square (N x N) grid and want to determine number of unique paths, which will take you from the top left corner in the grid to the bottom right one of if. You are allowed to move by one point at at time, and to the right or to the bottom only. For example, from the point 3,3 you can only visit point 3,4 or 4,3 in the grid.

Building a grid and traversing paths with PHP

Paths finding in a grid is fun when done with a pen and paper, in particular, when the grid you are using is not too large. A lot of people do it do unwind. However, for lattices greater than 3x3 it is probably better to employ a computer to do the job in a consistent manner.

Below there is a PHP class called SquareLattice. It can make your slacking computer to do some very, very heavy lifting while traversing and counting paths in the grid (see below). Internally SquareLattice uses linked lists to construct grids and pre-order traversal for finding paths.

/**
 * SquareLattice - class for building and traversing square lattices
 * Author: S.Wojnowski
 * Licence GNU v3
 */

class SquareLattice{

  private $size = NULL;
  private $lists = [];
  private $lattice = NULL;
  private $paths = [];

  public function __construct($conf){
    $this -> size = $conf['size'];
    $this -> separator = isset($conf['separator']) ? $conf['separator'] : '-';
    
    $this -> linkedList();
    $this -> join();
  }

  protected function linkedList(){
    $firstNode = NULL;
    $currentNode = NULL;    

    for($j = 0; $j < $this -> size; $j++){ 
      for($i = 0; $i < $this -> size; $i++){

        $node = new SquareLatticeNode;
        $node -> value = $j.$this -> separator.$i; 

        if($i > 0){
          $currentNode -> right = $node; 
        } else {
          $firstNode = $node;
        }

        $currentNode = $node; 
      }

      $this-> lists[] = $firstNode;
    }
  }

  protected function join(){
    $topList = NULL;
    $bottomList = NULL;

    $currentTop = NULL;
    $currentBottom = NULL;

    for($j = 0; $j < $this -> size; $j++){

      if($j === 0 ){
        $this -> lattice = $this -> lists[$j];

        if(!isset($this -> lists[$j+1])){
          return $this -> lattice;
        }
 
      }
 
      for($i = 0; $i < $this -> size ; $i++){
        if($i === 0){
          $currentTop = &$this -> lists[$j];
          $currentBottom = &$this -> lists[$j+1];
        } 

        $currentTop -> bottom = $currentBottom;
        $currentTop = &$currentTop -> right;
        $currentBottom = &$currentBottom -> right;            
      }
    }
  }

  // get lattice
  public function get(){
    return $this -> lattice;
  }

  /**
   * get all traversed paths in the lattice 
   */
  public function getPaths(){
    $this -> walk();
    return $this -> paths;
  }

  protected function walk($lattice = NULL,$path = "",$separator = ";"){
    if(!isset($lattice)){
      $lattice = $this -> lattice; 
      if(!isset($lattice)){
        return;
      } 
    }

    // this assumes node value is a string
    $path .= $lattice  -> value.$separator;

    // exit condition 
    if(!isset($lattice -> right) && !isset($lattice -> bottom)){
      $this -> paths[] = $path;
      return;
    } 

    if(isset($lattice -> right)){
      $path .= $this -> walk($lattice -> right,$path); 
    } 

    if(isset($lattice -> bottom)){
      $path .= $this -> walk($lattice -> bottom,$path); 
    }  
  }

  /**
   * print lattice
   */  
  public function __toString(){

    $str = "\n";
    $currentNode = NULL;
    $currentNodeVert = NULL;

    for($j = 0; $j < $this -> size; $j++){

      if($j === 0){
        $currentNode = &$this -> lattice;
        $currentNodeVert = &$this -> lattice;
      }      

      for($i = 0; $i < $this -> size; $i++){

        if(isset($currentNode)){
          $item = $currentNode -> value;
          $maxLen = 2 * strlen($this -> size.'') + strlen($this -> separator);
          $item = str_pad($item,$maxLen,' ',STR_PAD_LEFT);
          $str .= $item;
        }

        if(isset($currentNode -> right)){
          $str .= ' ';
          $currentNode = &$currentNode -> right;
        } else {
          $str .= "\n\n"; 
        }
      }

      if(isset($currentNodeVert -> bottom)){
        $currentNodeVert = &$currentNodeVert -> bottom;  
        $currentNode = &$currentNodeVert;
      }
    }

    return $str;
  } 
}

/**
 * SquareLattice point class
 */
class SquareLatticeNode{
  public $right = NULL;
  public $bottom = NULL;
  public $value = NULL;

  public function __construct(){

  }
}

Printing a lattice

Here is how to print a 12x12 square lattice on the command line

 
echo new SquareLattice([ "size" => 12,"separator" => "," ]);

=>
  0,0   0,1   0,2   0,3   0,4   0,5   0,6   0,7   0,8   0,9  0,10  0,11

  1,0   1,1   1,2   1,3   1,4   1,5   1,6   1,7   1,8   1,9  1,10  1,11

  2,0   2,1   2,2   2,3   2,4   2,5   2,6   2,7   2,8   2,9  2,10  2,11

  3,0   3,1   3,2   3,3   3,4   3,5   3,6   3,7   3,8   3,9  3,10  3,11

  4,0   4,1   4,2   4,3   4,4   4,5   4,6   4,7   4,8   4,9  4,10  4,11

  5,0   5,1   5,2   5,3   5,4   5,5   5,6   5,7   5,8   5,9  5,10  5,11

  6,0   6,1   6,2   6,3   6,4   6,5   6,6   6,7   6,8   6,9  6,10  6,11

  7,0   7,1   7,2   7,3   7,4   7,5   7,6   7,7   7,8   7,9  7,10  7,11

  8,0   8,1   8,2   8,3   8,4   8,5   8,6   8,7   8,8   8,9  8,10  8,11

  9,0   9,1   9,2   9,3   9,4   9,5   9,6   9,7   9,8   9,9  9,10  9,11

 10,0  10,1  10,2  10,3  10,4  10,5  10,6  10,7  10,8  10,9 10,10 10,11

 11,0  11,1  11,2  11,3  11,4  11,5  11,6  11,7  11,8  11,9 11,10 11,11

Numbers separated by a comma are points in the grid. They are not used for traversal.

Finding unique paths number for small lattices

// square lattice of size 1
$l1 = new SquareLattice([ "size" => 1 ]);
echo count($l1 -> getPaths());     
=> 1

// square lattice of size 2
$l2 = new SquareLattice([ "size" => 2 ]);
echo count($l2 -> getPaths());     
=> 2   

$l3 = new SquareLattice([ "size" => 3 ]);
echo count($l3 -> getPaths());     
=> 6

$l4 = new SquareLattice([ "size" => 4 ]);
echo count($l4 -> getPaths());     
=> 20

$l5 = new SquareLattice([ "size" => 5 ]);
echo count($l5 -> getPaths());     
=> 70

$l6 = new SquareLattice([ "size" => 6 ]);
echo count($l6 -> getPaths());     
=> 252

So far so good. Fairly fast and informative ( There are 252 unique paths in a 6x6 lattice, which would probably take a year for me to figure out by hand ).

Finding path number in 20x20 lattice

If you try to use the same technique to find number of paths for 20x20 grid, you will notice that your computer will choke seriously (the heavy lifting I mentioned above). The reason is, the number of unique paths in 20x20 grid is 35 345 263 800. Even a smaller grid, like 15x15 grid poses a bit of a problem and requires strong muscles and some amount of memory.

So how do you find the number of unique paths for 20x20 lattice?

If you look at results given for 1x1 through 6x6 lattices, you will notice, that they form a sequence. Its 20th term is 35 345 263 800. The sequence can be found at A000984.

Conclusion

When you look closer at how points in the lattice are traversed you will notice, it is a lot like traversing a binary tree. The only difference is, that instead of visiting the left and the right child node you use right and bottom ones. Another lesson from this exercise is, that the number of paths in a grid grows very rapidly and reaches incomprehensible numbers even for small grids.

That's it. I hope you have found this article interesting and informative. More machine torment is in the pipeline.

This post was updated on 14 Feb 2020 22:01:24

Tags:  php ,  recursion