LoginSignup
0
0
@daddygongon

「いちばんやさしいPython入門教室」修正(hit and blow判定のバグ修正)

Last updated at Posted at 2022-05-09

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

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

  1. 重複した数字を選ばないようにする，か，
  2. はたまた，より厳密に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)

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

flow_chart.png

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
  1. L3でa[0]=0とb[0]=0からhitですが，blowに数えておきます．
  2. i,jともに一つ増えます(incrementって言います)．
  3. L9ではa[1]=0 != b[1]=1です
  4. 数の小さい方(i)をincrementします．
  5. L15でa[2]=1 == b[1]=1でblowを加えます．
  6. i,jともに増やします．
  7. a[3]=6 == b[2]=6 でblowを増やします．
  8. i,j両方増やします．
  9. i==4なので終了です．
  10. 最後に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
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0