Finding coordinates on a grid (2D array)

Question

I'm currently trying to solve a problem I failed to solve in a white-board mock interview. I got stuck a few times. Any help is appreciated.

The question was worded as such:

Given an NxN grid with an array of lamp coordinates. Each lamp provides illumination to every square on their x-axis, every square on their y-axis, and every square that lies in their diagonal (think of the Queen in chess). Given an array of query coordinates, determine whether that point is illuminated or not.

The catch is when checking a query, all lamps adjacent to or on that query gets turned off. If you visit a coordinate/cell, turn off all lamps that are in that coordinates or adjacent. Two cells are adjacent if they share the same edge or corner.

write a function checkLampIllumination(N, lamps, queries)

N : size of the grid

lamps : coordinates of a lamp

queries : coordinates on the grid to be checked if they are lit or not

The test case I was given was:

N = 8

lamps = [
    [1,6],
    [5,6],
    [7,3],
    [3,2]
]

queries = [
    [4,4],
    [6,6],
    [8,1],
    [3,2],
    [2,3]
]

OUTPUT:

['DARK','LIGHT','DARK','DARK','LIGHT']

Second Test case:

checkLampIllumination(8, [[4,3],[4,4]], [[3,4],[7,6]])

N = 8

lamps = [
    [4,3],
    [4,4]
]

queries = [
    [3,4],
    [7,6]
]

OUTPUT:

['DARK','LIGHT']

Here is my current stab at it. I think the current solution just creates the grid. I really don't know where to go from here.

const checkLampIllumination=(N, lamps, queries) => {
    var gridNxN = []
    var row = []
    for (var i = 1; i < 100; i++) {
        if (i.toString().indexOf('0') !== -1) {
            row.push(i)
            gridNxN.push(row)
            row = []
        } else {
            row.push(i)
        }
    }
}

user_9515207 · Answer

Just for visualization of the lamps and queries, you can play with a pixel art generator if you want.

I'd first create a helper function isAdjacent to check whether two points are adjacent. Then, iterate over each query (target square), and check if any lamp illuminates the target. The problem reduces to checking that:

The lamp is not adjacent, and at least one of the following is true:
The lamp either has the same X coordinate, or
the same Y coordinate, or
they're on the same diagonal, which can be checked by seeing if the difference between the lamp's and target's X coordinates is equal to the difference between the lamp's and target's Y coordinates.

Putting this into code, you get:

let lamp = [
  [1, 6],
  [5, 6],
  [7, 3],
  [3, 2]
];
const queries = [
  [4, 4],
  [6, 6],
  [8, 1],
  [3, 2],
  [2, 3]
]

const isAdjacent = (x1, y1, x2, y2) => Math.abs(x2 - x1) < 2 && Math.abs(y2 - y1) < 2;
queries.forEach(([checkX, checkY]) => {
  const thisSquareIlluminated = lamp.some(([lampX, lampY]) => (
    !isAdjacent(checkX, checkY, lampX, lampY) && (
      lampX === checkX
      || lampY === checkY
      || Math.abs(lampX - checkX) === Math.abs(lampY - checkY)
    )
  ));
  console.log(thisSquareIlluminated ? 'LIGHT' : 'DARK');
});

I wouldn't recommend building the illuminated squares beforehand, because then, given a query, you wouldn't know if a particular square with illumination only has illumination due to an adjacent lamp or not, at least not without iterating through all the lamps again - better to just iterate through them once, after a query is selected.

Note that the N = 8 input is not used anywhere - it's a red herring, unless you also need to check for whether lamps/queries are in valid spaces on the board as well.

user_2202732 · Answer

Since we're not in an interview at the moment, I've decided to keep the code not compact, so it can be understood easier. You can shorten it if you want. I love this kind of problems, so I took my time with it.

Also I've updated the visual grid. Now you can see the states of the grid as it changes.

var lamps = [
    [1,6],
    [5,6],
    [7,3],
    [3,2]
];

var queries = [
    [4,4],
    [6,6],
    [8,1],
    [3,2],
    [2,3]
];

/* ==================== VISUAL GRID ==================== */

function arrayFlatten(array) {
    var result = [];
    array.forEach(function (item) {
        if (item instanceof Array) {
            result = result.concat(arrayFlatten(item));
        } else {
            result.push(item);
        }
    });
    return result;
}

