Заимствование в Rust

· обновлено · #rust · #aoc

Решаю на Rust вторую задачку Advent of Code. Задачка довольно простая. Входные данные выглядят так:

mvgowxqubnhaefjslkjlrptzyi
pvgowlqubnhaefmslkjdrpteyi
ovgowoqubnhaefmslkjnrptzyi
cvgowxqubnrxefmslkjdrptzyo
cvgowxqubnhaefmsokjdrprzyf
cvgowxqubnhjeflslkjgrptzyi
...

Задание:

...подсчитайте, сколько ID содержат какую-нибудь букву ровно два раза, и отдельно — сколько содержат какую-нибудь букву ровно три раза. Перемножив эти два числа, вы получите [ответ]...

На псевдокоде решение выглядело бы примерно так:

for line in input
   counters = count_letters(line)

seen_two_letters = 0
seen_three_letters = 0

for counter in counters
   if counter.values.includes(2)
      seen_two_letters += 1
   if counter.values.include(3)
      seen_three_letters += 1

print seen_two_letters * seen_three_letters

Теперь на Rust. Особо не заморачиваясь с оптимизацией, буду хранить количество каждого символа в строке в векторе из HashMap. Потом пройдусь по ним и посчитаю хеши, у которых среди значений есть 2 или 3.

extern crate utils;
use std::collections::HashMap;

fn part_one() {
    let input = utils::read_puzzle_input(2);

    for line in input.lines() {
        let mut counters: HashMap<char, u8> = HashMap::new();

        for chr in line.chars() {
            match counters.get(&chr).cloned() {
                Some(count) => counters.insert(chr, count + 1),
                None => counters.insert(chr, 1),
            };
        }
    }
}

Запускаем:

