Kattis 'Driver's Dilemma'

Question

The full problem description can be found here, a slightly trimmed version below:

A car driver is travelling on an isolated road (no gas stations, houses, or cell phone coverage). The driver glances at their fuel gauge: there is exactly half a tank left. They stop and see that the fuel tank is leaking.

The driver cannot repair the leak. Using a container of known volume and a wristwatch, they measure the rate of fuel loss at 𝑋 gallons per hour. They empty the container back into the tank.

The driver checks the manual and sees the fuel tank capacity is 𝐶 gallons. There's also a table resembling the one below, showing declining fuel efficiency in miles per gallon (MPG) as driving speed in miles per hour (MPH) increases. They must trade one against the other in an attempt to reach the nearest gas station 𝑀 miles away before nightfall.

Speed (MPH)  Fuel Efficiency (MPG)
         55                   22.0
         60                   21.3
         65                   20.2
         70                   18.3
         75                   16.9
         80                   15.8

The driver assumes manuals authors are experts, and has an aversion to interpolation (and extrapolation), they decide to drive at exactly one of the 6 speeds listed. That way, the distance travelled before running out of gas will be 100% predictable.

Can the driver reach the gas station before running out of fuel? If so, what is the maximum speed they can drive?

Examples:

Input	Output
18 0.5 160 55 22.0 60 21.3 65 20.2 70 18.3 75 16.9 80 15.8	YES 60
16 0.07 160 55 20.49 60 18.40 65 17.78 70 17.10 75 16.38 80 15.60	NO

---

main.rs

use std::io::{self, BufRead};

#[derive(Debug)]
struct Car {
    capacity: f32,
    rate_of_loss: f32,
    remaining: f32,
    efficiancy: Vec<MPG>,
}

#[derive(Debug)]
struct MPG {
    mph: f32,
    mpg: f32,
}

impl Car {
    fn in_range(&self, distance: f32) -> f32 {
        let mut res: f32 = -1.0;
        let volume = self.capacity * self.remaining;
        for entry in &self.efficiancy {
            let time = distance / entry.mph;
            let total_loss = time * self.rate_of_loss;
            let max_distance = (volume - total_loss) * entry.mpg;
            if max_distance > distance {
                res = res.max(entry.mph);
            }
        }
        res
    }
}

fn main() {
    let remaining: f32 = 0.5;
    let mut c: f32 = 0.0;
    let mut x: f32 = 0.0;
    let mut m: f32 = 0.0;
    let mut efficiancies: Vec<MPG> = Vec::new();

    let stdin = io::stdin();
    for (i, line) in stdin.lock().lines().map(|x| x.unwrap()).enumerate() {
        let nums: Vec<f32> = line
            .split_whitespace()
            .map(|n| n.parse().unwrap())
            .collect();
        if i == 0 {
            c = nums[0];
            x = nums[1];
            m = nums[2];
        } else {
            efficiancies.push(MPG {
                mph: nums[0],
                mpg: nums[1],
            });
        }
    }
    let car = Car {
        capacity: c,
        rate_of_loss: x,
        remaining: remaining,
        efficiancy: efficiancies,
    };
    let y = car.in_range(m);
    if y > 0.0 {
        println!("YES {:.0}", y);
    } else {
        println!("NO");
    }
}

I did initially write a smaller version that did everything in the main function, but I wanted to try using struct and impl. I primarily use python, so I'm mostly looking for pointers on style/idiomatic rust and intermediate/advanced topics that I could try out. Any advice is welcome :)

Answer 1

Design

I applaud the goal of using struct and impl, but this is a good example of where object-oriented style can go wrong: it is not clear exactly what functionality Car and MPG encapsulate. Rather, these are just structs that carry some relevant data for the in_range function, but they do not seem to lead to a meaningful "separation of concerns" or make the code easier to understand as written.

