// Ferry Loading
// Before bridges were common, ferries were used to transport cars across rivers.
// River ferries, unlike their larger cousins, run on a guide line and are powered by the
// river's current. Cars drive onto the ferry from one end, the ferry crosses the river, and
// the cars exit from the other end of the ferry.
// There is an l-meter-long ferry that crosses the river. A car may arrive at either
// river bank to be transported by the ferry to the opposite bank. The ferry travels
// continuously back and forth between the banks so long as it is carrying a car or there
// is at least one car waiting at either bank. Whenever the ferry arrives at one of the
// banks, it unloads its cargo and loads up cars that are waiting to cross as long as they
// fit on its deck. The cars are loaded in the order of their arrival and the ferry's deck
// accommodates only one lane of cars. The ferry is initially on the left bank where it
// had mechanical problems and it took quite some time to fix it. In the meantime, lines
// of cars formed on both banks that wait to cross the river.
// The first line of input contains c, the number of test cases. Each test case begins
// with the number l, a space and then the number m. m lines follow describing the cars
// that arrive in this order to be transported. Each line gives the length of a car (in
// centimeters), and the bank at which the car awaits the ferry ("left" or "right").
// For each test case, output one line giving the number of times the ferry has to cross
// the river in order to serve all waiting cars.
// Sample input
// 4
// 20 4
// 380 left
// 720 left
// 1340 right
// 1040 left
// 15 4
// 380 left
// 720 left
// 1340 right
// 1040 left
// 15 4
// 380 left
// 720 left
// 1340 left
// 1040 left
// 15 4
// 380 right
// 720 right
// 1340 right
// 1040 right
use std::collections::LinkedList;
use std::error::Error;
use std::io::BufRead;
#[derive(Debug, PartialEq, Eq)]
enum RiverBank {
Left,
Right,
}
impl RiverBank {
fn try_from(value: &str) -> Result<RiverBank, Box<Error>> {
match value {
"left" => Ok(RiverBank::Left),
"right" => Ok(RiverBank::Right),
_ => Err("A river bank must either be \"left\" or \"right\"".into()),
}
}
fn switch(&self) -> RiverBank {
match self {
&RiverBank::Left => RiverBank::Right,
&RiverBank::Right => RiverBank::Left,
}
}
}
type CarLength = u64;
type FerryLength = u64;
#[derive(Debug)]
struct StartingCarState {
river_bank: RiverBank,
car_length: CarLength,
}
#[derive(Debug)]
struct FerryProblem {
ferry_length: FerryLength,
car_descriptions: Vec<StartingCarState>,
}
fn read_input(from: impl BufRead) -> Result<Vec<FerryProblem>, Box<Error>> {
let mut lines = from.lines();
let first_line = match lines.next() {
Some(Ok(line)) => line,
Some(Err(err)) => {
return Err(err.into());
}
None => return Err("There was no first line provided to stdin".into()),
};
let number_of_test_cases: u64 = first_line
.parse()
.map_err(|_| "The first line needs to be a single non-negative number.")?;
let mut ferry_problems = Vec::new();
for _ in 0..number_of_test_cases {
let ferry_description_line = match lines.next() {
Some(Ok(line)) => line,
Some(Err(err)) => {
return Err(err.into());
}
None => {
return Err("Ran out of input when parsing test cases".into());
}
};
let (ferry_length, number_of_cars) = {
let split_by_whitespace: Vec<&str> = ferry_description_line.split("\\w+").collect();
if split_by_whitespace.len() == 2 {
let mut ferry_length = split_by_whitespace[0].parse()?;
ferry_length *= 100;
let number_of_cars: u64 = split_by_whitespace[1].parse()?;
(ferry_length, number_of_cars)
} else {
return Err("Malformed ferry description line".into());
}
};
let mut car_descriptions = Vec::new();
for _ in 0..number_of_cars {
let car_description_line = match lines.next() {
Some(Ok(line)) => line,
Some(Err(err)) => {
return Err(err.into());
}
None => return Err("Not enough descriptions of cars given".into()),
};
let car_state = {
let split_by_whitespace: Vec<&str> = car_description_line.split("\\w+").collect();
if split_by_whitespace.len() == 2 {
let car_length = split_by_whitespace[0].parse()?;
let river_bank = RiverBank::try_from(split_by_whitespace[1])?;
StartingCarState {
river_bank: river_bank,
car_length: car_length,
}
} else {
return Err("Malformed car description line".into());
}
};
car_descriptions.push(car_state);
}
ferry_problems.push(FerryProblem {
ferry_length,
car_descriptions,
})
}
Ok(ferry_problems)
}
#[derive(Debug)]
enum FerryProblemSolution {
RequiredTrips(u64),
Impossible,
}
fn required_crossings(problem: FerryProblem) -> FerryProblemSolution {
let mut left_bank: LinkedList<CarLength> = problem
.car_descriptions
.iter()
.filter(|car| car.river_bank == RiverBank::Left)
.map(|car| car.car_length)
.collect();
let mut right_bank: LinkedList<CarLength> = problem
.car_descriptions
.iter()
.filter(|car| car.river_bank == RiverBank::Right)
.map(|car| car.car_length)
.collect();
let mut bank = RiverBank::Left;
let mut used_capacity = 0;
let mut trips_made = 0;
loop {
let next_car = match bank {
RiverBank::Left => left_bank.pop_front(),
RiverBank::Right => right_bank.pop_front(),
};
match next_car {
Some(car) => {
if car > problem.ferry_length {
return FerryProblemSolution::Impossible;
} else if car + used_capacity > problem.ferry_length {
trips_made += 1;
used_capacity = 0;
match bank {
RiverBank::Left => left_bank.push_front(car),
RiverBank::Right => right_bank.push_front(car),
};
bank = bank.switch()
} else {
used_capacity += car;
}
}
None => {
trips_made += 1;
let other_bank_is_empty = match bank {
RiverBank::Left => right_bank.is_empty(),
RiverBank::Right => left_bank.is_empty(),
};
if other_bank_is_empty {
return FerryProblemSolution::RequiredTrips(trips_made);
} else {
used_capacity = 0;
bank = bank.switch()
}
}
}
}
}
fn main() -> Result<(), Box<Error>> {
let test_input = "4
20 4
380 left
720 left
1340 right
1040 left
15 4
380 left
720 left
1340 right
1040 left
15 4
380 left
720 left
1340 left
1040 left
15 4
380 right
720 right
1340 right
1040 right
";
/* replace with io::stdin().lock() for real input */
let problems = read_input(test_input.as_bytes())?;
for problem in problems {
let solution = required_crossings(problem);
match solution {
FerryProblemSolution::Impossible => println!("There is no solution"),
FerryProblemSolution::RequiredTrips(trips) => println!("{}", trips),
}
}
Ok(())
}