12/9(月) 応用科学学会シンポジウムで自動運転に関する講演を担当します☆彡（試乗会もあります！来て！）

5-10. マッチ棒クイズの自動生成

やること

マッチ棒クイズ（マッチ棒パズル）はご存知でしょうか。「マッチ棒を１本動かして式を完成させてください」といった問題です。もっとも基本的なものは１桁の足し算・引き算です。

問題
答え

掛け算・割り算もあるかと思います。

問題
答え

今回はマッチ棒クイズの問題をプログラムで自動生成してみます。（というか全探索してしまいます）

実行環境

WinPython3.6をおすすめしています。

WinPython - Browse /WinPython_3.6/3.6.7.0 at SourceForge.net
Portable Scientific Python 2/3 32/64bit Distribution for Windows
sourceforge.net

Google Colaboratoryが利用可能です。

Google Colab
colab.research.google.com

ルール

問題は次の範囲とします。

  • １桁＋１桁＝１桁のような数式
  • 記号は＋、－、×、/ の４種
  • 等号（＝）は触らない
  • 数字は一般的なデジタル表記に従う
  • 負の数は用いない
  • 答えは１通りしかないものとする

答えを１つに絞ったのは、複数解が存在すると問題として美しくないと考えたためです。

パーツ１

まずは、「ある文字から１本取り除くとどんな文字になるかを返す関数」と「ある文字に１本加えるとどんな文字になるかを返す関数」を作ります。

import numpy.random as nr
from copy import deepcopy

#文字から1本取り除くとどんな文字になるか
def minus(c):
    if c == '0': return []
    if c == '1': return []
    if c == '2': return []
    if c == '3': return []
    if c == '4': return []
    if c == '5': return []
    if c == '6': return ['5']
    if c == '7': return ['1']
    if c == '8': return ['0', '6', '9']
    if c == '9': return ['3', '5']
    if c == '+': return ['-']
    if c == '-': return []
    if c == '*': return ['/']
    if c == '/': return []
    return []

print(minus('8'))

#文字に1本加えるとどんな文字になるか
def plus(c):
    if c == '0': return ['8']
    if c == '1': return ['7']
    if c == '2': return []
    if c == '3': return ['9']
    if c == '4': return []
    if c == '5': return ['6', '9']
    if c == '6': return ['8']
    if c == '7': return []
    if c == '8': return []
    if c == '9': return ['8']
    if c == '+': return []
    if c == '-': return ['+']
    if c == '*': return []
    if c == '/': return ['*']
    return []

print(plus('5'))
['0', '6', '9']
['6', '9']

取り除く方の関数に ‘8’ を入力すると [‘0’, ‘6’, ‘9’] が返ってきました。加える方の関数に ‘5’ を入力すると [‘6’, ‘9’] が返ってきました。乗算記号を ‘*’ で表記している点にご注意ください。

パーツ２

次に、先程の関数を使用して「ある式から１本取り除くとどんな式になるかを返す関数」と「ある式に１本加えるとどんな式になるかを返す関数」を作ります。式は [‘6’, ‘+’, ‘7’, ‘==’, ‘0’] のように文字をリストに格納した形式です。等号は ‘==’ で表記します。

#式から1本取り除いた式のリスト
def minus_candidate(quiz):
    new_quiz_list = []
    for i in range(len(quiz)):
        ret = minus(quiz[i])
        for j in range(len(ret)):
            tmp = deepcopy(quiz)
            tmp[i] = ret[j]
            new_quiz_list.append(tmp)
    return new_quiz_list

print(minus_candidate(['6', '+', '7', '==', '0']))

#式に1本加えた式のリスト
def plus_candidate(quiz):
    new_quiz_list = []
    for i in range(len(quiz)):
        ret = plus(quiz[i])
        for j in range(len(ret)):
            tmp = deepcopy(quiz)
            tmp[i] = ret[j]
            new_quiz_list.append(tmp)
    return new_quiz_list

