In the land of Numerica, travelers seek the legendary First Valley—the initial dip in the terrain that holds untold treasures 💰💰💰. As a master cartographer, you've been tasked with creating a magical map called ValleyTraveler
that identifies these prized valleys in the ever-changing landscape and modifies them when sudden changes occur. The Data Lords of Numerica have left treasure in valleys. Upon excavating a valley, you, the cartographer collect these mysterious rewards.
Implement a Java class called ValleyTraveler
that operates on an array of distinct integers (representing the landscape of Numerica). The class should perform the following operations:
-
Constructor:
ValleyTraveler(int[] landscape)
Initializes the magical map with the given landscape of Numerica. -
getFirst()
: Locates the first valley point in the current landscape of Numerica and returns the associated treasure. -
remove()
: Excavates (removes) the first valley point from the current landscape and returns the associated treasure. This operation updates the landscape and its hidden treasures accordingly. -
insert(int height)
: Creates a new landform with the given height at the position where the first valley was just removed. This operation updates the landscape and its hidden treasures accordingly. -
isEmpty()
: Returnstrue
if the entire landscape is excavated (i.e., there are no landforms left), andfalse
otherwise. -
getTotalTreasure()
: Returns the current total treasure that has been "collected" through successiveremove()
operations.
A valley point is defined as a landform that is lower than its neighboring landforms. For example, in the landscape [5, 2, 8, 6, 3, 9, 4]
, the valley points are [2, 3, 4]
.
More formally, let
- For
$n = 1$ :$A_{0}$ is a valley point - For
$i = 0$ :$A_{i} < A_{i+1}$ - For
$i = n-1$ :$A_{i} < A_{i-1}$ - For
$0 < i < n-1$ :$A_{i} < A_{i-1}$ and$A_{i} < A_{i+1}$
Let the landscape be represented by a 0-indexed array
-
Implementation File:
Implement theValleyTraveler
class inValleyTraveler.java
. -
Constructor:
The class should have a constructor that takes an array of distinct integers (the initial landscape). -
Methods:
Implement the following methods:getFirst()
remove()
insert(int height)
isEmpty()
getTotalTreasure()
Handle edge cases and maintain the landscape's integrity after operations.
-
State Management:
The provided array should not be modified directly. Instead, the class must maintain its internal state to reflect any changes made byremove()
andinsert()
operations. -
Restrictions:
You are not allowed to use Java standard collections (e.g.,ArrayList
,HashMap
,HashSet
, etc.). Only primitive data types and arrays (e.g.,int[]
) are allowed. You may implement your own data structure(s) if necessary.
Consider the following initial landscape: [3, 2, 1, 4, 5]
.
-
getFirst()
returns2.0
(First treasure located)Terrain:
[3, 2, 1, 4, 5]
-
remove()
returns2.0
(First valley excavated, treasure collected)Terrain:
[3, 2, 4, 5]
-
insert(6)
(New landform created at current first valley)Terrain:
[3, 6, 2, 4, 5]
-
remove()
returns3.0
(Valley excavated, treasure collected)Terrain:
[6, 2, 4, 5]
-
remove()
returns4.0
(Valley excavated, treasure collected)Terrain:
[6, 4, 5]
-
remove()
returns5.0
(Valley excavated, treasure collected)Terrain:
[6, 5]
-
getTotalTreasure()
returns14.0
Submit your ValleyTraveler.java
file and any additional Java files (if created) through Gradescope.
- Submission link:
- Deadline: Feb 16th, 2025 at 11:59 PM EST.
- Late Submission Policy: Late submissions will not be accepted.
- Correctness: Does the implementation correctly identify and modify valley points in the landscape?
- Efficiency: Does the implementation have a reasonable time and space complexity?
-
Initialization: The
ValleyTraveler
object is initialized with an arbitrary array of distinct integers, representing the initial landscape. -
Operations: The three methods
getFirst()
,remove()
,insert(int height)
, andgetTotalTreasure()
can be invoked in any arbitrary order. -
Assumptions: It is guaranteed that invalid invocations will not occur. Specifically,
remove()
orgetFirst()
will not be called on an empty landscape. Also, at any points, the heights of all the landforms in the landscape are guaranteed to be distinct. -
Time Complexity: Given an initial landscape with
$N$ landforms and$Q$ queries (operations), the entire procedure should be completed in$O(N+Q)$ time complexity. - Testing: We will test your implementation with various test cases, each containing different landscapes and operations, and based on how many and which test cases your implementation passes, we will assign you a score between 0 and 25 points.
Begin your expedition with the provided ValleyTraveler.java
file.
Note: The starter code is provided as a guideline. You may modify or completely replace it as long as your final implementation meets all the requirements.
A script similar to Evaluator.java
will be used to evaluate your implementation. To run the evaluation script locally:
# Ensure Java is installed on your computer
java -version
# Navigate to the hw1 directory.
# Compile the Evaluator.java file along with ValleyTraveler.java
javac Evaluator.java ValleyTraveler.java
# Run the Evaluator with a provided sample test case
java Evaluator sample_tc.txt
# Feel free to create and run your own test cases