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

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

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

                         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!()
    }
}

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

създадат контролера и всички дронове, извиквайки DroneController::create_drone()
извикат методите 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] as &[i32]

                let mut scanner = scanner_from_chunks(chunks.into_iter());

                drone0.explore(&mut scanner);

            s.spawn(move || {

                let chunks = vec![

                    &[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, 0, 0] as &[i32]

                let mut scanner = scanner_from_chunks(chunks.into_iter());

                drone0.explore(&mut scanner);

            s.spawn(move || {

                let chunks = vec![

                    &[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![

                    &[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,

                    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

    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,

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

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

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