print(plus_candidate(['0', '+', '1', '==', '3']))
[['5', '+', '7', '==', '0'], ['6', '-', '7', '==', '0'], ['6', '+', '1', '==', '0']]
[['8', '+', '1', '==', '3'], ['0', '+', '7', '==', '3'], ['0', '+', '1', '==', '9']]

「6+7=0」という式から１本取り除くと「5+7=0」「6-7=0」「6+1=0」の３つの式ができることがわかりました。同様に、「0+1=3」という式に１本加えると「8+1=3」「0+7=3」「0+1=9」の３つの式ができました。

パーツ３

最後に、「式の集まり（＝２重リスト）をすべて評価して式として正しいものを厳選して返す関数」と「ランダムな式を生成する関数」も作りました。eval() で文字列形式の数式を「評価」すると、数式が正しい場合に True が返ることを利用しています。

#式リストをすべて評価して正しいものを返す
def eval_candidate(quiz_list):
    new_quiz_list = []
    for quiz in quiz_list:
        tmp = ''.join(quiz)
        #0除算であればパス
        if tmp[2] == '0':
            continue
        if eval(tmp):
            new_quiz_list.append(quiz)
    return new_quiz_list

#ランダムな式を作成
def make_quiz():
    quiz = []
    quiz.append(str(nr.randint(10)))
    quiz.append(str(nr.choice(['+', '-', '*', '/'], 1)[0]))
    quiz.append(str(nr.randint(10)))
    quiz.append('==')
    quiz.append(str(nr.randint(10)))
    return quiz

print(make_quiz())
['6', '/', '0', '==', '3']

マッチ棒パズルのランダム生成

いよいよクイズを探索します。ランダムな問題を作っては

  1. すでに数式が成立していたらやり直し
  2. 数式から１本除いた式の集まりを作る
  3. 各式について１本加えた式の集まりを作る
  4. 各式を評価して正しい式を厳選する
  5. 正しい式が１つだけであれば発見とする

という作業を50回繰り返すことにします。

#クイズの探索
for i in range(50):
    print('try {}'.format(i))
    
    #ランダムなクイズを作成
    quiz = make_quiz()
    #print(quiz)
    
    #クイズを評価して正しければやり直し
    if len(eval_candidate([quiz])) == 1:
        continue
    
    #1本取り除いた式のリスト
    minused_quiz_list = minus_candidate(quiz)
    #print(minused_quiz_list)
    
    #各式に1本加えた式のリスト
    plused_quiz_list = []
    for minused_quiz in minused_quiz_list:
        plused_quiz_list += plus_candidate(minused_quiz)
    #print(plused_quiz_list)
        
    #各式を評価して正しいものを選別
    true_quiz_list = eval_candidate(plused_quiz_list)
    #print(true_quiz_list)
    
    #1つだけ見つかったら表示
    if len(true_quiz_list) == 1:
        print('quiz {}'.format(quiz))
        print('ans  {}'.format(true_quiz_list[0]))
try 0
try 1
try 2
try 3
try 4
try 5
try 6
try 7
try 8
try 9
try 10
try 11
try 12
try 13
try 14
quiz ['0', '-', '8', '==', '9']
ans  ['0', '+', '9', '==', '9']
try 15
try 16
try 17
try 18
try 19
try 20
try 21
try 22
try 23
try 24
try 25
try 26
try 27
try 28
try 29
try 30
quiz ['5', '-', '5', '==', '7']
ans  ['6', '-', '5', '==', '1']
try 31
try 32
try 33
try 34
try 35
try 36
try 37
try 38
try 39
try 40
try 41
try 42
try 43
try 44
try 45
quiz ['5', '*', '3', '==', '2']
ans  ['6', '/', '3', '==', '2']
try 46
try 47
try 48
quiz ['9', '+', '2', '==', '6']
ans  ['8', '-', '2', '==', '6']
try 49

