Part A Re-exam solutions

Here are the questions for the TIN213 Part A re-exam on 2020-08-21, together with links to solutions. There were two versions of each question, and each student received one of the two versions at random.

1a. Median Word Length

The median word length of a string s is the median value of the list obtained by taking the number of letters in each word in s. For example, the median word length of the string "Sam I am" is 2, because:

it contains the words “Sam”, “I” and “am”, which have three, one, and two letters respectively;
the list of word lengths for this sentence is therefore {3, 1, 2}; and
the median value of the list {3, 1, 2} is 2.

Recall that the median value of a list of numbers is computed by ordering the list in ascending (or descending) order. Then, depending on the number of elements in the list:

If the list contains an odd number of elements, the median is the middle element of the list. For instance, in the list {2, 3, 5, 7, 11}, the median is 5.
If the list contains an even number of elements, the median is the mean (average) of the two middle elements of the list. For instance, in the list {2, 3, 5, 7, 11, 13}, the median is (5 + 7)/2 = 12/2 = 6.

Your task: write a method

double medianWordLength(String words)

which, given a string "words", prints the median word length of the string.

You may assume that the string "words" contains one or more words separated by spaces. For example, the line "one hamburger with fries" contains four words. (In particular, you may assume that the string is non-empty.) For the purposes of this question, a word is any sequence of letters (capital or lower case) from the English alphabet of length > 0.

Hint: you may find it useful to use the methods of the String (Links to an external site.) class in the standard library. especially split() and length(), as well as the method Arrays.sort() (Links to an external site.).

Solution: MedianWord.java

1b. Median line length

The median line length of a string s is the median value of the list obtained by taking the number of letters in each line in s. For example, the median word length of the string

I am Sam,
Sam I am,
Would you like green eggs and ham?

is 9, because:

it has three lines which have length 9, 9 and 34;
the list of word lengths for this sentence is therefore {9, 9, 34}; and
the median value of the list {9, 9, 34} is 9.

Recall that the median value of a list of numbers is computed by ordering the list in ascending (or descending) order. Then, depending on the number of elements in the list:

If the list contains an odd number of elements, the median is the middle element of the list. For instance, in the list {2, 3, 5, 7, 11}, the median is 5.
If the list contains an even number of elements, the median is the mean (average) of the two middle elements of the list. For instance, in the list {2, 3, 5, 7, 11, 13}, the median is (5 + 7)/2 = 12/2 = 6.

Your task: write a method

double medianLineLength(String lines)

which, given a string "words", prints the median word length of the string.

You may assume that the string "lines" contains one or more lines separated by the newline character '\n'. (In particular, you may assume that the string is non-empty.)

Hint: you may find it useful to use the methods of the String (Links to an external site.) class in the standard library. especially split() and length(), as well as the method Arrays.sort() (Links to an external site.).

Solution: MedianLine.java

2a.

The game Tic Tac Toe (Tre-i-rad) is played on a 3x3 grid of squares, where two players take turns marking the squares with Xs (for the first player) and Os (for the second player). The first player to mark three squares in a row with their symbol wins the game. Marked squares may not be overwritten, so the game ends in a draw if all squares should become filled before any player can line up three marks. Here is a finished game of Tic Tac Toe where player 2 has won.

(Image: Symode09 / Wikimedia Commons / Public Domain)

Your task: write a class TicTacToe which models the Tic Tac Toe game. The class must keep track of the state of the game board (i.e. which player owns which squares), whether the game has ended in victory for some player, if it’s a draw, or if the game is still on, and which player will make the next move.

The class must have the following methods and constructors:

A parameterless constructor public TicTacToe() which initializes the game with an empty 3x3 board and sets player 1 as the next player to take a turn.
public boolean isOver(), which returns true if the game is over (i.e. either player has won, or there are no more free squares), or false if the game is still on.
public int getWinner(), which returns 1 if player 1 has won the game, 2 if player 2 has won, and 0 if the game has ended in a draw. If the game is not yet over, an IllegalStateException must be thrown.
public int getNextPlayer(), which returns 1 if it’s player 1’s turn, or 2 if it’s player 2’s turn. If the game is over, an IllegalStateException must be thrown.
public void placeMark(int x, int y), which places the mark of the current player (i.e. the one returned by getNextPlayer()) in the grid at position (x,y). It must then pass the turn to the next player. Position (0,0) represents the top left corner of the board, and position (2,2) represents the bottom right corner. If the game is over, or if the given position is already marked, an IllegalStateException must be thrown. If either x or y is outside the range 0 to 2 (inclusive), an IllegalArgumentException must be thrown.

As an example, the following code should result in a TicTacToe object where player 1 owns the top left and top center squares, while player 2 owns the bottom right square:

TicTacToe game = new TicTacToe();
game.placeMark(0, 0); // player 1 places a mark
game.placeMark(2, 2); // player 2 places a mark
game.placeMark(0, 1); // player 1 places a mark

You may add any additional fields and methods that you need to the class.

