Purpose:
Your goal for this assignment is to write part of an AI for a hypothetical
video game called EU4. This assignment is not to make a game itself, which is
outside the scope of this class, but to control an AI (computer) player in a game.
In the video game, your country will be surrounded by provinces that you can
add to your empire through either military or diplomatic means.
To this end, your country will have two resources that you will have to track:
1) Soldiers
2) Diplomacy Points
These are both ints, and will be held in main.
Part I – LL Node class
The AI will use these resources to conquer nearby provinces. Nearby provinces
have two things you need to keep track of:
1) A name (a string)
2) A cost (an int representing how expensive it will be to take)
You will need to make a linked list node class (called LL, in the file ll.h)
that has these two variables in their private section, as well as
pointers to the previous and next members of the list they will be in. You
must make a fully ADTed class, with constructors, get/set methods, etc.
You’ll have to replace the placeholder code in the class definition to make it
work.
When your node class is done, run the program and select option 1 (“Test
your Linked List Node class”). It will test your class. If you did something
wrong, it will tell you what you did wrong (hopefully accurately). If you pass
all tests, then you are ready for Part II.
Part II – List Class
These nodes will be held in two lists:
1) One list for provinces that can be taken by soldiers
2) One list for provinces that can be annexed diplomatically
These lists are both empty by default. The user will add provinces to these
list.
You will write a List class (also in ll.h) that will maintain pointers to the
head and the tail of the list, as well as the size (number of provinces in the
list). Fully ADT your list class, with get/set methods, constructors, etc.
You will also implement functions that will do the following:
1) Insert at the beginning (head) of the list
2) Insert at the end (tail) of the list
These functions both return a string “X inserted” where X is the name of the province.
Example:
If the user inserts at the end a province called “Moscow” with a cost of 30, these
functions will return a string containing “Moscow inserted”. If the user
then inserts at the head “Paris” with a cost of 20, then “Kuala Lumpur” with a
cost of 10 at the end, and then “New York” with a cost of 10 at the end, your
list will look like:
Paris, Cost 20
Moscow, Cost 30
Kuala Lumpur, Cost 10
New York, Cost 10
3) Delete. Delete will take a cost value, and it will delete the first
province that has that cost or less, and then return (into the second parameter
that is call by reference) the change left over. You will delete the first (starting
at the head, heading towards the tail) province that matches, not all of them.
You will return a string containing “X deleted” where X is the name of the
province.
Example – your list contains:
Paris, Cost 20
Moscow, Cost 30
Kuala Lumpur, Cost 10
New York, Cost 10
If you are told to delete with a budget of 15, it will skip Paris and Moscow,
because their cost is too high, and then delete Kuala Lumpur, and return a string
saying “Kuala Lumpur deleted” and amount_out will be set to 5. The list will
now look like:
Paris, Cost 20
Moscow, Cost 30
New York, Cost 10
When your class is ready to test, run the program and select option 2.
Assuming you pass all tests, you are ready for Part III.
Part III – Main
Most of this is done for you already. All the i/o, updating the soldier and
diplomacy power stuff, etc. You will merely need to write the code that will
put data into the two linked lists. When the user chooses to insert a “high
priority” province that means to put it at the head of the list (since the
head gets processed first). Inserting a regular province adds at the end, so
if you do all provinces this way they will be held in the order they were
inserted.
You will need to write code to:
1) Make a function call to insert at the front of the invasion list
2) Make a function call to insert at the end of the invasion list
3) Make a function call to insert at the front of the annex list
4) Make a function call to insert at the end of the annex list
5) Make a function call to delete from the invasion list, passing in the
current number of soldiers you have, and then using the write parameter passed
back to update your soldiers count. This will delete one province, max.
6) Make a function call to delete from the annex list, but ANNEXATION WORKS DIFFERENTLY.
You will continue to annex provinces until there are no provinces left to
annex with your current budget. This is the only bit of Part III that might
even be a little tricky. The rest are simple.
Extra credit:
If the same province is available for conquest via both means (i.e. the same
name appears on both lists, after taking it one way remove it off the other
list for no cost).
#include <iostream>
#include <iomanip>
#include <sstream>
using namespace std; //Note: This is a bad idea in header files!
void die(string s = “”) {
if (s == “”)
cout << “BAD INPUT!” << endl;
else
cout << s << endl;
exit(1);
}
class LL { //A single node in a linked list
int cost = 0; //There is a class invariant stating cost can never be negative. Enforce this rule below.
string province;
LL *prev = nullptr;
LL *next = nullptr;
public:
//This is a default constructor, 1 parameter constructor, 2 param, 3 param, and 4 param in one!
LL(int new_cost = 0, string s = “”, LL *new_prev = nullptr, LL *new_next = nullptr) {
//YOU
}
int get_cost() const {
//YOU
}
void set_cost(int new_cost) {
//YOU
}
string get_province() const {
//YOU
}
void set_province(string s) {
//YOU
}
LL *get_next() const {
//YOU
}
void set_next(LL *new_next) {
//YOU
}
LL *get_prev() const {
//YOU
}
void set_prev(LL *new_prev) {
//YOU
}
};
//DON’T MODIFY THIS FUNCTION. IT WILL TEST YOUR LL CLASS TO MAKE SURE IT’S COOLIO
void LL_test() {
LL a;
if (a.get_cost() || a.get_province() != “” || a.get_next() || a.get_prev()) die(“Your default constructor or your get functions don’t work. Please fix.”);
LL b(42,”Constantinople”);
if (b.get_cost() != 42 || b.get_province() != “Constantinople” || b.get_next() || b.get_prev()) die(“Your one parameter constructor sucks. Please fix it pronto.”);
LL *c = new LL(-10,”Istanbul”);
if (c->get_cost() != 0) die(“You allowed a negative cost to be set in a constructor. Your code should set a negative cost to 0.”);
if (c->get_province() != “Istanbul”) die(“The province name was set to Istanbul, but get_province did not return it.”);
LL *d = new LL(20,”Prague”,c);
if (d->get_cost() != 20 || d->get_province() != “Prague” || d->get_prev() != c) die(“Your three parameter constructor doesn’t work.”);
LL *e = new LL(30,”Ulm”,c,d); //BTW, don’t make linked lists like this
if (e->get_cost() != 30 || e->get_province() != “Ulm” || e->get_prev() != c || e->get_next() != d) die(“Your four parameter constructor doesn’t work.”);
delete (c); //Every new must be paired with one delete
delete (d);
delete (e);
}
class List {
LL *head = nullptr;
LL *tail = nullptr;
int size = 0;
public:
List() {} //Set above
~List() { //This should free all memory allocated in this list
//YOU: one delete for every new
}
int get_size() const {
//YOU
}
//No set_size function needed. Why? Because it will only be set through insert/delete
//No get/set methods for head and tail. Why? Because main doesn’t need to know anything about them. Main will just call insert and delete
//Print list forwards or backwards
string print_list(bool forwards = true) {
LL *temp = forwards ? head : tail;
ostringstream ss; //This lets us write to a string like we do to cout
if (!temp) {
ss << “Empty Listn”;
return ss.str();
}
while (temp) {
ss << “Province: ” << left << setw(12) << temp->get_province() << ” Cost: ” << temp->get_cost() << endl;
temp = forwards ? temp->get_next() : temp->get_prev();
}
return ss.str();
}
string insert_at_beginning(int cost, string province) {
string retval = province + ” inserted”;
//YOU: Write code to make a new node and insert at the head
//Make sure size gets updated when you add to the list
return retval;
}
string insert_at_end(int cost, string province) {
string retval = province + ” inserted”;
//YOU
return retval;
}
//This function will delete a single node from the LL with a cost <= amount
//amount_out will hold how much change was left over after the delete was done
//It will return sentence containing “X deletedn” (if node X was deleted) or “Nothing deleted”
string delete_amount(int amount,int &amount_out) {
string s; //You must set this to the province name that is deleted
//YOU: First, handle the list being empty
return “Nothing deleted”;
//YOU: Second, handle there being one element in the list
//YOU: Third, handle deleting from the head or tail (actually the tail should be after the middle)
//YOU: Handle deleting from the middle of the list
return s + ” deleted”;
//Helpful hints – keep track of all of your invariants:
//1. Size should always be updated when you insert or delete
//2. All pointers to next and previous from neighbors should be updated if you delete a node in the middle
//3. If you delete the data at head, head will need to move to head->get_next()
//4. If you delete from the tail, tail will need to move backwards to tail->get_prev()
//Don’t use pointers to things after you’ve deleted them
}
};
//DO NOT MODIFY THIS FUNCTION. IT WILL TEST YOUR LIST CLASS
void List_test() {
List l,l2;
//Check for empty list
string s = l.print_list();
if (s != “Empty Listn”) die(“List::print_list() is broken.”);
//Insert first node
s = l.insert_at_beginning(30,”Moscow”);
if (s != “Moscow inserted”) die(“List::insert_at_beginning didn’t work with an empty list.”);
if (l.get_size() != 1) die(“Your size wasn’t updated properly in insert_at_beginning.”);
s = l.print_list();
if (s == “Empty Listn”) die(“Insert at beginning isn’t working with an empty list.”);
//Insert second node
s = l.insert_at_beginning(40,”Beijing”);
if (s != “Beijing inserted”) die(“List::insert_at_beginning didn’t work with a non-empty list.”);
if (l.get_size() != 2) die(“Your size wasn’t updated properly in insert_at_beginning.”);
//Insert first node in another list
s = l2.insert_at_end(60,”Nanjing”);
if (s != “Nanjing inserted”) die(“List::insert_at_end didn’t work with an empty list.”);
if (l2.get_size() != 1) die(“Your size wasn’t updated properly in insert_at_end.”);
//Insert third node at the end
s = l.insert_at_end(5,”Ile-de-france”);
if (s != “Ile-de-france inserted”) die(“List::insert_at_end didn’t work with a non-empty list.”);
if (l.get_size() != 3) die(“Your size wasn’t updated properly in insert_at_end.”);
//Insert fourth node at the end
s = l.insert_at_end(20,”Roma”);
if (s != “Roma inserted”) die(“List::insert_at_end didn’t work with a non-empty list.”);
if (l.get_size() != 4) die(“Your size wasn’t updated properly in insert_at_end.”);
//Insert fifth node at the beginning
s = l.insert_at_beginning(10,”Kiev”);
if (s != “Kiev inserted”) die(“List::insert_at_beginning didn’t work with a non-empty list.”);
if (l.get_size() != 5) die(“Your size wasn’t updated properly in insert_at_end.”);
string s1 = l.print_list(); //Print forwards
string s1right = “Province: Kiev Cost: 10nProvince: Beijing Cost: 40nProvince: Moscow Cost: 30nProvince: Ile-de-france Cost: 5nProvince: Roma Cost: 20n”;
if (s1 != s1right) {
cout << “==============================================n”;
cout << ” YOUR LIST n”;
cout << s1 << endl;
cout << ” CORRECT LIST n”;
cout << s1right << endl;
die(“Your code is wrong with five provinces in it.”);
}
string s2 = l.print_list(false); //Print backwards
string s2right = “Province: Roma Cost: 20nProvince: Ile-de-france Cost: 5nProvince: Moscow Cost: 30nProvince: Beijing Cost: 40nProvince: Kiev Cost: 10n”;
if (s2 != s2right) {
cout << “==============================================n”;
cout << ” YOUR LIST n”;
cout << s1 << endl;
cout << ” CORRECT LIST n”;
cout << s1right << endl;
die(“Your code is wrong with five provinces in it.”);
}
//Delete Ile-de-France from the middle (cost 5, with 6 as the amount)
int change = 0;
if (l.delete_amount(6,change) != “Ile-de-france deleted”) die(“Deleting Ile-de-france failed”);
if (change != 1) {
cout << “Deleting Ile-de-France (Cost 5, Amount 6) should return 1 change but you returned ” << change << endl;
die(“”);
}
//Delete Kiev from front of list (Cost 10, Amount 10)
s = l.delete_amount(10,change);
if (s != “Kiev deleted”) {
cout << “You were supposed to return ‘Kiev deleted’ but you printed ‘” << s << “‘.n”;
die(“Deleting Kiev failed”);
}
if (change != 0) die(“Deleting Kiev returned wrong change (should be 0)”);
//Delete Roma from end of list (Cost 10, Amount 10)
if (l.delete_amount(23,change) != “Roma deleted”) die(“Deleting Roma failed”);
if (change != 3) die(“Deleting Roma returned wrong change (should be 3)”);
//Testing the list
s = l.print_list();
string t = “Province: Beijing Cost: 40nProvince: Moscow Cost: 30n”;
if (s != t) {
cout << “The code is supposed to print:n” << t;
cout << “But you printed:n” << s;
die(“”);
}
//Add a few more
l.insert_at_end(50,”Cairo”);
l.insert_at_end(40,”Aleppo”);
l.insert_at_beginning(20,”Ayutthaya”);
l.insert_at_end(30,”Ternate”);
l.insert_at_beginning(30,”Kyoto”);
s = l.print_list();
t = “Province: Kyoto Cost: 30nProvince: Ayutthaya Cost: 20nProvince: Beijing Cost: 40nProvince: Moscow Cost: 30nProvince: Cairo Cost: 50nProvince: Aleppo Cost: 40nProvince: Ternate Cost: 30n”;
if (s != t) {
cout << “The code is supposed to print:n” << t;
cout << “But you printed:n” << s;
die(“”);
}
l.delete_amount(20,change); //Ayutthaya
l.delete_amount(30,change); //Kyoto
l.delete_amount(30,change); //Moscow
l.delete_amount(30,change); //Ternate
s = l.print_list();
t = “Province: Beijing Cost: 40nProvince: Cairo Cost: 50nProvince: Aleppo Cost: 40n”;
if (s != t) {
cout << “The code is supposed to print:n” << t;
cout << “But you printed:n” << s;
die(“”);
}
l.delete_amount(40,change); //Beijing
s = l.print_list();
t = “Province: Cairo Cost: 50nProvince: Aleppo Cost: 40n”;
if (s != t) {
cout << “The code is supposed to print:n” << t;
cout << “But you printed:n” << s;
die(“”);
}
l.delete_amount(40,change); //Aleppo – What is an Aleppo, Gary Johnson?
s = l.print_list();
t = “Province: Cairo Cost: 50n”;
if (s != t) {
cout << “The code is supposed to print:n” << t;
cout << “But you printed:n” << s;
die(“”);
}
l.delete_amount(40,change); //Nothing
l.delete_amount(40,change); //Nothing
l.delete_amount(50,change); //Cairo
s = l.print_list();
t = “Empty Listn”;
if (s != t) {
cout << “The code is supposed to print:n” << t;
cout << “But you printed:n” << s;
die(“”);
}
if (l.get_size() != 0) {
cout << “The list should be empty since I’ve deleted everything, but you say the size is ” << l.get_size() << endl;
die(“Make sure you add to size in your inserts and subtract from it in your deletes”);
}
s = l.delete_amount(50,change); //Nothing
if (s != “Nothing deleted”) {
die(“The code tried deleting from an empty list but your code did not return ‘Nothing deleted’.”);
}
}
