Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)

WIA/WIB1002 Data Structure S2, 2022/23

Topic 1: Three Kingdoms:The Battle of Red Cliff

Introduction

The Battle of Red Cliff, also known as the Battle of Chibi, was a decisive naval battle in
the winter of AD 208–209 at the end of the Han dynasty. The battle was fought between
the allied forces of the southern Kingdom, which is led by Sun Quan and Shu Kingdom,
which is led by Liu Bei against the numerically-superior forces of the northern warlord
Cao Cao, the Emperor of the Wei kingdom.

Cao Cao was a powerful and ambitious military leader who had risen to prominence
during the final years of the Han dynasty. He was a skilled strategist and had amassed
a large and disciplined army under his command. In AD 208, Cao Cao led his forces
southwards with the aim of consolidating his control and defeating his rivals, Sun Quan
and Liu Bei.

The Battle of Red Cliff lasted months, and the war took place in several places, both on
the ground and on the water. The final battle takes place in a river near a cliff, thus the
name ‘The Battle of the Red Cliff’.

During the battle, the allied forces of Sun Quan and Liu Bei employed a range of tactics,
including fire attacks, to destroy Cao Cao's ships and disrupt his supply lines. They also

1
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23
used their superior knowledge of the terrain to lure Cao Cao's forces into a trap, where
they were surrounded and decimated by the allied troops. In the end, the allied forces
emerged victorious, and Cao Cao was forced to retreat northwards with his army.

Forces of the Three Kingdom drawn on an ancient map

Sun Quan is the Wu Kingdom's emperor. He is also known as Eastern Wu or Sun Wu:

No. Character Ability Details

1.

Name: Sun Quan

Army Type: Cavalry
Strength: 96, Leadership: 98, Intelligence: 72, Politic: 77, Hit Point: 95

2
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23

Problem Statement
In this assignment, you’re Sun Quan’s loyal minister and
brilliant strategist who processes the knowledge of data
structures and algorithms. You are required to help Sun Quan
to win the battle against Cao Cao, the ruler of Wei Kingdom in
The Battle of Red Cliff.

Basic Features/Requirements (12 marks)

1. Forming Wu Kingdom’s Hierarchy (2 marks)

To manage human resources easily, Sun Quan decides to have a Wu kingdom
hierarchy.

Sun Quan appointed Zhou Yu as the Chief of Military and Zhang Zhao as the Chief of
Management. These are the details:

No. Character Ability Details

1.

Name: Zhang Zhao

Army Type: Archer
Strength: 22, Leadership: 80, Intelligence: 89, Politic: 99, Hit Point: 60

3
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23

2.

Name: Zhou Yu
Army Type: Cavalry
Strength: 80, Leadership: 86, Intelligence: 97, Politic: 80, Hit Point: 90

Besides the two Chiefs, there are also Generals, acting as troop unit leaders. They
belong either to the military department or the management department:

No. Character Ability Details

1.

Name: Xu Sheng
Army Type: Archer

Strength: 90, Leadership: 78, Intelligence: 72, Politic: 40, Hit Point: 94

2.

Name: Zhu Ge Jin

Army Type: Archer
Strength: 63, Leadership: 61, Intelligence: 88, Politic: 82, Hit Point: 71

4
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23

3.

Name: Lu Su
Army Type: Infantry Strength: 43, Leadership: 87, Intelligence: 84, Politic: 88, Hit Point: 53

4.

Name: Tai Shi Ci Strength: 96, Leadership: 81, Intelligence: 43, Politic: 33, Hit Point: 97
Army Type: Cavalry

5.

Name: Xiao Qiao

Army Type: Infantry

Strength: 42, Leadership: 52, Intelligence: 89, Politic: 77, Hit Point: 34

5
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23

6.

Name: Da Qiao
Army Type: Cavalry
Strength: 39, Leadership: 62, Intelligence: 90, Politic: 62, Hit Point: 41

Name: Zhou Tai

Army Type: Infantry Strength: 92, Leadership: 89, Intelligence: 72, Politic: 43, Hit Point: 99

Name: Gan Ning

Army Type: Archer
Strength: 98, Leadership: 92, Intelligence: 45, Politic: 23, Hit Point: 97

6
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23

Name: Lu Meng
Army Type: Cavalry
Strength: 70, Leadership: 77, Intelligence: 93, Politic: 83, Hit Point: 88

10

Name: Huang Gai

Army Type: Infantry
Strength: 83, Leadership: 98, Intelligence: 72, Politic: 42, Hit Point: 89

Use a tree data structure to implement the hierarchy that includes the Emperor Sun
Quan himself, the two Chiefs of military and management, and the Generals.

