Important note:

❼ In each section, the tasks are in increasing order of difficulty.  Manage your time so that you attempt both sections. You may wish to solve the easier tasks in both sections before moving on to the harder tasks

❼ It is critical that your solution compiles for automated testing to be effective.  Up to TEN MARKS will be deducted from solutions that do not compile (-5 marks per Section). Comment out any code that does not compile before you log out.

❼ You can use the terminal or an IDE like IDEA to compile and run your code.

Do not ask for help on how to use an IDE.

❼ Before your final commit/push, you must ensure that your source code is in the correct directory, otherwise your marks can suffer heavy penalties.  Only code in the original directories provided will be checked. Please make sure that your folder structure for each Section is:

~/javafinaltestpartX_username/ .git/

~/javafinaltestpartX_username/lib/

~/javafinaltestpartX_username/src/

~/javafinaltestpartX_username/test/

where X is “a” or “b” and username is your login.

❼ Before the 12:00 deadline, you will need to commit/push your code to GitLab and submit it via LabTS to CATe.  Code that is pushed to GitLab after the deadline will be capped at zero.

Useful commands

cd  ~/javafinaltestparta_username/

javac

-g

-d  out

-cp  " ./lib/*"

-sourcepath  src:test

src/**/* .java  test/**/* .java

java

-ea

-cp  " ./lib/*:out"

org .junit .runner .JUnitCore  aeroplane .Question#Tests

java

-ea

-cp  " ./lib/*:out"

aeroplane .TestSuiteRunner

cd  ~/javafinaltestpartb_username/

javac

-g

-d  out

-cp  " ./lib/*"

-sourcepath  src:test

src/**/* .java  test/**/* .java

java

-ea

-cp  " ./lib/*:out"

org .junit .runner .JUnitCore  alphatree .TestQuestion#

java

-ea

-cp  " ./lib/*:out"

alphatree .TestSuiteRunner

Section A

Problem Description

Your job is to write a program that will allocate seats on an aeroplane.  The aeroplane has 50 rows, numbered 1–50.  Each row has six seats, labelled ‘A’- ‘F’ . Row 1 is reserved for crew. Rows 2– 15 are reserved for business class passengers. The remaining rows are for economy class passengers. Emergency exits are located at rows 1, 10 and 30. We consider the aeroplane seats to be ordered as follows:  1A, 1B, . . . , 1F, 2A, 2B, . . . , 2F, etc.  The first and last seats are 1A and 50F, respectively.  In the instructions below, the specific ranges 1–50 and ‘A’- ‘F’ are used for rows and seat letters. However, your solution should be designed so that minimal code modifications would be required to change the number of rows and seats per row, which rows are reserved for which types of passengers, and which rows are emergency exit rows.  You can assume that each reserved section will always be a contiguous sequence of rows.

Getting Started

The skeleton files are located in the aeroplane package.  This is located in your Lexis home directory at:

❼ ~/javafinaltestparta username/src/aeroplane

You are provided with the following files:

❼ Seat .java: a skeleton class that you will fill out to represent an aeroplane seat

❼ Passenger .java: a skeleton class that you will fill out and subclass to represent different

types of aeroplane passenger

❼ SeatAllocator .java: an incomplete class which you will complete to represent and per-

form the allocation of passengers to seats

❼ Luxury .java:  an enumeration representing various luxuries to which business class pas-

sengers are entitled (do not modify this file)

❼ AllocationNotPossibleException.java:  a checked exception used to handle the case

where it is not possible to allocate a seat to a passenger (do not modify this file)

❼ MalformedDataException.java: a checked exception used to handle badly formed input

data (do not modify this file)

You may feel free to add additional methods and classes, beyond those specified in the in- structions, as you see fit, e.g. in order to follow good object-oriented principles, and for testing purposes. Any new Java files should be placed in the aeroplane package.

Testing

You are provided with a set of test classes under:

❼ ~/javafinaltestparta username/test/aeroplane

There is a test class QuestioniTests .java for each question i. These contain initially commented- out JUnit tests to help you gauge your progress during Section A. As you progress through

❼ All passengers should have an instance method, bool  isAdult(), that returns true

