tic-tac-toe data structure design challenge [closed]

Question

Design a data structure such that getWinner method runs in O(1) time.

Assume you call put(x, y, Player) for each move. Best space efficient solution wins.

Answer 1

PHP

<?php
    class TicTacToe {

        private $board;

        public function __construct($board = '_________') {
            $this->board = $board;
        }

        public function put($x, $y, $player) {
            // TODO: validate input
            // assumes $x, $y in [0..2] and $player in (O|X)
            $this->board[$x + 3*$y] = $player;
        }

        public function getWinner() {
            preg_match(
                '/^(...)*(O|X)\2\K\2'. // horizontal
                '|(O|X)..\3..\K\3'.    // vertical
                '|(O|X)...\4...\K\4'.  // diagonal \
                '|^..(O|X).\5.\K\5/',  // diagonal /
                $this->board,
                $matches
            );

            if(!empty($matches)) {
                return $matches[0];
            } else {
                return 'None';
            }
        }
    }
?>

getWinner() is a constant time lookup, because the length of $this->board is always exactly 9. A simiar approach should work for any language that supports mutable strings and regular expressions.