// Simplifications versus the shrine are in README.md next to this file.
const UPGRADE_BASE = {
    0: { 1: 0.9999999, 2: 0.98, 3: 0.95, 4: 0.7, 5: 0.6, 6: 0.4, 7: 0.25, 8: 0.15, 9: 0.07, 10: 0.024, 11: 0.14, 12: 0.11 },
    1: { 1: 0.99998, 2: 0.97, 3: 0.94, 4: 0.68, 5: 0.58, 6: 0.38, 7: 0.24, 8: 0.14, 9: 0.066, 10: 0.018, 11: 0.13, 12: 0.10 },
    2: { 1: 0.97, 2: 0.94, 3: 0.92, 4: 0.64, 5: 0.52, 6: 0.32, 7: 0.232, 8: 0.13, 9: 0.062, 10: 0.015, 11: 0.12, 12: 0.09 }
};
const COMPOUND_BASE = {
    0: { 1: 0.99, 2: 0.75, 3: 0.40, 4: 0.25, 5: 0.20, 6: 0.10, 7: 0.08, 8: 0.05, 9: 0.05, 10: 0.05 },
    1: { 1: 0.90, 2: 0.70, 3: 0.40, 4: 0.20, 5: 0.15, 6: 0.08, 7: 0.05, 8: 0.05, 9: 0.05, 10: 0.03 },
    2: { 1: 0.80, 2: 0.60, 3: 0.32, 4: 0.16, 5: 0.10, 6: 0.05, 7: 0.03, 8: 0.03, 9: 0.03, 10: 0.02 }
};
const DEFAULT_GRADES = [9, 10, 11, 12];
const HELMET_GRADES = [ 7, 9, 10, 12 ];
const HELMET_BASE_COST = 3200;
const MAX_FAILSTACK = 18;
const MAX_PRIMESTACK = 30;
const STAT_SCROLL_QTY = [1, 10, 100, 1000, 9999, 9999, 9999];
const CALC_VERSION = 8;

function example() {
    const item = { grades: [0,8,10,12], cost: 200000 };
    const targetLevel = 12;
    let costs = {
        priming: 5000000,
        scroll: [1000,40000,1600000,300000000,Infinity],
        offering: [0,5000000,27420000,650000000]
    };
    costs = stacks_calculate(costs);
    const use_lucky_slot = true;
    const use_server_ugrace = false;
    // const overrides = { 8: { offering_grade: 1 } };
    const overrides = null;
    const result = timing("upgrade_calc", () => upgrade_calc(item, targetLevel, { costs, use_lucky_slot, use_server_ugrace, overrides }));
    console.log(result);

    // const compoundCosts = { ...costs, scroll: [6400, 240000, 9200000, 1840000000] };
    // const compoundResult = timing("compound_calc", () => compound_calc(
    //     { grades: [3, 5, 6, 7], cost: 1000 },
    //     7,
    //     { costs: compoundCosts }
    // ));
    // console.log(compoundResult);
};

function statScrollQty(grade) {
    var n = STAT_SCROLL_QTY[grade];
    return n > 0 ? n : 9999;
}

// One stat-scroll click is +1 grace, the same as two +0.5 primes, and it
// spends one Primling plus statScrollQty(grade) Dexterity Scrolls.
function primingSpend(units, itemGrade, costs, canStat) {
    units = units || 0;
    var single = costs.priming;
    var statClicks = 0;
    var normal = units;
    var each = 0;
    var scroll = costs.statScroll;
    if (canStat && units >= 2 && isFinite(single) && isFinite(scroll) && scroll >= 0) {
        each = statScrollQty(itemGrade);
        var pair = single + each * scroll;
        if (pair <= single * 2) {
            statClicks = Math.floor(units / 2);
            normal = units % 2;
        } else {
            each = 0;
        }
    }
    var cost = 0;
    if (units) {
        if (!isFinite(single)) cost = Infinity;
        else cost = statClicks * (single + each * scroll) + normal * single;
    }
    return {
        statClicks: statClicks,
        normalPrimes: normal,
        statScrollEach: statClicks ? each : 0,
        cost: cost
    };
}

