Qiitaでこちらの問題をみたので、解いてみました。
これをjsで解けと会社の上司に言われたんですが全然わからん。
— ケイセイ@JavaScriptと仲良くなりたい (@keisei_otsuka) 2020年2月2日
誰かわかります?笑 pic.twitter.com/ZM6VmigaVQ
アルゴリズム
考えることは大きく分けて以下の2つです。
- 1から9を1回ずつ使った組み合わせを列挙する
- 分数を計算して1かどうか確かめる
1から9を1回ずつ使った組み合わせを列挙する
こちらのアルゴリズムを利用して、1から9を1回ずつ使った組み合わせを列挙します。
分数を計算して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 } }
あとがき
急いで書いたので、変数名が微妙になってしまいました。