Skip to content

Instantly share code, notes, and snippets.

@supertinou
Created January 26, 2023 04:58
Show Gist options
  • Save supertinou/08e324e27e58efa874ad4abb62c1a905 to your computer and use it in GitHub Desktop.
Save supertinou/08e324e27e58efa874ad4abb62c1a905 to your computer and use it in GitHub Desktop.
function getNbs(i,j, board){
let coords = []
for (let ii = i-1; ii<= i+1; ii++){
for (let jj = j-1; jj<= j+1; jj++){
const inbound = ii >= 0 && ii < board.length && jj >= 0 && jj < board[0].length
if (inbound){
coords.push([ii, jj])
}
}
}
return coords
}
function boggle(board, word){
if (word.length === 0) return false
const firstLetter = word[0]
let visited = Array.from({ length: board.length}, e => Array.from({ length: board[0].length }, e => false ))
for (let i = 0; i< board.length; i++){
for(let j=0; j< board[i].length;j++){
const letter = board[i][j]
if (letter === firstLetter){
console.log("Letter:", [i,j])
if (dfs([i,j], word, visited)){
return true
}
}
}
}
function dfs(letterCoordinate, word, visited){
console.log(visited)
let foundWord = false
function helper(letterCoordinate, word, index){
const [i,j] = letterCoordinate
if (foundWord){
return
}
if (index === word.length -1 ){
console.log('index === word.length')
foundWord = true
return
}
console.log({letter: board[i][j], index})
visited[i][j] = true
const nbs = getNbs(i,j, board)
const idealNeighborLetter = word[index+1]
for (let neighbor of nbs){
const [nI,nJ] = neighbor
const letterNeighbor = board[nI][nJ]
const neighborVisited = visited[nI][nJ]
if (!neighborVisited && letterNeighbor === idealNeighborLetter){
console.log('letterNeighbor', letterNeighbor)
helper(neighbor, word, index+1)
}
}
visited[i][j] = false
}
helper(letterCoordinate, word, 0)
return foundWord
}
return false
}
const board = [['N', 'P', 'E', 'I', 'C', 'E'],
['S', 'O', 'U', 'P', 'R', 'U'],
['I', 'P', 'O', 'U', 'A', 'U'],
['I', 'B', 'S', 'Y', 'S', 'X']
]
boggle(board, "SOUPE")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment