Решение задачи №90 от UniLecs

garden_bed_of_beetroot.rs

type FieldLen = u32;

#[deny(overflowing_literals)]
//Ограничение на максимальную длину входных данных
const FIELD_BOUND: FieldLen = 5_000 - 1;

#[derive(Debug, PartialEq)]
enum SideDir { //Возможные направления стороны поля
    NS, //С севера на юг (north-south)
    WE, //С запада на восток (west-east)
}

#[derive(Debug, PartialEq)]
struct FieldRect { //Тип прямоугольного участка на поле
    ns: FieldLen, //Длина вдоль направления север-юг
    we: FieldLen, //Длина вдоль направления запад-восток
}

impl FieldRect {
    //Проверяет, что self умещается в other. Если не умещается — 
    //возвращает направление, по которому не укладывается
    fn limit_by(&self, other: &Self) -> Result<(), SideDir> {
        if self.ns > other.ns {
            return Err(SideDir::NS);
        }
        if self.we > other.we {
            return Err(SideDir::WE);
        }
        Ok(())
    }
    
    //Проверяет, что обе стороны ненулевые. Возвращает направление
    //нулевой стороны, если таковая имеется
    fn check_zero(&self) -> Result<(), SideDir> {
        if self.ns == 0 {
            return Err(SideDir::NS);
        }
        if self.we == 0 {
            return Err(SideDir::WE);
        }
        Ok(())
    }
}

//Максимально возможные размеры поля
const FIELD_RECT_BOUND: FieldRect = FieldRect {
    ns: FIELD_BOUND,
    we: FIELD_BOUND,
};

#[derive(Debug, PartialEq)]
struct Field(FieldRect); //Тип, описывающий поле — newtype на FieldRect
//Несколько методов для упрощения кода.
//Ручной имплементации этих методов можно было бы избежать,
//используя библиотеку вроде derive_more, но таких нет
//на playground-е
impl ::std::ops::Deref for Field {
    type Target = FieldRect;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}
impl ::std::convert::From<FieldRect> for Field {
    fn from(fr: FieldRect) -> Self {
        Field(fr)
    }
}

#[derive(Debug, PartialEq)]
struct Bed(FieldRect); //Тип, описывающий грядку — newtype на FieldRect
//Обладает существенным пока не устранённым недостатком — не содержит информации
//о типе выращиваемой на грядке сельхозкультуры.
impl ::std::ops::Deref for Bed {
    type Target = FieldRect;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}
impl ::std::convert::From<FieldRect> for Bed {
    fn from(fr: FieldRect) -> Self {
        Bed(fr)
    }
}

#[derive(Debug, PartialEq)]
enum BedPosError { //Возможные ошибки при решении задачи
    LargeField(SideDir),        //Поле по указанному направлению больше FIELD_BOUND
    LargeBed(SideDir),          //Грядка по указанному направлению больше FIELD_BOUND
    BedLargerField(SideDir),    //Грядка по указанному направлению больше поля
    ZeroField(SideDir),         //Сторона поля по указанному направлению нулевая
    ZeroBed(SideDir),           //Сторона грядки по указанному направлению нулевая
    NotInField(SideDir, usize), //Занятый квадрат с указанным индексом находится
                                //за пределами поля
}

//Информация о занятых квадратах — слайс с координатами
type Occupied<'a> = &'a [(FieldLen, FieldLen)];

//Возвращает количество способов разместить грядку bed на поле field,
//не занимая ни один из уже занятых квадратов, перечисленных в occupied.
//Внимание! Ожидается, что координаты занятых квадратов начинаются от нуля
//и что первое число в паре — координата по направлению с запада на восток.
//Внимание! Внутри функции не совершается проверка на уникальность координат
//занятых квадратов.
fn count_bed_positions(field: &Field, bed: &Bed, occupied: Occupied) -> Result<usize, BedPosError> {
    use std::collections::HashSet;
    use BedPosError::*;

    //Проверяем, что у поля и грядки разумные размеры
    field.check_zero().map_err(ZeroField)?;
    bed.check_zero().map_err(ZeroBed)?;

    field.limit_by(&FIELD_RECT_BOUND).map_err(LargeField)?;
    bed.limit_by(&FIELD_RECT_BOUND).map_err(LargeBed)?;
    bed.limit_by(field).map_err(BedLargerField)?;

    //Координаты северо-западного угла грядки (в квадратах)
    //лежат в [0, bed_limits.we] x [0, bed_limiys.ns]
    let bed_limits = FieldRect {
        ns: field.0.ns - bed.0.ns,
        we: field.0.we - bed.0.we,
    };
    //excluded содержит координаты квадратов, которые не могут быть северо-западными
    //углами грядок из-за того, что некоторые квадраты под грядку уже заняты
    let mut excluded = HashSet::new();
    for (i, &(we, ns)) in occupied.iter().enumerate() {
        //Проверяем, что занятый квадрат находится в пределах поля
        FieldRect{ ns, we }.limit_by(field).map_err(|dir| NotInField(dir, i))?;

        //Помечаем квадраты, которые не могут быть северо-западными углами грядок.
        //Это все квадраты, ограниченные прямоугольником от квадрата
        //(we - (bed.we - 1), ns - (bed.ns - 1)) до квадрата (we, ns)
        //с поправкой на границы поля
        for x in we.saturating_sub(bed.0.we - 1)..=we.min(bed_limits.we) {
            for y in ns.saturating_sub(bed.0.ns - 1)..=ns.min(bed_limits.ns) {
                excluded.insert((x, y));
            }
        }
    }

    //Число возможных размещений равно числу размещений, разрешённых
    //соотношениями размеров поля и грядки, минус число размещений,
    //запрещённых занятыми квадратами
    let count = ((bed_limits.ns + 1) * (bed_limits.we + 1)) as usize - excluded.len();
    Ok(count)
}

