blow判定注意

「いちばんやさしいPython入門教室」¹５章のヒットアンドブローゲームのブロー判定にバグがあります．

テキストの

    blow = 0
    for j in range(4):
        for i in range(4):
            if (int(b[j])==a[i]) and (int(b[i])!=a[i]) and(int(b[j])!=a[j]):
                blow = blow + 1
                break

だと，randomで作った数字が

[0,1,6,0]

に対して

[6,6,1,0]

と予測した場合に，

hit:1 blow:3

と判断されます．正しくは，

hit:1 blow:2

bugの中身

順を追って見ていきましょう．最初はj=0です．

 1  [0, 1, 6, 0]
 2  b=[6, 6, 1, 0], h:1/b:2
 3  a: [*0,  1,  6,  0]
 4  b: [*6,  6,  1,  0]
 5  no match: a[ 0]: 0, b[ 0]: 6, blow: 0
 6  a: [ 0, *1,  6,  0]
 7  b: [*6,  6,  1,  0]
 8  no match: a[ 1]: 1, b[ 0]: 6, blow: 0
 9  a: [ 0,  1, *6,  0]
10  b: [*6,  6,  1,  0]
11  in match: a[ 2]: 6, b[ 0]: 6, blow: 1

i=2でblowが起こり，breakします．

次は，j=1です．

1  a: [*0,  1,  6,  0]
2  b: [ 6, *6,  1,  0]
3  no match: a[ 0]: 0, b[ 1]: 6, blow: 1
4  a: [ 0, *1,  6,  0]
5  b: [ 6, *6,  1,  0]
6  no match: a[ 1]: 1, b[ 1]: 6, blow: 1
7  a: [ 0,  1, *6,  0]
8  b: [ 6, *6,  1,  0]
9  in match: a[ 2]: 6, b[ 1]: 6, blow: 2

i=2でまたblowが起こり，breakします．これっておかしいですよね．一度breakしたのは削除するとかするべきなんですが，そのままでやっているので重複しています．

それ以外でもおかしな判定が起こります．おかしな判定ではないですが，j=2の場合も載せておきます．

1  a: [*0,  1,  6,  0]
2  b: [ 6,  6, *1,  0]
3  no match: a[ 0]: 0, b[ 2]: 1, blow: 2
4  a: [ 0, *1,  6,  0]
5  b: [ 6,  6, *1,  0]
6  in match: a[ 1]: 1, b[ 2]: 1, blow: 3

j=3の場合です．この場合はなんか無茶苦茶です．i=0で一致しているのですが，a[3]==b[3]が成り立っているのでblowカウントされません．i=3の時は意図したカウント除外なんですがね．

 1  a: [*0,  1,  6,  0]
 2  b: [ 6,  6,  1, *0]
 3  no match: a[ 0]: 0, b[ 3]: 0, blow: 3
 4  a: [ 0, *1,  6,  0]
 5  b: [ 6,  6,  1, *0]
 6  no match: a[ 1]: 1, b[ 3]: 0, blow: 3
 7  a: [ 0,  1, *6,  0]
 8  b: [ 6,  6,  1, *0]
 9  no match: a[ 2]: 6, b[ 3]: 0, blow: 3
10  a: [ 0,  1,  6, *0]
11  b: [ 6,  6,  1, *0]
12  no match: a[ 3]: 0, b[ 3]: 0, blow: 3
13  text blow:3

解決策1

というわけで，ゲームをしているときのヒントが，とんでもなく複雑でなかなか終わりません．解決策としては，

重複した数字を選ばないようにする，か，
はたまた，より厳密にblowを判断させるか．．．

です．でも，1.の解決策はゲームのルールを変えるある種の仕様変更です．バグを「それは仕様です」と強弁する漫画がよくありますが，それと同じです．正しいプログラマ(?)は2.の道を進もうとしますが．．．

厳密なblow判定をさせるのは以下の通り．意外とめんどいです．

 1  while True:
 2      if a1[i] == b1[j]:
 3          blow += 1
 4          print_results('in match   ',i,j,a1,b1, blow)
 5          i += 1
 6          j += 1
 7      else:
 8          if a1[i] < b1[j] :
 9              i += 1
10          else:
11              j += 1
12      if i == 4 or j == 4:
13          break
14      print_results('after incre',i,j,a1,b1, blow)

これをフローチャートで書くと次の通りです．

