Shortest Path to Get All Keys in JavaScript

Question

I build the Shortest Path to Get All Keys algorithm in JavaScript. It's working properly, but with a really bad performance.

The problem:

You are given an m x n grid grid where:

'.' is an empty cell. '#' is a wall. '@' is the starting point. Lowercase letters represent keys. Uppercase letters represent locks. You start at the starting point and one move consists of walking one space in one of the four cardinal directions. You cannot walk outside the grid, or walk into a wall.

If you walk over a key, you can pick it up and you cannot walk over a lock unless you have its corresponding key.

For some 1 <= k <= 6, there is exactly one lowercase and one uppercase letter of the first k letters of the English alphabet in the grid. This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.

Return the lowest number of moves to acquire all keys. If it is impossible, return -1.

Examples:

Input: grid = ["@.a.#","###.#","b.A.B"]
Output: 8
Explanation: Note that the goal is to obtain all the keys not to open all the locks.

Input: grid = ["@..aA","..B#.","....b"]
Output: 6

Input: grid = ["@Aa"]
Output: -1

I implemented a BFS where I keep the current state (path) in which position, so it allows me to go back to a position where I had been before, but now with a different state.

var shortestPathAllKeys = function(grid) {
 const directions = [ [0,1], [0,-1], [1,0], [-1,0] ];
 const keys = new Set(['a', 'b', 'c', 'd', 'e', 'f']);
 const locks = new Set(['A', 'B', 'C', 'D', 'E', 'F']);
 const lockToKey = {
 'A': 'a', 'B': 'b', 'C': 'c', 'D': 'd', 'E': 'e', "F": 'f'
 };
 let totalKeys = 0;
 let queue = [];
 
 for(let i=0; i<grid.length; i++) {
 for(let j=0; j<grid[i].length; j++) {
 if(keys.has(grid[i][j]))
 totalKeys++;
 else if(grid[i][j] === '@') {
 const path = `@`;
 queue.push([[i,j], path, new Set(), 0]);
 }
 }
 }
 
 const copyKeysSet = (set) => {
 let newSet = new Set();
 for(const value of set)
 newSet.add(value);
 return newSet;
 }
 
 let visited = new Set();
 while(queue.length > 0) {
 const [pos, curPath, curKeys, curSteps] = queue.shift();
 if(curKeys.size === totalKeys) {
 return curSteps;
 }
 const buildPath = `${pos[0]},${pos[1]},${curPath}`;
 if(!visited.has(buildPath)) {
 visited.add(buildPath);
 for(const d of directions) {
 const row = pos[0]+d[0];
 const col = pos[1]+d[1];
 if(row >= 0 && row < grid.length && col >=0 && col < grid[row].length) {
 const c = grid[row][col];
 if(c === '#') continue;
 if(locks.has(c) && !curKeys.has(lockToKey[c])) continue;
 if(keys.has(c)) {
 curKeys.add(c);
 const newPath = `${curPath},${c}`;
 queue.push([[row, col], newPath, copyKeysSet(curKeys), curSteps+1]);
 } else {
 const newPath = `${curPath}`;
 queue.push([[row, col], newPath, copyKeysSet(curKeys), curSteps+1]);
 }
 }
 }
 }
 }
 
 return -1;
};

It works fine for the test cases examples. However, if I try the input ["@abcdeABCDEFf"] it takes forever to run. Any idea how I could improve the performance?

Thank you.

• Blindman67: Your code does not work, The code either, ends up in an endless loop (Im guessing as I just killed the page rather than waited) or returns a incorrect distance,. example ["@cbaABC"] should return 13 but your code returns 3 and ["@abABcC"] returns 5, should be 7.
• myTest532 myTest532: @Blindman67 why should return 13? Move 3 times to the right and grab all 3 keys
• myTest532 myTest532: ["@abABcC"] Same. Move 5 times to the right and get all keys.
• Blindman67: My apologies I miss understood the requirement of the task that the doors do not need to be moved over, only the keys, sorry, However does the example where the key is blocked by a looked door ["@abcdeABCDEFf"] return a value -1?
• myTest532 myTest532: @Blindman67 no worries. Yes, it's a confusing problem. Yes in the example ["@abcdeABCDEFf"] it returns -1.

Answer 1

Style

• Always delimit code blocks. eg if (foo) bar() should be if (foo) { bar() }

• Avoid using continue

• Spaces between operators and after commas. Eg pos[0]+d[0] should be pos[0] + d[0] and [0,1] is [0, 1]

• Use constants for variables that do not change.

• Try to use arrays only to store items that represent the same thing, and use object to store sets of unique items.

  For example you create the queue array item as an array of 4 items queue.push([[i,j], path, new Set(), 0]);

  This should be an object queue.push({pos: {x: j, y: i}, path, keys: new Set(), steps: 0})

