Daily Challenge #79 - Connect Four

#challenge

Catch up on your Connect Four here .

The grid is 6 row by 7 columns, those being named from A to G.

You will receive a list of strings showing the order of the pieces which dropped in columns:

pieces_position_list = ["A_Red", "B_Yellow", "A_Red", "B_Yellow", "A_Red", "B_Yellow", "G_Red", "B_Yellow"]

The list may contain up to 42 moves and shows the order the players are playing.

The first player who connects four items of the same color is the winner.

You should return "Yellow", "Red" or "Draw" accordingly.

This challenge comes from aryan-firouzian at 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 (6)

EarlWare • Sep 30 '19

A Swift solution:

import Foundation

//  possible winning moves in the form of [ [deltaRow, deltaCol] ]
let acrossWinCords = [[0, 0], [0, 1], [0, 2], [0, 3]]
let vertWinCords = [[0, 0], [-1, 0], [-2, 0], [-3, 0]]
let diagUpWinCords = [[0, 0], [-1, 1], [-2, 2], [-3, 3]]
let diagDownWinCords = [[0, 0], [1, 1], [2, 2], [3, 3]]

let red    = Character("R")
let yellow = Character("Y")
let blank  = Character(" ")

// helper function to initalize a gameboard with all blanks.
func initBoard() -> [[Character]] {
    let newRow = [Character](repeating: blank, count: 7)
    let newBoard = [[Character]](repeating: newRow, count: 6)

    return newBoard
}

// helper function to neatly print out the board
func printBoard(_ board:[[Character]]) {

    print("Row   A    B    C    D    E    F    G")
    for index in 0..<board.count {
        print("", index, "",board[index])
    }
}

// helper function, checks to make sure its within bounds of the game board.
func validMove(_ row:Int, _ col:Int) -> Bool {
    if (row >= 0 && col >= 0) &&
       (row <= 5 && col <= 6) {
        return true
    }
    return false
}


func testForWin(_ board:[[Character]]) -> Character {

    // tests for a winning streak from the bottom left and continues left, then steps up
    for row in (0..<board.count).reversed() {
        for col in 0..<board[row].count {
            var winner = testWinType(row, col, board, acrossWinCords)
            if winner != blank {
                return winner
            }

            winner = testWinType(row, col, board, vertWinCords)
            if winner != blank {
                return winner
            }

            winner = testWinType(row, col, board, diagUpWinCords)
            if winner != blank {
                return winner
            }

            winner = testWinType(row, col, board, diagDownWinCords)
            if winner != blank {
                return winner
            }
        }
    }

    return blank
}

func testWinType(_ row:Int, _ col:Int, _ board:[[Character]], _ winCords:[[Int]]) -> Character {
    var countYellow = 0
    var countRed = 0

    // tests the moves from current location along the path defined in given winCords
    for move in winCords {
        let x = row+move[0]
        let y = col+move[1]

        if validMove(x, y) {
            let slot = board[x][y]
            if slot == blank {
                break  // if there is a blank, theres no possibility of a win
            } else if slot == red {
                countRed += 1
            } else if slot == yellow {
                countYellow += 1
            }
        } else {
            break // if there is an invalid move, theres no possiblity of a win
        }
    }

    if countRed == 4 {
        return red
    } else if countYellow == 4 {
        return yellow
    }
    return blank
}

func insert(_ aMove:String, _ board:[[Character]]) -> [[Character]] {

    // split the move into a column letter and player color.  Invalid inputs WILL break this.
    let move = aMove.split(separator: Character("_"), maxSplits: 2, omittingEmptySubsequences: true)
    let letter = move[0]
    let player = move[1]

    var col = 0

    // explictly decipher Letters into column index value.
    switch letter {
    case "A":
        col = 0
    case "B":
        col = 1
    case "C":
        col = 2
    case "D":
        col = 3
    case "E":
        col = 4
    case "F":
        col = 5
    case "G":
        col = 6
    default:
        // unexpected values shouldnt change the state of the board at all.
        return board
    }

    var newBoard = board

    // iterate through the board rows starting at the bottom in the given column
    for row in (0..<board.count).reversed() {
        if board[row][col] == blank {
            if player == "Red" {
                newBoard[row][col] = red
                return newBoard
            } else if player == "Yellow" {
                newBoard[row][col] = yellow
                return newBoard
            }
        }
    }

    // unexpected values shouldnt change the state of the board at all.
    return board
}