function upgrade_calc(
    { grades: item_grades, cost: item_cost, stat },
    target_level,
    { costs, use_lucky_slot = true, use_server_ugrace = false, overrides }) {

    const igrade = innateIgrade(item_grades);
    const igrace = igraceOf(igrade);
    const max_level = item_grades[3];
    target_level = Math.min(target_level, max_level);
    const item_grace_cap = target_level + 1;

    let last = [ { item_grace: igrace, cost: item_cost} ];
    for (let level_to = 1; level_to <= target_level; level_to++) {
        const base_chance = UPGRADE_BASE[igrade][level_to];
        const item_grade = itemGrade(item_grades, level_to - 1);
        const static_options = { level_to, base_chance, item_grade };
        const level_overrides = overrides?.[level_to] || {};

        const p1 = pruner();
        for (const parent of last) {
            let minPriming = level_overrides.priming != null
                ? level_overrides.priming
                : 0;
            let maxPriming = level_overrides.priming != null
                ? level_overrides.priming
                : Math.max(0, Math.ceil(2 * (item_grace_cap - parent.item_grace) - 1e-9));
            for (let priming = minPriming; priming <= maxPriming; priming++) {
                const spend = primingSpend(priming, item_grade, costs, stat);
                const itemGrace = Math.min(item_grace_cap, parent.item_grace + priming * 0.5);
                const cost = parent.cost + spend.cost;
                p1.get_set(itemGrace, cost, () => ({
                    parent,
                    priming,
                    primingCost: spend.cost,
                    statClicks: spend.statClicks,
                    normalPrimes: spend.normalPrimes,
                    statScrollEach: spend.statScrollEach,
                    cost,
                    item_grace: itemGrace
                }));
            }
        }
        const primedStates = p1.pareto();

        const minScrollGrade = level_overrides.scroll_grade != null ? level_overrides.scroll_grade : item_grade;
        const maxScrollGrade = level_overrides.scroll_grade != null ? level_overrides.scroll_grade : 4;
        const minOfferingGrade = level_overrides.offering_grade != null ? level_overrides.offering_grade : 0;
        const maxOfferingGrade = level_overrides.offering_grade != null ? level_overrides.offering_grade : 3;
        const minFailstack = level_overrides.failstack != null ? level_overrides.failstack : 0;
        const maxFailstack = level_overrides.failstack != null ? level_overrides.failstack : MAX_FAILSTACK;
        const minPrimestack = level_overrides.primestack != null ? level_overrides.primestack : 0;
        const maxPrimestack = level_overrides.primestack != null ? level_overrides.primestack : costs.primestack.length - 1;

        const p2 = pruner();
        for (const { parent, priming, primingCost, statClicks, normalPrimes, statScrollEach } of primedStates) {
            for (let scroll_grade = minScrollGrade; scroll_grade <= maxScrollGrade; scroll_grade++) {
                for (let offering_grade = minOfferingGrade; offering_grade <= maxOfferingGrade; offering_grade++) {
                    for (let failstack = minFailstack; failstack <= maxFailstack; failstack++) {
                        for (let primestack = minPrimestack; primestack <= maxPrimestack; primestack++) {
                            const options = {
                                scroll_grade, offering_grade, priming, primingCost,
                                statClicks, normalPrimes, statScrollEach,
                                failstack, primestack
                            };
                            const result = upgrade(static_options, parent.item_grace, options, { use_lucky_slot, use_server_ugrace });
                            result.item_grace = Math.min(result.item_grace, item_grace_cap);
                            const { cost, breakdown } = calculate_cost(static_options, options, result, parent.cost, costs);

                            const best = p2.get_set(result.item_grace, cost, () => ({ parent, ...static_options, ...options, ...result, cost, breakdown }));
                            const lowerBound = breakdown.fixed_cost + breakdown.attempt_cost / result.chance_cap;
                            if (lowerBound >= best.cost) break;
                            if (result.chance >= result.chance_cap) break;
                        }
                    }
                }
            }
        }

        last = p2.pareto();
    }
    last.sort((a, b) => a.cost - b.cost);

    let current = last[0];
    const result = [ ]
    while (current) {
        const parent = current.parent;
        delete current.parent;
        result.push(current);
        current = parent;
    }
    return result.reverse();
}

