puzzle : 4つの数で10を作る問題（または小町算？）

問２「９以下の自然数を４つ適当に選ぶ（重複を許す）。この４つの自然数と四則演算を用いて１０を生成することを考えよう。このとき（１）条件を満たすどのような自然数の組み合わせでも生成することが可能であるか？　（２）任意の組み合わせが与えられたときに、可能な計算順序の組み合わせを出力するアルゴリズムを考えよ。　（３）四則演算以外の演算について、一般に何かを語るための準備をせよ」
Twitter / satomi.k

(2)までやってみた。しかもシェルから呼び出せるようにインターフェイスまでつけてしまった。

core

• アルゴリズム的には可能な組合せを全て試す総当たりで（他が思いつきません）
• ある計算の順序が固定されたn個の数の並びについて、n個の数の問題→（n-1個の数の全ての結果）と（残り1個の数）との間で許される演算をすべて試して、これをn個の場合の結果とするという風に再帰で表現
• 1つの順序が固定された数字の並びに対しての計算量は許される演算の数がmとして、O(m^n)
• 「演算」自体を「もの」として扱うというSchemerなら当たり前の発想からすると、演算をコレクションしたり、構成を変えたりということは割と普通。同じ調子で、+ - * /以外の二項演算にも拡張可能なように作ってある。

background

電車に乗っている時の暇つぶしとして、切符に、意味はわからないけれども書かれている4桁の数字を四則演算で組み合わせて10にするという遊び。DSFF4のミニゲーム。いろんなところで見かけるパズルなのに、具体的な名前がよくわからない。小町算？（twitterで@iratqqさんに教えていただきました）

• 小町算 - Wikipedia

implementation（またの名を、このプログラムを書いた裏目的）

• gaucheの便利なライブラリの活用（特にgauche.parseopt）
• gaucheのオブジェクトシステム事始め（define-class, make, define-method）
• schemeではschemeの比較的プリミティブな機能だけを使った「勉強のためのプログラム」しか書いた無かったので、高級な機能を積極的に用い、まともに動くアプリケーションを書く練習をする

ソースコードは長いので最後につけます。
以下、長いので続きを読むで。