2020/10/11 Assignment 5 - Courses/COMP103_2020T2 |
https://ecs.wgtn.ac.nz/Courses/COMP103_2020T2/Assignment5 1/6 School of Engineering and Computer Science TeKuraMātaiPūkaha,Pūrorohiko COMP103 2020 Tri 2 Assignment 5: Goals
This assignment is about general tree structures, graphs, and recursive algorithms
Resources and links
Download Zip file of necessary code and data.
Getting online help
Submit your answers
Marks and feedback
Demo Videos for CPNCalculator, BusNetwork, Permutations, MazeSearch
ToHand In You are to submit electronic versions by 23 Oct 10 am
You should submit an electronic copy of
CPNCalculator.java
BusNetworks.java (and Towns.java if you modified it)
Permutations.java
MazeSearch.java
Submissions made after solutions have been handed out will not be marked. If you haven't finished at the deadline, submit whatever you
have done.
Part1: CPNCalculator(Weight: 4%)
The lectures demonstrated a program for a simple calculator that would read and evaluate expressions converted into a binary tree,
where each operator (+, -, *, /) had exactly two operands.
For this program, you are to complete a more complex calculator that has a wider range of operators, and also allows some of the
operators to have more than two operands (the values that the operator is applied to). It uses "Cambridge Polish Notation" which means
that it puts the operator before the operands and puts round brackets around every operator and its operands. For example, 6+3+5 is
written ( + 6 3 5 ).
Expressions can be nested; for example, the expression ( * ( + 4 8 3 7 2 ) 7 ( / 20 2 5 ) 18 ) is a multiplication operator
applied to four operands; the first operand is the sum of 4, 8, 3, 7 and 2; the second operand is 7; the third operand is 20 divided by 2 then
divided by 5, and the fourth operand is 18. The value of ( * ( + 4 8 3 7 2 ) 7 ( / 20 2 5 ) 18 ), should be 6048 (which is
24 * 7 * 2 * 18).
The operators that the calculator should know about are:
+ , which adds up all its operands.
- , which subtracts from the first operand all the remaining operands.
* , which multiplies all its operands.
/ , which divides the first operand by all the remaining operands.
^ , which has two arguments, and computes the first to the power of the second. eg, ( ^ 2 3 ) would compute 2 to the power of 3,
which is 8.
sqrt , which computes the square root of its (one) operand
log and ln , which compute the log to base 10 and the natural log (base e) of the operand. If log has two operands, it computes the
log of the first operand to base of the second operand.
sin , cos , and tan , which compute the standard trigonometric functions.
2020/10/11 Assignment 5 - Courses/COMP103_2020T2 | ECS | Victoria University of Wellington
https://ecs.wgtn.ac.nz/Courses/COMP103_2020T2/Assignment5 2/6
dist , which either has four operands (x1, y1, x2, y2) and computes the euclidean distance between the points (x1,y1) and (x2,y2), or
it has six operands (x1, y1, z1, x2, y2, z2) and computes the euclidean distance between the points (x1,y1,z1) and (x2,y2,z2)
avg , which computes the average of all its arguments (any number of them, but at least one).
The calculator should also know about two constants:
PI , which has the value Math.PI (3.14159...)
E , which has the value Math.E (2.71828..., the base of natural logarithms)
Some of the calculator program is written for you:
The GUI set up,
The top level REPL structure (a Read Evaluate, Print Loop that reads an expression, evaluates it, and prints it out).
A method that reads an expression from the user and turns it into a general tree where the leaves have numbers (or constants), and
the internal nodes have an operator and a list of child nodes that the operator is applied to.
You have to complete the evaluate method which evaluates an expression tree.
Core:
Make the calculator work on expressions with the operators + , - , * , and / , and the constants PI and E . You should test your code on a range of expressions. You can also run some automated tests from the test-core.txt file (using the
Set input option in the menu). This will enter 7 expressions for you (though you will need to enter a first expression manually). The
expected output is given at the end of the assignment.
Completion
Extend your evaluate method:
Handle the other operators above. You will find methods in the Math class to be useful.
Check for unknown operators - if an expression has an invalid operator, evaluate should report the error (eg, The operator $ is
invalid) and return the special double value Double.NaN .
Check that an operator has a valid number of operands; if not report the errors, and return Double.NaN
The arithmetic operators and avg allow any number of operands above 0. eg ( + 5 ) is OK and means just 5;
dist must have four or six operands
log must have one or two operands
The other operators have a fixed number of arguments.
You can run some automated tests from the test.txt file (using the Set Input option in the menu). This will enter 19 expressions for
you (though you will need to enter a first expression manually). The expected output is given at the end of the assignment.
Challenge
Extend readExpr :
Check for empty brackets (ie ( ) ). Report the error and return the null tree.
Check for an invalid expression that has brackets that don't match,
Add a printExpr method that will print the expression using normal infix for + , - , * , and /^ , using brackets only when necessary,
and using normal brackets notation for the other functions. For example
( + 7 6 ( * 5 4 ) ( * 3 2 1 ) ( ^ 2 5 ) ) prints as 7+6+5*4+3*2*1+2^5
( * 7 6 ( + 5 4 ) ( + 3 ( 2 5 ) 1 ) ) prints as 7*6*(5+4)*(3+2^5+1)
( + 3 ( sin ( + 4 ( * 5 PI ) ) ) ( ln 6 ) ) prints as 3+sin(4+5*PI)+ln(6)
Part 2: BusNetworks (4%)
For this question, you are to complete the BusNetworks program for analysing a proposed network of long-distance buses. The network
consists of nodes for each of the towns in the region and links between pairs of towns that have a direct bus service.
The program reads data about the network from a file. The first line of the file has a list of the names of the towns in the region. Each
remaining line has two names which are towns with a direct bus service between them.
For example, the file "data-small.txt" file has just 7 towns and six direct bus services:
2020/10/11 Assignment 5 - Courses/COMP103_2020T2 | ECS | Victoria University of Wellington
https://ecs.wgtn.ac.nz/Courses/COMP103_2020T2/Assignment5 3/6
Auckland Hamilton Napier NewPlymouth PalmerstonNorth Wellington Whanganui
Auckland Hamilton
Hamilton Napier
Hamilton PalmerstonNorth
NewPlymouth Whanganui
Napier PalmerstonNorth
PalmerstonNorth Wellington
The loadNetwork method is given the name of a file, and should read the data in the file, and construct a graph of the towns and their
connections.
The Town class (written for you) describes the nodes of the graph, with the name of the town and its set of neighbours (towns it has a
direct bus service to).
The busNetwork field should co300527291ntain a map of all the towns in the network. The keys should be the names of the towns,
and the values should be the Town objects. Note that the towns in the network may or may not be all connected.
The printNetwork method should print out the network by printing one line for each town in the network, giving the name of the town,
followed by its neighbours. Note, printNetwork does not need to traverse the graph - it can just use the set of towns in busNetwork . For
example, for the "data-small.txt" file, it should print
The current network:
====================
Auckland-> Hamilton
Hamilton-> Auckland PalmerstonNorth Napier
Napier-> PalmerstonNorth Hamilton
NewPlymouth-> Whanganui
PalmerstonNorth-> Wellington Hamilton Napier
Wellington-> PalmerstonNorth
Whanganui-> NewPlymouth
The printReachable method is passed the name of a town and should print out all the other towns that can be reached from this town via
the network. It must use the findAllConnected method to find all the Towns connected to a particular Town.
The printConnectedGroups method should find all the connected sets of towns, and print each set on a separate line. It will use the
findAllConnected method to find all the towns connected to a particular town.
For example, for the "data-small.txt" file, there are two connected sets of towns that aren't connected to each other, so it should print:
Connected Towns
===============
Group 1: Auckland Hamilton PalmerstonNorth Wellington Napier
Group 2: NewPlymouth Whanganui
Core
Complete the loadNetwork and printNetwork methods
Completion
Complete the findAllConnected , printReachable , and printConnectedGroups methods. You will need to construct a recursive
"helper" method for the findAllConnected method.
Challenge
Display the network of towns graphically.
(The file data-with-lat-long.txt contains the same network data as the data-big.txt , but in a different format (eg, it starts with
the number of towns, followed by a line for each town and location), and with latitude/longitude information as well. You will find this
useful.)
Ideally, it should should let the user click on a town and highlight the part of the network (towns and links) that can be reached from
that town.
Part 3: Permutations (3%)
Part 3 involves a program to generate all possible permutations (possible orderings) of a collection of items. This is somewhat related to
the program in the lectures that generated all combinations, and is most easily solved using a recursive algorithm.
The program obtains a collection of Strings from the user, and then finds all possible permutations of those items.
The A B C D E button is useful for initial testing, and constructs a collection of 5 strings: "A", "B", "C", "D", and "E". The Letters textfield
will take a series of letters (with or without spaces) and construct a collection of one-letter strings. The Words textfield lets you enter a
series of words, separated by spaces; the collection will have one String for each word.
2020/10/11 Assignment 5 - Courses/COMP103_2020T2 | ECS | Victoria University of Wellington
https://ecs.wgtn.ac.nz/Courses/COMP103_2020T2/Assignment5 4/6
The findPermutations method should construct and return a list of all the permutations. The version in the template sets up a list for the
answer, creates a modifiable copy of the collection of Strings, and calls the extendPermutation method, which is a recursive method that
builds up the possible permutations. You do not have to follow this pattern, but you must use a recursive algorithm to construct the
permutations.
extendPermutation is passed a Set of remaining Strings that it can use to extend the permutation, a Stack of the Strings in the
permutation built so far, and a List of all the permuations found so far. The comments on the method outline the suggested algorithm.
There are several methods in the Template to set up the GUI, get a list of Strings from the user, and to print out the answer.
Note: finding all permutations of large lists takes a lot of time, and the answer list may be too large to fit in memory or to print on the
screen! Find out how large you can get. You may need to stop recording the permutations in the answer after the first 10,000 permutations
or so.
How large a collection can your code work through in 5 minutes (assuming it doesn't try to store more than 10,000 of them)? If you made
the collection larger by three Strings, how long would it take?
Part 4: Maze Search (4%)
The MazeSearch program creates mazes and then finds a path through the maze from any point the user clicks on to the goal square
(shown in green). The part of the program that creates the maze is written for you. It creates a graph of MazeCell s. Each MazeCell
represents one square of the maze, and contains a collection of the neighbour MazeCell s that are connected to it. You are to write the
methods that search for paths through the graph of MazeCell s to the goal MazeCell . Core
Complete the exploreFromCell method which searches for a path from a given cell to the goal. As long as it hasn't visited the cell before,
it should start by visiting the cell (using the cell.visit() method), colouring it yellow (using the cell.draw(Color.yellow) method), and
pausing for a brief delay. It should then keep exploring from each of the neighbours. If it succeeds in finding a path through any of its
neighbours, it should return true . If it cannot find a path through any of its neighbours, it should colour the cell red, and return false , to
indicate that the cell was on a dead-end and it failed to find a path to the goal.
Your method should use a recursive depth-first search, but because the maze is a graph rather than a tree, it needs to mark each cell it
goes to so that it can check that it does not visit it again later. Because you are only looking for one path, you don't need to "unvisit" the
cells - just turning them red to indicate they were a dead end is enough.
The left hand image below shows a maze of size 10, where the user clicked in the top-left cell, and the program found a path to the goal.
The yellow cells are the cells on the path, the blue cell is the goal, and the red cells are the cells that were on dead-end parts of the
search.
Note that the search didn't find the shortest path (shown in the right hand image) - finding the shortest path is for the challenge.
Find a Path Find Shortest Path
Completion
Complete the exploreFromCellAll method which searches for all paths from the given cell to the goal. It should colour cells yellow (and
pause briefly) as it visits them, but it should also unvisit them and colour them white after it has finished exploring the neighbours
(successful or not). (This is so it can use the cell again in a different path).
Whenever it reaches the goal MazeCell, it should pause for 1000 milliseconds. (It may help to colour it blue before pausing and then
colour it green again after pausing, just to highlight the fact that it found a path.) It should never try to explore past the goal cell.
2020/10/11 Assignment 5 - Courses/COMP103_2020T2 | ECS | Victoria University of Wellington
https://ecs.wgtn.ac.nz/Courses/COMP103_2020T2/Assignment5 5/6 Challenge
Complete the exploreFromCellShortest method which searches for the shortest path from the given cell to goal. It should not color the
cells while it is searching. Instead, once it gets to the goal, it should colour all the cells on the path that got to the goal. To do this, it must
have some way of recording the paths as it builds them, eg by recording the cell it came from every time it gets to a new cell.
The right hand image above shows the shortest path from the top left corner. Appendix. Sample outputfor CPNCalculator on the test-core.txtfile:
expr: 20
-> 20.0
expr: ( + 7 6 ( * 5 4 ) ( * 3 2 1 ) )
-> 39.0
expr: ( * 7 6 ( + 5 4 ) ( + 3 2 1 ) )
-> 2268.0
expr: ( - ( * 2 4 ) ( / 2 4 ) )
-> 7.5
expr: ( - 24 2 3 4 )
-> 15.0
expr: ( / 24 2 3 4 )
-> 1.0
expr: ( * 2 PI 10 )
-> 62.83185307179586
Sample outputfor CPNCalculator on the test.txtfile:
2020/10/11 Assignment 5 - Courses/COMP103_2020T2 | ECS | Victoria University of Wellington
https://ecs.wgtn.ac.nz/Courses/COMP103_2020T2/Assignment5 6/6
expr: ( + 50 ( log ( * 125 8 ) ) )
-> 53.0
expr: ( ^ 2.718282 ( ln 20 ) )
-> 20.00000378099725
expr: ( ^ ( ^ 2 5 ) 2 )
-> 1024.0
expr: ( ^ 10 ( log 38 ) )
-> 37.99999999999999
expr: ( + ( sin ( / 3.14159 3 2 ) ) ( cos ( / 3.14159 3 ) ) ( tan ( / 3.14159 4 ) ) )
-> 1.9999990562184347
expr: ( dist 0 0 3 4 )
-> 5.0
expr: ( dist 0 0 0 3 4 12 )
-> 13.0
expr: ( avg 1 2 3 4 5 6 7 8 9 10 )
-> 5.5
expr: ( + 3 ( sin ( / PI 6 ) ) ( log ( * 125 8 ) ) )
-> 6.5
expr: ( ^ E ( ln 20 ) )
-> 19.999999999999993
expr: ( + ( sin ( / PI 3 2 ) ) ( cos ( / PI 3 ) ) ( tan ( / PI 4 ) ) )
-> 2.0
expr: ( log 64 4 )
-> 3.0
expr: ( The remaining examples should all be errors )
The is not a valid operator.
-> NaN
expr: ( + 1 2 3 4
Missing closing bracket
-> NaN
expr: ( log 64 2 2 )
Too many operands for log
-> NaN
expr: ( dist 1 2 3 )
Wrong operands for dist
-> NaN
expr: ( dist 1 2 3 4 5 )
Wrong operands for dist
-> NaN
expr: ( dist 1 2 3 4 5 6 7 )
Wrong operands for dist
-> NaN
expr: ( power 5 7 )
power is not a valid operator.
-> NaN