function pruner() {
    const bestByGrace = new Map();
    function get_set(item_grace, cost, getVal) {
        const grace10 = Math.round(item_grace * 10);
        let old = bestByGrace.get(grace10);
        if (!old || cost < old.cost) {
            const val = getVal();
            bestByGrace.set(grace10, val);
            return val;
        }
        return old;
    }
    function pareto() {
        const current = [...bestByGrace.values()];
        current.sort((a, b) => b.item_grace - a.item_grace);
        let bestCost = Infinity;
        const frontier = [];
        for (const state of current) {
            if (state.cost < bestCost) {
                frontier.push(state);
                bestCost = state.cost;
            }
        }
        return frontier;
    }
    return { get_set, pareto };
}

function calculate_cost(static_options, options, result, parent_cost, costs) {
    const { scroll_grade, offering_grade, priming, failstack, primestack } = options;
    const priming_cost = typeof options.primingCost === "number"
        ? options.primingCost
        : (priming ? costs.priming * priming : 0);
    const statClicks = options.statClicks || 0;
    const normalPrimes = options.normalPrimes != null ? options.normalPrimes : (priming || 0);
    const statEach = options.statScrollEach || 0;
    const stat_scroll_cost = statClicks * statEach * (costs.statScroll || 0);
    const primling_cost = (statClicks + normalPrimes) * (isFinite(costs.priming) ? costs.priming : 0);
    const base_cost = parent_cost + priming_cost;
    const scroll_cost = costs.scroll[scroll_grade];
    const offering_cost = costs.offering[offering_grade];
    const failstack_cost = failstack && costs.failstack[static_options.level_to][failstack].cost;
    const primestack_cost = primestack && costs.primestack[primestack].cost;

    let attempt_cost = 0;
    let fixed_cost = 0;
    if (scroll_grade == 4) { // special case - item is not destroyed on failure
        attempt_cost = scroll_cost + offering_cost;
        fixed_cost = base_cost + failstack_cost + primestack_cost;
    } else {
        attempt_cost = base_cost + scroll_cost + offering_cost;
        fixed_cost = failstack_cost + primestack_cost;
    }

    const cost = fixed_cost + attempt_cost / result.chance;
    const breakdown = {
        parent_cost,
        priming_cost,
        primling_cost,
        stat_scroll_cost,
        stat_clicks: statClicks,
        normal_primes: normalPrimes,
        stat_scroll_each: statEach,
        scroll_cost,
        offering_cost,
        failstack_cost,
        failstack: failstack && costs.failstack[static_options.level_to][failstack],
        primestack_cost,
        primestack: primestack && costs.primestack[primestack],
        fixed_cost,
        attempt_cost,
        chance: result.chance
    }

    return { cost, breakdown };
}

