Question Number
15
Project Euler Question

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

Solution Found
False

File Status: Solution File found. Code from the function code_solution_15 will be used

Solution: 137846528820

Solution Code:

      <?php

  function code_solution_15() {

    $grid = array_fill(0, 21, array_fill(0, 21, null));

    for($i = 20; $i >= 0; $i--) {
      for($j = 20; $j >= 0; $j--) {
        count_ways_to_end($i,$j, $grid);
      }
    }

    return $grid[0][0];
  }

  function count_ways_to_end($i,$j, &$grid) {
    if($grid[$i][$j] != null) {
      return $grid[$i][$j];
    }

    if($i== 20 and $j == 20) {
      $grid[$i][$j] = 0;
    } else if($i == 20 xor $j == 20) {
      $grid[$i][$j] = 1;
    } else {
      $grid[$i][$j] = $grid[$i][$j+1] + $grid[$i+1][$j];
    }
  }