Благодаря сообществу PPCG Санта сумел отсортировать свои подарки в правильном порядке для перемещения в транспортный док. К сожалению, дорожные указатели сломаны, поэтому он не знает, куда положить все подарки! Все подарки сгруппированы вместе, а не по их диапазонам, что, как признает Санта, было бы лучшей идеей.

Теперь, учитывая подарки в отсортированном порядке, определите все возможные конфигурации минимального диапазона, которые привели бы к тому, что настоящее будет в правильном порядке. То есть найдите все конфигурации с минимальным диапазоном, чтобы сортировка подарков в соответствии с алгоритмом из Задачи № 5 не изменила бы порядок.

Вызов

Минимальная конфигурация диапазона - это список диапазонов, каждый из которых настолько мал, насколько это возможно. То есть, если диапазон предназначен для охвата определенного подмножества подарков, то минимум и максимум диапазона должны быть такими же, как у подмножества. Другими словами, сокращение любого диапазона в обложке сделало бы его уже не обложкой.

Задача состоит в том, чтобы найти все возможные конфигурации минимального диапазона, которые бы соответствовали существующим размерам. Давайте возьмем пример:[3, 1, 2, 5, 4, 7, 6]

Существует тривиальный случай, который заключается в том, чтобы взять диапазон всей существующей конфигурации. В этом случае [[1, 7]]было бы решение.

Для примеров с уникальными элементами еще один тривиальный случай [[3], [1], [2], [5], [4], [7], [6]](потому что диапазоны не нужно упорядочивать).

Для этого примера мы также видим, что [[1, 3], [4, 7]]и [[1, 3], [4, 5], [6, 7]]будет работать, а также [[1, 3], [5], [4], [6, 7]]и [[1, 3], [4, 5], [7], [6]].

Окончательный ответ [3, 1, 2, 5, 4, 7, 6]будет [[[3], [1], [2], [5], [4], [7], [6]], [[3], [1], [2], [5], [4], [6, 7]], [[3], [1], [2], [4, 5], [7], [6]], [[3], [1], [2], [4, 5], [6, 7]], [[3], [1], [2], [4, 7]], [[3], [1, 2], [5], [4], [7], [6]], [[3], [1, 2], [5], [4], [6, 7]], [[3], [1, 2], [4, 5], [7], [6]], [[3], [1, 2], [4, 5], [6, 7]], [[3], [1, 2], [4, 7]], [[1, 3], [5], [4], [7], [6]], [[1, 3], [5], [4], [6, 7]], [[1, 3], [4, 5], [7], [6]], [[1, 3], [4, 5], [6, 7]], [[1, 3], [4, 7]], [[1, 5], [7], [6]], [[1, 5], [6, 7]], [[1, 7]]].

Спецификации форматирования

Входные данные будут представлены в виде простого списка натуральных чисел в пределах разумного поддерживаемого диапазона номеров вашего языка в любом приемлемом формате. Входные данные могут содержать дубликаты элементов. Выходные данные должны быть представлены в виде трехмерного списка натуральных чисел в любом приемлемом формате.

Каждый диапазон в вашем выводе (который находится на втором слое) может быть представлен как [min, max], [num]если это диапазон с одним значением, или как весь диапазон, но ваш формат вывода должен быть согласованным. Пожалуйста, укажите, если вы хотите использовать немного другой разумный формат вывода.

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

Ваше решение может возвращать диапазоны в любом порядке, и это не должно быть детерминированным.

правила

Применяются стандартные лазейки
Это Код-гольф поэтому самый короткий ответ в байтах выигрывает
Ответ не будет принят

Тест-кейс для списка с дублирующимися элементами:

2 3 2 4 -> [[[2, 3], [4]], [[2, 4]]]

Реализация эталона

В заголовке есть ссылка.

^{Примечание: я черпал вдохновение для этой серии испытаний из Advent Of Code . У меня нет связи с этим сайтом}

Вы можете увидеть список всех испытаний в серии, посмотрев раздел «Связанные» первой задачи здесь .

Удачного игры в гольф!