Pythonのcodeってこのフローチャートと似た感じしませんか？字下げ(indent)でif-elseの構造を作るのは，こういう発想からきているようです．ただ，これではどういう動きをしているのかとか，コードを作っていくときの助けにはなってくれません．私の頭の中でイメージしている動作を表現すると次のようになります．

まずはそれぞれの数列を昇順ソート(小さいものから順に並べる)しておきます．それを頭から比べながらblowを記録していきます．

 1  a: [*0,  0,  1,  6]
 2  b: [*0,  1,  6,  6]
 3  before comp: a[ 0]: 0, b[ 0]: 0, blow: 0
 4  a: [*0,  0,  1,  6]
 5  b: [*0,  1,  6,  6]
 6  in match   : a[ 0]: 0, b[ 0]: 0, blow: 1
 7  a: [ 0, *0,  1,  6]
 8  b: [ 0, *1,  6,  6]
 9  after incre: a[ 1]: 0, b[ 1]: 1, blow: 1
10  a: [ 0,  0, *1,  6]
11  b: [ 0, *1,  6,  6]
12  after incre: a[ 2]: 1, b[ 1]: 1, blow: 1
13  a: [ 0,  0, *1,  6]
14  b: [ 0, *1,  6,  6]
15  in match   : a[ 2]: 1, b[ 1]: 1, blow: 2
16  a: [ 0,  0,  1, *6]
17  b: [ 0,  1, *6,  6]
18  after incre: a[ 3]: 6, b[ 2]: 6, blow: 2
19  a: [ 0,  0,  1, *6]
20  b: [ 0,  1, *6,  6]
21  in match   : a[ 3]: 6, b[ 2]: 6, blow: 3
22  revised blow:2

L3でa[0]=0とb[0]=0からhitですが，blowに数えておきます．
i,jともに一つ増えます(incrementって言います)．
L9ではa[1]=0 != b[1]=1です
数の小さい方(i)をincrementします．
L15でa[2]=1 == b[1]=1でblowを加えます．
i,jともに増やします．
a[3]=6 == b[2]=6 でblowを増やします．
i,j両方増やします．
i==4なので終了です．
最後にhit分を引いて，blowは2になります

動きを一つ一つチェックしてください．ややこしい動きに対してプログラマは，こういうフローチャートを描いたり，途中経過を出力してチェックしています．

これらの動きを表示するプログラムは次の通りです．他の数列でも試して見てください．

./python_codes/c5_hit_and_blow/c5_hit_and_blow_check.py

import random
a = [0, 1, 6, 0]
#a= [2, 1, 6, 6]
b=[6,6,1,0]
print(a)
print("b=[6, 6, 1, 0], h:1/b:2")
print("b=[2, 2, 1, 6], h:0/b:2")
print("b=[6, 6, 6, 1], h:1/b:1")
print("b=[0, 0, 0, 1], h:1/b:2")

hit = 0
for i in range(4):
    if a[i] == b[i]:
        hit = hit + 1
print("hit:"+str(hit))

def mark_ij_pos(i):
    res = [' ',' ',' ',' ']
    res[i] = '*'
    return res

def print_results(text, i,j, a,b, blow):
    mark = mark_ij_pos(i)
    print('a: [{0:s}{4:d}, {1:s}{5:d}, {2:s}{6:d}, {3:s}{7:d}]'.format(*mark,*a))
    mark = mark_ij_pos(j)
    print('b: [{0:s}{4:d}, {1:s}{5:d}, {2:s}{6:d}, {3:s}{7:d}]'.format(*mark,*b))
    print('{0:s}: a[{1:2d}]:{3:2d}, b[{2:2d}]:{4:2d}, blow:{5:2d}'.format(text, i,j,a[i],b[j], blow))
    
print("a:",a)
print("b:",b)
blow = 0
for j in range(4):
    for i in range(4):
        if (b[j]==a[i]) and (b[i]!=a[i]) and(b[j]!=a[j]):
            blow = blow + 1
            print_results('in match', i,j, a,b, blow)
            break
        print_results('no match', i,j, a,b, blow)

print("text blow:"+str(blow))

blow = 0
a1 = sorted(a)
b1 = sorted(b)
i = 0
j = 0

print('a:',a1)
print('b:',b1)
print_results('before comp',i,j,a1,b1, blow)
while True:
    if a1[i] == b1[j]:
        blow += 1
        print_results('in match   ',i,j,a1,b1, blow)
        i += 1
        j += 1
    else:
        if a1[i] < b1[j] :
            i += 1
        else:
            j += 1
    if i == 4 or j == 4:
        break
    print_results('after incre',i,j,a1,b1, blow)

