Twoje zadanie tutaj jest proste:
Biorąc pod uwagę listę zestawów liczb całkowitych, znajdź ich zestaw. Innymi słowy, znajdź najkrótszą listę zbiorów liczb całkowitych, które zawierają wszystkie elementy z oryginalnej listy zestawów (ale żadnych innych elementów). Na przykład:
[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
Zestawy są notowane przy użyciu notacji zakresu: [1,4]
oznaczają liczby całkowite 1,2,3,4
. Zbiory mogą być również nieograniczone: [3,]
oznaczają wszystkie liczby całkowite >= 3
i [,-1]
oznaczają wszystkie liczby całkowite <= -1
. Gwarantujemy, że pierwszy element zakresu nie będzie większy niż drugi.
Możesz wybrać zestawy w notacji łańcuchowej lub możesz użyć krotek 2-elementowych, używając stałej liczby całkowitej jako wartości „nieskończonej”. Możesz użyć dwóch różnych stałych do przedstawienia nieskończonej górnej granicy i nieskończonej dolnej granicy. Na przykład w JavaScript możesz używać [3,{}]
do notowania wszystkich liczb całkowitych >= 3
, o ile konsekwentnie używasz {}
wszystkich przypadków testowych.
Przypadki testowe:
[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]
To jest gra w golfa , więc odpowiedz tak krótko, jak to możliwe!
źródło
Infinity
zamiast tego użyć{}
?[1.0, 3.0]
Zamiast[1, 3]
?[1.0, 3.0], [4.0, 5.0]
powinien zostać[1.0, 5.0]
Infinity
i-Infinity
jako danych wejściowych, czy można go przyjmować-999999
i999999
(lub nawet większy / mniejszy)?Odpowiedzi:
R +
intervals
,90 8781 bajtówWypróbuj online!
Dane wejściowe to lista interwałów.
-Inf
iInf
są wbudowane w R. dla nieskończoności minus / plus. Dane wyjściowe to macierz kolumn interwałów.Zwykle nie jest fanem korzystania z niestandardowych bibliotek, ale ta była fajna. TIO nie zostało
intervals
zainstalowane. Możesz go wypróbować we własnej instalacji lub na stronie https://rdrr.io/snippets/Te
intervals
podpory pakietów prawdziwa i całkowita (type = "Z"
) przedziały ireduce
funkcją jest wbudowany w co chce wyzwaniem, ale wyjście wydaje się domyślnie otwartych przedziałów, więc jest potrzebne, aby uzyskać pożądany efekt.close_intervals
+c(1,-1)
Stara wersja zawierała przykłady na liście list, które mogą być wygodne, więc zostawiłem tutaj link.
źródło
function(...)close_intervals(reduce(Intervals(rbind(...),type="Z")))
. Lub jeszcze lepiej możesz sprawdzić za pomocą op, czy pozwalają one na macierz jako dane wejściowe.reduce
iReduce
tam.f=function(...)t(reduce(Intervals(rbind(...),type="Z")))+c(1,-1)
?JavaScript (ES6), 103 bajty
Zaoszczędzono 1 bajt dzięki @Shaggy
Zapisano 1 bajt dzięki @KevinCruijssen
Oczekuje
+/-Infinity
na nieskończone wartości.Wypróbuj online!
W jaki sposób?
Najpierw sortujemy przedziały według ich dolnej granicy, od najniższej do najwyższej. Górne granice są ignorowane.
Następnie iterujemy posortowane przedziały[ pn, qn] , jednocześnie śledząc bieżące dolne i górne granice m i M. , zainicjowane na p1 i q1 , odpowiednio.
Dla każdego przedziału[ pn, qn] :
Skomentował
źródło
p<=M+1
może byćp<M+2
?Python 2 ,
118113112111106105104101 bajtówZaoszczędzono jeden bajt dzięki Mr. Xcoder, jeden dzięki Jonathanowi Frechowi, a trzy dzięki Dead Possum.
Wypróbuj online!
źródło
(b,c),
zapisuje bajt.g
oznacza to, że twoja funkcjaf
nie nadaje się do ponownego użycia i dlatego jest nieprawidłowa?return
staje sięprint
dla innego bajtu.Rubin ,
8976 bajtówWypróbuj online!
Posortuj tablicę, a następnie spłaszcz, dołączając wszystkie zakresy do pierwszego: jeśli zakres pokrywa się z poprzednim, odrzuć 2 elementy z ostatnich 3 (zachowując tylko maksimum).
Rozpłaszcz wszystko na końcu.
źródło
Pascal (FPC) ,
367362357 bajtówWypróbuj online!
Procedura, która pobiera dynamiczną tablicę rekordów składającą się z 2 granic zakresu, modyfikuje tablicę w miejscu, a następnie zapisuje ją na standardowym wyjściu, jeden zakres na linię. (Przepraszam za to skręcone zdanie.) Używa
1/0
do podbicia i-1/0
bez ograniczeń.Wersja do odczytu
Byłoby miło zwrócić tablicę z poprawioną liczbą elementów, ale tablica dynamiczna przekazana do funkcji / procedury nie jest już tablicą dynamiczną ... Najpierw znalazłem to , a potem jest to doskonałe, zadziwiające wyjaśnienie .
To najlepsza struktura danych, jaką udało mi się znaleźć do skracania kodu. Jeśli masz lepsze opcje, możesz coś zasugerować.
źródło
Wolfram Language (Mathematica) , 57 bajtów
Wypróbuj online!
Pobiera dane wejściowe jako listę list
{a,b}
reprezentujących przedział[a,b]
, gdziea
może być-Infinity
ib
może byćInfinity
.Używa wbudowanego
IntervalUnion
, ale oczywiście najpierw musimy masować interwały do kształtu. Aby udawać, że przedziały są liczbami całkowitymi, dodajemy 1 do górnej granicy (upewniając się, że suma[1,3]
i[4,9]
jest[1,9]
). Na koniec cofamy tę operację i przekształcamy wynik z powrotem w listę list.Istnieje również zupełnie inne podejście, które osiąga 73 bajty :
Tutaj, po posortowaniu przedziałów, po prostu zastępujemy dwa kolejne przedziały ich połączeniem, ilekroć byłby to pojedynczy przedział, i powtarzamy, dopóki nie pozostanie taka operacja do wykonania.
źródło
05AB1E (starsza wersja) ,
887978 bajtówNieskończoność jest wprowadzana jako małe litery (
'abcdefghijklmnopqrstuvwxyz'
).Wypróbuj online lub sprawdź wszystkie przypadki testowe .
Ważna uwaga: Gdyby istniał rzeczywisty
Infinity
i-Infinity
, zamiast tego byłoby4342 bajtów . Takniewiele ponad 50%około 30% jest tak samo obejście z powodu brakuInfinity
...Wypróbuj online (z
Infinity
zastąpionymi przez9999999999
i-Infinity
zastąpionymi przez-9999999999
).Można zdecydowanie grać w golfa. W końcu okazało się bardzo, bardzo brzydkie pełne obejść. Ale na razie cieszę się, że to działa.
Wyjaśnienie:
źródło
C (clang) ,
346342 bajtówKompilator flagi
-DP=printf("(%d,%d)\n"
,-DB=a[i+1]
oraz-DA=a[i]
Wypróbuj online!
źródło
i
globalnej wartości.while(A)i++;
należyfor(i=0;A;)i++;
jawnie ustawići=0
przed użyciem go w pętli while, zamiast używania jego0
wartości domyślnej na poziomie globalnym. Nie jestem pewien, dlaczego, ale jest to wymagane zgodnie z meta regułami. Głównie dlatego, że metody powinny być samowystarczalne / wielokrotnego użytku, bez konieczności resetowania wartości globalnych pomiędzy wywołaniami metod, IIRC.i
wartościStax ,
4639 bajtówUruchom i debuguj
Ten program pobiera dane wejściowe w pierwotnie określonym zapisie ciągu.
źródło