tło

Zainspirowało mnie ostatnie wideo 3Blue1Brown na temat problemu rozszczepiania naszyjnika (lub, jak to nazywa, problemu skradzionego naszyjnika) i jego związku z twierdzeniem Borsuk-Ulam .

W tym problemie dwóch złodziei ukradło cenny naszyjnik składający się z kilku różnych rodzajów klejnotów. Istnieje parzysta liczba każdego rodzaju klejnotów, a złodzieje chcą równomiernie rozdzielić każdy rodzaj klejnotu między nimi. Problem polega na tym, że muszą to zrobić, dzieląc naszyjnik na pewną liczbę sąsiadujących ze sobą segmentów i rozdzielając segmenty między dwa z nich.

Oto przykład z czterema rodzajami oznaczone biżuteryjnych S, E, Di R(w przypadku, Emerald szafir, diament i rubin, odpowiednio). Powiedzmy, że naszyjnik wygląda następująco:

[S,S,S,E,S,D,E,R,S,R,E,S,S,S,D,R,E,E,R,E,D,E,R,R,D,E,E,E]

Są 8szafiry, 10szmaragdy, 4diamenty i 6rubiny. Naszyjnik możemy podzielić w następujący sposób:

[[S],[S],[S,E,S,D,E,R,S],[R,E,S,S,S,D,R,E,E,R,E,D,E],[R,R,D,E,E,E]]

Następnie, jeśli przekażemy pierwszy, trzeci i piąty segment jednemu złodziejowi, a drugi i czwarty segment drugiemu złodziejowi, każdy skończy z 4szafirami, 5szmaragdami, 2diamentami i 3rubinami:

[S],    [S,E,S,D,E,R,S],                            [R,R,D,E,E,E]
    [S],                [R,E,S,S,S,D,R,E,E,R,E,D,E],

Przy użyciu 0-indexing cięcia te występują przy indeksach [1,2,9,22].

Cel

Okazuje się, że takiego sprawiedliwego podziału zawsze można dokonać przy użyciu co najwyżej ncięć, gdzie njest liczba rodzajów klejnotów. Twoim zadaniem jest napisanie kompletnego programu lub funkcji, która przyjmuje naszyjnik jako dane wejściowe i generuje minimalny taki podział (najmniejszą liczbę cięć).

Wejście

Dane wejściowe mogą być w dowolnym dogodnym formacie. Naszyjnik powinien być ciągiem klejnotów i niczym więcej; np. lista liczb całkowitych, słownik z kluczami reprezentującymi typy klejnotów i wartości będące listami indeksów. Opcjonalnie możesz podać długość naszyjnika lub liczbę różnych rodzajów klejnotów, ale nie powinieneś przyjmować żadnych innych danych.

Możesz założyć, że naszyjnik wejściowy jest prawidłowy. Nie musisz zajmować się przypadkiem, w którym znajduje się nieparzysta liczba klejnotów danego typu lub naszyjnik jest pusty.

Wynik

Ponownie, wyjście może być w dowolnym dogodnym formacie; np. lista segmentów, lista wyciętych pozycji, słownik z kluczami reprezentującymi dwóch złodziei i wartości będące listami segmentów itp. Segmenty mogą być reprezentowane przez ich indeks początkowy, indeks końcowy, listę kolejnych indeksów, listę klejnotów, ich długości itp. Możesz użyć 0- lub 1- indeksowania. Jeśli kolejność nie jest znacząca dla twojego formatu, wtedy twoje wyniki mogą być w dowolnej kolejności. Oto powyższy wynik w kilku różnych formatach:

list of segments: [[S],[S],[S,E,S,D,E,R,S],[R,E,S,S,S,D,R,E,E,R,E,D,E],[R,R,D,E,E,E]]
list of cuts:     [1,2,9,22]
list of lengths:  [1,1,7,13,6]
dictionary:       {'thief1' : [(R,R,D,E,E,E),(S),(S,E,S,D,E,R,S)], 'thief2' : [(S),(R,E,S,S,S,D,R,E,E,R,E,D,E)]}

