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 1002003nie 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.

Pyth, 34

FNyUz#aYmv:zhdedC,+0N+NlzB)efqSTTY

Wypróbuj online tutaj . Zauważ, że ma to złożoność czasową (i przestrzenną) O (n). Dlatego przypadek testowy 12345678901234567890w kompilatorze online trwa zbyt długo. Zamiast tego użyj trybu offline (1 minuta na moim laptopie).

To tylko moja pierwsza próba. Może być miejsce na ulepszenia.

Najpierw kilka pomysłów, jak działa mój algorytm.

• Interpretuję dane wejściowe jako ciąg, a nie liczbę.
• Następnie tworzę wszystkie możliwe podzbiory [0, 1, 2, ..., len(n-1)]
• Dla każdego z tych podzbiorów (weźmy [1, 4, 5]) dzielę łańcuch wejściowy na część, używając tych liczb. [input[0:1], input[1, 4], input[4,5], input[5,len(input)]].
• Następnie próbuję przekonwertować te liczby na ciągi. Mogą występować dwa problemy. Pyth (lub Python) zgłasza wyjątek dla pustego łańcucha i ciągu liczb rozpoczynającego się od 0. Dlatego używam try - catchbloku (w rzeczywistości pętli nieskończoności z natychmiastową przerwą). Jeśli konwersja zakończyła się powodzeniem, dodaję wynik do listyY .
• Po obsłużeniu wszystkich podzbiorów filtruję listę pod Ykątem wyników, które są już posortowane i drukuję ostatni (ostatni ma najwięcej grup).

Teraz szczegółowe wyjaśnienie:

                            Implicit: z = input() (z is a String!)
                                      Y = empty list
FNyUz                       for each subset N of [0, 1, 2, ..., len(z)-1]:

     #                         start try-catch block (actually an infinite loop, 
                               but the Python implementation uses a try catch. 

      aY                          append to Y:
                C,+0N+Nlz            zip([0] + N, N + [len(z)])
        m                            map each element d to
          :zhded                     z[d[0]:d[-1]]
         v                           evaluated
                         B        if this didn't throw an exception already, end the infinite loop
                          ) end for loop   

 f    Y      filter Y for elements T, for which
  qSTT           sorted(T) == T
e            and print the last one (the subsets generated with yUz are sorted 
             by length, so the last one has the most groups)

Mathematica, 134 127 bajtów

Jest to dość nieefektywne, ponieważ generuje o wiele więcej partycji niż prawidłowe. 324142434445Sprawdzian przebiega w ciągu kilku sekund, ale nie będę próbować 12345678901234567890.

f/@Last@Select[Needs@"Combinatorica`";f=FromDigits;SetPartitions[d=IntegerDigits@#],0<=##&@@f/@#&&Join@@#==d&&#~FreeQ~{0,__}&]&

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ę do d.

• SetPartitions(co wymaga Needs@"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:

  {{{1, 2, 3}}, {{1}, {2, 3}}, {{1, 2}, {3}}, {{1, 3}, {2}}, {{1}, {2}, {3}}}
  

  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 mapujemy FromDigitsna 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ę do 0 <= 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.
• Na koniec f/@odzyskuje liczby z list cyfr.

Python 3, 134 bajty

def f(s,n=0,L=[],R=[],i=0):
 while s[i:]:i+=1;m=int(s[:i]);R=max([f(s[i:],m,L+[m]),R][m<n or"1">s[i:]>"":],key=len)
 return[L,R][s>""]

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 dodatkowymor "1">s[i:]>"" warunek.

Pobiera dane wejściowe f("12345678901234567890")i zwraca listę liczb całkowitych.

Pyth 62 61 60

JlzKkef&qJsml`dTqTSTolNmmibTcjKsC,z+m>Ndt>+*J]0jk2_JKNU^2-J1

Wyjaśnienie

Algorytm działa, generując wszystkie liczby binarne między 0(włącznie) a 2^(n-1)(wyłącznie), gdzie njest 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.

Jlz                                                   set J to len(input)
Kk                                                    set K to ""
e                                                     take the last of:
 f&                                                    only take lists where:
   qJsml`dT                                             sum of string lengths of items
                                                        is equal to length of input and
           qTST                                         list is in order
               olN                                       sort by length
                  m                                       map k over...
                   mibT                                    convert items to int (base-10)
                       c                        N           split by N
                        jK                                   join by ""
                          s                                   sum to combine tuples
                           C,z                                 zip input with
                              +                K                append [""] for equal lengths
                               m>Nd                              replace 1 with N, 0 with ""
                                   t                              take all but first
                                    >        _J                    take len(input) last values
                                     +                              pad front of binary with
                                      *J]0                           [0] times input's length
                                          jk2                        current k in binary
                                                 U^2-J1  range 0..2^(len(input)-1)-1

(NIEKONKURENCYJNY) Pyth, 25 bajtów

ef&&Fmnhd\0T.A<V=NsMTtN./

Wypróbuj online!

Jak to działa:

ef&&Fmnhd\0T.A<V=NsMTtN./  Q = eval(input())
                         ./  all partitions of Q
 f                       ./  filter all partitions of Q where:
  &                            both:
   &Fmnhd\0T                     neither substring starts with "0"
                               and:
            .A<V=NsMTtN          all entries are less than their proceeding ones
e                            returns the last amongst the filtered partitions

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).

f=.3 :0
>({~(i.>./)@:(((-:/:~)@(#$])*#)@>))<@".(' 0';' _1')rplc"1~(#~y-:"1' '-."#:~])(i.!2*#y)A.y,' '#~#y
)

Funkcja przyjmuje dane wejściowe jako ciąg znaków.

Przykłady:

   f every '5423';'103';'1023'
  5 423
103   0
 10  23

Metoda:

• Dodaj taką samą liczbę spacji do wejścia, jak jego długość.
• Pozwól na to w każdy możliwy sposób.
• Sprawdź, czy ciąg bez spacji jest taki sam jak dane wejściowe (tzn. Jest to jego partycja).
• Zamień „0” na „_1”, aby unieważnić wiodące rozwiązania zerowe.
• Oceń każdy ciąg.
• Znajdź najdłuższą listę, która jest również posortowana. To jest wartość zwracana.

Haskell, 161 bajtów

(#)=map
f[x]=[[[x]]]
f(h:t)=([h]:)#f t++(\(a:b)->(h:a):b)#f t
g l=snd$maximum[(length x,x::[Int])|x<-[read#y|y<-f l,all((/='0').head)y],and$zipWith(>=)=<<tail$x]

Testowe uruchomienie:

*Main> mapM_ (print . g) ["123456","345823","12345678901234567890","102","302","324142","324142434445","1356531","11121111111","100202003"]
[1,2,3,4,5,6]
[3,4,5,8,23]
[1,2,3,4,5,6,7,8,90,123,456,7890]
[102]
[302]
[32,41,42]
[32,41,42,43,44,45]
[1,3,5,6,531]
[1,1,1,2,11,11,111]
[100,202003]

Jak to działa: funkcja pomocnika fdzieli listę danych wejściowych na każdą możliwą listę list podrzędnych. gnajpierw odrzuca tych, których lista początkowa zaczyna się od, 0a 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.