Xác thực một từ boggle bằng JavaScript

Vấn đề

Bảng Boggle là một mảng 2D gồm các ký tự riêng lẻ, ví dụ:-

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

Chúng tôi được yêu cầu viết một hàm JavaScript sử dụng bảng boggle và một chuỗi và kiểm tra xem chuỗi đó có phải là một dự đoán hợp lệ trong bảng boggle hay không. theo đường chéo) mà không sử dụng lại bất kỳ ô nào đã sử dụng trước đó.

Ví dụ:trong bảng ở trên, "LINGO" và "ILNBIA" sẽ là các dự đoán hợp lệ, trong khi "BUNGIE" và "SINUS" thì không.

Ví dụ

Sau đây là mã -

const board = [
   ["I","L","A","W"],
   ["B","N","G","E"],
   ["I","U","A","O"],
   ["A","S","R","L"]
];
const guess = 'BINGO';
const checkWord = (board = [], guess = '') => {
   const numRows = board.length;
   const numCols = board[0].length;
   let queue = board.reduce((acc, row, i) => {
      row.forEach((x, j) => {
         if (x === guess[0]) {
            acc.push ( { pos: {r: i, c: j} , nextIndex: 1, path: [numCols*i + j ] } );
         }
      });
      return acc;
   }, []);
   let exploreWord = (obj, queue) => {
      let allMoves = [ {r: obj.pos.r - 1, c: obj.pos.c },
      {r: obj.pos.r + 1, c: obj.pos.c },
      {r: obj.pos.r, c: obj.pos.c - 1 },
      {r: obj.pos.r, c: obj.pos.c + 1 },
      {r: obj.pos.r - 1, c: obj.pos.c - 1 },
      {r: obj.pos.r - 1, c: obj.pos.c + 1 },
      {r: obj.pos.r + 1, c: obj.pos.c - 1 },
      {r: obj.pos.r + 1, c: obj.pos.c + 1 }];
      allMoves.forEach((o) => {
         let index = numCols * o.r + o.c;
         if (o.r >= 0 && o.r < numRows && o.c >= 0 && o.c < numCols) {
            if (board[o.r][o.c] === guess[obj.nextIndex] && !obj.path.includes(index)) {
               let cloneObj = JSON.parse(JSON.stringify(obj));
               cloneObj.pos = { r: o.r, c: o.c };
               cloneObj.nextIndex += 1;
               cloneObj.path.push(index);
               queue.push(cloneObj);
            }
         }
      });
   };
   while (queue.length > 0) {
      let obj = queue.shift();
      if (obj.nextIndex === guess.length) {
         return true;
      }
      exploreWord(obj, queue);
   }
   return false;
};
console.log(checkWord(board, guess));

Giải thích mã

Các bước chúng tôi đã thực hiện là -

• Chúng tôi quét mảng 2d để tìm sự xuất hiện của chữ cái đầu tiên

• Sau đó, chúng tôi đẩy {vị trí, chỉ mục} vào hàng đợi, trong khi hàng đợi không trống, chúng tôi bật đối tượng đầu tiên ra

• Sau đó, chúng tôi tìm kiếm tất cả các hướng. nếu chữ cái trong ô khớp với chữ cái trong word và ô không được sử dụng lại, chúng tôi cập nhật {position, index} và nối vào hàng đợi khác, chúng tôi loại bỏ đối tượng và chúng tôi dừng khi tìm thấy kết quả khớp hoặc tất cả đều không khớp.

Đầu ra

true