if and only if the passenger is at least 18 years of age.  You should assume that all crew are adults.

❼ Business class passengers should have an associated luxury. This can be either cham-

pagne, truffles or strawberries, and should be represented using the Luxury enumer- ation with which you are provided.

❼ The string representation of a passenger should consist of the passenger’s type (crew,

business class or economy class), followed by details of the fields associated with the passenger. The unit tests for Question2 dictate constraints on the precise format this

string should take: study these tests and ensure that your solution passes them all. Test your solution using (at least) the tests in Question2Tests.

[16 marks]

3.  Equality on Seats.  Further edit the Seat class so that two Seat objects are regarded as equal if and only if they have identical fields.  Test your solution using (at least) the tests in Question3Tests.

[5 marks]

4.  Allocating seats.  Look at the skeleton class SeatAllocator, which represents an al- location of seats to passengers.   SeatAllocator has a single field,  allocation, which maps seats to passengers. If a seat is not mapped to any passenger, the seat is free. The toString() method of SeatAllocator provides details of allocated seats in seat order, based on the toString() methods of Seat and the Passenger class hierarchy.

SeatAllocator provides an instance method, void  allocate(String  filename), whose job is to read passenger details from the specified input file and allocate seats for these passengers. The functionality for seat allocation is missing: it is your job to complete this functionality.

❼ A stub instance method, allocateInRange( . . .), is provided. Fill out this method

so that it allocates the given passenger to the first suitable seat in the range first– last (inclusive). A seat is suitable for a passenger if a) the seat is free, and b) if the seat is in an emergency row then the passenger is an adult.  If there is no suitable seat, the method should throw an AllocationNotPossibleException.

❼ Look at the incomplete methods allocateCrew( . . .), allocateBusiness( . . .) and

allocateEconomy( . . .). These methods read passenger fields from a buffered reader object. Complete each of these methods by a) using the fields which have been read to construct an appropriate passenger object, and b) calling allocateInRange with

this passenger object and an appropriate range of seats.

Test your solution using (at least) the tests in Question4Tests.

[15 marks]

5.  Counting adults. In class SeatAllocator, write a static method, int  countAdults( . . .), that takes a set of passengers and returns the number of adults in the set.  It should be   possible to call the method with any set of passenger objects, not just with a set of the   form Set<Passenger>. Test your solution using (at least) the tests in Question5Tests.

[4 marks]

Total for Section A: 50 marks

Section B

Problem Description

This question is about a word guessing game we will call bangman.  Your opponent randomly chooses a secret word, consisting of n lowercase characters, from a given dictionary and they tell you its length. Your goal is to guess the secret word in the minimum number of turns. Each turn you can send the opponent a message:

1. You can send the message ask(xs) to ask if the secret is a given string xs.

2. You can send the message ask(i,  xs) to ask if the letter at index i in the secret is any letter in a given string xs, where 0 s i < n.

Your opponent will either answer true or false. The game is finished when the answer to your guess ask(xs) is true, since it is the same word as the secret.

For example, your opponent could choose the word  "imperial", and your play might be as follows:

1.  ask(0,  "aeiou")  =  true

2.  ask(0,  "ae")  =  false

3.  ask(0,  "i")  =  true

4.  ask(3,  "abcdefghijkl")  =  false

5.  ask(3,  "mnopqrs")  =  true

6.  ask(3,  "m")  =  true

7.  ask("imperium")  =  false

8.  ask("imperial")  =  true

The game has ended after 8 turns because you have guessed the correct word.   This was a remarkably short game, and it would usually take many more guesses to finish the game.

If you like, you can even play this game on the command line, though it is not recommend you spend too much time on it right now, exciting as it is.  To help you cheat, the game has been set so that it actually tells you the secret as a hint.

Your task is to write some code that will help a program to play this game for you by imple- menting the algorithm described below. The algorithm does not implement an optimal strategy, but performs relatively well.

The overall strategy will be to guess letters that occur with high frequency first. The frequency of a letter is calculated by counting the number of occurrences of each letter in the whole dictionary.  Each letter in the secret is guessed in turn by guessing a string where the sum of its letter frequencies is high.  This allows the secret character to be narrowed down with each guess until a single letter remains. Then, the next letter is guessed using the same frequencies. When all the letters have been guessed, the word is known.

