การตรวจสอบคำที่ถูกต้องในเกม Boggle ด้วย JavaScript

ปัญหา

กระดาน Boggle (บ็อกเกิล) เป็นอาร์เรย์ 2 มิติของตัวอักษรเดี่ยว เช่น:

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

เราต้องเขียนฟังก์ชัน JavaScript ที่รับกระดาน Boggle และสตริง และตรวจสอบว่าสตริงนั้นเป็นคำเดาที่ถูกต้องในกระดาน Boggle หรือไม่ คำเดาที่ถูกต้องคือสตริงที่สามารถสร้างได้จากการเชื่อมเซลล์ติดกัน (แนวนอน แนวตั้ง หรือแนวทแยง) โดยไม่ใช้ซ้ำเซลล์ที่ใช้ไปแล้ว

เช่น ในกระดานข้างต้น "LINGO", และ "ILNBIA" จะเป็นคำเดาที่ถูกต้อง ส่วน "BUNGIE" และ "SINUS" จะไม่ถูกต้อง

ตัวอย่าง

โค้ดตัวอย่างดังนี้:

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));

คำอธิบายโค้ด

ขั้นตอนที่เราทำ:

• สแกนอาร์เรย์ 2D เพื่อหาตำแหน่งตัวอักษรแรกของคำ
• นำ { position, index } เข้า queue, ขณะ queue ไม่ว่าง นำ object แรกออก
• ตรวจสอบ 8 ทิศทาง หากตัวอักษรในเซลล์ตรงกับตัวอักษรในคำ และเซลล์ยังไม่ถูกใช้ ให้อัปเดต {position, index} และเข้า queue มิฉะนั้นทิ้ง object หยุดเมื่อเจอคำหรือหมดทาง

ผลลัพธ์

true