「ピーターからの問題」1から9までを使って分数の穴埋め算。解答のJavaScriptプログラム

Qiitaでこちらの問題をみたので、解いてみました。

これをjsで解けと会社の上司に言われたんですが全然わからん。
誰かわかります？笑 pic.twitter.com/ZM6VmigaVQ

— ケイセイ＠JavaScriptと仲良くなりたい (@keisei_otsuka) 2020年2月2日

アルゴリズム

考えることは大きく分けて以下の2つです。

1. 1から9を1回ずつ使った組み合わせを列挙する
2. 分数を計算して1かどうか確かめる

1から9を1回ずつ使った組み合わせを列挙する

こちらのアルゴリズムを利用して、1から9を1回ずつ使った組み合わせを列挙します。

yucatio.hatenablog.com

分数を計算して1かどうか確かめる

今回、分数の計算が必要に思えますが、式を以下のように変形すれば、分数を使わずとも解けることがわかります。

a/x + b/y + c/z = 1
// ↓
a*y*z + b*x*z + c*x*y = x*y*z

下準備

各マスに番号をふっておきます。配列のインデックスに対応します。

1から9までの数字を格納している配列をnとすると、解く式は以下のように書けます。

n[0]/(n[1] * 10 + n[2]) + n[3]/(n[4] * 10 + n[5]) + n[6]/(n[7] * 10 + n[8]) = 1

コード

/**
 * 配列の順列を列挙するジェネレータ
 */
function* arrayEnumerator(numArr){
  yield [...numArr]
  while(true) {
    // numArr[i] < numArr[i-1] となるiを探す
    const changeIndex1 = numArr.findIndex((value, i , arr) => i >=1 && arr[i-1] > value)
    if (changeIndex1 < 0) {
      break
    }
    const changeNumber1 = numArr[changeIndex1]
    const newOrderArr = numArr.slice(0, changeIndex1)
    // changeNumber1 より下位の桁で、changeNumber1 より大きい数字のうち、最小のものを探す
    const changeNumber2 = Math.min(...newOrderArr.filter(value => value > changeNumber1))
    const changeIndex2 = newOrderArr.indexOf(changeNumber2)
    // changeNumber1とchangeNumber2入れ替える
    // 下位桁はreverseする
    newOrderArr[changeIndex2] = changeNumber1
    numArr = [...newOrderArr.reverse(), changeNumber2, ...numArr.slice(changeIndex1 + 1)]
    yield [...numArr]
  }
}


const enumerator = arrayEnumerator([9, 8, 7, 6, 5, 4, 3, 2, 1])

for(let n of enumerator){
  // denominators(分母)
  const denomi = [10 * n[1] + n[2], 10 * n[4] + n[5], 10 * n[7] + n[8]]
  // 左辺
  const left = n[0] * denomi[1] * denomi[2] + n[3] * denomi[0] * denomi[2] + n[6] * denomi[0] * denomi[1]
  // 右辺
  const right = denomi.reduce((acc, cur) => acc * cur , 1)
  if (left === right) {
    console.log(`${n[0]}/${n[1]}${n[2]} + ${n[3]}/${n[4]}${n[5]} + ${n[6]}/${n[7]}${n[8]} equals to 1`)
    break
  }
}

あとがき

急いで書いたので、変数名が微妙になってしまいました。