Zauważ, że kolejność jest ważna na liście segmentów (segmenty naprzemiennie między złodziejami) i liście długości (w celu identyfikacji segmentów), ale nie na liście cięć lub w słowniku. Edycja: Greg Martin wskazał, że nie byłyby to prawidłowe wyniki, ponieważ sprawiedliwy podział można uzyskać w dwóch cięciach

Przypadki testowe

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

Notatki

1. Standardowe luki są zabronione.
2. To jest golf golfowy ; najkrótsza odpowiedź (w bajtach) wygrywa.

Brachylog , 13 bajtów

~c.ġ₂z₁Ċcᵐoᵛ∧

Wypróbuj online!

Uwaga: metapredykat ᵛjest nowszy niż to wyzwanie.

Wyjaśnienie

~c.ġ₂z₁Ċcᵐoᵛ∧  Input is a list, say L = [1,2,2,2,1,2,3,3]
~c.            Output is a partition of the input: [[1,2,2],[2,1,2],[3],[3]]
  .ġ₂          Split the output into chunks of length 2: [[[1,2,2],[2,1,2]],[[3],[3]]]
     z₁        Zip (transpose) the chunks: [[[1,2,2],[3]],[[2,1,2],[3]]]
       Ċ       This is a 2-element list (forbid the trivial partition).
        cᵐ     Concatenate both: [[1,2,2,3],[2,1,2,3]]
          oᵛ   If you sort both lists, they are equal.
            ∧  Don't unify with the output.

Partycje są wyliczane w porządku rosnącym według liczby bloków, więc wynik będzie miał jak najmniej bloków.

Galaretka , 18 bajtów

s2ZFṢ$€E¬,L
ŒṖṖÇÞḢ

Wypróbuj online!

Nieefektywny - przykład ma 28 klejnotów, które nie będą działać bez dużych zasobów, ponieważ pierwszym krokiem tej implementacji byłoby zbudowanie listy 2 ²⁷ możliwych partycji.

Zwraca listę list - segmenty w kolejności, aby rozdzielić je między alternatywnymi złodziejami. (Re wyjście TIO: gdy lista zawiera tylko jeden element, niejawny wydruk nie przeszkadza w nawiasach []).

W jaki sposób?

