Tic-Tac-Toe Game Result

Problem

The input has 3 lines with 3 characters each: X, O or . (an empty cell). Print X wins or O wins if that player has three in a row (horizontal, vertical or diagonal). If nobody has won and an empty cell is left, print Pending. If the board is full and nobody has won, print Draw. Boards have at most one winner.

Constraints

  • The board has 3 lines of 3 characters

Examples

Input

XXX
OO.
...

Output

X wins

Solutions

Best approachTime O(1)Space O(1)

A 3 by 3 board has exactly 8 winning lines. Writing them as text makes the check a simple comparison. Check the winners before the draw, because a full board can also have a winner.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Find the result.
 * Input   : 3 lines of 3 characters.
 * Output  : The result text.
 * Approach: Check 8 lines.
 * Time    : O(1)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static String solve(String[] lines) {
        // Step 1: Collect all 8 winning lines: 3 rows, 3 columns and 2 diagonals. Each line is a text of 3 characters.
        String[] winLines = new String[8];
        for (int i = 0; i < 3; i++) {
            winLines[i] = lines[i];
            winLines[3 + i] = "" + lines[0].charAt(i) + lines[1].charAt(i) + lines[2].charAt(i);
        }
        winLines[6] = "" + lines[0].charAt(0) + lines[1].charAt(1) + lines[2].charAt(2);
        winLines[7] = "" + lines[0].charAt(2) + lines[1].charAt(1) + lines[2].charAt(0);

        // Step 2: A player wins if one line has the same player three times.
        for (String line : winLines) {
            if (line.equals("XXX")) {
                return "X wins";
            }
            if (line.equals("OOO")) {
                return "O wins";
            }
        }

        // Step 3: No winner. If an empty cell is left, the game goes on. Otherwise it is a draw.
        for (String row : lines) {
            if (row.indexOf('.') >= 0) {
                return "Pending";
            }
        }
        return "Draw";
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(solve(lines));
    }
}
Hints (1)
  1. How many winning lines are there?