How to compute all possible paths on a grid

Question

I've recently seen a challenge picture on brillant.org's Instagram account:

The instructions: The robot takes 4 random steps (can't go diagonal).

In which area is it most likely to land?

Obviously there are 4⁴ = 256 possible paths for the robot. I tried to write a program (Javascript) to solve that problem but my approaches didn't work. Actually I don't have useful code to show here because I got stuck pretty early on.

So my question: How would you write a program that:

1. Checks all 256 possible paths and

2. Tells me how many (%) landed in which area

Answer 1

This is a very cool question! And thanks for letting me discover brillant.org's Instagram account. So, I would proceed as following:

1. Write a function to calculate all possible permutation with repetition (n^k)
2. Generate a map where to execute all possible moves calculated in the step 1
3. Check the area where the robot would land on with the final step and store it
4. Calculate the percentage based on the counting in step 3

The first step is a problem by itself, and it's not part of this scope. You can use or adapt the code here: https://rosettacode.org/wiki/Permutations_with_repetitions

Then, to generate the map, I simply used an array:

const map = [
  0, 0, 0, 0, 1, 0, 0, 0, 0,
  0, 0, 0, 1, 1, 1, 0, 0, 0,
  0, 0, 1, 1, 2, 1, 1, 0, 0,
  0, 1, 1, 2, 2, 2, 1, 1, 0,
  1, 1, 3, 3, 2, 3, 3, 1, 1,
  0, 1, 1, 3, 3, 3, 1, 1, 0,
  0, 0, 1, 1, 3, 1, 1, 0, 0,
  0, 0, 0, 1, 1, 1, 0, 0, 0,
  0, 0, 0, 0, 1, 0, 0, 0, 0,
];

This is a representation of the image you gave, each area is marked with a different number, that we will reuse later.

At this point I defined an array of the 4 possible moves:

const moves = [
  -1,  // left 
   1,  // right,
  -9,  // top
   9,  // bottom
];

The values indicates the offset needed to move in the direction wrote in in the comment: left and right I guess are self explanatory. For the top and bottom, since we're using an array as "matrix", we basically need to translate the y value to a index value in the array. The formula is simple: index = x + y * width there fore it means if you want to specify a y to move up by one cell you have -1 * 9, and to move down is 1 * 9.

For the same reason the robot's starting position (at the center of the map) is calculate as follow: 4 + 4 * 9.

Now I calculate all the possible moves combination with the permutation function:

const allmoves = permutationsWithRepetition(4, moves);

And create an array to store the results:

let results = [0, 0, 0, 0];

After that, I just iterate all the possible moves array, and calculate the position at the end of the moves:

for (let j = 0; j < allmoves.length; j++) {
  // set the robot's initial position at the center
  // before executing any moves' list
  let pos = 4 + 4 * 9;

  // calculate the new position using the current moves
  for (let i = 0; i < moves.length; i++) {
    let move = allmoves[j][i];
    pos += move;
  }

  // now `map[pos]` points to a number between 1 and 3
  // that identify the area where the robot is.
  // we use that number as index of the results
  // to increment its value.
  // Notice that it's impossible land to any 0 area
  // if we start from the center and we can only perform
  // 4 moves.
  // We use that number as `index` for our `results`
  results[map[pos]]++;
}

Now in results you will have how many times the robot ended up in which area:

console.log(results); // [0, 60, 100, 96]

As mentioned is impossible given the starting position and the number of moves for the robot to land in any of the 0 area, so the first index would have 0 as value. You can see that it landed in the area 1 (the orange one) 60 times, in the area 2 100 times (the smallest area, the green / aqua one), and in the area 3, 96 times (the blue / purple one).

At this point you can calculate the percentage (times / total * 100) and display it with a proper formatting:

// we skip the first element of results since
// it's not an area (and we'll be always 0)
for (let k = 1; k < results.length; k++) {
  console.log(k, `${(results[k] /  allmoves.length * 100).toFixed(2)}%`)
}

And you'll get:

1 "23.44%"
2 "39.06%"
3 "37.50%"

You can also do an empiric check, and actually generate ten thousands of moves randomly and make the program apply those instead of allmoves, and you'll see that you end always with similar number (obviously, but that also the fun part of math, verify that is actually what you will expect!).

Here the a working code that also implement the permutation code mentioned at the beginning, from rosettacode.org, and the code explained in this post: https://codepen.io/zer0/pen/RwWPZmE

(You need to open the console to see the results)

Answer 2

I would create different objects representing the different possibilities like below:

function Path(x, y, movesLeft) {

    this.x = x;
    this.y = y;
    this.movesLeft = movesLeft;

    this.paths = [];
    if (movesLeft > 0) {
        this.paths.push(new Path(x - 1, y, movesLeft - 1));
        this.paths.push(new Path(x + 1, y, movesLeft - 1));
        this.paths.push(new Path(x, y - 1, movesLeft - 1));
        this.paths.push(new Path(x, y + 1, movesLeft - 1));
    }

    this.getArray = function() {
        if (this.movesLeft > 0) {
            var output = [];
            for (var i = 0; i < this.paths.length; i++) {
                output = output.concat(this.paths[i].getArray());
            }
            return output;
        }
        return [this];
    }

}

Now, you can create an object and test the results:

var endPosArray = new Path(0, 0, 4).getArray();

All you need to do is loop through the array and calculate the chances.