Python으로 BlockGame 풀기

알고리즘 Study 에서 이번에 BlockGame이라는 문제를 풀게 되었습니다.

https://algospot.com/judge/problem/read/BLOCKGAME

인데요, 풀이의 포인트는 다음의 두 가지로 정리됩니다.

1. 전수조사

3칸 or 2칸 block 을 골라야 하지만 편의상 2칸의 block만을 고른다고 할 때 대략
25C2 * 23C2 * 21C2 ... 3C2 입니다.
모든 경우에 3칸도 고를 수 있다고 치면 2를 매번 곱하면 되므로 2^12를 추가로 곱해주면 될 것 같네요.
3786916514485104000000L * 2^12 = 15511210043330985984000000L
정도의 경우의 수가 나오므로 이걸 다 저장하고 계산하는 것은 무리입니다.
하지만, [1,1,1,1,0] 이 [1,1,0,0,0] 다음에 생성되거나,[0,0,1,1,0] 다음에 생성되거나 결과는 동일하므로 순서가 중요하지 않고 검사 할 당시 배열의 상태만이 중요합니다. (설명을 위하여 1차원 배열로 기술하였으나 실제로는 2차원 배열)
즉, 가능한 모든 Board의 모양은 2^25 보다 적을 것 입니다.
2^25 는 33554432 이므로 이 정도라면 저장 할 수 있습니다.
즉, 메모이제이션을 쓴다면 탐색 시간이 아주 짧아지겠죠.

2. Bitmasking
문제를 풀기 위한 함수가 최대 2^25번 호출된다고 하면, 이 함수를 최대한 간소화해서 짜야 합니다. 이점을 간과하고 처음에는 5x5의 board에 block이 들어가는지 확인하기 위해 다음과 같은 코드를 짰습니다.

    def canPush(self, board, pushBoard):

        for x in range(len(board)):

            for y in range(len(board[0])):

                if 1 == pushBoard[x][y]:

                    if board[x][y] != 0:

                        return False

        return True

그냥 단순하게  5*5 번의 loop을 돌며 두 board (두번째 board는 block이라고 보시면 됩니다) 를 비교하는 code인데 이것이 상당한 cost가 되더군요.
이를 사용한 코드는 대략 는 이렇습니다.

        for block in totalBlock:

            if self.canPush(board, block):

               ...

별것 아닌 것 같은데 이 경우 시간이 너무 오래 걸렸습니다.
이를 해결하기 위해서 bitmask 를 사용합니다.
즉, 5x5 배열이 어짜피 1 혹은 0으로 표시 될 수 있으므로 이를 AND나 OR 연산으로 한번에 비교하는 것 입니다. 다음과 같습니다.

for block in totalBlock:

            if block & board == 0:

                if not self.isWin(board | block, totalBlock): 

이렇게 하면 획기적으로 속도가 빨라지더군요-



설명한 1과 2를 이용한 전체 코드는 다음과 같습니다.

    def isWin(self, board, totalBlock):

        self.callCnt = self.callCnt + 1

        ret = False

        if board in self.boardMap:

            self.hitCnt = self.hitCnt + 1

            ret = self.boardMap[board]

            return ret

        for block in totalBlock:

            if block & board == 0:

                if not self.isWin(board | block, totalBlock):

                    ret = True

                    break

        self.boardMap[board] = ret

        return ret

자 그럼 이 경우 문제가 풀렸느냐

그렇지 않습니다.

...ㅠㅠ

Python에서 제귀 자체에 대한 비용이 꽤 큰지 탐색 할 경우가 많으면, 제대로 풀리지 않았습니다.

일단 pypy를 사용해봤는데요, 정말 획기적으로 속도 향상이 있었지만 문제가 되는 케이스에서는 여전히 만족할 속도가 나오지 않았습니다.
대략적으로 python에서 50여초가 걸리던 케이스가 pypy에서는 9초가 걸리더군요-

우선 개선점을 좀 더 고민하다가, board가 저장되면 이를 90도, 180도, 270도 돌린 board도 결과가 같음을 알았습니다.

