updated monster killing

// DavidL1450 - solves PvE instances in Cosmos Quest

#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <ctime>
using namespace std;

class monster;

class fight_result{
public:

    vector<monster> * source = nullptr;
    fight_result(bool winner, int lost, int damage, int followers):winner(winner), lost(lost),damage(damage),followers(followers){};
    bool winner;//false -> left win, true -> right win.
    int lost;
    int damage;
    int followers; // left side's followers
    bool operator<= (fight_result & f){ // if this left side did non-strictly worse than 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(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
        }
    };
};
int fights_simulated = 0;
class monster{
public:
    int hp;
    int damage;
    int cost;
    string name;
    string element;
    monster(int hp, int damage, int cost, string name, string element):hp(hp),damage(damage),cost(cost),name(name),element(element){};
    int fight(string enemy_element){ // target's element
        if(element == "e" && enemy_element == "a"){
            return damage*1.5;
        }if(element == "a" && enemy_element == "w"){
            return damage*1.5;
        }if(element == "w" && enemy_element == "f"){
            return damage*1.5;
        }if(element == "f" && enemy_element == "e"){
            return damage*1.5;
        }
        return damage;
    };
};

vector<monster> monster_list {
    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, 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(vector<monster> & army);
fight_result simulate_fight(vector<monster> & left, vector<monster> & right){
    //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;
    while(left_lost < left.size() && right_lost < right.size()){
        //attack once
        right_damage_taken += left.at(left_lost).fight(right.at(right_lost).element);
        left_damage_taken += right.at(right_lost).fight(left.at(left_lost).element);
        //check for deaths
        if(left_damage_taken >= left.at(left_lost).hp){
            left_damage_taken = 0;
            left_lost++;
        }
        if(right_damage_taken >= right.at(right_lost).hp){
            right_damage_taken = 0;
            right_lost++;
        }
    }
    //draws count as right wins.
    if(left_lost == left.size()){
        return fight_result(true, right_lost, right_damage_taken, cost(left));
    }
    return fight_result(false, left_lost, left_damage_taken,cost(left));
}

int cost(vector<monster> & m){
    int result = 0;
    for(int i=0;i<m.size();i++){
        result = result + m.at(i).cost;
    }
    return result;
}
bool function_compare(fight_result & a, fight_result & b){
    return (a.followers < b.followers);
}
int main(int argc, char** argv) {
    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
    string target_string;
    cout << "enter the enemy sequence left to right ";
    getline(cin,  target_string);
	string parsing = "";
    for(int i=0; i < target_string.length();i++){
		if(target_string.at(i) != ' '){
			parsing = parsing + target_string.at(i);
		}
		else {
			target.push_back(monster_map.at(parsing));
			parsing = "";
		}
    }
	target.push_back(monster_map.at(parsing));
    int limit = 0; // somehow get stuff here.
    cout << "enter the maximum number of monsters ";
    cin >> limit;
    vector<vector<monster> >optimal = {}; // initialize with all single monsters
    for(int i=0; i<monster_list.size();i++){
        optimal.push_back(vector<monster>{monster_list.at(i)});
    }
    //get a good upper bound

    int upper_bound = 99999999;
    vector<monster> trial {};
    vector<monster> best {};
    for(int i=0; i < target.size() && i < limit;i++){
        trial.push_back(monster_map.at(countered_by.at(target.at(i).name) ));
    }
    fight_result this_result = simulate_fight(trial, target);
    if(this_result.winner == false){
        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.size() >= 3);
	if(target.size() >= 3){
		vector<monster> last2 = {target.at(target.size()-2), target.at(target.size()-1) };
		for(int i=0; i < monster_list.size(); i++){
			if(monster_list.at(i).cost > upper_bound){
				continue;
			}
			vector<monster> fighting { monster_list.at(i)};
			fight_result s = simulate_fight(  fighting, last2);
			if(s.winner == false){
				//single monster can defeat last 2 -> cannot optimize
				optimizable = false;
			}
		}
	}

    //best so far
    for(int c=1; c <= limit; c++){
        if(time_it == true){
            cout << "TIME : starting loop " << time(NULL) << "\n";
        }
        vector<fight_result> result {};
        // for each optimal result (that is, not known to be dominated), fight against the target and record values
        for(int i=0; i<optimal.size();i++){
            fight_result this_result = simulate_fight(optimal.at(i), target);
            this_result.source = &optimal.at(i);
            if(this_result.winner == false && cost(optimal.at(i)) < upper_bound ){ // left (our side) wins:
                upper_bound =  this_result.followers;
                best = optimal.at(i);
            }
            result.push_back(this_result);

        }
        if(time_it == true){
            cout << "TIME : finished fight, starting sort " << time(NULL) << "\n";
        }
		if(c != limit){ // do not do the last expansion
			//sort for O(n) searching
	  //       //faster lookup
			sort(result.begin(), result.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++){
				// 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.size()-2)
					/*
					cout << "OPTIMIZED OUT"; //debug
					for (monster m : *(result.at(i).source)){
						cout << m.name << " ";
					} // end debug
					*/
					(*(result.at(i).source)).at(0).name = "dominated";
				}
				if((*(result.at(i).source)).at(0).name != "dominated"){
					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).source)).at(0).name = "dominated";
						}
						if(result.at(i).followers < result.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<vector<monster> > next_optimal {};
			for(int i=0;i<optimal.size();i++){
				for(int m=0; m < monster_list.size();m++){
					monster x = monster_list.at(m);
					if((*(result.at(i).source)).at(0).name != "dominated" && (result.at(i).followers + x.cost) < upper_bound){
						// expand: next_optimal.append( x + optimal.at(i)), for every monster x that keeps followers count strictly less than the upper bound.;
						next_optimal.push_back((*(result.at(i).source)));
						next_optimal.at(next_optimal.size()-1).push_back(x);
					}
				}
			}
			if(time_it == true){
				cout << "TIME : finished expanding (move)" << time(NULL) << "\n";
			}
			optimal = move(next_optimal);
		}
    }
    // print out the winning combination!
    cout << "The minimum number of followers is : " << upper_bound;
    cout << "\nand the winning combination is:\n";
    for(int i=0; i<best.size();i++){
        cout << best.at(best.size()-1-i).name << " "; // backwards
    }
    cout << "\n" << "(right-most fights first)\n" << fights_simulated << " fights simulated\n";
    return 0;
}