//Вспомогательная функция для тестирования.
//Возвращает список занятых квадратов по строковому представлению поля
fn parse_occupied(input: &str) -> Vec<(FieldLen, FieldLen)> {
    let mut res = Vec::new();
    for (s, j) in input.lines().filter(|s| !s.is_empty()).zip(0..) {
        for (b, i) in s.bytes().filter(|b| !b.is_ascii_whitespace()).zip(0..) {
            match b {
                b'#' => res.push((i, j)),
                b'.' => (),
                _ => panic!("Unrecognized character {} at ({}, {})", b as char, i, j),
            }
        }
    }
    res
}

//Вспомогательная функция для тестирования.
//Корректирует индексы с one-based на zero-based
fn to_zero_based(squares: &mut [(FieldLen, FieldLen)]) {
    for pair in squares {
        pair.0 -= 1;
        pair.1 -= 1;
    }
}

#[test]
fn some_variants() {
    let field = FieldRect { ns: 3, we: 4 }.into();
    let bed = FieldRect { ns: 1, we: 2 }.into();
    let occupied = parse_occupied(r#"
        #...
        ..#.
        ....
    "#);
    assert_eq!(count_bed_positions(&field, &bed, &occupied), Ok(6));

    let field = FieldRect { ns: 4, we: 4 }.into();
    let bed = FieldRect { ns: 2, we: 2 }.into();
    let mut occupied = [(1, 1), (1, 3), (2, 2), (2, 4), (3, 4), (4, 1)];
    to_zero_based(&mut occupied);
    assert_eq!(count_bed_positions(&field, &bed, &occupied), Ok(1));
}

#[test]
fn check_large_errors() {
    use SideDir::*;
    use BedPosError::{LargeField, LargeBed, BedLargerField};
    
    let field = FieldRect{ ns: FIELD_BOUND + 1, we: 1 }.into();
    let bed = FieldRect{ ns: 1, we: 2 }.into();
    let occupied = [];
    assert_eq!(count_bed_positions(&field, &bed, &occupied), Err(LargeField(NS)));
    
    let field = FieldRect{ ns: 3, we: FIELD_BOUND + 1 }.into();
    assert_eq!(count_bed_positions(&field, &bed, &occupied), Err(LargeField(WE)));
    
    let field = FieldRect{ ns: 1, we: 2 }.into();
    let bed = FieldRect{ ns: FIELD_BOUND + 1, we: 1 }.into();
    assert_eq!(count_bed_positions(&field, &bed, &occupied), Err(LargeBed(NS)));
    
    let bed = FieldRect{ ns: 5, we: FIELD_BOUND + 1 }.into();
    assert_eq!(count_bed_positions(&field, &bed, &occupied), Err(LargeBed(WE)));
    
    let field = FieldRect{ ns: 4, we: 5 }.into();
    let bed = FieldRect{ ns: 5, we: 3 }.into();
    assert_eq!(count_bed_positions(&field, &bed, &occupied), Err(BedLargerField(NS)));
    
    let bed = FieldRect{ ns: 2, we: 17 }.into();
    assert_eq!(count_bed_positions(&field, &bed, &occupied), Err(BedLargerField(WE)));
}

#[test]
fn check_zero_errors() {
    use SideDir::*;
    use BedPosError::{ZeroField, ZeroBed};
    
    let field = FieldRect{ ns: 0, we: 5 }.into();
    let bed = FieldRect{ ns: 2, we: 5 }.into();
    let occupied = [];
    assert_eq!(count_bed_positions(&field, &bed, &occupied), Err(ZeroField(NS)));
    
    let field = FieldRect{ ns: 5, we: 0 }.into();
    assert_eq!(count_bed_positions(&field, &bed, &occupied), Err(ZeroField(WE)));
    
    let field = FieldRect{ ns: 2, we: 5 }.into();
    let bed = FieldRect{ ns: 0, we: 5 }.into();
    assert_eq!(count_bed_positions(&field, &bed, &occupied), Err(ZeroBed(NS)));
    
    let bed = FieldRect{ ns: 3, we: 0 }.into();
    assert_eq!(count_bed_positions(&field, &bed, &occupied), Err(ZeroBed(WE)));
}

#[test]
fn check_not_in_field_errors() {
    use SideDir::*;
    use BedPosError::NotInField;
    
    let field = FieldRect{ ns: 16, we: 32 }.into();
    let bed = FieldRect{ ns: 10, we: 16 }.into();
    let occupied = [(0, 0), (100, 2)];
    assert_eq!(count_bed_positions(&field, &bed, &occupied), Err(NotInField(WE, 1)));
    
    let occupied = [(0, 0), (10, 2), (8, 345)];
    assert_eq!(count_bed_positions(&field, &bed, &occupied), Err(NotInField(NS, 2)));
}

Playground (rev. 1): https://play.rust-lang.org/?gist=f1d276e515a5282eb62cebbf32e73b56&version=beta&mode=debug
Playground (rev. 2): https://play.rust-lang.org/?gist=a2d5611f0da6a802b3d8d372fe06e2a3&version=beta&mode=debug