Решение на Домашно 1 - търсене на съкровища от Иван Коджабашев
Към профила на Иван Коджабашев
Резултати
- 20 точки от тестове
- 0 бонус точки
- 20 точки общо
- 5 успешни тест(а)
- 0 неуспешни тест(а)
Код
use std::collections::HashMap;
use std::collections::HashSet;
use std::sync::{
Arc,
atomic::{AtomicBool, Ordering},
mpsc,
};
fn main() {}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct TreasureLoc {
pub lane_index: usize,
pub cell_coord: usize,
pub value: i32,
}
#[derive(Debug, PartialEq, Eq)]
pub enum FoundTreasures {
Big(TreasureLoc),
Small(Vec<TreasureLoc>),
Nothing,
}
pub struct Scan<'a> {
// coord of first element in `cells`
pub start_coord: usize,
pub cells: &'a [i32],
}
#[derive(Debug)]
enum Msg {
Found(TreasureLoc),
Done { lane_index: usize },
}
pub struct Drone {
lane_index: usize,
tx: mpsc::Sender<Msg>,
stop: Arc<AtomicBool>,
}
impl Drone {
pub fn explore(&mut self, scanner: &mut dyn Iterator<Item = Scan<'_>>) {
for scan in scanner {
if self.stop.load(Ordering::Relaxed) {
break;
}
for (i, &value) in scan.cells.iter().enumerate() {
if self.stop.load(Ordering::Relaxed) {
break;
}
if value > 0 {
let loc = TreasureLoc {
lane_index: self.lane_index,
cell_coord: scan.start_coord + i,
value,
};
if self.tx.send(Msg::Found(loc.clone())).is_err() {
self.stop.store(true, Ordering::Relaxed);
break;
}
if value >= 999 {
self.stop.store(true, Ordering::Relaxed);
break;
}
}
}
}
let _ = self.tx.send(Msg::Done {
lane_index: self.lane_index,
});
}
}
pub struct DroneController {
tx: mpsc::Sender<Msg>,
rx: mpsc::Receiver<Msg>,
stop: Arc<AtomicBool>,
drones_created: usize,
}
impl DroneController {
pub fn new() -> Self {
let (tx, rx) = mpsc::channel();
Self {
tx,
rx,
stop: Arc::new(AtomicBool::new(false)),
drones_created: 0,
}
}
pub fn create_drone(&mut self, lane_index: usize) -> Drone {
self.drones_created += 1;
Drone {
lane_index,
tx: self.tx.clone(),
stop: Arc::clone(&self.stop),
}
}
pub fn run(&mut self) -> FoundTreasures {
let mut done_count = 0usize;
let mut best_by_lane: HashMap<usize, TreasureLoc> = HashMap::new();
let mut sum_small: i32 = 0;
let mut solution: Option<FoundTreasures> = None;
while done_count < self.drones_created {
let msg = self.rx.recv();
if msg.is_err() {
break;
}
let msg = msg.unwrap();
if let Msg::Found(loc) = msg {
if solution.is_some() {
continue;
}
if loc.value >= 999 {
solution = Some(FoundTreasures::Big(loc));
self.stop.store(true, Ordering::Relaxed);
continue;
}
let lane = loc.lane_index;
if !best_by_lane.contains_key(&lane) {
sum_small += loc.value;
best_by_lane.insert(lane, loc);
} else {
let existing = best_by_lane.get(&lane).unwrap();
if loc.value > existing.value {
sum_small -= existing.value;
sum_small += loc.value;
best_by_lane.insert(lane, loc);
}
}
if sum_small >= 300 {
let mut selected = Vec::new();
for treasure in best_by_lane.values() {
selected.push(treasure.clone());
}
solution = Some(FoundTreasures::Small(selected));
self.stop.store(true, Ordering::Relaxed);
}
} else if let Msg::Done { .. } = msg {
done_count += 1;
}
}
solution.unwrap_or(FoundTreasures::Nothing)
}
}
const fn assert_send_static<T: Send + 'static>() {}
const _: () = assert_send_static::<DroneController>();
const _: () = assert_send_static::<Drone>();
#[cfg(test)]
mod tests {
use super::*;
use std::thread;
#[test]
fn test_big_treasure() {
let mut drone_ctl = DroneController::new();
let mut drone0 = drone_ctl.create_drone(0);
let mut drone1 = drone_ctl.create_drone(1);
let result = with_timeout(std::time::Duration::from_secs(3), move || {
let handle = thread::spawn(move || drone_ctl.run());
thread::scope(|s| {
s.spawn(move || {
let chunks = vec![&[0, 0, 0, 0, 0, 0], &[0, 0, 0, 0, 0, 0] as &[i32]];
let mut scanner = scanner_from_chunks(chunks.into_iter());
drone0.explore(&mut scanner);
});
s.spawn(move || {
let chunks = vec![&[0, 0, 0, 0, 0, 0], &[0, 999, 0, 0, 0, 0] as &[i32]];
let mut scanner = scanner_from_chunks(chunks.into_iter());
drone1.explore(&mut scanner);
});
});
handle.join().unwrap()
});
assert_eq!(
result,
FoundTreasures::Big(TreasureLoc {
lane_index: 1,
cell_coord: 7,
value: 999
}),
);
}
#[test]
fn test_small_treasure() {
let mut drone_ctl = DroneController::new();
let mut drone0 = drone_ctl.create_drone(0);
let mut drone1 = drone_ctl.create_drone(1);
let mut drone2 = drone_ctl.create_drone(2);
let result = with_timeout(std::time::Duration::from_secs(3), move || {
let handle = thread::spawn(move || drone_ctl.run());
thread::scope(|s| {
s.spawn(move || {
let chunks = vec![&[0, 0, 0, 0, 100, 0], &[0, 0, 0, 0, 0, 0] as &[i32]];
let mut scanner = scanner_from_chunks(chunks.into_iter());
drone0.explore(&mut scanner);
});
s.spawn(move || {
let chunks = vec![&[0, 0, 0, 0, 0, 0], &[0, 100, 0, 0, 0, 0] as &[i32]];
let mut scanner = scanner_from_chunks(chunks.into_iter());
drone1.explore(&mut scanner);
});
s.spawn(move || {
let chunks = vec![
&[0, 0, 0, 0, 0, 0],
&[0, 0, 0, 50, 0, 0],
&[100, 0, 0, 0, 0, 0] as &[i32],
];
let mut scanner = scanner_from_chunks(chunks.into_iter());
drone2.explore(&mut scanner);
});
});
handle.join().unwrap()
});
match result {
FoundTreasures::Small(mut treasures) => {
treasures.sort_by_key(|t| t.lane_index);
assert_eq!(
treasures,
vec![
TreasureLoc {
lane_index: 0,
cell_coord: 4,
value: 100
},
TreasureLoc {
lane_index: 1,
cell_coord: 7,
value: 100
},
TreasureLoc {
lane_index: 2,
cell_coord: 12,
value: 100
},
]
);
}
_ => panic!("assertion failed\nexpected: FoundTreasures::Small(_)\nfound: {result:?}"),
}
}
fn with_timeout<F, T>(timeout: std::time::Duration, f: F) -> T
where
F: FnOnce() -> T + Send + std::panic::UnwindSafe + 'static,
T: Send + 'static,
{
let (sender, receiver) = std::sync::mpsc::sync_channel(1);
let _ = std::thread::spawn(move || {
let catch_result = std::panic::catch_unwind(f);
sender.send(catch_result).unwrap();
});
match receiver.recv_timeout(timeout) {
Ok(Ok(val)) => val,
Ok(Err(panic_payload)) => std::panic::resume_unwind(panic_payload),
Err(std::sync::mpsc::RecvTimeoutError::Timeout) => panic!("test timeout"),
Err(std::sync::mpsc::RecvTimeoutError::Disconnected) => unreachable!(),
}
}
fn scanner_from_chunks<'a>(
chunks: impl Iterator<Item = &'a [i32]>,
) -> impl Iterator<Item = Scan<'a>> {
chunks
.scan(0, |sum, chunk| {
let start_index = *sum;
*sum += chunk.len();
Some((start_index, chunk))
})
.map(|(start_index, chunk)| Scan {
start_coord: start_index,
cells: chunk,
})
}
}
Лог от изпълнението
Updating crates.io index
Locking 46 packages to latest compatible versions
Compiling proc-macro2 v1.0.104
Compiling quote v1.0.42
Compiling unicode-ident v1.0.22
Compiling libc v0.2.178
Compiling syn v2.0.111
Compiling futures-core v0.3.31
Compiling futures-sink v0.3.31
Compiling parking_lot_core v0.9.12
Compiling pin-project-lite v0.2.16
Compiling futures-channel v0.3.31
Compiling futures-task v0.3.31
Compiling scopeguard v1.2.0
Compiling cfg-if v1.0.4
Compiling slab v0.4.11
Compiling smallvec v1.15.1
Compiling pin-utils v0.1.0
Compiling futures-io v0.3.31
Compiling memchr v2.7.6
Compiling lock_api v0.4.14
Compiling errno v0.3.14
Compiling signal-hook-registry v1.4.8
Compiling parking_lot v0.12.5
Compiling mio v1.1.1
Compiling futures-macro v0.3.31
Compiling tokio-macros v2.6.0
Compiling futures-util v0.3.31
Compiling socket2 v0.6.1
Compiling bytes v1.11.0
Compiling tokio v1.48.0
Compiling futures-executor v0.3.31
Compiling futures v0.3.31
Compiling solution v0.1.0 (/tmp/d20251229-4108951-1im3ujm/solution)
warning: unused import: `std::collections::HashSet`
--> src/lib.rs:2:5
|
2 | use std::collections::HashSet;
| ^^^^^^^^^^^^^^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: function `main` is never used
--> src/lib.rs:9:4
|
9 | fn main() {}
| ^^^^
|
= note: `#[warn(dead_code)]` on by default
warning: field `lane_index` is never read
--> src/lib.rs:34:12
|
34 | Done { lane_index: usize },
| ---- ^^^^^^^^^^
| |
| field in this variant
|
= note: `Msg` has a derived impl for the trait `Debug`, but this is intentionally ignored during dead code analysis
warning: function `assert_send_static` is never used
--> src/lib.rs:168:10
|
168 | const fn assert_send_static<T: Send + 'static>() {}
| ^^^^^^^^^^^^^^^^^^
warning: `solution` (lib) generated 4 warnings (run `cargo fix --lib -p solution` to apply 1 suggestion)
Finished `test` profile [unoptimized + debuginfo] target(s) in 17.95s
Running tests/solution_test.rs (target/debug/deps/solution_test-f512224d9fb3caf8)
running 5 tests
test solution_test::test_big_treasure ... ok
test solution_test::test_nothing ... ok
test solution_test::test_small_treasure ... ok
test solution_test::test_small_treasure_2 ... ok
test solution_test::test_return_immediately_when_found ... ok
test result: ok. 5 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.10s