function upgrade(
    { level_to, base_chance, item_grade },
    item_grace,
    { scroll_grade, offering_grade, priming, failstack, primestack },
    { use_lucky_slot, use_server_ugrace }) {

    item_grace += priming * 0.5;

    const item_grace_cap = level_to + 1;
    const raw_ugrace = Math.min(3, failstack / 4.5);
    const raw_server_ugrace = use_server_ugrace ? Math.min(6, failstack / 3.0) : 0;
    const raw_ograce = primestack * 0.6 / 3.2;

    var chance = base_chance;
    var grace = Math.max(0, Math.min(item_grace_cap, item_grace + raw_ugrace) + raw_server_ugrace + raw_ograce);
    grace = (chance * grace) / level_to + grace / 1000.0;

    if (scroll_grade > item_grade && level_to <= 10) {
        chance = chance * 1.2 + 0.01;
        item_grace += 0.4;
    }

    if (offering_grade) {
        if (offering_grade > item_grade + 1) {
            chance = chance * 1.7 + grace * 4;
            item_grace += 3;
        } else if (offering_grade > item_grade) {
            chance = chance * 1.5 + grace * 1.2;
            item_grace += 1;
        } else if (offering_grade == item_grade) {
            chance = chance * 1.4 + grace;
            item_grace += 0.4;
        } else if (offering_grade == item_grade - 1) {
            chance = chance * 1.15 + grace / 3.2;
            item_grace += 0.2;
        } else {
            chance = chance * 1.08 + grace / 4;
            item_grace += 0.1;
        }
    } else {
        grace = Math.max(0, grace / 4.8 - 0.4 / ((level_to - 0.999) * (level_to - 0.999)));
        chance += grace;
    }

    let chance_cap = (scroll_grade > item_grade && level_to <= 10 || offering_grade > item_grade)
        ? Math.min(base_chance + 0.36, base_chance * 3)
        : Math.min(base_chance + 0.24, base_chance * 2);
    chance_cap = Math.min(chance_cap, 1);
    chance = Math.min(chance, chance_cap);

    function adjust_for_lucky_slot(p) {
        if (p <= 0) return 0;
        if (p >= 1) return 1;
        let transformed;
        if (p < 0.0001) transformed = (p * 10000) * ((p + 0.012) / 0.975);
        else if (p < 0.963) transformed = (p + 0.012) / 0.975;
        else transformed = 1;
        return 0.4 * p + 0.6 * transformed;
    }
    if (use_lucky_slot) {
        chance = adjust_for_lucky_slot(chance);
        chance_cap = adjust_for_lucky_slot(chance_cap);
    }

    return { chance, item_grace, chance_cap };
}

function compound_calc(
    { grades: item_grades, cost: item_cost, igrade },
    target_level,
    { costs, overrides }) {

    const innate = igrade != null ? igrade : innateIgrade(item_grades);
    const max_level = Math.min(item_grades[3], 10);
    target_level = Math.min(target_level, max_level);

    let last = [ { item_grace: 0, cost: item_cost } ];
    for (let level_to = 1; level_to <= target_level; level_to++) {
        const level = level_to - 1;
        const row = level >= 3 ? itemGrade(item_grades, level - 2) : innate;
        const base_chance = (COMPOUND_BASE[row] || COMPOUND_BASE[2])[level_to];
        const item_grade = itemGrade(item_grades, level);
        const static_options = { level_to, base_chance, item_grade };
        const level_overrides = overrides?.[level_to] || {};

        const minScrollGrade = level_overrides.scroll_grade != null ? level_overrides.scroll_grade : item_grade;
        const maxScrollGrade = level_overrides.scroll_grade != null ? level_overrides.scroll_grade : 3;
        const minOfferingGrade = level_overrides.offering_grade != null ? level_overrides.offering_grade : 0;
        const maxOfferingGrade = level_overrides.offering_grade != null ? level_overrides.offering_grade : 3;
        const minPrimestack = level_overrides.primestack != null ? level_overrides.primestack : 0;
        const maxPrimestack = level_overrides.primestack != null ? level_overrides.primestack : costs.primestack.length - 1;

        const p2 = pruner();
        for (const parent of last) {
            for (let scroll_grade = minScrollGrade; scroll_grade <= maxScrollGrade; scroll_grade++) {
                for (let offering_grade = minOfferingGrade; offering_grade <= maxOfferingGrade; offering_grade++) {
                    for (let primestack = minPrimestack; primestack <= maxPrimestack; primestack++) {
                        const options = { scroll_grade, offering_grade, primestack };
                        const result = compound(static_options, parent.item_grace, options);
                        const { cost, breakdown } = calculate_compound_cost(static_options, options, result, parent.cost, costs);

                        const best = p2.get_set(result.item_grace, cost, () => ({ parent, ...static_options, ...options, ...result, copies: 3, cost, breakdown }));
                        const lowerBound = breakdown.fixed_cost + breakdown.attempt_cost / result.chance_cap;
                        if (lowerBound >= best.cost) break;
                        if (result.chance >= result.chance_cap) break;
                    }
                }
            }
        }
        last = p2.pareto();
    }
    last.sort((a, b) => a.cost - b.cost);

    let current = last[0];
    const result = [ ]
    while (current) {
        const parent = current.parent;
        delete current.parent;
        result.push(current);
        current = parent;
    }
    return result.reverse();
}