print("revised blow:"+str(blow-hit))

もっと楽なやり方があれば教えてください．

これも「何か動くプログラム」です．こんなのも課題としてOKですし，こういうのはプログラムの中身を理解するのに役に立つでしょ？

もっと楽なやり方

「もっと楽なやり方があれば教えてください」にtkuro-pさんに反応いただいたものです．

./python_codes/c5_hit_and_blow/c5_hit_and_blow_check_tkuro-p.py

def print_check(txt, mark, i, j):
    global a,b,mark_a,mark_b
    print(txt, i,j)
    mark_a[i]=mark
    mark_b[j]=mark
    print('answer: [{0:s}{4:d}, {1:s}{5:d}, {2:s}{6:d}, {3:s}{7:d}]'.format(*mark_a,*a))
    print(' trial: [{0:s}{4:d}, {1:s}{5:d}, {2:s}{6:d}, {3:s}{7:d}]'.format(*mark_b,*b))
    
def naive_check_original(answr, trial):
    blow, hit = 0, 0
    answr = answr[:] # 浅いコピー
    for i in range(len(trial)):
        if trial[i] == answr[i]:
            answr[i] = None
            print_check('hit:','o',i,i)
            hit +=1
        else:
            for j in range(len(answr)):
                if trial[i] == answr[j]:
                    answr[j] = None
                    blow+=1
                    print_check('blow:','x',j,i)
                    break
    return hit, blow

def naive_check_revised(answr, trial):
    global a,b,mark_a,mark_b
    blow, hit = 0, 0
    answr = answr[:] # 浅いコピー
    for i in range(len(trial)):
        if trial[i] == answr[i]:
            answr[i] = None
            print_check('hit:','o',i,i)
            hit +=1
    for i in range(len(trial)): # change this loop
        for j in range(len(answr)):
            if trial[i] == answr[j]:
                answr[j] = None
                blow+=1
                print_check('blow:','x',j,i)
                break
    return hit, blow

print("\nnormal pair test")
a = [0, 1, 6, 0]
mark_a=[' ',' ',' ',' ']
b=[6,6,1,0]
mark_b=[' ',' ',' ',' ']
print(naive_check_original(a, b))

print("\nopposite pair test for original")
a = [6,6,1,0]
mark_a=[' ',' ',' ',' ']
b=[0, 1, 6, 0]
mark_b=[' ',' ',' ',' ']
print(naive_check_original(a, b))

print("\nopposite pair test for revised")
a = [6,6,1,0]
mark_a=[' ',' ',' ',' ']
b=[0, 1, 6, 0]
mark_b=[' ',' ',' ',' ']
print(naive_check_revised(a, b))

以下の通り，'opposite test for original'では失敗します．これは，hit判定する前にblow判定してしまうと，その候補がNoneで消えるからです．

normal pair test
blow: 2 0
answer: [ 0,  1, x6,  0]
 trial: [x6,  6,  1,  0]
blow: 1 2
answer: [ 0, x1, x6,  0]
 trial: [x6,  6, x1,  0]
hit: 3 3
answer: [ 0, x1, x6, o0]
 trial: [x6,  6, x1, o0]
(1, 2)

opposite pair test for original
blow: 3 0
answer: [ 6,  6,  1, x0]
 trial: [x0,  1,  6,  0]
blow: 2 1
answer: [ 6,  6, x1, x0]
 trial: [x0, x1,  6,  0]
blow: 0 2
answer: [x6,  6, x1, x0]
 trial: [x0, x1, x6,  0]
(0, 3)

opposite pair test for revised
hit: 3 3
answer: [ 6,  6,  1, o0]
 trial: [ 0,  1,  6, o0]
blow: 2 1
answer: [ 6,  6, x1, o0]
 trial: [ 0, x1,  6, o0]
blow: 0 2
answer: [x6,  6, x1, o0]
 trial: [ 0, x1, x6, o0]
(1, 2)

'opposite test for revised'でうまくいきます．revisedではあらかじめ，hit-loopを回しているので，その候補はblow判定では無視されます．

blow判定のloop自身はそれほど難しくないので自分で追いかけてみてください．

参照

Footnotes

¹ 「いちばんやさしいPython入門教室」大澤文孝著,(ソーテック社出版,2017).

source ~/Desktop/Lectures/lecture_22s/CompA/c5_hit_and_blow_rev.org