Pythonでバイナリ文字列として与えられたスコアからゲームの勝者を判定する方法

バレーボールの試合スコアを表すバイナリ文字列が与えられたとき、次のルールに基づいて試合の勝者を判定する方法を解説します。

ゲームのルール

• 15点先取制: 2チームが対戦し、先に15点を獲得したチームが勝者となります。ただし、両チームが14点に到達した場合はこの限りではありません。
• デュースのルール: 両チームが14点に達した場合(デュース)、そこから2点のリードを奪ったチームが勝者となります。

バイナリ文字列において、「0」は注目しているチームがポイントを失ったこと(相手チームの得点)を、「1」は注目しているチームがポイントを獲得したことを表します。この文字列をもとに、そのチームが試合に勝利したのか敗北したのかを判定する必要があります。

たとえば、入力が score = "1001100110111001110011011" のような場合、出力は「Team won」となります。

解決のためのアプローチ

以下の手順で勝者を判定できます。

1. スコアカウンタ score_cnt を [0, 0] で初期化します。
2. スコア文字列の先頭から各文字を順番に処理します。
   ・pos := ASCII(score[i]) − ASCII('0') で文字を数値に変換
   ・score_cnt[pos] を1増加させる
   ・score_cnt[0] == n かつ score_cnt[1] < n − 1 の場合 → 「Team lost」を返す
   ・score_cnt[1] == n かつ score_cnt[0] < n − 1 の場合 → 「Team won」を返す
   ・score_cnt[0] == n − 1 かつ score_cnt[1] == n − 1(デュース突入)の場合 → カウンタを [0, 0] にリセットしてループを抜ける
3. デュース以降は残りの文字を処理し続け、|score_cnt[0] − score_cnt[1]| == 2 となった時点で勝敗を確定します。相手側(score_cnt[0])が上回っていれば「Team lost」、自チーム(score_cnt[1])が上回っていれば「Team won」を返します。

ここで、デュース後にカウンタを0にリセットしても問題ないのは、勝敗が「直後に2点差がつくかどうか」だけで決まるためです。絶対的な得点ではなく、相対的な点差だけを追跡すればよいことになります。

実装例

理解を深めるために、以下のPython実装を見てみましょう。

def predictWinner(score, n):
    score_cnt = [0, 0]
    for i in range(len(score)):
        pos = ord(score[i]) - ord('0')
        score_cnt[pos] += 1
        if (score_cnt[0] == n and score_cnt[1] < n - 1):
            return "Team lost"
        if (score_cnt[1] == n and score_cnt[0] < n - 1):
            return "Team won"
        if (score_cnt[0] == n - 1 and score_cnt[1] == n - 1):
            score_cnt[0] = 0
            score_cnt[1] = 0
            break
    i += 1
    for i in range(i, len(score)):
        pos = ord(score[i]) - ord('0')
        score_cnt[pos] += 1
        if (abs(score_cnt[0] - score_cnt[1]) == 2):
            if (score_cnt[0] > score_cnt[1]):
                return "Team lost"
            else:
                return "Team won"

score = "1001010101111011101111"
n = 15
print(predictWinner(score, n))

入力

"1001010101111011101111"

出力

Team won