code-golf array-manipulation set-partitions HyperNeutrino
источник

3

Mathematica, 106 байт

sSelect[MinMax/@s~TakeList~#&/@Join@@Permutations/@IntegerPartitions@Tr[1^s],Unequal@@Join@@Range@@@#&]

Попробуйте онлайн!

Мартин спас 16 байтов

J42161217
источник

3

Брахилог , 17 16 байт

{~c⟨⌋⟦₂⌉⟩ᵐ.c≠∧}ᶠ

Работает со списками с дубликатами. Диапазоны представлены списками элементов, которые они содержат. Попробуйте онлайн!

объяснение

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

{~c⟨⌋⟦₂⌉⟩ᵐ.c≠∧}ᶠ  Input is a list.
{             }ᶠ  Compute all possible outputs for this predicate:
 ~c                Break the list into contiguous blocks.
   ⟨    ⟩ᵐ         For each block,
    ⌋  ⌉           take its minimum and maximum,
     ⟦₂            and create the range between them.
          .        This is the output.
           c       Also, if you concatenate the output,
            ≠      its elements are distinct.
             ∧     Prevent the interpreter from thinking this is also the output.

Zgarb
источник

1

JavaScript (ES6), 166 164 байта

Редактировать: обновленная версия, которая теперь поддерживает дубликаты

Печатает результаты непосредственно на консоль в формате [min, max] .

f=(a,r=[],l=0)=>a[l++]?f([...a],r,l,f(a,[...r,[Math.min(...x=a.splice(0,l)),Math.max(...x)]])):a[0]|r.some(([x,y],i)=>r.some(([z])=>i--&&z>=x&z<=y))||console.log(r)

Контрольные примеры

Показать фрагмент кода

f=(a,r=[],l=0)=>a[l++]?f([...a],r,l,f(a,[...r,[Math.min(...x=a.splice(0,l)),Math.max(...x)]])):a[0]|r.some(([x,y],i)=>r.some(([z])=>i--&&z>=x&z<=y))||console.log(r)

consoleLog = console.log;
console.log = s => consoleLog(JSON.stringify(s))

consoleLog('Test case: [3, 1, 2, 5, 4, 7, 6]')
f([3, 1, 2, 5, 4, 7, 6])
consoleLog('Test case: [2, 3, 2, 4]')
f([2, 3, 2, 4])

Развернуть фрагмент

Arnauld
источник

0

Python 2 , 179 байт

lambda l:[l for l in[[range(min(x),max(x)+1)for x in P]for P in p(l)]if len(sum(l,[]))==len(set(sum(l,[])))]
p=lambda l:[[l[:i]]+a for i in range(1,len(l))for a in p(l[i:])]+[[l]]

Попробуйте онлайн!

Выводит список полных диапазонов.

Сильно вдохновлен эталонной реализацией.

Строит все разделы, затем диапазоны min / max для каждого раздела. Список диапазонов действителен, если никакое значение не появляется более одного раза в списке.

sum(l,[]) выравнивает список списков и позволяет мне проверять дубликаты:

l=[[1, 2], [2, 3]]
sum(l,[]) = [1,2,2,3]
len([1,2,2,3] == len(set([1,2,2,3]))  -> False (duplicates)

TFeld
источник

0

Pyth , 17 байт

f{IsTmm}hSkeSkd./

Попробуй это здесь!

Теперь это намного лучше. Выводит все диапазоны. Смотрите историю изменений для предыдущей версии (ошеломляющие 31 байт).

Как это работает

f {IsTmm} hSkeSkd ./ ~> Полная программа.

               ./ ~> Список разделов.
     m ~> Карта с использованием переменной d.
      md ~> Отобразить d, используя переменную k.
        hSk ~> Минимум k.
           eSk ~> Максимум k.
       } ~> Включающий диапазон целых чисел.
f ~> Фильтровать эти ...
   Что, когда сплющено,
 {I ~> Инвариантны над дедупликацией.

Мистер Xcoder
источник

Advent Challenge 6: Перемаркировка транспортного дока!