function calculate_compound_cost(static_options, { scroll_grade, offering_grade, primestack }, result, parent_cost, costs) {
    const scroll_cost = costs.scroll[scroll_grade];
    const offering_cost = costs.offering[offering_grade];
    const primestack_cost = primestack && costs.primestack[primestack].cost;
    const attempt_cost = 3 * parent_cost + scroll_cost + offering_cost;
    const fixed_cost = primestack_cost;
    const cost = fixed_cost + attempt_cost / result.chance;
    const breakdown = {
        parent_cost,
        scroll_cost,
        offering_cost,
        primestack_cost,
        primestack: primestack && costs.primestack[primestack],
        fixed_cost,
        attempt_cost,
        chance: result.chance
    }
    return { cost, breakdown };
}

function compound(
    { level_to, base_chance, item_grade },
    item_grace,
    { scroll_grade, offering_grade, primestack }) {

    const level = level_to - 1;
    const ograce = primestack * 0.6;
    const grace_sum = item_grace * 3;

    var chance = base_chance;
    var high = false;

    item_grace = (offering_grade ? grace_sum : item_grace) / 6.4;

    if (scroll_grade > item_grade) {
        chance = chance * 1.1 + 0.001;
        item_grace += 0.4;
        high = scroll_grade - item_grade;
    }

    if (offering_grade) {
        var grace = 0.027 * (grace_sum + 0.5 + ograce);
        if (offering_grade > item_grade + 1) {
            chance = chance * 1.64 + grace * 2;
            high = true;
            item_grace += 3;
        } else if (offering_grade > item_grade) {
            chance = chance * 1.48 + grace;
            high = true;
            item_grace += 1;
        } else if (offering_grade == item_grade) {
            chance = chance * 1.36 + Math.min(30 * 0.027, grace);
            item_grace += 0.5;
        } else if (offering_grade == item_grade - 1) {
            chance = chance * 1.15 + Math.min(25 * 0.019, grace) / Math.max(level - 2, 1);
            item_grace += 0.2;
        } else {
            chance = chance * 1.08 + Math.min(15 * 0.015, grace) / Math.max(level - 1, 1);
            item_grace += 0.1;
        }
    } else {
        var raw = 0.007 * (grace_sum + ograce);
        chance = chance + Math.min(25 * 0.007, raw) / Math.max(level - 1, 1);
    }

    let chance_cap = Math.min(
        base_chance * (3 + ((high && high * 0.6) || 0)),
        base_chance + 0.2 + ((high && high * 0.05) || 0)
    );
    chance_cap = Math.min(chance_cap, 1);
    chance = Math.min(chance, chance_cap);

    return { chance, item_grace, chance_cap };
}

//
// Failstack and Primestack Calculation
//

