API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jun 25th, 2017
310
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 40.24 KB | None | 0 0
raw download clone embed print report
  1. // DavidL1450 - solves PvE instances in Cosmos Quest - now with heroes
  2. // input now needs to be separated by commas. To enter heroes, do <name>:<level>, for example:
  3. // a2,e3,lady of twilight:1,e4
  4. #include <cstdlib>
  5. #include <iostream>
  6. #include <vector>
  7. #include <string>
  8. #include <map>
  9. #include <algorithm>
  10. #include <ctime>
  11. #include <cmath>
  12. using namespace std;
  13.  
  14. /* #update monster map
  15. for i in range(40):
  16. elements = ["a", "w", "e", "f"]
  17. element = elements[i//10]
  18. string = s[i]
  19. #remove last comma
  20. commaLocation = 0
  21. for j in range(len(string)):
  22. if(string[j] == ","):
  23. commaLocation = j
  24. string = string[0:commaLocation]
  25. number = (i%10)+1
  26. print('{"' + str(element) + str(number) + '", ' + string + '},')
  27.  
  28. #update counters list
  29.  
  30. for i in range(40):
  31. element = elements[i//10]
  32. counter = counters[i//10]
  33. number = i%10+1
  34. print('{"' + element + str(number) + '", "' + counter + str(number) + '"},')
  35.  
  36. #update heroes - s is the list of heroes, directly from the code.
  37. def sl(s):
  38. return s[0:len(s)-1]
  39.  
  40. while(True):
  41. name=a[12*i+0].split('"')[1].lower()
  42. element = "aefw"[int(sl(a[12*i+1].split(":")[1]))]
  43. hp = int(sl(a[12*i+4].split(":")[1]))
  44. attack = int(sl(a[12*i+5].split(":")[1]))
  45. skill_type = a[12*i+7].split('"')[1]
  46. skill_target = ["all","a","e","f","w"][1+int(sl(a[12*i+8].split(":")[1]))]
  47. skill_value = int(a[12*i+9].split(":")[1])
  48. print('{"' + name +'", monster(' + str(hp)+ ', '+str(attack) + ', 0, "' + str(name) +
  49. '", "' + str(element) + '", {"' + skill_type + '", "' + skill_target + '" , "' + element+'" , ' + str(skill_value) + '})},')
  50. i+=1
  51.  
  52.  
  53. * get rarities
  54. i=0
  55. while(True):
  56. name=a[12*i+0].split('"')[1].lower()
  57. rarity = sl(a[12*i+2].split(":")[1])
  58. print('{"' + name +'", ' + rarity + '},')
  59. i+=1
  60. * get names only
  61. i=0
  62. s = ""
  63. while(True):
  64. name=a[12*i+0].split('"')[1].lower()
  65. s += '"' + name + '",'
  66. i+=1
  67. */
  68.  
  69. vector<string> split(string s, string to_split){
  70. vector<string> output;
  71. int x=0;
  72. int limit=0;
  73. while(limit != string::npos){
  74. limit = s.find(to_split, x);
  75. output.push_back(s.substr(x, limit-x));
  76. x = limit+to_split.length();
  77. }
  78. return output;
  79. }
  80.  
  81. struct hero_skill {
  82. string type; // can be nothing, dmg, def, aoe, heal
  83. string target; // all, a,w,e,f
  84. string source_element;
  85. int amount; //amount - self explanatory
  86. };
  87. hero_skill none = hero_skill({"nothing", "a","a" ,1});
  88. class army;
  89. class monster;
  90.  
  91. class fight_result{
  92. public :
  93.  
  94. army * source = nullptr;
  95. 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)
  96. {};
  97. bool winner; //false -> left win, true -> right win.
  98. int lost;
  99. int damage;
  100. int left_aoe_damage;
  101. int right_aoe_damage;
  102. int followers; // left side's followers
  103. bool dominated;
  104. bool operator <= (fight_result & f)
  105. { // if this left side is said to be dominated by the other left side
  106. if (winner == false && f.winner == true) { // this left won, that left didn't
  107. return false;
  108. }
  109. if (winner == true && f.winner == false) { // this left lost, that left won
  110. return true;
  111. }
  112. if (winner == false && f.winner == false) { // both lefts won
  113. return true; // non-strict comparison
  114. } // the right won here. "lost" is right losses
  115. if(left_aoe_damage < f.left_aoe_damage || right_aoe_damage > f.right_aoe_damage){
  116. return false; // more AOE Damage
  117. }
  118. if (lost < f.lost) { // this left killed strictly less
  119. return true;
  120. }
  121. if (lost > f.lost) { // this left killed strictly more
  122. return false;
  123. }
  124. if (lost == f.lost) {
  125. return damage <= f.damage; // left dealt less damage -> left won
  126. }
  127. throw "ERROR?";
  128. };
  129. bool operator >= (fight_result & f){
  130. return f <= *this;
  131. }
  132. };
  133. int fights_simulated = 0;
  134.  
  135. struct precomputed_fight{
  136. int lost;
  137. int damage;
  138. int left_aoe_damage;
  139. int right_aoe_damage;
  140. bool valid;
  141. };
  142.  
  143. class monster{
  144. public :
  145. int hp;
  146. int damage;
  147. int cost;
  148. string name; // must be EXACTLY the same as its key in the hash tables.
  149. string element;
  150. hero_skill skill;
  151. monster(int hp, int damage, int cost, string name, string element, hero_skill skill =
  152. none) : hp(hp), damage(damage), cost(cost), name(name), element(element), skill(skill)
  153. {};
  154. };
  155.  
  156. class army{
  157. public:
  158. vector<monster*> monsters;
  159. vector<hero_skill *> skills {};
  160. vector<string> heroes_used {};
  161. precomputed_fight pf {0,0,0,false};
  162. army(vector<monster*> monsters):monsters(monsters){
  163. for(int i=0;i<monsters.size();i++){
  164. skills.emplace_back(&monsters.at(i)->skill);
  165. if(monsters.at(i)->skill.type != "nothing"){
  166. heroes_used.push_back(monsters.at(i)->name);
  167. }
  168.  
  169. }
  170. };
  171. void add(monster * m){
  172. monsters.push_back(m);
  173. skills.push_back(&m->skill);
  174. if(m->skill.type != "nothing"){
  175. heroes_used.push_back(m->name);
  176. }
  177. }
  178. bool used_hero(string s) const{
  179. return find(heroes_used.begin(), heroes_used.end(), s) != heroes_used.end();
  180. }
  181. };
  182. int my_upper_bound = 2147483647; // apparently "upper_bound" is a vector operation
  183. army best({});
  184. struct solution {
  185. army optimal;
  186. int followers;
  187. };
  188. vector<monster> monster_list{ // non-heroes
  189. monster(20, 8, 1000, "a1", "a"),
  190. monster(48, 6, 3900, "a2", "a"),
  191. monster(36, 12, 8000, "a3", "a"),
  192. monster(24, 26, 15000, "a4", "a"),
  193. monster(60, 20, 41000, "a5", "a"),
  194. monster(62, 34, 96000, "a6", "a"),
  195. monster(106, 26, 144000, "a7", "a"),
  196. monster(78, 52, 257000, "a8", "a"),
  197. monster(116, 54, 495000, "a9", "a"),
  198. monster(142, 60, 785000, "a10", "a"),
  199.  
  200. monster(30, 6, 1400, "w1", "w"),
  201. monster(24, 12, 3900, "w2", "w"),
  202. monster(18, 24, 8000, "w3", "w"),
  203. monster(36, 20, 18000, "w4", "w"),
  204. monster(78, 18, 52000, "w5", "w"),
  205. monster(44, 44, 84000, "w6", "w"),
  206. monster(92, 32, 159000, "w7", "w"),
  207. monster(108, 36, 241000, "w8", "w"),
  208. monster(80, 70, 418000, "w9", "w"),
  209. monster(110, 70, 675000, "w10", "w"),
  210.  
  211. monster(44, 4, 1300, "e1", "e"),
  212. monster(30, 8, 2700, "e2", "e"),
  213. monster(26, 16, 7500, "e3", "e"),
  214. monster(72, 10, 18000, "e4", "e"),
  215. monster(36, 40, 54000, "e5", "e"),
  216. monster(72, 24, 71000, "e6", "e"),
  217. monster(66, 36, 115000, "e7", "e"),
  218. monster(60, 60, 215000, "e8", "e"),
  219. monster(120, 48, 436000, "e9", "e"),
  220. monster(122, 64, 689000, "e10", "e"),
  221.  
  222. monster(16, 10, 1000, "f1", "f"),
  223. monster(18, 16, 3900, "f2", "f"),
  224. monster(54, 8, 8000, "f3", "f"),
  225. monster(52, 16, 23000, "f4", "f"),
  226. monster(42, 24, 31000, "f5", "f"),
  227. monster(104, 20, 94000, "f6", "f"),
  228. monster(54, 44, 115000, "f7", "f"),
  229. monster(94, 50, 321000, "f8", "f"),
  230. monster(102, 58, 454000, "f9", "f"),
  231. monster(104, 82, 787000, "f10", "f")
  232. };
  233.  
  234.  
  235. map<string, monster>monster_map{
  236. {"a1", monster(20, 8, 1000, "a1", "a")},
  237. {"a2", monster(48, 6, 3900, "a2", "a")},
  238. {"a3", monster(36, 12, 8000, "a3", "a")},
  239. {"a4", monster(24, 26, 15000, "a4", "a")},
  240. {"a5", monster(60, 20, 41000, "a5", "a")},
  241. {"a6", monster(62, 34, 96000, "a6", "a")},
  242. {"a7", monster(106, 26, 144000, "a7", "a")},
  243. {"a8", monster(78, 52, 257000, "a8", "a")},
  244. {"a9", monster(116, 54, 495000, "a9", "a")},
  245. {"a10", monster(142, 60, 785000, "a10", "a")},
  246.  
  247. {"w1", monster(30, 6, 1400, "w1", "w")},
  248. {"w2", monster(24, 12, 3900, "w2", "w")},
  249. {"w3", monster(18, 24, 8000, "w3", "w")},
  250. {"w4", monster(36, 20, 18000, "w4", "w")},
  251. {"w5", monster(78, 18, 52000, "w5", "w")},
  252. {"w6", monster(44, 44, 84000, "w6", "w")},
  253. {"w7", monster(92, 32, 159000, "w7", "w")},
  254. {"w8", monster(108, 36, 241000, "w8", "w")},
  255. {"w9", monster(80, 70, 418000, "w9", "w")},
  256. {"w10", monster(110, 70, 675000, "w10", "w")},
  257.  
  258. {"e1", monster(44, 4, 1300, "e1", "e")},
  259. {"e2", monster(30, 8, 2700, "e2", "e")},
  260. {"e3", monster(26, 16, 7500, "e3", "e")},
  261. {"e4", monster(72, 10, 18000, "e4", "e")},
  262. {"e5", monster(36, 40, 54000, "e5", "e")},
  263. {"e6", monster(72, 24, 71000, "e6", "e")},
  264. {"e7", monster(66, 36, 115000, "e7", "e")},
  265. {"e8", monster(60, 60, 215000, "e8", "e")},
  266. {"e9", monster(120, 48, 436000, "e9", "e")},
  267. {"e10", monster(122, 64, 689000, "e10", "e")},
  268.  
  269. {"f1", monster(16, 10, 1000, "f1", "f")},
  270. {"f2", monster(18, 16, 3900, "f2", "f")},
  271. {"f3", monster(54, 8, 8000, "f3", "f")},
  272. {"f4", monster(52, 16, 23000, "f4", "f")},
  273. {"f5", monster(42, 24, 31000, "f5", "f")},
  274. {"f6", monster(104, 20, 94000, "f6", "f")},
  275. {"f7", monster(54, 44, 115000, "f7", "f")},
  276. {"f8", monster(94, 50, 321000, "f8", "f")},
  277. {"f9", monster(102, 58, 454000, "f9", "f")},
  278. {"f10", monster(104, 82, 787000, "f10", "f")}
  279. };
  280.  
  281. map<string, monster> all_monster_map { // includes heroes
  282. // starts out this way but will be added to later.
  283.  
  284. {"a1", monster(20, 8, 1000, "a1", "a")},
  285. {"a2", monster(48, 6, 3900, "a2", "a")},
  286. {"a3", monster(36, 12, 8000, "a3", "a")},
  287. {"a4", monster(24, 26, 15000, "a4", "a")},
  288. {"a5", monster(60, 20, 41000, "a5", "a")},
  289. {"a6", monster(62, 34, 96000, "a6", "a")},
  290. {"a7", monster(106, 26, 144000, "a7", "a")},
  291. {"a8", monster(78, 52, 257000, "a8", "a")},
  292. {"a9", monster(116, 54, 495000, "a9", "a")},
  293. {"a10", monster(142, 60, 785000, "a10", "a")},
  294.  
  295. {"w1", monster(30, 6, 1400, "w1", "w")},
  296. {"w2", monster(24, 12, 3900, "w2", "w")},
  297. {"w3", monster(18, 24, 8000, "w3", "w")},
  298. {"w4", monster(36, 20, 18000, "w4", "w")},
  299. {"w5", monster(78, 18, 52000, "w5", "w")},
  300. {"w6", monster(44, 44, 84000, "w6", "w")},
  301. {"w7", monster(92, 32, 159000, "w7", "w")},
  302. {"w8", monster(108, 36, 241000, "w8", "w")},
  303. {"w9", monster(80, 70, 418000, "w9", "w")},
  304. {"w10", monster(110, 70, 675000, "w10", "w")},
  305.  
  306. {"e1", monster(44, 4, 1300, "e1", "e")},
  307. {"e2", monster(30, 8, 2700, "e2", "e")},
  308. {"e3", monster(26, 16, 7500, "e3", "e")},
  309. {"e4", monster(72, 10, 18000, "e4", "e")},
  310. {"e5", monster(36, 40, 54000, "e5", "e")},
  311. {"e6", monster(72, 24, 71000, "e6", "e")},
  312. {"e7", monster(66, 36, 115000, "e7", "e")},
  313. {"e8", monster(60, 60, 215000, "e8", "e")},
  314. {"e9", monster(120, 48, 436000, "e9", "e")},
  315. {"e10", monster(122, 64, 689000, "e10", "e")},
  316.  
  317. {"f1", monster(16, 10, 1000, "f1", "f")},
  318. {"f2", monster(18, 16, 3900, "f2", "f")},
  319. {"f3", monster(54, 8, 8000, "f3", "f")},
  320. {"f4", monster(52, 16, 23000, "f4", "f")},
  321. {"f5", monster(42, 24, 31000, "f5", "f")},
  322. {"f6", monster(104, 20, 94000, "f6", "f")},
  323. {"f7", monster(54, 44, 115000, "f7", "f")},
  324. {"f8", monster(94, 50, 321000, "f8", "f")},
  325. {"f9", monster(102, 58, 454000, "f9", "f")},
  326. {"f10", monster(104, 82, 787000, "f10", "f")}
  327. };
  328. map<string, monster> base_heroes{ // unleveled heroes
  329. {"lady of twilight", monster(45, 20, 0, "lady of twilight", "a", {"def", "all" , "a" , 1})},
  330. {"tiny", monster(70, 30, 0, "tiny", "e", {"aoe", "all" , "e" , 2})},
  331. {"nebra", monster(90, 40, 0, "nebra", "f", {"dmg", "all" , "f" , 4})},
  332. {"noname a", monster(20, 10, 0, "noname a", "a", {"def", "a" , "a" , 1})},
  333. {"noname e", monster(30, 8, 0, "noname e", "e", {"def", "e" , "e" , 1})},
  334. {"noname f", monster(24, 12, 0, "noname f", "f", {"def", "f" , "f" , 1})},
  335. {"noname w", monster(50, 6, 0, "noname w", "w", {"def", "w" , "w" , 1})},
  336. {"hunter", monster(22, 14, 0, "hunter", "a", {"dmg", "a" , "a" , 2})},
  337. {"shaman", monster(40, 20, 0, "shaman", "e", {"def", "e" , "e" , 2})},
  338. {"alpha", monster(82, 22, 0, "alpha", "f", {"aoe", "all" , "f" , 1})},
  339. {"carl", monster(28, 12, 0, "carl", "w", {"dmg", "w" , "w" , 2})},
  340. {"nimue", monster(38, 22, 0, "nimue", "a", {"def", "a" , "a" , 2})},
  341. {"athos", monster(70, 26, 0, "athos", "e", {"def", "all" , "e" , 2})},
  342. {"jet", monster(24, 16, 0, "jet", "f", {"dmg", "f" , "f" , 2})},
  343. {"geron", monster(36, 24, 0, "geron", "w", {"def", "w" , "w" , 2})},
  344. {"rei", monster(46, 40, 0, "rei", "a", {"dmg", "all" , "a" , 2})},
  345. {"ailen", monster(19, 22, 0, "ailen", "e", {"dmg", "e" , "e" , 2})},
  346. {"faefyr", monster(50, 18, 0, "faefyr", "f", {"def", "f" , "f" , 2})},
  347. {"auri", monster(60, 32, 0, "auri", "w", {"heal", "all" , "w" , 2})}
  348.  
  349. };
  350. map<string, int> rarities { // hero rarities
  351. {"lady of twilight", 0},
  352. {"tiny", 1},
  353. {"nebra", 2},
  354. {"noname a", 0},
  355. {"noname e", 0},
  356. {"noname f", 1},
  357. {"noname w", 1},
  358. {"hunter", 0},
  359. {"shaman", 1},
  360. {"alpha", 2},
  361. {"carl", 0},
  362. {"nimue", 1},
  363. {"athos", 2},
  364. {"jet", 0},
  365. {"geron", 1},
  366. {"rei", 2},
  367. {"ailen", 0},
  368. {"faefyr", 1},
  369. {"auri", 2}
  370. };
  371. map<string, string> countered_by{
  372. {"a1", "e1"},
  373. {"a2", "e2"},
  374. {"a3", "e3"},
  375. {"a4", "e4"},
  376. {"a5", "e5"},
  377. {"a6", "e6"},
  378. {"a7", "e7"},
  379. {"a8", "e8"},
  380. {"a9", "e9"},
  381. {"a10", "e10"},
  382.  
  383. {"w1", "a1"},
  384. {"w2", "a2"},
  385. {"w3", "a3"},
  386. {"w4", "a4"},
  387. {"w5", "a5"},
  388. {"w6", "a6"},
  389. {"w7", "a7"},
  390. {"w8", "a8"},
  391. {"w9", "a9"},
  392. {"w10", "a10"},
  393.  
  394. {"e1", "f1"},
  395. {"e2", "f2"},
  396. {"e3", "f3"},
  397. {"e4", "f4"},
  398. {"e5", "f5"},
  399. {"e6", "f6"},
  400. {"e7", "f7"},
  401. {"e8", "f8"},
  402. {"e9", "f9"},
  403. {"e10", "f10"},
  404.  
  405. {"f1", "w1"},
  406. {"f2", "w2"},
  407. {"f3", "w3"},
  408. {"f4", "w4"},
  409. {"f5", "w5"},
  410. {"f6", "w6"},
  411. {"f7", "w7"},
  412. {"f8", "w8"},
  413. {"f9", "w9"},
  414. {"f10", "w10"}
  415. };
  416. // initialize
  417. int cost(const army & army_1);
  418.  
  419. int enhance_damage(int damage_c, string source_element, string target_element){
  420. int damage = damage_c;
  421. if (source_element == "e" && target_element == "a") {
  422. damage = damage * 1.5;
  423. }
  424. if (source_element == "a" && target_element == "w") {
  425. damage = damage * 1.5;
  426. }
  427. if (source_element == "w" && target_element == "f") {
  428. damage = damage * 1.5;
  429. }
  430. if (source_element == "f" && target_element == "e") {
  431. damage = damage * 1.5;
  432. }
  433. return damage;
  434. }
  435. 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) {
  436. // left attacks right
  437. // damage the front took, cumulative aoe damage
  438. // index_l and index_r are the number of monsters lost on the left and right, respectively
  439. int damage = enhance_damage(left.damage, left.element, right.element);
  440. int aoe_damage = 0;
  441. int healing = 0;
  442. //hero stuff
  443. hero_skill left_skill;
  444. hero_skill right_skill;
  445. for(int i=index_r;i<right_skills.size();i++){
  446. right_skill = *right_skills.at(i);
  447. if (right_skill.type == "def" && (right_skill.target == "all" || right_skill.target == right.element)) {
  448. damage -= right_skill.amount;
  449. }
  450. if (right_skill.type == "heal" && (right_skill.target == "all" || right_skill.target == right.element)) {
  451. healing += right_skill.amount;
  452. }
  453. }
  454. for(int i=index_l;i<left_skills.size();i++){
  455. left_skill = *left_skills.at(i);
  456. if (left_skill.type == "aoe" && (left_skill.target == "all" || left_skill.target == right.element)) {
  457. aoe_damage += left_skill.amount;
  458. }
  459. if (left_skill.type == "dmg" && (left_skill.target == "all" || left_skill.target == left.element)) {
  460. damage += enhance_damage(left_skill.amount, left.element, right.element);
  461. }
  462. }
  463.  
  464. damage = max(0, damage);
  465.  
  466. return {damage, healing, aoe_damage};
  467.  
  468. }
  469.  
  470. fight_result simulate_fight(const army & left, const army & right, bool verbose = false) {
  471. //fights left to right, so left[0] and right[0] are the first to fight
  472. fights_simulated++;
  473. int left_lost = 0;
  474. int left_damage_taken = 0;
  475. int right_lost = 0;
  476. int right_damage_taken = 0;
  477. int left_cumulative_aoe_damage =0;
  478. int right_cumulative_aoe_damage = 0; //all this is damage taken
  479. // a suffix for this fight was already pre-computed
  480. if(left.pf.valid && verbose == false){
  481. // can use pre-computed values
  482. left_lost = left.monsters.size()-1;
  483. left_damage_taken = left.pf.left_aoe_damage;
  484. right_lost = left.pf.lost;
  485. right_damage_taken = left.pf.damage;
  486. right_cumulative_aoe_damage = left.pf.right_aoe_damage;
  487. }
  488. while (left_lost < left.monsters.size() && right_lost < right.monsters.size()) {
  489. //attack once - first get parameters
  490. monster left_monster = *left.monsters.at(left_lost);
  491. monster right_monster = *right.monsters.at(right_lost);
  492. //get hero skill
  493. vector<int> left_attack = one_turn(left_monster, left.skills, left_lost, right_monster, right.skills, right_lost);
  494. vector<int> right_attack = one_turn(right_monster, right.skills, right_lost, left_monster, left.skills, left_lost);
  495. right_damage_taken += left_attack.at(0) + left_attack.at(2);
  496. left_damage_taken += right_attack.at(0) + right_attack.at(2);
  497. right_cumulative_aoe_damage += left_attack.at(2);
  498. left_cumulative_aoe_damage += right_attack.at(2);
  499. //check for deaths
  500. while(left_lost < left.monsters.size() && left_damage_taken >= left.monsters.at(left_lost)->hp) {
  501. left_damage_taken = left_cumulative_aoe_damage ;
  502. left_lost++;
  503. }
  504. while(right_lost < right.monsters.size() && right_damage_taken >= right.monsters.at(right_lost)->hp) {
  505. right_damage_taken = right_cumulative_aoe_damage;
  506. right_lost++;
  507. }
  508. // healing - does not take effect on death
  509. left_damage_taken = max(0, left_damage_taken - right_attack.at(1));
  510. right_damage_taken = max(0, right_damage_taken - left_attack.at(1));
  511. if (verbose == true) {
  512. cout << left_lost << " " << left_damage_taken << " " << right_lost << " " << right_damage_taken << "\n";
  513. }
  514. }
  515. //draws count as right wins.
  516. if(verbose == true && left_lost == left.monsters.size() && right_lost == right.monsters.size()){
  517. cout << "Draw\n";
  518. }
  519. if (left_lost == left.monsters.size()) {
  520. return fight_result(true, right_lost, right_damage_taken, cost(left), false,left_cumulative_aoe_damage, right_cumulative_aoe_damage);
  521. }
  522. //left wins if the code gets here.
  523. return fight_result(false, left_lost, left_damage_taken, cost(left), false, left_cumulative_aoe_damage, right_cumulative_aoe_damage);
  524. }
  525. vector<fight_result> simulate_multiple_fights(vector<army> & list, army & target, bool change_optimal = true){//
  526. //simulates all of the fights from list and puts it into a vector of fight_results.
  527. vector<fight_result> output;
  528. output.reserve(list.size());
  529. for (int i = 0; i < list.size(); i++) {
  530. fight_result this_result = simulate_fight(list.at(i), target);
  531. this_result.source = &list.at(i);
  532. if (this_result.winner == false && cost(list.at(i)) < my_upper_bound && change_optimal) { // left (our side) wins:
  533. my_upper_bound = this_result.followers;
  534. vector<string> best_names {};
  535. for(int j=0;j<list.at(i).monsters.size();j++){
  536. best_names.push_back(list.at(i).monsters.at(j)->name );
  537. }
  538. best = army(vector<monster *> {});
  539. for(int j=0;j<best_names.size();j++){
  540. best.add(&all_monster_map.at(best_names.at(j)));
  541. }
  542. //fix the pointers in best - the heroes_available in solve_instance is not global scope.
  543.  
  544. }
  545. output.push_back(this_result); //still need this for consistency
  546. }
  547. return output;
  548. }
  549. void expand(vector<army> * source, vector<fight_result> &current_armies, vector<monster> & to_expand_with, int my_upper_bound, bool check_heroes_repeat){
  550. // expand stuff directly onto source, does not expand dominated or winning or too costly armies
  551. // if the bool is true, we check if we repeat any heroes
  552. for(int i=0;i<current_armies.size();i++){
  553. fight_result * this_result = &current_armies.at(i);
  554. if(this_result->dominated == true || this_result->winner == false){
  555. continue;
  556. }
  557. for(int j=0; j < to_expand_with.size();j++){
  558. if(this_result->followers + to_expand_with.at(j).cost >= my_upper_bound){
  559. continue;
  560. }
  561. bool can_use = true;
  562. if(check_heroes_repeat){
  563. string current_name = to_expand_with.at(j).name;
  564. for(int k=0; k < this_result->source->heroes_used.size();k++){
  565. if(this_result->source->heroes_used.at(k) == current_name ){
  566. can_use = false;
  567. break;
  568. }
  569. }
  570. }
  571. if(can_use == false){
  572. continue;
  573. }
  574. source->push_back(*(this_result->source));
  575. source->at(source->size() - 1).add(&to_expand_with.at(j));
  576. if(to_expand_with.at(j).skill.type == "nothing")
  577. {
  578. 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
  579. } else{
  580. source->at(source->size() - 1).pf.valid = false;
  581. }
  582. }
  583. }
  584. }
  585.  
  586. int cost(const army & m) {
  587. int result = 0;
  588. for (int i = 0; i < m.monsters.size(); i++) {
  589. result = result + m.monsters.at(i)->cost;
  590. }
  591. return result;
  592. }
  593.  
  594. bool function_compare(fight_result & a, fight_result & b) { // used for sorting.
  595. return (a.followers < b.followers);
  596. }
  597.  
  598. monster level_up_hero(const monster & m, int rarity, int level){
  599. int points = level-1;
  600. if(rarity == 1){
  601. points = 2 * points;
  602. }
  603. if(rarity == 2){
  604. points = 6* points;
  605. }
  606. int value = m.hp + m.damage;
  607. return monster(floor(m.hp + points * ((double)m.hp) / value),
  608. m.damage + floor(points * ((double)m.damage) / value),
  609. m.cost,
  610. m.name,
  611. m.element,
  612. m.skill
  613. );
  614. }
  615. string add_hero_string(string s){
  616. //turns a string representing a hero into its actual hero
  617. //adds it into all_monsters_map
  618. //for example, "lady of twilight:1" adds a level 1 lady of twilight into the all_monsters_map
  619. //returns the name of the hero as stored in the hash table
  620. string t = s.substr(0, s.find(':'));
  621. int level = stoi(s.substr(s.find(':')+1));
  622. monster m = level_up_hero(base_heroes.at(t), rarities.at(t), level);
  623. string name = t + ":" + to_string(level);
  624. m.name = name;
  625. all_monster_map.insert({name, m});
  626. return m.name;
  627. }
  628. solution solve_instance(vector<monster> heroes_available, army target, int limit, bool time_it) {
  629. army trial({});
  630.  
  631. //try to get a good upper bound by looking at counters
  632. for (int i = 0; i < target.monsters.size() && i < limit; i++) {
  633. if(countered_by.count(target.monsters.at(i)->name) != 0){ // if it is not a hero
  634. trial.add(&monster_map.at(countered_by.at(target.monsters.at(i)->name)));
  635. }
  636. }
  637. fight_result this_result = simulate_fight(trial, target);
  638. if (this_result.winner == false) {
  639. my_upper_bound = cost(trial);
  640. best = trial;
  641. }
  642. //check if optimizable - if no single monster can defeat the last two monsters, then we can optimize
  643. bool optimizable = (target.monsters.size() >= 3);
  644. if (target.monsters.size() >= 3) {
  645. // get the last two
  646. army last2 = army({target.monsters.at(target.monsters.size() - 2), target.monsters.at(target.monsters.size() - 1)});
  647. for (int i = 0; i < monster_list.size(); i++) {
  648. if (monster_list.at(i).cost > my_upper_bound) {
  649. continue;
  650. }
  651. army fighting({ &all_monster_map.at(monster_list.at(i).name)});
  652. fight_result s = simulate_fight(fighting, last2);
  653. if (s.winner == false) {
  654. //single monster can defeat last 2 -> cannot optimize
  655. optimizable = false;
  656. break;
  657. }
  658. }
  659. for (int i = 0; i < heroes_available.size(); i++) {
  660. army fighting({&all_monster_map.at(heroes_available.at(i).name)});
  661. fight_result s = simulate_fight(fighting, last2);
  662. if (s.winner == false) {
  663. //single monster can defeat last 2 -> cannot optimize
  664. optimizable = false;
  665. break;
  666. }
  667.  
  668. }
  669. }
  670.  
  671. vector<army >optimal = {}; // initialize with all single monsters
  672. vector<army >optimal_heroes = {}; // initialize with all heroes
  673. for (int i = 0; i < monster_list.size(); i++) {
  674. optimal.emplace_back(vector<monster *>{&all_monster_map.at(monster_list.at(i).name)});
  675. }
  676.  
  677. for (int i = 0; i < heroes_available.size(); i++) {
  678. optimal_heroes.emplace_back(vector<monster *>{&all_monster_map.at(heroes_available.at(i).name)});// emplace back!
  679. }
  680. //best so far
  681. for (int c = 1; c <= limit; c++) { // c is the length of the list of monsters
  682. if (time_it == true) {
  683. cout << "TIME : starting loop " << optimal.size() << " " << optimal_heroes.size() << " " << time(NULL) << "\n";
  684. }
  685. // for each optimal result (that is, not known to be dominated), fight against the target and record values
  686. vector<fight_result> result = simulate_multiple_fights(optimal, target, true);
  687. if (time_it == true) {
  688. cout << "TIME : finished fighting for non-heroes " << optimal.size() << " " << optimal_heroes.size() << " " << time(NULL) << "\n";
  689. }
  690. vector<fight_result> result_heroes = simulate_multiple_fights(optimal_heroes, target, true);
  691.  
  692. if (time_it == true) {
  693. cout << "TIME : finished fight, starting sort " << time(NULL) << "\n";
  694. }
  695. if (c != limit) { // do not do the last expansion
  696. //sort so we can stop early
  697. sort(result.begin(), result.end(), function_compare);
  698. sort(result_heroes.begin(), result_heroes.end(), function_compare);
  699. // do not use optimal.at(i) anymore, replace with (*(result.at(i).source))
  700.  
  701. if (time_it == true) {
  702. cout << "TIME : finished sort, starting check dominance " << time(NULL) << "\n";
  703. }
  704. for (int i = 0; i < optimal.size(); i++) { // non-heroes
  705. // it is also dominated if c+1 = limit (one monster left) and the last 2 monsters are still alive
  706. if (c + 1 == limit && optimizable == true) {
  707. if (result.at(i).winner == true && result.at(i).lost < target.monsters.size() - 2 && result.at(i).right_aoe_damage == 0){
  708. /*
  709. cout << "OPTIMIZED OUT"; //debug
  710. for (monster m : *(result.at(i).source)){
  711. cout << m.name << " ";
  712. } // end debug
  713. */
  714. result.at(i).dominated = true;
  715. }
  716. }
  717. if (result.at(i).dominated == false) {
  718. for (int j = i + 1; j < optimal.size(); j++) {
  719. // if i costs more followers and got less far than j, then i is dominated
  720. // set optimal[i][0]'s name to dominated
  721. if (result.at(i).followers >= result.at(j).followers && result.at(i) <= result.at(j)) {
  722. result.at(i).dominated = true;
  723. break;
  724. }
  725. if (result.at(i).followers < result.at(j).followers) {
  726. break; // since the list is sorted
  727. }
  728. }
  729. for(int j=0; j<optimal_heroes.size();j++){// non-heroes dominate heroes
  730. if (result.at(i).followers <= result_heroes.at(j).followers && result.at(i) >= result_heroes.at(j) ) {
  731. result_heroes.at(j).dominated = true;
  732. }
  733. if (result.at(i).followers > result_heroes.at(j).followers) {
  734. break; // since the list is sorted
  735. }
  736. }
  737. }
  738. }
  739.  
  740.  
  741. //domination for heroes:
  742. for (int i = 0; i < optimal_heroes.size(); i++) {
  743. // it is also dominated if c+1 = limit (one monster left) and the last 2 monsters
  744. // are still alive, but we also require no AOE damage dealt
  745. if (c + 1 == limit && optimizable == true && result_heroes.at(i).right_aoe_damage == 0) {
  746. if (result_heroes.at(i).winner == true && result_heroes.at(i).lost < target.monsters.size() - 2){
  747. result_heroes.at(i).dominated = true;
  748. }
  749. }
  750. if (result_heroes.at(i).dominated != true ){
  751. for (int j = i + 1; j < optimal_heroes.size(); j++) {
  752. // if i costs more followers and got less far than j, then i is dominated
  753. // set optimal[i][0]'s name to dominated
  754.  
  755. if (result_heroes.at(i).followers >= result_heroes.at(j).followers && result_heroes.at(i) <= result_heroes.at(j)) {
  756. bool used = false;// i did not use a hero that j used, so j cannot dominate i
  757. for(int sj = 0; sj < result_heroes.at(j).source->heroes_used.size();sj++){
  758. string j_hero = result_heroes.at(j).source->heroes_used.at(sj);
  759. bool i_used_hero = false;
  760. for(int si = 0; si < result_heroes.at(i).source->heroes_used.size();si++){
  761. string i_hero = result_heroes.at(i).source->heroes_used.at(si);
  762. if(i_hero == j_hero){
  763. i_used_hero = true;
  764. break;
  765. }
  766. }
  767. if(i_used_hero == false){
  768. used = true;
  769. break;
  770. }
  771. }
  772. if(used == false){
  773. result_heroes.at(i).dominated = true;
  774. break;
  775. }
  776. }
  777. if (result_heroes.at(i).followers < result_heroes.at(j).followers) {
  778. break; // since the list is sorted
  779.  
  780. }
  781. }
  782. }
  783. }
  784. //
  785. // now we expand to add the next monster to all non-dominated armies
  786. if (time_it == true) {
  787. cout << "TIME : finished check dominance, starting expanding " << time(NULL) << "\n";
  788. }
  789. vector<army > next_optimal;
  790. expand(&next_optimal, result, monster_list, my_upper_bound, false);
  791. vector<army > next_optimal_heroes;
  792. expand(&next_optimal_heroes, result_heroes, monster_list, my_upper_bound, false);
  793. expand(&next_optimal_heroes, result, heroes_available, my_upper_bound, false);
  794. expand(&next_optimal_heroes, result_heroes, heroes_available, my_upper_bound, true);
  795.  
  796. if (time_it == true) {
  797. cout << "TIME : finished expanding (move)" << time(NULL) << "\n";
  798. }
  799. optimal = move(next_optimal);
  800. optimal_heroes = move(next_optimal_heroes);
  801. }
  802. }
  803. return {best, my_upper_bound};
  804. }
  805. void test_cases(){
  806.  
  807. // test cases for dominance of fight_results
  808. add_hero_string("rei:3");
  809. add_hero_string("hunter:2");
  810. add_hero_string("rei:1");
  811. add_hero_string("tiny:1");
  812. solution solv = solve_instance({all_monster_map.at("tiny:1"),all_monster_map.at("rei:1"),},
  813. army(vector<monster*>{
  814. &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")
  815. }), 6, true);
  816. // don't know the true value, so I can't tell. only doing this to see if there are exceptions.
  817. add_hero_string("lady of twilight:1");
  818. add_hero_string("jet:1");
  819. for(int i=0; i<solv.optimal.monsters.size();i++){
  820. cout << (solv.optimal.monsters.at(i) -> name) << " ";
  821. }
  822. cout << "\n";
  823. /*
  824.  
  825. 0 16 0 8
  826. 0 32 0 16
  827. 0 48 1 0
  828. 1 0 1 8
  829. 1 12 2 0
  830. 1 24 2 6
  831. 2 0 2 12
  832. 2 12 2 18
  833. 2 24 3 0
  834. 3 0 3 9
  835. 3 27 3 13
  836. 4 0 3 17
  837. 4 16 4 0
  838. 4 22 4 12
  839. 5 0 4 24
  840. */
  841. simulate_fight(army(vector<monster*>{
  842. &all_monster_map.at("f3"),
  843. &all_monster_map.at("w1"),
  844. &all_monster_map.at("w1"),
  845. &all_monster_map.at("e1"),
  846. &all_monster_map.at("w2")
  847. }),
  848.  
  849. army(vector<monster*>{
  850. &all_monster_map.at("hunter:2"),
  851. &all_monster_map.at("f1"),
  852. &all_monster_map.at("a1"),
  853. &all_monster_map.at("jet:1"),
  854. &all_monster_map.at("w1"),
  855. &all_monster_map.at("e2")
  856.  
  857. }), true);
  858. //
  859. cout << "YAY?\n";
  860. /*
  861. 0 42 0 6
  862. 1 0 0 12
  863. 2 0 0 24
  864. 3 0 0 36
  865. 4 0 0 44
  866. 5 0 1 0
  867. 5 9 1 16
  868. 6 0 2 0
  869. */
  870. simulate_fight(army(vector<monster*>{
  871. &all_monster_map.at("e1"),
  872. &all_monster_map.at("e2"),
  873. &all_monster_map.at("w2"),
  874. &all_monster_map.at("a1"),
  875. &all_monster_map.at("w2"),
  876. &all_monster_map.at("f2")
  877. }),
  878.  
  879. army(vector<monster*>{
  880. &all_monster_map.at("rei:1"),
  881. &all_monster_map.at("w1"),
  882. &all_monster_map.at("e1"),
  883. &all_monster_map.at("f1"),
  884. &all_monster_map.at("a1"),
  885. &all_monster_map.at("e1")
  886.  
  887. }), true);
  888. cout << "YAY!";
  889. /*
  890. 0 66 0 26
  891. 1 0 0 52
  892. 1 44 1 0
  893. 1 98 1 28
  894. 2 0 1 56
  895. 2 36 2 0
  896. 2 87 2 34
  897. 3 0 3 0
  898. 4 0 4 0
  899. 4 66 4 26
  900. 5 0 4 52
  901. 5 44 5 0
  902. 6 0 6 0
  903. Draw
  904.  
  905. */
  906. simulate_fight(army(vector<monster*>{
  907. &all_monster_map.at("e6"),
  908. &all_monster_map.at("a7"),
  909. &all_monster_map.at("w7"),
  910. &all_monster_map.at("f7"),
  911. &all_monster_map.at("e6"),
  912. &all_monster_map.at("rei:1")
  913. }),
  914.  
  915. army(vector<monster*>{
  916. &all_monster_map.at("f7"),
  917. &all_monster_map.at("e7"),
  918. &all_monster_map.at("a6"),
  919. &all_monster_map.at("w6"),
  920. &all_monster_map.at("f7"),
  921. &all_monster_map.at("w6")
  922.  
  923. }), true);
  924. cout << "YAY!\n";
  925.  
  926. // 63 damage, 9 damage
  927. 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);
  928. 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);
  929. cout << damage_dealt << " "<< damage_dealt_2<<"\n";
  930. add_hero_string("faefyr:3");
  931.  
  932. }
  933. int main(int argc, char** argv) {
  934. //test_cases();
  935. cout << sizeof(army) << " " << sizeof(fight_result )<< " " << sizeof(hero_skill) << "\n";
  936. bool time_it = (argc == 3); // if set to true, it will show how much time each step takes
  937. vector<monster *> target; //somehow get stuff here
  938. vector<monster *> target2;
  939. vector<string> target_s;
  940. string target_string = "";
  941.  
  942. if (argc == 2) { // custom input mode
  943. while (true) {
  944. target.clear();
  945. target2.clear();
  946. cout << "enter the sequence 1 left to right. Enter done to stop ";
  947. getline(cin, target_string);
  948. if (target_string == "done") {
  949. break;
  950. }
  951. target_s = split(target_string, ",");
  952. //get the heroes and add them
  953. for(int i=0; i<target_s.size();i++){
  954. if(target_s.at(i).find(":") != target_s.at(i).npos){
  955. add_hero_string(target_s.at(i));
  956. }
  957. }
  958. for(int i=0; i<target_s.size();i++){
  959. target.push_back(&all_monster_map.at(target_s.at(i)));
  960. }
  961. cout << "enter the sequence 2 left to right ";
  962. getline(cin, target_string);
  963. target_s = split(target_string, ",");
  964. //get the heroes and add them
  965. for(int i=0; i<target_s.size();i++){
  966. if(target_s.at(i).find(":") != target_s.at(i).npos){
  967. add_hero_string(target_s.at(i));
  968. }
  969. }
  970. for(int i=0; i<target_s.size();i++){
  971. target2.push_back(&all_monster_map.at(target_s.at(i)));
  972. }
  973. fight_result custom_result = simulate_fight(army(target), army(target2), true);
  974. cout << custom_result.winner << " " << cost(army(target)) << " " << cost(army(target2)) << "\n";
  975. }
  976. return 0;
  977. }
  978.  
  979. cout << "enter the enemy sequence left to right ";
  980. getline(cin, target_string);
  981. target_s = split(target_string, ",");
  982. //get the heroes and add them
  983. for(int i=0; i<target_s.size();i++){
  984. if(target_s.at(i).find(":") != target_s.at(i).npos){
  985. add_hero_string(target_s.at(i));
  986. }
  987. }
  988. for(int i=0; i<target_s.size();i++){
  989. target.push_back(&all_monster_map.at(target_s.at(i)));
  990. }
  991. int limit = 0; // somehow get stuff here.
  992. cout << "enter the maximum number of monsters";
  993. getline(cin, target_string);
  994. limit = stoi(target_string);
  995.  
  996. vector<monster> available_heroes {};
  997. 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"};
  998. string level_c = "";
  999.  
  1000. for(int i=0;i<all_heroes.size();i++){
  1001. cout<< "enter the level of " << all_heroes.at(i) << " or nothing if you don't have it";
  1002. getline(cin, level_c);
  1003. if(level_c == ""){
  1004. level_c = "0";
  1005. }
  1006. if(stoi(level_c) != 0){
  1007. available_heroes.push_back( all_monster_map.at(add_hero_string(all_heroes.at(i) + ":" + to_string(stoi(level_c)) )));
  1008. }
  1009. }
  1010. solution solu = solve_instance(available_heroes, army(target), limit, time_it);
  1011. //last check to see if winning combination wins:
  1012. army best = solu.optimal;
  1013. int my_upper_bound = solu.followers;
  1014. if (my_upper_bound != 2147483647) {
  1015. best.pf.valid = false;
  1016. fight_result final_result = simulate_fight(best, target);
  1017. if (final_result.winner == true) {
  1018. for (int i = 1; i <= 100; i++) {
  1019. cout << "ERROR";
  1020. }
  1021. throw 32;
  1022. }
  1023. }
  1024. // print out the winning combination!
  1025. cout << "The minimum number of followers is : " << my_upper_bound;
  1026. cout << "\nand the winning combination is:\n";
  1027. for (int i = 0; i < best.monsters.size(); i++) {
  1028. cout << best.monsters.at(best.monsters.size() - 1 - i)->name << " "; // backwards
  1029. }
  1030. cout << "\n" << "(right-most fights first)\n" << fights_simulated << " fights simulated\n";
  1031. return 0;
  1032. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!