🛠️ Поиск допустимых комбинаций операторов для уравнений калибровки

leetcoder, 21-04-2025 ,

100

Задача 7-го дня Advent of Code — Bridge Repair.

📘 Часть I. Условие задачи

У инженеров почти готова калибровка оборудования, но из формул пропали все операторы!
Остались только числа. В каждой строке входных данных указано:

Слева — целевое значение;
Справа — последовательность чисел.

Задача: вставить между числами операторы + и *, чтобы получить целевое значение.
Важно: выражения вычисляются строго слева направо, без учёта приоритетов операций.
Например:

190: 10 19
3267: 81 40 27

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

💡 Идея

Каждую строку можно представить как выражение, в которое надо вставить операторы.
Количество вставок — len(seq) - 1.
Для каждой строки мы перебираем все возможные комбинации из операторов + и * и проверяем, приводит ли результат к целевому числу.

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

📘 Часть II. Условие задачи

Добавляется новый оператор || — конкатенация чисел.
Он объединяет два числа: 12 || 345 = 12345.

Теперь задача — вставить операторы +, * и || между числами, по тем же правилам (слева направо), и выяснить, можно ли получить целевое значение. По прежнему требуется определить, какие строки могут быть истинными, и посчитать сумму их целевых значений.

💡 Идея

Добавляется ещё один возможный оператор между двумя числами. Таким образом, расширяется пространство перебора. Но вся логика остаётся прежней — рекурсивно перебираем возможные комбинации, вычисляя значение на каждом шаге.

🔍 Детали реализации

Используем перечисление Operation с тремя вариантами: Mul, Add, Concat для того, чтобы однообразить перебор.
Вспомогательная структура EvalContext помогает эффективно передавать контекст перебора в глубь рекурсивного спуска.
Рекурсивная функция backtrack перебирает все последовательности операций и проверяет, приводят ли они к нужному значению.
Оператор Concat реализован через выражение l * 10^k + r, где k — количество цифр в r.
- Используем трюк с добавлением EPS, чтобы избежать ошибок с потерей точности в log10.

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

Пусть в строке n чисел.

Временная сложность: O(Σk^n-1)
- Возможных комбинаций операторов: k^n-1, где k — количество допустимых операций
  (для части I – k=2; для части II – k=3).
- Для каждой строки сложность — O(k^n-1).
- Так как n в тестах небольшой (до 12 чисел), такой перебор вполне допустим.
Пространственная сложность: O(n)
- Используем константное число промежуточных переменных и стек для рекурсивного перебора

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

use super::TaskData;

pub struct Solution;

/// Operators used to evaluate calibration equations, applied left-to-right.
enum Operation {
    Mul,
    Add,
    Concat,
}

/// Holds the context for evaluating a sequence with a specific set of operations.
struct EvalContext<'a, const N: usize> {
    target: i64,
    sequence: &'a [i64],
    operations: [Operation; N],
}

impl Solution {
    /// Part I: Evaluate using only addition and multiplication.
    pub fn solve_simple(data: &TaskData) -> i64 {
        data.targets.iter().zip(data.sequences.iter())
            .filter_map(|(&target, sequence)| {
                let ctx = EvalContext {
                    target,
                    sequence: &sequence,
                    operations: [Operation::Mul, Operation::Add],
                };
                Self::backtrack(sequence[0], 1, &ctx).then_some(target)
            }).sum()
    }

    /// Part II: Evaluate using addition, multiplication, and concatenation.
    pub fn solve_hard(data: &TaskData) -> i64 {
        data.targets.iter().zip(data.sequences.iter())
            .filter_map(|(&target, sequence)| {
                let ctx = EvalContext {
                    target,
                    sequence: &sequence,
                    operations: [Operation::Mul, Operation::Add, Operation::Concat],
                };
                Self::backtrack(sequence[0], 1, &ctx).then_some(target)
            }).sum()
    }

    /// Recursively evaluates all possible operator sequences between numbers.
    fn backtrack<'a, const N: usize>(cur_value: i64, depth: usize, ctx: &EvalContext<'a, N>) -> bool {
        if depth < ctx.sequence.len() {
            ctx.operations.iter().any(|op| {
                let next_value = op.apply(cur_value, ctx.sequence[depth]);
                Self::backtrack(next_value, depth + 1, ctx)
            })
        } else {
            // Recursion base - just check that evaluation result is target
            cur_value == ctx.target
        }
    }
}

impl Operation {
    /// Applies the operation to `l` and `r` with left-to-right semantics.
    fn apply(&self, l: i64, r: i64) -> i64 {
        const EPS: f64 = 1e-16;
        const TEN: f64 = 10.0;

        match self {
            Operation::Mul => l * r,
            Operation::Add => l + r,
            Operation::Concat => {
                // Compute how many digits are in `r` to shift `l` accordingly.
                let digits = 1 + ((r as f64 + EPS).log10()) as i32;
                l * TEN.powi(digits) as i64 + r
            }
        }
    }
}

Tags: #rust #algorithms #backtracking #math