<< Poprzedni Następny >>

Dzięki społeczności PPCG Mikołajowi udało się uporządkować prezenty w odpowiedniej kolejności, aby przenieść się do doku transportowego. Niestety znaki doku transportowego są zepsute, więc nie wie, gdzie położyć wszystkie prezenty! Wszystkie prezenty są pogrupowane razem, a nie według ich zakresów, co według Świętego Mikołaja byłoby lepszym pomysłem.

Teraz, biorąc pod uwagę prezenty w posortowanej kolejności, określ wszystkie możliwe konfiguracje minimalnego zakresu, które spowodowałyby, że teraźniejszość byłaby w prawidłowej kolejności. Oznacza to, że znajdź wszystkie konfiguracje o minimalnym zakresie, tak aby sortowanie prezentów zgodnie z algorytmem w Wyzwaniu nr 5 nie zmieniło kolejności.

Wyzwanie

Konfiguracja minimalnego zakresu to lista zakresów, dzięki czemu każdy z nich jest tak mały, jak to możliwe. Oznacza to, że jeśli wyznaczony jest zakres obejmujący określony podzbiór prezentów, wówczas minimalny i maksymalny zakres musi być taki sam jak w tym podzbiorze. Innymi słowy, zmniejszenie dowolnego zakresu w osłonie spowodowałoby, że przestałby być osłoną.

Wyzwaniem jest znalezienie wszystkich możliwych konfiguracji minimalnego zakresu, które miałyby zastosowanie do obecnych rozmiarów. Weźmy przykład:[3, 1, 2, 5, 4, 7, 6]

Istnieje trywialny przypadek, który polega na objęciu całej obecnej konfiguracji. W takim przypadku [[1, 7]]byłoby rozwiązaniem.

Dla przykładów z unikalnymi elementami, innym trywialnym przypadkiem byłby [[3], [1], [2], [5], [4], [7], [6]](ponieważ zakresów nie trzeba porządkować).

W tym przykładzie również to widzimy [[1, 3], [4, 7]]i [[1, 3], [4, 5], [6, 7]]działałoby, a także [[1, 3], [5], [4], [6, 7]]i [[1, 3], [4, 5], [7], [6]].

Ostateczna odpowiedź na [3, 1, 2, 5, 4, 7, 6]byłoby [[[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]]].

Specyfikacja formatowania

Dane wejściowe zostaną podane w postaci płaskiej listy dodatnich liczb całkowitych w rozsądnym obsługiwanym zakresie liczbowym Twojego języka w dowolnym rozsądnym formacie. Dane wejściowe mogą zawierać zduplikowane elementy. Dane wyjściowe należy podać jako trójwymiarową listę liczb całkowitych dodatnich w dowolnym rozsądnym formacie.

Każdy zakres na wyjściu (który znajduje się na drugiej warstwie) może być reprezentowany jako [min, max], [num]jeśli jest to zakres pojedynczej wartości, lub jako cały zakres, ale format wyjściowy musi być spójny. Podaj, czy chcesz użyć nieco innego rozsądnego formatu wyjściowego.

Zduplikowane wartości muszą być objęte jednym zakresem danych wyjściowych; to znaczy, żadne dwa zakresy na wyjściu nie mogą się pokrywać.

Twoje rozwiązanie może zwrócić zakresy w dowolnej kolejności i nie musi to być deterministyczne.

Zasady

• Obowiązują standardowe luki
• To jest golf-golf więc wygrywa najkrótsza odpowiedź w bajtach
• Żadna odpowiedź nie zostanie zaakceptowana

Przypadek testowy dla listy ze zduplikowanymi elementami:

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

Wdrożenie referencyjne

Nagłówek jest linkiem.

^{Uwaga: Inspirację do tej serii wyzwań czerpałem z Advent Of Code . Nie mam powiązań z tą stroną}

Możesz zobaczyć listę wszystkich wyzwań w serii, patrząc na sekcję „Połączone” pierwszego wyzwania tutaj .

Miłej gry w golfa!

Mathematica, 106 bajtów

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

Wypróbuj online!

Martin zapisał 16 bajtów

Brachylog , 17 16 bajtów

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

Działa również na listach z duplikatami. Zakresy są reprezentowane przez listy elementów, które zawierają. Wypróbuj online!

Wyjaśnienie

Chodzi o to, aby podzielić listę na bloki i przekształcić bloki w zakresy, a następnie sprawdzić, czy się nie pokrywają.

{~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.

JavaScript (ES6), 166 164 bajtów

Edycja: zaktualizowana wersja, która obsługuje teraz duplikaty

Drukuje wyniki bezpośrednio na konsoli w formacie [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)

Przypadki testowe

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])

Python 2 , 179 bajtów

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]]

Wypróbuj online!

Wyświetla listę pełnych zakresów.

Mocno zainspirowany referencyjnym wdrożeniem.

Tworzy wszystkie partycje, a następnie zakresy min / max dla każdej partycji. Lista zakresów jest ważna, jeśli żadna wartość nie pojawia się na liście więcej niż jeden raz.

sum(l,[]) spłaszcza listę list i pozwala mi sprawdzić, czy są duplikaty:

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

Pyth , 17 bajtów

f{IsTmm}hSkeSkd./

Wypróbuj tutaj!

Teraz jest o wiele lepiej. Wyprowadza całe zakresy. Zobacz historię zmian poprzedniej wersji (oszałamiająco 31 bajtów).

Jak to działa

f {IsTmm} hSkeSkd./ ~> Pełny program.

               ./ ~> Lista partycji.
     m ~> Mapa przy użyciu zmiennej d.
      md ~> Mapuj d używając zmiennej k.
        hSk ~> Minimum k.
           eSk ~> Maksymalna wartość k.
       } ~> Uwzględniający zakres liczb całkowitych.
f ~> Filtruj te ...
   sT ~> Które po spłaszczeniu
 {I ~> Są niezmienne w stosunku do deduplikacji.