Learning Outcomes:

• Gain more confidence programming in Java.
• Design an object-oriented programming (OOP) solution to a problem.
• Use popular data structures: List, Set, Queue, Map
• Create and traverse a Graph using popular algorithms

Warning about static fields

You should not need to use static fields in this assignment. If you are using static fields, you will encounter lots of problems.

Static Methods are fine, Static Fields are not (unless are final)!. See this ED post

If you use static fields, you will be penalised

If you use static fields, you will notice a weird behaviour that your test cases will pass when executed one at a time, but mostly fail when executed in one go. This is because the static field values are shared across all test cases, and the test cases are executed with this persistant value. This is not the behaviour you want.

So, be sure to always test your final submission using the command we have provided below, as this is how you will be marked:

./mvnw clean compile test for Unix/Mac OS or .\mvnw.cmd clean compile test for Windows

</div>

Table of Contents

• Recommended Approach
• Routing Application
• Files Provided
• OOP Requirements
• The Commands
• Tasks
  • Task 1
  • Task 2
• Marking Scheme
• Important Instructions

Recommended Approach

To make sure that your machine is properly set for doing the assignment (and all assignments in this course), refer to the FAQ on the course website.

Then it’s a matter of:

• Clone the GitHub repository.
• Use Visual Studio Code for doing the assignment.
• Use the graphical “Testing” view in Visual Studio Code to run the tests (details below).
• As a final check before submitting, use the Maven wrapper to check that everything compiles and the test cases pass (details below).
• To debug your program you should use the debugging mode step by step as we did in class, this will drastically help you to debug and understand your program. Recall that if a test case runs for more than 10 seconds, it will fail. We have to do this check because some students might create infinite loops and the marking of the assignments will run for eternity. This poses a problem for the debugging mode as you will likely spend more than 10 seconds inspectioning the execution. To solve the issue, you have to comment line 51 of CliTest.java.

   // @Rule public Timeout timeout = new Timeout(10, TimeUnit.SECONDS);

Remember to uncomment that line when you finish the assignment to make sure that each test does not run for more than 10 seconds

Let’s begin!

The Risk Map

Do you know this map?

Is the Map of the Game Risk! a strategy board game where you fight your opponents with dice to win their countries. Don’t worry, I am not asking you to implement the game; we will just use the map. I’m not sure how famous this game is in New Zealand, as New Zealand is obviously missing from the map. Apparently, it is a common trend to omit our beautiful country. Maps Without NZ.

Anyway, this map is a simplified version of the World map with only 42 countries and 6 continents: Europe, North America, South America, Africa, Asia, and Australia. You can see that there are gray lines to show which countries are connected via water.

A Graph is the perfect data structure to model a map. In this case, countries are the nodes (vertices) of the graph. The graph will have 42 nodes. The edges in the map represent the “neighborhood” relation. For example, Brazil has Venezuela, North Africa, Argentina, and Peru as neighboring countries. Thus, Brazil will have an edge to the nodes of the graph that represent those countries. For example, there is no edge between India and Siberia because they are not adjacent countries (do not share a border or have a link via water). This relation is clearly symmetric: if country A is a neighbor of country B, then country B must also be a neighbor of country A.

By traversing the resulting Graph, we can simulate routing across countries. For example, to go from Congo to Brazil, a possible path is Congo -> North Africa -> Brazil. We cannot jump from Congo to Brazil because these two countries are not adjacent; we must go through North Africa.

What you need to implement for A3 is the code to load the map into a graph and print the shortest path between two countries.

Additionally, you can notice that in the Risk map, each country has an associated number. In the Risk game, these numbers are used for reinforcement bonuses. In this assignment, we are using those numbers to specify the taxes that need to be paid to cross the border. For example, the total taxes to pay from Congo to Brazil are: 5 (for North Africa) and 2 (for Brazil), totaling 7 NZD. We don’t need to pay the 1 NZD for Congo because we start from there.

This assignment simulates a real case scenario where a company offering international delivery wants to implement software to find the optimal routing across the world. The map would be more complex, but they will definitely use a Graph data structure.

Files Provided

Below is a list of the files provided for this assignment. You should not modify any of the files except for MapEngine.java (where you will implement the logic for the commands), MainTest.java (where you can add your own test cases if you wish), and Utils.java (where you can add more methods but cannot change existing ones).

maven wrapper (mvnw for Unix/Mac OS or mvnw.cmd for Windows)

