Как вырезать участки из числа и получить остатки?

Question

[Михаил]

Добрый день, например есть число 100 000 (сто тысяч)
Допустим с 30 до 500 нужно вырезать
Далее с 1200 по 3700 вырезать
И еще где то вырезаем...
Таким образом должны остаться только свободные числа в виде массива от и до, типа
array(
1 => [1, 30],
2 => [500, 1200],
3 => [3700, 100000],
)

Но может быть и такое:
Допустим с 30 до 500 нужно вырезать
Далее с 20 по 700 вырезать
Еще с 10 до 35 вырезать
И получается общее с 10 по 700
Получается некая функция которая принимает основное число от и до из которого вырезаем
и массив с тем, что нужно вырезать и на выходе нужно получить массив остатков.

Comments

[Дмитрий]

$arr = range(1,30) + range(500, 1200) + range(3700, 100000);

[Михаил]

Дмитрий, Неа, тут ты делаешь уже зная то, что останется. а изначально мы знаем только с 30 до 500 заняты числа и так далее. Ты получается просто ответы в массивы запихнул. А тут как раз инверсия нужна.

Answer 1

[v3shin]

У меня получилось громоздко. Есть ли решение лаконичнее?

function cut(array $base, array $cuts = [])
{
    $parts = [];
    $cutParts = [];

    // сортируем вырезанные отрезки по началу
    usort($cuts, function (array $a, array $b) {
        return $a[0] - $b[0];
    });

    // склеиваем вырезанные отрезки
    foreach ($cuts as $cut) {
        $i = count($cutParts)-1;
        if ($i === -1) { // первый отрезок
            $cutParts[] = [max($base[0], $cut[0]), min($base[1], $cut[1])];
        } else {
            if ($cut[0] > $cutParts[$i][1]) { // новый отрезок
                $cutParts[] = [max($base[0], $cut[0]), min($base[1], $cut[1])];
            } else { // склейка
                $cutParts[$i][1] = max($cutParts[$i][1], $cut[1]);
            }
        }
    }

    // считаем, что осталось
    if ($cutParts[0][0] === $base[0]) { // начинать надо не от начала
        if ($cutParts[0][1] === $base[1]) { // вырезано все
            return [];
        } else { // начинаем отсчет с конца первого отрезка
            $parts[0] = [$cutParts[0][1]];
            array_shift($cutParts);
        }
    } else { // начинаем отсчет от начала исходного отрезка
        $parts[0] = [$base[0]];
    }
    foreach ($cutParts as $i => $cutPart) {
        $parts[$i][1] = $cutPart[0];
        if ($cutPart[1] < $base[1]) {
            $parts[$i + 1] = [$cutPart[1]];
        } else { // отрезок покрывает конец исходного отрезка
            return $parts;
        }
    }
    $parts[count($parts) - 1][1] = $base[1];

    return $parts;
}

print_r(cut([1, 100000], [[30, 500], [1200, 3700]]));
print_r(cut([1, 1000], [[30, 500], [20, 700], [10, 35]]));

Comments

[Дмитрий]

Ну можно использовать range и функции разницы массивов

[v3shin]

Дмитрий, создать массив на 100000 элементов, удалить то, что надо вырезать и собрать остатки в отрезки? =)

[Дмитрий]

v3shin, ну а почему бы и нет) я догадываюсь про ваши опасения, но завезли генераторы

[v3shin]

Дмитрий, куда читать про генераторы?

[Дмитрий]

v3shin, https://www.php.net/manual/ru/language.generators.... ну например

Answer 2

[Slava Rozhnev]

v3shin , В принципе то же самое + array_reduce

<?php
function cut($num, $remove_intervals) {
	// sort remove intervals by first value
	usort($remove_intervals, function($a, $b){return $a[0] <=> $b[0];});

	// merge overlapped intervals
	$remove = array_reduce(
		$remove_intervals,
		function($res, $el) {
			$cnt = count($res)-1;
			if ($el[0] <= $res[$cnt][1]) {
				$res[$cnt][1] = max($el[1], $res[$cnt][1]);
			} else {
				$res[] = $el;
			}
			
			return $res;
		},
		[$remove_intervals[0]]
	);
	// build result array
	$result = array_reduce(
		$remove,
		function($res, $el) use ($num) {
			$cnt = count($res)-1;
			
			if ($el[0] < $res[$cnt][1]) {
				$res[$cnt][1] = $el[0];
				if ($el[1] < $num) {
					$res[] = [$el[1], $num];
				}
			}
			return $res;
		},
		[[1, $num]]
	);
	
	var_export($result);

	return $result;
}
print_r(cut(10000, [[30, 500], [700, 900], [800, 1000]]));
print_r(cut(10000, [[30, 500], [1200, 3700], [50, 700], [1000, 3000], [6000, 20000]]));
print_r(cut(1000, [[30, 500], [20, 7000], [10, 35]]));

Share PHP code online

Comments

[Михаил]

А что тут такое $num? Например cut(10000... Это типа всегда диапазон исходный от 0 и до $num ?

[Михаил]

Михаил, Вообще очень похоже на решение, только изначальный диапазон начинается от X до Y
И всегда может быть разным.

[Михаил]

Михаил, Получается нужно в array_reduce добавить array_reduce в место 1, динамическое число в виде переменной, которая будет прилетать в функцию cut типа [[$start, $num]]

[Slava Rozhnev]

Михаил, В Вашем вопросе написано:

Добрый день, например есть число 100 000 (сто тысяч)

теперь появился диапазон

соответственно решение должно быть адаптировано под диапазон

[Михаил]

Slava Rozhnev, Спасибо, поправил вопрос.

Answer 3

[Wataru]

Отсортируйте точки начала и конца всех отрезков вместе, помеченные с +1 или с -1 в зависимости от стороны.
Далее есть вот у вас все точки на числовой прямой. Пройдитесь по ним слева направо считая, сколько сейчас открыто отрезков. Если между двумя точками отркрыто 0 отрезков - добавляйте отрезок в ответ.

Удобный трюк - сдвинуть начала отрезков на 1 влево, чтобы отрезок, вырезающий число 1 (1..1) был длиной 1.
Представьте, что у вас на числовой прямой 10000 единичных кусочков, с 0 до 10000 - это ваши изначальные числа. Если вы хотите вырезать отрезок 5..7 (числа 5, 6 и 7), то вам надо на этой прямой вырезать отрезок [4...7] - от точки 4 до точки 7.

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

php не знаю, вот вам на C++. Спрашивайте, если что непонятно:

vector<pair<int, int>> CutOutSegments(int begin, int end, vector<pair<int, int>> segments)
  // Массив из пар чисел. Пустой массив, в который будем добавлять строки из 2 чисел.
  vector<pair<int, int>> events; 
  events.push_back({begin-1, 1});  // добавляем строку с числами begin и 1.
  events.push_back({end, -1});
  for (auto s: segments) {
     events.push_back({s.first-1, 1});  // s.first - начало отрезка.
     events.push_back({s.second, -1});  // s.second  - конец отрезка.
  }
  sort(events.begin(), events.end());
  int prev_pos = events[0].first;
  int count = 0;
  vector<pair<int, int>> result;
  for (auto e: events) { // e - строка массива events. e.first/second - 2 числа в ней.
    if (prev_pos < e.first && count == 1) {
      result.push_back(prev_pos + 1, e.first); // добавялем +1, что бы отрезок [0, 1] был выдан как одно число 1..1.
    }
    count += e.second;
    if (e.first == end) break;
  }
  return result;
}

Возмождно последний цикл можно переписать через reduce, но вряд ли будет короче или читабельнее.