大きい数を作る
しばらく前に Twitter で流れた問題。
1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0の10個と + - × ÷ ( )を使って大きい数を作れ
数字の利用は各一回ずつ、順番は自由、べき乗は禁止。
出題者は[twitter:@fufufukawa]さん、広めたのは[twitter:@s01]さん。
@s01さんの解説がこことここに、[twitter:@xhl]さんがメモリ40GBを使って近似解を求めたプログラムの解説がここにある。
以下ネタばれ注意。
人力で解く場合の考え方
というか、僕が考えたことのログ。
大きくするならとりあえず全部掛けておけばいいんじゃね、という考えを0.5秒で却下し、2未満の数では掛け算より足し算の方が強いことに気がつくよりも前に、1.2-1.1=0.1 で割るのが強力なことに気がつく。これで 39,000 が作れる。（僕は足し算が強力なことに気づいていなかったので最初は 38,000 だと思っていた。。。）
(2.0+1.9) / (1.8-1.7) / (1.6-1.5) / (1.4-1.3) / (1.2-1.1) = 39,000
(2.0+1.9) のところがいかにも無駄な感じがするから、数字3個使って作れる小さな数はないかな、と考えると、1.1*1.2-1.3=0.02 に気がつく。
2.0 / (1.9-1.8) / (1.7-1.6) / (1.5-1.4) / (1.2*1.1-1.3) = 100,000
「小さい数を作る」という発想から、「2つの近い数を作る」という発想に移行すると、1.1*1.2≒1.3 ⇒ 1.1≒1.3/1.2 に気がつく。
2.0 / (1.9-1.8) / (1.7-1.6) / (1.5-1.4) / (1.1-1.3/1.2) = 120,000
ここから先は新しい発想は必要なくて、地道に近い数の組み合わせを探すだけ。0.1刻みの２つの数の掛け算表を作って、近い値になるものを探していくと、以下のものが見つかる。矢印の右側は、そこから作れる最小の数。
1.1*1.2≒1.3 ⇒ 1/60 1.1*1.8≒2.0 ⇒ 1/90 1.2*1.6≒1.9 ⇒ 1/70 1.3*1.4≒1.8 ⇒ 1/80
1.1*1.3≒1.4 ⇒ 3/130 1.1*1.7≒1.9 ⇒ 3/170
これらの中からうまく組み合わせられるものを探すと、468,000 が作れる。
1.5 / (2.0/1.8-1.1) / (1.2-1.9/1.6) / (1.1-1.4/1.3) = 468,000
さらに割り算の表も作ると、1.1*1.3≒2.0/1.4 が出てくる。これを使うと 1,092,000 が作れる。
1.5 / (1.8-1.7) / (1.1-2.0/1.3/1.4) / (1.2-1.9/1.6) = 1,092,000
僕はここまでだったけど、人力で 1,992,264 を見つけたつわものもいるようだ。
プログラムによる全探索
探索空間
結合則・交換則を無視して単純にすべての式を列挙しようとすると4,625,065,731,686,400個の候補があるので、とてもじゃないけど調べきれない。ところが結合則・交換則を考えると、1,500分の1にまで減って2,894,532,443,154になるらしい。（詳細はs01さん記事のコメント参照）
さらに、求めるのは最大値なので、値が負の範囲は考える必要がない*1。また、この問題設定で最後の演算が加減算になることはありえない*2ので、式の形はa*b, a/bのどちらか。さらに、aを大きくするのに引き算はありえない、bを小さくするのに足し算はありえない、と考えると、可能性があるのは X*Y*Z, X*Y/Z, X/Y/Z, (X+Y)*Z, (X+Y)/Z, X/(Y-Z) の形の式のみ。これで、探索空間の大きさは、途中でゼロ除算が発生したものを除いて776,831,666,818にまで減った*3。ちなみに、正の範囲に絞るだけで式の形に関する仮定をおかない場合は1,490,692,190,589。
アルゴリズム
式の形を二分木で考えていると、結合則・交換則による重複を考えるのはすごく大変。そこで、ひとつのノードでn個の数の加減算（または乗除算）を一度に考えることにする。その上で、加減算（乗除算）の子に加減算（乗除算）がくるのを許さないことにすると、各n項演算の中だけで重複を除去すれば良いことになる。n項加減算演算子では負になるものを除いて2^(n-1)通り、乗除算演算子では(2^n)-1通りを調べればよい。
探索は、ボトムアップに式を構築しながら行うことにした。袋の中に10個の数を入れておいて、そこから構築できる高さ1の木（正確にはその評価値）をすべて列挙する。そのそれぞれに対し、高さ2の式、高さ3の式、と再帰的に構築していき、袋の中の数字が3個以下になったら上で説明した形の式を適用して、もっとも大きい値を探す。
で、8時間半まわして出てきた答えがこれ。
2.0/(1.1-1.6/(1.8/1.9/((1.4+1.5)*1.7+1.2)+1.3) ) = 3,388,220
これを人力で見つけた人がいたら尊敬しますっていうか怖いです。
ちなみに、最終的な式の形に重複はないけど、途中で出てくる部分式には重複がある。これを除去するために、ある閾値以下の個数の数字を使ってできる値のリストをキャッシュしておくともっと速くなるかも*4。その場合にはボトムアップではなくトップダウンに探索したほうが良さそう。
プログラム
import文のないJavaプログラムなんてものを書くのは、Hello World以外では初めてじゃないだろうか。
public class LargeNum2 {
/** check(double)を呼び出した回数 */
private static long c = 0;
/** これまでに見つけた最大値 */
private static double currentMax;
/** 値の集合 */
private static double vals;
/** vals[i] の値の種類。 最初からある数字は0、加減算の結果は1、乗除算の結果は2*/
private static int types;
/** vals 内に残っている要素の数 */
private static int numVals;
private static final double DELTA = 1e-11;
private static final boolean CHECK_DIV_ZERO = true;
private static final int TYPE_MUL = 1;
private static final int TYPE_ADD = 2;
private static final int LIMIT_NUMVALS = 3;
/**
* vals[0] から vals[r-1] までに高さNの演算結果が入っている前提で、
* vals[l]からvals[r-1]のうちから少なくともひとつの値を使ってできる高さN+1の値をすべて調べる。
* @param nextNewValPos 新しく作る高さN+1の演算結果を入れる場所
* @param l 演算に使う数の左端（inclusive）
* @param r 演算に使う数の右端（exclusive）
* @return 今までで最大の値を見つけた場合はtrue
*/
private static boolean search(int nextNewValPos, int l, int r) {
if (numVals <= LIMIT_NUMVALS)
return check();
boolean flg = false;
for (int i = l; i < r; i++) {
swap(nextNewValPos, i);
switch (types[nextNewValPos]) {
case 0:
flg |= searchMul(nextNewValPos, i+1, i+1, r, true);
flg |= searchAdd(nextNewValPos, i+1, i+1, r);
break;
case TYPE_MUL:
flg |= searchAdd(nextNewValPos, i+1, i+1, r);
break;
case TYPE_ADD:
flg |= searchMul(nextNewValPos, i+1, i+1, r, true);
break;
default:
throw new RuntimeException();
}
swap(nextNewValPos, i);
}
return flg;
}
/**
* 乗除算演算子を使って作れる値を調べる。
* @param posNewVal 演算結果の格納場所、かつ最初のオペランドが入っている場所
* @param ll 同じ高さの別のtermを作る場合に使うoperandの左端。
* @param l オペランドの候補の左端。
* @param r 同じ高さの別のtermを作る場合に使う最初のoperandのの右端。（exclusive）
* @param needReverse vals[posNewVal]の値が、乗算のみによって作られている場合はtrue。この場合、vals[posNewVal]の逆数を探索の候補とする。
* @return 今までで最大の値を見つけた場合はtrue
*/
private static boolean searchMul(int posNewVal, int ll, int l, int r, boolean needReverse) {
boolean flg = false;
double t1 = vals[posNewVal];
int t_type = types[posNewVal];
types[posNewVal] = TYPE_MUL;
for (int i = l; i < numVals; i++) {
if (types[i] == TYPE_MUL) continue;
int t_type2 = types[i];
double t2, t3;
boolean lessThanR;
if (i < r) {
lessThanR = true;
t2 = removeFromVals2(i, r);
r--;
} else {
lessThanR = false;
t2 = removeFromVals(i);
}
t3 = vals[posNewVal] = t1 * t2;
boolean f = false;
f |= search(0, 0, posNewVal + 1); // next height
f |= searchMul(posNewVal, ll, i, r, needReverse); // same height, いま作ったtermにさらにつなげる
f |= search(posNewVal + 1, ll, r); // same height, 別のtermを作る
if (f) {
System.out.println(t1 + "*" + t2 + "=" + t3);
flg = true;
}
if (!CHECK_DIV_ZERO || t2 >= DELTA) {
t3 = vals[posNewVal] = t1 / t2;
f = false;
f |= search(0, 0, posNewVal + 1);
f |= searchMul(posNewVal, ll, i, r, false);
f |= search(posNewVal + 1, ll, r);
if (f) {
System.out.println(t1 + "/" + t2 + "=" + t3);
flg = true;
}
}
if (needReverse && (!CHECK_DIV_ZERO || t1 >= DELTA)) {
t3 = vals[posNewVal] = t2 / t1;
f = false;
f |= search(0, 0, posNewVal + 1);
f |= searchMul(posNewVal, ll, i, r, false);
f |= search(posNewVal + 1, ll, r);
if (f) {
System.out.println(t2 + "/" + t1 + "=" + t3);
flg = true;
}
}
if (lessThanR) {
insertVal2(i, r, t2, t_type2);
r++;
} else {
insertVal(i, t2, t_type2);
}
}
vals[posNewVal] = t1;
types[posNewVal] = t_type;
return flg;
}
/**
* 加減算演算子を使って作れる値を調べる。
* @param posNewVal 演算結果の格納場所、かつ最初のオペランドが入っている場所
* @param ll 同じ高さの別のtermを作る場合に使うoperandの左端。
* @param l オペランドの候補の左端。
* @param r 同じ高さの別のtermを作る場合に使う最初のoperandのの右端。（exclusive）
* @return 今までで最大の値を見つけた場合はtrue
*/
private static boolean searchAdd(int posNewVal, int ll, int l, int r) {
boolean flg = false;
double t1 = vals[posNewVal];
int t_type = types[posNewVal];
types[posNewVal] = TYPE_ADD;
for (int i = l; i < numVals; i++) {
if (types[i] == TYPE_ADD) continue;
int t_type2 = types[i];
double t2, t3;
boolean lessThanR;
if (i < r) {
lessThanR = true;
t2 = removeFromVals2(i, r);
r--;
} else {
lessThanR = false;
t2 = removeFromVals(i);
}
t3 = vals[posNewVal] = t1 + t2;
boolean f = false;
f |= search(0, 0, posNewVal + 1);
f |= searchAdd(posNewVal, ll, i, r);
f |= search(posNewVal + 1, ll, r);
if (f) {
System.out.println(t1 + "+" + t2 + "=" + t3);
flg = true;
}
t3 = vals[posNewVal] = abs(t1 - t2);
f = false;
f |= search(0, 0, posNewVal + 1);
f |= searchAdd(posNewVal, ll, i, r);
f |= search(posNewVal + 1, ll, r);
if (f) {
System.out.println(t1 + "-" + t2 + "=" + t3);
flg = true;
}
if (lessThanR) {
insertVal2(i, r, t2, t_type2);
r++;
} else {
insertVal(i, t2, t_type2);
}
}
vals[posNewVal] = t1;
types[posNewVal] = t_type;
return flg;
}
private static boolean check() {
switch (numVals) {
case 1:
return check(vals[0]);
case 2:
if (vals[0] > 1) {
if (vals[1] > 1) {
return check(vals[0] * vals[1]);
} else if (!CHECK_DIV_ZERO || vals[1] >= DELTA){
return check(vals[0] / vals[1]);
} else {
return false;
}
} else if (!CHECK_DIV_ZERO || vals[0] >= DELTA) {
return check(vals[1] / vals[0]);
} else {
return false;
}
case 3:
boolean flg = false;
double a, b, c;
if (vals[0] > vals[1]) {
if (vals[2] > vals[0]) {
a = vals[2];
b = vals[0];
c = vals[1];
} else {
a = vals[0];
if (vals[2] > vals[1]) {
b = vals[2];
c = vals[1];
} else {
b = vals[1];
c = vals[2];
}
}
} else {
if (vals[2] > vals[1]) {
a = vals[2];
b = vals[1];
c = vals[0];
} else {
a = vals[1];
if (vals[0] > vals[2]) {
b = vals[0];
c = vals[2];
} else {
b = vals[2];
c = vals[0];
}
}
}
flg |= check(a * (b + c));
if (!CHECK_DIV_ZERO || b - c >= DELTA)
flg |= check(a / (b - c));
if (!CHECK_DIV_ZERO || a - b >= DELTA)
flg |= check(c / (a - b));
if (!CHECK_DIV_ZERO || c >= DELTA) {
flg |= check((a + b) / c);
if (b > 1) {
if (c > 1)
flg |= check(a * b * c);
else
flg |= check(a * b / c);
} else if (!CHECK_DIV_ZERO || b >= DELTA){
flg |= check(a / b / c);
}
}
return flg;
default:
throw new RuntimeException();
}
}
private static boolean check(double v) {
c++;
// if (v < currentMax && v > DELTA) {
if (v > currentMax) {
currentMax = v;
System.out.println("current max is " + currentMax);
return true;
}
return false;
}
private static double removeFromVals(int i) {
numVals--;
double t = vals[i];
vals[i] = vals[numVals];
types[i] = types[numVals];
return t;
}
private static double removeFromVals2(int i, int r) {
assert i < r;
numVals--;
double t = vals[i];
vals[i] = vals[r - 1];
vals[r - 1] = vals[numVals];
types[i] = types[r - 1];
types[r - 1] = types[numVals];
return t;
}
private static void insertVal(int i, double v, int type) {
vals[numVals] = vals[i];
vals[i] = v;
types[numVals] = types[i];
types[i] = type;
numVals++;
}
private static void insertVal2(int i, int r, double v, int type) {
assert i <= r;
vals[numVals] = vals[r];
vals[r] = vals[i];
vals[i] = v;
types[numVals] = types[r];
types[r] = types[i];
types[i] = type;
numVals++;
}
private static void swap(int i1, int i2) {
if (i1 == i2) return;
double t = vals[i1];
vals[i1] = vals[i2];
vals[i2] = t;
int t2 = types[i1];
types[i1] = types[i2];
types[i2] = t2;
}
private static double abs(double v) {
return v > 0 ? v : -v;
}
public static void main(String args) {
long t = System.currentTimeMillis();
vals = new double {1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8};
run(10000);
t = System.currentTimeMillis() - t;
System.out.println("final result is " + currentMax);
System.out.println(t / 1000.0 + "sec");
System.out.println(c / 2);
System.out.println(((double)t) / c);
}
public static double run(int initMax) {
c = 0;
types = new int[vals.length];
currentMax = initMax;
numVals = vals.length;
search(0, 0, numVals);
return currentMax;
}
}