This file will allow you to build and run this assignment. We will use a Maven wrapper to guarantee that we all have a common configuration to run and test the assignment. This is how your project will be marked. There are three main Maven commands relevant to this assignment:

• compile (./mvnw compile for Unix/Mac OS or .\mvnw.cmd compile for Windows) Compiles the Java classes (will only compile the Java source files that have changed from the previous build). To make sure your code is compiling correctly, you should see a BUILD SUCCESS output. However, note that at the very beginning you will see a BUILD FAILURE output (more information below).

  

• test (./mvnw test for Unix/Mac OS or .\mvnw.cmd test for Windows) Compiles the Java classes and runs the test cases (will only compile the files that have changed from the previous build). You should see a BUILD SUCCESS output if the code compiles and all the tests pass. If the code doesn’t compile, or if any of the tests fail, you will see a BUILD FAILURE output.

• clean (./mvnw clean for Unix/Mac OS or .\mvnw.cmd clean for Windows) Removes the Java binary files (*.class) by clearing the target directory into which Maven normally builds your project. Running clean periodically is useful, for example to remove those .class files referring to deleted or renamed Java source files.

You can append commands together. For example, ./mvnw clean test for Unix/Mac OS or .\mvnw.cmd clean test for Windows will execute the clean command followed by the test command. This is generally a good idea, as a clean will remove any old compiled files that may be causing problems, and you can feel more reassured that the tests are running on a clean slate.

For more information about Maven, visit the related page about development environment.

Note: The first time you run the wrapper, it might take some time (a couple of minutes) to download the required libraries and dependencies. This is normal. Subsequent runs will be much faster.

src/main/java/nz/ac/auckland/se281/Main.java

This class implements the command line interface (CLI).

You should not modify this class.

src/main/java/nz/ac/auckland/se281/MessageCli.java

This class declares most of the system messages.

You should not modify this class, but you are encouraged to use it.

You are encouraged to refer to these messages in your code, as it will help you avoid spelling and formatting issues that might otherwise cause you to fail test cases.

There are two ways to use these messages in your code:

• Get the message so that you can print it yourself by calling the getMessage() method, or
• Request the message to be printed directly by calling the printMessage() method.

You will notice that most of the messages have %s placeholders. For example, consider the definition of the ROUTE_INFO message:

public enum MessageCli {
  // ...
  ROUTE_INFO("The fastest route is: %s"),
  // ...
}

This message expects you to pass an argument to getMessage() or printMessage(). For example, to construct the message "The fastest route is: [India, Siam, China]", you would do:

String message = MessageCli.ROUTE_INFO.getMessage("[India, Siam, China]");  // get the message
System.out.println(message);  // print it yourself

Or, you can print the message directly:

MessageCli.ROUTE_INFO.printMessage("[India, Siam, China]");  // print the message directly

Be sure to understand how this works, as it will be very useful and make your job easier. You should already be familiar with this concept from how printf() works in C.

src/main/java/nz/ac/auckland/se281/MapEngine.java

This class declares the methods invoked by the command line interface (Main.java). This is where you need to start your coding.

You must NOT change the signature of the existing methods in this class (such as method names, parameters, and return types).

You can (and should) add instance fields and new methods of your own (but cannot add static fields, here or anywhere else).

You should not create constructors in the MapEngine class, as they will not be used by the command line or test cases. The only constructor you can use is the default constructor public MapEngine() { ... } that takes no arguments.

src/main/java/nz/ac/auckland/se281/Utils.java

This class contains helper methods and objects useful for completing the assignment. Like in A2, you need to use the Utils.scanner to read from the console.

src/test/java/nz/ac/auckland/se281/CliTest.java

This is the custom testing framework we created to allow system-level testing of your assignment. You cannot change this class.

src/test/java/nz/ac/auckland/se281/MainTest.java

This file contains the test cases for this assignment. These test cases ensure that you have implemented most of the assignment correctly.

Making sure that your program passes all of the provided tests will not guarantee full marks for the assignment, but it will ensure you receive at least half of the marks for the parts that work according to those tests. We have only provided half of the test cases that will be used for marking. Note that the test cases we will use for marking will use slightly different inputs to ensure you are not hardcoding expected outputs.

Since we want to give you the freedom to design the system following the object-oriented concepts learned in class, these are not traditional JUnit test cases. The tests do not directly invoke the code (as we do not know how you are going to implement it, which classes and methods you will create, etc.). Instead, they test the system from the command line interface, simulating a user typing commands and observing the results shown on the screen.

