Discussion on: Daily Challenge #79 - Connect Four

View post

A O( n² ) solution written in JavaScript. The board is represented as a matrix.

(Thank you @earlware for providing the test cases)

Update: Found some flaws in my code and since made some improvements to it. Tried to make it short and sweet but things didn't go as plan. Anyway, I did try to make everything more descriptive and easy to read :-)

Here it is, three more functions are being added to check for 4 consecutive matches in all directions (horizontal, vertical, and diagonal). It should still be O( n² )

const pieces_position_list = {
  yellowWins: [
    "B_Red",
    "A_Yellow",
    "C_Red",
    "B_Yellow",
    "C_Red",
    "C_Yellow",
    "D_Red",
    "E_Yellow",
    "D_Red",
    "E_Yellow",
    "D_Red",
    "D_Yellow"
  ],
  redWins: [
    "A_Red",
    "A_Yellow",
    "B_Red",
    "B_Yellow",
    "C_Red",
    "C_Yellow",
    "D_Red",
    "D_Yellow"
  ],
  draw: ["A_Red", "G_Yellow", "B_Red", "F_Yellow", "C_Red", "E_Yellow"]
};

const board_map = {
  A: 0,
  B: 1,
  C: 2,
  D: 3,
  E: 4,
  F: 5,
  G: 6
};

const checkDiagonal = (boardMatrix, currentRow, currentColumn) => {
  let trackAlign = 0;
  let count = 0;
  while (count < 3) {
    count++;
    // check up right
    if (
      boardMatrix[currentRow - count] &&
      boardMatrix[currentRow - count][currentColumn + count] &&
      boardMatrix[currentRow - count][currentColumn + count] ===
        boardMatrix[currentRow][currentColumn]
    ) {
      console.log(trackAlign);
      trackAlign++;
    }
    // check up left
    if (
      boardMatrix[currentRow - count] &&
      boardMatrix[currentRow - count][currentColumn - count] &&
      boardMatrix[currentRow - count][currentColumn - count] ===
        boardMatrix[currentRow][currentColumn]
    ) {
      trackAlign++;
    }
    // check down right
    if (
      boardMatrix[currentRow + count] &&
      boardMatrix[currentRow + count][currentColumn + count] &&
      boardMatrix[currentRow + count][currentColumn + count] ===
        boardMatrix[currentRow][currentColumn]
    ) {
      trackAlign++;
    }
    // check down left
    if (
      boardMatrix[currentRow + count] &&
      boardMatrix[currentRow + count][currentColumn - count] &&
      boardMatrix[currentRow + count][currentColumn - count] ===
        boardMatrix[currentRow][currentColumn]
    ) {
      trackAlign++;
    }
  }
  return trackAlign === 3;
};

const checkVertical = (boardMatrix, currentRow, currentColumn) => {
  let trackAlign = 0;
  let count = 0;
  while (count < 3) {
    // check down
    count++;
    if (
      boardMatrix[currentRow + count] &&
      boardMatrix[currentRow + count][currentColumn] ===
        boardMatrix[currentRow][currentColumn]
    ) {
      trackAlign++;
    }
  }
  return trackAlign === 3;
};

const checkHorizontal = (boardMatrix, currentRow, currentColumn) => {
  let trackAlign = 0;
  let count = 0;
  while (count < 3) {
    count++;
    // check left
    if (
      boardMatrix[currentRow] &&
      boardMatrix[currentRow][currentColumn - count] ===
        boardMatrix[currentRow][currentColumn]
    ) {
      trackAlign++;
    }
    // check right
    if (
      boardMatrix[currentRow] &&
      boardMatrix[currentRow][currentColumn + count] ===
        boardMatrix[currentRow][currentColumn]
    ) {
      trackAlign++;
    }
  }
  return trackAlign === 3;
};

const getCheckerColumn = checker => {
  return checker && checker.substring(0, checker.indexOf("_"));
};

const getCheckerColor = checker => {
  return checker && checker.substring(checker.indexOf("_") + 1, checker.length);
};

const connectFour = pieces_position_list => {
  const board = {
    matrix: [
      [0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0]
    ]
  };
  let i = 0;
  while (i < pieces_position_list.length) {
    const column = board_map[getCheckerColumn(pieces_position_list[i])];
    const color = getCheckerColor(pieces_position_list[i]);
    let j = 6;
    while (j > 0) {
      j--;
      if (board.matrix[j][column] === 0) {
        board.matrix[j][column] = color;
        if (
          checkDiagonal(board.matrix, j, column) ||
          checkHorizontal(board.matrix, j, column) ||
          checkVertical(board.matrix, j, column)
        ) {
          console.log("Result:");
          console.log(`The winner is ${color}!`);
          console.log(board.matrix);
          console.log("\n");
          return;
        }
        break;
      }
    }
    i++;
  }

  console.log("Is a draw !");
  console.log(board.matrix);
  console.log("\n");
};

//Tests
console.log("Test 1");
connectFour(pieces_position_list.yellowWins);
console.log("Test 2");
connectFour(pieces_position_list.redWins);
console.log("Test 3");
connectFour(pieces_position_list.draw);

Test 1
Result:
The winner is Yellow!
[ [ 0, 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 'Yellow', 0, 0, 0 ],
  [ 0, 0, 'Yellow', 'Red', 0, 0, 0 ],
  [ 0, 'Yellow', 'Red', 'Red', 'Yellow', 0, 0 ],
  [ 'Yellow', 'Red', 'Red', 'Red', 'Yellow', 0, 0 ] ]


Test 2
Result:
The winner is Red!
[ [ 0, 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0 ],
  [ 'Yellow', 'Yellow', 'Yellow', 0, 0, 0, 0 ],
  [ 'Red', 'Red', 'Red', 'Red', 0, 0, 0 ] ]


Test 3
Is a draw !
[ [ 0, 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0 ],
  [ 'Red', 'Red', 'Red', 0, 'Yellow', 'Yellow', 'Yellow' ] ]