Getting all possible paths down and to the right in the nxn grid

Question

Problem 15:
Starting from the upper left corner of the 2 × 2 grid, there are 6 routes in the lower right corner (no return).
How many routes exist through a 20 × 20 grid?

So, my attempt Problem 15 is a curious expression, because I am trying to get permutations of all possible valid paths by going from the right to the left and changing the predecessor of the first change of direction. For example, when I have a 2x2 grid (look at the link graphic 15), the first path I will take will be right - right - down - and the last one I will take will be down-down - right - right , which is also my completion criterion. I am adding possible valid paths to the list, and also use this list to determine if a valid path has already been set or not. And to rearrange the path, I will do what I mentioned earlier: I go from right to left in my array (which on the chart will be in the lower right corner, where the arrow points), and change the first element, from which the next element is different from itself. Thus, on the right - on the right down - it will become on the right - on the right - on the right - down , which, obviously, is not valid, since you must have the same number of rights and falls capable of reaching the final angle. So I decided to make another loop, going from left to right, and change as many elements as possible to get a valid path. So, in this example, the right - right - right - down becomes down - right - right - down .

In addition, I forgot that I do not count points, I count the edges from the upper left corner to the lower right corner.

So, I already wrote the code, but it doesn't work at all.

package projecteuler; import java.util.ArrayList; public class Projecteuler { public static final int GRIDSIZE = 2; public static void main(String[] args) { ArrayList<boolean[]> paths = new ArrayList<>(); paths.add(new boolean[GRIDSIZE * 2]); for(int i = 0; i < GRIDSIZE; i++) { paths.get(0)[i] = true; paths.get(0)[GRIDSIZE * 2 - 1 - i] = false; } boolean[] buf = paths.get(0).clone(); printArr(buf); boolean tmp; while(!checkTerminate(paths)) { while(paths.contains(buf)) { tmp = buf[buf.length - 1]; for(int i = buf.length - 1; buf[i - 1] != tmp && 0 < i; i--) { buf[i] = !buf[i]; for(int j = 0; checkValid(buf) && j < i; j++) buf[j] = !buf[j]; } } paths.add(buf.clone()); printArr(buf); } System.out.println(paths.size()); } public static boolean checkTerminate(ArrayList<boolean[]> paths) { boolean[] endPath = new boolean[GRIDSIZE * 2]; for(int i = 0; i < GRIDSIZE; i++) { endPath[i] = false; endPath[GRIDSIZE * 2 - 1 - i] = true; } return paths.contains(endPath); } public static boolean checkValid(boolean[] arr) { int countR = 0, countL = 0; for(int i = 0; i < arr.length; i++) if(arr[i]) countR++; else countL++; return countR == countL; } public static void printArr(boolean[] arr) { for(int i = 0; i < arr.length; i++) System.out.print(arr[i] ? "right " : "down "); System.out.println(); } } 

It somehow does not change anything.

 right right down down right right down down right right down down right right down down ... 

etc. it all leads out. It seems that the code just does not rearrange my path, but also does not get stuck in any of the for loops. My best guess would be that my function criteria are placed in the wrong sequence

I also thought of a solution with a digression, as it was done for the maze two years ago at school, but I want to see how this approach is impossible or not anywhere before, before redoing everything.

EDIT:
I will try to implement the images of the 2 x 2 grid asap example, but at the moment the ProjectEuler site is under control.

Answer 1

The decision is determined by the number of combinations of "down" and "right" movements that we can have. Since there is no return, there is N down and N to the right as a whole (in any route, for the grid NxN ). Only 2N movements.

We can get this using a binomial coefficient, ⁿ C _r (pronounced "n select r"), which represents the number of ways to select objects r from N objects (each of which can be two things). In our case, the “object” is either a downward movement or to the right. It is given

So we want:

For N = 2 this gives 6 . For N = 20 this gives 137846528820 .

Answer 2

Let the step on the right be called R and the step down be called D.

To go from the top left to the bottom right on the grid of n rows and m, you will need to go right m times and go down n times.

Essentially, you will need to get all possible locations of m R and n D.

---

Example. For a 2 by 2 grid, the number of unique permutations of the word RRDD will be the number of ways you can go, namely:

• Rrdd
• RDRD
• DRDR
• DDRR

---

Google formula for calculating permutations of letters with repetition, which is set:

n! / (r ₁ ! * r ₂ ! ...), where the sum of all r is n.

This question first appears in Math SE when looking for a recurring number of permutations of letters, and the second answer explains better, in my opinion.

---

So, to return the score and even return the paths, you do not need to go through the maze at all. Just do a formula calculation for the first and type permutations for the second problem.

Providing paths when certain steps are disconnected from the grid will be the only case requiring the actual passage of the maze.

---

UPDATE:

This helps to visualize the formula for rearranging repeating letters.

Here is a slide demonstrating this case. See how 2 E eventually duplicates mechanisms when creating permutations. In general, any letter repeating r times will cause r! duplication, because wherever this letter is located, it can be replaced by another letter without providing a new permutation.

Thus, if we divide the total number n! permutations with r !, we get actual unique permutations.

_{Image source}