Writing your own tests or extending the provided ones is strongly recommended.

You can easily write a test using the helper methods runCommands(), assertContains(), and assertDoesNotContain() (which are implemented by us—they are not standard JUnit).

First, with runCommands(), you specify the commands (or inputs) to be executed (separated by a comma). Then, with assertContains(), you specify the text you expect to see on the console after executing all the commands. For example, this test case checks that two new profiles are correctly created and added into the system:

While you can add as many tests as you want, we will not consider them when marking your assignment. Your code must still work with the original version of the MainTest.java file, where we will reuse the initial test cases and add new ones not visible to you.

src/main/resources/countries.csv

This Comma Separated Values (CSV) file contains the list of 42 countries: unique name, continent, and cross-border tax.

Afghanistan,Asia,1
Alaska,North America,1
Alberta,North America,2
Argentina,South America,1
....

CSV is a standard format where commas separate items in the list. You can imagine this like a table in Microsoft Excel, where commas separate columns.

The starter code for A3 reads the information of the countries from this file.

YOU CANNOT CHANGE THIS FILE, IF YOU DO THAT YOUR RESULTS WILL BE DIFFERENT FROM THE RESULT EXPECTED BY THE TEST CASES

src/main/resources/adjacencies.csv

This Comma Separated Values (CSV) file contains information about adjacent countries for each of the 42 countries.

Afghanistan,Ukraine,Ural,China,India,Middle East
Alaska,Alberta,Northwest Territory,Kamchatka
Alberta,Alaska,Northwest Territory,Ontario,Western United States
Argentina,Peru,Brazil
Brazil,Venezuela,North Africa,Argentina,Peru

For each line, the first column is the unique name of the country (node in the Graph), and the remaining columns are the nodes that should have an edge with that country.

For example,

Argentina,Peru,Brazil

means that the node representing Argentina has two edges: one to Peru and one to Brazil. Indeed, Argentina has only two neighboring countries in the Risk map.

The starter code for A3 reads the border information from this file.

IMPORTANT The adjacencies.csv file already contains DOUBLE edges. For example,

Alaska,Alberta,Northwest Territory,Kamchatka
Alberta,Alaska,Northwest Territory,Ontario,Western United States

There is an edge from Alaska to Alberta, and another one from Alberta to Alaska. As such, you don’t need to add double edges like we did in class.

  public void addEdge(T node1, T node2) {
    adjacencyMap.get(node1).add(node2);
    adjacencyMap.get(node2).add(node1); // YOU DON'T NEED TO DO ALSO THIS
  }

Otherwise you will have the same edges twice and you might get wrong results.

YOU CANNOT CHANGE THIS FILE, IF YOU DO THAT YOUR RESULTS WILL BE DIFFERENT FROM THE RESULT EXPECTED BY THE TEST CASES

Note: We also provide additional “hidden” files (those starting with “.”). You would need to change the folder options to be able to see them. We provide a .gitignore file that specifies intentionally-untracked files that Git should ignore, and a .mvn folder containing the Maven wrapper. You should not change these files, and you should not delete them.

OOP Requirements

For this assignment, you should use the OOP concepts and data structures covered in class. You should create appropriate classes and objects, and we give you complete freedom on how to design the OO structure. You will decide how many and which Java classes to create. However, to ensure you are using the correct data structures, you are required to do the following:

Set<SOME_OBJECT> var = new HashSet<>();
or
Set<SOME_OBJECT> var = LinkedHashSet<>();

Queue<SOME_OBJECT> var = new LinkedList<>();

List<SOME_OBJECT> var = new LinkedList<>();
or
List<SOME_OBJECT> var = new ArrayList<>();

It goes without saying that just creating those data structures is not sufficient. Your code must make meaningful use of them if you want to earn the associated marks. Also, you need to pass a minimum number of test cases to get the OOP marks

The Commands

Before proceeding with the tasks, read the code provided to you and start to familiarise yourself with the command-line interface.

To run the application in VS Code in an interactive mode, run the Main class using the Maven wrapper through VS Code’s built-in terminal. If the terminal window is not open, you can open it by clicking on the Terminal menu, then New Terminal. Then type the following command:

./mvnw clean compile exec:java@run for Unix/Mac OS or .\mvnw.cmd clean compile exec:java@run for Windows

You should see the following output:

Now you can try some of the commands!

Try the HELP command to see the list of available commands

You can also try the EXIT command to exit the system:

