Derive + Generic структури

Програмиране с Rust

Курс във Факултета по Математика и Информатика към СУ

Домашно 1 - търсене на съкровища

Предадени решения

Краен срок:
23.12.2025 23:59
Точки:
20

Срокът за предаване на решения е отминал

use solution::*;
use std::panic::UnwindSafe;
use std::sync::mpsc;
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],
&[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: 6, value: 100 },
]
);
}
_ => panic!("assertion failed\nexpected: FoundTreasures::Small(_)\nfound: {result:?}"),
}
}
#[test]
fn test_small_treasure_2() {
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![
&[10], &[20], &[30], &[40], &[50], &[60], &[70], &[80], &[90], &[100],
&[110], &[120], &[130], &[140], &[150], &[160], &[170], &[180], &[190], &[200] as &[i32]
];
let mut scanner = scanner_from_chunks(chunks.into_iter());
drone0.explore(&mut scanner);
});
s.spawn(move || {
let chunks = vec![
&[10], &[20], &[30], &[40], &[50], &[60], &[70], &[80], &[90], &[100],
&[110], &[120], &[130], &[140], &[150], &[160], &[170], &[180], &[190], &[200] as &[i32]
];
let mut scanner = scanner_from_chunks(chunks.into_iter());
drone1.explore(&mut scanner);
});
});
handle.join().unwrap()
});
match result {
FoundTreasures::Small(treasures) => {
assert_eq!(treasures.len(), 2);
assert!(treasures.iter().map(|loc| loc.value).sum::<i32>() >= 300);
}
_ => panic!("assertion failed\nexpected: FoundTreasures::Small(_)\nfound: {result:?}"),
}
}
#[test]
fn test_nothing() {
let mut drone_ctl = DroneController::new();
let drone0 = drone_ctl.create_drone(0);
let 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| {
for mut drone in [drone0, drone1] {
s.spawn(move || {
let chunks = vec![
&[0, 0, 10, 0, 0, 0],
&[0, 0, 0, 10, 0, 0] as &[i32]
];
let mut scanner = scanner_from_chunks(chunks.into_iter());
drone.explore(&mut scanner);
});
}
});
handle.join().unwrap()
});
assert_eq!(result, FoundTreasures::Nothing);
}
#[test]
fn test_return_immediately_when_found() {
let mut drone_ctl = DroneController::new();
let mut drone0 = drone_ctl.create_drone(0);
let mut drone1 = drone_ctl.create_drone(1);
with_timeout(std::time::Duration::from_secs(3), move || {
let handle_ctl = thread::spawn(move || drone_ctl.run());
let (drone0_sender, handle0) = {
let (sender, receiver) = mpsc::channel();
let mut scanner = scanner_from_chan(receiver);
let h = thread::spawn(move || drone0.explore(&mut scanner));
(sender, h)
};
let (drone1_sender, handle1) = {
let (sender, receiver) = mpsc::channel();
let mut scanner = scanner_from_chan(receiver);
let h = thread::spawn(move || drone1.explore(&mut scanner));
(sender, h)
};
drone0_sender.send(&[999]).unwrap();
drone1_sender.send(&[0]).unwrap();
// Даваме време на обектите да си изпратят нужните съобщения и сигнали
std::thread::sleep(std::time::Duration::from_millis(100));
let _ = drone0_sender.send(&[0]);
let _ = drone1_sender.send(&[0]);
// Очаква се DroneController::run да e върнал веднага след като е намерено съкровището
let result = handle_ctl.join().unwrap();
assert_eq!(result, FoundTreasures::Big(TreasureLoc { lane_index: 0, cell_coord: 0, value: 999 }));
// Очаква се Drone::explore да са прекратили търсенето, въпреки, че итератора не е достигнал края си
handle0.join().unwrap();
handle1.join().unwrap();
});
}
fn with_timeout<F, T>(timeout: std::time::Duration, f: F) -> T
where
F: FnOnce() -> T + Send + 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,
})
}
fn scanner_from_chan<'a>(chan: mpsc::Receiver<&'a [i32]>) -> impl Iterator<Item = Scan<'a>> {
chan
.into_iter()
.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,
})
}

