// name, lvl, modifiers, weights
var rawData = `MapAtlasMapsHave20PercentQuality 1   "Maps have 20% Quality
Unique Bosses deal 20% increased Damage"    default 1,000
MapAtlasContainsAdditionalRandomBoss    1   Areas are inhabited by an additional Invasion Boss  "hall_of_grandmasters 0
default 1,000"
MapAtlasClustersOfBloodwormBarrels  1   Areas contain 30 additional Clusters of Mysterious Barrels  default 850
MapAtlasPhysicalDamageAndPacks_ 1   "Areas contain additional Monsters that deal Physical Damage
Players and Monsters take 10% increased Physical Damage"    "no_monster_packs 0
default 1,000"
MapAtlasHighValueEnemiesOnOwnTeam   1   Areas contain hunted traitors   "no_monster_packs 0
default 100"
MapAtlasMagicAndRareMapsHaveAdditionalPacks 1   "Magic Maps contain additional Magic Monsters
Rare Maps contain additional Rare Monsters
Normal Maps contain additional Normal Monsters" "unique_map 0
no_monster_packs 0
default 1,000"
MapAtlasMoveAttackCastSpeed 1   "20% increased Player and Monster Movement Speed
20% increased Monster Attack Speed
20% increased Monster Cast Speed"   default 1,000
MapAtlasMontersThatConvertOnDeath__ 1   Areas contain additional Monsters that Convert when Killed  "no_monster_packs 0
default 1,000"
MapAtlasUnIDedMapsGrantQuantity 1   "30% increased Quantity of Items found in Unidentified Maps
Found Items drop Identified in Identified Maps
15% increased Pack Size in Unidentified Maps"   default 1,000
MapAtlasReducedReflectedDamageTakenMirroredRares    1   "Players cannot take Reflected Damage
Areas contain additional Packs with Mirrored Rare Monsters" default 1,000
MapAtlasPlayersDamageDealtAndTakenWhileStationary_  1   "Players deal 100% increased Damage while stationary
Players take 10% increased Damage while stationary" "vaults_of_atziri 0
default 1,000"
MapAtlasFireDamageAndPacks  1   "Areas contain additional Monsters that deal Fire Damage
Players and Monsters take 10% increased Fire Damage"    "no_monster_packs 0
default 1,000"
MapAtlasGroundHaste 1   Areas contain Slipstreams   default 1,000
MapAtlasInstantFlasksAndHealingMonsters 1   "Life and Mana Recovery from Flasks are instant
Areas contain additional Monsters that Heal"    default 1,000
MapAtlasOnslaughtWhenHitAndOnslaughtEffect  1   "Players and Monsters have Onslaught if they have been Hit Recently
100% increased effect of Onslaught on Players and Monsters" "vaults_of_atziri 0
default 1,000"
MapAtlasColdDamageAndPacks  1   "Areas contain additional Monsters that deal Cold Damage
Players and Monsters take 10% increased Cold Damage"    "no_monster_packs 0
default 1,000"
MapAtlasStrongboxMonstersEnrageAndDrops 1   "Strongbox Monsters have 500% increased Item Quantity
Strongbox Monsters are Enraged
Areas contain an extra Strongbox"   "hall_of_grandmasters 0
no_strongboxes 0
default 1,000"
MapAtlasMagicPackSize   1   30% increased Magic Pack Size   "no_monster_packs 0
default 1,000"
MapAtlasBodyguardsAndBossMapDrops   1   "Unique Bosses are accompanied by Bodyguards
An additional Map drops on Completing Areas"    "no_boss 0
default 1,000"
MapAtlasLightningDamageAndPacks 1   "Areas contain additional Monsters that deal Lightning Damage
Players and Monsters take 10% increased Lightning Damage"   "no_monster_packs 0
default 1,000"
MapAtlasPoisonEffectsAndParasites   1   "Players deal 10% increased Damage for each Poison on them
Players have 5% increased Movement Speed for each Poison on them
Areas contain additional Poisonous Monsters"    default 1,000
MapAtlasRogueExilesDamageAndDropAdditionalJewels    1   "Rogue Exiles deal 20% increased Damage
Rogue Exiles have 20% increased Maximum Life
Rogue Exiles drop 2 additional Jewels
Areas are inhabited by 1 additional Rogue Exile"    "no_monster_packs 0
default 1,000"
MapAtlasCurseEffectOnPlayersAndMonsters 73  "20% reduced Effect of Curses on Monsters
60% reduced Effect of Curses on Players"    "vaults_of_atziri 0
default 1,000"
MapAtlasContainsZanaMission 73  Areas contain Zana  "unique_map 0
default 200"
MapAtlasMapQualityBonusAlsoAppliesToRarity  73  "Quality bonus of Maps also applies to Rarity of Items found
Unique Bosses have 20% increased Life"  default 1,000
MapAtlasStrongboxesAreCorruptedAndUnided    73  "Strongboxes in Areas are Corrupted
Areas contain an extra Strongbox
Strongboxes in Areas are at least Rare Rarity"  "no_strongboxes 0
default 200"
MapAtlasChaosDamageAndPacks_    73  "Areas contain additional Monsters that deal Chaos Damage
Players and Monsters take 10% increased Chaos Damage"   "no_monster_packs 0
default 1,000"
MapAtlasUniqueMonstersDropCorruptedItems    73  Unique Monsters drop Corrupted Items    "vaults_of_atziri 0
hall_of_grandmasters 0
default 200"
MapAtlasCorruptedMapBossesDropAdditionalVaalItems   78  "Unique Bosses of Corrupted Maps drop an additional Vaal Item
Found Items have a 5% chance to drop Corrupted in Areas"    default 1,000
MapAtlasBloodlinesDropAdditionalCurrency    78  Nemesis Monsters drop 3 additional Currency Items   "no_monster_packs 0
default 200"
MapAtlasFishy   78  Areas are Alluring  default 10`;

