sasaharayuugo.net

【随時更新】解答に必要な機能まとめ

googleのOR-toolsでもやろうと思えばやれるのかもしれないけど、難しい上にいちいち入力するのが手間だし、理論上は制約が伝われば良いだけでもっと簡単な入力方法があるはずだから、とにかく今は解答に必要な制約をまとめるだけにする。
問題は、制約を解いた後にもまだ作業が残っている場合で、その場合はprolog系以外の良い制約プログラミング言語があれば、それを原始的に使うことにしたい。無ければ諦める。そもそもこの研究は数学の分析哲学的な記述に抗っているのであって、prologⅢを使うんじゃ意味が無い。

追記：と思ったらプログラミング言語を介さない普通のソルバーだと、数式みたいなので入力できたりするのか（ソルバーと制約プログラミング言語って何が違うんだ？）。まあでも、算数オリンピックにおいてはワケの分からない制約があったりするし、それを解く機能が無くて研究が土台から崩れて終わりというのは嫌なんで、とりあえずこのページでまとめて、自動化できるかは別系統の研究として後から考えよう。計算の増加量が滅茶苦茶だとか技術的な問題があっても、軽くする手法が無ければ結局は人間もそれをやっているわけで、制約の種類さえ明らかにできればとりあえずその後は考えなくて良い。

後日追記：円リストと呼んでいたものは「循環リスト」として既に存在していたので削除。タイトルを「【随時更新】解答に必要な制約まとめ」から「【随時更新】解答に必要な機能まとめ」に変更。

後後日追記：汚い見た目のまま行こうかと思っていたけど、考察の中心が機能から【随時更新】計算量の減らし方まとめ - ニート歴10年からの数学日記に移ってきたので、見ながら計算量の減らし方を考えれるようにするために、見た目を改善することにした。andとorを撤廃した。挿入の記法を新しくした。他にも細々と機能を付け加えた。まだ未完成、一旦完成したらこの未完成の一文は消す。

後後後日追記：for文みたいなのとか、ゲームとか、色々入れて収拾がつかなくなっている。まあ使っている内に良くなっていくと思うけど…。一番の問題点は集合とフローの区別が付いてない所なんじゃないかという気がしている。

後後後後日追記：まとまってきたので書き直した。C言語とか既存の言語風。

後後後後後日追記：フィルター機能の記述法の変更。「~」に二つの意味を持たせること。位置の制約について。それぞれ更新。
　

まず、既存のプログラミング言語との比較から。
手続き型プログラミングと制約の組み合わせということであれば、まずはKaleidoscopeがある。
書式の上ではpythonとjavascriptとその元々であるC言語を手続き型ということでよく参考にしている。
他には細かな点でSmalltalk(代入の:=)やScala(filterのit)などパッと見かけたものから拝借している。
が基本的には、基本的な書き方は上にあげた3つの手続き型プログラミング言語を参考にしているので、ニュアンスで解釈して貰えればと思う。その点は細かく説明はしない。

自分の中で、数学の問題文を記述する際に新しく必要だったのは、この並列するフローの記法ということになる。
改行を二つ入れて、段落を作ることでそれまでのフローを一旦実行する。逆に言えば段落が入るまではフローはandで並列している。
意味的には並列しているが見た目的にどうしても離したい時は、『
命令1
,
命令2
』という風にしても良い。

andに対して、orはこういう風に記述する。『
or(それ以外否定で2){
　実行文1
} or {
　実行文2
} or {
　実行文3
}
』。
if文のように見えるが、全ての場合を実行する。つまりこの場合は、1と2、1と3、2と3、を実行する場合に分かれる。例えるなら、水路が分かれていくようなイメージだ。
もちろんそれぞれの実行文にも理論上は複数の場合があり得て、その場合の全てが掛け合わさっていくので、実行する計算量は膨大になる。プログラミング言語としては致命的だが、日本語などの自然言語で書かれた数学の問題文は現にそうなっているし、それを記述するためのものだから仕方ない。
もし実際に動くプログラミング言語として存在し得るなら、その目的はもっぱら数学の解法の計算量のチェック自体になるだろう。

実行文で無く集合をorで用意するだけなら、「集合A.2.sum」のように、「.」を使って集合Aの要素を隣に渡していっても良い。この場合は、集合Aの要素の2つどれかを足し合わせた数、を表している。
それが全通りで用意される。or文はフロー自体が分かれるわけだが、これは単にリスト処理のようなものだ。
少し前までは、「集合A.filter(it > X)」みたいなので、集合AのXより大きい要素を取得したりしていた。しかしよくよく考えれば、例えば普通の文で「Y > X;」とかの文を書くとそれ以外の選択肢は消し去っていたので、もっと単純に「集合A.(it > X)」で良いような気がしたので、とりあえずそうしてみる。

「?」であり得る全ての値が用意される。例えば「リストA[?]」は「リストA」と何も変わらない（厳密には順番をどう扱うかはまだ決めてない、いやあとリストAはリストだが前者はバラバラの中身がそのまま扱われることになるか）。
「?2」のように?の直後に数字を付けることで、例えば「?5」と「?5」の間で値を共有することもできる。（これは普通の変数とは違って、例えばfor文の1回1回でしか共有されない）

集合から集合への移動は、例えば「集合A.every := 4つまでカブり有りで追加 : 同じものを2つずつ10つ : 4つまでコピー := 集合B.every」という風に記述する。
「集合A.every」と「集合B.every」は、複数の選択先集合の表現、を意味する。つまり集合Bの全てが移動し得るよということだ。
「4つまでカブり有りで追加」は、「4つまで」が選択先1つ辺りに最大いくつまで受け入れるか、「カブり有り」が選択先として何回選ばれても良いということ、「追加」が元々の集合の中身を消さずに更に追加することを意味する。
「追加」に対しては「置き換え」があって、また送り元の方の「コピー」に対しては「移動」がある。「4つまでコピー」は、送り元の集合1つ1つをそれぞれ4つまでコピーできるということ。
「同じものを2つずつ10つ」は、つまり一回辺りに2つずつ同じものを選んで、合計で10つ送るということ。「違うものを」という風に書けば必ずしも同じものでは無くなる。
とりあえず暫定なので日本語で表現している。もっと良い表現があれば良いのだけど。

『
A := 1;
B := 2;

記録1;

A := A + 1;
B := B + 1;

記録1~{
　print(A + B);
}』で3を表示することができる。

この「~」には、「1~10」みたいな「1から10」みたいな意味と共に、「において」という意味も付与しておきたい。
例えば「集合A~not_equal();」あるいは「集合A~≠;」でも良いんだが、それで集合Aの全ての要素はそれぞれ≠だということを表したい。今までのは「集合A.not_equal();」あるいは「集合A.≠;」で表していたが、こういう記述法によるものはあくまでその場のみのリスト処理で、制約としては反映されないようにしようと思う（そうじゃなければ多分フィルタリングしたいのか制約にしたいのかが分からない場合が出てくる）。

とりあえずこういうものが必要だということで、それは実践を見れば納得してもらえると思う。
他には、漢字の「数」で「集合.数」と書くことで集合の要素の数自体を参照できる。
「この項目を設定することで結果がｎ通り以下（かつ1通り以上）に絞られるように」という命令。
「対象が最大になるような組み合わせ」、「最小になるような組み合わせ」という命令。
などなどあるので、書き忘れを思い出すたびに書き加えていく。