The Generals are assigned to either the management department or the military
department according to their expertise. Make the assignment automatic to ease the
work of Sun Quan. The term and conditions for the assignment are:
● if the General’s intelligence > strength, assign to the management department
● if the General’s strength > intelligence, assign to the military department

The kingdom’s hierarchy shall be a three-level tree hierarchy.

7
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23

2. Soldier’s Arrangement (1 mark)

Arranging his Generals is a challenging task for Sun Quan, as he strives to maintain a
particular order consistently. He wants the Generals to always be sorted. Use various
sorting methods based on different attributes, such as Leadership, Strength,
Intelligence, Political Skill, Hit Point to sort the Generals.

Sort the General based on their ability. Then, use binary search to search a General
with a specific ability.

Then using binary search, suggest 3 Generals in one team in each field (politic,
leadership, strength, intelligence) with the minimum requirement S level, A level, B
level, and C level:

S level: sum of ability >= 250

A level: sum of ability >= 220
B level: sum of ability >= 190
C level: sum of ability <= 190

3. Borrowing Arrows with Straw Boats (1 mark)

8
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23
To win the battle against Cao Cao, having enough weapon resources such as arrows is
very important. However, the Wu kingdom is currently short of arrows and the
production of arrows takes time. The smartest military
strategist, Zhu Ge Liang has come up with a brilliant. He
foresees the river field will be filled with fog one day. He will
deceive the enemy by covering boats with straw men to make
them appear as real soldiers thanks to the fog, and then use
this ruse to trick the enemy into believing that they are
attacking a larger force. As the enemy fires their arrows at the
straw men, Zhu Ge Liang and his troops will retrieve the
arrows and use them against the enemy, thereby gaining an advantage in battle. This
clever tactic demonstrates the power of strategy and the importance of using one's wits
to outsmart the opponent.

Zhu Ge Liang has designed the boat that will be used to capture the arrows, as in the
diagram below:

There are four directions of the boats, the straw men are placed along the edge of the
boat front, right, back, and left (red area in the diagram above).

9
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23
There are several conditions:
1. The number of straw men placed is different across all four sides.

2. The enemy will shoot N waves of arrows. The number of arrows shot in each
wave will decrease gradually, which means it’s in decreasing order.

3. The capture efficiency decreases after the first wave of arrows since some of the
straw men are depleted after capturing some arrows.

4. The number of straw men in one direction is always less than 100. The number
of arrows captured in one direction is calculated as: number of arrows * (number
of straw men left/100)

The example below shows how the capture efficiency drops in one direction:

1st wave arrow: 1000 arrows

100 straw men at 100% efficiency
100 straw men can get 1000*(100/100) = 1000 arrows

2nd wave arrow: 1000 arrows

Efficiency is 80% left -> (100*0.8) = 80 straw men
80 straw men can get 1000*(80/100) = 800 arrows

3rd arrow: 1000 arrows

Efficiency is 40% left -> (100*0.4) = 40 straw men
40 straw men can get 1000*(40/100) = 400 arrows

4th arrow: 1000 arrows

Efficiency is 0% left -> (100*0) = 0 straw men
0 straw men can get 1000*(0/100) = 0 arrows

Thus, the straw men cannot be used more than 3 times.

The boats are ought to turn such that in each wave, one face of the boat is always
facing the enemy. Example: left, right, left, right, front.

10
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23
Considering the different number of straw men placed in each direction and the fact that
the capture efficiency will drop, help Zhu Ge Liang to determine the best direction for
the boat to face the enemy in each wave to maximize the arrows captured.

Example input:
Number of straw men
Front: 10
Left: 50
Right: 50
Back: 15

Arrow: [2000,1500,1000,800,600,500,300,300]

Example output:
Boat direction: [left, right, left, right, left, right, back, front]
Arrow received: [1000, 750, 400, 320, 120, 100, 45, 36]
Total = 2771

4. Enemy Fortress Attack Simulation (2 marks)

Before the Battle of the Red Cliff, Cao Cao had also built a fortress on the battlefield as
their headquarters.

Graph: example for the battlefield

11
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23

Graph for map

Node 1 is the starting point. Node 3 to Node 7 is a directed edge.

Display all the possible paths, considering that the time taken to travel to each location
is the same. Use a breadth-first search algorithm to find all possible paths to reach the
enemy's base camp.

12
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23

Graph showing the base camp is at the node 8

Example output:
Enter the base camp for the enemy base camp: 8
Best path:
1-> 6-> 8
1-> 10 -> 8

Enter the base camp for the enemy base camp: 7

Best path:
1-> 3-> 7
1-> 6-> 7

13
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23

5. Food Harvesting (2 marks)

You need to depart from Sun Wu’s camp (Node 1) and harvest all of the food on each
node and back to Sun Wu’s camp (Node 1) without passing through a node twice.
Please find out the path.