// tier "enum"
var tier = {
    WHITE: 1,
    YELLOW: 73,
    RED: 78,
};

function getSextantCost(tier) {
    switch (tier) {
        case 1:
            return 2.0; // 4 chaos
        case 73:
            return 4.0; // 5 chaos
        case 78:
            return 8.0; // 6 chaos
    }
}

var maxIterations = 500000;

var mapData = {
    "Shaped Primordial Pool": {
        tier: tier.YELLOW,
        adjacent: [
            "Cavern",
            "Waste Pool",
            "Phantasmagoria",
            "Burial Chambers",
        ]
    },
    "Canyon": {
        tier: tier.YELLOW,
        adjacent: [
            "Waste Pool",
        ]
    },
    "Vaal City": {
        tier: tier.YELLOW,
        adjacent: [
            "Burial Chambers",
            "Vaults of Atziri",
            "Arachnid Tomb",
            "Olmec's Sanctum",
            "Shore",
            "Catacombs",
        ]
    },
    "Arachnid Tomb": {
        tier: tier.YELLOW,
        adjacent: [
            "Vaults of Atziri",
            "Shore",
            "Vaal City",
            "Vaal Pyramid",
        ]
    },
    "Shore": {
        tier: tier.YELLOW,
        adjacent: [
            "Arachnid Tomb",
            "Vaal City",
            "Catacombs",
            "Olmec's Sanctum",
        ]
    },
    "Catacombs": {
        tier: tier.YELLOW,
        adjacent: [
            "Vaal City",
            "Shore",
            "Olmec's Sanctum",
        ]
    },
    "Olmec's Sanctum": {
        tier: tier.YELLOW,
        adjacent: [
            "Vaal City",
            "Shore",
            "Catacombs",
        ]
    },
    "Vaal Pyramid": {
        tier: tier.WHITE,
        adjacent: [
            "Phantasmagoria",
            "Burial Chambers",
            "Marshes",
            "Vaults of Atziri",
            "Arachnid Tomb",
        ]
    },
    "Marshes": {
        tier: tier.WHITE,
        adjacent: [
            "Phantasmagoria",
            "Vaal Pyramid",
        ]
    },
    "Phantasmagoria": {
        tier: tier.WHITE,
        adjacent: [
            "Shaped Primordial Pool",
            "Vaal Pyramid",
            "Marshes",
        ]
    },
    "Burial Chambers": {
        tier: tier.WHITE,
        adjacent: [
            "Shaped Primordial Pool",
            "Vaal Pyramid",
            "Vaults of Atziri",
            "Vaal City",
        ]
    },
    "Cavern": {
        tier: tier.WHITE,
        adjacent: [
            "Shaped Primordial Pool",
            "Waste Pool",
        ]
    },
    "Waste Pool": {
        tier: tier.WHITE,
        adjacent: [
            "Shaped Primordial Pool",
            "Cavern",
            "Canyon",
            "Channel",
        ]
    },
    "Channel": {
        tier: tier.WHITE,
        adjacent: [
            "Waste Pool",
            "Acid Lakes",
            "Mesa",
            "Factory",
        ]
    },
    "Vaults of Atziri": {
        tier: tier.WHITE,
        adjacent: [
            "Burial Chambers",
            "Vaal City",
            "Arachnid Tomb",
            "Vaal Pyramid",
        ]
    },
    "Acid Lakes": {
        tier: tier.WHITE,
        adjacent: [
            "Channel",
            "Factory",
        ]
    },
    "Mesa": {
        tier: tier.WHITE,
        adjacent: [
            "Channel",
        ]
    },
    "Factory": {
        tier: tier.WHITE,
        adjacent: [
            "Channel",
            "Acid Lakes",
        ]
    },
};

