magical match

[amarao]

Всё-таки match в Rust - это киллер-фича. Язык должен был называться Match.

Задача на общую занимаемую площадь двумя прямоугольниками, которые могут перекрываться любым образом.

https://leetcode.com/problems/rectangle-area

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


Сначала компактный код решения, в котором "всё понятно".

use std::cmp;

impl Solution {

pub fn compute_area(ax1: i32, ay1: i32, ax2: i32, ay2: i32, bx1: i32, by1: i32, bx2: i32, by2: i32) -> i32 {

let mut combined = (cmp::min(ay2, by2) - cmp::max(ay1, by1)) * (cmp::min(ax2, bx2) - cmp::max(ax1, bx1));

if by2 < ay1 || ay2 < by1 || bx2 < ax1 || ax2 < bx1 {

combined = 0;

}

(ay2-ay1) * (ax2-ax1) + (by2-by1) * (bx2-bx1) - combined

}

}

А вот моё решение. Оно сильно больше строк занимает, но, надеюсь, оно лучше объясняет суть решения:

#[derive (Copy, Clone, Debug, PartialEq, Eq)]

enum Color {

Pink,

Violet

}

#[derive (Copy, Clone, Debug)]

enum State{

No,

One(Color), //Single color zone

Intersection(i32) // two color zone

}

use State::*;

use Color::*;

impl Solution {

pub fn compute_area(ax1: i32, ay1: i32, ax2: i32, ay2: i32, bx1: i32, by1: i32, bx2: i32, by2: i32) -> i32 {

fn intersection(a1: i32, a2: i32, b1: i32, b2: i32) -> i32{

let mut colored_dots = [(a1, Violet), (a2, Violet), (b1, Pink), (b2, Pink)];

colored_dots.sort_by(|a, b| a.0.cmp(&b.0));

let mut state = No;

for dot in colored_dots{

match (state, dot) {

(No, (_, color)) => {

state = One(color);

},

(One(color), (start, new_color)) if color != new_color => {

state = Intersection(start);

},

(Intersection(start), (end, _)) => {

return end-start;

}

_ => { // no intersection

return 0;

}

}

}

0

}

fn area(x1:i32, x2:i32, y1:i32, y2:i32) -> i32 {

(x2-x1)*(y2-y1)

}

let intersection = intersection(ax1, ax2, bx1, bx2) * intersection(ay1, ay2, by1, by2);

let rect1 = area(ax1, ax2, ay1, ay2);

let rect2 = area(bx1, bx2, by1, by2);

rect1 + rect2 - intersection

}

}

Когда я написал match, это было ощущение "хорошей презентации". Вместо каких-то странных cmp/min/max, я объясняю алгоритм.

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

Идя по всем точкам: для первой точки (state=No), нам важен только цвет. Запомним его.
Далее, для следующей точки, если у нас цвет уже известен, и цвет поменялся, запомним начало пересечения.
Если у нас уже есть пересечение, на следующей точке, вне зависимости от её цвета, находится конец пересечения.

Если нам не удалось найти пересечения, то его нет.

Вот это "вне зависимости от цвета" или "нам важен только цвет первой точки" - это же явно написано. "Оставшееся выбросить". И при написании мы точно знаем, что покрыли все-все варианты, потому что match исчерпывающий.

Comments

[sab123]

Я бы сказал, что короткий вариант гораздо понятнее. По крайней мере, я легко понял что он делает, а длинный - с трудом и не понял.

[ufm]

Ты-же, вроде, на ерланге писал? Почему тебя там это не вштырило?

[amarao]

Я никогда не писал на эрланге, и за приличный язык я его не считаю. Язык, программы на котором не могут работать без epamd, это не язык программирования, а скриптовая обвязка для телефонистов.

[ufm]

Значит я тебя с кем-то перепутал.
epmd нужен только когда требуется поднять распределенный кластер, так-то оно прекрасно без него умеет.