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



# blow判定注意

「いちばんやさしいPython入門教室」<sup><a id="fnr.1" class="footref" href="#fn.1" role="doc-backlink">1</a></sup>５章のヒットアンドブローゲームのブロー判定にバグがあります．

テキストの

```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

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

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

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

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

```python
 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](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/151211/508be977-a4d7-1cad-25f3-2fc871ddf4dd.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:./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:./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

<sup><a id="fn.1" href="#fnr.1">1</a></sup> 「いちばんやさしいPython入門教室」大澤文孝著,(ソーテック社出版,2017).


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