PA2 - Leaf Mulching

The image below shows Prof Hott’s front yard. It was absolutely beautiful in the springtime when he and his wife bought their new 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. Prof Horton 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 below. 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).

Input

Your algorithm will receive as input the body (list of strings) of a file called yard.txt. The file will contain the coordinates of each tree in the yard of the form:

x1 y1
x2 y2
x3 y3

Note: each line contains an \(x\) and \(y\) coordinate, space separated. The example input yard.txt is shown below.

yard.txt

    4 13
    12 10
    8 9
    1 1
    42 108

Output

Your output will be the distance between the closest trees.

Implementation

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 3.10.6 or Java 19.0.2 (OpenJDK)
• You must download the appropriate wrapper code based on the language you choose: Main.py and RobotMulcher.py for Python, Main.java and RobotMulcher.java for Java.
  • Java package: pa2-java.zip
  • Python package: pa2-python.zip
• The compute() method in RobotMulcher receives as input the body of the input file as a list of strings. You must have compute() return the results described above. An example input file is shown below, which has answer \(\approx 4.12311\).
• You should write another function in the RobotMulcher file to implement the Closest Trees 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 also 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 \(\approx 1.4142135623\). You should produce additional tests, including edge cases.
• You may modify the Main files to test your algorithm, but they will not be used during grading.
• You must submit your RobotMulcher file to Gradescope. Do not submit Main.java, Main.py, or any test files.
• You may submit your code a maximum of 15 times to Gradescope. After the 15th submission, Gradescope will not run your code.
• A few other notes:
  • Your code will be run as:
    python3 Main.py for Python, or javac *.java && java Main for Java.
  • You may upload multiple files if you need additional classes for Java, but do not assign packages to the files.
  • You may use any editor or IDE you prefer as long as the code can be executed as stated above.
  • We strongly encourage you to practice good development as you write code: use meaningful variable names, break your code into functions, “code a little then test a little”, use the debugger, etc.

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, Profs Horton and Hott 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 \(\Omega(n^2)\) algorithm is too slow; to be efficient enough, your algorithm must run in \(O(n \log n)\) time.

Rules on Collaboration and Outside Sources

You may discuss the problem and the overall strategy with up to 4 other students, but you must list those people in your submission under collaborators. You may not share code, look at others’ code, or help others debug their code. You must write your own code. Not just type it (though you need to do that too): compose it yourself, as your own original work. Please read the syllabus carefully around coding. Do not seek published or online solutions for any assignments. If you use any published or online resources (which may not include solutions) when completing this assignment, be sure to cite them. Do not submit a solution that you are unable to explain orally to a member of the course staff.

Use of Generative AI

For PA2, you are not allowed to use generative AI tools to help you solve this problem.