For example, what is an MPG object? It carries a pair of a miles-per-hour and a miles-per-gallon, but why are these particular pieces of data grouped together and not with the other pieces of data? For Car, the primary problem is that it carries a lot of data but not enough functionality. If I were to reuse or extend your code, I would not be sure what to use a Car for, and whether and how I should extend Car with additional methods.

To improve your code, I would start by getting rid of MPG. Then, I would settle on a simple abstraction of a car that seems generalizable. We could start with this: a car is something that drives, given a certain amount of fuel, a fuel leak rate, a certain speed, and a certain fuel efficiency. Note that we no longer have efficiancy: Vec<MPG> as part of the car --- that muddles the meaning of a car, since it can then only drive at certain rates. We might get something like the following design:

struct Car {
    fuel_remaining: f32, // Gallons
    fuel_leak_rate: f32, // Gallons/hour
    speed: f32, // Miles/hour
    efficiency: f32, // Miles/gallon
}
impl Car {
    fn new(
        fuel_remaining: f32,
        fuel_leak_rate: f32,
        speed: f32,
        efficiency: f32,
    ) -> Self {
        assert!(fuel_remaining >= 0);
        assert!(fuel_leak_rate >= 0);
        assert!(speed > 0);
        assert!(efficiency > 0);
        Self { fuel_remaining, fuel_leak_rate, speed, efficiency }
    }
    fn can_drive(&self, distance: f32) -> bool {
        let time = distance / self.speed;
        let fuel_req = time * self.fuel_leak_rate + distance / self.efficiency;
        fuel_req < self.fuel_remaining
    }
}

What I want to stress here is that the design is extensible:

• First, we've articulated the requirements on our struct in the new function: which arguments must be greater than or equal to zero, possibly equal to zero, and so on.

• Second, we've simplified the functionality to can_drive which just checks whether we can drive a given distance, but we could now imagine adding other functions, like fn drive(&mut self, distance: f32) to actually do the drive, fn out_of_gas(&self) -> bool to check if we are out of gas, fn fill_up(&mut self, new_gas: f32), and so on. These additional features would conceptually align with what the object is designed for.

A Note On Units

Although overkill for this example, another improvement to your design would be to make use of Rust's type system to keep different units separate at compile time. Here's how you would do that: first we define struct wrappers for each different kind of unit we are interested in:

struct Miles(f32):
struct Gallons(f32):
struct Hours(f32);
struct MPH(f32);
struct MPG(f32);

Then we can define operations like multiplication for the particular types which "make sense" to multiply. E.g.:

use std::ops::{Add, Mul};

impl Add for Hours {
    type Output = Self;
    fn add(self, other: Self) -> Self {
        self.0 + other.0
    }
}
impl Mul<Hours> for MPH {
    type Output = Miles;
    fn mul(self, time: Hours) -> Miles {
        self.0 * time.0
    }
}

and so on. The beauty of this approach is that we get a compiler error if we make any arithmetic mistakes, like adding Miles to Hours. And moreover, that comes for free: in the actual running code, Miles and Hours both compile to plain f32 values.

Minutae

In addition to what the other answer said, run cargo clippy! It usually gives very helpful suggestions. Here you can replace remaining: remaining with remaining. It would also be great to see some unit tests.

Answer 2

• Just construct let mut car = Car ... at the beginning of main.
• Do not do unwrap, replace collects with collecting to Result<Vec<A>, E> and run ? on the result. Return Result<(), E> from main. You may use a crate such as anyhow. Look into error handling in parsing in this solution Advent of Code 2020 - Day 3: tobogganing down a slope

impl<A, E, V> FromIterator<Result<A, E>> for Result<V, E>
where
    V: FromIterator<A>,

• Instead of implementing parsing on your own, look into crates such as parse-display, reformation or recap.
• For in_range, I would do a max on an iterator, so that the code is functional rather than imperatively stateful with the res variable.
• a typo efficiancy -> efficiency