Златко търси съкровища с дрони. Помогнете му да намери съкровищата намиращи се на острова.

                         X
  +——————————————————————>
  | ~ ~ ~ д→. . . ♣ ♣ ♣
  | ~ ≈ ~ д→. . ♠ ♠ ♣ ♣
  | ~ ≈ ~ д→. . ♠ ♠ *3♣
  | ~ ~ ~ д→. . . ♠ ♠ *8
  | ~ ~ ≈ д→. . . ♠ ♣ ♠
  | ~ ~ ≈ д→. . . ♣ ♠ ♣
  | ~ ≈ ~ д→. . . ♠ ♣ ♣
  | ~ ~ ~ д→. ♠ . ♠ *5♣
  | ~ ≈ ~ д→. . . ♠ ♠ ♣
Y v

(имаше повече смисъл от тази диаграма в предишна чернова на задачата)

Златко мисловно е разделил картата на острова на коридори.
Във всеки коридор е поставил по един дрон. Дроновете сканират повърхността и получават поредица от числови стойности, където 0 означава нищо, а положително число означава, че е намерено съкровище със съответната стойност.

Златко разграничава два вида съкровища - малки (стойност < 999) и големи (стойност >= 999).
Целта му е да намери едно от следните:

  • едно голямо съкровище
  • произволен брой малки съкровища със обща стойност поне 300

Решението трябва да съдържа координатите и стойностите на всички избрани съкровища.
Поради ограничената товароносимост на дроновете, от всеки коридор може да бъде избрано най-много едно съкровище.

Острова може да бъде безкрайно голям, затова не може да бъде обходен целия. Ако в даден момент бъде намерено решение (едно голямо съкровище или множество малки със стойност >= 300), претърсването трябва да бъде прекратено и да се върне намереното решение. Търси се първото решение, а не най-доброто.
FoundTreasures::Nothing трябва да се върне само ако оствора е крайно голям и бъде обходен целия, без да е намерено решение.

Общи типове:

#[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,
}

Дрон - работи самостоятелно, сканира картата и предава информация на контролера.
scanner може да е краен или безкраен итератор.

pub struct Scan<'a> {
    // coord of first element in `cells`
    pub start_coord: usize,
    pub cells: &'a [i32],
}

pub struct Drone {
    // ...
}

impl Drone {
    pub fn explore(&mut self, scanner: &mut dyn Iterator<Item = Scan<'_>>) {
        todo!()
    }
}

Контролер - контролира дроновете и събира информацията от тях. Връща решението на задачата.

pub struct DroneController {
    // ...
}

impl DroneController {
    pub fn new() -> Self {
        todo!()
    }

    pub fn create_drone(&mut self, lane_index: usize) -> Drone {
        todo!()
    }

    pub fn run(&mut self) -> FoundTreasures {
        todo!()
    }
}

Задачата ще работи по следния начин. Тестовете ще:

  1. създадат контролера и всички дронове, извиквайки DroneController::create_drone()
  2. извикат методите DroneController::run() и Drone::explore(). Тези методи се очаква да работят паралелно. Няма предвиден начин за комуникация между тях - за това трябва да се погрижите сами.

Задачата се счита за решена, когато:

  • всички дронове са излезли от exlore() метода си
  • контролера е върнал резултат от run() метода си

Тестовете ще изискват типовете Drone и DroneControler да имплементират Send + 'static (от къде ви е познато това ограничение - hint - thread::spawn). Един вариант да се подсигурите за това е да си направите ad hoc static assertion по следния начин:

const fn assert_send_static<T: Send + 'static>() {}
const _: () = assert_send_static::<DroneController>();
const _: () = assert_send_static::<Drone>();

За разлика от упражненията, за това домашно напълно важат указанията по-долу. Специфично всички типове и функции, които се използват от теста трябва да са публично видими.
Базовия тест е само примерен, финалния тест ще съдържа повече проверки.

Задължително прочетете (или си припомнете): Указания за предаване на домашни

Погрижете се решението ви да се компилира с базовия тест:

use solution::*;
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,
})
}