function createGrid(lamps, queries) {
    var grid = document.createElement("table");
    grid.classList.add("grid");
    var gridSize = Math.max.apply(null, arrayFlatten([lamps, queries])) + 1;
    
    document.body.appendChild(grid);
    
    // create cells
    for (var i = 0; i < gridSize; i++) {
        var row = document.createElement("tr");
        for (var j = 0; j < gridSize; j++) {
            var cell = document.createElement("td");
            row.appendChild(cell);
        }
        grid.appendChild(row);
    }
    
    // add lamps
    lamps.forEach(lamp => grid.rows[lamp[1]].cells[lamp[0]].classList.add("lamp"));

    var illuminatedRows = Array.from(new Set(lamps.map(([lampX, lampY]) => lampY)));
    var illuminatedCols = Array.from(new Set(lamps.map(([lampX, lampY]) => lampX)));
    illuminatedRows.sort();
    illuminatedCols.sort();

    // add lights
    // horizontal
    for (var i = 0; i < grid.rows.length; i++) {
        if (illuminatedRows.includes(i)) {
            Array.from(grid.rows[i].cells).forEach(cell => cell.classList.add("horizontal-light"));
        }
    }
    // vertical
    for (var i = 0; i < grid.rows.length; i++) {
        for (var j = 0; j < grid.rows[i].cells.length; j++) {
            if (illuminatedCols.includes(j)) {
                grid.rows[i].cells[j].classList.add("vertical-light");
            }
        }
    }
    // diagonal
    for (var i = 0; i < grid.rows.length; i++) {
        for (var j = 0; j < grid.rows[i].cells.length; j++) {
            var x = j;
            var y = i;
            lamps.forEach(function (lamp) {
                if (isDiagonal(lamp[0], lamp[1], x, y)) {
                    grid.rows[i].cells[j].classList.add("diagonal-light");
                }
            });
        }
    }
    
}

createGrid(lamps, queries);

/* ==================== CALCULATION ==================== */

function isHorizontal(y1, y2) {
    return y1 == y2;
}

function isVertical(x1, x2) {
    return x1 == x2;
}

function isDiagonal(x1, y1, x2, y2) {
    return Math.abs(x1 - x2) == Math.abs(y1 - y2);
}

function isIlluminated(queryX, queryY, lampX, lampY) {
    return isHorizontal(queryY, lampY) || isVertical(queryX, lampX) || isDiagonal(queryX, queryY, lampX, lampY);
}

function isAdjacent(x1, y1, x2, y2) {
    return Math.abs(x2 - x1) < 2 && Math.abs(y2 - y1) < 2
}

// check every lamp for each query
function checkLamps(lamps, queryX, queryY) {
    // store checks for each lamp for a query
    var checks = [];
    // loop every lamp
    for (var i = lamps.length - 1; i >= 0; i--) {
        var lampX = lamps[i][0];
        var lampY = lamps[i][1];
        // check if the target cell is adjacent to the current lamp
        if (isAdjacent(queryX, queryY, lampX, lampY)) {
            console.log("Query (" + [queryX, queryY].join() + ") is adjacent to lamp (" + [lampX, lampY].join() + "). Removing this lamp.");
            // lamp is adjacent; remove it
            lamps.splice(i, 1);
            // create a grid with the new state (for visual purposes)
            createGrid(lamps, queries);
            // skip this lamp
            continue;
        } else {
            // storing the check for the current lamp
            checks.push(isIlluminated(queryX, queryY, lampX, lampY));
        }
    }
    // if all checks are false, it's dark
    // if there's even a single true, that means the cell is illuminated by a lamp
    if (checks.includes(true)) {
        console.log("(" + [queryX, queryY].join() + ") is LIGHT");
    } else {
        console.log("(" + [queryX, queryY].join() + ") is DARK");
    }
}

function checkLampIllumination(lamps, queries) {
    // create a local copy of lamps because it'll (might) mutate
    var lamps = lamps.slice();
    // loop queries
    queries.forEach(([queryX, queryY]) => checkLamps(lamps, queryX, queryY));
}

checkLampIllumination(lamps, queries);

.grid {
    background-color: black;
    border-collapse: collapse;
    margin-right: 1em;
    float: left;
}
.grid td {
    width: 25px;
    height: 25px;
    border: 1px solid hsl(0, 0%, 50%);
}
.grid td.horizontal-light,
.grid td.vertical-light,
.grid td.diagonal-light {
    background-color: hsla(0, 0%, 80%, .33);
}
.grid td.horizontal-light.vertical-light,
.grid td.horizontal-light.diagonal-light,
.grid td.vertical-light.diagonal-light {
    background-color: hsla(0, 0%, 80%, .45);
}
.grid td.horizontal-light.vertical-light.diagonal-light {
    background-color: hsla(0, 0%, 80%, .6);
}
.grid td.lamp {
    background-color: hsl(0, 0%, 100%) !important;
}

Finding coordinates on a grid (2D array)

2 Answers