• Keep code compact, using short form style when possible.

  For example when copying a set you have the function (rewritten as...)

   const copyKeysSet = set => {
   const newSet = new Set();
   for (const value of set) {
   newSet.add(value);
   }
   return newSet;
   }
  

  however this can be written as

   const copyKeysSet = set => new Set([...set])
  

• Avoid duplication. When you add to the queue you have the same line twice...

   queue.push([[row, col], newPath, copyKeysSet(curKeys), curSteps+1]);
  

  With some rearranging that line need only be written once, one could thus also negate the need to call copyKeySet amd using an object

   queue.push({pos: {x: col, y: row}, path: newPath, keys: new Set([...curKeys]), steps: curSteps + 1});
  

Bug

Testing your code I still find inconsistencies

The problem, collect all keys using the shortest path. Return the number of steps needed to find all keys.

Paths steps can only be one of 4 directions, up down left right.

Lowercase characters are keys, uppercase are doors. Doors can not be stepped over unless you have the corresponding key.

Bug 1

When given the String (Example A)

const map = [
 "@...b",
 "....B",
 "..a.A"
];

Your function returns 6, yet the shortest path I can manually find is 8 steps

"@.678" "@1234" "@1278"
"1.5.B" "..765" "..36B"
"234.A" "..8.A" "..45A"

Yet for...

const map = [
 "@....",
 ".....",
 "..a.A"
];

...you return 4

I will assume your code is missing something simple as it works more often than not.

Bug 2

There are a few cases where the function does not return (even after very long waits). As I don't think your solution is worth further refinement (too computational complex) I have not tracked down why this happens.

Performance

In terms of speed and memory use your function is very poor.

Estimating complexity.

Using \$n\$ as cells times keys. For example input A we get \$n = 5 * 3 * 2 = 30\$ 5 columns, 3 rows, and 2 keys

I will play it safe and say the its \$O(n^{log(n)})\$ in both time and space complexity. This is very bad and makes the solution only usable for very small grids.

Improving performance

Time and space complexity is not a measure of performance as some simple changes to your code that does not change the complexity can improve performance by a order of magnitude.

The most basic performance improvements can be found...

• JavaScript string are slow. Rather than manipulate strings, convert the input grid to character codes as JavaScript handles number much quicker than strings.

  grid.map(line => [...line].map((c, i) => line.charCodeAt(i)));
  

• Use flat arrays to reduce indexing overhead.

• JavaScript's Set is just a simple hash map. However the hashing function is a general function and are rather slow. The values you are hashing eg ${y},${x},${key} can easily be converted to unique sequential values x + (y * gridWidth) + (key * gridWidth * gridHeight) and used to quickly index into a pre allocated array. This can be many times quicker than using Set

  You also use sets to check for keys eg the letters "a","b","c","d"... However if you use character codes you can test for a key as cell[idx] >= 97 (is lowercase key) you can convert to a key index by subtracting 97. To get the Door for a key just flip the 6th bit doorCC = cell[idx] & 0b1011111 for "a" charCode 97 doorCC is 65 "A"

  As @, ., # are all under character code 65 you can test for a door or key with just if (grid[idx] >= 65)to check if its a key check the 6th bit if (grid[idx] & 0b100000) { /* is key */ } else { /* is door */ }

Alternative algorithm

You can use Dijktra's algorithm to find the shortest path between pairs of keys and then recursive select the shortest path.

This answer contains an implementation of Dijktra's algorithm

Thus if we have 3 keys find the distance from "@" to "a", "b", "c". If doors block the path some keys will not be found. Assuming the first key can be found repeat the search but open the door for "A" finding the path from "a" to "b", "c" repeat until you have found the distance between all pairs of keys.

As you do this you will be in a state where all keys are found. You will have a distance traveled, you can then just check that against the lowest distance, and if lower that is the current shortest distance.

Example

A full solution is too long, so I have given a sub set solution...

• It does not handle maps that do not have a solution.

• It expected that maps are correctly formed. Keys are in order, IE if there is a key c then there must be keys a, b. For each key there must be a door

• The maps are rectangular, thus the length of grid H and the length of the first element W matches the number of cells cells === W * H

The example algorithm is much more complex however the 2 orders improvement in performance is worth the effort, and has lots of room for optimization.

Hint the shortest paths from each key to all other keys is often duplicated. Key a to b is the same as b to a, if there is no door between the two. This is ignored in the example

The complexity

• Space is \$O(n)\$ and
• Time is \$O(mn^2)\$ where \$m\$ is number of cells and \$n\$ is number of keys. (This is an estimate that resembles a guess)

Performance

Excluding visuals The example solves a 13 by 13 grid with 3 keys in 47μs compared to the 64,610μs your function requires to solve the same map.