To build the strategy that works with frequencies, a binary tree called an AlphaTree is con- structed. For instance, here is the AlphaTree for the characters in “abcbdecc”:

{a,b,c,d,e}, 8

{b,e}, 3             {a,c,d}, 5

{e}, 1    {b}, 2  {a,d}, 2  {c}, 3

{a}, 1    {d}, 1

Notice that the nodes of the tree consist of a set of letters together with an integer that contains the sum of their frequencies.  Also note that each parent node is formed from two children by

taking the union of their letters and the sum of their frequencies.

The tree  building algorithm to build such a tree is as follows:

1.  The dictionary is used to construct an AlphaFreq structure, which contains a mapping from each alphabetical character to its frequency.

2. Each letter and its associated frequency in the AlphaFreq is used to construct a new singleton AlphaTree that is added to a priority queue of type AlphaTreeQueue.   The queue is ordered so that the trees with least frequency are extracted first.  If two trees have the same frequencies, the one most recently added is first.

3. While the queue contains more than one tree, the first two trees are removed from the queue and a new parent is created with them as children, and is added into the queue.

4. When the queue contains exactly one tree, this is returned as the desired frequency tree.

Testing

You can play a game of bangman by executing the bangman .Bangman class.  This is an inter- active game you can play in the console.  You will also see various bots implemented in the bangman .player package, such as PlayerCheat, PlayerBruteAlpha, and PlayerBruteFreq. The PlayerBruteFreq class makes use of the classes you need to implement.

You are furthermore provided with a set of test classes under:

❼ ~/javafinaltestpartb_username/test/alphatree

There is a test class TestQuestioni .java where i corresponds to questions 1, 2, 3, and 4.

These tests are not exhaustive and are merely intended to guide you. You should think carefully about whether your solution is complete, even if you pass all of the given tests.

Overview

The skeleton files are provided in the bangman package and the alphatree package. These are located at:

❼ ~/javainterimtestpartb_username/src/bangman

❼ ~/javainterimtestpartb_username/src/alphatree

You may only modify the following files, or those you create yourself:

❼ alphatree/AlphaFreq .java, where you will implement a class that associates frequencies

to the letters of the alphabet.

❼ alphatree/AlphaTree .java, where you will implement a class that represents binary

trees whose nodes contain sets of characters and their frequencies.

❼ alphatree/AlphaTreeQueue.java, where you will implement a class that stores a priority

queue of trees.

❼ alphatree/Utils .java, where you will implement the tree building algorithm.

You must not change type signatures of existing methods or constructors of these classes. You may add any attributes and methods as desired, as well as any new classes you may require.

Tasks

1. Implement the AlphaTree class

The AlphaTree class represents trees that store sets of characters and their frequencies in nodes. You may implement this class using any collection types from java .util. You will have to implement:

❼ AlphaTree( . . .): constructors for empty, singleton, and binary nodes. ❼ isEmpty(): return true only when the tree is empty.

❼ isSingleton(): return true only when the tree contains one node.

❼ left() and right(): return the left and right subtree if they exist, otherwise null. ❼ chars(): return the set of characters in the current node.

❼ freq(): return the frequency of the current node.

[10 marks]

2. Implement the AlphaFreq class

The AlphaFreq class is a structure that associates a frequency to each of the 26 (lowercase) characters, one for each of the letters in the alphabet. You must implement this from first principles where any new attributes you define must not be collections from java .util. You will have to implement:

❼ AlphaFreq(): constructs a structure where the frequency of every letter is 0.

❼ AlphaFreq(List<Character>  cs):  constructs a structure where the frequency of

every letter is the number of occurrences it has in the given list cs.

❼ isEmpty(): return true only when the frequencies for all the characters are 0. ❼ size(): return the sum of all the frequencies.

❼ get(char  c): return the frequency corresponding to the character c.

❼ add(char  c): increment the frequency corresponding to the character c. ❼ reset(): reset the frequencies of all characters to 0.

Note that not all values of type char are lowercase alphabetical letters, and these methods should be well defined even for bad input.

[10 marks]