Base Conversion, Oil Deposits and Maze
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

0 Introduction

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!)

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

1.1 Learning objectives

Writing recursive program
Using cast to convert between integer and character

1.2 Task

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₁₀ = 443₅ = 7B₁₆.

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.

1.3 Sample runs

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: 5
443

Sample run #2:

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

Sample run #3:

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

1.4 Submission

Submit your program ConvertBase.java through CourseMarker.

1.5 Important notes

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.

2 Exercise 2: Oil Deposits (60%)

2.1 Learning objectives

Using a 2-dimensional array
Writing recursive program

2.2 Task

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.)

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

2.3 Sample runs

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

2.4 Submission

Submit your program OilDeposits.java through CourseMarker.

2.5 Important notes

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

3 Exercise 3: Maze (Ungraded: 0%)

3.1 Learning objectives

Writing recursive program

3.2 Task

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.

3.3 Sample runs

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

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

Sample run:

$ java Maze
YES

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

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