Last active
February 1, 2024 11:02
-
-
Save krishnathota/3eb0cfb2831fdeae9bfd946e3b936afd to your computer and use it in GitHub Desktop.
Word Search Puzzle - Position finder
This file contains 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
//* Function to solve a word search puzzle | |
function wordSearch(board, words) { | |
board = board.map((row) => row.split('')); | |
//* Define the possible directions to move on the board | |
const directions = [ | |
[-1, 0, '↑'], // up | |
[1, 0, '↓'], // down | |
[0, -1, '←'], // left | |
[0, 1, '→'], // right | |
]; | |
const results = {}; | |
//* Define a helper function to search for a word starting at a specific position | |
function search(x, y, word, index) { | |
//* If we have reached the end of the word, return true | |
if (index === word.length) return true; | |
//* If the current position is out of bounds or the character does not match, return false | |
if (x < 0 || y < 0 || x >= board.length || y >= board[0].length || board[x][y].toLowerCase() !== word[index]) | |
return false; | |
//* Mark the current position as visited | |
board[x][y] = '*'; | |
//* Try each direction from the current position | |
for (let [dx, dy, direction] of directions) { | |
//* If we find the word in this direction, return the direction and the current position | |
if (search(x + dx, y + dy, word, index + 1)) { | |
return { direction, x, y }; | |
} | |
} | |
//* If we didn't find the word, backtrack by resetting the current position and return false | |
board[x][y] = word[index]; | |
return false; | |
} | |
//* For each word in the list | |
words.forEach((word) => { | |
//* Convert the word to lower case to make a case insensitive search | |
word = word.toLowerCase(); | |
//* Try to find the word starting at each position on the board | |
const result = board.some((row, i) => | |
row.some((_, j) => { | |
//* If we find the word, store the result and return true | |
const found = search(i, j, word, 0); | |
if (found) results[word] = found; | |
return found; | |
}) | |
); | |
//* If we didn't find the word, store false in the results | |
if (!result) results[word] = false; | |
}); | |
return results; | |
} | |
const board = [ | |
'ROFENTEEDSREMELSLRVRGTMNAV', | |
'DBVCSHTSOXRHOTWNELITRMOTYB', | |
'RESDRIVINGLICENCEMGTMNAVIL', | |
'TDPTDODDSLRCOSLSNCQWAHEAOT', | |
'UREVERSEHORNBOVERLOADINGFF', | |
'VEERECXVIHAHAITLOPVCSHDNER', | |
'AFDOXRTIAITZEDSRSQGOSLOWND', | |
'SPLSTUSEATBELTQDAHEAFENLTB', | |
'PEISALQWMELBTYGEDSRSVIOIEV', | |
'OAMGLSPMOTORVEHICLEACHTTEC', | |
'ROITAVIIIHAAEEDSREMFSATRDS', | |
'OSTMNCHREAFCQCRUSHHELMETSH', | |
'ATBEESARWNERVCSHTDODFEXIRT', | |
'DEVICHHOMGTOIHAHAITIELTSED', | |
'NECHHTARHITSEAFEKSOSKIASMO', | |
'ADSAAADICROSSWITHCAUTIONEED', | |
'USHHNOTLQHNIRNAVNAFANEDILC', | |
'ERTAGDLSKUFNBOFEOHENADDHSS', | |
'FEDIEYDUINEGLTFRAAKCUSRALO', | |
'PMOTKQTTRAFFICRULESEERIHRN', | |
'EEDLIRIUPORONRVGCAHAFEVAVI', | |
'UBFQULTREAOSDIEROADSAFETYL', | |
'URBSHUVNELSLSVRBHTFRDBVCSH', | |
'WOVERTAKINGFPKSOOTISSEIHAH', | |
'EDSREMELSLREOITRLECEPLEAFE', | |
'CSHTDODCSONTTNAVGXRHOTWNEL', | |
]; | |
console.log(wordSearch(board, ['OVER', 'LANE', 'REVO', 'ATSR', 'OLTI', 'SEAT', 'UNKNOWN', 'DRIVING'])); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Output: