Cryptarithm

指定した形の虫食い算の問題を生成するPythonモジュールです．作問や問題の検証に使ってください．

インストールと実行

1. Python3のインストール

   • 公式サイトから最新バージョンをダウンロード・インストールしてください．python3.6以降ならたぶん動くとは思います．

   • コマンドプロンプトで，

     ~ % python -V
     ~ % pip -V
     

     を実行し，python, pipがインストールされていることを確認してください．

2. cryptarithmのインストール

   PyPIに登録するか迷いましたが，今のところはしてないので，次のコマンドでインストールしてください．

   ~ % pip install git+https://github.com/dragoemon1/cryptarithm
   

3. 実行

   とりあえず動かしたいという場合は，

   • create_division.py (割り算)
   • create_multiplication.py (掛け算)

   にサンプルプログラムがあるので，これをダウンロード・編集して実行してください．

   ~ % python create_division.py
   ~ % python create_multiplication.py
   

使い方

1. 文字列

   まず，生成したい問題の形の文字列を用意してください．例を見れば大体わかると思います．

   #割り算の場合
   STRING = '''
          ####
      ---------
   1##)#######
       ####
   ------------
        ####
        ##3#
   ------------
         ####
         ####
   ------------
          ####
          ####
   ------------
             0
   '''
   

   #掛け算の場合
   STRING = '''
      ###
      #4#
   -------
     ####
    SAKU
   MONN
   -------
   #2####
   '''
   

   注意点

   • 線を表す-およびスペースは可読性のためのものなのであってもなくても動きます．改行と割り算の)　(|でもよい)は数字の区切りを表すため必要です．
   • *と#は空欄を表し，0~9の数字が入ることを表します (但し最高位は0でない)．これらには同じ数字が入っても構いません．
   • #と*には若干の違いがあります．問題生成の段階で，#は答えが一意に定まるように適当な数字に置き換わることがありますが，*は数字に置き換わることなく空欄のままとなります．
   • *,#,-,スペースおよび0~9の数字以外の文字(アルファベトなど)はすべて空欄として処理されます．これらについては，同じ文字には同じ数字が，異なる文字には異なる数字が入るようになります．また，問題生成の段階でこれらは数字に置き換わることはありません．
   • 割り算の筆算について，商のどこかの位に0を含むものには対応していません．

2. 問題の生成 関数make_problem()に1で定義した文字列を渡すと，問題を次々に生成するプロンプトが起動します．

   #割り算の場合
   from cryptarithm import make_problem
   make_problem(STRING, type="d")
   

   #掛け算の場合
   from cryptarithm import make_problem
   make_problem(STRING, type="m")
   

3. 出力

   make_problem()の出力の読み方です．

   • はじめに，元のSTRINGの答えとなりうるものが一覧として表示されます．
   • 次に，答えが一意に定まるような問題とその答えが1つ作成されます．PROBLEMが問題，ANSWERが答え，FIXEDが問題生成の際に新たに埋めた#の個数を表します．
   • エンターキーを押すと次の問題が出力されます．
   出力結果の例

   ANSWER No.1
      438
      743
   ------
     1314
    1752
   3066
   ------
   325434
   
   (中略)
   
   ANSWER No.7
      438
      749
   ------
     3942
    1752
   3066
   ------
   328062
   
   There are 7 answers in the given case
   
   PROBLEM
      ***
      *4*
   ------
     ****
    SAKU
   MONN
   ------
   *2**1*
   
   ANSWER
      438
      745
   ------
     2190
    1752
   3066
   ------
   326310
   
   U:2, K:5, A:7, S:1, N:6, O:0, M:3
   FIXED:1
   
   Press enter to create another case:
   

4. 高度な設定

   cryptarithm.make_problem()にはstring, typeの他に2つのパラメータがあります．

   • key

     問題を生成するアルゴリズムに若干の違いがあり，生成される問題の特徴に違いが現れます．デフォルトはkey="disorder"です．

     • key="disorder": なるべくランダムに問題が出力されます．空欄の数は不安定になります．とりあえずこれにしておいて，空欄が多い(FIXEDの値が小さい)ものを選ぶのが良いと思います．
     • key="short": 空欄が多い問題が優先的に出力されます．その分問題の多様性が少なくなります．
     • key="random": なるべくランダムで，どの追加情報を消しても答えが一意に定まらないよう空欄の数を極大化したものが出力されます．ただし,"short","disorder"に比べて生成に時間がかかります．

   • M

     最初に問題の答えとなりうるものを全列挙しますが，その個数の上限を表します．デフォルトはM=100000に設定されています．なお，選択肢の個数がMを超えてしまって全列挙できなくても問題は出力されますが，その場合問題の生成に時間がかかります．

開発者向けのお話

問題を生成する関数make_problem()以外にも，いくつかのクラスや関数が定義されています．詳しいことは書いてないのでソースコードを見てください．

1. class Multiplication, class Division

   掛け算，割り算オブジェクトを表します．クラスメソッドMultiplication.string2multiplication(), Division.string2division()を用いて文字列から変換できます．

   from cryptarithm import Multiplication
   
   STRING = '''
      ###
      #4#
   -------
     ####
    SAKU
   MONN
   -------
   #2####
   '''
   mul = Multiplication.string2multiplication(STRING)
   
   print(mul.str()) #出力
   

   copy()メソッドで複製，str()メソッドで文字列に変換できます．

2. def solve_multiplication(), def solve_division()

   Multiplication, Divisionオブジェクトを渡すと，それらの答えを表すMultiplication, Divisionオブジェクトを列挙するイテレータを返します．渡したオブジェクトが書き換えられることがあるので，.copy()で複製したものを渡すことを推奨します．

   from cryptarithm import solve_multiplication
   for answer in solve_multiplication(mul.copy()):
       print(answer.str())
   

   中身は動的計画法で数字を埋めていって，最後まで上手く行ったものを出力しているだけです．大したことはしていません．

3. class Box

   空欄を表すオブジェクトです．詳しい機能は気が向いたら書きます．

4. class Column

   数字を，Boxオブジェクトと0~9のint からなるリストを使って表すオブジェクトです．詳しい機能は気が向いたら書きます．