add two numbers

Одна из простых задач, которые сложны в Rust'е: даны числа в виде списка чисел (десятичные знаки в i32), список в обратном порядке
(то есть head списка - самое крупное число). Надо в таком же виде (списка) вернуть сумму этих чисел.

https://leetcode.com/problems/add-two-numbers

Rust'овые проблемы:

1. Чтобы в том же порядке сложить числа, их нужно засовывать в хвост по мере складывания. В Rust значительно проще было бы делать это в обратном порядке, но увы. Засовывание в хвост чревато тем, что мы должны иметь значение головы для возврата, то есть по списку по мере построения мы двигаемся с помощью &mut, что приводит к тому, что нам надо менять head по & mut, а это означает чёрную магию mem::swap. (Магия хоть и чёрная, но safe, ура).

2. Когда мы ползём по списку, мы не можем казуально заглядывать в tail полученного списка несколько раз, т.к. происходит move (передача владения), в момент заглядывания. Обходные пути через ссылки не очень работают, потому что компилятор не понимает, можно ли нам верить с сроком жизни полученных ссылок (точнее, он знает, что верить нельзя).

Получается такое:

pub fn add_two_numbers(

mut l1: Option<Box<ListNode>>,

mut l2: Option<Box<ListNode>>,

) -> Option<Box<ListNode>> {

let mut carry = 0;

let mut result = None;

let mut tail = &mut result;

while l1.is_some() || l2.is_some() || carry > 0 {

let (n1, next_l1) = l1.map_or((0, None), |n| (n.val, n.next));

let (n2, next_l2) = l2.map_or((0, None), |n| (n.val, n.next));

let sum = n1 + n2 + carry;

let mut new_node = Some(Box::new(ListNode {

next: None,

val: sum % 10,

}));

std::mem::swap(tail, &mut new_node);

tail = &mut (tail.as_mut().unwrap().next);

carry = sum / 10;

l1 = next_l1;

l2 = next_l2;

}

result

}

трюки:

1. mem::swap для того, чтобы поменять &mut (ведущий на None) на новое значение.
2. синхронное выковыривание val & next в одну строчку.

Алготримическое:

While зависит от обоих цифр и carry. Это позволяет элегантно решать проблему последнего символа.

Я думал, что это у меня кривые руки и задача решается проще, но не нашёл ни одного соседнего решения, которое было бы элегантным. Пока что основное, что я видел, то предсоздание в качестве result '0' вместо None (что, соотственно,  IRL ломает инвариант для add_two_numbers(None, None), который должен сделать None, хотя тут задача становится мутной, потому что 1 + None - это сколько?).

За что мне при этом дали 31мс решения я не понял, кажется, это флуктуации.

В рамках гольфа: Если гоняться за оптимизацией памяти, то мы можем переиспользовать полученные l1/l2 для новых нод, таким образом, экономя на аллокациях.

В рамках экономии строк: если n1/n2 декларировать над циклом, то можно будет делать n1, l1 = ...., без временных переменных и let.

Upd: могу, но не могу. Моя версия Rust это уже умеет, leetcode'овская утверждает, что destructuring assignments are unstable.

mastodon

Btw, я подумаваю о частичном появлении там. Меня останавливает только то, что я не понимаю, на какой сервер я хочу. Кто-то им уже пользуется?