function stacks_calculate(costs) {
    const calculated = cache("stacks_calculate", { priming: costs.priming, scroll: costs.scroll, offering: costs.offering }, () => {
        const stackCosts = stacking_precalculate(costs);
        const seed = {
            failstack: stacking_failstack(stackCosts),
            primestack: stacking_primestack(stackCosts)
        };
        const plan = upgrade_calc(
            { grades: HELMET_GRADES, cost: HELMET_BASE_COST },
            HELMET_GRADES[3],
            { costs: { ...costs, ...seed }, use_lucky_slot: true, use_server_ugrace: false }
        );
        // Chances stay on the unlucky matching-scroll click. The plan replaces the helmet that click destroys.
        for (let i = 1; i < stackCosts.length; i++) {
            const grade = itemGrade(HELMET_GRADES, i - 1);
            const copy = plan[i - 1].cost;
            stackCosts[i].lucky_cost = plan[i].cost;
            stackCosts[i].failstack_cost = copy + costs.scroll[grade];
            stackCosts[i].primestack_attempt_cost = copy + costs.scroll[grade] + costs.offering[1];
        }
        return {
            failstack: stacking_failstack(stackCosts),
            primestack: stacking_primestack(stackCosts),
            helmetTime: helmetLevelTimes(plan)
        };
    });
    return { ...costs, ...calculated };
}
function stacking_precalculate(costs) {
    const item_grades = HELMET_GRADES;
    const base_item_cost = HELMET_BASE_COST;

    const igrade = innateIgrade(item_grades);
    const igrace = igraceOf(igrade);
    const max_level = item_grades[3];

    const results = [ { lucky_cost: base_item_cost } ];

    for (let i = 1; i <= max_level; i++) {
        const prev = results[i - 1];

        const item_grade = itemGrade(item_grades, i - 1);
        const static_options = { level_to: i, base_chance: UPGRADE_BASE[igrade][i], item_grade };
        const options = { scroll_grade: item_grade, offering_grade: 0, priming: 0, failstack: 0, primestack: 0 };

        const lucky_result = upgrade(static_options, igrace, options, { use_lucky_slot: true });
        const lucky_cost = calculate_cost(static_options, options, lucky_result, prev.lucky_cost, costs).cost;

        const unlucky_result = upgrade(static_options, igrace, options, { use_lucky_slot: false });
        const failstack_attempt_cost = prev.lucky_cost + costs.scroll[item_grade];

        const primestack_result = upgrade(static_options, igrace, { ...options, offering_grade: 1 }, { use_lucky_slot: false });
        const primestack_attempt_cost = prev.lucky_cost + costs.scroll[item_grade] + costs.offering[1];

        results.push({ lucky_cost, failstack_chance: unlucky_result.chance, failstack_cost: failstack_attempt_cost, primestack_chance: primestack_result.chance, primestack_attempt_cost });
    }
    return results;
}
// Personal ugrace from one failed upgrade to `levelTo`, no offering.
// Server ugrace is priced as these same amounts. A success clears only index `levelTo`.
function failUgraceGains(levelTo) {
    const gain = new Map();
    const add = (level, n) => {
        if (level < 0) return;
        gain.set(level, (gain.get(level) || 0) + n);
    };
    add(levelTo, 1);
    add(levelTo - 1, 1);
    if (levelTo >= 8 && levelTo <= 15) {
        add(levelTo - 1, 1);
        add(levelTo - 2, 2);
        add(levelTo - 3, 2);
    }
    return gain;
}

function streakAttempts(failChance, failures) {
    if (failures <= 0) return 0;
    if (failChance >= 1) return failures;
    if (!(failChance > 0)) return Infinity;
    const p = failChance;
    return (1 - Math.pow(p, failures)) / ((1 - p) * Math.pow(p, failures));
}

function splashPlans(sources, maxUGrace) {
    const plans = new Array(maxUGrace + 1).fill(null);
    if (!sources.length) return plans;
    const maxGain = sources.reduce((max, src) => Math.max(max, src.gain), 0);
    const limit = maxUGrace + maxGain;
    const dp = new Array(limit + 1).fill(null);
    dp[0] = { cost: 0, counts: Object.create(null) };
    for (let g = 0; g <= limit; g++) {
        const cur = dp[g];
        if (!cur) continue;
        for (const src of sources) {
            const next = g + src.gain;
            if (next > limit) continue;
            const cost = cur.cost + src.attemptCost / src.q;
            if (!dp[next] || cost < dp[next].cost) {
                const counts = Object.assign(Object.create(null), cur.counts);
                counts[src.level] = (counts[src.level] || 0) + 1;
                dp[next] = { cost, counts };
            }
        }
    }
    let best = null;
    for (let g = limit; g >= 1; g--) {
        if (dp[g] && (!best || dp[g].cost < best.cost)) best = dp[g];
        if (g <= maxUGrace) plans[g] = best;
    }
    return plans;
}

