Javascript A* search implementation
168 ms, 45.9MB\n\nAn ugly implementation, but since didn\'t see a javascript implementation of this yet decided to post mine up to see if it helps someone. The 
168 ms, 45.9MB\n\nAn ugly implementation, but since didn\'t see a javascript implementation of this yet decided to post mine up to see if it helps someone. The priorityqueue implementation was straight lifted from a stack overflow post. Basically a* search is bfs + heuristics + priorityqueue. Used the same heuristic that many other users are using which is just the manhattan distance + number of moves thus far.\n\nOriginally I try to just solve this without using a priorityqueue and just sorting the array at every loop, but the time penalty was too great (I naively thought time complexity will remain the same assuming that nlogn of sort is equivalent to heapifying n moves, but I realized that at each instance you are only really considering 5 new states to push in to the queue so it\'s not the same). Also, now looking at it using Map for states was probably not necessary, probably would\'ve been better to use a Set and use...\n((block[0]*grid[0].length)+block[1])*(grid[0].length*grid.length) +((character[0]*grid[0].length)+character[1])\n\n```\n/**\n * @param {character[][]} grid\n * @return {number}\n */\nconst top = 0;\nconst parent = i => ((i + 1) >>> 1) - 1;\nconst left = i => (i << 1) + 1;\nconst right = i => (i + 1) << 1;\n\nclass PriorityQueue {\n  constructor(comparator = (a, b) => a > b) {\n    this._heap = [];\n    this._comparator = comparator;\n  }\n  size() {\n    return this._heap.length;\n  }\n  isEmpty() {\n    return this.size() == 0;\n  }\n  peek() {\n    return this._heap[top];\n  }\n  push(...values) {\n    values.forEach(value => {\n      this._heap.push(value);\n      this._siftUp();\n    });\n    return this.size();\n  }\n  pop() {\n    const poppedValue = this.peek();\n    const bottom = this.size() - 1;\n    if (bottom > top) {\n      this._swap(top, bottom);\n    }\n    this._heap.pop();\n    this._siftDown();\n    return poppedValue;\n  }\n  replace(value) {\n    const replacedValue = this.peek();\n    this._heap[top] = value;\n    this._siftDown();\n    return replacedValue;\n  }\n  _greater(i, j) {\n    return this._comparator(this._heap[i], this._heap[j]);\n  }\n  _swap(i, j) {\n    [this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]];\n  }\n  _siftUp() {\n    let node = this.size() - 1;\n    while (node > top && this._greater(node, parent(node))) {\n      this._swap(node, parent(node));\n      node = parent(node);\n    }\n  }\n  _siftDown() {\n    let node = top;\n    while (\n      (left(node) < this.size() && this._greater(left(node), node)) ||\n      (right(node) < this.size() && this._greater(right(node), node))\n    ) {\n      let maxChild = (right(node) < this.size() && this._greater(right(node), left(node))) ? right(node) : left(node);\n      this._swap(node, maxChild);\n      node = maxChild;\n    }\n  }\n}\n\nvar minPushBox = function(grid) {\n    if(typeof(grid)===\'undefined\' || grid===null\n       || grid.length===0 || grid[0].length===0){\n        return -1;\n    }\n    \n    let TARGET = null;\n    let startBlk = null;\n    let startPer = null;\n    const DIR = [\n        [0,1], [1,0], [0,-1], [-1,0]\n    ];\n    \n    for(let i = 0; i<grid.length; i++){\n        for(let j = 0; j<grid[0].length; j++){\n            if(grid[i][j]===\'S\'){\n                startPer = [i,j];\n                grid[i][j]=\'.\';\n            }\n            if(grid[i][j]===\'T\'){\n                TARGET = [i,j];\n            }\n            if(grid[i][j]===\'B\'){\n                startBlk = [i,j];\n                grid[i][j]=\'.\';\n            }\n        }\n    }\n    \n    let queue = new PriorityQueue((a,b)=>a.weight<b.weight);\n    let states = new Map();\n    queue.push({weight: manDist(startBlk), block: startBlk, character: startPer, move: 0});\n    while(!queue.isEmpty()){\n        let {weight,block,character,move} = queue.pop();\n        if(TARGET[0]===block[0] && TARGET[1]===block[1]){\n            return move;\n        }\n        let key = (block[0]*grid[0].length)+block[1];\n        let val = (character[0]*grid[0].length)+character[1];\n        if(!states.has(key)){\n            states.set(key,new Set());\n        }\n        states.get(key).add(val);\n        DIR.forEach(d=>{\n            let i = d[0]+character[0];\n            let j = d[1]+character[1];\n            let curV = (i*grid[0].length)+j;\n            if(validMove(i,j,block[0],block[1]) && !states.get(key).has(curV)){\n                queue.push({weight: manDist(block)+move, block: block, character: [i,j], move: move});\n            }\n        });\n        let pushDir = tryPush(character,block);\n        if(pushDir!==null){\n            let newBlk = [block[0]+pushDir[0],block[1]+pushDir[1]];\n            let newCha = [character[0]+pushDir[0],character[1]+pushDir[1]];\n            let nBK = (newBlk[0]*grid[0].length)+newBlk[1];\n            let nVal = (newCha[0]*grid[0].length)+newCha[1];\n            if(!states.has(nBK) || !states.get(nBK).has(nVal)){\n                queue.push({weight: manDist(newBlk)+(move+1), block: newBlk, character: newCha, move: move+1});  \n            }\n        }\n    }\n    \n    return -1;\n    \n    \n    function manDist(block){\n        let [x,y] = TARGET;\n        let [i,j] = block;\n        return Math.abs(x-i) + Math.abs(y-j);\n    }\n    function validMove(i,j,x=null,y=null){\n        if(i<0 || j<0 || i>=grid.length || \n           j>=grid[0].length){\n            return false;\n        }\n        if(((x!==null&&(i===x)) && (y!==null&&(j===y))) || grid[i][j]===\'#\'){\n            return false;\n        }\n        return true;\n    }\n    function tryPush(c,b){\n        let [i,j] = c;\n        let [x,y] = b;\n        for(let u = 0; u<DIR.length; u++){\n            let [v,w] = DIR[u];\n            if(((Math.abs(x-i)===1 && y===j) || (Math.abs(y-j)===1 && x===i)) && validMove(i+v,j+w) && validMove(x+v,y+w) && (i+v)===x && (j+w)===y){\n                return [v,w];\n            }\n        }\n        return null;\n    }\n};\n```
[]