boggle.ts

const fs = require("fs");

const words = fs.readFileSync('/usr/share/dict/words', 'utf-8').split("\n") as string[];

const root = {
  children: {},
  word: false,
};

function addWord(parent: any, word: any) {
  const letter = word.substr(0, 1);
  const rest = word.substr(1, word.length);

  if (!parent.children[letter]) {
    parent.children[letter] = {
      children: {},
      word: rest === '',
    }
  }

  if (rest !== '') {
    addWord(parent.children[letter], rest);
  } else {
    parent.children[letter].word = true;
  }
}

function getTrieNode(prefix: string) {
  let current = root;

  for (let i = 0; i < prefix.length; i++) {
    const char = prefix[i];

    if (!current.children[char]) {
      return false;
    }

    current = current.children[char];
  }

  return current;
}

words.forEach((word) => addWord(root, word));

const board = [
  'r i m q'.split(' '),
  'l y t e'.split(' '),
  'l e u e'.split(' '),
  'f a k i'.split(' '),
]

const moves = [
  [-1, -1],
  [0, -1],
  [1, -1],
  [-1, 0],
  [1, 0],
  [-1, 1],
  [0, 1],
  [1, 1],
]

const found = new Set();

function checkWord(row: number, col: number, word = '', seen: Record<string, boolean> = {}) {
  word += board[row][col];

  const node = getTrieNode(word);

  if (!node) {
    return;
  }

  if (node.word) {
    found.add(word);
  }

  seen[`${row}${col}`] = true,

  moves.forEach(([dcol, drow]) => {
    const movecol = col + dcol;
    const moverow = row + drow;

    if (movecol < 0 || moverow < 0 || movecol >= board[0].length || moverow >= board.length || seen[`${moverow}${movecol}`]) {
      return;
    }

    checkWord(moverow, movecol, word, {...seen});
  });
}

for (let row = 0; row < board.length; row++) {
  for (let col = 0; col < board[0].length; col++) {
    checkWord(row, col);
  }
}
console.log(found)