leetcode-go/oj/360-2019-spring/24point.js

const eps = 0.000001

class Operation {
    constructor(val, rank, exp) {
        this.val = val
        this.rank = rank
        this.exp = exp
    }

    plus(that) {
        return new Operation(this.val + that.val, 0, `${this.exp}+${that.exp}`)
    }

    minus(that) {
        let exp
        if (that.rank === 0) exp = `${this.exp}-(${that.exp})`
        else exp = `${this.exp}-${that.exp}`
        return new Operation(this.val - that.val, 0, exp)
    }

    mult(that) {
        let exp
        if (this.rank === 0 && that.rank === 0) exp = `(${this.exp})*(${that.exp})`
        else if (this.rank === 0) exp = `(${this.exp})*${that.exp}`
        else if (that.rank === 0) exp = `${this.exp}*(${that.exp})`
        else exp = `${this.exp}*${that.exp}`
        return new Operation(this.val * that.val, 1, exp)
    }

    div(that) {
        let exp
        if (this.rank === 0 && that.rank !== 2) exp = `(${this.exp})/(${that.exp})`
        else if (this.rank === 0) exp = `(${this.exp})/${that.exp}`
        else if (that.rank !== 2) exp = `${this.exp}/(${that.exp})`
        else exp = `${this.exp}/${that.exp}`
        return new Operation(this.val / that.val, 1, exp)
    }
}

function solve24point(...numbers) {
    const nums = new Array(numbers.length)
    for (let i = 0; i < numbers.length; i++) {
        nums[i] = new Operation(numbers[i], 2, numbers[i])
    }
    return dfs(nums)
}

function dfs(nums) {
    if (nums.length === 1 && Math.abs(nums[0].val - 24.0) < eps) return nums[0].exp
    for (let i = 0; i < nums.length - 1; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            let next = new Array(nums.length - 2)
            for (let k = 0, idx = 0; k < nums.length; k++) {
                if (k == i || k == j) continue
                next[idx++] = nums[k]
            }
            let p = nums[i], q = nums[j]
            let tmp = [p.plus(q), p.minus(q), q.minus(p), p.mult(q)]
            if (q.val > 0) tmp.push(p.div(q))
            if (p.val > 0) tmp.push(q.div(p))
            for (let i = 0; i < tmp.length; i++) {
                next.push(tmp[i])
                const res = dfs(next)
                if (res !== null) return res
                next.pop()
            }
        }
    }
    return null
}

// eslint-disable-next-line no-console
const log = console.log.bind(console)

log(solve24point(2, 4, 1, 8))
log(solve24point(2, 4, 6, 8))
log(solve24point(1, 2, 5, 8))
log(solve24point(1, 7, 8, 8))
log(solve24point(6, 6, 6, 6, 6))
log(solve24point(1, 5, 5, 5))
log(solve24point(2, 5, 5, 10))
log(solve24point(1, 4, 5, 6))
log(solve24point(6, 9, 9, 10))