# Final Exam
Please follow the below instructions carefully; you may get point deduction otherwise.
1. Use the keyword `const` whenever appropriate.
2. Implement the given algorithms, not the ones you invent.
3. Do proper encapsulation and declare members as private or protected whenever possible to avoid unnecessary information revealing.
However, if you can’t fulfill all requirements, you may earn partial credit for fulfilling part of them. For example, implement a non-template version for a template question.
# Problem 1 - Circular Doubly linked list (4 pts)
## Description
A circular doubly linked list is a common variant of a linked list. Besides everything we have in a normal linked list, a circular doubly linked list includes a backward edge between any two neighbor nodes, making it easier to traverse back and forth in the list, hence "doubly". In addition to that, in a circular doubly linked list, the backward edge of the first node always points to the last node, and the forward edge of the last node always points to the first node, hence "circular". Below is a simple graph representation of a doubly linked list.
In the provided file `List.h`, we have implemented the double circular linked list in class `List`.
You are encouraged to understand the code before proceeding.
## 1-1 Concatenate Two Lists
In this section, you are asked to expand its feature and implement a concatenating function.
First, inherit the base class `List` with class `MyList`.
Next, add a new member function `concatenate`. You should determine the return type and parameters yourself.
What this function does is that it concatenates the circular doubly linked list provided in the argument to the caller object, and clears the list provided in the argument.
Below is a sample usage for this concatenate function.
### Sample Input
### Sample Output for `cout`
```
MyList la,lb;
la.push_front(1);
cout << la << endl;
lb.push_front(3);
lb.push_front(2);
cout << lb << endl;
la.concatenate(lb);
cout << la << endl;
cout << lb << endl;
```
```
1->NULL
2->3->NULL
1->2->3->NULL
NULL
```
```
MyList la,lb,lc;
la.push_front(1);
lb.push_front(2);
lc.push_front(3);
la.concatenate(lb).concatenate(lc);
cout << la << endl;
cout << lb << endl;
cout << lc << endl;
```
```
1->2->3->NULL
NULL
NULL
```
## Hint
Initial state of circular list A,B
After calling `A.concatenate(B)`
## File
MyList.h
# Problem 2 - Binary Search Tree (6 pts)
## Description
Recall that we have implemented the `BST` class which is given in `BST.h`. Write a class named `MyBST` which inherits the `BST` class publicly. Add two functionality in the `MyBST` class to find the minimum and the second minimum of distinct integers. Test your code using the `2.cpp`.
## 2-1 Find min (2 pts)
Find the minimum of distinct integers.
### Algorithm
1. Start at the root node.
2. Follow the left child in each branch until you reach a node that does not have a left child. The value at that node is the minimum value in the binary search tree.
### Sample Input
### Sample Output
```cpp
#include <iostream>
#include "BST.h"
#include "MyBST.h"
using namespace std;
int main() {
// Find min
MyBST ta;
ta.insert(3);
ta.insert(4);
ta.insert(5);
ta.insert(2);
ta.insert(1);
cout << ta.findMin() << endl;
return 0;
}
```
```
1
```
## 2-2 Find 2nd min (4 pts)
Find the 2nd minimum of distinct integers.
### Algorithm
First, find the node with the minimum value. Then, find the node with the second minimum value as follow:
- If the minimum node has NO right sibling, then the parent of the min node is the second minimum node
- Otherwise, the second minimum node is the minimum node in the subtree rooted with the right sibling of the minimum node
### Sample Input
### Sample Output
```cpp
#include <iostream>
#include "BST.h"
#include "MyBST.h"
using namespace std;
int main() {
// Find min
MyBST ta;
ta.insert(3);
ta.insert(4);
ta.insert(5);
ta.insert(2);
ta.insert(1);
cout << ta.find2ndMin() << endl;
return 0;
}
```
```
2
```
## File
MyBST.h
# Problem 3 - Fraction (13 pts)
## Description
Write a class named `Fraction` that supports addition, subtraction, multiplication, division and power. There are two private ****members: numerator and denominator (nonzero). Use template for int, short and long.
## 3-1 Constructor & Destructor (1 pt)
Construct and destruct the class.
### Sample Code
```cpp
// Constructor 1
Fraction<int> fractionA;
// Constructor 2
Fraction<int> fractionB(6, -14);
// Constructor 3
Fraction<int> fractionC(fractionA);
```
**Hint:** Write the GCD and the LCM function as private members of the class.
## 3-2 `cin` & `cout` (1 pt)
Overload the standard input and output. Make sure every output fraction is irreducible, and make it an integer whenever the numerator is a multiple of the denominator.
**Hint**
```cpp
istream& operator>>(istream& i, Fraction& F){}
ostream& operator<<(ostream& o, const Fraction& F){}
```
### Sample Code
### Sample Input
```cpp
Fraction<int> fractionD;
cin >> fractionD;
cout << fractionD << endl;
Fraction<int> fractionE(6, -14);
cout << fractionE << endl;
Fraction<int> fractionF(fractionD);
cout << fractionF << endl;
Fraction<int> fractionG(10, -5);
cout << fractionG << endl;
```
```
15/-25
```
### Sample Output
```
-3/5
-3/7
-3/5
-2
```
## 3-3 Setter & Getter (1 pt)
Set and get the numerator and the denominator.
```cpp
void setFraction(T num, T den);
T getNumerator() const;
T getDenominator() const;
```
### Sample Code
### Sample Output
```cpp
Fraction<int> fractionH;
fractionH.setFraction(14, 18);
cout << fractionH << endl;
cout << fractionH.getNumerator() << endl;
cout << fractionH.getDenominator() << endl;
```
```
7/9
7
9
```
## 3-4 Add, Subtract, Multiply, Divide, and Power (5 pts)
Overload operator `+`, `-`, `*`, `/`, and `^` to support addition, subtraction, multiplication, division, and power respectively.
**Note**
When you are overloading `^` and `cout`, write `cout << (x^2)` instead of `cout << x^2`.
### Sample Code
### Sample Input
```cpp
Fraction<int> fractionA;
Fraction<int> fractionB;
cin >> fractionA;
cin >> fractionB;
cout << fractionA + fractionB << endl;
cout << fractionA - fractionB << endl;
cout << fractionA * fractionB << endl;
cout << fractionA / fractionB << endl;
cout << (fractionA ^ 3) << endl;
```
```cpp
3/4 // input
5/6 // input
```
### Sample Output
```cpp
19/12 // +
-1/12 // -
5/8 // *
9/10 // /
27/64 // ^3
```
## 3-5 `+=`, `-=`, `*=`, `/=` and `^=` (5 pts)
Overload `+=`, `-=`, `*=`, `/=` and `^=`.
### Sample Code
```cpp
Fraction<int> fractionA;
Fraction<int> fractionB;
cin >> fractionA;
cin >> fractionB;
fractionA += fractionB;
cout << fractionA << endl;
fractionC -= fractionB;
cout << fractionC << endl;
fractionC *= fractionB;
cout << fractionC << endl;
fractionC /= fractionA;
cout << fractionC << endl;
fractionC ^= 2;
cout << fractionC << endl;
fractionA += (fractionB + fractionC);
cout << fractionA << endl;
fractionA = (fractionB += fractionC);
cout << fractionA << endl;
(fractionB += fractionC).setFraction(-3,-4);
cout << (fractionB += fractionC) << endl;
cout << (fractionB += fractionC).getNumerator() << endl;
cout << (fractionB += fractionC).getDenominator() << endl;
cout << fractionB + fractionC << endl;
cout << fractionA + fractionB + fractionC + fractionD << endl;
Fraction<int> fractionJ(4, 2);
cout << fractionJ << endl;
Fraction<int> fractionK;
fractionK.setFraction(12, -7);
cout << fractionK << endl;
```
### Sample
```cpp
3/5 // input
3/7 // input
36/35 // +=
6/35 // -=
18/245 // *=
1/14 // /=
1/196 // ^=
1433/980 // fractionA += (fractionB + fractionC)
85/196 // fractionA = (fractionB += fractionC)
37/49 // (fractionB += fractionC).setFraction(-3,-4)
149 // (fractionB += fractionC).getNumerator()
98 // (fractionB += fractionC).getDenominator()
151/196 // fractionB + fractionC
758/315 // fractionA + fractionB + fractionC + fractionD
2 // fractionJ(4, 2);
-12/7 // fractionK.setFraction(12, -7);
```
## File
Fraction.cpp
# Problem 4 - League of Legend (17 pts)
## Description
There are three roles: the Assassin, the Warrior, and the Joker. They have different attributes shown in the following table (Table A):
### Table A
The following table (Table B) explains each fields in Table A:
### Table B
These three roles have a natural advantage/disadvantage over each other. The following table (Table C) shows the base damage multiplier when two roles fight each other.
### Table C
In short, the attacking flow is shown as follow:
**Example**
Suppose an assassin is attacking a warrior.
1. From Table A, the base damage of the assassin is 15.
2. From Table C, multiply the base damage of the assassin by 1.3; thus, the adjusted base damage is 15 * 1.3 == 19.5.
3. From Table A, ****the assassin has 25% chance to send a critical attack (scaling the adjusted base damage by 2.5). If this happens, then the scaled damage of the assassin is 19 * 2.5 == 48.75.
4. From Table C, the warrior has 5% chance to dodge the attack from the assassin. If the warrior dodges the attack successfully, then no harm will do to the warrior, that is. However, if the warrior is not able to dodge the attack, then its health point is decreased by the amount of the damage from the assassin.
## Problem 4-1 The Agent Class (3 pts)
Complete an abstract class `Agent`. There are two public pure virtual functions.
- The Attack Function `virtual void attack(Agent*) = 0;`
Calculate total amount of damage sent by one agent
- The Get Damage Function `virtual void get_dmg(float dmg) = 0;`
Decrement the health point of the agent (should also check whether the damage is dodged)
There will be three derived classes of the Agent class (see problem 2-2 for more information):
1. the Assassin class (publicly inheriting)
2. the Warrior class (publicly inheriting)
3. the Joker class (publicly inheriting)
All these classes inherit the above two functions with different implementation. Write all declarations in `Agent.h` and all implementations in `Agent.cpp`.
### Agent.h
```cpp
#ifndef _AGENT_H_
#define _AGENT_H_
class Agent {
protected:
// Your code here
public:
Agent() {}
virtual ~Agent() {}
virtual void attack(Agent*) = 0;
virtual void get_dmg(float dmg) = 0;
// Your code here
/* Hint
bool will_dodge();
bool will_critical();
float get_hp(void);
void get_stunned(void);
*/
};
#endif
```
### Agent.cpp
```cpp
#include "Agent.h"
```
## Problem 4-2 Build The Three Characters (9 pts)
Implement the Assassin class, the Warrior class, and the Joker class. Besides the `attack` function and the `get_dmg` function, each role has a special ability (see **Special Abilities**).
## Basic Attributes
See Table A.
## Special Abilities
### The Assassin Class (3 pts)
When an assassin's health point is lower than 20, every attack will heal his own hp by the actual damage done to his opponent's health point times 1/3.
**Example**
Suppose an assassin has health point 18 damage 15 and is attacking a warrior. If the assassin does NOT invoke his critical attack, and the warrior fails to dodge the attack, then the assassin is able to recover its health point by 15 * 1.3 * 1/3 == 6.5.
### The Warrior Class (3 pts)
When the warrior's hp reaches 0 or below, if his hp is not lower than -10, he will be revived, and his hp will be reset to 50. This ability can only be used once.
**Example**
For example, suppose a warrior has health point 3 (i.e, still alive) and never revived before. After receiving an attack of damage 8 and failing to dodge it, the health point is now 3 - 8 == -5. At this moment, reset the health point of the warrior to 50.
### The Joker Class (3 pts)
Every time a joker attacks, he has a 30% chance of stunning the opponent. A stunned opponent will lose his ability to attack for one round.
**Example**
Suppose a joker successfully stuns a warrior, then the warrior is NOT able to attack for one round.
### Character.h
```cpp
#ifndef _CHARACTER_H_
#define _CHARACTER_H_
class Assassin:public Agent{
private:
public:
};
class Warrior:public Agent{
private:
public:
};
class Joker:public Agent{
private:
public:
};
#endif
```
### Character.cpp
```cpp
#include "Character.h"
// Assassin
// Warrior
// Joker
```
### Sample Code
The following is an example code snippet. The `get_hp()` function return the hp of a character.
```cpp
#include <iostream>
#include "Agent.h"
#include "Character.h"
using namespace std;
int main()
{
cout << "Creating assassions A and Warrior B..." << endl;
Agent* A = new Assassin();
Agent* B = new Warrior();
cout << "Initially...\t\tHP of A: " << A->get_hp() << "\t" << "HP of B: " << B->get_hp() << endl;
cout << "A is attacking B..." << '\t';
A->attack(B);
cout << "HP of A: " << A->get_hp() << '\t';
cout << "HP of B: " << B->get_hp() << endl;
cout << "B is attacking A..." << '\t';
B->attack(A);
cout << "HP of A: " << A->get_hp() << '\t';
cout << "HP of B: " << B->get_hp() << endl;
cout << "A is attacking B..." << '\t';
A->attack(B);
cout << "HP of A: " << A->get_hp() << '\t';
cout << "HP of B: " << B->get_hp() << endl;
cout << "B is attacking A..." << '\t';
B->attack(A);
cout << "HP of A: " << A->get_hp() << '\t';
cout << "HP of B: " << B->get_hp() << endl;
}
```
### Sample Output
```cpp
Creating assassions A and Warrior B...
Initially... HP of A: 50 HP of B: 100
A is attacking B... HP of A: 50 HP of B: 51.25
B is attacking A... HP of A: 40 HP of B: 51.25
A is attacking B... HP of A: 40 HP of B: 31.75
B is attacking A... HP of A: 30 HP of B: 31.75
```
## Problem 4-3 Round-Robin (5 pts)
To know which character is the best among the three, we apply the Round-Robin method. In a Round-Robin round, every possible match-up will be held exactly once. Since here we have three kinds of characters, there are 3 * 3 == 9 of **(first to attack, second to attack)** pairs of match up. During one match, two characters **take turns** to attack each other **until one of them dies**. We set up a 2D array `int result[3][3]` to count the **number of winnings**. For example, in one Round-Robin, we have the following table. The (Assassin, Warrior) == 1, indicating that the assassin attacks first and beats the warrior in this round.
Do 10000 Round-Robin rounds and use the given `display` function to print out the winning ratios.
### Round_Robin.h
```cpp
#ifndef _ROUND_ROBIN_H_
#define _ROUND_ROBIN_H_
#include <iostream>
#include "Agent_sol.h"
#include "Character_sol.h"
using namespace std;
int result[3][3]{ 0 };
void Round_Robin(int rounds)
{
// Your code here
}
void display(int rounds)
{
string Characters[3]{ "Assass", "Warrior", "Joker" };
cout << "\t" << Characters[0] << "\t" << Characters[1] << "\t" << Characters[2] << endl;
for (int i = 0; i < 3; i++) {
cout << Characters[i] << "\t";
for (int j = 0; j < 3; j++) {
cout << int(float(result[i][j]) * 100 / rounds) << "%\t";
}
cout << endl;
}
}
#endif
```
### Sample Code
```cpp
#include <ctime>
#include "Round_Robin.h"
using namespace std;
int main()
{
int rounds = 10000;
srand(time(NULL));
Round_Robin(rounds);
display(rounds);
}
```
### Sample Output
```cpp
Assass Warrior Joker
Assass 60% 91% 35%
Warrior 17% 61% 68%
Joker 83% 43% 59%
```
## File
1. Agent.h
2. Agent.cpp
3. Character.h
4. Character.cpp
5. Round_Robin.h
{"metaMigratedAt":"2023-06-15T13:39:16.540Z","metaMigratedFrom":"Content","title":"Final Exam","breaks":true,"contributors":"[{\"id\":\"43b588d9-b0f2-4cbe-9a8b-600b35bdd822\",\"add\":1507,\"del\":1528}]"}