Znajdź przebiegi w tablicy
Przebieg jest zdefiniowany jako trzy lub więcej liczb, które zwiększają się w stosunku do poprzedniego ze stałym krokiem. Na przykład [1,2,3] będzie przebiegiem z krokiem 1, [1,3,5,7] będzie przebiegiem z krokiem 2, a [1,2,4,5] nie będzie biegiem.
Możemy wyrazić te przebiegi poprzez zapis „i do j przez s”, gdzie i to pierwsza liczba przebiegów, j to ostatnia liczba przebiegów, a s to krok. Jednak przebiegi kroku 1 będą wyrażone „i do j”.
Używając wcześniej tablic, otrzymujemy:
[1,2,3] -> „1 do 3”
[1,3,5,7] -> „1to7by2”
[1,2,4,5] -> „1 2 4 5”
W tym wyzwaniu Twoim zadaniem jest zrobienie tego dla tablic, które mogą mieć wiele przebiegów.
Przykładowy kod Pythona z rekurencją:
def arr_comp_rec(a, start_index):
# Early exit and recursion end point
if start_index == len(a)-1:
return str(a[-1])
elif start_index == len(a):
return ''
# Keep track of first delta to compare while searching
first_delta = a[start_index+1] - a[start_index]
last = True
for i in range(start_index, len(a)-1):
delta = a[i+1] - a[i]
if delta != first_delta:
last = False
break
# If it ran through the for loop, we need to make sure it gets the last value
if last: i += 1
if i - start_index > 1:
# There is more than 2 numbers between the indexes
if first_delta == 1:
# We don't need by if step = 1
return "{}to{} ".format(a[start_index], a[i]) + arr_comp_rec(a, i+1)
else:
return "{}to{}by{} ".format(a[start_index], a[i], first_delta) + arr_comp_rec(a, i+1)
else:
# There is only one number we can return
return "{} ".format(a[start_index]) + arr_comp_rec(a, i)
Wejście
Tablica posortowanych dodatnich liczb całkowitych (bez duplikatów)
Wynik
Ciąg przebiegów oddzielony spacją lub tablica ciągów przebiegów
Nie musi być chciwy w określonym kierunku
Może mieć końcowe białe znaki
Przypadki testowe
In: [1000, 1002, 1004, 1006, 1008, 1010]
Out: "1000to1010by2"
In: [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]
Out: "1to3 5 8 13 21 34 55 89 144 233"
In: [10, 20, 30, 40, 60]
Out: "10to40by10 60"
In: [5, 6, 8, 11, 15, 16, 17]
Out: "5 6 8 11 15to17"
In: [1, 2, 3, 4, 5, 6, 7, 9, 11, 13, 15, 30, 45, 50, 60, 70, 80, 90, 91, 93]
Out: "1to7 9to15by2 30 45 50to90by10 91 93"
To jest golf golfowy, więc wygrywa najmniej bajtów.
źródło
[4, 5, 6, 7, 9, 11, 13, 15]
nie może być4to6 7to15by2
?)Odpowiedzi:
Galaretka ,
4240 bajtów-2 dzięki Kevinowi Cruijssenowi (odfiltruj dwójki
ḟ2
zamiast zastępować dwójki zerami2,0y
)Pełny program drukujący wynik.
(Jako monadyczny link uzyskana zostanie lista zawierająca mieszaninę liczb całkowitych i znaków)
Wypróbuj online!
(Zbyt mało wydajny, aby największy przypadek testowy mógł zostać ukończony w ciągu 60s, więc usunąłem
[1,2,3,4]
.)W jaki sposób?
źródło
2,0ySƲÞ
można grać w golfaḟ2SƊÞ
na -2 bajty.P
, a nie sumyS
i potrzebowałem zer.Szybki, 246 bajtów
Wypróbuj online!
źródło
K (ngn / k) , 102 bajty
Wypróbuj online!
źródło
JavaScript (ES6), 129 bajtów
Zwraca tablicę ciągów.
Wypróbuj online!
W jaki sposób?
Krok 1
Najpierw dołączamy do każdego numeru sufiks składający się z wiodącego,
'-'
a następnie różnicy z następnym numerem, z wyjątkiem ostatniego wpisu, który pozostaje niezmieniony. Ta nowa tablica jest wymuszana na ciąg.Przykład:
Krok 2
Identyfikujemy wszystkie przebiegi w powstałym ciągu i zastępujemy je odpowiednią notacją.
Przykład:
Krok 3
Na koniec podzieliliśmy ciąg na pozostałe sufiksy, w tym końcowe przecinki.
Przykład:
źródło
Rubin ,
125118 bajtówWypróbuj online!
Wyjaśnienie
Ruby's Enumerable ma przydatną
chunk
metodę, która robi dokładnie to, czego potrzebujemy tutaj - grupuje elementy według kolejnych serii o tej samej wartości zwracanej z bloku, w naszym przypadku - różnicy między wartością bieżącą (x
) a poprzednią (y
).Zastrzeżenie polega na tym, że taka strategia nie uchwyci pierwszego elementu przebiegu, np. Tutaj tylko dwa ostatnie elementy są zgrupowane razem:
Dlatego podczas mapowania na poprawnie sformatowane ciągi, gdy napotkamy nowy potencjalny przebieg (porcja z> 1 elementem), musimy śledzić, czy poprzedni element był pojedynczy (
i=1
), czy był już używany w innym uruchomieniu (i=0
). Jeśli jest nieużywany pojedynczy element, staje się on punktem początkowym przebiegu i obniża próg wielkości porcji z 3 do 2.źródło
R ,
180175 bajtówWypróbuj online!
Pod względem koncepcyjnym jest to część mojej odpowiedzi Ruby , choć oczywiście nieco inna technicznie.
5 bajtów zapisanych przez JayCe.
źródło
rle
ale byłem zbyt leniwy ... możesz zaoszczędzić 1 bajt robiącsum(1|x)
w miejscelength(x)
: TIOcat
na 175 bajtów: TIOR ,
238217 bajtówDzięki @digEmAll za -19 bajtów.
Wypróbuj online!
źródło
F
zamiastn
jak już jest zainicjowane0
, co powinno zaoszczędzić kilka bajtów, tak myślę.split
,diff
irle
. Niestety, zachłanne poszukiwanie biegów oznacza dużo zabawy.'by'[D>1]
dobra sztuczka.JavaScript (Node.js) ,
177173 bajtówWypróbuj online!
źródło
Czysty ,
208... 185 bajtówWypróbuj online!
źródło
Galaretka , 41 bajtów
Wypróbuj online!
Pełny program
źródło
Python 2 ,
170166 bajtówWypróbuj online!
źródło
Python 2 ,
138136 bajtów-2 bajty dzięki Erikowi Outgolfer .
Wypróbuj online!
źródło
gvm (commit 2612106 ) bytecode, 108 bajtów
Oczekuje rozmiaru tablicy w jednym wierszu, a następnie członków w jednym wierszu.
Hexdump:
Przebiegi testowe:
Ręcznie zmontowany z tego:
źródło
05AB1E (starsza wersja) ,
4950 bajtówZbyt długo, ale już się cieszę, że to działa. To wyzwanie jest o wiele trudniejsze, niż się wydaje. Można bez wątpienia dalej grać w golfa.
Σ€g2KO>}¤
jest port2,0ySƲÞṪ
z odpowiedzi galaretki @JonathanAllan (dzięki!).Wypróbuj online. (UWAGA: przekroczono limit czasu dla dużych przypadków testowych).
+1 bajt jako rozwiązanie błędu, ponieważ
0
podczas sortowania zawsze znajduje się w pozycji końcowej.Wyjaśnienie:
źródło
Perl 5 , 154 bajtów
To samo dotyczy spacji, znaków nowej linii, #komentacji i
sub by
:Wypróbuj online!
... za zdanie testów z OP.
źródło
Retina 0.8.2 , 77 bajtów
Wypróbuj online! Link zawiera przypadki testowe. Wyjaśnienie:
Konwertuj na unary.
Oblicz kolejne różnice.
Konwertuj przebiegi do
to...by
składni.Usuń nieprzekształcone różnice i
by1
.Konwertuj na dziesiętny.
źródło