281-map>exit
You closed the terminal. Goodbye.
[INFO] ------------------------------------------------------------------------
[INFO] BUILD SUCCESS
[INFO] ------------------------------------------------------------------------
[INFO] Total time:
[INFO] Finished at:
[INFO] ------------------------------------------------------------------------

Only the HELP and EXIT commands are implemented for you. You will need to implement the other two commands.

Tasks

To guide you through the assignment, we have divided it into two tasks

For each task, we provide a number of test cases (in MainTest.java) that you can use to test your code.

Task 1

Initial Test Results

As soon as you compile and run the tests, you will notice that all 6 test cases of Task 1 fail.

[INFO]
[ERROR] Tests run: 6, Failures: 6, Errors: 0, Skipped: 0
[INFO]
[INFO] ------------------------------------------------------------------------
[INFO] BUILD FAILURE
[INFO] ------------------------------------------------------------------------
[INFO] Total time:  5.747 s
[INFO] Finished at: 2024-05-16T23:06:01+12:00
[INFO] ------------------------------------------------------------------------

With the Maven Wrapper:

./mvnw clean compile test for Unix/Mac OS or .\mvnw.cmd clean compile test for Windows:

With the Test Runner for Java Extension in VS Code:

From the left side of VS Code, click on the Testing icon:

You will then see all the test cases. You might need to expand to see them all:

Hint: Look at the numbering of the test cases to guide you in the recommended order to tackle them. In this case, the first test case is T1_01_info_india().

The important message to read is:

[ERROR] T1_01_info_india(nz.ac.auckland.se281.MainTest$Task1)  Time elapsed: 0.113 s  <<< FAILURE!
java.lang.AssertionError:
The test is expecting the following output in the console, but it was not there:
        "India => continent: Asia, tax fees: 3"

This means that the test is expecting the output India => continent: Asia, tax fees: 3 to be printed in the console, but it was not there. This is because you have not implemented the logic for the INFO-COUNTRY command yet.

Task 1 will require you to implement the creation of the data structure(s) (e.g., Graph) that you need for running the commands.

In the constructor of MapEngine, we need to load the map data from the two files and create the data structures before we can run the commands.

  public MapEngine() {
    // add other code here if you want
    loadMap(); // keep this method invocation
  }

  /** Invoked one time only when constructing the MapEngine class. */
  private void loadMap() {
    List<String> countries = Utils.readCountries();
    List<String> adjacencies = Utils.readAdjacencies();
    // add code here to create your data structures
  }

• You need to complete the method loadMap(). Specifically, List<String> countries and List<String> adjacencies contain the contents of the respective files. The code to read the files is already implemented for you; you just need to parse the content of those lists and populate the data structure(s). Each entry of the list is a line in the file. You need to split the line with the comma (using the method String.split) and create the needed data structure(s).

• After you have done that, you can implement the INFO-COUNTRY command. The command takes zero arguments, but once it is executed, the program asks the user to provide the name of the country and prints the information of the country. For example,

281-map> info-country
Insert the name of the country:
Japan USER TYPED THIS
Japan => continent: Asia, tax fees: 5
281-map> info-country
Insert the name of the country:
China USER TYPED THIS
China => continent: Asia, tax fees: 2

You need to implement this in the method showInfoCountry().

  /** This method is invoked when the user runs the command info-country. */
  public void showInfoCountry() {
    // add code here
  }

More specifically, you need to print the related messages (see MessageCli.java), ask for the country name (you must use Utils.scanner). If the user inserts a country name that is misspelled or not present in the list of countries, you need to throw an exception. The calling method will catch it, show an error message, and ask for another name. Don’t do something like this:

try {
  throw new MyCoolException();
} catch (MyCoolException e) {
  // do something
}

Instead, do something like this:

try {
  method(...);
} catch (MyCoolException e) {
  // do something
}

public RETURN_TYPE method(...) {
  ...
  throw new MyCoolException();
  ...
}

Continue to ask for a new country name until the name of the country is valid.

281-map> info-country
Insert the name of the country:
hello world
ERROR! This country was not found: Hello World, try again!
ciao mondo
ERROR! This country was not found: Ciao Mondo, try again!
Japan
Japan => continent: Asia, tax fees: 5
281-map>

Note that country names are case-sensitive. However, if a user inputs a country name with a lowercase first letter, such as northwest territory, it should be automatically converted to Northwest Territory before accessing the data structure to ensure proper recognition.

For example, the following interactions would still work:

