Wyzwanie jest naprawdę proste: biorąc pod uwagę liczbę, dzielisz jej cyfry na tablicę mniejszych liczb, dzięki czemu liczby wynikowe nie maleją. Problem polega na tym, że musisz go podzielić tak, aby długość tablicy była maksymalna.
Zmieszany?
- Otrzymujesz dodatnią liczbę całkowitą za pośrednictwem STDIN (lub najbliższej alternatywy), argumentu wiersza poleceń lub argumentu funkcji w dowolnym dogodnym, jednoznacznym formacie wejściowym.
- Musisz podzielić cyfry dziesiętne na ciągłe, rozłączne grupy.
- Tablica liczb reprezentowana przez te grupy cyfr powinna być sortowana (w zwykłej, nie malejącej kolejności) bez zmiany kolejności grup .
- W przypadkach, gdy istnieje więcej niż jedna taka partycja, musisz podzielić dane wejściowe na możliwie jak najwięcej liczb. W przypadku remisów zwróć jeden taki wynik.
- Możesz wyprowadzić tablicę do STDOUT (lub najbliższej alternatywy) lub jako wartość zwracaną przez funkcję. W przypadku STDOUT (lub najbliższej alternatywy) tablica powinna być wydrukowana w dowolnym wygodnym, jednoznacznym formacie listy.
- Liczby podzielone nie powinny mieć wiodących zer. Tak na przykład
1002003
nie mogą być drukowane jako albo[1, 002, 003]
czy[1, 2, 3]
i ważna tylko odpowiedź na to[100, 2003]
.
Przypadki testowe:
123456 -> [1, 2, 3, 4, 5, 6]
345823 -> [3, 4, 5, 8, 23]
12345678901234567890 -> [1, 2, 3, 4, 5, 6, 7, 8, 90, 123, 456, 7890]
102 -> [102]
302 -> [302]
324142 -> [3, 24, 142] OR [32, 41, 42]
324142434445 -> [32, 41, 42, 43, 44, 45]
1356531 -> [1, 3, 5, 6, 531]
11121111111 -> [1, 1, 1, 2, 11, 11, 111]
100202003 -> [100, 202003]
Punktacja
To jest golf golfowy, więc wygrywa najkrótszy kod w bajtach.
code-golf
number
combinatorics
set-partitions
Optymalizator
źródło
źródło
aY
zamiast~Y]
a
. Nie wiem dlaczego.int("01")
jest to błąd w Pyth (nie zdarza się to w Pythonie).n
jest to długość danych wejściowych.Mathematica,
134127 bajtówJest to dość nieefektywne, ponieważ generuje o wiele więcej partycji niż prawidłowe.
324142434445
Sprawdzian przebiega w ciągu kilku sekund, ale nie będę próbować12345678901234567890
.Definiuje nienazwaną funkcję, która przyjmuje liczbę całkowitą i zwraca listę liczb całkowitych.
Wyjaśnienie
Kolejność odczytu tego kodu jest trochę wszędzie, więc podzielę się w kolejności, w jakiej ma być czytany (i w większości oceniany):
d=IntegerDigits@#
pobierz cyfry dziesiętne wejścia i przypisz tę listę dod
.SetPartitions
(co wymagaNeeds@"Combinatorica`";
) daje mi wszystkie części tego. Zwraca jednak znacznie więcej, niż faktycznie chciałem, ponieważ traktuje dane wejściowe jako zestaw . To sprawia, że jest nieefektywny, ale używam tego, ponieważ najkrótszy znany mi sposób uzyskania wszystkich partycji listy jest znacznie dłuższy. Na przykład, jeśli lista jest{1, 2, 3}
funkcją, funkcja zwróci:Zauważ, że a) wszystkie kolejne partycje są w odpowiedniej kolejności i b) partycje są sortowane od grubszej do najlepszej.
Select[...,...&]
następnie filtruje tę listę według anonimowej funkcji przekazanej jako drugi argument.Join @@ # == d
sprawdza, czy faktycznie mamy partycję listy zamiast partycji zestawu ogólnego.#~FreeQ~{0, __}
sprawdza, czy żadna partycja nie zaczyna się od zera na początku.0 <= ## & @@ f /@ #
jest nieco bardziej niejasny. Najpierw mapujemyFromDigits
na każdą listę w partycji, aby odzyskać liczby reprezentowane przez cyfry. Następnie stosujemy się0 <= ##
do tych liczb, gdzie##
odnoszą się do wszystkich liczb. Jeśli partycja to,{1, 23, 45}
to rozwija się do0 <= 1 <= 23 <= 45
, więc sprawdza, czy tablica jest posortowana.Last@
następnie daje mi ostatnią partycję pozostałą po filtrowaniu - to działa, ponieważSetPartitions
już posortowałem partycje, tak że najlepsze są na końcu.f/@
odzyskuje liczby z list cyfr.źródło
Python 3, 134 bajty
Jest trochę niechlujny, ale no cóż. Program generuje rekurencyjnie wszystkie prawidłowe partycje. Interesujące jest to, że aby nie dopuścić do zer wiodących, wszystko, co było konieczne, było dodatkowym
or "1">s[i:]>""
warunek.Pobiera dane wejściowe
f("12345678901234567890")
i zwraca listę liczb całkowitych.źródło
Pyth
626160Wyjaśnienie
Algorytm działa, generując wszystkie liczby binarne między
0
(włącznie) a2^(n-1)
(wyłącznie), gdzien
jest długość danych wejściowych.Cyfry binarne każdego z nich są następnie mapowane na separator (
N
) dla 1 i nic dla 0.Znaki te są następnie wstawiane między każdy znak wejściowy, a wynik jest dzielony przez
N
, w wyniku czego powstaje lista.Wartości na listach są następnie analizowane na liczby całkowite, a listy są sortowane według długości. Następnie pozostaje tylko odfiltrować te nieposortowane i te, które zostały podzielone na zera wiodące, po czym wybierana jest najdłuższa lista.
źródło
(NIEKONKURENCYJNY) Pyth, 25 bajtów
Wypróbuj online!
Jak to działa:
źródło
J, 109 bajtów
Bardzo długi, ale przynajmniej zajmuje pamięć O (n * (2n)!) I czas O (n * log (n) * (2n)!), Gdzie n jest długością wejścia. (Więc nie próbuj uruchamiać go z więcej niż 5 cyframi).
Funkcja przyjmuje dane wejściowe jako ciąg znaków.
Przykłady:
Metoda:
źródło
Haskell, 161 bajtów
Testowe uruchomienie:
Jak to działa: funkcja pomocnika
f
dzieli listę danych wejściowych na każdą możliwą listę list podrzędnych.g
najpierw odrzuca tych, których lista początkowa zaczyna się od,0
a następnie tych, którzy nie mają właściwej kolejności. Sparuj każdą pozostałą listę z jej długością, weź maksimum i odrzuć część długości ponownie.źródło