[Moderate] interview questions #4

[rygh4775]

Tic Tac Win: Design an algorithm to figure out if someone has won a game of tic-tac-toe.

[btakeya]

• 현재 판의 상태를 통해 게임의 종료 여부와 종료 되었으면 누가 이겼는지를 판단한다.
• 종료되지 않은 게임에서 한 수를 두었을 때 이 수를 통해 게임이 끝나는지를 판단한다. (게임이 끝난다면 수를 둔 쪽이 이김)
• 판의 상태를 hash table로 저장하여 memoization을 한다. -> 연산시간 줄이기

[btakeya]

X = 0x00
A = 0x01
B = 0x02

_MIN_INDEX = 0
_MAX_INDEX = 2

class Board(object):

    def __init__(self):
        self.val = 0x0000000000
        self.cache = {}

    def debug(self):
        print(hex(self.val))
        for _x in range(_MIN_INDEX, _MAX_INDEX + 1):
            for _y in range(_MIN_INDEX, _MAX_INDEX + 1):
                print('{} '.format(self.get(_x, _y)), end='')
            print()

    def _cache_current_status(self):
        self.cache[self.val] = self.has_finished()

    def has_finished(self):
        if self.cache.get(self.val) is not None:
            return self.cache[self.val]

        for _x in range(_MIN_INDEX, _MAX_INDEX + 1):
            candidate = self.get(_x, 0)
            if (candidate is not X) and (candidate == self.get(_x, 1) == self.get(_x, 2)): # using loop for y would be better
                return candidate

        for _y in range(_MIN_INDEX, _MAX_INDEX + 1):
            candidate = self.get(0, _y)
            if (candidate is not X) and (candidate == self.get(1, _y) == self.get(2, _y)): # using loop for y would be better
                return candidate

        # diagonal
        candidate = self.get(0, 0)
        if (candidate is not X) and (candidate == self.get(1, 1) == self.get(2, 2)): # using loop for y would be better
            return candidate

        # reverse-diagonal
        candidate = self.get(0, 2)
        if (candidate is not X) and (candidate == self.get(0, 1) == self.get(2, 0)): # using loop for y would be better
            return candidate

        return None

    def get(self, x, y):
        return (self.val >> ((x * 3 + y) * 4)) & 0x0F

    def put(self, x, y, val):
        if x < _MIN_INDEX or _MAX_INDEX < x:
            return False

        if y < _MIN_INDEX or _MAX_INDEX < y:
            return False

        if self.get(x, y) is not X:
            return False

        self.val |= val << ((x * 3 + y) * 4)

        self._cache_current_status()

        return True

def main():
    board = Board()
    board.debug()
    board.put(1, 2, A)
    print(board.has_finished())
    board.put(2, 0, B)
    print(board.has_finished())
    board.put(2, 1, B)
    print(board.has_finished())
    board.put(2, 2, B)
    print(board.has_finished())
    print(board.put(1, 2, A))
    board.debug()

if __name__ == '__main__':
    main()