_{μs is 1/1,000,000th second}

Snippet

I have added visual representation to the algorithm that extracts the best paths as arrays of cell indexes. However this is not required to get the length of the shortest path.

To simplify the need to check for the map edge I add a wall around the grid. This means that at no time do I need to use coordinate pairs when searching for a path.

 const data = [
 "@....A.......",
 ".....#######.",
 ".....#.....#.",
 ".....#...c.#.",
 ".....B.....#.",
 ".....#######.",
 ".....#.......",
 ".....#.......",
 ".....#.......",
 ".....#.......",
 ".....#.......",
 ".....#.......",
 "a....#b...C..",
];
setTimeout(() => console.log("Shortest path: " + shortestPathAllKeys(data)));
function shortestPathAllKeys(grid) {
 const CHAR_CODE = c => c.charCodeAt(0);
 const Door = (cc, idx) => cc & 32 ? {key: idx, loc: undefined} : {key: undefined, loc: idx, distTo: undefined};
 const Path = (loc, doorIdx, dist) => ({loc, dist, doorIdx, paths: []});
 const MAX_DOORS = 26;
 const KEY_MASK = 0b11111;
 const CC_START = 64; // or use CHAR_CODE("@");
 const CC_WALL = 35; // CHAR_CODE("#");
 const CC_OPEN = 46; // CHAR_CODE(".");
 const CC_LOCKED = 65; // CHAR_CODE("A");
 const CC_KEY = 65 | 32; // CHAR_CODE("a");
 const W = grid[0].length + 2, H = grid.length + 2;
 const boundWall = ("").padStart(W + 1 , "#");
 var startIdx, minDist = Infinity, keysFound, maxDoors = 0, doors = new Array(MAX_DOORS).fill();
 const map = flattenMap(grid);
 const DOOR_COUNT = doors.length;
 if (DOOR_COUNT === 0) { return 0 }
 const mapSize = map.length;
 const workMap = new Array(mapSize).fill(0);
 const foundPaths = [], displayPaths = []; // only for visuals
 
 showMap();
 findPaths(Path(startIdx, -1, 0));
 {
 let i = 0;
 for (const p of displayPaths) { drawPath(p, W, DOOR_COUNT - 1 - i++) }
 }
 return minDist < Infinity ? minDist : -1;
 function showMap() {
 var i = 0;
 const showMap = [...map];
 for (const d of doors) {
 showMap[d.loc] = i + 65;
 showMap[d.key] = i + 97;
 i++;
 }
 drawMap(showMap, W, H);
 }
 function flattenMap(grid) {
 var i = 0;
 grid = boundWall + grid.join("##") + boundWall;
 const map = [];
 while (i < grid.length) {
 const cc = grid.charCodeAt(i);
 if (cc === CC_START) {
 startIdx = i;
 map.push(CC_OPEN);
 } else if (cc >= CC_LOCKED) {
 const doorArrayIdx = (cc & KEY_MASK) - 1;
 maxDoors = Math.max(maxDoors, doorArrayIdx + 1);
 const door = doors[doorArrayIdx];
 map.push(cc & 32 ? cc : CC_WALL);
 door ? (cc & 32 ? door.key = i : door.loc = i) : doors[doorArrayIdx] = Door(cc, i);
 } else { map.push(cc) }
 i++;
 }
 doors.length = maxDoors;
 return map;
 }
 function pathsDistFrom(fromIdx) { // modified Dijktra's algorithm
 const USED = 0x0F000000;
 const DIST_MASK = 0xFFFFFF;
 const wM = workMap, m = map;
 var stackIdx = 0;
 const stack = [fromIdx]; // stack is actualy a queue (too late now its done to fix name in CR snippet)
 const paths = [];
 wM.fill(0);
 wM[fromIdx] = USED;
 const distToStart = idx => {
 const checkHomeStep = (next) => {
 const nVal = wM[next];
 if (nVal >= DIST_MASK) {
 const dist = nVal & DIST_MASK;
 if (dist < mDist) {
 mDist = dist;
 bestIdx = next;
 return next;
 }
 }
 }
 var mDist, dist = 0, bestIdx;
 const pathSteps = [idx]; // for visuals 
 while (idx !== fromIdx) {
 const distFromHome = Math.abs(idx - fromIdx);
 if (distFromHome === W || distFromHome === 1) { break }
 const up = idx - W, down = idx + W, left = idx - 1, right = idx + 1;
 mDist = wM[idx] & DIST_MASK;
 bestIdx = idx;
 checkHomeStep(up);
 checkHomeStep(down);
 checkHomeStep(left);
 checkHomeStep(right);
 idx = bestIdx
 pathSteps.push(idx); // for visuals 
 dist += 1;
 }
 pathSteps.push(fromIdx);
 foundPaths.push(pathSteps); // for visuals 
 return dist;
 }
 const nextCell = (idx, dist) => {
 const locVal = m[idx];
 if (wM[idx] === 0 && locVal !== CC_WALL) {
 if (locVal >= CC_KEY) { paths.push(Path(idx, (locVal - 97))) }
 if (locVal !== CC_WALL) {
 wM[idx] = USED + dist + 1;
 stack.push(idx);
 }
 }
 }
 while (stackIdx < stack.length) {
 const idx = stack[stackIdx++];
 const dist = wM[idx] & DIST_MASK;
 nextCell(idx - W, dist); // up
 nextCell(idx + W, dist); // down
 nextCell(idx - 1, dist); // left
 nextCell(idx + 1, dist); // right
 }
 foundPaths.length = 0; // for visuals 
 for (const p of paths) { p.dist = distToStart(p.loc) + 1 }
 return paths;
 }
 function findPaths(path, dist = 0, keysFound = 0) {
 var i = 0, foundShort = false, toFirstKey; // for visuals 
 const opensDoor = path.doorIdx > -1 ? doors[path.doorIdx] : undefined;
 opensDoor && (map[opensDoor.key] = map[opensDoor.loc] = CC_OPEN);
 keysFound += 1;
 path.paths.push(...pathsDistFrom(path.loc));
 if (!opensDoor) { toFirstKey = foundPaths[0] } // for visuals 
 const dPaths = [...foundPaths]; // for visuals 
 if (path.paths.length) {
 if (keysFound === DOOR_COUNT ) {
 for (const p of path.paths) { 
 if (minDist > dist + p.dist) { // for visuals 
 displayPaths.length = 0; // for visuals 
 displayPaths[0] = foundPaths[i]; // for visuals 
 foundShort = true; // for visuals 
 }
 minDist = Math.min(minDist, dist + p.dist);
 i++; // for visuals 
 }
 } else { 
 for (const p of path.paths) { 
 if (findPaths(p, dist + p.dist, keysFound)) { // for visuals 
 displayPaths.push(dPaths[i]); // for visuals 
 }
 i++; // for visuals 
 }
 }
 }
 opensDoor && (map[opensDoor.key] = path.doorIdx + 97, map[opensDoor.loc] = CC_WALL);
 toFirstKey && displayPaths.push(toFirstKey); // for visuals 
 return foundShort;
 }
 
}
const ctx = canvas.getContext("2d");
const S = 30; // cell pixel size
const cols = ["red","green","blue","yellow","cyan","pink","brown","purple"];
function drawArrow(w, idx1, idx2) {
 ctx.lineWidth = 2;
 const x1 = idx1 % w;
 const y1 = idx1 / w | 0;
 const x2 = idx2 % w;
 const y2 = idx2 / w | 0;
 ctx.setTransform(x2 - x1, y2 - y1, -(y2 - y1), x2 - x1, (x2 + 0.5) * S, (y2 + 0.5) * S);
 ctx.beginPath();
 ctx.lineTo(-S * 0.2, S / 4);
 ctx.lineTo(S * 0.5, S / 4);
 ctx.moveTo(-S * 0, S / 4 - S * 0.2);
 ctx.lineTo(-S * 0.2, S / 4);
 ctx.lineTo(-S * 0, S / 4 + S * 0.2);
 ctx.stroke();
}
function drawPath(path, w, cidx) {
 ctx.strokeStyle = cols[cidx % cols.length];
 var i = 0;
 var pIdx = path[i++];
 while (i < path.length) {
 const idx = path[i++];
 drawArrow(w, pIdx, idx);
 pIdx = idx;
 }
}
function drawMap(map, w, h) {
 canvas.width = w * S;
 canvas.height = h * S;
 ctx.font = S + "px Arial black";
 ctx.textAlign = "center";
 ctx.textBaseline = "middle";
 var x, y = 0;
 ctx.strokeRect(0,0, w * S, h * S)
 while (y < h) {
 x = 0;
 while (x < w) {
 const idx = y * w + x;
 if (map[idx] === 35) {
 ctx.fillStyle = "black";
 ctx.fillRect(x * S, y * S, S, S);
 } else if (map[idx] >= 65) {
 ctx.fillStyle = cols[((map[idx] & 0b11111) - 1) % 4];
 if ((map[idx] & 32) === 0) {
 ctx.fillRect(x * S, y * S, S, S);
 } else {
 ctx.fillText("K", (x + 0.5) * S, (y + 0.6) * S);
 }
 } else {
 ctx.strokeRect(x * S, y * S, S, S)
 }
 x++;
 }
 y++;
 }
 ctx.setTransform(1,0,0,1,0,0);
 
}

<canvas id="canvas"></canvas>