var goodMods = {
    "MapAtlasFireDamageAndPacks": true,
    "MapAtlasColdDamageAndPacks": true,
    "MapAtlasLightningDamageAndPacks": true,
    "MapAtlasPhysicalDamageAndPacks_": true,
    "MapAtlasChaosDamageAndPacks_": true,
    "MapAtlasMontersThatConvertOnDeath__": true,
    "MapAtlasInstantFlasksAndHealingMonsters": true,
    "MapAtlasMagicAndRareMapsHaveAdditionalPacks": true,
    "MapAtlasHighValueEnemiesOnOwnTeam": true,
    "MapAtlasPoisonEffectsAndParasites": true,
    "MapAtlasClustersOfBloodwormBarrels": true,
    "MapAtlasClustersOfParasiteBarrels": true,
    "MapAtlasClustersOfWealthyBarrels": true,
    "MapAtlasClustersOfBeaconBarrels": true,
    "MapAtlasClustersOfVolatileBarrels": true,
    "MapAtlasMagicPackSize": true,
    "MapAtlasUniqueMonstersDropCorruptedItems": true,
    "MapAtlasBloodlinesDropAdditionalCurrency": true,
    "MapAtlasReducedReflectedDamageTakenMirroredRares": true,
    "MapAtlasStrongboxesAreCorruptedAndUnided": true,
    "MapAtlasStrongboxMonstersEnrageAndDrops": true,
}

var parsed = rawData.match(/.+\t.+\t[^\t]+\t[^\t]+\n/g);

