Grid Illumination

There is a good algorithm problem I found on LeetCode. Let’s say you have a lamp on at a coordinate [x1, y1], and you want to see if the light can reach another coordinate [x2, y2]. The conditions are the lamp can light up a coordinate if it is horizontal, vertical, or diagonal from it. However, if a query that is adjacent to the lamp, the lamp is turned off and we will get a dark answer. Here is a simple illustration of the problem in figure 1.

Fig. 1: Lamp illumination

If you want to read the problem in more detail, I have linked the question from LeetCode below.

The first step is to see whether a query is vertical, horizontal, or diagonal from the lamp(s). Let’s start with vertical. We are using (x, y) coordinates so if something is vertical, then x1 = x2. In code terms, this is

function vertical(x1, x2){
    return x1 === x2
}. 

Next, we will look at horizontal. It is

function horizontal(y1, y2){
    return y1 === y2
}, 

and finally, diagonal is when the differences between (x1, y1) and (x2, y2) are equal or

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

Next, we need a function to see if a query will be illuminated. If the query coordinate satisfies one of the three above conditions, it is.

function isIlluminated(qx, qy, lx, ly){
    return horizontal(ly, qy) || vertical(lx, qx) || diagonal(lx, qx, ly, qy)
}

We need to add a function regarding the adjacent property. The lamp and query are adjacent if the difference between both coordinates are less than 2. In this question, adjacent is when the query is less than 2 coordinates away. In other words,

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

The easy part is over. We now are at the meat of the problem. We want to check each lamps against all queries; if this query is not adjacent, then it is illuminated. If this query is true, we will return light; if not, return dark. The code is

function check(lamps, qx, qy){
    var arr = []
    for(var x = 0; x < lamps.length; x++){
        let lx = lamps[x][0]
        let ly = lamps[x][1]
        if(!adjacent(lx, qx, ly, qy)){
            arr.push(isIlluminated(qx, qy, lx, ly))
        }
    }
    if(arr.includes(true)){
        return 'LIGHT'
    }
    else{
        return 'DARK'
    }
}

Finally, we make a final function that calls the “check” function and push ‘light’ and ‘dark’ into an array.

function gridIllumination(lamps, queries) {
   var arr = []
   queries.forEach(([qx, qy]) => arr.push(check(lamps, qx, qy)))
   return arr
}

Full code is

function horizontal(y1, y2){
    return y1 === y2
}
function vertical(x1, x2){
    return x1 === x2
}
function diagonal(x1, x2, y1, y2){
    return Math.abs(x1 - x2) === Math.abs(y1 - y2)
}
function isIlluminated(qx, qy, lx, ly){
    return horizontal(ly, qy) || vertical(lx, qx) || diagonal(lx, qx, ly, qy)
}
function adjacent(x1, x2, y1, y2){
    return Math.abs(x1 - x2) < 2 && Math.abs(y1 - y2) < 2
}
function check(lamps, qx, qy){
    var arr = []
    for(var x = 0; x < lamps.length; x++){
        let lx = lamps[x][0]
        let ly = lamps[x][1]
        if(!adjacent(lx, qx, ly, qy)){
            arr.push(isIlluminated(qx, qy, lx, ly))
        }
    }
    if(arr.includes(true)){
        return 'LIGHT'
    }
    else{
        return 'DARK'
    }
}
function gridIllumination(lamps, queries) {
   var arr = []
   queries.forEach(([qx, qy]) => arr.push(check(lamps, qx, qy)))
   return arr
}

Let’s give it a go. Say our lamps and queries are

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

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

and the given solution is

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

let’s see if it matches.

Fig. 2: Solution.

We can see it is indeed the solution!

References

1. https://leetcode.com/problems/grid-illumination/