ｍake10パズルを解く

記事概要

JSでmake10パズルを解く。
make10とは ⇓

4桁の数字を一桁の数字4つとみなし、これに四則演算などを用いて10を作る遊び。

wikiより

スクリプト

const calcAll = (a, q) => {
    let ANSER_LIST = []

    // 配列入れ替え
    const shuffleArray = (inputArray) => {
        return inputArray.sort(() => Math.random() - 0.5)
    }

    // 2次元配列作成
    const arrayCreation = (q) => {
        let results = [q]

        for (const qIndex in q) {
            let _results = results
            results = []
            _results.forEach((qList) => {
                // 渡されたINDEXより後ろを固定して列を再作成
                const result = qList.slice(qIndex).map((v1, i1) => {
                    const r2 = qList.slice(qIndex).filter((v2, i2) => i2 != i1)
                    return qList.slice(0, qIndex).concat([v1]).concat(r2)
                })
                results = results.concat(result)
            })
        }

        // 重複排除
        results = [...new Set(results.map(JSON.stringify))].map(JSON.parse)

        return results
    }

    // 与えられた数字の組み合わせリスト
    let calcNumList = arrayCreation(q)

    // 毎回違う個体になるように配列のシャッフル
    calcNumList = shuffleArray(calcNumList)

    // 四則演算の組み合わせリスト
    const calcSymbolList = []
    for (let i = 0; i < 4 ** (q.length - 1); i++) {
        const d = (Array(q.length - 1).fill(0).join('') + String(i.toString(4))).slice(-(q.length - 1)).split('')
            .map(v => v = v.replace(/0/g, '+').replace(/1/g, '-').replace(/2/g, '*').replace(/3/g, '/'))
        calcSymbolList.push(d)
    }

    // 逆ポーランド記法から中置記法に変換（検算用）
    const rpnToInfix = (expression) => {
        const stack = []
        const isOperator = (token) => ['+', '-', '*', '/'].includes(token)
        const isHigherPrecedence = (op1, op2) => {
            const precedence = { '+': 1, '-': 1, '*': 2, '/': 2 }
            return precedence[op1] >= precedence[op2]
        }
        const tokens = expression.split('')
        for (const token of tokens) {
            if (!isOperator(token)) {
                // 数値の場合、そのままスタックにプッシュ
                stack.push(token)
            } else {
                // 演算子の場合、スタックから適切な数のオペランドをポップし、中置記法の形に変換してスタックにプッシュ
                const operand2 = stack.pop()
                const operand1 = stack.pop()
                const infixExpression = `(${operand1}${token}${operand2})`
                stack.push(infixExpression)
            }
        }
        return stack.pop()
    }

    calcNumList.some((v1, i1) => {
        calcSymbolList.some((v2, i2) => {
            // 計算式を作成
            let formulaString = v1[0]
            for (let i3 = 0; i3 < v2.length; i3++) {
                if (v2[i3] === '+') {
                    formulaString = `${formulaString}${v2[i3]}${v1[i3 + 1]}`
                } else if (v2[i3] === '-') {
                    formulaString = `${formulaString}${v2[i3]}${v1[i3 + 1]}`
                } else if (v2[i3] === '*') {
                    formulaString = `${formulaString}${v2[i3]}${v1[i3 + 1]}`
                } else if (v2[i3] === '/') {
                    formulaString = `${formulaString}${v2[i3]}${v1[i3 + 1]}`
                }
            }

            // 式を配列に
            const ary1 = formulaString.split('')

            // 四則演算のINDEX（奇数が四則演算）
            const ary2 = arrayCreation(ary1.reduce((l, v, i) => { if (i % 2) { l.push(i) }; return l }, []))

            ary2.some((ary3) => {
                const ary5 = formulaString.split('')
                // 逆ポーランド記法文字列に変換
                let polandStr = ''
                ary3.some((ary4, idx4) => {
                    const num1 = Number(ary5[ary4 - 1])
                    const num2 = Number(ary5[ary4 + 1])
                    if (num1 && num2) {
                        polandStr = idx4 === 0 ? `${num1}${num2}${ary5[ary4]}` : ary3[idx4] > ary3[idx4 - 1] ? `${polandStr}${num1}${num2}${ary5[ary4]}` : `${num1}${num2}${ary5[ary4]}${polandStr}`
                    } else if (num1) {
                        polandStr = `${num1}${polandStr}${ary5[ary4]}`
                    } else if (num2) {
                        polandStr = `${polandStr}${num2}${ary5[ary4]}`
                    } else {
                        polandStr = `${polandStr}${ary5[ary4]}`
                    }
                    ary5[ary4 - 1] = null
                    ary5[ary4 + 0] = null
                    ary5[ary4 + 1] = null
                })

                if (a === eval(rpnToInfix(polandStr))) {
                    ANSER_LIST.push([rpnToInfix(polandStr), polandStr])
                    return true
                }
            })
            if (ANSER_LIST.length > 0) {
                return true
            }
        })
        if (ANSER_LIST.length > 0) {
            return true
        }
    })
    // 重複排除
    ANSER_LIST = Array.from(new Set(ANSER_LIST))
    return ANSER_LIST
}

// const a = 19
// const q = [2, 3, 6, 6]
const a = 14
const q = [1, 3, 4, 8, 8, 9]
console.log('q =>', q)
console.log('a =>', a)
console.log('*************************************')
let r = calcAll(a, q)
console.log('r =>', r[0][0], '=', eval(r[0][0]))
console.log('*************************************')
r = calcAll(a, q)
console.log('r =>', r[0][0], '=', eval(r[0][0]))
console.log('*************************************')
r = calcAll(a, q)
console.log('r =>', r[0][0], '=', eval(r[0][0]))
console.log('*************************************')
r = calcAll(a, q)
console.log('r =>', r[0][0], '=', eval(r[0][0]))
console.log('*************************************')
r = calcAll(a, q)
console.log('r =>', r[0][0], '=', eval(r[0][0]))
console.log('*************************************')