Решение задачи UniLecs №57

count_places.rs

fn count_places(street: &str) -> usize {
    let mut free = vec![true; street.len()]; //заводим вектор, в котором будем писать, свободно ли место
                                             //и инициализируем его истинными значениями
    for (i, a) in street.bytes().enumerate() { //перебираем символы вместе с индексами
        match a {                              //смотрим, что за символ
            b'E' => free[i] = false,                       //если выезд - помечаем соответсвующее место как занятое
            b'S' => {                                      //если остановка - помечаем как занятое
                        free[i]                   = false; //текущее место...
                        free[i.saturating_sub(1)] = false; //...предыдущее...
                        free[i.saturating_sub(2)] = false; //...и предпредыдущее
                    },
            b'C' => {                                      //если перекрёсток - помечаем как занятое
                        free[i.saturating_add(1)] = false; //следующее место...
                        free[i]                   = false; //...текущее...
                        free[i.saturating_sub(1)] = false; //...и предыдущее
                    },
            b'-' => (),                                    //если дефис - игрорируем
            _    => panic!("Unrecognised symbol in sequence: {}", a as char), //если любой другой символ - падаем
        }
    }
    
    free.into_iter().filter(|&x| x == true).count() //считаем число мест, отмеченных как свободные
}

fn main() {
    //убеждаемся, что результат функции совпадает с ожидаемым
    assert_eq!(count_places("---S--C-E--C--"), 4);
    assert_eq!(count_places("--C--C--C--C--"), 2);
}

Немного об особенностях кода, связанных с Rust:

1. Почему street.bytes(), то есть итерация идёт по байтам, а не по символам? Дело в том, что строки в Rust закодированы в UTF-8 — кодировке с переменным числом байт на символ (от одного до шести). Соответственно, выделение символов — это нетривиальная операция, требующая времени. Выделение байтов же — простая операция, выполняющаяся за константное время (в силу того, что "под капотом" &str не более чем массив байт). Таким образом, итерация по байтам быстрее, чем итерация по символам, и при росте строк эта разница только растёт.

2. Зачем такие странные операции: saturating_add и saturating_sub? Для того, чтобы отмечать недоступные для парковки места, в случае с перекрёстками и остановками нужно менять не только текущие элементы, но и соседние. Просто вычитать и прибавлять к значению индекса смещение — неприемлемый вариант, так как:

   • Есть опасность выхода за границы индекса;
   • Индекс, возвращаемый enumerate, имеет тип usize, то есть неотрицательного целого числа нативного для целевой платформы размера, а по умолчанию в отладочной сборке Rust выражение вида j = i - 1;, где i равно нулю и имеет тип usize будет вызывать аварийное прерывание программы с ошибкой вида Integer underflow (аналогично в случае с переполнением).

Приводить индекс к знаковому типу перед вычислением тоже не годится, т.к. старший бит беззнакового числа после приведения становится знаковым битом, поэтому при больших значениях в выражении может неожиданно появиться отрицательное число.

Для того, чтобы избежать этих неприятностей, в программе используются методы saturating_sub и saturating_add. Семантически i.saturating_sub(1) (если i имеет тип usize) эквивалентно i = max(0, i-1) с той разницей, что в первом случае не происходит ошибки underflow в случае, если i нулевое. Аналогично i.saturating_add(1) эквивалентно i = min(std::usize::MAX, i+1).