Then, sometimes some of the nodes may not have food, so you may not need to go to
that node.

Example: Node 9 doesn't have food this time. So your path should not have node 9 and
return a new path to return node 1. If the node is 8 and you must pass through that
node in order to connect all food. Then, you should include node 8 in your path.

Example input:
Enter node without food: 9

Example output:
Path:
<answer_path>

14
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23

6. Encrypted Text (1 mark)

To penetrate the enemy forces, steal the enemy’s

information, and manipulate the enemy’s decisions, Sun
Quan assigned a spy, Pang Tong as Cao Cao’ s loyal
minister. For Sun Quan to communicate with Pang Tong,
they cannot write letters in a pure language but instead,
have to encrypt the text so that only both of them can
understand the text. They decided to use Caeser Cipher as their encryption algorithm.

The other syntax of the encrypted text is also given below:

^ Character after this symbol is capitalized

$ Space character

() The text inside parentheses is inverted

Help Pang Tong decipher the letter sent by Sun Quan. Your program should be able to take in
an input text, and shifting position. Encryption and decryption should be shown:

Example input:
Text:^hkcpzl$^jhv$^jhv$av$bzl$^aol$^johpu$^zayhalnlt,$(ojpod)$pz$av$johpu$opz$(zw
pozlsaahi)$dpao$zayvun$pyvu$johpuz.
Shift: 7

Example output:
Advise Cao Cao to use The Chain Strategem, which is to chain his battleships with
strong iron chains.

15
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23

7. Red Cliff on Fire (1 mark)

Everything is well prepared before the final battle. Sun Quan’s forces have enough
arrows, enough food. They cleared the enemy's base camp on the battleground.
Moreover, Cao Cao had used The Chain Strategem as advised by spy Pang Tong,
which is the decision that will make him regret.

A 2D matrix that contains the position of all Cao Cao chained battleships will be
provided by Pang Tong. Sun Quan will catapult fireballs to the battleships. Upon
landing, the fireball will gradually spread between Cao Cao chained battleships with the
help of the east wind.
1100100111
1000100010
1011101010
1000001000
1011111111
0000000000
1111011010
1000000010
1000101111
1000100000

1 denotes the battleship, 0 denotes the position without a battleship. A group of chained
battleships (straight and diagonal) forms a battleship cluster (red box in diagram
below).

16
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23

Find out how many clusters are there so that Sun Quan can determine how many
fireballs to prepare.

Example Input:
1100
1000
1011
1000

Example Output:
2 cluster

8. Engaging Cao Cao at Hua Rong Road (2 marks)

Finally, Cao Cao lost The Battle of Red Cliff. He retreated away from the river via Hua
Rong Road and managed to escape. Hua Rong Road is a road with complex terrains.
Show how Cao Cao might have retreated from Hua Rong Road so that Liu Bei and
Zhao Yun can catch up with him. Besides, Guan Yu is ahead and is engaging Cao Cao
at the exit of the maze.

Liu Bei Zhao Yun Guan Yu

This is a sample 2D maze of Hua Rong Road.

17
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23

1111111111111
2000100010001
1011101010111
1000001000001
1011111111011
1000100000001
1111111011101
1010000010001
1010101111111
1000100000003
1111111111111

2 denotes the starting point. 3 denotes the exit of the maze.

Display the path of how Cao Cao might have escaped.

Although, in real history, Cao Cao managed to escape from Sun Wu’s chasing soldiers,
The Battle of Red Cliff is still one of the most iconic events in the Three Kingdoms.

Extra Features (4 marks)

Graphic User Interface (GUI)

Build your Sun Wu system with a nice-looking GUI. It is possible to simulate it in a graph
or in a graph with a graphic map background. Your program should simulate the
process of destroying the enemy camps (movement of soldiers to the camps with
respect to time).

Extra Algorithm Implementation

You can implement other searching algorithms to search for the best-known path. Here
are some of the possible searching algorithms you might want to consider:
1. Best First Search
2. A* Search
3. Dijkstra algorithm

18
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23
4. Your custom searching algorithm

Dynamic Arrow Borrowing

The amount of arrow shots is not in descending order anymore, it will be in random
input like the following:

Arrow: [300,1500,1000,2000,600,800,300,500,400]

The straw men are also limited to only 2 uses. Mean after 2 uses, the coefficient will be
dropped to 0. It is not necessary to capture the arrow each time.

Find out how much the arrows will be and your boat direction.

Food Harvesting I
Given each node will harvest you 100 food. So, you need to assign 3 Generals in
politics or intelligence to do those tasks. Note that the type of teams will buff the food
production.

S team in politic = food *2

A team in politic = food *1.5
B team in politic = food *1.2
C team in politic = food * 1

S team in intelligence = food *1.8

