Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // DavidL1450 - solves PvE instances in Cosmos Quest - now with heroes
- // input now needs to be separated by commas. To enter heroes, do <name>:<level>, for example:
- // a2,e3,lady of twilight:1,e4
- #include <cstdlib>
- #include <iostream>
- #include <vector>
- #include <string>
- #include <map>
- #include <algorithm>
- #include <ctime>
- #include <cmath>
- using namespace std;
- /* #update monster map
- for i in range(40):
- elements = ["a", "w", "e", "f"]
- element = elements[i//10]
- string = s[i]
- #remove last comma
- commaLocation = 0
- for j in range(len(string)):
- if(string[j] == ","):
- commaLocation = j
- string = string[0:commaLocation]
- number = (i%10)+1
- print('{"' + str(element) + str(number) + '", ' + string + '},')
- #update counters list
- for i in range(40):
- element = elements[i//10]
- counter = counters[i//10]
- number = i%10+1
- print('{"' + element + str(number) + '", "' + counter + str(number) + '"},')
- #update heroes - s is the list of heroes, directly from the code.
- def sl(s):
- return s[0:len(s)-1]
- while(True):
- name=a[12*i+0].split('"')[1].lower()
- element = "aefw"[int(sl(a[12*i+1].split(":")[1]))]
- hp = int(sl(a[12*i+4].split(":")[1]))
- attack = int(sl(a[12*i+5].split(":")[1]))
- skill_type = a[12*i+7].split('"')[1]
- skill_target = ["all","a","e","f","w"][1+int(sl(a[12*i+8].split(":")[1]))]
- skill_value = int(a[12*i+9].split(":")[1])
- print('{"' + name +'", monster(' + str(hp)+ ', '+str(attack) + ', 0, "' + str(name) +
- '", "' + str(element) + '", {"' + skill_type + '", "' + skill_target + '" , "' + element+'" , ' + str(skill_value) + '})},')
- i+=1
- * get rarities
- i=0
- while(True):
- name=a[12*i+0].split('"')[1].lower()
- rarity = sl(a[12*i+2].split(":")[1])
- print('{"' + name +'", ' + rarity + '},')
- i+=1
- * get names only
- i=0
- s = ""
- while(True):
- name=a[12*i+0].split('"')[1].lower()
- s += '"' + name + '",'
- i+=1
- */
- vector<string> split(string s, string to_split){
- vector<string> output;
- int x=0;
- int limit=0;
- while(limit != string::npos){
- limit = s.find(to_split, x);
- output.push_back(s.substr(x, limit-x));
- x = limit+to_split.length();
- }
- return output;
- }
- struct hero_skill {
- string type; // can be nothing, dmg, def, aoe, heal
- string target; // all, a,w,e,f
- string source_element;
- int amount; //amount - self explanatory
- };
- hero_skill none = hero_skill({"nothing", "a","a" ,1});
- class army;
- class monster;
- class fight_result{
- public :
- army * source = nullptr;
- fight_result(bool winner, int lost, int damage, int followers, bool dominated, int left_aoe_damage, int right_aoe_damage) : winner(winner), lost(lost), damage(damage), followers(followers),dominated(dominated),left_aoe_damage(left_aoe_damage), right_aoe_damage(right_aoe_damage)
- {};
- bool winner; //false -> left win, true -> right win.
- int lost;
- int damage;
- int left_aoe_damage;
- int right_aoe_damage;
- int followers; // left side's followers
- bool dominated;
- bool operator <= (fight_result & f)
- { // if this left side is said to be dominated by the other left side
- if (winner == false && f.winner == true) { // this left won, that left didn't
- return false;
- }
- if (winner == true && f.winner == false) { // this left lost, that left won
- return true;
- }
- if (winner == false && f.winner == false) { // both lefts won
- return true; // non-strict comparison
- } // the right won here. "lost" is right losses
- if(left_aoe_damage < f.left_aoe_damage || right_aoe_damage > f.right_aoe_damage){
- return false; // more AOE Damage
- }
- if (lost < f.lost) { // this left killed strictly less
- return true;
- }
- if (lost > f.lost) { // this left killed strictly more
- return false;
- }
- if (lost == f.lost) {
- return damage <= f.damage; // left dealt less damage -> left won
- }
- throw "ERROR?";
- };
- bool operator >= (fight_result & f){
- return f <= *this;
- }
- };
- int fights_simulated = 0;
- struct precomputed_fight{
- int lost;
- int damage;
- int left_aoe_damage;
- int right_aoe_damage;
- bool valid;
- };
- class monster{
- public :
- int hp;
- int damage;
- int cost;
- string name; // must be EXACTLY the same as its key in the hash tables.
- string element;
- hero_skill skill;
- monster(int hp, int damage, int cost, string name, string element, hero_skill skill =
- none) : hp(hp), damage(damage), cost(cost), name(name), element(element), skill(skill)
- {};
- };
- class army{
- public:
- vector<monster*> monsters;
- vector<hero_skill *> skills {};
- vector<string> heroes_used {};
- precomputed_fight pf {0,0,0,false};
- army(vector<monster*> monsters):monsters(monsters){
- for(int i=0;i<monsters.size();i++){
- skills.emplace_back(&monsters.at(i)->skill);
- if(monsters.at(i)->skill.type != "nothing"){
- heroes_used.push_back(monsters.at(i)->name);
- }
- }
- };
- void add(monster * m){
- monsters.push_back(m);
- skills.push_back(&m->skill);
- if(m->skill.type != "nothing"){
- heroes_used.push_back(m->name);
- }
- }
- bool used_hero(string s) const{
- return find(heroes_used.begin(), heroes_used.end(), s) != heroes_used.end();
- }
- };
- int my_upper_bound = 2147483647; // apparently "upper_bound" is a vector operation
- army best({});
- struct solution {
- army optimal;
- int followers;
- };
- vector<monster> monster_list{ // non-heroes
- monster(20, 8, 1000, "a1", "a"),
- monster(48, 6, 3900, "a2", "a"),
- monster(36, 12, 8000, "a3", "a"),
- monster(24, 26, 15000, "a4", "a"),
- monster(60, 20, 41000, "a5", "a"),
- monster(62, 34, 96000, "a6", "a"),
- monster(106, 26, 144000, "a7", "a"),
- monster(78, 52, 257000, "a8", "a"),
- monster(116, 54, 495000, "a9", "a"),
- monster(142, 60, 785000, "a10", "a"),
- monster(30, 6, 1400, "w1", "w"),
- monster(24, 12, 3900, "w2", "w"),
- monster(18, 24, 8000, "w3", "w"),
- monster(36, 20, 18000, "w4", "w"),
- monster(78, 18, 52000, "w5", "w"),
- monster(44, 44, 84000, "w6", "w"),
- monster(92, 32, 159000, "w7", "w"),
- monster(108, 36, 241000, "w8", "w"),
- monster(80, 70, 418000, "w9", "w"),
- monster(110, 70, 675000, "w10", "w"),
- monster(44, 4, 1300, "e1", "e"),
- monster(30, 8, 2700, "e2", "e"),
- monster(26, 16, 7500, "e3", "e"),
- monster(72, 10, 18000, "e4", "e"),
- monster(36, 40, 54000, "e5", "e"),
- monster(72, 24, 71000, "e6", "e"),
- monster(66, 36, 115000, "e7", "e"),
- monster(60, 60, 215000, "e8", "e"),
- monster(120, 48, 436000, "e9", "e"),
- monster(122, 64, 689000, "e10", "e"),
- monster(16, 10, 1000, "f1", "f"),
- monster(18, 16, 3900, "f2", "f"),
- monster(54, 8, 8000, "f3", "f"),
- monster(52, 16, 23000, "f4", "f"),
- monster(42, 24, 31000, "f5", "f"),
- monster(104, 20, 94000, "f6", "f"),
- monster(54, 44, 115000, "f7", "f"),
- monster(94, 50, 321000, "f8", "f"),
- monster(102, 58, 454000, "f9", "f"),
- monster(104, 82, 787000, "f10", "f")
- };
- map<string, monster>monster_map{
- {"a1", monster(20, 8, 1000, "a1", "a")},
- {"a2", monster(48, 6, 3900, "a2", "a")},
- {"a3", monster(36, 12, 8000, "a3", "a")},
- {"a4", monster(24, 26, 15000, "a4", "a")},
- {"a5", monster(60, 20, 41000, "a5", "a")},
- {"a6", monster(62, 34, 96000, "a6", "a")},
- {"a7", monster(106, 26, 144000, "a7", "a")},
- {"a8", monster(78, 52, 257000, "a8", "a")},
- {"a9", monster(116, 54, 495000, "a9", "a")},
- {"a10", monster(142, 60, 785000, "a10", "a")},
- {"w1", monster(30, 6, 1400, "w1", "w")},
- {"w2", monster(24, 12, 3900, "w2", "w")},
- {"w3", monster(18, 24, 8000, "w3", "w")},
- {"w4", monster(36, 20, 18000, "w4", "w")},
- {"w5", monster(78, 18, 52000, "w5", "w")},
- {"w6", monster(44, 44, 84000, "w6", "w")},
- {"w7", monster(92, 32, 159000, "w7", "w")},
- {"w8", monster(108, 36, 241000, "w8", "w")},
- {"w9", monster(80, 70, 418000, "w9", "w")},
- {"w10", monster(110, 70, 675000, "w10", "w")},
- {"e1", monster(44, 4, 1300, "e1", "e")},
- {"e2", monster(30, 8, 2700, "e2", "e")},
- {"e3", monster(26, 16, 7500, "e3", "e")},
- {"e4", monster(72, 10, 18000, "e4", "e")},
- {"e5", monster(36, 40, 54000, "e5", "e")},
- {"e6", monster(72, 24, 71000, "e6", "e")},
- {"e7", monster(66, 36, 115000, "e7", "e")},
- {"e8", monster(60, 60, 215000, "e8", "e")},
- {"e9", monster(120, 48, 436000, "e9", "e")},
- {"e10", monster(122, 64, 689000, "e10", "e")},
- {"f1", monster(16, 10, 1000, "f1", "f")},
- {"f2", monster(18, 16, 3900, "f2", "f")},
- {"f3", monster(54, 8, 8000, "f3", "f")},
- {"f4", monster(52, 16, 23000, "f4", "f")},
- {"f5", monster(42, 24, 31000, "f5", "f")},
- {"f6", monster(104, 20, 94000, "f6", "f")},
- {"f7", monster(54, 44, 115000, "f7", "f")},
- {"f8", monster(94, 50, 321000, "f8", "f")},
- {"f9", monster(102, 58, 454000, "f9", "f")},
- {"f10", monster(104, 82, 787000, "f10", "f")}
- };
- map<string, monster> all_monster_map { // includes heroes
- // starts out this way but will be added to later.
- {"a1", monster(20, 8, 1000, "a1", "a")},
- {"a2", monster(48, 6, 3900, "a2", "a")},
- {"a3", monster(36, 12, 8000, "a3", "a")},
- {"a4", monster(24, 26, 15000, "a4", "a")},
- {"a5", monster(60, 20, 41000, "a5", "a")},
- {"a6", monster(62, 34, 96000, "a6", "a")},
- {"a7", monster(106, 26, 144000, "a7", "a")},
- {"a8", monster(78, 52, 257000, "a8", "a")},
- {"a9", monster(116, 54, 495000, "a9", "a")},
- {"a10", monster(142, 60, 785000, "a10", "a")},
- {"w1", monster(30, 6, 1400, "w1", "w")},
- {"w2", monster(24, 12, 3900, "w2", "w")},
- {"w3", monster(18, 24, 8000, "w3", "w")},
- {"w4", monster(36, 20, 18000, "w4", "w")},
- {"w5", monster(78, 18, 52000, "w5", "w")},
- {"w6", monster(44, 44, 84000, "w6", "w")},
- {"w7", monster(92, 32, 159000, "w7", "w")},
- {"w8", monster(108, 36, 241000, "w8", "w")},
- {"w9", monster(80, 70, 418000, "w9", "w")},
- {"w10", monster(110, 70, 675000, "w10", "w")},
- {"e1", monster(44, 4, 1300, "e1", "e")},
- {"e2", monster(30, 8, 2700, "e2", "e")},
- {"e3", monster(26, 16, 7500, "e3", "e")},
- {"e4", monster(72, 10, 18000, "e4", "e")},
- {"e5", monster(36, 40, 54000, "e5", "e")},
- {"e6", monster(72, 24, 71000, "e6", "e")},
- {"e7", monster(66, 36, 115000, "e7", "e")},
- {"e8", monster(60, 60, 215000, "e8", "e")},
- {"e9", monster(120, 48, 436000, "e9", "e")},
- {"e10", monster(122, 64, 689000, "e10", "e")},
- {"f1", monster(16, 10, 1000, "f1", "f")},
- {"f2", monster(18, 16, 3900, "f2", "f")},
- {"f3", monster(54, 8, 8000, "f3", "f")},
- {"f4", monster(52, 16, 23000, "f4", "f")},
- {"f5", monster(42, 24, 31000, "f5", "f")},
- {"f6", monster(104, 20, 94000, "f6", "f")},
- {"f7", monster(54, 44, 115000, "f7", "f")},
- {"f8", monster(94, 50, 321000, "f8", "f")},
- {"f9", monster(102, 58, 454000, "f9", "f")},
- {"f10", monster(104, 82, 787000, "f10", "f")}
- };
- map<string, monster> base_heroes{ // unleveled heroes
- {"lady of twilight", monster(45, 20, 0, "lady of twilight", "a", {"def", "all" , "a" , 1})},
- {"tiny", monster(70, 30, 0, "tiny", "e", {"aoe", "all" , "e" , 2})},
- {"nebra", monster(90, 40, 0, "nebra", "f", {"dmg", "all" , "f" , 4})},
- {"noname a", monster(20, 10, 0, "noname a", "a", {"def", "a" , "a" , 1})},
- {"noname e", monster(30, 8, 0, "noname e", "e", {"def", "e" , "e" , 1})},
- {"noname f", monster(24, 12, 0, "noname f", "f", {"def", "f" , "f" , 1})},
- {"noname w", monster(50, 6, 0, "noname w", "w", {"def", "w" , "w" , 1})},
- {"hunter", monster(22, 14, 0, "hunter", "a", {"dmg", "a" , "a" , 2})},
- {"shaman", monster(40, 20, 0, "shaman", "e", {"def", "e" , "e" , 2})},
- {"alpha", monster(82, 22, 0, "alpha", "f", {"aoe", "all" , "f" , 1})},
- {"carl", monster(28, 12, 0, "carl", "w", {"dmg", "w" , "w" , 2})},
- {"nimue", monster(38, 22, 0, "nimue", "a", {"def", "a" , "a" , 2})},
- {"athos", monster(70, 26, 0, "athos", "e", {"def", "all" , "e" , 2})},
- {"jet", monster(24, 16, 0, "jet", "f", {"dmg", "f" , "f" , 2})},
- {"geron", monster(36, 24, 0, "geron", "w", {"def", "w" , "w" , 2})},
- {"rei", monster(46, 40, 0, "rei", "a", {"dmg", "all" , "a" , 2})},
- {"ailen", monster(19, 22, 0, "ailen", "e", {"dmg", "e" , "e" , 2})},
- {"faefyr", monster(50, 18, 0, "faefyr", "f", {"def", "f" , "f" , 2})},
- {"auri", monster(60, 32, 0, "auri", "w", {"heal", "all" , "w" , 2})}
- };
- map<string, int> rarities { // hero rarities
- {"lady of twilight", 0},
- {"tiny", 1},
- {"nebra", 2},
- {"noname a", 0},
- {"noname e", 0},
- {"noname f", 1},
- {"noname w", 1},
- {"hunter", 0},
- {"shaman", 1},
- {"alpha", 2},
- {"carl", 0},
- {"nimue", 1},
- {"athos", 2},
- {"jet", 0},
- {"geron", 1},
- {"rei", 2},
- {"ailen", 0},
- {"faefyr", 1},
- {"auri", 2}
- };
- map<string, string> countered_by{
- {"a1", "e1"},
- {"a2", "e2"},
- {"a3", "e3"},
- {"a4", "e4"},
- {"a5", "e5"},
- {"a6", "e6"},
- {"a7", "e7"},
- {"a8", "e8"},
- {"a9", "e9"},
- {"a10", "e10"},
- {"w1", "a1"},
- {"w2", "a2"},
- {"w3", "a3"},
- {"w4", "a4"},
- {"w5", "a5"},
- {"w6", "a6"},
- {"w7", "a7"},
- {"w8", "a8"},
- {"w9", "a9"},
- {"w10", "a10"},
- {"e1", "f1"},
- {"e2", "f2"},
- {"e3", "f3"},
- {"e4", "f4"},
- {"e5", "f5"},
- {"e6", "f6"},
- {"e7", "f7"},
- {"e8", "f8"},
- {"e9", "f9"},
- {"e10", "f10"},
- {"f1", "w1"},
- {"f2", "w2"},
- {"f3", "w3"},
- {"f4", "w4"},
- {"f5", "w5"},
- {"f6", "w6"},
- {"f7", "w7"},
- {"f8", "w8"},
- {"f9", "w9"},
- {"f10", "w10"}
- };
- // initialize
- int cost(const army & army_1);
- int enhance_damage(int damage_c, string source_element, string target_element){
- int damage = damage_c;
- if (source_element == "e" && target_element == "a") {
- damage = damage * 1.5;
- }
- if (source_element == "a" && target_element == "w") {
- damage = damage * 1.5;
- }
- if (source_element == "w" && target_element == "f") {
- damage = damage * 1.5;
- }
- if (source_element == "f" && target_element == "e") {
- damage = damage * 1.5;
- }
- return damage;
- }
- vector<int> one_turn(monster & left, const vector<hero_skill *> & left_skills, int index_l, monster & right, const vector<hero_skill *> & right_skills, int index_r) {
- // left attacks right
- // damage the front took, cumulative aoe damage
- // index_l and index_r are the number of monsters lost on the left and right, respectively
- int damage = enhance_damage(left.damage, left.element, right.element);
- int aoe_damage = 0;
- int healing = 0;
- //hero stuff
- hero_skill left_skill;
- hero_skill right_skill;
- for(int i=index_r;i<right_skills.size();i++){
- right_skill = *right_skills.at(i);
- if (right_skill.type == "def" && (right_skill.target == "all" || right_skill.target == right.element)) {
- damage -= right_skill.amount;
- }
- if (right_skill.type == "heal" && (right_skill.target == "all" || right_skill.target == right.element)) {
- healing += right_skill.amount;
- }
- }
- for(int i=index_l;i<left_skills.size();i++){
- left_skill = *left_skills.at(i);
- if (left_skill.type == "aoe" && (left_skill.target == "all" || left_skill.target == right.element)) {
- aoe_damage += left_skill.amount;
- }
- if (left_skill.type == "dmg" && (left_skill.target == "all" || left_skill.target == left.element)) {
- damage += enhance_damage(left_skill.amount, left.element, right.element);
- }
- }
- damage = max(0, damage);
- return {damage, healing, aoe_damage};
- }
- fight_result simulate_fight(const army & left, const army & right, bool verbose = false) {
- //fights left to right, so left[0] and right[0] are the first to fight
- fights_simulated++;
- int left_lost = 0;
- int left_damage_taken = 0;
- int right_lost = 0;
- int right_damage_taken = 0;
- int left_cumulative_aoe_damage =0;
- int right_cumulative_aoe_damage = 0; //all this is damage taken
- // a suffix for this fight was already pre-computed
- if(left.pf.valid && verbose == false){
- // can use pre-computed values
- left_lost = left.monsters.size()-1;
- left_damage_taken = left.pf.left_aoe_damage;
- right_lost = left.pf.lost;
- right_damage_taken = left.pf.damage;
- right_cumulative_aoe_damage = left.pf.right_aoe_damage;
- }
- while (left_lost < left.monsters.size() && right_lost < right.monsters.size()) {
- //attack once - first get parameters
- monster left_monster = *left.monsters.at(left_lost);
- monster right_monster = *right.monsters.at(right_lost);
- //get hero skill
- vector<int> left_attack = one_turn(left_monster, left.skills, left_lost, right_monster, right.skills, right_lost);
- vector<int> right_attack = one_turn(right_monster, right.skills, right_lost, left_monster, left.skills, left_lost);
- right_damage_taken += left_attack.at(0) + left_attack.at(2);
- left_damage_taken += right_attack.at(0) + right_attack.at(2);
- right_cumulative_aoe_damage += left_attack.at(2);
- left_cumulative_aoe_damage += right_attack.at(2);
- //check for deaths
- while(left_lost < left.monsters.size() && left_damage_taken >= left.monsters.at(left_lost)->hp) {
- left_damage_taken = left_cumulative_aoe_damage ;
- left_lost++;
- }
- while(right_lost < right.monsters.size() && right_damage_taken >= right.monsters.at(right_lost)->hp) {
- right_damage_taken = right_cumulative_aoe_damage;
- right_lost++;
- }
- // healing - does not take effect on death
- left_damage_taken = max(0, left_damage_taken - right_attack.at(1));
- right_damage_taken = max(0, right_damage_taken - left_attack.at(1));
- if (verbose == true) {
- cout << left_lost << " " << left_damage_taken << " " << right_lost << " " << right_damage_taken << "\n";
- }
- }
- //draws count as right wins.
- if(verbose == true && left_lost == left.monsters.size() && right_lost == right.monsters.size()){
- cout << "Draw\n";
- }
- if (left_lost == left.monsters.size()) {
- return fight_result(true, right_lost, right_damage_taken, cost(left), false,left_cumulative_aoe_damage, right_cumulative_aoe_damage);
- }
- //left wins if the code gets here.
- return fight_result(false, left_lost, left_damage_taken, cost(left), false, left_cumulative_aoe_damage, right_cumulative_aoe_damage);
- }
- vector<fight_result> simulate_multiple_fights(vector<army> & list, army & target, bool change_optimal = true){//
- //simulates all of the fights from list and puts it into a vector of fight_results.
- vector<fight_result> output;
- output.reserve(list.size());
- for (int i = 0; i < list.size(); i++) {
- fight_result this_result = simulate_fight(list.at(i), target);
- this_result.source = &list.at(i);
- if (this_result.winner == false && cost(list.at(i)) < my_upper_bound && change_optimal) { // left (our side) wins:
- my_upper_bound = this_result.followers;
- vector<string> best_names {};
- for(int j=0;j<list.at(i).monsters.size();j++){
- best_names.push_back(list.at(i).monsters.at(j)->name );
- }
- best = army(vector<monster *> {});
- for(int j=0;j<best_names.size();j++){
- best.add(&all_monster_map.at(best_names.at(j)));
- }
- //fix the pointers in best - the heroes_available in solve_instance is not global scope.
- }
- output.push_back(this_result); //still need this for consistency
- }
- return output;
- }
- void expand(vector<army> * source, vector<fight_result> ¤t_armies, vector<monster> & to_expand_with, int my_upper_bound, bool check_heroes_repeat){
- // expand stuff directly onto source, does not expand dominated or winning or too costly armies
- // if the bool is true, we check if we repeat any heroes
- for(int i=0;i<current_armies.size();i++){
- fight_result * this_result = ¤t_armies.at(i);
- if(this_result->dominated == true || this_result->winner == false){
- continue;
- }
- for(int j=0; j < to_expand_with.size();j++){
- if(this_result->followers + to_expand_with.at(j).cost >= my_upper_bound){
- continue;
- }
- bool can_use = true;
- if(check_heroes_repeat){
- string current_name = to_expand_with.at(j).name;
- for(int k=0; k < this_result->source->heroes_used.size();k++){
- if(this_result->source->heroes_used.at(k) == current_name ){
- can_use = false;
- break;
- }
- }
- }
- if(can_use == false){
- continue;
- }
- source->push_back(*(this_result->source));
- source->at(source->size() - 1).add(&to_expand_with.at(j));
- if(to_expand_with.at(j).skill.type == "nothing")
- {
- source->at(source->size() - 1).pf = precomputed_fight({this_result->lost, this_result->damage, this_result->left_aoe_damage, this_result->right_aoe_damage, true}); // pre-computed fight
- } else{
- source->at(source->size() - 1).pf.valid = false;
- }
- }
- }
- }
- int cost(const army & m) {
- int result = 0;
- for (int i = 0; i < m.monsters.size(); i++) {
- result = result + m.monsters.at(i)->cost;
- }
- return result;
- }
- bool function_compare(fight_result & a, fight_result & b) { // used for sorting.
- return (a.followers < b.followers);
- }
- monster level_up_hero(const monster & m, int rarity, int level){
- int points = level-1;
- if(rarity == 1){
- points = 2 * points;
- }
- if(rarity == 2){
- points = 6* points;
- }
- int value = m.hp + m.damage;
- return monster(floor(m.hp + points * ((double)m.hp) / value),
- m.damage + floor(points * ((double)m.damage) / value),
- m.cost,
- m.name,
- m.element,
- m.skill
- );
- }
- string add_hero_string(string s){
- //turns a string representing a hero into its actual hero
- //adds it into all_monsters_map
- //for example, "lady of twilight:1" adds a level 1 lady of twilight into the all_monsters_map
- //returns the name of the hero as stored in the hash table
- string t = s.substr(0, s.find(':'));
- int level = stoi(s.substr(s.find(':')+1));
- monster m = level_up_hero(base_heroes.at(t), rarities.at(t), level);
- string name = t + ":" + to_string(level);
- m.name = name;
- all_monster_map.insert({name, m});
- return m.name;
- }
- solution solve_instance(vector<monster> heroes_available, army target, int limit, bool time_it) {
- army trial({});
- //try to get a good upper bound by looking at counters
- for (int i = 0; i < target.monsters.size() && i < limit; i++) {
- if(countered_by.count(target.monsters.at(i)->name) != 0){ // if it is not a hero
- trial.add(&monster_map.at(countered_by.at(target.monsters.at(i)->name)));
- }
- }
- fight_result this_result = simulate_fight(trial, target);
- if (this_result.winner == false) {
- my_upper_bound = cost(trial);
- best = trial;
- }
- //check if optimizable - if no single monster can defeat the last two monsters, then we can optimize
- bool optimizable = (target.monsters.size() >= 3);
- if (target.monsters.size() >= 3) {
- // get the last two
- army last2 = army({target.monsters.at(target.monsters.size() - 2), target.monsters.at(target.monsters.size() - 1)});
- for (int i = 0; i < monster_list.size(); i++) {
- if (monster_list.at(i).cost > my_upper_bound) {
- continue;
- }
- army fighting({ &all_monster_map.at(monster_list.at(i).name)});
- fight_result s = simulate_fight(fighting, last2);
- if (s.winner == false) {
- //single monster can defeat last 2 -> cannot optimize
- optimizable = false;
- break;
- }
- }
- for (int i = 0; i < heroes_available.size(); i++) {
- army fighting({&all_monster_map.at(heroes_available.at(i).name)});
- fight_result s = simulate_fight(fighting, last2);
- if (s.winner == false) {
- //single monster can defeat last 2 -> cannot optimize
- optimizable = false;
- break;
- }
- }
- }
- vector<army >optimal = {}; // initialize with all single monsters
- vector<army >optimal_heroes = {}; // initialize with all heroes
- for (int i = 0; i < monster_list.size(); i++) {
- optimal.emplace_back(vector<monster *>{&all_monster_map.at(monster_list.at(i).name)});
- }
- for (int i = 0; i < heroes_available.size(); i++) {
- optimal_heroes.emplace_back(vector<monster *>{&all_monster_map.at(heroes_available.at(i).name)});// emplace back!
- }
- //best so far
- for (int c = 1; c <= limit; c++) { // c is the length of the list of monsters
- if (time_it == true) {
- cout << "TIME : starting loop " << optimal.size() << " " << optimal_heroes.size() << " " << time(NULL) << "\n";
- }
- // for each optimal result (that is, not known to be dominated), fight against the target and record values
- vector<fight_result> result = simulate_multiple_fights(optimal, target, true);
- if (time_it == true) {
- cout << "TIME : finished fighting for non-heroes " << optimal.size() << " " << optimal_heroes.size() << " " << time(NULL) << "\n";
- }
- vector<fight_result> result_heroes = simulate_multiple_fights(optimal_heroes, target, true);
- if (time_it == true) {
- cout << "TIME : finished fight, starting sort " << time(NULL) << "\n";
- }
- if (c != limit) { // do not do the last expansion
- //sort so we can stop early
- sort(result.begin(), result.end(), function_compare);
- sort(result_heroes.begin(), result_heroes.end(), function_compare);
- // do not use optimal.at(i) anymore, replace with (*(result.at(i).source))
- if (time_it == true) {
- cout << "TIME : finished sort, starting check dominance " << time(NULL) << "\n";
- }
- for (int i = 0; i < optimal.size(); i++) { // non-heroes
- // it is also dominated if c+1 = limit (one monster left) and the last 2 monsters are still alive
- if (c + 1 == limit && optimizable == true) {
- if (result.at(i).winner == true && result.at(i).lost < target.monsters.size() - 2 && result.at(i).right_aoe_damage == 0){
- /*
- cout << "OPTIMIZED OUT"; //debug
- for (monster m : *(result.at(i).source)){
- cout << m.name << " ";
- } // end debug
- */
- result.at(i).dominated = true;
- }
- }
- if (result.at(i).dominated == false) {
- for (int j = i + 1; j < optimal.size(); j++) {
- // if i costs more followers and got less far than j, then i is dominated
- // set optimal[i][0]'s name to dominated
- if (result.at(i).followers >= result.at(j).followers && result.at(i) <= result.at(j)) {
- result.at(i).dominated = true;
- break;
- }
- if (result.at(i).followers < result.at(j).followers) {
- break; // since the list is sorted
- }
- }
- for(int j=0; j<optimal_heroes.size();j++){// non-heroes dominate heroes
- if (result.at(i).followers <= result_heroes.at(j).followers && result.at(i) >= result_heroes.at(j) ) {
- result_heroes.at(j).dominated = true;
- }
- if (result.at(i).followers > result_heroes.at(j).followers) {
- break; // since the list is sorted
- }
- }
- }
- }
- //domination for heroes:
- for (int i = 0; i < optimal_heroes.size(); i++) {
- // it is also dominated if c+1 = limit (one monster left) and the last 2 monsters
- // are still alive, but we also require no AOE damage dealt
- if (c + 1 == limit && optimizable == true && result_heroes.at(i).right_aoe_damage == 0) {
- if (result_heroes.at(i).winner == true && result_heroes.at(i).lost < target.monsters.size() - 2){
- result_heroes.at(i).dominated = true;
- }
- }
- if (result_heroes.at(i).dominated != true ){
- for (int j = i + 1; j < optimal_heroes.size(); j++) {
- // if i costs more followers and got less far than j, then i is dominated
- // set optimal[i][0]'s name to dominated
- if (result_heroes.at(i).followers >= result_heroes.at(j).followers && result_heroes.at(i) <= result_heroes.at(j)) {
- bool used = false;// i did not use a hero that j used, so j cannot dominate i
- for(int sj = 0; sj < result_heroes.at(j).source->heroes_used.size();sj++){
- string j_hero = result_heroes.at(j).source->heroes_used.at(sj);
- bool i_used_hero = false;
- for(int si = 0; si < result_heroes.at(i).source->heroes_used.size();si++){
- string i_hero = result_heroes.at(i).source->heroes_used.at(si);
- if(i_hero == j_hero){
- i_used_hero = true;
- break;
- }
- }
- if(i_used_hero == false){
- used = true;
- break;
- }
- }
- if(used == false){
- result_heroes.at(i).dominated = true;
- break;
- }
- }
- if (result_heroes.at(i).followers < result_heroes.at(j).followers) {
- break; // since the list is sorted
- }
- }
- }
- }
- //
- // now we expand to add the next monster to all non-dominated armies
- if (time_it == true) {
- cout << "TIME : finished check dominance, starting expanding " << time(NULL) << "\n";
- }
- vector<army > next_optimal;
- expand(&next_optimal, result, monster_list, my_upper_bound, false);
- vector<army > next_optimal_heroes;
- expand(&next_optimal_heroes, result_heroes, monster_list, my_upper_bound, false);
- expand(&next_optimal_heroes, result, heroes_available, my_upper_bound, false);
- expand(&next_optimal_heroes, result_heroes, heroes_available, my_upper_bound, true);
- if (time_it == true) {
- cout << "TIME : finished expanding (move)" << time(NULL) << "\n";
- }
- optimal = move(next_optimal);
- optimal_heroes = move(next_optimal_heroes);
- }
- }
- return {best, my_upper_bound};
- }
- void test_cases(){
- // test cases for dominance of fight_results
- add_hero_string("rei:3");
- add_hero_string("hunter:2");
- add_hero_string("rei:1");
- add_hero_string("tiny:1");
- solution solv = solve_instance({all_monster_map.at("tiny:1"),all_monster_map.at("rei:1"),},
- army(vector<monster*>{
- &all_monster_map.at("a4"),&all_monster_map.at("f5"),&all_monster_map.at("e4"),&all_monster_map.at("w5"),&all_monster_map.at("a5")
- }), 6, true);
- // don't know the true value, so I can't tell. only doing this to see if there are exceptions.
- add_hero_string("lady of twilight:1");
- add_hero_string("jet:1");
- for(int i=0; i<solv.optimal.monsters.size();i++){
- cout << (solv.optimal.monsters.at(i) -> name) << " ";
- }
- cout << "\n";
- /*
- 0 16 0 8
- 0 32 0 16
- 0 48 1 0
- 1 0 1 8
- 1 12 2 0
- 1 24 2 6
- 2 0 2 12
- 2 12 2 18
- 2 24 3 0
- 3 0 3 9
- 3 27 3 13
- 4 0 3 17
- 4 16 4 0
- 4 22 4 12
- 5 0 4 24
- */
- simulate_fight(army(vector<monster*>{
- &all_monster_map.at("f3"),
- &all_monster_map.at("w1"),
- &all_monster_map.at("w1"),
- &all_monster_map.at("e1"),
- &all_monster_map.at("w2")
- }),
- army(vector<monster*>{
- &all_monster_map.at("hunter:2"),
- &all_monster_map.at("f1"),
- &all_monster_map.at("a1"),
- &all_monster_map.at("jet:1"),
- &all_monster_map.at("w1"),
- &all_monster_map.at("e2")
- }), true);
- //
- cout << "YAY?\n";
- /*
- 0 42 0 6
- 1 0 0 12
- 2 0 0 24
- 3 0 0 36
- 4 0 0 44
- 5 0 1 0
- 5 9 1 16
- 6 0 2 0
- */
- simulate_fight(army(vector<monster*>{
- &all_monster_map.at("e1"),
- &all_monster_map.at("e2"),
- &all_monster_map.at("w2"),
- &all_monster_map.at("a1"),
- &all_monster_map.at("w2"),
- &all_monster_map.at("f2")
- }),
- army(vector<monster*>{
- &all_monster_map.at("rei:1"),
- &all_monster_map.at("w1"),
- &all_monster_map.at("e1"),
- &all_monster_map.at("f1"),
- &all_monster_map.at("a1"),
- &all_monster_map.at("e1")
- }), true);
- cout << "YAY!";
- /*
- 0 66 0 26
- 1 0 0 52
- 1 44 1 0
- 1 98 1 28
- 2 0 1 56
- 2 36 2 0
- 2 87 2 34
- 3 0 3 0
- 4 0 4 0
- 4 66 4 26
- 5 0 4 52
- 5 44 5 0
- 6 0 6 0
- Draw
- */
- simulate_fight(army(vector<monster*>{
- &all_monster_map.at("e6"),
- &all_monster_map.at("a7"),
- &all_monster_map.at("w7"),
- &all_monster_map.at("f7"),
- &all_monster_map.at("e6"),
- &all_monster_map.at("rei:1")
- }),
- army(vector<monster*>{
- &all_monster_map.at("f7"),
- &all_monster_map.at("e7"),
- &all_monster_map.at("a6"),
- &all_monster_map.at("w6"),
- &all_monster_map.at("f7"),
- &all_monster_map.at("w6")
- }), true);
- cout << "YAY!\n";
- // 63 damage, 9 damage
- int damage_dealt =one_turn({all_monster_map.at("rei:1")}, {&all_monster_map.at("rei:1").skill}, 0, {all_monster_map.at("w6")}, {&all_monster_map.at("w6").skill}, 0).at(0);
- int damage_dealt_2 =one_turn({all_monster_map.at("a2")}, {&all_monster_map.at("a2").skill}, 0, {all_monster_map.at("w2")}, {&all_monster_map.at("w2").skill}, 0).at(0);
- cout << damage_dealt << " "<< damage_dealt_2<<"\n";
- add_hero_string("faefyr:3");
- }
- int main(int argc, char** argv) {
- //test_cases();
- cout << sizeof(army) << " " << sizeof(fight_result )<< " " << sizeof(hero_skill) << "\n";
- bool time_it = (argc == 3); // if set to true, it will show how much time each step takes
- vector<monster *> target; //somehow get stuff here
- vector<monster *> target2;
- vector<string> target_s;
- string target_string = "";
- if (argc == 2) { // custom input mode
- while (true) {
- target.clear();
- target2.clear();
- cout << "enter the sequence 1 left to right. Enter done to stop ";
- getline(cin, target_string);
- if (target_string == "done") {
- break;
- }
- target_s = split(target_string, ",");
- //get the heroes and add them
- for(int i=0; i<target_s.size();i++){
- if(target_s.at(i).find(":") != target_s.at(i).npos){
- add_hero_string(target_s.at(i));
- }
- }
- for(int i=0; i<target_s.size();i++){
- target.push_back(&all_monster_map.at(target_s.at(i)));
- }
- cout << "enter the sequence 2 left to right ";
- getline(cin, target_string);
- target_s = split(target_string, ",");
- //get the heroes and add them
- for(int i=0; i<target_s.size();i++){
- if(target_s.at(i).find(":") != target_s.at(i).npos){
- add_hero_string(target_s.at(i));
- }
- }
- for(int i=0; i<target_s.size();i++){
- target2.push_back(&all_monster_map.at(target_s.at(i)));
- }
- fight_result custom_result = simulate_fight(army(target), army(target2), true);
- cout << custom_result.winner << " " << cost(army(target)) << " " << cost(army(target2)) << "\n";
- }
- return 0;
- }
- cout << "enter the enemy sequence left to right ";
- getline(cin, target_string);
- target_s = split(target_string, ",");
- //get the heroes and add them
- for(int i=0; i<target_s.size();i++){
- if(target_s.at(i).find(":") != target_s.at(i).npos){
- add_hero_string(target_s.at(i));
- }
- }
- for(int i=0; i<target_s.size();i++){
- target.push_back(&all_monster_map.at(target_s.at(i)));
- }
- int limit = 0; // somehow get stuff here.
- cout << "enter the maximum number of monsters";
- getline(cin, target_string);
- limit = stoi(target_string);
- vector<monster> available_heroes {};
- vector<string> all_heroes {"lady of twilight","tiny","nebra","noname a","noname e","noname f","noname w","hunter","shaman","alpha","carl","nimue","athos","jet","geron","rei","ailen","faefyr","auri"};
- string level_c = "";
- for(int i=0;i<all_heroes.size();i++){
- cout<< "enter the level of " << all_heroes.at(i) << " or nothing if you don't have it";
- getline(cin, level_c);
- if(level_c == ""){
- level_c = "0";
- }
- if(stoi(level_c) != 0){
- available_heroes.push_back( all_monster_map.at(add_hero_string(all_heroes.at(i) + ":" + to_string(stoi(level_c)) )));
- }
- }
- solution solu = solve_instance(available_heroes, army(target), limit, time_it);
- //last check to see if winning combination wins:
- army best = solu.optimal;
- int my_upper_bound = solu.followers;
- if (my_upper_bound != 2147483647) {
- best.pf.valid = false;
- fight_result final_result = simulate_fight(best, target);
- if (final_result.winner == true) {
- for (int i = 1; i <= 100; i++) {
- cout << "ERROR";
- }
- throw 32;
- }
- }
- // print out the winning combination!
- cout << "The minimum number of followers is : " << my_upper_bound;
- cout << "\nand the winning combination is:\n";
- for (int i = 0; i < best.monsters.size(); i++) {
- cout << best.monsters.at(best.monsters.size() - 1 - i)->name << " "; // backwards
- }
- cout << "\n" << "(right-most fights first)\n" << fights_simulated << " fights simulated\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement