Last active
June 8, 2021 00:49
-
-
Save GerardoLSJ/42266d6cbdfee24ae90b8d02b1301346 to your computer and use it in GitHub Desktop.
Breadth FIrst Search over a matrix using Javascript
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* Have the function ClosestNeighbour(strArr) read the matrix of numbers stored in strArr which | |
| will be a 2D matrix that contains only the integers 1, 0, or 2. | |
| Then from the position in the matrix where a 1 is, return the number of spaces either left, | |
| right, down, or up you must move to reach an enemy which is represented by a 2. | |
| You are able to wrap around one side of the matrix to the other as well. | |
| For example: if strArr is ["0000", "1000", "0002", "0002"] then this looks like the following: | |
| 0 0 0 0 | |
| 1 0 0 0 | |
| 0 0 0 2 | |
| 0 0 0 2 | |
| For this input your program should return 2 because the closest enemy (2) is 2 spaces away from | |
| the 1 by moving left to wrap to the other side and then moving down once. | |
| The array can contain any number of 0's and 2's, but only a single 1. | |
| It may not contain any 2's at all as well, where in that case your program should return a 0. | |
| The program should also return 0 if the matrix is malformed, meaning the column count is not the | |
| same in all rows. | |
| */ | |
| class Node{ | |
| constructor(value, coords, level){ | |
| this.value = value | |
| this.coords = coords | |
| this.level = level | |
| } | |
| } | |
| class Main{ | |
| constructor(matrix){ | |
| if(this.validateMatrix(matrix)){ | |
| this.n = matrix.length | |
| this.m = matrix[0].length | |
| this.matrix = matrix | |
| //we want to know which nodes are already visited | |
| this.auxMatrix = Array(this.m).fill(0).map(()=>Array(this.n).fill(0)) | |
| this.queue = [] | |
| this.invalid = false | |
| }else{ | |
| this.invalid = true | |
| console.log('invalid matrix') | |
| } | |
| } | |
| run(){ | |
| //If the matrix is not valid return 0 could be -1 for notation and error reference | |
| if(this.invalid) return 0 | |
| const root = this.findRoot() //Where is the 1 in the matrx | |
| this.queue.push(new Node(this.matrix[root[0]][root[1]], root, 0)) | |
| this.auxMatrix[root[0]][root[1]] = 1 | |
| //BFS Search over the matrix | |
| while(this.queue.length){ | |
| const node = this.queue.shift() | |
| if(node.value == 2){ // If there is a 2 it means we already find a monster | |
| console.log(node) | |
| return node.level //its level is the number of steps according to BFS | |
| } | |
| this.addNeighbors(node) | |
| } | |
| return 0 | |
| } | |
| addNeighbors(n){ | |
| //console.log('init', n.coords) | |
| //top | |
| this.checkNeighbor([n.coords[0],n.coords[1]-1],n.level,'top') | |
| //right | |
| this.checkNeighbor([n.coords[0]+1,n.coords[1]],n.level,'ri') | |
| //bottom | |
| this.checkNeighbor([n.coords[0],n.coords[1]+1],n.level,'btm') | |
| //left | |
| this.checkNeighbor([n.coords[0]-1,n.coords[1]],n.level,'lft') | |
| } | |
| checkNeighbor(c,level,type){ | |
| //console.log(type,c) | |
| if(c[0] >= this.m) c[0] = 0 | |
| if(c[0] < 0) c[0] = this.m-1 | |
| if(c[1] >= this.n) c[1] = 0 | |
| if(c[1] < 0) c[1] = this.n-1 | |
| if(!this.auxMatrix[c[0]][c[1]]){ //Check if the node is already visited | |
| this.queue.push(new Node(this.matrix[c[0]][c[1]], c, level+1 )) | |
| this.auxMatrix[c[0]][c[1]] = 1 // Mark as visited | |
| } | |
| } | |
| findRoot(){ | |
| for(let [index, value] of this.matrix.entries()){ | |
| value = value.split("") // convert to array for search | |
| const idx = value.findIndex((val)=> val == 1) | |
| if(idx>=0){ | |
| //console.log(index,idx) | |
| return [index,idx] | |
| } | |
| } | |
| } | |
| validateMatrix(matrix){ | |
| const m = matrix.length | |
| for( const item of matrix){ | |
| if(item.length != m) | |
| return false | |
| } | |
| return true | |
| } | |
| } | |
| const main = new Main(["0000", "1000", "0002", "0002"]) | |
| //const main = new Main(["10","02"]) | |
| //let r = main.validateMatrix(["10","02"]) | |
| //console.log(r) | |
| const result = main.run() | |
| console.log(result) |
Author
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Runtime:
Ubuntu 16.04
NodeJS v8.11.2
Sample output