東急線のドア広告に貼ってあった問題。東急グループがエンジニアを募集する広告のようだ。デザイナーだが面白そうなので解く。
四則演算のみを用いて下記の4つの数字で10を作ることはできますか。例：1+(0×8)+9=10
1,3,3,7
また、任意の0〜9の4つの数字で、上記同様の10を作る問いが与えられたとき、その解法を出力するプログラムを作ることはできますか。
最初の1,3,3,7についてはしばらく暗算してたがわからなかった。こういうときは答えのある問題を出すものだと思ったので、総当たりのプログラムを考えることにする。JavaScriptで書いた。
思考の筋道を書き残すため、書いた順に記すことにする。
最初のプログラム
最初に書いたのが以下である（なにも参考にならないので折りたたんでおく）。めちゃめちゃだが、答えは出た。
ひたすらforで回して、計算順も強引に「( )」をつけた。
JavaScript
if (!Array.prototype.append) {
Array.prototype.append = function(index, element) {
return this.splice(index + 1, 0, element);
};
Array.prototype.prepend = function(index, element) {
return this.splice(index, 0, element);
};
}
let nums = [1,3,3,7];
let operators = ["+", "-", "*", "/"];
var getAllAnswer = function () {
var a = [];
for (var i = 0; i < 4; i++) {
var n1 = nums[i];
for (var j = 0; j < 4; j++) {
var o1 = operators[j];
for (var i2 = 0; i2 < 4; i2++) {
if (i2 == i) continue;
var n2 = nums[i2];
for (var j2 = 0; j2 < 4; j2++) {
var o2 = operators[j2];
for (var i3 = 0; i3 < 4; i3++) {
if (i3 == i || i3 == i2) continue;
var n3 = nums[i3];
for (var i4 = 0; i4 < 4; i4++) {
if (i4 == i || i4 == i2 || i4 == i3) continue;
var n4 = nums[i4];
for (var j3 = 0; j3 < 4; j3++) {
var o3 = operators[j3];
var n = [n1, o1, n2, o2, n3, o3, n4];
// a.push(n);
// brackets
// 0(n1) 1(n2) 2(n3) 3(n4)
var bp = [
[[0,1],[2,3],[0]],
[[0,2],[0,1],[-1]],
[[0,2],[1,2],[-1]],
[[1,3],[1,2],[-1]],
[[1,3],[2,3],[-1]]
];
for (var p = 0; p < bp.length; p++) {
var pp = bp[p];
var r = {};
var nn = n.slice();
for (var p2 = 0; p2 < pp.length - 1; p2++) {
var pp2 = pp[p2];
if (pp2.length) {
if (p2 == 0) {
nn.prepend(pp2[0] * 2, "(");
nn.append( pp2[1] * 2 + 1, ")");
}
else {
nn.prepend(pp2[0] * 2 + 2 + pp[2][0], "(");
nn.append( pp2[1] * 2 + 3 + pp[2][0], ")");
}
}
}
var fml = nn.join(' ');
var res = Function('return parseFloat(' + fml + ')')();
var f = `${fml} = ${res}`;
// res === 10 && console.log(`${f}`);
r.n = nn;
r.answer = res;
r.formula = f;
console.log(f);
a.push(r);
}
}
}
}
}
}
}
}
return a;
};
var arr = getAllAnswer();
console.log(JSON.stringify(arr));
任意の数字に対応するバージョン
答えは出るようなので、このままで２つ目の「任意の4つの数字」に対応するバージョンにする。
（やはり折りたたんでおく）
基本的な部分は同じ。
var getAnswer = (n1, n2, n3, n4) => {
const operators = ["+", "-", "*", "/"];
const bp = [
[[0,1],[2,3],[0]],
[[0,2],[0,1],[-1]],
[[0,2],[1,2],[-1]],
[[1,3],[1,2],[-1]],
[[1,3],[2,3],[-1]]
];
let nums = [n1, n2, n3, n4];
let a = [];
for (let i = 0; i < 4; i++) {
let n1 = nums[i];
for (let j = 0; j < 4; j++) {
let o1 = operators[j];
for (let i2 = 0; i2 < 4; i2++) {
if (i2 == i) continue;
let n2 = nums[i2];
for (let j2 = 0; j2 < 4; j2++) {
let o2 = operators[j2];
for (let i3 = 0; i3 < 4; i3++) {
if (i3 == i || i3 == i2) continue;
let n3 = nums[i3];
for (let i4 = 0; i4 < 4; i4++) {
if (i4 == i || i4 == i2 || i4 == i3) continue;
let n4 = nums[i4];
for (let j3 = 0; j3 < 4; j3++) {
let o3 = operators[j3];
let r = {};
let n = [n1, o1, n2, o2, n3, o3, n4];
for (var p = 0; p < bp.length; p++) {
var pp = bp[p];
var nn = n.slice();
for (var p2 = 0; p2 < pp.length - 1; p2++) {
var pp2 = pp[p2];
if (pp2.length) {
if (p2 == 0) {
nn.prepend(pp2[0] * 2, "(");
nn.append( pp2[1] * 2 + 1, ")");
}
else {
nn.prepend(pp2[0] * 2 + 2 + pp[2][0], "(");
nn.append( pp2[1] * 2 + 3 + pp[2][0], ")");
}
}
}
let fml = nn.join(' ');
let res = Function('return parseFloat(' + fml + ')')();
let f = `${fml} = ${res}`;
res == 10 && (a.push(r), console.log(`${f}`));
}
}
}
}
}
}
}
}
a.length == 0 && (a = ["no answer found."], console.log(`${a[0]}`));
return a;
};
for (var i = 0; i < 5; i++) {
let n1 = Math.floor(Math.random() * 10);
let n2 = Math.floor(Math.random() * 10);
let n3 = Math.floor(Math.random() * 10);
let n4 = Math.floor(Math.random() * 10);
console.log(n1, n2, n3, n4);
getAnswer(n1, n2, n3, n4);
}
書き直した
あまりにもスパゲッティなので、もうすこしちゃんと書き直すことにする。
ちなみに、このような問題は「メイク10パズル」というものらしい。ググってみるとだいたい総当りのプログラムで解いているようなので、基本方針は問題ないようだ。
数値は順列の処理で、演算子は重複順列の処理で行う。pythonのitertoolsにpermutationsとproductというおあつらえ向きのものがあったので、これをJavaScriptにポートしたようなものを探した。
また、計算順序のパターンが少ないなら、テンプレートを使えばいいのかと思い至る。
JavaScript
class Make10 {
static get formulas() {
return [
"((${n1} ${o1} ${n2}) ${o2} ${n3} ) ${o3} ${n4}",
"(${n1} ${o1} ${n2}) ${o2} (${n3} ${o3} ${n4})",
"(${n1} ${o1} (${n2} ${o2} ${n3})) ${o3} ${n4}",
"${n1} ${o1} ((${n2} ${o2} ${n3}) ${o3} ${n4})",
"${n1} ${o1} (${n2} ${o2} (${n3} ${o3} ${n4}))"
];
}
static get operators() {
return "+-*/".split('');
}
constructor(numbers=[1,3,3,7], gen10Only = false) {
this.numbers = numbers;
this.gen10Only = gen10Only;
}
calc() {
var numbers = this.permutations(this.numbers);
var operators = this.product(Make10.operators, 3);
var formulas = Make10.formulas;
var results = [];
numbers.forEach((n, i) => {
operators.forEach((o, j) => {
let no = {
n1: n[0], n2: n[1], n3: n[2], n4: n[3],
o1: o[0], o2: o[1], o3: o[2]
};
formulas.forEach(f => {
let formula = f.replace(/\${(.*?)}/g, (m, p) => {
return no[p];
});
let result = Function('return parseFloat(' + formula + ')')();
let r = {
formula: formula,
result: result,
isTen: (result === 10)
};
if (this.gen10Only) {
if (r.isTen) {
results.push(r);
}
}
else {
results.push(r);
}
});
});
});
return results;
}
permutations(input) {
let result = [];
const _f = (arr, m = []) => {
if (arr.length === 0) {
result.push(m)
}
else {
for (let i = 0; i < arr.length; i++) {
let curr = arr.slice();
let next = curr.splice(i, 1);
_f(curr.slice(), m.concat(next))
}
}
}
_f(input);
return result;
}
product(input, repeat=1) {
let result = [];
const _f = (arr, repeat) => {
var cp = [];
for (var i = 0; i < repeat; i++) {
cp.push(arr.slice());
}
result = cp.reduce(function tl(acc, val) {
var tmp = [];
acc.forEach(function(e1) {
val.forEach(function(e2) {
tmp.push(e1.concat(e2));
});
});
return tmp;
}, [[]]);
};
_f(input, repeat);
return result;
}
}
let r1 = new Make10([1,3,3,7], true).calc();
console.log(r1);
この問題では４つの数字に同じ数がある（3が2つある）ので、同じ式が２つできてしまう。しかしもうお腹いっぱいだ。