function farmsFromCounts(counts, byLevel, attemptsOf) {
    const farms = [];
    for (const key of Object.keys(counts)) {
        const level = Number(key);
        const failures = counts[key];
        const action = byLevel[level];
        farms.push({
            level,
            gain: action.gain,
            failures,
            attempts: attemptsOf(action, failures)
        });
    }
    farms.sort((a, b) => a.level - b.level);
    return farms;
}

function finishFailstack(j, farms) {
    let attempts = 0;
    let cost = 0;
    let level = null;
    let most = -1;
    for (const farm of farms) {
        attempts += farm.attempts;
        if (farm.attempts > most) {
            most = farm.attempts;
            level = farm.level;
        }
    }
    return { level, ugrace: j, attempts, cost, farms };
}

function priceFailstack(direct, splash, byLevel, j) {
    let farms = null;
    let best = Infinity;
    const splashPlan = splash && splash[j];
    if (splashPlan && Number.isFinite(splashPlan.cost)) {
        best = splashPlan.cost;
        farms = farmsFromCounts(splashPlan.counts, byLevel, (action, failures) => failures / action.q);
    }
    if (direct) {
        const failures = Math.ceil(j / direct.gain);
        const attempts = streakAttempts(direct.q, failures);
        const cost = attempts * direct.attemptCost;
        if (Number.isFinite(cost) && cost < best) {
            best = cost;
            farms = [{ level: direct.level, gain: direct.gain, failures, attempts }];
        }
    }
    if (!farms) {
        return { level: null, ugrace: j, attempts: Infinity, cost: Infinity, farms: [] };
    }
    const priced = finishFailstack(j, farms);
    priced.cost = best;
    return priced;
}

function stacking_failstack(stackCosts, maxUGrace = MAX_FAILSTACK) {
    const farmLevels = [];
    for (let level = 1; level < stackCosts.length; level++) {
        const row = stackCosts[level];
        const q = 1 - row.failstack_chance;
        if (!(q > 0) || !Number.isFinite(row.failstack_cost)) continue;
        farmLevels.push({
            level,
            q,
            attemptCost: row.failstack_cost,
            gains: failUgraceGains(level)
        });
    }

    const results = [[]];
    for (let target = 1; target < stackCosts.length; target++) {
        const splash = [];
        const byLevel = Object.create(null);
        let direct = null;
        for (const farm of farmLevels) {
            const gain = farm.gains.get(target) || 0;
            if (!gain) continue;
            const action = { level: farm.level, gain, q: farm.q, attemptCost: farm.attemptCost };
            byLevel[farm.level] = action;
            if (farm.level === target) direct = action;
            else splash.push(action);
        }
        const splashTable = splashPlans(splash, maxUGrace);
        const level_results = [{ level: target, ugrace: 0, attempts: 0, cost: 0, farms: [] }];
        for (let j = 1; j <= maxUGrace; j++) {
            level_results.push(priceFailstack(direct, splashTable, byLevel, j));
        }
        results.push(level_results);
    }
    return results;
}
function stacking_primestack(stackCosts, maxOGrace = MAX_PRIMESTACK) {
    const step = 0.6;

    let actions = stackCosts
        .map((x, level) => x && ({
            level,
            chance: x.primestack_chance,
            attemptCost: x.primestack_attempt_cost
        }))
        .filter(x => x && x.chance < 1 && Number.isFinite(x.attemptCost));

    // Remove levels that are both more expensive and more likely to succeed.
    actions = actions.filter(a =>
        !actions.some(b =>
            b !== a &&
            b.attemptCost <= a.attemptCost &&
            b.chance <= a.chance &&
            (b.attemptCost < a.attemptCost || b.chance < a.chance)
        )
    );

    function expectedAttempts(target, p) {
        if (target <= 0) return 0;

        // Finer internal resolution because success produces grace * 0.25.
        const resolution = 0.05;
        const n = Math.ceil(target / resolution);
        const v = new Float64Array(n);

        const q = 1 - p;
        const failures = Math.ceil(target / step);
        const initial = (1 - Math.pow(q, failures)) / (p * Math.pow(q, failures));
        v.fill(initial);

        function get(g) {
            if (g >= target) return 0;

            const x = g / resolution;
            const lo = Math.min(Math.floor(x), n - 1);
            const hi = Math.min(lo + 1, n - 1);
            const f = x - lo;

            return v[lo] * (1 - f) + v[hi] * f;
        }

        for (let iteration = 0; iteration < 300; iteration++) {
            let maxChange = 0;

            for (let i = n - 1; i >= 0; i--) {
                const g = i * resolution;
                const old = v[i];

                const next =
                    1 +
                    p * get(g * 0.25) +
                    (1 - p) * get(g + step);

                v[i] = next;

                const change = Math.abs(next - old);
                if (change > maxChange) maxChange = change;
            }

            if (maxChange < 1e-5) break;
        }

        return v[0];
    }

    const count = Math.floor(maxOGrace / step);
    const result = [{
        ograce: 0,
        level: null,
        attempts: 0,
        cost: 0
    }];

    for (let i = 1; i <= count; i++) {
        const ograce = i * step;
        let best = null;

        for (const action of actions) {
            const attempts = expectedAttempts(ograce, action.chance);
            const cost = attempts * action.attemptCost;

            if (!best || cost < best.cost) {
                best = {
                    ograce,
                    level: action.level,
                    attempts,
                    cost
                };
            }
        }

        result.push(best);
    }

    return result;
}