s2ZFṢ$€E¬,L - Link 1, get (isUnfair, Slices): A possible partition
s2          - split into slices of length 2 (any odd one on it's own at the end)
  Z         - transpose (first item is one thief's slices, second is the others)
     $€     - last two links as a monad for €ach
   F        -     flatten
    Ṣ       -     sort
       E    - equal? (theif1's jewels == theif2's jewels)
        ¬   - not
          L - length (number of slices in the partition)
         ,  - pair

ŒṖṖÇÞḢ - Main link: necklace
ŒṖ     - all partitions
  Ṗ    - pop, we must remove the rightmost one...
              because Link 1 will say it is fair, and it will have length 1!
              (a list of one thing has all entries equal)
    Þ  - sort by
   Ç   -     last link (1) as a monad
     Ḣ - head (get the first one, i.e. minimal isUnfair, then minimal length)

Mathematica, 118 bajtów

Prawie pobiłem Jelly ... tylko 1 off;)

SelectFirst[l_±c_:=Append[-#±Most@c,#2]&@@l~TakeDrop~Last@c;l_±{}:={l};i=#;(i±#)&/@Range@#2~Subsets~#3,Tr[Tr/@#]==0&]&

Czysta funkcja przyjmująca trzy argumenty: naszyjnik jako listę tokenów takich jak {A, A, A, A, B, C, D, B, C, D, B, B}; długość naszyjnika; i liczba różnych czasów klejnotów. Zwraca listę podlist w postaci {{A, A}, {-A, -A, -B, -C, -D, -B}, {C, D, B, B}}, w której tokeny bez znaków ujemnych trafiają do jednego złodzieja, a tokeny z znakami ujemnymi do drugiego złodzieja. (Chociaż jest to nadmiarowa informacja, algorytm prowadzi do tej reprezentacji, a usunięcie znaków ujemnych kosztowałoby kilka bajtów).

Najpierw musimy zaimplementować funkcję, która pobiera listę i zestaw miejsc ncięcia i zwraca listę list n+1podrzędnych uzyskanych przez wycięcie listy danych wejściowych w tych nmiejscach cięcia; ±do tego celu wykorzystywany jest operator binarnej infix i definiowany rekurencyjnie poprzez l_±c_:=Append[-#±Most@c,#2]&@@l~TakeDrop~Last@c;l_±{}:={l};. Z powodu znaku ujemnego zaraz po Appendtym, podlisty naprzemiennie mają i nie mają znaków ujemnych dołączonych do każdego tokena.

Następnie generujemy wszystkie możliwe zestawy elementów ciętych, których długość jest co najwyżej liczbą rodzajów klejnotów, używając Range@#2~Subsets~#3i za pomocą , i=#;(i±#)&/@aby zastosować ±operator (z listą wejściową klejnotów) do każdego z tych zestawów cięcia po kolei.

Na koniec SelectFirst[...,Tr[Tr/@#]==0&]&wybiera pierwszy wynikający z podziałów naszyjnik, który jest sprawiedliwy. Czyni to dosłownie sumując wszystkie elementy ze wszystkich list podrzędnych; Mathematica jest wystarczająco mądra, aby w oczywisty sposób anulować pozytywne i negatywne kopie każdego tokena.

Pyth, 16 bajtów

hfqFSMsM.TcT2t./

Wypróbuj online: pakiet demonstracyjny lub testowy

Wyjaśnienie:

hfqFSMsM.TcT2t./Q   implicit Q (=input) at the end
              ./Q   create all partitions of the input list 
                    (they are already sorted by number of cuts)
             t      remove the partition with zero splits
 f                  filter for partitions T, which satisfy:
          cT2          chop into pieces of length 2
        .T             transpose to get the pieces of each thieve
    SMsM               combine all pieces for each thieve and sort the results
  qF                   check if they got the same jewels
h                   print the first such partition

05AB1E , 14 bajtów

.œ¨ʒ2ôζε˜{}Ë}¤

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

.œ                # All partitions of the (implicit) input
                  #  i.e. [2,3,2,1,3,1]
                  #   → [[[2],[3],[2],[1],[3],[1]],[[2],[3],[2],[1],[3,1]],
                  #      ...,[[2,3,2,1,3,1]]]
  ¨               # Remove the last one
   ʒ        }     # Filter this list by:
    2ô            # Split it into parts of 2
                  #  i.e. [[2,3],[2],[1],[3,1]] → [[[2,3],[2]],[[1],[3,1]]]
                  #  i.e. [[2,3,2],[1,3],[1]] → [[[2,3,2],[1,3]],[[1]]]
      ζ           # Swap rows and columns (using space as filler if necessary)
                  #  i.e. [[[2,3],[2]],[[1],[3,1]]] → [[[2,3],[1]],[[2],[3,1]]]
                  #  i.e. [[[2,3,2],[1,3]],[[1]]] → [[[2,3,2],[1]],[[1,3]," "]]
       ε  }       # Map each inner list to:
        ˜         # Flatten the list
                  #  i.e. [[2,3],[1]] → [2,3,1]
                  #  i.e. [[1,3]," "] → [1,3," "]
         {        # Sort the list
                  #  i.e. [2,3,1] → [1,2,3]
                  #  i.e. [1,3," "] → [1,3," "]
           Ë      # Check if both sorted lists are equal
                  # (if not, remove them from the partitions)
             ¤    # After filtering, take the last one as result (and output implicitly)
                  #  i.e. [[[2],[3,2],[1,3],[1]],[[2,3],[2],[1],[3,1]]]
                  #   → [[2,3],[2],[1],[3,1]]