저장하는 부분 self.boardMap[board] = ret 에 위의 3가지 케이스가 더해지도록 합니다.
우선 회전을 위한 코드는 다음과 같습니다.

    def rotate5x5(self, board):

        while len(board) < 25:

            board = "0" + board

        rotated = [0 for i in range(25)]

        rotatedIdx = [[i+j*5 for i in range(5)] for j in range(5)]

        rotatedIdx = [list(tmp) for tmp in zip(*rotatedIdx[::-1])] # Rotate

        rotatedIdx = [item for sublist in rotatedIdx for item in sublist] # to Flat

        for idx in range(25):

            rotated[idx] = board[rotatedIdx[idx]]

        return rotated

이를 활용해서 저장부에 다음을 추가합니다.

        rotated = self.rotate5x5("{0:b}".format(board)) # 90

        self.boardMap[int("".join(rotated), 2)] = ret

        rotated = self.rotate5x5("".join(rotated)) # 180

        self.boardMap[int("".join(rotated), 2)] = ret

        rotated = self.rotate5x5("".join(rotated)) # 270

        self.boardMap[int("".join(rotated), 2)] = ret

자- 잘 풀렸을까요?

아닙니다. isWin의 cost가 rotate5x5로 인해 늘어나서 속도는 더 느려집니다. ㅠㅠ

rotate5x5의 연산 cost를 다음과 같이 좀 무식하게 해서 줄여봤습니다.

 while len(board) < 25:

            board = "0" + board

        rotated = [0 for i in range(25)]

        rotated[0] = board[20]

        rotated[1] = board[15]

        rotated[2] = board[10]

        rotated[3] = board[5]

        rotated[4] = board[0]

        rotated[5] = board[21]

        rotated[6] = board[16]

        rotated[7] = board[11]

        rotated[8] = board[6]

        rotated[9] = board[1]

        rotated[10] = board[22]

        rotated[11] = board[17]

        rotated[12] = board[12]

        rotated[13] = board[7]

        rotated[14] = board[2]

        rotated[15] = board[23]

        rotated[16] = board[18]

        rotated[17] = board[13]

        rotated[18] = board[8]

        rotated[19] = board[3]

        rotated[20] = board[24]

        rotated[21] = board[19]

        rotated[22] = board[14]

        rotated[23] = board[9]

        rotated[24] = board[4]

        return rotated

조금 줄어들긴 합니다만, 여전히 안쓰는 것 보다 더 높은 cost 를 요구합니다 ㅠㅠ

즉, bit 연산처럼 O(1) 의 cost로 배열을 돌릴 수 없다면, 5x5의 경우 그다지 성능 개선이 나오지 않습니다. (물론 더 커지면 의미가 있을 것 같네요)

아무래도 그냥 메모이제이션만 사용하는게 우선은 최선이라 할 수 있겠네요.

즉, 이 문제는 python으로는 무리가 있는 것 같습니다.
(해결하신 분은 저도 알려주세요. 계속 고민해봐야죠.)

여기서 궁금증이 생겨서 python(그리고 pypy)의 recursion cost를 측정해봤습니다.

재미있는 점은 변수도 cost에 큰 영향을 준 점인데요, 아래의 코드에서 callCnt가 그것입니다.(callCnt는 굳이 이렇게 측정하지 않아도 2^n이지만 비교를 위해 넣습니다) 일단 코드는 다음과 같습니다.

    callCnt = 0

    def cost(self, n):

        self.callCnt = self.callCnt + 1

        if n == 0:

            return 1

        else:

            return self.cost(n-1) + self.cost(n-1)

    def testRecursion(self):

        self.cost(20)

        print self.callCnt

이를 돌리면  python에서는 0.640529870987 의 시간이 걸립니다.
pypy에서는 어떨까요? 0.121232032776 가 걸리네요-

재미있는 점은 위에서 self.cost(20)이 아닌 5와 같이 작은 수로 한 경우인데요,
이 경우 pypy가 더 느립니다.

pypy: 0.000104904174805
python: 5.60283660889e-05

10정도 해도 pypy가 더 느리네요.

pypy: 0.016s
python: 0.001s

아마 pypy의 최적화 코드가 어느정도 까지는 오버해드로 작용하는 것 같습니다.

사용한 python은 Python 2.7.6 이며, pypy는 Python 2.7.3(PyPy 2.2.1 with GCC 4.8.4) 입니다.