Hello again dear fellows from the Rust community.
In my last Topic (Sorting Vector of vectors of f64 - #8 by dzamlo) we talked about creating a vector of vectors from user input for using in a fractional knapsack algorithm. One of the suggestions was that instead of collecting the data as a vector and then pushing each entry into another vector, I should use structs to do this, since it would make the code cleaner.....etc.
Just to remind you, the user would input data in the following manner:
First line would contain the number of items (N) and the total capacity of the knapsack
N following lines would contain the Value and Weight of each item.
These would get parsed and collected into a vector. Now I did the same thing with structs, but there are some things I didn't quite get yet. Here is the code (the text continues after the code).
use std::io;
use std::str::FromStr;
use std::cmp::Ordering;
struct Items {
value: f64 ,
weight: f64,
score: f64,
}
struct Capacity {
nitems: f64 ,
maxweight: f64,
}
impl Items {
fn new() -> Items {
let values = Items::read_values().unwrap();
Items {value: values[0], weight: values[1], score: values[0]/values[1]}
}
fn read_values<T: FromStr>() -> Result<Vec<T>, T::Err> {
let mut s = String::new();
io::stdin().read_line(&mut s).expect("Could not read Item from stdin");
s.trim().split_whitespace().map(|word| word.parse()).collect()
}
}
impl Capacity {
fn new() -> Capacity {
let values = Capacity::read_values().unwrap();
Capacity {nitems: values[0], maxweight: values[1]}
}
fn read_values<T: FromStr>() -> Result<Vec<T>, T::Err> {
let mut s = String::new();
io::stdin().read_line(&mut s).expect("Could not read Item from stdin");
s.trim().split_whitespace().map(|word| word.parse()).collect()
}
}
fn comp_f64(a: &f64, b: &f64) -> Ordering {
if a < b {
return Ordering::Less;
} else if a > b {
return Ordering::Greater;
}
Ordering::Equal
}
fn input_parser() -> (Vec<Items>, Capacity) {
let capacity = Capacity::new();
let mut items:Vec<Items> = Vec::with_capacity(capacity.nitems as usize);
for _ in 0..items.capacity() {
let mut values = Items::new();
items.push(values);
};
items.sort_by(|a, b| comp_f64(&a.score,&b.score));
(items, capacity)
}
fn fract_knapsack(items: Vec<Items>, capacity:Capacity) {
let mut result = 0f64;
let mut tweight = 0f64;
let maxweight = capacity.maxweight;
for item in items.iter().rev() {
if tweight < maxweight && maxweight - tweight >= item.weight {
result += item.value;
tweight += item.weight;
} else if maxweight - tweight < item.weight {
result += item.value * ((maxweight - tweight) / item.weight);
tweight += item.weight * ((maxweight - tweight) / item.weight);
}
if tweight == maxweight {
break;
}
}
println!("{:.4}", result);
}
fn main() {
let (items, capacity) = input_parser();
fract_knapsack(items, capacity);
}
Before I wrote this version, I tried writing an alternative version of the read_values function that would take the parsed values from stdin and create the struct without collecting into a vector first. My first very naive attempt was to replace the
s.trim().split_whitespace().map(|word| word.parse()).collect()
by
s.trim().split_whitespace().map(|word| word.parse()).collect::()
Rust told me that a collection of type Capacity cannot be built from an iterator over elements of type 'std::result::Result<_, _>'
My second attempt was to use another map function to map the values into the struct, but I didn't get very far with that either.
Do you guys think that's possible?
Ok. I didn't really do the entire ToDo list, but here is goes. I removed the knapsack part so that you guys can focus on the troubling part.
#![allow(unused_imports)]
use std::io;
use std::str::FromStr;
use std::cmp::Ordering;
use std::num::{ParseIntError, ParseFloatError};
struct Items {
value: f64 ,
weight: f64,
score: f64,
}
impl Items {
fn read_values() -> String {
let mut s = String::new();
io::stdin().read_line(&mut s).expect("Could not read line from stdin");
s.to_owned()
}
}
impl FromStr for Items {
type Err = ParseFloatError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let input: Vec<&str> = s.split_whitespace().collect();
let value = input[0].parse::<f64>()?;
let weight = input[1].parse::<f64>()?;
Ok(Items {value: value, weight: weight, score: value/weight})
}
}
struct Capacity {
nitems: f64,
maxweight: f64,
}
impl Capacity {
fn read_values<T: FromStr>() -> String {
let mut s = String::new();
io::stdin().read_line(&mut s).expect("Could not read line from stdin");
s.to_owned()
}
}
impl FromStr for Capacity {
type Err = ParseFloatError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let input: Vec<&str> = s.split_whitespace().collect();
let nitems = input[0].parse::<f64>()?;
let maxweight = input[1].parse::<f64>()?;
Ok(Capacity {nitems: nitems, maxweight: maxweight})
}
}
fn input_parser() -> (Vec<Items>, Capacity) {
let capacity = Capacity::from_str(&Capacity::read_values::<f64>()).expect("Error obtaining values from String");
let mut items:Vec<Items> = Vec::with_capacity(capacity.nitems as usize);
for _ in 0..items.capacity() {
let mut values = Items::from_str(&Items::read_values()).expect("Error obtaining values from String");
items.push(values);
};
items.sort_by(|a, b| comp_f64(&a.score,&b.score));
(items, capacity)
}
fn comp_f64(a: &f64, b: &f64) -> Ordering {
if a < b {
return Ordering::Less;
} else if a > b {
return Ordering::Greater;
}
Ordering::Equal}
fn main() {
let (item,capacity) = input_parser();
}
The code works, but I still have some doubts.
One of them would be:
Originally I intended in defining the Capacity struct with nitems as a usize value.
I just could not figure out how to do that, mainly because I had to define the type Err within the impl FromStr for Capacity. If I use a usize value for nitems and a f64 for maxweight, the Err type should be ParseIntError and ParseFloatError respectively. I thought about a match statement but I didn't really figure out how.
Other than that, any comments on the code would be nice.
Thank you
Fabrício
Ps: Wrote this in a hurry because my ride was already going (sorry for any confusion or typos).
Hi there. I've update the code to not use vectors in order to capture stdin. So the final implementation of FromStr became this:
impl FromStr for Capacity {
type Err = ParseFloatError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut words = s.split_whitespace();
let nitems = words.next().unwrap().parse()?;
let maxweight = words.next().unwrap().parse()?;
Ok(Capacity {nitems: nitems, maxweight: maxweight})
}
}
Sorry I took so long to reply, but I had no idea how I would implement the type Err for both f64 and i64, so, I went to study a bit. I searched some hints on the Programming-Rust book and the Rust Book, but, in the end, I was finally defeated by my own lack of knowledge. I just couldn't figure out how to do this.
I know that you can wrap an existing struct into an enum. Something like
but try it yourself - better learning exercise.