どうでしょう。今回は４種類の問題が見つかりました。ポチポチ実行するといくらでも問題が生成できます。

マッチ棒パズルの全探索

ところで、今回の条件では問題はたかだか4000パターンしかありません。これくらいなら全探索できそうです。

全パターンの問題を生成する関数を作りました。

#全パターンの式リストを作成
def make_quiz_list():
    quiz_list = []
    for i in range(10):
        for j in ['+', '-', '*', '/']:
            for k in range(10):
                for l in range(10):
                    quiz = []
                    quiz.append(str(i))
                    quiz.append(j)
                    quiz.append(str(k))
                    quiz.append('==')
                    quiz.append(str(l))
                    quiz_list.append(quiz)
    return quiz_list

全パターンを調べます。

#全パターンの式リストを作成
quiz_list = make_quiz_list()
print(len(quiz_list))

#全探索
count = 0
for quiz in quiz_list:
    #クイズを評価して正しければパス
    if len(eval_candidate([quiz])) == 1:
        continue
    
    #1本取り除いた式のリスト
    minused_quiz_list = minus_candidate(quiz)
    #print(minused_quiz_list)
    
    #各式に1本加えた式のリスト
    plused_quiz_list = []
    for minused_quiz in minused_quiz_list:
        plused_quiz_list += plus_candidate(minused_quiz)
    #print(plused_quiz_list)
        
    #各式を評価して正しいものを選別
    true_quiz_list = eval_candidate(plused_quiz_list)
    #print(true_quiz_list)
    
    #1つだけ見つかったら表示
    if len(true_quiz_list) == 1:
        print('ID {}'.format(count))
        print('quiz {}'.format(quiz))
        print('ans  {}'.format(true_quiz_list[0]))
        count += 1
ID 0
quiz ['0', '+', '1', '==', '7']
ans  ['8', '-', '1', '==', '7']
・
・
・
ID 473
quiz ['9', '/', '8', '==', '7']
ans  ['8', '/', '8', '==', '1']

今回のルールでは、4000パターン中474パターンが問題として成立するようです。

また、一部を書き換えることで「答えが２つある」問題を調べ上げることもできます。

    #2つだけ見つかったら表示
    if len(true_quiz_list) == 2:
        print('ID {}'.format(count))
        print('quiz {}'.format(quiz))
        print('ans1 {}'.format(true_quiz_list[0]))
        print('ans2 {}'.format(true_quiz_list[1]))
        count += 1
ID 0
quiz ['0', '+', '5', '==', '8']
ans1 ['0', '+', '6', '==', '6']
ans2 ['0', '+', '9', '==', '9']
・
・
・
ID 83
quiz ['9', '/', '6', '==', '1']
ans1 ['6', '/', '6', '==', '1']
ans2 ['9', '/', '9', '==', '1']

84問見つけることができました。

「答えが３つある」問題も調べてみました。

    #3つだけ見つかったら表示
    if len(true_quiz_list) == 3:
        print('ID {}'.format(count))
        print('quiz {}'.format(quiz))
        print('ans1 {}'.format(true_quiz_list[0]))
        print('ans2 {}'.format(true_quiz_list[1]))
        print('ans3 {}'.format(true_quiz_list[2]))
        count += 1
ID 0
quiz ['0', '/', '5', '==', '8']
ans1 ['0', '*', '5', '==', '0']
ans2 ['0', '/', '6', '==', '0']
ans3 ['0', '/', '9', '==', '0']
・
・
・
ID 4
quiz ['9', '+', '3', '==', '5']
ans1 ['3', '+', '3', '==', '6']
ans2 ['8', '-', '3', '==', '5']
ans3 ['9', '-', '3', '==', '6']

５問しかないようですが、「全部答えよ」とすれば骨のあるクイズになると思います。

まとめ

クイズの自動生成ができればクイズアプリを全自動運営できるような気がします。

タイトルとURLをコピーしました