Logging Lease Optimizer - Assignment #2

CSCI 135
Fundamentals of Computer Science I
Fall 2011

Course information | Schedule | Assignments | Exams | Resources

ASSIGNMENT #2

In this assignment, you will gain experience reading from standard input, using arrays, and using Math methods. You will also learn how to design a brute-force algorithmic solution to a problem that would be tedious and error-prone for a human to calculate.

Logging Lease Optimizer
You work for a logging company which needs to decide what portion of a forest to lease in order to maximize its take of the juicy, juicy ponderosa pine trees. A detailed survey of the forest has been conducted giving details of each pine tree in the forest. The location of each tree is given by its distance (in feet) to the east and to the north of the southwest corner of the forest. Each tree also had its height recorded and its DBH (diameter at breast height). The survey also recorded the location of any Grizzly bear dens in the forest.

The forest service requires your lease be a square with sides that are an integer number of feet. The sides of the leased square must be as big as possible without exceeding the specified lease square footage. So for example, if a lease of 1000 ft^2 was requested, the lease area would be 31 ft x 31 ft. Your leased area must not extend outside the specified forest.

You are allowed to log any trees in your leased square including trees on the edge of the square. However, since Grizzlies are a threatened species (and your loggers are scared of them), you are not allowed to lease any area containing a bear den (even one on the lease's edge). The value of a lease area is determined by the total volume of trees contained in the area. A ponderosa pine in western Montana has a volume in cubic feet of approximately 10^-2.3582 · d^1.87254 · h^0.89306 where d is the DBH in inches and h is the height in feet (taken from here).

The survey data comes in a text file that starts with the following three integer values:

Width of forest (distance in feet from eastern border to western border)
Height of forest (distance in feet from southern border to northern border)
Number of data points (trees or bear dens) in the file

After this comes a series of data points consisting of four integer values:

Distance to the east in feet (x coordinate)
Distance to the north in feet (y coordinate)
Height of tree (to nearest in foot), a negative value if this point is a bear den
DBN, diameter breast height (to nearest inch), a negative value if this point is a bear den

Here is an example file for a toy 10x7 forest having 12 trees and 2 bear dens:

Visual representation of the toy 10 x 7 forest.
The pink shaded area is the optimal 4 ft^2 lease.

Create a program LoggingLease.java that takes a single parameter specifying the area (in square feet) of the lease. Your program should read in the survey data from standard input. Write an algorithm that evaluates all possible locations for the lease. Choose the location that maximizes the total volume of wood harvested. In the event of a tie, choose the location with the smallest sum of x and y coordinates. Your program should print out the following:

number of trees in the forest
number of bear dens in the forest
southwest corner of the best lease
northeast corner of the best lease
volume of trees in the best lease

If no valid lease can be placed in the forest (due to size or bear issues), print out "No lease possible!". Here are some example runs:

% java LoggingLease 4 < 10x7.txt
Forest trees     : 12
Forest bear dens : 2
Best southwest   : (6, 1)
Best northeast   : (8, 3)
Best tree volume : 158.77176344661575 ft^3

% java LoggingLease 9 < 10x7.txt
Forest trees     : 12
Forest bear dens : 2
Best southwest   : (2, 4)
Best northeast   : (5, 7)
Best tree volume : 161.22920802240924 ft^3

% java LoggingLease 18 < 10x7.txt
Forest trees     : 12
Forest bear dens : 2
Best southwest   : (6, 2)
Best northeast   : (10, 6)
Best tree volume : 176.07474821139263 ft^3

% java LoggingLease 25 < 10x7.txt
Forest trees     : 12
Forest bear dens : 2
No lease possible!

% java LoggingLease 2 < 10x7.txt
Forest trees     : 12
Forest bear dens : 2
Best southwest   : (4, 4)
Best northeast   : (5, 5)
Best tree volume : 128.0389718453977 ft^3

Here is a much bigger square mile forest, some example runs, and a graph of the square mile forest:


% java LoggingLease 10000 < square_mile.txt
Forest trees     : 100
Forest bear dens : 10
Best southwest   : (2591, 2185)
Best northeast   : (2691, 2285)
Best tree volume : 451.11381707316303 ft^3

% java LoggingLease 100000 < square_mile.txt
Forest trees     : 100
Forest bear dens : 10
Best southwest   : (2375, 1969)
Best northeast   : (2691, 2285)
Best tree volume : 647.2593310955781 ft^3

% java LoggingLease 7767368 < square_mile.txt
Forest trees     : 100
Forest bear dens : 10
Best southwest   : (2494, 0)
Best northeast   : (5280, 2786)
Best tree volume : 2962.083090075347 ft^3

How do I read information from standard input? We will use the class StdIn.java to read from standard input. Make sure you put this java file in the source directory with your LoggingLease.java program. By calling static methods in StdIn you can easily parse data from an input file. Here is an example program StudentAvg.java which you can run a data file like scores.txt. Note in this example, the number of lines in the file is unknown so StdIn.isEmpty() is used to loop until the end of the file is reached. In your LoggerLease.java program, you know the number of data points, so you should loop over exactly that many lines.

How do I create and use an array? Check out MeanVar.java and points.txt. This example also shows how to read in a fixed number of lines just like you need to do in your program. For another array example, see Backwards.

Extra credit:
The forest service has loosened up their lease rules. You can now lease rectangular sections of land. You may also request a lease with any area so long as it is less than or equal to the specified area (the area specified on the command line). Occasionally (due to bear dens or forest boundaries), a smaller lease may actually be more profitable. Copy your previous solution into a new class LoggingLeaseEC.java. Modify your program to find the optimal lease under the new loosened rules.

Submission. Submit your program LoggingLease.java and optionally LoggingLeaseEC.java via Moodle. Be sure each submitted source file has the required header with your name, username, and a description of the program.

Page last updated: August 16, 2012