🦠 Устойчивый парсинг повреждённого дампа памяти с условной фильтрацией команд умножения

leetcoder, 10-04-2025 ,

154

Задача третьего дня Advent of Code — Mull It Over.

📘 Часть I. Описание задачи

В дампе памяти содержатся команды вида mul(X,Y), где X и Y — это числа от 1 до 999.
Такие команды представляют собой простое умножение двух чисел.
Однако память повреждена, и в тексте могут встречаться невалидные команды
(например: "mul(4*," "mul ( 2 , 3 )" и т.п.).

Необходимо выделить все корректные mul(X,Y) и подсчитать сумму произведений.

💡 Идея

Парсим только строки, точно соответствующие регулярному выражению "mul(\d{1,3},\d{1,3})", остальные пропускаем. После чего результат каждого умножения суммируем.

📘 Часть II. Описание задачи

Кроме mul, в дампе встречаются do() и don't():

do() включает обработку mul
don't() отключает

По умолчанию mul разрешён. Надо подсчитать только те mul, которые активны в момент встречи.

💡 Идея

Добавим поддержку do() и don't() в парсер.
При проходе по потоку команд будем отслеживать флаг allow.
Регулярное выражение будет единым и поддерживать все три типа команд: do(), don't(), mul(a,b).

⚙️ Детали подхода

Используем регулярное выражение с двумя альтернативами:
- "(do|don't)\(()()\)" — ловит do() и don't(), возвращает пустые аргументы
- "(mul)\((\d{1,3}),(\d{1,3})\)" — ловит mul(x,y) с числами от 1 до 999
Используем метод extract() из regex::Captures, чтобы получить тройку: cmd, arg0, arg1
Парсинг команд реализован в виде метода command_from_caps внутри CommandScanner
Итерация над командами внутри solve_hard() реализована через .fold(...), что устраняет необходимость в мутабельных переменных

⏱️ Асимптотика

Пусть n — длина строки mem_dump, k — количество валидных команд.

Временная сложность: O(n)
- Поиск и парсинг: O(n)
- Обработка команд: O(k)
Память: O(1)
- команды обрабатываются на лету

📄 Исходный код

use super::TaskData;
use regex::{Captures, Regex};

pub struct Solution {}

enum Command {
    Mul(i32, i32),
    Do,
    Dont,
}

struct CommandScanner {
    re: Regex,
}

impl Solution {
    /// Part I: sum all valid mul(a,b) instructions
    pub fn solve_simple(data: &TaskData) -> i32 {
        CommandScanner::new()
            .scan(&data.mem_dump)
            .filter_map(|cmd| match cmd {
                Command::Mul(a, b) => Some(a * b),
                _ => None,
            }).sum()
    }

    /// Part II: obey do() / don't() switches to enable/disable mul
    pub fn solve_hard(data: &TaskData) -> i32 {
        CommandScanner::new()
            .scan(&data.mem_dump)
            .fold((0,true), |(acc, allow), cmd| match cmd {
                Command::Do => (acc, true),
                Command::Dont => (acc, false),
                Command::Mul(a, b) => (acc + if allow { a*b } else {0}, allow),
            }).0
    }
}

impl CommandScanner {
    // Unified regex: exactly matches do(), don't(), or mul(X,Y) without spaces
    const RE_COMMAND: &str = r"(do|don't)\(()()\)|(mul)\((\d{1,3}),(\d{1,3})\)";

    pub fn new() -> Self {
        Self {re: Regex::new(Self::RE_COMMAND).unwrap()}
    }

    /// Parses input into a stream of valid Command items
    pub fn scan<'a>(&'a self, input: &'a str) -> impl Iterator<Item = Command> + 'a {
        self.re.captures_iter(input).filter_map(Self::command_from_caps)
    }

    /// Converts a regex capture into a Command
    fn command_from_caps(cap: Captures) -> Option<Command> {
        let (_, [cmd, arg0, arg1]) = cap.extract();

        match cmd {
            "do" => Some(Command::Do),
            "don't" => Some(Command::Dont),
            "mul" => Some(Command::Mul(arg0.parse().ok()?, arg1.parse().ok()?)),
            _ => None,
        }
    }
}

Tags: #rust #regex #adventofcode