Javascript 2d array select around from single point-CodePudding

Say I have a 15x15 2d array

    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, A, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

See the character A? at y:9 and x:4 (index starts with 0). What I want to do here is to update the array where I select or update the 0s around the A to, say, asterisk (*).

For an example, lets say I want 0s around the A as far as 3 indexes to be updated as *

    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, *, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, *, *, *, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, *, *, *, *, *, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, *, *, *, A, *, *, *, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, *, *, *, *, *, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, *, *, *, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, *, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

What is the most efficient way to achieve this?

EDIT What I've tried:

var s_length = 4, coordinate_y_x = [9, 4]
    for (let i1 = 0; i1 < s_length; i1  ) {

      for (let i = 0; i < s_length; i  ) {
        if (map[coordinate_y_x[0] - i][coordinate_y_x[1]] != undefined) map[coordinate_y_x[0] - i][coordinate_y_x[1]] = 1
        if (map[coordinate_y_x[0]][coordinate_y_x[1] - i]!= undefined) map[coordinate_y_x[0]][coordinate_y_x[1] - i] = 1
      }

      for (let i = s_length; i > 0; i--) {
        console.log("loop2");
        if (map[coordinate_y_x[0]   i][coordinate_y_x[1]]!= undefined) map[coordinate_y_x[0]   i][coordinate_y_x[1]] = 1
        if (map[coordinate_y_x[0]][coordinate_y_x[1]   i]!= undefined) map[coordinate_y_x[0]][coordinate_y_x[1]   i] = 1
      }

    }

I managed to change what's left, right, top, and bottom from this code with given point and length, but I can't seem to figure out how to do the rest (between directions)

    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, A, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

CodePudding user response：

One way is with a somewhat spiral matrix walk, but instead of a "square" walk, yours will be diagonal / "diamond" shape. Additionally, we don't really care about the "connectiveness" of the path, so I'll jump around a bit. That is, when a walk has finished a ring, it isn't important that the next ring start on a neighboring cell of the previous ring's last step.

In your example data, I've marked the cells that the algorithm would visit in order (1st, 2nd, 3rd, etc.)

[0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
[0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
[0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
[0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
[0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
[0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
[0,  0,  0,  0, 16,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
[0,  0,  0, 15,  7, 17,  0,  0,  0,  0,  0,  0,  0,  0,  0],
[0,  0, 14,  6,  2,  8, 18,  0,  0,  0,  0,  0,  0,  0,  0],
[0, 13,  5,  1,  A,  3,  9, 19,  0,  0,  0,  0,  0,  0,  0],
[0,  0, 24, 12,  4, 10, 20,  0,  0,  0,  0,  0,  0,  0,  0],
[0,  0,  0, 23, 11, 21,  0,  0,  0,  0,  0,  0,  0,  0,  0],
[0,  0,  0,  0, 22,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
[0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
[0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]

Note, I've chosen to always start from the left side of the origin, but that is arbitrary. You could start from the top, right, or bottom side.

So our three loops (in order) will be

The length we want to "expand" by can be thought of as a separate "ring." So loop each ring.
Next, loop each "side" of that ring.
Finally, loop each "step" along that side.

To keep things symmetric, each side will only occupy a single "corner" cell. So for example when looping the 3rd ring, each side would only be 3 steps each. Here I have each side labeled as a, b, c, and d.

* * * b * * *
* * a * b * *
* a * * * b *
a * * X * * c
* d * * * c *
* * d * c * *
* * * d * * *

Otherwise the only tricky part is figuring out how to change directions as you loop each side.

A very simple way to do this is store "deltas," how much we expect each x and y value (where we currently are) to change for each step. We know we'll be moving 1 step each time, so it is just a matter of moving right / down (positive ) or left / up (negative -).

I decided to store these values in an array, but you can probably do some modulo math to switch between them. Looping over a constant is just a little easier to understand. So moving up and to the right would have an x_delta value of 1 and y_delta value of -1, etc.

Finally, you need a "in bounds" check as you are completing your walk. The algo will still try and "visit" these cells, but won't try to write to the array if it doesn't exist. This is one area of the algo you can probably improve.

Put it all together, and you have this:

const data = Array(15)
    .fill()
    .map(v => Array(15).fill(0));

// Assumes the graph won't contain `undefined` values. Otherwise, do a `length` check on the arrays
function inBounds(data, [y, x]) {
    return data?.[y]?.[x] !== undefined;
}

const deltas = [
    [ 1, -1], // Up right
    [ 1,  1], // Down right
    [-1,  1], // Down left
    [-1, -1], // Up left
];

function fillFrom({origin: [oy, ox], data, length, value}) {
    // Walk in diamond "rings" around our origin
    for (let size = 1; size <= length; size  ) {
        // Start from the left side of our ring
        let x = ox - size;
        let y = oy;
        // Move along 4 sides of the diamond
        for (let [xd, yd] of deltas) {
            // Move each step along the side
            for (let step = 0; step < size; step  ) {
                if (inBounds(data, [y, x])) {
                    data[y][x] = value;
                }
                x  = xd;
                y  = yd;
            }
        }
    }

    return data;
}


// Updates data "in place." Would need to deep clone if you wanted to keep things immutable
fillFrom({origin: [9, 4], data, length: 3, value: 1});
data[9][4] = 'A';

console.log(data.map(r => r.join('')).join('\n'));