// 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);
}