/*
 ConnectFour challenge function.

 @param pieceList:[String] an ordered list of moves in the format of ColLetter_Color(ie "D_Red" or "F_Yellow")

 @return String containing the winner, or Draw

 */
func connectFour(_ pieceList:[String]) -> String {
    // create a blank playfield
    var connect4Grid:[[Character]] = initBoard()

    //  add pieces to the board.
    for move in pieceList {
        connect4Grid = insert(move, connect4Grid)
    }

    printBoard(connect4Grid)

    let winner = testForWin(connect4Grid)

    if winner == red {
        return "Red"
    } else if winner == yellow {
        return "Yellow"
    }

    return "Draw"
}


let example1 = ["A_Red",
                "B_Yellow",
                "A_Red",
                "B_Yellow",
                "A_Red",
                "B_Yellow",
                "G_Red",
                "B_Yellow"]

let example2 = ["A_Red",
                "A_Yellow",
                "B_Red",
                "B_Yellow",
                "C_Red",
                "C_Yellow",
                "D_Red",
                "D_Yellow"]

let example3 = ["A_Red",
                "G_Yellow",
                "B_Red",
                "F_Yellow",
                "C_Red",
                "E_Yellow"]


print("Example1 results:   ", connectFour(example1))
print("\n")
print("Example2 results:   ", connectFour(example2))
print("\n")
print("Example3 results:   ", connectFour(example3))
print("\n")

Output:

Row   A    B    C    D    E    F    G
 0  [" ", " ", " ", " ", " ", " ", " "]
 1  [" ", " ", " ", " ", " ", " ", " "]
 2  [" ", "Y", " ", " ", " ", " ", " "]
 3  ["R", "Y", " ", " ", " ", " ", " "]
 4  ["R", "Y", " ", " ", " ", " ", " "]
 5  ["R", "Y", " ", " ", " ", " ", "R"]
Example1 results:    Yellow


Row   A    B    C    D    E    F    G
 0  [" ", " ", " ", " ", " ", " ", " "]
 1  [" ", " ", " ", " ", " ", " ", " "]
 2  [" ", " ", " ", " ", " ", " ", " "]
 3  [" ", " ", " ", " ", " ", " ", " "]
 4  ["Y", "Y", "Y", "Y", " ", " ", " "]
 5  ["R", "R", "R", "R", " ", " ", " "]
Example2 results:    Red


Row   A    B    C    D    E    F    G
 0  [" ", " ", " ", " ", " ", " ", " "]
 1  [" ", " ", " ", " ", " ", " ", " "]
 2  [" ", " ", " ", " ", " ", " ", " "]
 3  [" ", " ", " ", " ", " ", " ", " "]
 4  [" ", " ", " ", " ", " ", " ", " "]
 5  ["R", "R", "R", " ", "Y", "Y", "Y"]
Example3 results:    Draw


Program ended with exit code: 0

I feel like its a bit of a mess, but it works! I didn't do any input validation, and I also assumed that there would only be one winner per move list given for the input, so invalid move list structure and move lists with multiple winners possible to be found might be unreliable. I just spent too much time on this already so I'm cutting my losses! As always, any constructive criticism is always very much appreciated.

Alvaro Montoro • Oct 1 '19

Doing this in CSS could take a long time, but it is possible as it is basically a decision tree. Not fully completing the challenge, but related to it: here is a CSS-only Connect Four:

Jeff Ong • Oct 1 '19 • Edited

Nice ! This is a very creative way to solve the problem.

willsmart • Oct 1 '19 • Edited

One in TypeScript that tracks "groups" of connected pieces so all it needs to do is check for when a group grows to 4 pieces
I feel the code ended up overly complex for the problem, but at least it prints the board prettily ¯_(ツ)_/¯

const pieces_position_list = [
  "C_Yellow",
  "E_Red",
  "G_Yellow",
  "B_Red",
  "D_Yellow",
  "B_Red",
  "B_Yellow",
  "G_Red",
  "C_Yellow",
  "C_Red",
  "D_Yellow",
  "F_Red",
  "E_Yellow",
  "A_Red",
  "A_Yellow",
  "G_Red",
  "A_Yellow",
  "F_Red",
  "F_Yellow",
  "D_Red",
  "B_Yellow",
  "E_Red",
  "D_Yellow",
  "A_Red",
  "G_Yellow",
  "D_Red",
  "D_Yellow",
  "C_Red",
];

type Group = { count: number; overriddenBy?: Group };

type Piece = {
  color: string;
  groups: { [groupKey: string]: Group };
};