for (var i = 0; i < parsed.length; i++) {
    var str = parsed[i];

    str = str.match(/[^\t]+/g);

    parsed[i] = {
        name: str[0],
        level: parseInt(str[1]),
        mods: str[2].match(/[^\n"]+/g),
        weights: str[3].match(/[^\n"]+/g),
    }

    var weightsObj = {};

    for (var j = 0; j < parsed[i].weights.length; j++) {
        var r = parsed[i].weights[j].split(/\s/);
        weightsObj[r[0]] = parseInt(r[1].replace(",", ""));
    }

    parsed[i].weights = weightsObj;
}

var maps = {};

// Map prototype -------------------------------------------------

// constructor

function Map(name, tier, adj, activeMod) {
    this.name = name;
    this.tier = tier;
    this.sextantCost = getSextantCost(this.tier);
    //console.log( this.name + " sextant cost is " + this.sextantCost + "c.");
    if (activeMod) {
        for (var mod in parsed) {
            if (mod.name == activeMod) {
                this.mod = mod;
                break;
            }
        }
    }
    this.adjacent = adj;

    maps[this.name] = this;
}

Map.prototype.getBlockedMods = function(log) {
    if (log) {
        console.log("Blocked mods for " + this.name + ":");
    }
    var blocked = {};
    for (var i in this.adjacent) {
        if (this.adjacent[i].mod) {
            if (log) {
                console.log(this.adjacent[i].name + " blocks " + this.adjacent[i].mod.name);
            }
            blocked[this.adjacent[i].mod.name] = true;
        }

        for (var j in this.adjacent[i].adjacent) {
            if (this.adjacent[i].adjacent[j].mod) {
                if (log) {
                    console.log(this.adjacent[i].adjacent[j].name + " blocks " + this.adjacent[i].adjacent[j].mod.name);
                }
                blocked[this.adjacent[i].adjacent[j].mod.name] = true;
            }
        }
    }
    return blocked;
}

Map.prototype.getFilteredModList = function() {
    var blocked = this.getBlockedMods();

    return parsed.filter(function(mod) {
        if (this.tier < mod.level || blocked[mod.name] || mod == this.mod) {
            return false;
        }
        return true;
    });
}

Map.prototype.roll = function() {
    var mods = this.getFilteredModList();

    var totalWeight = mods.reduce(function(acc, val) {
        return acc + val.weights.default;
    }, 0);
    var roll = Math.random() * totalWeight;
    var sum = 0;

    for (var mod in mods) {
        sum += mods[mod].weights.default;
        if (roll < sum) {
            this.mod = mods[mod];
            //console.log("Applied '" + this.mod.name + "' to " + this.name + ".");
            return this.sextantCost;
        }
    }
}

Map.prototype.isAdjacentTo = function(name) {
    return Boolean(this.adjacent.find(map => map.name === name));
}

// END Map prototype -------------------------------------------

// START atlas prototype ---------------------------------------

function Atlas(maps) {
    this.maps = maps;
    this.savedMods = {};

    for (var map in this.maps) {
        this.savedMods[this.maps[map].name] = this.maps[map].mod;
    }

    //console.log(this.savedMods);
}

Atlas.prototype.reset = function() {
    for (var map in this.savedMods) {
        this.maps[map].mod = this.savedMods[map];
    }
};

// END atlas prototype -----------------------------------------

// create map objects

for (var map in mapData) {
    new Map(map, mapData[map].tier, mapData[map].adjacent, mapData[map].mod);
}

// objectify adjacent arrays

for (var k in maps) {
    var map = maps[k];

    map.adjacent = map.adjacent.map(function(element) {
        if (!maps[element]) {
            throw new Error("Could not convert '" + element + "' to object");
        }
        return maps[element];
    });
}

// sanity check adjacents

for (var k in maps) {
    var map = maps[k];

    map.adjacent.forEach(function(a) {
        if (!a.isAdjacentTo(map.name)) {
            throw new Error("1 sided adjacent relation: " + map.name + ", " + a.name);
        }
    })
}

// block mods

function applyBlockMod(originMap, currentMap) {
    if (currentMap.name == "Shaped Primordial Pool" || currentMap.isAdjacentTo("Shaped Primordial Pool")) {
        return;
    }
    if (currentMap.mod) {
        return;
    }

    // filter out good mods
    // filter non-white mods
    var mods = originMap.getFilteredModList().filter(function(mod) {
        return !goodMods[mod.name];
    }).filter(function(mod) {
        return mod.level == tier.WHITE;
    });

    // sort by weight, descending
    mods.sort(function(a, b) {
        return b.weights.default-a.weights.default;
    });

    currentMap.mod = mods[0];
    console.log("Applied '" + currentMap.mod.name + "' to " + currentMap.name + ".");
}

// First, apply sextants to maps 2 degrees away from Pool.

var m = maps["Shaped Primordial Pool"];

m.adjacent.forEach(function(map) {
    map.adjacent.forEach(function(map2) {
        applyBlockMod(m, map2);
    });
});

// Second, block sextants on Burial Chambers.

m = maps["Burial Chambers"];

m.adjacent.forEach(function(map) {
    map.adjacent.forEach(function(map2) {
        applyBlockMod(m, map2);
    });
});

for (var m in maps) {
    var m = maps[m];

    if (!m.isAdjacentTo("Shaped Primordial Pool")) {
        continue;
    }

    // apply to adjacent maps

    for (var i = 0; i < m.adjacent.length; i++) {
        var c = m.adjacent[i];
        applyBlockMod(m, c);
    }

    // apply to 2nd degree adjacent maps

    for (var i = 0; i < m.adjacent.length; i++) {
        var proxy = m.adjacent[i];

        if (proxy.name == "Shaped Primordial Pool") {
            continue;
        }

        for (var j = 0; j < proxy.adjacent.length; j++) {
            var c = proxy.adjacent[j];
            applyBlockMod(m, c);
        }
    }
}

// create atlas object and snapshot blocked mods
var atl = new Atlas(maps);

// heaps permute --------------------------------------------

var swap = function(array, pos1, pos2) {
    var temp = array[pos1];
    array[pos1] = array[pos2];
    array[pos2] = temp;
};

var heapsPermute = function(array, output, n) {
    n = n || array.length; // set n default to array.length
    if (n === 1) {
        output(array);
    } else {
        for (var i = 1; i <= n; i += 1) {
            heapsPermute(array, output, n - 1);
            if (n % 2) {
                var j = 1;
            } else {
                var j = i;
            }
            swap(array, j - 1, n - 1); // -1 to account for javascript zero-indexing
        }
    }
};

// END heaps permute -------------------------------------------

// START result prototype --------------------------------------

function result(order) {
    this.order = order;
    this.sum_x = 0;
    this.sum_x2 = 0;
    this.n = 0;
}

result.prototype.mean = function() {
    return this.sum_x / this.n;
}

result.prototype.stdDev = function() {
    var mean = this.mean();
    return Math.sqrt(this.sum_x2 / this.n - mean * mean);
}

result.prototype.generateSamples = function(n) {
    // Apply sextants to maps
    for (var iter = 0; iter < n; iter++) {
        atl.reset();
        var cost = 0;

        // First, roll any mod on each map in order.
        this.order.forEach(function(m) {
            if (!maps[m].mod) {
                cost += maps[m].roll();
            }
        });

        // Second, finish rolling each map to a good mod, again respecting the order.
        this.order.forEach(function(m) {
            // While no/bad sextant, keep rolling
            while (!(maps[m].mod && goodMods[maps[m].mod.name])) {
                cost += maps[m].roll();
            }
        });

        this.sum_x += cost;
        this.sum_x2 += cost * cost;
        this.n++;
    }
}

result.prototype.confidenceInterval = function() {
    return 1.645 * (this.stdDev() / Math.sqrt(this.n));
}

// END result prototype ------------------------------------------

function countKeys(a) {
    var n = 0;
    for (var k in a) {
        n++;
    }
    return n;
}

var results = [];

var mapsToRoll = [];
for (var map in maps) {
    if (map == "Shaped Primordial Pool" || maps[map].isAdjacentTo("Shaped Primordial Pool")) {
        console.log(map + " blocks " + countKeys(maps[map].getBlockedMods()) + " mods");
        mapsToRoll.push(map);
    }
}

// create a result entry for every permutation
heapsPermute(mapsToRoll, function(order) {
    /*if ( order[0] !== "Shaped Primordial Pool" ) {
    return;
  }*/

    results.push(new result(order.slice(0)));
});

while (true) {
    var results_b = results.filter(function(r) {
        if (r == results[0] || results[0].n == 0) {
            return true;
        }
        return r.mean() - r.confidenceInterval() <= results[0].mean() + results[0].confidenceInterval();
    });

    if (results_b.length <= 1 || results_b[0].n >= maxIterations) {
        break;
    }

    console.log(results[0].n + " iterations (" + results_b.length + " remaining permutations)");

    var iterTarget = results[0].n + 5000 / Math.sqrt(results_b.length);

    results_b.forEach(function(r) {
        r.generateSamples(iterTarget - r.n);
    });

    results.sort(function(a, b) {
        return a.mean() - b.mean();
    });
}

console.log("Results (up to " + maxIterations + " iterations):");

for (var i = 0; i < results.length; i++) {
    var str = "" + results[i].mean().toFixed(3) + " ± " + results[i].confidenceInterval().toFixed(3) + "c";

    for (var j = 0; j < results[i].order.length; j++) {
        if (j > 0) {
            str += ","
        };
        str += " " + results[i].order[j];
    }

    console.log(str);
}