4つの数字で10を作るテンパズル・メイクテン（JavaScript編）

[テンパズル](https://ja.wikipedia.org/wiki/%E3%83%86%E3%83%B3%E3%83%91%E3%82%BA%E3%83%AB) (10パズル) 、メイクテン (make 10) と呼ばれる数遊びをご存じですか？与えられた4つの数字を全て使って、四則演算（足し算、引き算、かけ算、割り算）で10を作れたら勝ちです。例えば、4211なら 4x2+1+1 で10を作れます。数字を入れ替えても構いません。

2013年に Google Nexus7 のCM「1,1,5,8で10を作る」で有名になりました。小学生でもできる、暇つぶしに持ってこいのクイズです。車での旅行なら対向車のナンバープレートを、電車での旅行なら切符に印字された数字を使って遊んでいました。交通系ICカードがなかった時代の話です。

与えられた数字で10が作れるか判定し、その時の解法を表示するJavaScriptのコードをChatGPT（GPT-4）に書いてもらいました。1234で10が作れるか、make 10?ボタンを押してみてください。別の数字も試せます。

<p class="codepen" data-height="300" data-default-tab="result" data-slug-hash="GRYregz" data-user="takatama" style="height: 300px; box-sizing: border-box; display: flex; align-items: center; justify-content: center; border: 2px solid; margin: 1em 0; padding: 1em;">
  <span>See the Pen <a href="https://codepen.io/takatama/pen/GRYregz">
  make10</a> by Hirokazu Takatama (<a href="https://codepen.io/takatama">@takatama</a>)
  on <a href="https://codepen.io">CodePen</a>.</span>
</p>
<script async src="https://cpwebassets.codepen.io/assets/embed/ei.js"></script>

# 4つの数字で10が作れるかを判定する

`makeTen`関数は与えられた4つの数字で10が作れるか判定し、その時の解法を表示します。10を作れない場合は`Not Possible`と表示します。

例えば`makeTen(1,1,9,9)`は`'((1 / 9) + 1) * 9'`になります。

```javascript
function makeTen(a, b, c, d) {
  const nums = [a, b, c, d];
  const ops = ['+', '-', '*', '/'];

  function calc(op, x, y) {
    if (op === '+') return x + y;
    if (op === '-') return x - y;
    if (op === '*') return x * y;
    if (op === '/') return x / y;
  }

  for (let i = 0; i < 4; i++) {
    for (let j = 0; j < 4; j++) {
      if (j === i) continue;
      for (let k = 0; k < 4; k++) {
        if (k === i || k === j) continue;
        for (let l = 0; l < 4; l++) {
          if (l === i || l === j || l === k) continue;
          for (const op1 of ops) {
            for (const op2 of ops) {
              for (const op3 of ops) {
                const results = [
                  calc(op1, nums[i], calc(op2, nums[j], calc(op3, nums[k], nums[l]))),
                  calc(op1, nums[i], calc(op3, calc(op2, nums[j], nums[k]), nums[l])),
                  calc(op3, calc(op1, nums[i], nums[j]), calc(op2, nums[k], nums[l])),
                  calc(op2, calc(op1, nums[i], nums[j]), calc(op3, nums[k], nums[l])),
                  calc(op3, calc(op1, nums[i], nums[j]), calc(op2, nums[k], nums[l])),
                  calc(op3, calc(op2, calc(op1, nums[i], nums[j]), nums[k]), nums[l]),
                ];

                for (let resultIndex = 0; resultIndex < results.length; resultIndex++) {
                  if (Math.abs(results[resultIndex] - 10) < 1e-9) {
                    switch (resultIndex) {
                      case 0:
                        return `${nums[i]} ${op1} (${nums[j]} ${op2} (${nums[k]} ${op3} ${nums[l]}))`;
                      case 1:
                        return `${nums[i]} ${op1} ((${nums[j]} ${op2} ${nums[k]}) ${op3} ${nums[l]})`;
                      case 2:
                        return `(${nums[i]} ${op1} ${nums[j]}) ${op3} (${nums[k]} ${op2} ${nums[l]})`;
                      case 3:
                        return `(${nums[i]} ${op1} ${nums[j]}) ${op2} (${nums[k]} ${op3} ${nums[l]})`;
                      case 4:
                        return `(${nums[i]} ${op1} ${nums[j]}) ${op3} (${nums[k]} ${op2} ${nums[l]})`;
                      case 5:
                        return `((${nums[i]} ${op1} ${nums[j]}) ${op2} ${nums[k]}) ${op3} ${nums[l]}`;
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }

  return 'Not possible';
}
```

# 4つの数字で10を作る解法がいくつあるかを計算する

次に、与えられた4つの数字に対して解法がいくつあるかを計算してもらいました。ここで注意が必要なのが、足し算と掛け算は計算する順番を入れ替えても同じ結果になる（交換法則を満たす）点です。交換法則を適用すると等価になる解法はカウントしないことにしました。

ただ、この条件をChatGPTに提示するのが難しかったため、先に「数式を与えると、それと等価な数式をすべて表示する」アルゴリズムを作りました。

例えば`generateEquivalentExpressions(makeTen(1,1,9,9))`は、次の4つの等価な数式を表示します。

- `((1 / 9) + 1) * 9`
- `9 * ((1 / 9) + 1)`
- `(1 + (1 / 9)) * 9`
- `9 * (1 + (1 / 9))`

```javascript
function parseExpression(expr) {
  let stack = [[]];
  let number = '';
  for(const char of expr) {
    if (/\d/.test(char)) {
      number += char;
    } else if (['+','*','(',')','-','/'].includes(char)) {
      if (number) {
        stack[stack.length - 1].push(number);
        number = '';
      }
      if (char === '(') {
        stack.push([]);
      } else if (char === ')') {
        const inner = stack.pop();
        stack[stack.length - 1].push(inner);
      } else {
        stack[stack.length - 1].push(char);
      }
    }
  }
  if (number) {
    stack[stack.length - 1].push(number);
  }
  return stack[0];  
}

function generateCombinations(expr) {
  if (expr.length === 1) return expr;

  let results = [];

  if (expr.length === 3) {
    let left = generateCombinations(expr[0]);
    let right = generateCombinations(expr[2]);

    for (let l of left) {
      for (let r of right) {
        results.push([l, expr[1], r]);
        if (expr[1] === "+" || expr[1] === "*") {
          results.push([r, expr[1], l]);
        }
      }
    }
  }

  return results;
}

function reconstructExpression(elements) {
  const left = elements[0].length === 1 ? elements[0][0] : '(' + reconstructExpression(elements[0]) + ')';
  const right = elements[2].length === 1 ? elements[2][0] : '(' + reconstructExpression(elements[2]) + ')';
  return `${left} ${elements[1]} ${right}`;
}

function generateEquivalentExpressions(expression) {
  let parsedExpression = parseExpression(expression);
  let combinations = generateCombinations(parsedExpression);
  let equivalentExpressions = new Set();

  for (let combo of combinations) {
    equivalentExpressions.add(reconstructExpression(combo));
  }

  return Array.from(equivalentExpressions);
}
```

次に、すべての解法を出力する`makeTenAllSolutions`関数を作りました。先ほどの`generateEquivalentExpressions`関数を使って、等価な解法はカウントしないようにしてあります。

例えば`makeTenAllSolutions(1,1,9,9)`の結果は、`['((1 / 9) + 1) * 9']`の1つだけになります。

```javascript
function makeTenAllSolutions(a, b, c, d) {
  const nums = [a, b, c, d];
  const ops = ['+', '-', '*', '/'];
  const solutions = new Set();

  function calc(op, x, y) {
    if (op === '+') return x + y;
    if (op === '-') return x - y;
    if (op === '*') return x * y;
    if (op === '/') return x / y;
  }

  function isEquivalent(expr1, expr2) {
    const equivalentExpressions = generateEquivalentExpressions(expr1);
    return equivalentExpressions.includes(expr2);
  }

  function isNewSolution(solution) {
    for (const existingSolution of solutions) {
      if (isEquivalent(solution, existingSolution)) {
        return false;
      }
    }
    return true;
  }

  for (let i = 0; i < 4; i++) {
    for (let j = 0; j < 4; j++) {
      if (j === i) continue;
      for (let k = 0; k < 4; k++) {
        if (k === i || k === j) continue;
        for (let l = 0; l < 4; l++) {
          if (l === i || l === j || l === k) continue;
          for (const op1 of ops) {
            for (const op2 of ops) {
              for (const op3 of ops) {
                const results = [
                  calc(op1, nums[i], calc(op2, nums[j], calc(op3, nums[k], nums[l]))),
                  calc(op1, nums[i], calc(op3, calc(op2, nums[j], nums[k]), nums[l])),
                  calc(op3, calc(op1, nums[i], nums[j]), calc(op2, nums[k], nums[l])),
                  calc(op2, calc(op1, nums[i], nums[j]), calc(op3, nums[k], nums[l])),
                  calc(op3, calc(op1, nums[i], nums[j]), calc(op2, nums[k], nums[l])),
                  calc(op3, calc(op2, calc(op1, nums[i], nums[j]), nums[k]), nums[l]),
                ];

                for (let resultIndex = 0; resultIndex < results.length; resultIndex++) {
                  if (Math.abs(results[resultIndex] - 10) < 1e-9) {
                    let solution;
                    switch (resultIndex) {
                      case 0:
                        solution = `${nums[i]} ${op1} (${nums[j]} ${op2} (${nums[k]} ${op3} ${nums[l]}))`;
                        break;
                      case 1:
                        solution = `${nums[i]} ${op1} ((${nums[j]} ${op2} ${nums[k]}) ${op3} ${nums[l]})`;
                        break;
                      case 2:
                        solution = `(${nums[i]} ${op1} ${nums[j]}) ${op3} (${nums[k]} ${op2} ${nums[l]})`;
                        break;
                      case 3:
                        solution = `(${nums[i]} ${op1} ${nums[j]}) ${op2} (${nums[k]} ${op3} ${nums[l]})`;
                        break;
                      case 4:
                        solution = `(${nums[i]} ${op1} ${nums[j]}) ${op3} (${nums[k]} ${op2} ${nums[l]})`;
                        break;
                      case 5:
                        solution = `((${nums[i]} ${op1} ${nums[j]}) ${op2} ${nums[k]}) ${op3} ${nums[l]}`;
                        break;
                    }

                    if (isNewSolution(solution)) {
                      solutions.add(solution);
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }

  if (solutions.size === 0) {
    return 'Not possible';
  }

  return Array.from(solutions);
}
```

この`makeTenAllSolutions`関数を使って、0000から9999までの4つの数字に対して解法がいくつあるかを表示します。ただし、4つの数字を並び替えたもの（例えば、1158と1185）は解法の数が同じになるため出力しません。

```javascript
function countSolutions() {
  const calculatedSolutions = new Map();

  function getKey(a, b, c, d) {
    const sorted = [a, b, c, d].sort((x, y) => x - y);
    return sorted.join('');
  }

  let results = [];

  for (let a = 0; a <= 9; a++) {
    for (let b = 0; b <= 9; b++) {
      for (let c = 0; c <= 9; c++) {
        for (let d = 0; d <= 9; d++) {
          const key = getKey(a, b, c, d);
          if (calculatedSolutions.has(key)) {
            continue;
          } else {
            const solutions = makeTenAllSolutions(a, b, c, d);
            const count = solutions === 'Not possible' ? 0 : solutions.length;
            calculatedSolutions.set(key, count);
            results.push({
              numbers: `${a}${b}${c}${d}`,
              count,
            });
          }
        }
      }
    }
  }

  return results;
}

function displaySolutions() {
  const solutionCounts = countSolutions();
  const count = {};
  solutionCounts.forEach(item => {
    if (!count[item.count]) {
      count[item.count] = [];
    }
    count[item.count].push(item.numbers);
  });
  const result = ['| pattens | count | numbers |', '|---|---|---|'];
  Object.entries(count).forEach(entry => result.push(`| ${entry[0]} | ${entry[1].length} | ${entry[1].join(', ')} |`)); 
  console.log(result.join('\n'));
}

displaySolutions();
```

この記事の末尾に、結果の表を掲載します。解法の数ごとに分類しました。0000から9999の715通りのうち、10にならない4桁の数字は163通り、10になるものは552通りです。

# 難問を抽出する

テンパズルにおける難問の定義は難しいのですが、ここでは、解法が1パターンのみで、割り算を使い、割り算部分の計算が整数にならないもの、とします。

`findDifficultProblems(singleSolutionNumbers)`の結果は`['1158', '1199', '1337', '3478']`の4通りとなりました。それぞれの解法は次の通りです。

| numbers | solution |
|---|---|
| 1158 | 8 / (1 - (1 / 5)) |
| 1199 | ((1 / 9) + 1) * 9 |
| 1337 | 3 * (1 + (7 / 3)) |
| 3478 | 8 * (3 - (7 / 4)) |

```javascript
function displayDifficultProblems() {
  const singleSolutionNumbers = [1114, 1116, 1149, 1158, 1167, 1189, 1199, 1337, 1388, 1555, 1566, 1599, 2289, 2666, 3333, 3357, 3366, 3377, 3466, 3478, 3577, 3588, 4449, 4466, 4467, 4559, 4679, 5557, 5559, 5679, 5778, 7778, 7779, 7889, 7899, 8888, 8889, 8999, 9999];

  function isDifficult(expression) {
    const divisionRegex = /(\d+\s*\/\s*\d+)/g;
    const divisions = expression.match(divisionRegex);

    if (!divisions) {
      return false;
    }

    for (const division of divisions) {
      const [numerator, denominator] = division.split('/').map((num) => Number(num.trim()));
      if (numerator % denominator !== 0) {
        return true;
      }
    }

    return false;
  }

  function getKey(a, b, c, d) {
    const sorted = [a, b, c, d].sort((x, y) => x - y);
    return sorted.join('');
  }

  function findDifficultProblems(numbers) {
    const difficultProblems = new Set();

    for (const number of numbers) {
      const [a, b, c, d] = number.toString().split('').map(Number);
      const key = getKey(a, b, c, d);

      if (difficultProblems.has(key)) {
        continue;
      }

      const solutions = makeTenAllSolutions(a, b, c, d);

      if (solutions !== 'Not possible' && isDifficult(solutions[0])) {
        difficultProblems.add(key);
      }
    }

    return Array.from(difficultProblems);
  }

  console.log(findDifficultProblems(singleSolutionNumbers));
}
```
# ChatGPT（GPT-4）を使ってみて

`makeTen`関数はすぐに作れたのですが、解法のカウントはどうしても正しい答えにならず、人間がコードを書きました。make10は有名でインターネットに公開されていたので、それを学習したのかも知れません。

なおChatGPTは自信満々で間違った解答をするので、検算が欠かせません。検算に使うデータはこちらのサイトにお世話になりました。

https://www.quiz-puzzle.com/make10/answer/list.html

ChatGPTをうまく使いこなすには、やりたいことを言語化する力や、大局的に考えつつ、問題を分解する力が重要だと感じました。指示を繰り返しているうちに袋小路に入ってしまい、欲しいアルゴリズムにたどり着けなくなることが度々あったためです。
とはいえ、ChatGPTのおかげで、思いついたことを形にするまでの「気の重さ」は軽減し、気楽に試行錯誤できるようになったと感じています。

# 解法の数による分類

4つの数字で10を作る解法がいくつあるか、解法の数で分類した結果です。

| pattens | count | numbers |
|---|---|---|
| 0 | 163 | 0000, 0001, 0002, 0003, 0004, 0005, 0006, 0007, 0008, 0009, 0011, 0012, 0013, 0014, 0015, 0016, 0017, 0018, 0022, 0023, 0024, 0026, 0027, 0029, 0033, 0034, 0035, 0036, 0038, 0039, 0044, 0045, 0047, 0048, 0049, 0056, 0057, 0058, 0059, 0066, 0067, 0068, 0069, 0077, 0078, 0079, 0088, 0089, 0099, 0111, 0112, 0113, 0114, 0116, 0117, 0122, 0123, 0134, 0144, 0148, 0157, 0158, 0166, 0167, 0168, 0177, 0178, 0188, 0222, 0233, 0236, 0269, 0277, 0279, 0299, 0333, 0335, 0336, 0338, 0344, 0345, 0348, 0359, 0366, 0369, 0388, 0389, 0399, 0444, 0445, 0447, 0448, 0457, 0478, 0479, 0489, 0499, 0566, 0567, 0577, 0588, 0589, 0599, 0666, 0667, 0668, 0677, 0678, 0689, 0699, 0777, 0778, 0788, 0799, 0888, 1111, 1112, 1113, 1122, 1159, 1169, 1177, 1178, 1179, 1188, 1399, 1444, 1499, 1666, 1667, 1677, 1699, 1777, 2257, 3444, 3669, 3779, 3999, 4444, 4459, 4477, 4558, 4899, 4999, 5668, 5788, 5799, 5899, 6666, 6667, 6677, 6777, 6778, 6888, 6899, 6999, 7777, 7788, 7789, 7799, 7888, 7999, 8899 |
| 1 | 39 | 1114, 1116, 1149, 1158, 1167, 1189, 1199, 1337, 1388, 1555, 1566, 1599, 2289, 2666, 3333, 3357, 3366, 3377, 3466, 3478, 3577, 3588, 4449, 4466, 4467, 4559, 4679, 5557, 5559, 5679, 5778, 7778, 7779, 7889, 7899, 8888, 8889, 8999, 9999 |
| 2 | 15 | 1168, 1277, 1288, 1336, 2222, 2279, 2299, 2477, 3339, 4888, 5889, 6678, 6779, 6788, 6889 |
| 3 | 19 | 1222, 1269, 1347, 1479, 1778, 1888, 2266, 2557, 2777, 3336, 3344, 3349, 3477, 3555, 4448, 4889, 6688, 6689, 6799 |
| 4 | 13 | 1117, 1123, 1279, 1378, 1445, 2226, 2278, 2334, 2499, 3559, 4478, 4779, 6669 |
| 5 | 28 | 1333, 1338, 1447, 1556, 1668, 2333, 2339, 2399, 2669, 2999, 3334, 3449, 3488, 3558, 3888, 4447, 4569, 4577, 4669, 4777, 4788, 5558, 5669, 5699, 5777, 5888, 5999, 6699 |
| 6 | 20 | 1134, 1144, 1259, 1299, 1346, 1389, 1455, 1466, 2223, 2227, 2358, 2367, 2388, 3335, 3367, 3399, 3467, 3499, 5568, 5579 |
| 7 | 8 | 1567, 1589, 2245, 2267, 2377, 3338, 3368, 5677 |
| 8 | 14 | 1448, 1489, 2355, 3378, 3389, 3666, 3679, 3688, 3899, 4445, 4469, 4588, 5688, 6789 |
| 9 | 15 | 0115, 1133, 2224, 2229, 2248, 2368, 2688, 3556, 4488, 4668, 4799, 5569, 5578, 5789, 6668 |
| 10 | 17 | 0455, 0555, 0556, 0558, 1115, 1166, 1278, 1289, 1446, 1457, 2233, 2235, 2447, 2779, 3358, 4499, 5666 |
| 11 | 13 | 0133, 1558, 2446, 2455, 2578, 2667, 3388, 3459, 4489, 4555, 5556, 5567, 5589 |
| 12 | 14 | 0124, 0223, 0225, 0247, 0256, 0259, 1379, 1488, 1557, 2244, 3369, 3448, 3789, 4579 |
| 13 | 12 | 1233, 2234, 2269, 2277, 2456, 2788, 2799, 3677, 3699, 4566, 4599, 4689 |
| 14 | 24 | 0126, 0135, 0224, 0227, 0229, 0249, 0267, 0339, 0449, 0488, 0568, 0579, 0669, 0779, 0889, 0999, 1223, 2249, 2288, 2366, 2389, 2449, 2559, 3578 |
| 15 | 7 | 1124, 1255, 1369, 2236, 2444, 2889, 3347 |
| 16 | 27 | 0139, 0149, 0159, 0169, 0179, 0189, 0199, 0228, 0237, 0246, 0278, 0288, 0337, 0346, 0347, 0357, 0377, 0378, 0466, 0467, 0469, 1345, 1799, 2256, 3356, 4568, 5555 |
| 17 | 15 | 1139, 1157, 1228, 1377, 2379, 2467, 2478, 2489, 2579, 2678, 2699, 3599, 3668, 3778, 4557 |
| 18 | 9 | 1118, 1246, 2469, 2556, 2689, 3345, 3379, 3479, 4667 |
| 19 | 14 | 1148, 1344, 1456, 1588, 1788, 2247, 3348, 3889, 4457, 4479, 4778, 5667, 5779, 6679 |
| 20 | 8 | 1224, 1335, 2238, 2337, 2344, 3445, 3468, 4458 |
| 21 | 5 | 1135, 1237, 1577, 2488, 3455 |
| 22 | 4 | 0255, 2677, 3457, 4468 |
| 23 | 1 | 2359 |
| 24 | 7 | 0557, 0559, 1225, 1366, 2357, 3359, 3589 |
| 25 | 5 | 1126, 1334, 2259, 3446, 3566 |
| 26 | 11 | 0234, 0368, 0446, 2239, 2268, 2458, 2468, 2568, 3567, 4456, 4678 |
| 27 | 5 | 1244, 1355, 1477, 1688, 2336 |
| 28 | 5 | 0118, 0244, 0258, 0289, 0334 |
| 29 | 8 | 1268, 1689, 2258, 4455, 5566, 5577, 5588, 5599 |
| 30 | 7 | 0238, 0379, 0456, 1266, 1359, 1469, 2346 |
| 31 | 2 | 2255, 3355 |
| 32 | 5 | 1136, 2888, 3337, 3777, 4666 |
| 33 | 10 | 1127, 1467, 1478, 1678, 2466, 3579, 3678, 4446, 4589, 5689 |
| 34 | 3 | 2459, 2789, 3489 |
| 35 | 9 | 0266, 0477, 0688, 0899, 1348, 2347, 2348, 2555, 4789 |
| 36 | 2 | 0355, 3568 |
| 37 | 5 | 1145, 1227, 1258, 2378, 2569 |
| 38 | 3 | 1357, 2225, 4567 |
| 39 | 4 | 1999, 2228, 3458, 3569 |
| 40 | 3 | 0055, 3469, 4578 |
| 41 | 3 | 1256, 1579, 2479 |
| 42 | 3 | 0268, 1226, 3689 |
| 43 | 3 | 1267, 2356, 2369 |
| 44 | 3 | 1155, 2589, 5678 |
| 45 | 1 | 1899 |
| 46 | 5 | 1234, 1238, 1249, 1568, 2679 |
| 47 | 3 | 1247, 2349, 2457 |
| 48 | 14 | 0025, 0127, 0136, 0145, 0356, 0458, 1156, 1236, 2566, 2599, 3447, 3667, 3799, 4699 |
| 49 | 8 | 1138, 1147, 1235, 2558, 2588, 2899, 3557, 4556 |
| 50 | 5 | 2237, 2567, 2577, 3788, 4677 |
| 51 | 3 | 0226, 2778, 3346 |
| 53 | 2 | 1578, 2335 |
| 54 | 3 | 1257, 2338, 2445 |
| 55 | 9 | 0155, 1119, 1229, 1339, 1368, 1449, 1559, 1779, 1889 |
| 56 | 3 | 1367, 1669, 4688 |
| 57 | 3 | 1358, 1468, 2345 |
| 58 | 1 | 1129 |
| 60 | 2 | 0235, 2668 |
| 62 | 12 | 0138, 0147, 0156, 0239, 0349, 0358, 0459, 0569, 0578, 0679, 0789, 1789 |
| 63 | 1 | 2448 |
| 64 | 2 | 1349, 1679 |
| 65 | 1 | 1239 |
| 66 | 3 | 1248, 1569, 2246 |
| 67 | 5 | 0019, 0028, 0037, 0046, 3456 |
| 70 | 1 | 1459 |
| 72 | 3 | 1128, 1137, 1146 |
| 74 | 3 | 0245, 0257, 1356 |
| 75 | 1 | 1125 |
| 78 | 3 | 0129, 0367, 0468 |
| 90 | 1 | 0125 |
| 91 | 1 | 0119 |
| 92 | 1 | 0248 |
| 94 | 3 | 0128, 0137, 0146 |
| 96 | 1 | 1458 |
| 109 | 1 | 1245 |