Problem overview
A bottle holds at most a fixed amount of water. You can't pour in more than fits, and you can't drink more than is inside. WaterBottle tracks how much water is in one bottle, in whole milliliters:
WaterBottle::new(capacity)creates an empty bottle that holds at mostcapacity.fill(amount)pours inamount, but only as much as fits, and returns how much actually went in.drink(amount)drinksamount, but only as much as is in the bottle, and returns how much was actually drunk.level()returns how much water is in the bottle now.
With a capacity of 300, fill(250) returns 250. Only 50 more fit, so fill(100) returns 50 and the bottle is full. A full bottle takes nothing more: fill(10) returns 0.
Approach
The bottle only needs to remember two numbers: its capacity, which never changes, and the water it holds now. Both rules have the same shape. A request is cut down to what is possible:
- When filling, the room left is
capacity - water. The amount that goes in is the smaller of the request and the room left. - When drinking, the most you can drink is
water. The amount drunk is the smaller of the request and the water.
Because the amount is cut down before it is applied, the water can never go above the capacity or below 0, and no if is needed. Returning the cut-down amount tells the caller what really happened. The fields are named capacity and water, so the field water and the method level are easy to tell apart.
Step by step
- Declare the fields:
capacityandwater, bothi32. - Build an empty bottle in
new. The parametercapacityhas the same name as the field, so the shorthandcapacityis enough, andwaterstarts at 0. - In
fill, compute how much goes in.amount.min(self.capacity - self.water)is the smaller of the two numbers. If the whole amount fits, it isamount. If not, it is the room left, and the bottle ends up exactly full. - Add it to the water with
+=, using the cut-down value, not the original request. - Return it. The last expression is
added, without a semicolon. - In
drink, do the same in reverse:drunkisamount.min(self.water), subtract it with-=, and return it. levelreturnsself.water. It only reads, so it takes&self, whilefillanddrinkchange the bottle and take&mut self.
The solution in Rust
struct WaterBottle {
capacity: i32,
water: i32,
}
impl WaterBottle {
fn new(capacity: i32) -> WaterBottle {
WaterBottle { capacity, water: 0 }
}
fn fill(&mut self, amount: i32) -> i32 {
let added = amount.min(self.capacity - self.water);
self.water += added;
added
}
fn drink(&mut self, amount: i32) -> i32 {
let drunk = amount.min(self.water);
self.water -= drunk;
drunk
}
fn level(&self) -> i32 {
self.water
}
}
Using it with a capacity of 300:
let mut b = WaterBottle::new(300);
println!("{}", b.fill(250));
println!("{}", b.fill(100));
println!("{}", b.level());
println!("{}", b.fill(10));
println!("{}", b.drink(100));
println!("{}", b.drink(500));
println!("{}", b.level());
The output, one number per line:
250
50
300
0
100
200
0
The second drink asks for 500 but only 200 were left, so it returns 200 and the level drops to 0.
Rust details worth knowing:
minis a method on numbers.amount.min(other)returns the smaller of the two, for any integer type that can be ordered, so it needs no import.letwithoutmutis enough foradded. The variable is set once and never changed. Only the bottle, which is modified, must belet mutwhere it is used.- The last expression is the result.
addedanddrunkhave no semicolon. Writingadded;would return()and the compiler would report a type mismatch.
Complexity
Each method does a fixed number of operations on two integers, so every call runs in O(1) time. The struct holds two integers, so it uses O(1) space.
Edge cases and common mistakes
- Adding the request instead of the cut-down amount. If
filldidself.water += amount, filling 100 into a bottle with 250 of 300 would leave 350. Addingaddedkeeps the level at 300. - Returning the request. The return value is how much really went in or came out.
fill(100)in that situation returns 50, not 100. - Drinking from an empty bottle. It returns 0 and the level stays 0.
- A request of 0. The smaller of 0 and anything non-negative is 0, so nothing changes and the call returns 0.
- Filling a full bottle. The room left is 0, so
addedis 0. - Mixing up the limits. Fill is limited by the room left (
capacity - water), not by the capacity. Drink is limited by the water, not by the capacity.
Testing
With a capacity of 100, a fresh bottle behaves like this:
drink(10)returns 0, because the bottle starts empty.fill(60)returns 60.drink(100)returns 60, which empties the bottle again.level()returns 0, anddrink(5)returns 0.
These calls give 0 60 60 0 0 in that order. Checking a case where the request is bigger than what is possible, in both directions, catches most mistakes: one fill past the capacity and one drink past the water.