//
// Utils
//

// Mass Production++ is on for every click, so the shrine wait is divided by 10.
function shrineClickMs(mode, levelTo, igrade) {
    if (mode === "compound") return 1000;
    const tmult = igrade >= 2 ? 2 : igrade === 1 ? 1.5 : 1;
    return 500 * levelTo * Math.sqrt(levelTo) * tmult / 10;
}

// Expected shrine time to hold one helmet at each level. plan[0] is +0.
function helmetLevelTimes(plan) {
    const times = [0];
    for (let n = 1; n < plan.length; n++) {
        const step = plan[n];
        const click = shrineClickMs("upgrade", step.level_to, 0);
        const p = step.chance;
        const prev = times[n - 1];
        if (!(p > 0) || !isFinite(p) || !isFinite(click) || !isFinite(prev)) {
            times[n] = Infinity;
            continue;
        }
        const clicks = 1 / p;
        times[n] = step.scroll_grade === 4 ? prev + click * clicks : (prev + click) * clicks;
    }
    return times;
}

function itemGrade(grades, level) {
    grades = grades || DEFAULT_GRADES;
    level = level || 0;
    if (level >= grades[3]) return 4;
    if (level >= grades[2]) return 3;
    if (level >= grades[1]) return 2;
    if (level >= grades[0]) return 1;
    return 0;
}
function innateIgrade(grades) {
    return itemGrade(grades, 0);
}
function igraceOf(igrade) {
    if (igrade === 0) return 1;
    if (igrade === 1) return -1;
    if (igrade === 2) return -2;
    return 0;
}

function cache(name, key, cbValue) {
    const cacheKey = "upgrade_calc_" + name;
    const keyString = JSON.stringify(key);
    const version = CALC_VERSION;

    try {
        const cached = JSON.parse(localStorage.getItem(cacheKey));
        if (cached?.key === keyString && cached?.version === version) return cached.result;
    } catch {}

    const result = timing(name, () => cbValue());
    try {
        localStorage.setItem(cacheKey, JSON.stringify({ key: keyString, version, result }));
    } catch {}

    return result;
}

function timing(name, cb) {
    const start = performance.now();
    const result = cb();
    console.log(`${name} took ${performance.now() - start}ms`);
    return result;
}