• home
  • about
  • 全ての投稿
  • ソフトウェア・ハードウェアの設定のまとめ
  • 分析関連のまとめ
  • ヘルスケア関連のまとめ
  • 生涯学習関連のまとめ

雄牛と雌牛

date: 2022-12-11 excerpt: 雄牛と雌牛(bulls and cows)について

tag: アルゴリズムゲームbulls and cows


雄牛と雌牛(bulls and cows)について

概要

  • N桁(たいていは4桁)の数字を推論するゲーム
  • ある桁の数字があっているとbullで、桁はあっていないが数字が他の桁に含まれるとcow
    • 数字は繰り返し利用することができないという制約がある

具体例

  • 例1
    • secret; 1807
    • guess; 7810
    • 以上の時、1bulls, 2cowsである
  • 例2
    • secret; 1123
    • guess; 0111
    • 以上の時、1bulls, 1cowsである

一般化

def check(secret, guess):
    secret = list(secret)
    guess = list(guess)

    cows = 0
    for i in range(len(secret)):
        if secret[i] == guess[i]:
            cows += 1
            guess[i] = None
            secret[i] = None
    bulls = 0
    for i in range(len(secret)):
        if secret[i] is None:
            continue
        for j in range(len(guess)):
            if secret[i] is not None and guess[j] is not None and secret[i] == guess[j]:
                guess[j] = None
                bulls += 1
                break
    return f'{cows}A{bulls}B'

print(check("1807", "7810")) # "1A3B"
print(check("1123", "0111")) # "1A1B"

参考

  • 299. Bulls and Cows/LeetCode


アルゴリズムゲームbulls and cows Share Tweet