➜  aoc2018 git:(master) ✗ cargo run --bin 2
   Compiling aoc2018 v0.1.0 (file:///Users/antono/Code/rust/aoc2018)
error[E0502]: cannot borrow `counters` as mutable because it is
also borrowed as immutable
  --> src/bin/2.rs:57:32
   |
56 |             match counters.get(&chr) {
   |                   -------- immutable borrow occurs here
57 |                 Some(count) => counters.insert(chr, count + 1),
   |                                ^^^^^^^^ mutable borrow occurs here
58 |                 None => counters.insert(chr, 1),
59 |             };
   |             - immutable borrow ends here

error[E0502]: cannot borrow `counters` as mutable because it is
also borrowed as immutable
  --> src/bin/2.rs:58:25
   |
56 |             match counters.get(&chr) {
   |                   -------- immutable borrow occurs here
57 |                 Some(count) => counters.insert(chr, count + 1),
58 |                 None => counters.insert(chr, 1),
   |                         ^^^^^^^^ mutable borrow occurs here
59 |             };
   |             - immutable borrow ends here

error: aborting due to 2 previous errors

For more information about this error, try `rustc --explain E0502`.
error: Could not compile `aoc2018`.

To learn more, run the command again with --verbose.

Перечитываю в Rust Book главы про владение и заимствование. С владением мне всё вроде бы понятно. А вот с заимствованием, тем более изменяемым, — не очень. Чтобы заимствовать правильно, надо соблюдать несколько правил:

Во-первых, любое заимствование должно длиться не дольше, чем область видимости владельца. Во-вторых, у вас может быть либо один, либо другой из этих двух видов заимствований, но не оба одновременно: одна или несколько ссылок (&T) на ресурс либо ровно одна изменяемая ссылка (&mut T).

Выходит, проблема в том, что я заимствовал хеш-таблицу counters и на чтение, и на запись сразу. HashMap#get возвращает Option со ссылкой на значение (которое лежит в куче). А counter.insert() в то же самое время заимствует данные хеша как изменяемые, чтобы их поменять (всё в той же куче). Rust такого не допускает — ради безопасности памяти и чтобы не было состояния гонки:

Владение — это способ, которым Rust достигает своей главной цели: безопасности памяти.

Один из способов не заимствовать значение из хеша на чтение — просто его скопировать. В документации к Option нашёлся полезный метод .cloned().

Превращает Option<&T> в Option<T>, клонируя содержимое Option.

Буду вызывать его, когда достаю значение из хеша:

fn part_one() {
    let input = utils::read_puzzle_input(2);

    for line in input.lines() {
        let mut counters: HashMap<char, u8> = HashMap::new();

        for chr in line.chars() {
            match counters.get(&chr).cloned() {
                Some(count) => counters.insert(chr, count + 1),
                None => counters.insert(chr, 1),
            };
        }

        println!("{:?}", counters.values());
    }
}

Запускаем:

cargo run --bin 2
   Compiling aoc2018 v0.1.0 (file:///Users/antono/Code/rust/aoc2018)
    Finished dev [unoptimized + debuginfo] target(s) in 0.62 secs
     Running `target/debug/2`
[1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1]
[1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1]
[1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2]
[1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]
[1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1]
...

Заработало. Смущает только, что приходится каждый раз копировать значение, лишь бы не заимствовать его на чтение. Один умный человек подсказал мне HashMap#entry(): он отдаёт Entry, через который значение в хеше можно менять прямо на месте. У самого Entry куча полезных методов. Entry#and_modify() — ровно то, что мне нужно. Пример из документации:

use std::collections::HashMap;

let mut map: HashMap<&str, u32> = HashMap::new();

map.entry("poneyland")
   .and_modify(|e| { *e += 1 })
   .or_insert(42);

assert_eq!(map["poneyland"], 42);

Ух ты! Переделываю свой код вот с такого:

   for line in input.lines() {
        let mut counters: HashMap<char, u8> = HashMap::new();

        for chr in line.chars() {
            match counters.get(&chr).cloned() {
                Some(count) => counters.insert(chr, count + 1),
                None => counters.insert(chr, 1),
            };
        }
   }

на такой:

    for line in input.lines() {
        let mut counters: HashMap<char, u8> = HashMap::new();

        for chr in line.chars() {
            counters
                .entry(chr)
                .and_modify(|count| { *count += 1})
                .or_insert(1);
        }
    }

Так. Пора добивать задачку AOC. Буквы во всех ID я посчитал. Теперь осталось посчитать вот что:

...подсчитайте, сколько ID содержат какую-нибудь букву ровно два раза, и отдельно — сколько содержат какую-нибудь букву ровно три раза. Перемножив эти два числа, вы получите [ответ]...

# pseudocode

seen_two_letters = 0
seen_three_letters = 0

for counter in counters
   if counter.values.includes(2)
      seen_two_letters += 1
   if counter.values.include(3)
      seen_three_letters += 1

print seen_two_letters * seen_three_letters

Переводим на Rust:

extern crate utils;
use std::collections::HashMap;

fn part_one() {
    let input = utils::read_puzzle_input(2);
    let mut seen_two_letters_count = 0;
    let mut seen_three_letters_count = 0;

    for line in input.lines() {
        let mut counter: HashMap<char, u8> = HashMap::new();

        for chr in line.chars() {
            counter
                .entry(chr)
                .and_modify(|count| { *count += 1})
                .or_insert(1);
        }

        if counter.values().find(|v| { **v == 2 }).is_some() {
            seen_two_letters_count += 1;
        }

        if counter.values().find(|v| { **v == 3 }).is_some() {
            seen_three_letters_count += 1;
        }
    }

    println!("{}", seen_three_letters_count * seen_two_letters_count);
}

Запускаем:

➜  aoc2018 git:(master) ✗ cargo run --bin 2
   Compiling aoc2018 v0.1.0 (file:///Users/antono/Code/rust/aoc2018)
    Finished dev [unoptimized + debuginfo] target(s) in 0.62 secs
     Running `target/debug/2`
5368

Ответ принят!

Ваш ответ: 5368. Первая половина задачки решена! За неё вы получаете одну золотую звезду: *


Дисклеймер