281-map> info-country
Insert the name of the country:
northwest territory
Northwest Territory => continent: North America, tax fees: 6
281-map> info-country
Insert the name of the country:
northwest Territory
Northwest Territory => continent: North America, tax fees: 6

Note that you capitilise only the first letter of each word (some country names are composed of multiple words) other letters will remain the same

For example, noRthwest territory will become NoRthwest Territory, which is an invalid name

281-map> info-country
Insert the name of the country:
noRthwest territory
ERROR! This country was not found: NoRthwest Territory, try again!

There is a method in Utils.java that will help you with that.

The info to print includes the name of the country, the continent, and the cross-border fees. See MessageCli for the required format. As always, you can use MessageCli to print the message MessageCli.COUNTRY_INFO.printMessage(countryName, continent, taxFee);

If all the test cases pass and you are confident that the program is correct, you can move to the next task.

Task 2

In Task 2, you need to implement the ROUTE command that shows the shortest path between two countries.

Go to the top of the MainTest.java file, and uncomment the following line:

@RunWith(Suite.class)
@SuiteClasses({
    MainTest.Task1.class,
    // MainTest.Task2.class, // <-- uncomment this line to get started on Task 2
})

You will see 14 new test cases, all of which are failing. Follow the same process as Task 1 to get them all passing, and carefully read the requirements below.

When the ROUTE command is invoked, the program should ask for two country names: the source and destination. (It is a good design to reuse the same code you implemented in Task 1 to ask for the country name.) When both country names are valid, the program will print the path from the source to the destination, also showing the ordered list of continents that will be visited (including the starting one) and the total cross-border taxes to pay. Note that if we start from country X, we don’t need to pay the taxes for country X as we are already there. For example:

APOLOGIES: there is a typo You will visit the following countries: should be You will visit the following continents:. It’s ok leave countries, sorry :(

281-map> ROUTE
Insert the name of the country where you start the journey:
Alberta
Insert the name of the country of destination:
Siam
The fastest route is: [Alberta, Alaska, Kamchatka, Mongolia, China, Siam]
You will visit the following countries: [North America, Asia]
You will spend this amount 26 for cross-border taxes

Note that it is possible to choose the same source and destination. This would be the output:

281-map> ROUTE
Insert the name of the country where you start the journey:
Congo
Insert the name of the country of destination:
Congo
No cross-border travel is required!
281-map>

If the user types an invalid country name, we need to re-ask for the country name until it is valid. If the user provides a valid first country name but an invalid second one, we only need to ask for the second one.

281-map> ROUTE
Insert the name of the country where you start the journey:
Japan
Insert the name of the country of destination:
Argent
ERROR! This country was not found: Argent, try again!
Argenti
ERROR! This country was not found: Argenti, try again!
Aregntina
ERROR! This country was not found: Aregntina, try again!
Argentina
The fastest route is: [Japan, Kamchatka, Alaska, Alberta, Western United States, Central America, Venezuela, Brazil, Argentina]
You will visit the following countries: [Asia, North America, South America]
You will spend this amount 27 for cross-border taxes

You need to implement this using BFS as we discussed in class because we want the shortest path in terms of the number of countries to cross. Note that there could be multiple paths with the same optimal length. To ensure that the test cases are checking for the one that you will find, the only thing you need to be aware of is that the adjacentMap of the Graph has to insert the list of adjacent nodes exactly as shown in the file.

For example, in the file adjacencies.csv, the Iceland line is:

Iceland,Greenland,Great Britain,Scandinavia

This means that the node that represents Iceland should have this adjacent list of nodes in this specific order: Greenland, Great Britain, Scandinavia.

If you do that, then BFS will traverse the nodes in the same order of what we expect, and you just need to output the FIRST shortest path that BFS finds. Note that in an unweighted graph (like this one), BFS traversal order guarantees finding a path (there could be more than one) with the shortest length.

You need to start the implementation from method showRoute() in MapEngine

  /** this method is invoked when the user run the command route. */
  public void showRoute() {}

Marking Scheme

Important Instructions

Please read the following information carefully before you begin your assignment.

@Test
public void testIsEven() {
  checkIfIsEven(2);
  assertContains("true");
}

public void checkIfIsEven(int number) {
  if (number == 2) {
    System.out.println("true");
  } else {
    System.out.println("false");
  }
}

@Test
public void testIsEven() {
  checkIfIsEven(280);
  assertContains("true");
}

email: "student@aucklanduni.ac.nz"
accessToken: "token-that-was-emailed-to-you"