五目並べチェッカー

#五目並べチェッカー

### はじめに

Twitterでchokudaiさんのツイートを見ました。
<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">個人的に、「これが解ければ業務任せてもロジック部分は安心だな！」って思える問題は五目並べチェッカーなのよね。<a href="https://t.co/wIKuygqlzs">https://t.co/wIKuygqlzs</a></p>&mdash; chokudai(高橋 直大)🍆🍡🌸 (@chokudai) <a href="https://twitter.com/chokudai/status/1140671467488600064?ref_src=twsrc%5Etfw">June 17, 2019</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

この問題ができたら業務を任せても安心なレベルらしいので、さっそく挑戦してみました。

### 問題

[ARC12 C問題 - 五目並べチェッカー](https://atcoder.jp/contests/arc012/submissions/6004160)

### 方針を考える

コードを書き始める前に、まず何を実現する必要があるのか考えます。問題文に書いてあるとおり、以下の2つの場合がないかどうかを検索したいです。

- どちらかのプレーヤーの勝利条件を満たしているのに、もう片方のプレーヤーがさらに碁石を置いている。
- お互いが置いた個数がありえない状態になっている。

まず個数についてカウントし、以下の3つのパターンのどれかであることを確認しましょう。

- 黒が白より1個多い(最後に行動したのは黒)
- 黒と白が同じ個数(最後に行動したのは白)
- 盤面に何も石が置いていない

(ちなみに私が最初に提出したコードで、黒石と白石の個数の差が1個以下であればOKとしてしまったのですが<font color="#449d44"><B>AC</B></font>になりました。白石が黒石より1個多い場合はOKではないので<B><font color="#ec971f">嘘解法</font></B>ですが、それはテストケースに含まれていなかったみたいです。)

個数を確認できたら、以下の手順で勝利条件の確認をします。

- 現在の盤面で両者ともに勝利条件を満たしていなければOK
- 最後に行動したプレイヤーの石をどれか取り除いてみて、その状態で両者ともに勝利条件を満たしていなければOK

五目並べの勝利条件とは、5つ以上の碁石が縦・横・ななめに並んでいることです。これを確認するためには碁盤の縦・横・ななめを1次元の配列で取り出して連続する碁石の数を数えれば良さそうです。

### 実装

方針が決まったので、さっそくコードを実装していきます。それなりに長くて複雑になりそうなので、クラスで定義してメソッドを分割して書くことにしました。

```python:ARC.py
class Checker:
    def __init__(self):
        self.grid = []
        self.black = 0
        self.white = 0
        self.normal = False
        self.size = 19
```

使いそうなインスタンス変数を定義しておきます。`self.grid`は碁盤を2次元配列で入れるために使います。`self.black`と`self.white`は黒石と白石をカウントした個数を入れます。`self.normal`は碁盤が正常な状態かどうか判定した結果を入れます。今回は碁盤の大きさが`19x19`で決まっていますが、汎用性を持たせたいので`self.size`に大きさを入れておきます。

```python:ARC.py
    def make(self):
        for _ in range(self.size):
            row = list(input())
            self.grid.append(row)
```

まずは標準入力を受け取って碁盤を作成します。各行の碁盤の状態が文字列で入力されるので、`list(input())`で配列に変換しています。ここで`self.grid`は以下のような2次元配列になっています。

```
[['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', 'x', '.', '.', '.', '.', '.', '.', 'o', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', 'o', '.', '.', '.', '.', 'o', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', '.', 'x', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', 'o', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', 'x', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.']]
```

```python:ARC.py
    def count(self):
        for row in self.grid:
            self.black += row.count("o")
            self.white += row.count("x")
```

碁盤においてある碁石の数をカウントします。各行ごとに配列で取り出して`"o"`と`"x"`がいくつあるのか`count`で数えて足し合わせればよいです。

```python:ARC.py
    def judge(self):
        self.count()
        if self.black == self.white + 1:
            check = "o"
        elif self.black == self.white:
            check = "x"
        else:
            return

        self.isnormal()
        if self.normal:
            return
        for r in range(self.size):
            for c in range(self.size):
                if self.grid[r][c] == check:
                    self.grid[r][c] = "."
                    self.isnormal()
                    if self.normal:
                        return
                    self.grid[r][c] = check
```

最初に方針で確認したとおりまず個数についてカウントし、以下の3つのパターンのどれかであることを確認しましょう。

- 黒が白より1個多い(最後に行動したのは黒)
- 黒と白が同じ個数(最後に行動したのは白)
- 盤面に何も石が置いていない

今回のコードでは盤面に何も石が置かれていない場合は、場合分けしなくても正しく判定できるます。黒石の個数が白石より1個多いか、同じであることを確認して、それぞれ最後に行動したプレイヤーがどちらなのかを決めます。最後に行動したプレイヤーが黒石`o`または白石`x`であることを`check`という変数に入れました。
石の個数が異常な場合はそのまま`return`します。`self.normal`の初期値は`False`にしてあるので、盤面が異常であることを返しています。

個数が正しいことが確認できたら、以下の手順で勝利条件の確認をします。

- 現在の盤面で両者ともに勝利条件を満たしていなければOK
- 最後に行動したプレイヤーの石をどれか取り除いてみて、その状態で両者ともに勝利条件を満たしていなければOK

盤面が勝利条件を満たしていないことを`isnormal`で判定することにします。(これは後で書きましょう)
まず現在の盤面で判定し、ここで`self.normal`が`True`になっていれば盤面が正常であることを返します。
そうでなければ最後に行動したプレイヤーの石をどれか1つ取り除いてみます。各行(`r`)、各列(`c`)ごとにすべてのマス目を見ていきます。マス目に`check`で決めておいた石が置かれていたらいったん取り除いて、`isnormal`で判定します。これで`self.normal`が`True`になればOKであり`return`します。そうでなければ石をもとに戻して、次のマス目を見ます。
最後まで確認して`self.normal`が`False`のままであれば、そのままこのメソッドを終了します。

```python:ARC.py
    def isnormal(self):
        self.normal = True
        for row in self.grid:
            self.combo(row)

        for col in zip(*self.grid):
            self.combo(col)

        field = []
        for row in self.grid:
            field_row = ["."] * self.size + row + ["."] * self.size
            field.append(field_row)

        for c in range(self.size * 2):
            check_arr = []
            for r in range(self.size):
                check_arr.append(field[r][r+c])
            self.combo(check_arr)

        for c in range(self.size * 2):
            check_arr = []
            for r in range(self.size):
                check_arr.append(field[r][self.size+c-r])
            self.combo(check_arr)
```

次に`isnormal`を書きましょう。このメソッドの内部では`self.normal`をまず`True`にしておき、縦・横・ななめのどれかで5つ以上連続する石があった場合に`self.normal`を`False`にします。縦・横・ななめのすべての検索で`False`にならなければ、`self.normal`が`True`のままメソッドが終了します。

配列を入れると連続する最大の個数を判定する`combo`というメソッドを使うことにします。(これは後で書きましょう)
行ごとに配列を取り出して`combo`に渡します。列ごとに取り出す場合は`zip(*self.grid)`で同様に配列を取り出します。

`zip`は以下のような挙動をします。配列がリストではなくタプルに出てくることに注意しておきます。後で`combo`で判定するときに問題が出てくるようであれば、ここでリストに変換してから`combo`に渡すことにします。

```
grid = [[1, 2, 3], [4, 5, 6]]
for col in zip(*grid):
    print(col)
 
(1, 4)
(2, 5)
(3, 6)
```

次が今回の問題で一番面倒な、ななめの判定です。`self.grid`をななめに見て配列を取り出していきます。このようなときグリッドの周囲に空白のマスを付け加えておくと、書きやすいです。

![ななめ.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/393886/61a4e2a0-2287-29ec-e937-be52756d115c.png)

黒色の点が碁盤で、空白のマス目(図の水色の点)を左右に付け足しています。このようにすることでななめを判定するときに碁盤の左右にはみ出してしまう問題を簡単に解決できます。

つけたしてできたグリッドを`field`とします。これに対して`field[r][r+c]`を見ていくと右下方向に向かうななめの配列を取り出せます。

![ななめ2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/393886/f5fd61ef-006a-f1ed-52b5-8fd48ec038a2.png)

同様に`field[r][self.size+c-r]`を見ていくと左下方向のななめの配列が取り出せます。それぞれ`combo`に渡して判定します。

```python:ARC.py
    def combo(self, arr):
        curr = "."
        combo = 0
        max_combo = 0
        for item in arr:
            if item in ["o", "x"]:
                if item == curr:
                    combo += 1
                else:
                    curr = item
                    combo = 1
                max_combo = max(max_combo, combo)
            else:
                curr = "."
        if max_combo >= 5:
            self.normal = False
```

最後に連続する碁石の数を判定する`combo`を作ります。同じ石が連続していたら`combo`を増やしていき、最大値を`max_combo`とします。これが5以上であれば`self.normal`を`False`にしています。

```python:ARC.py
    def print(self):
        print("YES" if self.normal else "NO")
```

問題文の形式に合わせた出力を行います。

それではすべてのメソッドをまとめて、実行してみましょう。

```python:ARC.py
class Checker:
    def __init__(self):
        self.grid = []
        self.black = 0
        self.white = 0
        self.normal = False
        self.size = 19

    def print(self):
        print("YES" if self.normal else "NO")

    def count(self):
        for row in self.grid:
            self.black += row.count("o")
            self.white += row.count("x")

    def make(self):
        for _ in range(self.size):
            row = list(input())
            self.grid.append(row)

    def judge(self):
        self.count()
        if self.black == self.white + 1:
            check = "o"
        elif self.black == self.white:
            check = "x"
        else:
            return

        self.isnormal()
        if self.normal:
            return
        for r in range(self.size):
            for c in range(self.size):
                if self.grid[r][c] == check:
                    self.grid[r][c] = "."
                    self.isnormal()
                    if self.normal:
                        return
                    self.grid[r][c] = check

    def combo(self, arr):
        curr = "."
        combo = 0
        max_combo = 0
        for item in arr:
            if item in ["o", "x"]:
                if item == curr:
                    combo += 1
                else:
                    curr = item
                    combo = 1
                max_combo = max(max_combo, combo)
            else:
                curr = "."
        if max_combo >= 5:
            self.normal = False

    def isnormal(self):
        self.normal = True
        for row in self.grid:
            self.combo(row)

        for col in zip(*self.grid):
            self.combo(col)

        field = []
        for row in self.grid:
            field_row = ["."] * self.size + row + ["."] * self.size
            field.append(field_row)

        for c in range(self.size * 2):
            check_arr = []
            for r in range(self.size):
                check_arr.append(field[r][r+c])
            self.combo(check_arr)

        for c in range(self.size * 2):
            check_arr = []
            for r in range(self.size):
                check_arr.append(field[r][self.size+c-r])
            self.combo(check_arr)


game = Checker()
game.make()
game.judge()
game.print()
```

問題のテストケースを入れると正しく`YES`と`NO`で判定されます。無事に<font color="#449d44"><B>AC</B></font>になりました。