Lab #9 (AY2007/8 Semester 1)

Date of release: 30 October 2007, Tuesday, 23:59.

Submission deadline: 7 November 2007, Wednesday, 23:59.

School of Computing, National University of Singapore

You are advised to review the material covered in chapters 1 through 15.

This lab assignment complements the lectures on recursion. You must code the programs using recursion, even when more efficient non-recursive algorithms are possible.

There are three exercises in this assignment. Only the first two are to be submitted.

You may assume that **all input data are correct**.

You should use `Scanner` class on `System.in` for
input and `System.out` for output in your programs,
unless otherwise stated.

**Test your programs thoroughly with your own input data before you
submit to CourseMarker.** Do not use CourseMarker as a debugging tool.
For this lab, the number of submissions is set to **5**.
Only your last submission will be graded.

This is the final lab assignment for CS1101. (Hooray!)

- Writing recursive program
- Using cast to convert between integer and character

We can convert a positive integer in decimal (base 10) to another base by doing repeated division. The two examples below show how to convert decimal value 123 to base 5 (quinary) and base 16 (hexadecimal).

The answer is obtained by collecting the remainder in each step of the
division, from the bottom up. Hence,
123_{10} = 443_{5} = 7B_{16}.

For bases larger than 10, the digits 10, 11, 12, ... are represented by the characters A, B, C, ... Hence the digits in hexadecimal are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F.

Write a program `ConvertBase.java` to read in a positive
integer and a target base (between 2 and 36 inclusive),
and generate the equivalent value in the target base.
Your program must employ a recursive algorithm. No mark will be
given if you do not use recursion.

You are **not** allowed to use methods such as `toBinaryString`,
`toHexstring`, `toOctalString`, `toString`
(all in the `Integer`
class; refer to java.lang.Integer if you wish), or other
similar methods in other classes that convert a decimal value into
another base.

Sample run using interactive input (user's input shown in
blue; output shown in
**bold purple**):

Sample run #1:

$ javac ConvertBase.java $ java ConvertBase Enter a positive decimal integer: 123 Enter target base: 5443

Sample run #2:

$ java ConvertBase Enter a positive decimal integer: 123 Enter target base: 167B

Sample run #3:

$ java ConvertBase Enter a positive decimal integer: 12345 Enter target base: 369IX

Submit your program `ConvertBase.java` through CourseMarker.

- An iterative method will not be accepted since it
undermines the objective of this exercise.

- Do not use any of such methods like
`toBinaryString`,`toHexstring`,`toOctalString`,`toString`(all in the`Integer`class) or other similar pre-defined methods to do the conversion.

- Using a 2-dimensional array
- Writing recursive program

The ACM International Collegiate Programming Contest (ICPC) is a contest for university students all over the world, in which thousands of teams participate every year. NUS School of Computing is organising the 32nd ACM ICPC Regional Contest in Singapore on 13-14 December 2007, where teams from universities in the region will gather here to pit their programming skills against one another. Top teams of the regional contests will proceed to the World Finals to be held in April 2008 in Alberta. On 14 December, another programming contest, the Algo*Mania, aimed for students from local secondary schools, junior colleges, ITE and polytechnics, will also be held concurrently with the ACM ICPC Regional Contest.

(If you are keen in joining the ACM team to represent NUS to participate in the ACM ICPC in future, please contact me (tantc @ comp.nus.edu.sg) and I will link you up with the co-ordinator. Training will be provided.)

This UVa website provides many problem sets for aspiring contestants to hone their programming skills. A problem suitable for this lab assignment is found here. The question is reproduced below, slightly modified. For this lab assignment, please follow the write-up below.

(Copyright belongs to Universidad de Valladolid) The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil.

A plot containing oil is called a **pocket**. If two pockets
are adjacent, then they are part of the same **oil deposit**.
Oil deposits can be quite large and may contain numerous pockets.
Your job is to determine how many different oil deposits are
contained in a grid.

