El desafío es realmente simple: dado un número, se dividen sus dígitos en una matriz de números más pequeños de modo que los números resultantes no disminuyan. El problema es que debe dividirlo de modo que la longitud de la matriz sea máxima.

¿Confuso?

• Se le da un número entero positivo a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función en cualquier formato de entrada conveniente y sin ambigüedades.
• Debe dividir los dígitos decimales del número en grupos contiguos y disjuntos.
• La matriz de números representados por estos grupos de dígitos debe ordenarse (en el orden habitual, no decreciente) sin reorganizar los grupos .
• En los casos en que exista más de una de estas particiones, debe dividir la entrada en tantos números como sea posible. En caso de empate, devuelva uno de esos resultados.
• Puede enviar la matriz a STDOUT (o la alternativa más cercana) o como un valor de retorno de función. En el caso de STDOUT (o la alternativa más cercana), la matriz debe imprimirse en cualquier formato de lista conveniente y sin ambigüedades.
• Los números divididos no deben tener ceros a la izquierda. Entonces, por ejemplo 1002003, no se puede imprimir como o [1, 002, 003]o [1, 2, 3]y la única respuesta válida es [100, 2003].

Casos de prueba:

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]

Puntuación

Este es el código de golf, por lo que el código más corto en bytes gana.

Pyth, 34

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

Pruébelo en línea aquí . Tenga en cuenta que esto tiene una complejidad de tiempo (y espacio) de O (n). Por lo tanto, el caso de prueba 12345678901234567890lleva demasiado tiempo en el compilador en línea. Utilice el fuera de línea en su lugar (1 minuto en mi computadora portátil).

Este es solo mi primer intento. Puede haber espacio para mejoras.

Primero algunas ideas de cómo funciona mi algoritmo.

• Interpreto la entrada como una cadena y no como un número.
• Luego creo todos los subconjuntos posibles de [0, 1, 2, ..., len(n-1)]
• Para cada uno de estos subconjuntos (tomemos [1, 4, 5]), dividí la cadena de entrada en parte usando estos números. [input[0:1], input[1, 4], input[4,5], input[5,len(input)]].
• Luego trato de convertir estos números en cadenas. Puede haber dos problemas. Pyth (o Python) lanza una excepción para una cadena vacía y para una cadena de números que comienzan con 0. Por lo tanto, uso un try - catchbloque (en realidad bucle infinito con una interrupción inmediata) Si la conversión fue exitosa, agrego el resultado a una listaY .
• Después de manejar todos los subconjuntos, filtro la lista Yde resultados, que ya están ordenados e imprimo el último (el último tiene la mayoría de los grupos).

Ahora la explicación detallada:

                            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 bytes

Esto es bastante ineficiente ya que genera muchas más particiones que las válidas. El 324142434445caso de prueba se ejecuta en unos pocos segundos, pero no lo intentaría 12345678901234567890.

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

Esto define una función sin nombre que toma un entero y devuelve una lista de enteros.

Explicación

El orden de lectura de este código está un poco por todas partes, por lo que me desglosaré en el orden en que está destinado a ser leído (y evaluado en su mayor parte):

• d=IntegerDigits@#obtenga los dígitos decimales de la entrada y asigne esta lista a d.

• SetPartitions(que requiere Needs@"Combinatorica`";) me da todas las particiones de esto. Sin embargo, devuelve mucho más de lo que realmente quiero, ya que trata la entrada como un conjunto . Esto es lo que lo hace ineficiente, pero lo estoy usando porque la forma más corta que conozco para obtener todas las particiones de la lista es mucho más larga. Como ejemplo, si la lista fuera {1, 2, 3}la función devolvería:

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

  Tenga en cuenta que a) las particiones consecutivas están todas en el orden correcto yb) las particiones se ordenan de la más gruesa a la más fina.

• Select[...,...&] luego filtra esta lista por la función anónima pasada como segundo argumento.
  • Join @@ # == d comprueba que realmente tenemos una partición de lista en lugar de una partición de conjunto general.
  • #~FreeQ~{0, __} comprueba que ninguna partición comience con un cero a la izquierda.
  • 0 <= ## & @@ f /@ #Es un poco más oscuro. Primero asignamos FromDigitsa cada lista en la partición para recuperar los números representados por los dígitos. Luego aplicamos 0 <= ##a esos números, donde se ##refiere a todos los números. Si la partición es {1, 23, 45}entonces esto se expande a 0 <= 1 <= 23 <= 45, por lo que verifica que la matriz esté ordenada.
• Last@luego me da la última partición que queda después del filtrado; esto funciona porque SetPartitionsya ordenó las particiones, de modo que las más finas están al final.
• Finalmente, f/@recupera los números de las listas de dígitos.

Python 3, 134 bytes

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>""]

Es un poco desordenado, pero bueno. El programa solo genera todas las particiones válidas de forma recursiva. La parte interesante es que para no permitir los ceros iniciales, todo lo que se necesitaba era una or "1">s[i:]>""condición adicional .

Toma entrada como f("12345678901234567890")y devuelve una lista de entradas.

Pyth 62 62 61 60 60

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

Explicación

El algoritmo funciona generando todos los números binarios entre 0(inclusivo) y 2^(n-1)(exclusivo), donde nes la longitud de la entrada.

Los dígitos binarios de cada uno se asignan a un separador ( N) para 1 y nada para 0.

Estos caracteres luego se insertan entre cada carácter de entrada, y el resultado se divide por N , dando una lista.

Los valores en las listas se analizan en enteros y las listas se ordenan por longitud. Entonces todo lo que queda es filtrar los que no están ordenados y los que se han dividido en ceros a la izquierda, después de lo cual se selecciona la lista más larga.

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

(SIN COMPETENCIA) Pyth, 25 bytes

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

Pruébalo en línea!

Cómo funciona:

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 bytes

Muy largo, pero al menos ocupa O (n * (2n)!) Memoria y O (n * log (n) * (2n)!) Tiempo donde n es la longitud de la entrada. (Por lo tanto, no intente ejecutarlo con más de 5 dígitos).

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

La función toma la entrada como una cadena.

Ejemplos:

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

Método:

• Agregue el mismo número de espacios a la entrada que su longitud.
• Permutalo de todas las formas posibles.
• Compruebe si la cadena sin espacio es la misma que la entrada (es decir, es una partición de ella).
• Reemplace '0's a' _1's para invalidar las soluciones iniciales cero.
• Evalúa cada cadena.
• Encuentra la lista más larga que también está ordenada. Este es el valor de retorno.

Haskell, 161 bytes

(#)=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]

Prueba de funcionamiento:

*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]

Cómo funciona: la función auxiliar fdivide la lista de entrada en cada lista posible de sublistas. gprimero descarta aquellos con una sublista que comienza con 0y luego aquellos sin el orden adecuado. Empareje cada lista restante con su longitud, tome el máximo y descarte la parte de longitud nuevamente.