Daily Challenge #92 - Boggle Board

#challenge

Write a function that determines whether a string is a valid guess in a Boggle board, as per the rules of Boggle. A Boggle board is a 2D array of individual characters, e.g.:

[ ["I","L","A","W"], ["B","N","G","E"], ["I","U","A","O"], ["A","S","R","L"] ]

Valid guesses are strings that can be formed by connecting adjacent cells (horizontally, vertically, or diagonally) without re-using any previously used cells.

For example, in the above board BINGO, LINGO, and ILNBIA would all be valid guesses, while BUNGIE, BINS, and SINUS would not.

Your function should take two arguments (a 2D array and a string) and return true or false depending on whether the string is found in the array as per Boggle rules.

Test cases will provide various array and string sizes (squared arrays up to 150x150 and strings up to 150 uppercase letters). You do not have to check whether the string is a real word or not, only if it's a valid guess.

This challenge comes from 747823 on CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Top comments (2)

erezwanderman • Oct 16 '19

TypeScript:

const isValid = (board: string[][], guess: string) => {
  const checkGuess = (biggerBoard: string[][], guess: string, coords: [number, number]) => {
    if (guess === '') return true;
    if (biggerBoard[coords[0]][coords[1]] !== guess[0]) return false;

    const temp = biggerBoard[coords[0]][coords[1]];
    biggerBoard[coords[0]][coords[1]] = '*';
    const answer = [
        [coords[0] - 1, coords[1] - 1],
        [coords[0] - 1, coords[1]    ],
        [coords[0] - 1, coords[1] + 1],
        [coords[0]    , coords[1] - 1],

        [coords[0]    , coords[1] + 1],
        [coords[0] + 1, coords[1] - 1],
        [coords[0] + 1, coords[1]    ],
        [coords[0] + 1, coords[1] + 1]
    ].some(([r, c]) => checkGuess(biggerBoard, guess.substring(1), [r, c]));
    biggerBoard[coords[0]][coords[1]] = temp;
    return answer;
  };
  // Create a padded array
  const biggerBoard = Array(board.length + 2);
  biggerBoard[0] = biggerBoard[board.length + 1] = Array(board[0].length + 2).fill(undefined);
  board.forEach((row, i) => biggerBoard[i + 1] = [undefined, ...row, undefined]);

  const coords = [].concat(...biggerBoard.map((row, r) => row.map((val, c) => [r, c])));

  return coords.some(([r, c]) => checkGuess(biggerBoard, guess, [r, c]));
}

const testBoard = [
  ["I","L","A","W"],
  ["B","N","G","E"],
  ["I","U","A","O"],
  ["A","S","R","L"]
];

const testWords = ['BINGO', 'LINGO', 'ILNBIA', 'BUNGIE', 'BINS', 'SINUS'];
for (const word of testWords) {
  console.log(word, isValid(testBoard, word));
}

erezwanderman • Oct 16 '19

Shorter ver:

const isValid = (board: string[][], guess: string, prevCoords?: [number, number]) => {
  if (guess === '') return true;
  if (!prevCoords) {
    const coords = [].concat(...board.map((row, r) => row.map((val, c) => [r, c])));
    return coords.some(c => isValid(board, guess, c));
  } else {
    if (board[prevCoords[0]][prevCoords[1]] !== guess[0]) return false;

    const temp = board[prevCoords[0]][prevCoords[1]];
    board[prevCoords[0]][prevCoords[1]] = '*';
    const answer = [
        [prevCoords[0] - 1, prevCoords[1] - 1],
        [prevCoords[0] - 1, prevCoords[1]    ],
        [prevCoords[0] - 1, prevCoords[1] + 1],
        [prevCoords[0]    , prevCoords[1] - 1],

        [prevCoords[0]    , prevCoords[1] + 1],
        [prevCoords[0] + 1, prevCoords[1] - 1],
        [prevCoords[0] + 1, prevCoords[1]    ],
        [prevCoords[0] + 1, prevCoords[1] + 1]
    ]
    .filter(([r, c]) => r >= 0 && c >= 0 && r < board.length && c < board[0].length)
    .some(([r, c]) => isValid(board, guess.substring(1), [r, c]));
    board[prevCoords[0]][prevCoords[1]] = temp;
    return answer;
  }
}

const testBoard = [
  ["I","L","A","W"],
  ["B","N","G","E"],
  ["I","U","A","O"],
  ["A","S","R","L"]
];

const testWords = ['BINGO', 'LINGO', 'ILNBIA', 'BUNGIE', 'BINS', 'SINUS'];
for (const word of testWords) {
  console.log(word, isValid(testBoard, word));
}

DEV Community

Daily Challenge #92 - Boggle Board

Top comments (2)

Read next

Threat Modeling in Architecture

The Rewrite Trap: A Programmer's Survival Guide

Day 38 Journal

Testing