Skip to content

Instantly share code, notes, and snippets.

@WilfredTA
Created February 26, 2019 06:20
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save WilfredTA/d9872420c9686337d40e84cbe0a760ca to your computer and use it in GitHub Desktop.
Save WilfredTA/d9872420c9686337d40e84cbe0a760ca to your computer and use it in GitHub Desktop.
Word search solution with unique cell and adjacent cell branching logic
var exist = function(board, word) {
var seen = [];
var targetCharIdx = 0;
var result = {
found: false
};
for (var i = 0; i < board.length; i++) {
for (var j = 0; j < board[0].length; j++) {
if (board[i][j] === word[targetCharIdx]) {
seen.push([i,j]);
targetCharIdx++;
existHelper(board, word, seen, result, targetCharIdx, [i,j])
targetCharIdx--;
seen.pop();
}
}
}
return result.found;
};
var existHelper = function(board, word, seen, result, targetCharIdx, currCell) {
if (word.length === seen.length) {
if (wordMatches(word, seen, board)) {
result.found = true;
}
}
var adjCells = adjacentCells(currCell, board);
for (var i = 0; i < adjCells.length; i++) {
var adjCell = adjCells[i];
if (!alreadySeen(adjCell, seen)) {
seen.push(adjCell);
existHelper(board, word, seen, result, targetCharIdx, adjCell)
seen.pop(adjCell)
}
}
};
function adjacentCells(currCell, board) {
return [[currCell[0] + 1, currCell[1]],
[currCell[0] - 1, currCell[1]],
[currCell[0], currCell[1] + 1],
[currCell[0], currCell[1] - 1]
]
.filter(function(cell) {
return (cell[0] >= 0 && cell[1] >= 0) &&
(cell[0] < board.length && cell[1] < board[0].length)
});
};
function alreadySeen(currCell, seen) {
var lookup = '';
var currCell = currCell[0].toString() + currCell[1].toString();
for (var i = 0; i < seen.length; i++) {
lookup = seen[i][0].toString() + seen[i][1].toString();
if (lookup === currCell) {
return true;
}
}
return false;
}
var wordMatches = function(word, seen, board) {
var constructedWord = '';
seen.forEach(function(coordinate) {
constructedWord += board[coordinate[0]][coordinate[1]];
});
return constructedWord === word;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment