BurstBubbles.js

burstbubbles.js

// VALUES = [3, 1, 5, 8], EXPECTED_SCORE = 167
// VALUES = [ 9, 76, 64, 21, 97, 60 ], EXPECTED_SCORE = 1086136
VALUES = [35, 16, 83, 87, 84, 59, 48, 41, 20, 54], EXPECTED_SCORE = 1849648

// maxCoins = maximizeScoreViaSorting
// maxCoins = maximizeScoreViaThrees
maxCoins = maximizeScoreViaRecursion

console.log("Score:", maxCoins(VALUES))
console.log("     =", EXPECTED_SCORE + "?")

function maximizeScoreViaRecursion(values, leftvalue = 1, rightvalue = 1) {
    // console.log(values, leftvalue, rightvalue)

    score = 0

    while(values.length >= 3) {
        const sortedValues = values.slice().sort((a, b) => b - a)
        const spicyValues = sortedValues.slice(0, 3)
        const spicyIndexes = spicyValues.map((value) => {
            return values.indexOf(value)
        }).sort()

        if(spicyIndexes[0]+1 != spicyIndexes[1]) {
            let a = spicyIndexes[0]+1
            let b = spicyIndexes[1]
            let leftvalue = values[a-1]
            let rightvalue = values[b]
            let subvalues = values.slice(a, b)
            values.splice(a, b- a)
            score += maximizeScoreViaRecursion(subvalues, leftvalue, rightvalue)
        } else if(spicyIndexes[1]+1 != spicyIndexes[2]) {
            let a = spicyIndexes[1]+1
            let b = spicyIndexes[2]
            let leftvalue = values[a-1]
            let rightvalue = values[b]
            let subvalues = values.slice(a, b)
            values.splice(a, b - a)
            score += maximizeScoreViaRecursion(subvalues, leftvalue, rightvalue)
        } else {
            score += values[spicyIndexes[0]] * values[spicyIndexes[1]] * values[spicyIndexes[2]]
            console.log(">", values[spicyIndexes[0]] * values[spicyIndexes[1]] * values[spicyIndexes[2]])
            values.splice(spicyIndexes[1], 1)
        }
    }

    if(values.length == 2) {
        if(values[0] < values[1]) {
            score += leftvalue * values[0] * values[1]
            console.log(">", leftvalue * values[0] * values[1])
            values.splice(0, 1)
        } else {
            score += values[0] * values[1] * rightvalue
            console.log(">", values[0] * values[1] * rightvalue)
            values.splice(1, 1)
        }
    }

    if(values.length == 1) {
        score += leftvalue * values[0] * rightvalue
        console.log(">", leftvalue * values[0] * rightvalue)
        values.splice(0, 1)
    }

    return score
}

function maximizeScoreViaThrees(values) {
    function pop(index) {
        const value = values[index] * (values[index-1] || 1) * (values[index+1] || 1)
        values.splice(index, 1)
        return value
    }

    let sum = 0

    while(values.length > 0) {
        const bursts = values.map((value, index) => {
            return {
                "index": index,
                "value": values[index] * (values[index-1] || 1) * (values[index+1] || 1)
            }
        })

        bursts.sort((a, b) => {
            return a.value - b.value
        })

        console.log(bursts)
        const bestBurst = bursts.pop()
        console.log(bestBurst)

        sum += bestBurst.value

        pop(bestBurst.index)

        console.log("-----")
    }

    console.log(sum)
    return sum
}

function maximizeScoreViaSorting(nums) {
    let values = nums

    // values = values.map(function(value) {
    //     return {value}
    // })

    // const indexes = values.map((value, index) => {
    //     return {value, index}
    // })
    //
    // indexes.pop()
    // indexes.shift()
    //
    // indexes.sort(function(a, b) {
    //     return a.value - b.value
    // })

    function pop(index) {
        const value = values[index] * (values[index-1] || 1) * (values[index+1] || 1)
        values.splice(index, 1)
        return value
    }

    // console.log(values)
    // console.log(pop(2))
    // console.log(values)

    // console.log(watervalues)
    // console.log(values)
    // console.log(watervalues === values)

    let coins = 0
    while(values.length > 2) {
        let watervalues = values.slice()
        watervalues.pop()
        watervalues.shift()
        const index = watervalues.indexOf(Math.min(...watervalues)) // does not handle dupes sorry
        console.log(values)
        console.log("Removing", watervalues[index])
        coins += pop(index + 1)
        console.log(values)
        console.log("coins", coins)
        console.log("--------")
    }

    if(values.length == 2) {
        console.log(values)
        coins += pop(0)
        console.log(values)
        console.log(coins)
        console.log("--------")
    }

    if(values.length == 1) {
        console.log(values)
        coins += pop(0)
        console.log(values)
        console.log(coins)
        console.log("--------")
    }

    console.log("final coins", coins)
    return coins
}

// function maxCoins(nums) {
//     const viaSorted = maxCoinsViaSorted(nums.slice())
//     const viaThrees = maxCoinsViaThrees(nums.slice())
//     const coins = Math.max(viaSorted, viaThrees)
//     console.log(coins)
//     return coins
// }