Description

Figure 1 shows Robbie’s new front yard. It was absolutely beautiful in the springtime when he and his wife bought the house. That continued into the summer, but then fall happened. The beautiful, mature trees started dropping leaves! They dropped at such a rate that with a rake and leaf blower, they could not keep up. After an entire afternoon of raking, the yard was again covered in leaves within 24 hours.

After multiple passive-aggressive fliers left on their door by lawn companies, they’ve decided to reach out for help this year. David offered to help, but none of us want to toil in vain. So, we’ve decided to create a high-tech solution to the problem! Robot vacuums have been available for years, and thankfully robot lawnmowers have recently started appearing in stores. To solve our leaf problem and cash in on this trend, we would like to create a robot leaf mulcher. However, as good product designers, we must first decide the best width of robot mulcher based on yard dimensions and the layout of trees and bushes. We would prefer to create the widest mulcher possible for Robbie’s yard, allowing us to maximize battery life and minimize the amount of time the mulcher must traverse the lawn.

Since the trees and bushes in the yard appear to have been planted haphazardly many years ago, we must take their unmovable positions into account. A mockup of the lawn can be seen in Figure 2. Before we build our first prototype robot mulcher, we need to know the maximum width such that it will fit between any two trees in the yard, i.e. we need to determine distance between the closest pair of tree or bush trunks (for simplicity, disregard the leaves and branches around the base of the bushes).

Implement an algorithm which takes as input the locations of the trees and bushes as Cartesian coordinates, and returns the maximum width of the robot mulcher we can use in the yard (i.e. the closest pair of trees). Your program should have the following properties:

•    Your algorithm must be written in Python (2 or 3) or Java (10).

•    You must download the appropriate wrapper code from Collab based on the language you choose: main.py and closest_pair.py for Python, Main.java and ClosestPair.java for

Java.

•    The compute() method in both Python and Java receives as input the body of the input file as a list of lines. You must have main() return the distance between the closest trees or bushes. An example input file is shown in Figure 3, which has answer ≈ 4.12311. Note: the coordinates may be integers or floating point numbers.

•    You should write another function in the closest_pair.py or ClosestPair.java file to implement the Closest Pair algorithm. Your compute() method will then invoke this function. Do not modify the method definition for compute.

•    You should think about what intermediate representation you want to use to represent the list of coordinates. You will probably prefer a different representation than a list of strings. We suggest you write a helper method to parse the input into your chosen representation.

•    Two additional test files are provided, test1.txt and test2.txt, both with answer ≈

1.4142135623. You should produce additional tests, including edge cases.

•    You may modify the Main.java or main.py files to test your algorithm, but they will not be used during grading.

•    You must submit your ClosestPair.java or closest_pair.py files on Collab. Do not zip them. Do not submit Main.java, main.py, or any test files.

•    A few other notes:

–   Your code will be run as: python main.py or python3 main.py for Python, or javac *.java && java Main for Java.

–   You may upload multiple Java files if you need addional classes, but do not assign packages to the files

In the case that we discover our robot mulcher becomes the envy of the neighborhood and super popular, and this whole “professor thing” doesn’t work out for us, David and I may enter the robot mulcher business and mass produce them for wider use. Therefore, we would like this algorithm to be very efficient, so that we can quickly determine the appropriate size of mulcher for any size lawn, even tree farms with thousands of trees! If we put in the locations of thousands of trees and bushes, the algorithm should still run in a reasonable amount of time. For this reason, an Ω(n2) algorithm is too slow; to be efficient enough, your algorithm must run in O(n log n) time.