blow判定注意
「いちばんやさしいPython入門教室」1５章のヒットアンドブローゲームのブロー判定にバグがあります．
テキストの
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
1 「いちばんやさしいPython入門教室」大澤文孝著,(ソーテック社出版,2017).
- source ~/Desktop/Lectures/lecture_22s/CompA/c5_hit_and_blow_rev.org