Nadchodzi rok 2019 i prawdopodobnie wszyscy zauważyli osobliwość tej liczby: w rzeczywistości składa się ona z dwóch pod-liczb (20 i 19) reprezentujących sekwencję kolejnych malejących liczb.
Wyzwanie
Biorąc pod uwagę liczbę x
, zwróć długość maksymalnej sekwencji kolejnych, malejących liczb, które można utworzyć, przyjmując pod-liczby x
.
Uwagi:
- cząstkowe wartości nie może zawierać zera (na przykład
1009
nie może być podzielony10
,09
) - kolejne i malejące oznaczają, że liczba w sekwencji musi być równa poprzedniej liczbie -1, lub (np.
52
nie można podzielić na,5,2
ponieważ5
i2
nie są kolejne2 ≠ 5 - 1
) - sekwencja musi być uzyskane za pomocą pełnego numeru, np
7321
nie można odrzucić7
i uzyskać sekwencję3
,2
,1
- tylko sekwencja może być otrzymana z numerem, na przykład
3211098
nie może być podzielona na dwie sekwencje3
,2
,1
i10
,9
,8
Wejście
- Liczba całkowita (
>= 0
): może być liczbą, łańcuchem lub listą cyfr
Wynik
- Pojedyncza liczba całkowita z maksymalną liczbą malejących podliczb (zauważ, że dolna granica tej liczby to
1
, tzn. Liczba składa się sama w malejącej sekwencji o długości jeden)
Przykłady:
2019 --> 20,19 --> output : 2
201200199198 --> 201,200,199,198 --> output : 4
3246 --> 3246 --> output : 1
87654 --> 8,7,6,5,4 --> output : 5
123456 --> 123456 --> output : 1
1009998 --> 100,99,98 --> output : 3
100908 --> 100908 --> output : 1
1110987 --> 11,10,9,8,7 --> output : 5
210 --> 2,1,0 --> output : 3
1 --> 1 --> output : 1
0 --> 0 --> output : 1
312 --> 312 --> output : 1
191 --> 191 --> output : 1
Główne zasady:
- To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.
Nie pozwól, aby języki gry w golfa zniechęcały Cię do publikowania odpowiedzi w językach niekodujących golfa. Spróbuj znaleźć możliwie najkrótszą odpowiedź na „dowolny” język programowania. - Do odpowiedzi mają zastosowanie standardowe reguły z domyślnymi regułami We / Wy , więc możesz używać STDIN / STDOUT, funkcji / metody z odpowiednimi parametrami i typem zwracanych, pełnych programów. Twoja decyzja.
- Domyślne luki są zabronione.
- Jeśli to możliwe, dodaj link z testem kodu (tj. TIO ).
- Zalecane jest również dodanie wyjaśnienia do odpowiedzi.
210 -> 2,1,0
niepoprawny (to samo z0 -> 0
)? Zadania mówią, że „ pod-liczby nie mogą zawierać zer wiodących ”, czy zero to szczególny przypadek?212019
. Wygląda na to, że nie przeczytałem wszystkich zasad.Odpowiedzi:
Galaretka ,
159 bajtówBugfix dzięki Dennisowi
Wypróbuj online! (O ( N2)) )
321
zajmujenawetpół minuty, ponieważ kod to co najmniejW jaki sposób?
źródło
JavaScript (ES6), 56 bajtów
Port odpowiedzi na Python ArBo jest znacznie krótszy. Jednak nie udaje się to w niektórych przypadkach testowych z powodu zbyt dużej rekurencji.
Wypróbuj online!
JavaScript (ES6), 66 bajtów
Pobiera dane wejściowe jako ciąg.
Wypróbuj online!
Skomentował
źródło
Perl 6 ,
43 4140 bajtów-1 bajt dzięki nwellnhof
Wypróbuj online!
Rozwiązanie oparte na regeksie. Zamiast tego próbuję znaleźć lepszy sposób dopasowania z listy malejącej, ale Perl 6 nie radzi sobie dobrze z partycjami
Wyjaśnienie:
źródło
Python 3 ,
232228187181180150149 bajtów-1 dzięki @ Jonathan Frech
Wypróbuj online!
Początkowy nie golfowy kod:
źródło
s+1 for
może byćs+1for
,(t(n[:j])-t(n[j:j+i])==1)*t(n[0])
może byćt(n[:j])-t(n[j:j+i])==1>=t(n[0])
.if
.Python 2 ,
787473 bajtyWypróbuj online!
-1 bajt dzięki Arnauldowi
Pobiera dane wejściowe jako ciąg. Program dość szybko uruchamia limit głębokości rekurencji Pythona, ale może zakończyć większość przypadków testowych.
Jak to działa
źródło
a+c+1
można skrócić doa-~c
.05AB1E , 10 bajtów
Bardzo powolny, więc poniższe TIO działa tylko dla przypadków testowych poniżej 750 ..
Wypróbuj online .
Wyjaśnienie:
źródło
n!
pon lg n
prostu nie jest tego warte.Pyth, 16 bajtów
Spróbuj go online tutaj , lub sprawdzić wszystkie przypadki testowe od razu tutaj .
źródło
Galaretka , 11 bajtów
Wypróbuj online!
Jak to działa
źródło
Węgiel drzewny , 26 bajtów
Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:
Pętla
i
od 0 do długości wejścia.Pętla
k
od 0 do długości wejścia.Oblicz pierwsze
k
liczby w kolejności malejącej, zaczynając od liczby podanej przez pierwszei
cyfry danych wejściowych, połącz je i zsumuj każdy wynikowy ciąg na predefiniowanej pustej liście.Znajdź pozycję pierwszej pasującej kopii wejścia i zmniejsz ją modulo o 1 więcej niż długość wejścia.
Przykład: Dla wejścia
2019
generowane są następujące ciągi:2019
znajduje się następnie przy indeksie 12, który jest zredukowany modulo 5, aby dać 2 pożądaną odpowiedź.źródło
Haskell, 87 bajtów
Dane wejściowe to lista cyfr.
Wypróbuj online!
Funkcja
#
buduje listę wszystkich możliwych podziałów, patrząc na obaa
do wszystkich podziałów zwracanych przez wywołanie rekurencyjne z resztą input (x<-b#c
), ale tylko wtedy, gdy następny numer nie jest zero (b>0
) (lub jest ostatnim numerem na input (c==[]
)) ia
jest o jeden większy od pierwszego numer odpowiedniego poprzedniego podziałux
(a==x!!0+1
).i
b
z listy wprowadzania do bieżącego numerua
i kontynuowanie reszty wprowadzania ((10*a+b)#c
)Przypadek podstawowy występuje, gdy lista wejściowa jest pusta (tzn. Nie pasuje do wzorca
(b:c)
). Rekurencja rozpoczyna się od bieżącej liczby , któraa
jest0
((0#)
), która nigdy nie uderza w pierwszą gałąź (poprzedzająca
wszystkie poprzednie podziały), ponieważ nigdy nie będzie większa niż jakakolwiek liczba podziałów.Weź długość każdego podziału i znajdź maksimum (
maximum.map length
).Wariant z 87 bajtami:
co w zasadzie działa w ten sam sposób, ale zamiast utrzymywać cały podział na liście, zachowuje tylko parę
(r,x)
długości podziałur
i pierwszą liczbę w podzialex
.źródło
Python 3 ,
302282271 bajtów-10 bajtów dzięki wskazówce @ElPedro.
Pobiera dane wejściowe jako ciąg. Zasadniczo zajmuje coraz większe wycinki liczby od lewej i sprawdza, czy dla tego wycinka liczby można utworzyć sekwencję przy użyciu wszystkich liczb.
Wypróbuj online!
źródło
range
3 razy, możesz zdefiniowaćR=range
poza obiema funkcjami, a następnie użyćR(whatever)
zamiast,range(whatever)
aby zapisać 4 bajty.Japt , 27 bajtów
Wypróbuj online! lub Sprawdź większość przypadków testowych
To nie jest dobry wynik, ale używa unikalnej metody i może być miejsce na grę w golfa o wiele więcej. Działa również wystarczająco dobrze, aby wszystkie przypadki testowe inne niż
201200199198
unikały przekroczenia limitu czasu.Wyjaśnienie:
źródło
21201
ponieważ nie wymuszają prawidłowego wyrównania końca sekwencji (z mojej oryginalnej wersji wiersz „kończy się przecinkiem”). Ta lub ta alternatywa działa.210
mi się uruchomić, ponieważ po 0. nie ma separatora. Oto ustalony 28-bajtowy, który działa.Haskell, 65 bajtów
Dane wejściowe to ciąg znaków.
Wypróbuj online!
Zupełnie inna niż moja inna odpowiedź . Prosta brutalna siła, która wypróbowuje wszystkie listy kolejnych liczb malejących, dopóki nie znajdzie takiej, która jest równa liście wejściowej.
Jeśli mamy ograniczyć liczbę wejściowy 64-bitowych liczb całkowitych, możemy zaoszczędzić 6 bajtów poprzez zapętlenie
y
poprzez[1..19]
, ponieważ największy 64-bitowa liczba całkowita ma 19 cyfr i nie ma potrzeby, aby list testowych z kilku elementów.Haskell, 59 bajtów
Wypróbuj online!
źródło
Python 2 , 95 bajtów
Kolejne wolne, brutalne rozwiązanie.
Wypróbuj online!
źródło
Dyalog APL, 138 bajtów
Trochę kęs, ale działa również szybko dla dużych liczb. Jeśli wypróbujesz to online , poprzedź dfn przez
⎕←
i podaj dane po prawej jako listę cyfr.Wyjaśnienie
Po pierwsze, wewnętrzny dfn po prawej stronie, który rekurencyjnie tworzy listę możliwych sposobów podziału (z
⊂
) listą cyfr. Na przykład1 0 1 0 ⊂ 2 0 1 9
zwraca zagnieżdżony wektor(2 0)(1 9)
.Używamy,
1,
aby dodać kolumnę 1s na początku i kończyć macierz prawidłowych partycji dla ⍵.Teraz pociąg funkcji po lewej stronie w parens. Ze względu
⍨
na lewy argument do pociągu jest wiersz macierzy partycji, a prawy argument to dane wejściowe użytkownika. Pociąg jest stosem widelców ze szczytem jako skrajnie lewym palcem.Jeśli partycja tworzy sekwencję malejących liczb, pociąg zwraca długość sekwencji. W przeciwnym razie zero.
⍤1⊢
stosuje ciąg funkcji między danymi wejściowymi użytkownika a każdym wierszem macierzy partycji, zwracając wartość dla każdego wiersza macierzy.⊢
jest konieczne, aby rozróżnić operand od⍤
argumentu dla pochodnej funkcji⍤
.⌈/
znajduje maksimum.Mogłem znaleźć krótszy algorytm, ale chciałem wypróbować ten sposób, który jest najbardziej bezpośredni i deklaratywny.
źródło
TSQL, 169 bajtów
Uwaga: można to wykonać tylko wtedy, gdy dane wejściowe można przekonwertować na liczbę całkowitą.
Rekurencyjny sql używany do zapętlania.
Gra w golfa:
Nie golfowany:
Wypróbuj to
źródło
R , 101 bajtów
Wypróbuj online!
Minęły ponad 2 tygodnie bez żadnej odpowiedzi R, więc postanowiłem opublikować własną :)
Kod jest dość szybki, ponieważ wykorzystuje „ograniczone” podejście brutalnej siły
Kod i objaśnienie:
źródło