Hint: you can represent the board using a two-dimensional array of integers, using 0 to represent an empty square, and 1 and 2 to represent marks from players 1 and 2 respectively.

Solution: TicTacToe.java

2b.

The game Tic Tac Toe (Tre-i-rad) is played on a 3x3 grid of squares, where two players take turns marking the squares with Xs (for the first player) and Os (for the second player). The first player to mark three squares in a row with their symbol wins the game. Marked squares may not be overwritten, so the game ends in a draw if all squares should become filled before any player can line up three marks. Here is a finished game of Tic Tac Toe where player 2 has won.

(Image: Symode09 / Wikimedia Commons / Public Domain)

Your task: write a class TicTacToeB which models the Tic Tac Toe game. The class must keep track of the state of the game board (i.e. which player owns which squares), whether the game has ended in victory for some player, if it’s a draw, or if the game is still on, and which player will make the next move.

The class must have the following methods and constructors:

A parameterless constructor public TicTacToeB() which initializes the game with an empty 3x3 board and sets player 1 as the next player to take a turn.
public int getWinner(), which returns 1 if player 1 has won the game, 2 if player 2 has won, 0 if the game has ended in a draw, and -1 if the game is not yet over.
public int getNextPlayer(), which returns 1 if it’s player 1’s turn, or 2 if it’s player 2’s turn. If the game is over, an IllegalStateException must be thrown.
public char getContents(int x, int y), which returns the contents of the square at position (x, y): either 'X', 'O', or ' ' if the square is empty. Position (0,0) represents the top left corner of the board, and position (2,2) represents the bottom right corner. If either x or y is outside the range 0 to 2 (inclusive), an IllegalArgumentException must be thrown.
public void placeMark(int x, int y), which places the mark of the current player (i.e. the one returned by getNextPlayer()) in the grid at position (x,y). It must then pass the turn to the next player. Position (0,0) represents the top left corner of the board, and position (2,2) represents the bottom right corner. If the game is over, or if the given position is already marked, an IllegalStateException must be thrown. If either x or y is outside the range 0 to 2 (inclusive), an IllegalArgumentException must be thrown.

As an example, the following code should result in a TicTacToe object where player 1 owns the top left and top center squares, while player 2 owns the bottom right square:

TicTacToeB game = new TicTacToeB();
game.placeMark(0, 0); // player 1 places a mark
game.placeMark(2, 2); // player 2 places a mark
game.placeMark(0, 1); // player 1 places a mark

You may add any additional fields and methods that you need to the class.

Hint: you can represent the board using a two-dimensional array of integers, using 0 to represent an empty square, and 1 and 2 to represent marks from players 1 and 2 respectively.

Solution: TicTacToeB.java

3a.

Given two positive integers a and b, we say that an integer c can be formed by merging the digits in a and b iff the digits of c are formed by writing down:

some number (perhaps 0) of the digits of a;
then some of the digits of b;
then some of the digits of a;
then some of the digits of b;
...

until all the digits of a and b have been used. The digits of a must appear in the same order in c, and the digits of b must appear in the same order in c.

For example, we can merge 123 and 456 to form 123456 or 142536 or 451263, but not 654123.

Write a method

int largestMerge(int a, int b)

which, given two integers a and b, returns the largest integer that can be formed by merging the digits of a and b.

Hint: There are two standard ways to turn an integer into a sequence of digits:

Given an integer n, n % 10 will give you the last digit of n, and n / 10 will give you the integer n with the last digit deleted. By repeating these operations, you can obtain all the digits of n.
Alternatively, the method String.valueOf() will turn an integer 12345 (for example) into the string "12345". The method charAt(i) will give you the (i+1)th digit as a character. Character.getNumericValue can then be used to turn it back into an integer. Thus for example Character.getNumericValue(String.valueOf(12345).charAt(3)) will evaluate to 4.

Solution: LargestMerge.java

3b.

Given two positive integers a and b, we say that an integer c can be formed by merging the digits in a and b iff the digits of c are formed by writing down:

some number (perhaps 0) of the digits of a;
then some of the digits of b;
then some of the digits of a;
then some of the digits of b;
...

until all the digits of a and b have been used. The digits of a must appear in the same order in c, and the digits of b must appear in the same order in c.

For example, we can merge 123 and 456 to form 123456 or 142536 or 451263, but not 654123.

Write a method

int smallestMerge(int a, int b)

which, given two integers a and b, returns the smallest integer that can be formed by merging the digits of a and b.

Hint: There are two standard ways to turn an integer into a sequence of digits:

Given an integer n, n % 10 will give you the last digit of n, and n / 10 will give you the integer n with the last digit deleted. By repeating these operations, you can obtain all the digits of n.
Alternatively, the method String.valueOf() will turn an integer 12345 (for example) into the string "12345". The method charAt(i) will give you the (i+1)th digit as a character. Character.getNumericValue can then be used to turn it back into an integer. Thus for example Character.getNumericValue(String.valueOf(12345).charAt(3)) will evaluate to 4.

Solution: SmallestMerge.java