type Neighbour = {
  x: number;
  y: number;
  groupKey: string;
};

const preceedingNeighbours: Neighbour[] = [
  {
    x: -1,
    y: 0,
    groupKey: "-",
  },
  {
    x: -1,
    y: -1,
    groupKey: "\\",
  },
  {
    x: 0,
    y: -1,
    groupKey: "|",
  },
  {
    x: 1,
    y: -1,
    groupKey: "/",
  },
];

function whoIsWinner(piecesPositionList: string[]): string {
  const columns: Piece[][] = [];

  return (
    piecesPositionList.find(pieceString =>
      addPiece(pieceString.charCodeAt(0) - "A".charCodeAt(0), pieceString.substring(2))
    ) || "__Draw"
  ).substring(2);

  function addPieceToGroup(group: Group | undefined): number {
    if (group === undefined) return 0;
    if (group.overriddenBy !== undefined) return addPieceToGroup(group.overriddenBy);
    else group.count++;
    return group.count;
  }

  function pieceAt(columnIndex: number, rowIndex: number): Piece | undefined {
    return columns[columnIndex] ? columns[columnIndex][rowIndex] : undefined;
  }

  function addPiece(columnIndex: number, color: string) {
    const column = columns[columnIndex] || (columns[columnIndex] = []),
      rowIndex = column.length,
      piece: Piece = {
        color,
        groups: {},
      };
    column.push(piece);
    for (const { x, y, groupKey } of preceedingNeighbours) {
      const preceedingNeighbour = pieceAt(columnIndex + x, rowIndex + y);
      const proceedingNeighbour = pieceAt(columnIndex - x, rowIndex - y);
      const preceedingNeighbourGroup =
        preceedingNeighbour && preceedingNeighbour.color === color && preceedingNeighbour.groups[groupKey];
      let proceedingNeighbourGroup =
        proceedingNeighbour && proceedingNeighbour.color === color && proceedingNeighbour.groups[groupKey];

      const group = (piece.groups[groupKey] = preceedingNeighbourGroup ||
        proceedingNeighbourGroup || {
          count: 0,
          overriddenBy: undefined,
        });
      if (preceedingNeighbourGroup && proceedingNeighbourGroup) {
        // If we have groups on both sides, merge the proceeding one (eg the one to the right) into the preceeding one
        // This is done by setting the proceeding group's `overriddenBy` reference
        while (proceedingNeighbourGroup.overriddenBy) proceedingNeighbourGroup = proceedingNeighbourGroup.overriddenBy;
        group.count += proceedingNeighbourGroup.count;
        proceedingNeighbourGroup.overriddenBy = group;
      }

      if (group && addPieceToGroup(group) >= 4) {
        logBoard();
        return color;
      }
    }
    return undefined;
  }

  function logBoard(): void {
    const rowDivider = "-".repeat(1 + 7 * 9) + "\n";
    let s = rowDivider;
    for (let rowIndex = 5; rowIndex >= 0; rowIndex--) {
      for (let columnIndex = 0; columnIndex < 7; columnIndex++) {
        const piece = pieceAt(columnIndex, rowIndex);
        if (!piece) s += "|        ";
        else
          s += `| ${piece.color.substring(0, 1)} ${["-", "\\", "|", "/"].reduce(
            (acc, groupKey) => acc + groupCountString(piece.groups[groupKey]),
            ""
          )} `;
      }
      s += "|\n" + rowDivider;
    }
    console.log(s);

    function groupCountString(group: Group): string {
      if (group === undefined) return " ";
      if (group.overriddenBy !== undefined) return groupCountString(group.overriddenBy);
      else return String(group.count);
    }
  }
}

console.log(whoIsWinner(pieces_position_list));

----------------------------------------------------------------
|        |        |        |        |        |        |        |
----------------------------------------------------------------
|        |        |        |        |        |        |        |
----------------------------------------------------------------
| R 1111 | Y 1221 |        | Y 1111 |        |        | Y 14   |
----------------------------------------------------------------
| Y 2221 | Y 2223 | R 3311 | R 3111 | R 3112 | Y 1411 | R 1321 |
----------------------------------------------------------------
| Y 1221 | R 1321 | Y 3123 | Y 3221 | Y 3411 | R 2322 | R 2221 |
----------------------------------------------------------------
| R 2311 | R 2121 | Y 2221 | Y 2423 | R 2311 | R 2221 | Y 1111 |
----------------------------------------------------------------

Yellow

Jeff Ong • Oct 1 '19 • Edited

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' ] ]