A team in intelligence = food *1.3
B team in intelligence = food *1
C team in intelligence = food * 0.8

Maximize the food production by selecting your Generals.

19
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23

Food Harvesting II
Report! Enemies ahead! All of the nodes are guarded by a number of enemies. To
eliminate and capture the camps, Sun Quan wants General Xu Sheng, Lu Meng, and
Xiao Qiao to occupy all the camps. Three of them have different strength points,
denoted in Question 1.

Each node has a soldier count. The food can only be captured by a General having a
strength point equal to or more than the soldier count.

A path is a sequence of visited and captured enemy camps by one General, starting
and ending at Sun Wu’s camp (Node 1). A cost is the total steps moved between nodes
by a General. A simulation is a list of paths of all Generals capturing the enemy camps.

The number of enemy soldiers in each node is shown:

Node 1 0 Node 6 6

Node 2 9 Node 7 8

Node 3 8 Node 8 3

Node 4 5 Node 9 5

Node 5 3 Node 10 6

Display the simulation with the smallest cost.

Example output:

Best Simulation:
Total cost = 14
Xu Sheng:
1->10->9->8 ->10 ->1
Cost = 5

Lu Meng:
1->3->4 ->2->1
Cost = 4

20
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23

Xiao Qiao:
1->6->5->7->6->1
Cost = 5

Enemy Fortress Attack Simulation I

Showing distance in the map

Even though the nodes showing the nodes are near, it is not necessary that the nodes
are close. The distance and the geographical factor may cause the travel time to be
different.

Given geographical factor

● Edges with flat road

○ 1-6
○ 1-3
○ 5-6
○ 7-8

21
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23
○ 7-9
○ 1 - 10
○ 9 - 10

● Edges with forest

○ 1-2
○ 5-7
○ 6-7
○ 8 - 10

● Edges with swamp

○ 2-4
○ 3-4
○ 4-5
○ 8-9

● Edges with plank road

○ 3-7
○ 6-8

The general’s speed when entering specific edges

- Cavalry - speed : 2 km/h
- Flat road - x 3
- Forest - x 0.8
- Swamp - x 0.3
- Plank road - x 0.5
- Archer - speed: 1 km/h
- Flat road - x 2
- Forest - x 1
- Swamp - x 2.5
- Plank road - x 0.5

- Infantry - speed:1 km/h

- Flat road - x 2
- Forest - x 2.5
- Swamp - x 1
- Plank road - x 0.5

Considering the geographical conditions, find again the path that would be the shortest
time to reach the enemy fortress for each General.

22
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23

Text Converter with More Secured Encryption

The current Caeser Cipher uses simple shifting. It is very easy for someone to guess
the shifting used in the cipher, thus not used in the real world. You must now implement
a different encryption algorithm that is highly secured and not prone to leakage.
Besides, a new rule is introduced:

&num{} All of the characters should be subtracted

with num before decrypting it

Also, you may also create your own cipher algorithm. You may refer to some common
encryption algorithm that works. Explain how secure your encryption is.

Red Cliff on Fire with Optimized Points

Once the fireball is thrown on one coordinate in a cluster, it will spread in all 8
directions(straight and diagonal). However, throwing the fireball at random coordinates
does not efficiently burn enemies’ battleships.

For instance, consider the cluster below:

11000
11100
01100
01100
10000

In this cluster, if the fireball is thrown on point [4,0], it would take four cycles for the
whole cluster to be completely burnt (fire spreading four times). However, if the fireball
is thrown on point [2,1], it would only take two cycles (fire spreading two times) for the
cluster to be burnt down.

23
Group Assignment Topic 1 (Three Kingdoms:The Battle of Red Cliff)
WIA/WIB1002 Data Structure S2, 2022/23

To maximize the speed at which all battleship clusters are burned, determine the
optimal coordinates for throwing the fireball for each cluster to ensure the enemy’s
battleships are burnt down in the shortest time possible. If there are 5 clusters, there
shall be 5 optimal coordinates.

Special Note: Apart from the extra features listed in this document, feel free to include
any other relevant extra features that spark your interest!

Tips or Recommendations
1. To optimize the implementation, it is advisable to utilize as many appropriate data
structures as possible. Additionally, OOP practices are highly recommended so
that your code base is well structured.
2. To collaborate with your teammates, Git version control is recommended.
3. Try to learn Graph data structure and its related algorithm, it’s helpful for most of
the features.
4. You might want to try out Leetcode, you might get the intuition to solve some of
the questions.
5. Be creative!
6. Background story:
Red Cliff movie - Red Cliff (2008) - IMDb
Dynasty Warrior Game - Dynasty Warriors (series) | Koei Wiki | Fandom

References and contact information

If you have any questions regarding the question, you can email to
[email protected]

24