You are to write a program `OilDeposits.java` to implement
a class `OilDeposits` that contains the following:

- A data member
`char[][] grid`-- a two-dimensional character array.

- A constructor
`OilDeposits (char[][] g)`that assigns`g`to the data member`grid`.

Your program should read in the following input data:

- The first line contains two positive integers
*rows*(≤ 20) and*cols*(≤ 40) which denote the number of rows and columns, respectively, in the grid.

- Followed by a (
*rows*×*columns*) array of characters '*' and '@'. Each character corresponds to one square plot, and is either '*' representing the absence of oil, or '@' representing an oil pocket.

- Note that rows (starting with row 0) are numbered from top to bottom, and columns (starting with column 0) from left to right.

Your program outputs the **number of distinct oil deposits**.
Two pockets are parts of the same oil deposit if they are adjacent
horizontally, vertically, or diagonally.

The following is an example showing a 5 × 8 grid.

5 8 ****@*** *@@*@*@* *@***@** @@@*@*** @@**@@@*

The number of oil deposits for the above example is 2. The two oil deposits are shown in different colours below. (Your program only needs to output the value 2. The figure below is for explanatory purpose only.)

****@*** *@@*@*@* *@***@** @@@*@*** @@**@@@*

Sample run using interactive input (user's input shown in
blue; output shown in
**bold purple**):

$ javac OilDeposits.java $ java OilDeposits 4 5 ***** ***** ***** *****0

Another sample run:

$ java OilDeposits 7 18 *****@************ ****@*@*****@***** ***@***@***@*@**** **@**@**@*@***@*** ***@***@***@*@**** ****@*@*****@***** *****@************3

Submit your program `OilDeposits.java` through CourseMarker.

- A grid has at most 20 rows and 40 columns.

- Entering the data interactively for this exercise is tedious,
especially when the grid is large. If you use the sunfire UNIX
system, you may do the following without the
need to change your code.

Type the input data into a text file, let's call it`grid.dat`. You may then use the UNIX input redirection symbol`<`to redirect input from this file:

`java OilDeposits < grid.dat`

- Writing recursive program

You are given a text file `maze.dat` that contains on the first
line two positive integers: number of rows and columns of the maze,
followed by the maze, as shown below.

8 10 ########## # # # # # # # E # # ## # # # # X ## # ### # # ## ##########

In the maze, the character '#' denotes a wall. The character 'E' denotes the entrance, and 'X' the exit. There will be exactly one entrance, and exactly one exit in the maze, and they lie on the boundary of the maze.

Write a program `Maze.java` to read the input from the text
file `maze.dat`, and determines if there is any path from
the entrance to the exit, and prints "YES" if it is so, or "NO"
otherwise. Your program should include a recursive
method `solveMaze`.

A demonstration program DemoLab9.java to show how you may read data from a text file demo.dat is given.

Example 1: Assuming that the following is the content of the text file
`maze.dat`:

8 10 ########## # # # # # # # E # # ## # # # # X ## # ### # # ## ##########

Sample run:

$ java MazeYES

Example 2: Assuming that the following is the content of the text file
`maze.dat`:

8 10 ########## # # # # # # # E # # #### # # # X ## # ### # # ## ##########

Sample run:

$ java MazeNO

No submission is required for this task. It is only for your own amusement.

- You should test your program with different
`maze.dat`files. For convenience in testing, your program may request for the filename of the input file and read that specified file accordingly.

The deadline for handing in programs for exercises 1 and 2
is **7 November 2007, Wednesday, 23:59**.
Late submissions will NOT be accepted.

- 0 Introduction

- 1 Exercise 1: Converting Decimal to another Base (40%)

- 2 Exercise 2: Oil Deposits (60%)

- 3 Exercise 3: Maze (Ungraded: 0%)

- 4 Deadline

tantc@comp.nus.edu.sg

Mon Oct 15 08:43:31 SGT 2007