Готовлюсь к Advent of Code 2022, и чтобы стряхнуть с себя паутину, пробую некоторые проблемы прошлого года в ржавчине. Начиная с первого дня, я пытался освоиться с механикой итераторов. Описание проблемы для обеих частей:
Предположим, у вас есть следующий отчет:
199 200 208 210 200 207 240 269 260 263
В этом отчете указано, что при сканировании в направлении от подводной лодки гидролокатор обнаружил глубины 199, 200, 208, 210 и так далее.
Первое, что нужно сделать, это выяснить, как быстро увеличивается глубина, просто чтобы вы знали, с чем имеете дело — никогда не знаешь, унесут ли ключи в более глубокие воды океанское течение, или рыба, или что-то в этом роде.
Для этого подсчитайте, во сколько раз измерение глубины увеличивается по сравнению с предыдущим измерением. (Перед первым измерением нет измерений.) В приведенном выше примере изменения следующие:
199 (Н/Д — нет предыдущего измерения) 200 (увеличение) 208 (увеличение) 210 (увеличение) 200 (уменьшение) 207 (увеличение) 240 (увеличение) 269 (увеличение) 260 (уменьшение) 263 (увеличение) В этом примере есть 7 измерений, которые больше, чем предыдущее измерение.
На сколько измерений больше, чем предыдущее измерение?
Часть 2. Вместо этого рассмотрим суммы трехмерного скользящего окна. Опять же, учитывая приведенный выше пример:
199 A 200 AB 208 ABC 210 BCD 200 ECD 207 EFD 240 EFG 269 FGH 260 GH 263 H Начните со сравнения первого и второго трехмерных окон. Измерения в первом окне отмечены буквой А (199, 200, 208); их сумма 199 + 200 + 208 = 607. Второе окно отмечено буквой B (200, 208, 210); его сумма равна 618. Сумма измерений во втором окне больше, чем сумма в первом, поэтому это первое сравнение увеличилось.
Теперь ваша цель состоит в том, чтобы подсчитать, во сколько раз сумма измерений в этом скользящем окне увеличивается по сравнению с предыдущей суммой. Итак, сравните A с B, затем сравните B с C, затем C с D и так далее. Остановитесь, когда останется недостаточно измерений для создания новой суммы трех измерений.
В приведенном выше примере сумма каждого окна с тремя измерениями выглядит следующим образом:
A: 607 (Н/Д — нет предыдущей суммы) B: 618 (увеличение) C: 618 (без изменений) D: 617 (уменьшение) E: 647 (увеличение) F: 716 (увеличение) G: 769 (увеличение) H : 792 (увеличено) В этом примере есть 5 сумм, которые больше, чем предыдущая сумма.
Рассмотрим суммы трехмерного скользящего окна. На сколько сумм больше предыдущей суммы?
Мое решение для обеих частей:
// main.rs
use std::fs::File;
use std::io::{Result, Read};
fn parse_to_int(body: String) -> Vec<i32> {
// Parse the file once and collect into a vec
body
.split("\n")
.map(|x| x.trim().parse::<i32>().unwrap())
.collect()
}
fn part_one(parsed: &Vec<i32>) -> i32 {
// offset iterator to compare if parsed[i] < parsed[i+1]
// sum all occurrences where this is true
parsed
.iter()
.zip(parsed.iter().skip(1))
.map(|(a, b)| (b > a) as i32)
.sum()
}
fn part_two(parsed: &Vec<i32>) -> i32 {
// Need a sliding window of three elements wide
let a = parsed
.iter()
.zip(parsed.iter().skip(1))
.zip(parsed.iter().skip(2))
.map(|((x, y), z)| x + y + z);
// I tried doing let b = a.skip(1);
// but the borrow checker wouldn't have it.
// This works though
let b = parsed
.iter()
.skip(1)
.zip(parsed.iter().skip(2))
.zip(parsed.iter().skip(3))
.map(|((x, y), z)| x + y + z);
a.zip(b)
.map(|(x, y)| (y > x) as i32)
.sum()
}
pub fn main() -> Result<()> {
let mut fh = File::open("data/day1.txt")?;
let mut body = String::new();
fh.read_to_string(&mut body)?;
body = body.trim().to_string();
let values = parse_to_int(body);
let total_1 = part_one(&values);
println!("Part 1 solution: {:?}", total_1);
let total_2 = part_two(&values);
println!("Part 2 solution: {:?}", total_2);
Ok(())
}
#[cfg(test)]
#[test]
fn test_int_conversion() {
// Make sure my integer converter works
let test = String::from("199\n200\n208\n210\n200\n207");
let res = parse_to_int(test);
assert_eq!(
res,
vec![199, 200, 208, 210, 200, 207]
);
}
#[cfg(test)]
#[test]
fn test_part_one() {
let test = String::from(
"199\n200\n208\n210\n200\n207\n240\n269\n260\n263"
);
let res = parse_to_int(test);
let tot = part_one(&res);
assert_eq!(tot, 7);
}
#[cfg(test)]
#[test]
fn test_part_two() {
let test = String::from(
"199\n200\n208\n210\n200\n207\n240\n269\n260\n263"
);
let res = parse_to_int(test);
let tot = part_two(&res);
assert_eq!(tot, 5);
}
Любые советы приветствуются, но мне бы хотелось, чтобы некоторые указатели могли сделать это более идиоматичным. В качестве примечания, body.strip() строка связана с тем, что мой редактор продолжает помещать дополнительную новую строку в конец файла данных AoC, иначе мне это не нужно.
1 ответ
Ваш код выглядит хорошо для меня! Вот как мы можем попытаться улучшить ситуацию.
Используйте больше инструментов: fmt
Ваш код выглядит правильно отформатированным. Однако, для информации, вы можете использовать cargo fmt чтобы вам больше никогда не приходилось беспокоиться о форматировании кода вручную.
С предоставленным кодом единственные изменения касаются пустых строк и разрывов строк.
Используйте больше инструментов: clippy
резкий — действительно хороший инструмент для выявления ошибок и улучшения вашего кода.
В вашем случае ничего впечатляющего не предлагается, но стоит добавить в свой набор инструментов.
Вот предложения, все их легко принять во внимание.
error: this argument is passed by value, but not consumed in the function body
--> src/2021/day1/main_review.rs:6:23
|
6 | fn parse_to_int(body: String) -> Vec<i32> {
| ^^^^^^ help: consider changing the type to: `&str`
|
= note: `-D clippy::needless-pass-by-value` implied by `-D clippy::pedantic`
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#needless_pass_by_value
error: single-character string constant used as pattern
--> src/2021/day1/main_review.rs:9:16
|
9 | .split("\n")
| ^^^^ help: try using a `char` instead: `'\n'`
|
= note: `-D clippy::single-char-pattern` implied by `-D clippy::perf`
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#single_char_pattern
error: writing `&Vec` instead of `&[_]` involves a new object where a slice will do
--> src/2021/day1/main_review.rs:12:21
|
12 | fn part_one(parsed: &Vec<i32>) -> i32 {
| ^^^^^^^^^ help: change this to: `&[i32]`
|
= note: `-D clippy::ptr-arg` implied by `-D clippy::style`
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#ptr_arg
error: casting `bool` to `i32` is more cleanly stated with `i32::from(_)`
--> src/2021/day1/main_review.rs:18:23
|
18 | .map(|(a, b)| (b > a) as i32)
| ^^^^^^^^^^^^^^ help: try: `i32::from(b > a)`
|
= note: `-D clippy::cast-lossless` implied by `-D clippy::pedantic`
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#cast_lossless
Упрощение тестов
В частности, приняв во внимание эти предложения, вы сможете избавиться от String::from в ваших тестовых примерах и получить что-то гораздо более лаконичное:
#[cfg(test)]
#[test]
fn test_int_conversion() {
let res = parse_to_int("199\n200\n208\n210\n200\n207\n240\n269\n260\n263");
assert_eq!(res, vec![199, 200, 208, 210, 200, 207, 240, 269, 260, 263]);
}
#[cfg(test)]
#[test]
fn test_part_one() {
let res = parse_to_int("199\n200\n208\n210\n200\n207\n240\n269\n260\n263");
let tot = part_one(&res);
assert_eq!(tot, 7);
}
#[cfg(test)]
#[test]
fn test_part_two() {
let res = parse_to_int("199\n200\n208\n210\n200\n207\n240\n269\n260\n263");
let tot = part_two(&res);
assert_eq!(tot, 5);
}
Вы также можете попробовать определить входной пример только один раз (и, возможно, удалить различные переменные, используемые только один раз):
#[cfg(test)]
mod tests {
use super::*;
const INPUT_EXAMPLE: &str = "199\n200\n208\n210\n200\n207\n240\n269\n260\n263";
#[cfg(test)]
#[test]
fn test_int_conversion() {
assert_eq!(
parse_to_int(INPUT_EXAMPLE),
vec![199, 200, 208, 210, 200, 207, 240, 269, 260, 263]
);
}
#[test]
fn test_part_one() {
assert_eq!(part_one(&parse_to_int(INPUT_EXAMPLE)), 7);
}
#[test]
fn test_part_two() {
assert_eq!(part_two(&parse_to_int(INPUT_EXAMPLE)), 5);
}
}
Решение для части 1
Алгоритм, заложенный в части 1, мне кажется хорошим.
Однако вместо того, чтобы иметь parsed.iter() несколько раз, включая один сдвиг из 1, вы можете напрямую использовать tuple_windows (из ящика itertools) написать: parsed.iter().tuple_windows().map(|(a, b)| i32::from(b > a)).sum().
Это может показаться немного чрезмерным, но это будет еще более актуально для части 2.
Кроме того, имя переменной parsed не передает особого смысла. Я бы предпочел что-то вроде depths (хотя легко забыть, что мы решаем задачу о подводной лодке, а не только математическую).
В качестве последнего примечания, вместо того, чтобы иметь map(|(a, b)| i32::from(b > a)).sum()можно было бы использовать filter(|(a, b)| a < b).count() но я не могу гарантировать, что это более эффективно и/или более идиоматично.
Решение для части 2
Для этой конкретной части можно применить математический трюк. Действительно, мы сравниваем сумму скользящих окон, но делаем это очевидным образом: вычисляем скользящие окна, вычисляем суммы, сравниваем суммы. Вместо этого можно сделать следующее наблюдение:
Вычисления:
Window(n + 1) > Window(n)
ss то же, что и вычисление:
d(n+1) + d(n+2) + ... + d(n+1+windowsize) > d(n) + d(n+1) + ... + d(n+windowsize)(кудаdэто глубина)
Это то же самое, что вычисление:
d(n+1+windowsize) > d(n)который не предполагает никакого суммирования.
Следовательно, решение для части 2 может быть записано:
fn part_two(depths: &[i32]) -> usize {
// Window(n + 1) > Window(n)
// d(n+1) + d(n+2) + ... + d(n+1+windowsize) > d(n) + d(n+1) + ... + d(n+windowsize)
// d(n+1+windowsize) > d(n)
depths
.iter()
.tuple_windows()
.filter(|(a, _, _, d)| a < d)
.count()
}