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
, D
i 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ą 8
szafiry, 10
szmaragdy, 4
diamenty i 6
rubiny. 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 4
szafirami, 5
szmaragdami, 2
diamentami i 3
rubinami:
[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 n
cięć, gdzie n
jest 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
- Standardowe luki są zabronione.
- To jest golf golfowy ; najkrótsza odpowiedź (w bajtach) wygrywa.
źródło
[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]
wydaje się, że wynik powinien być[[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]]
, ponieważ ma mniej cięć niż[[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]]
. Czy rozumiem specyfikację poprawnie?Odpowiedzi:
Brachylog , 13 bajtów
Wypróbuj online!
Uwaga: metapredykat
ᵛ
jest nowszy niż to wyzwanie.Wyjaśnienie
Partycje są wyliczane w porządku rosnącym według liczby bloków, więc wynik będzie miał jak najmniej bloków.
źródło
Galaretka , 18 bajtów
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 27 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?
źródło
Mathematica, 118 bajtów
Prawie pobiłem Jelly ... tylko 1 off;)
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
n
cięcia i zwraca listę listn+1
podrzędnych uzyskanych przez wycięcie listy danych wejściowych w tychn
miejscach cięcia;±
do tego celu wykorzystywany jest operator binarnej infix i definiowany rekurencyjnie poprzezl_±c_:=Append[-#±Most@c,#2]&@@l~TakeDrop~Last@c;l_±{}:={l};
. Z powodu znaku ujemnego zaraz poAppend
tym, 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~#3
i 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.źródło
Pyth, 16 bajtów
Wypróbuj online: pakiet demonstracyjny lub testowy
Wyjaśnienie:
źródło
05AB1E , 14 bajtów
Wypróbuj online lub sprawdź wszystkie przypadki testowe .
Wyjaśnienie:
źródło