Ваша задача здесь проста:
По заданному списку целочисленных множеств найдите объединение множеств. Другими словами, найдите кратчайший список целочисленных наборов, которые содержат все элементы в исходном списке наборов (но не другие элементы). Например:
[1,5] and [3,9] becomes [1,9] as it contains all of the elements in both [1,5] and [3,9]
[1,3] and [5,9] stays as [1,3] and [5,9], because you don't want to include 4
Наборы записываются с использованием обозначения диапазона: [1,4]
означает целые числа 1,2,3,4
. Наборы также могут быть неограниченными: [3,]
означает все целые числа >= 3
и [,-1]
означает все целые числа <= -1
. Гарантируется, что первый элемент диапазона не будет больше второго.
Вы можете выбрать наборы в строковой нотации или использовать двухэлементные кортежи, используя постоянное нецелое число в качестве «бесконечного» значения. Вы можете использовать две различные константы для представления бесконечной верхней границы и бесконечной нижней границы. Например, в Javascript вы можете использовать [3,{}]
для записи всех целых чисел >= 3
, если вы последовательно используете их {}
во всех тестовых случаях.
Тестовые случаи:
[1,3] => [1,3]
[1,] => [1,]
[,9] => [,9]
[,] => [,]
[1,3],[4,9] => [1,9]
[1,5],[8,9] => [1,5],[8,9]
[1,5],[1,5] => [1,5]
[1,5],[3,7] => [1,7]
[-10,7],[1,5] => [-10,7]
[1,1],[2,2],[3,3] => [1,3]
[3,7],[1,5] => [1,7]
[1,4],[8,] => [1,4],[8,]
[1,4],[-1,] => [-1,]
[1,4],[,5] => [,5]
[1,4],[,-10] => [1,4],[,-10]
[1,4],[,] => [,]
[1,4],[3,7],[8,9],[11,20] => [1,9],[11,20]
Это код-гольф , поэтому ответ должен быть как можно короче!
источник
Infinity
вместо этого{}
?[1.0, 3.0]
вместо[1, 3]
?[1.0, 3.0], [4.0, 5.0]
все равно должно стать[1.0, 5.0]
Infinity
и в-Infinity
качестве входных данных, разрешается ли вместо него принимать-999999
и999999
(или даже больше / меньше)?Ответы:
R +
intervals
,90 8781 байтПопробуйте онлайн!
Ввод представляет собой список интервалов.
-Inf
иInf
являются R встроенными для минус / плюс бесконечность. Вывод представляет собой матрицу столбцов интервалов.Обычно не фанат использования нестандартных библиотек, но этот был забавным. TIO не
intervals
установлен. Вы можете попробовать его самостоятельно или по адресу https://rdrr.io/snippets/В
intervals
пакет поддерживает реальное и целое (type = "Z"
) интервалы иreduce
функция является встроенной для того, что хочет , чтобы проблема, но выход , кажется, по умолчанию интервалов, поэтому необходимо , чтобы получить желаемый результат.close_intervals
+c(1,-1)
В старой версии были примеры в списке списков, которые могут быть удобными, поэтому я оставил ссылку здесь.
источник
function(...)close_intervals(reduce(Intervals(rbind(...),type="Z")))
. Или, что еще лучше, вы можете проверить с помощью op, разрешают ли они вводить матрицу.reduce
иReduce
там.f=function(...)t(reduce(Intervals(rbind(...),type="Z")))+c(1,-1)
?JavaScript (ES6), 103 байта
Сохранено 1 байт благодаря @Shaggy
Сохранено 1 байт благодаря @KevinCruijssen
Ожидает
+/-Infinity
бесконечные значения.Попробуйте онлайн!
Как?
Сначала мы сортируем интервалы по их нижней границе, от самой низкой до самой высокой. Верхние границы игнорируются.
В конце процесса мы создаем последний интервал с текущими границами .[m,M]
комментарии
источник
p<=M+1
может бытьp<M+2
?Python 2 ,
118113112111106105104101 байтОдин байт был сохранен благодаря Mr.Xcoder, один - Джонатану Фреху, а три - Мертвому Опоссуму.
Попробуйте онлайн!
источник
(b,c),
сохраняет байт.g
означает ли, что ваша функцияf
не пригодна для повторного использования и поэтому недействительна?return
становитсяprint
для следующего байта.Рубин ,
8976 байтПопробуйте онлайн!
Сортируйте массив, затем сгладьте, добавив все диапазоны к первому: если диапазон перекрывает предыдущий, отбросьте 2 элемента из последних 3 (оставив только максимум).
Расстегни все в конце.
источник
Паскаль (FPC) ,
367362357 байтПопробуйте онлайн!
Процедура, которая принимает динамический массив записей, состоящий из 2 границ диапазона, модифицирует массив на месте и затем записывает его в стандартный вывод, по одному диапазону на строку. (Извините за это искаженное предложение.) Используется
1/0
для неограниченного вверх и-1/0
для неограниченного вниз.Читаемая версия
Было бы неплохо просто вернуть массив с исправленным количеством элементов, но динамический массив, переданный функции / процедуре, больше не является динамическим массивом ... Сначала я нашел это , затем есть это превосходное, ошеломляющее объяснение .
Это лучшая структура данных, которую я смог найти для сокращения кода. Если у вас есть лучшие варианты, не стесняйтесь сделать предложение.
источник
Wolfram Language (Mathematica) , 57 байтов
Попробуйте онлайн!
Вводит в виде списка списков,
{a,b}
представляющих интервал[a,b]
, гдеa
может быть-Infinity
иb
может бытьInfinity
.Использует встроенный
IntervalUnion
, но, конечно, мы должны сначала втирать интервалы в форму. Чтобы сделать вид, что интервалы являются целыми числами, мы добавляем 1 к верхней границе (убедившись, что объединение[1,3]
и[4,9]
есть[1,9]
). В конце мы отменяем эту операцию и возвращаем результат обратно в список списков.Существует также совершенно другой подход, который составляет 73 байта :
Здесь, после сортировки интервалов, мы просто заменяем два последовательных интервала их объединением всякий раз, когда это будет один интервал, и повторяем до тех пор, пока не останется такой операции.
источник
05AB1E (legacy) ,
887978 байтовБесконечность вводится как строчный алфавит (
'abcdefghijklmnopqrstuvwxyz'
).Попробуйте онлайн или проверьте все контрольные примеры .
Важное примечание: если бы существовал факт
Infinity
и-Infinity
, вместо него было бы4342 байта . Так чточуть более 50%около 30% - это обходной путь для отсутствияInfinity
..Попробуйте онлайн (с
Infinity
заменой на9999999999
и-Infinity
заменой на-9999999999
).Определенно можно играть в гольф существенно. В итоге получилось очень, очень уродливо полно обходных путей. Но сейчас я просто рад, что это работает.
Объяснение:
источник
C (лязг) ,
346342 байтаCompiler флаги
-DP=printf("(%d,%d)\n"
,-DB=a[i+1]
и-DA=a[i]
Попробуйте онлайн!
источник
i
мировую ценность.while(A)i++;
следуетfor(i=0;A;)i++;
явно установитьi=0
перед использованием в цикле while, вместо использования0
значения по умолчанию на глобальном уровне. Больше не знаю почему, но это требуется в соответствии с мета-правилами. Главным образом потому, что методы должны быть автономными / повторно используемыми, без необходимости сбрасывать глобальные значения между вызовами методов, IIRC.i
значенияStax ,
4639 байтЗапустите и отладьте его
Эта программа принимает ввод в первоначально указанной строковой записи.
источник