Partição lexical classificada de um número

17

O desafio é realmente simples: dado um número, você divide seus dígitos em uma matriz de números menores, de forma que os números resultantes não diminuem. O problema é que você precisa dividi-lo para que o comprimento da matriz seja o máximo.

Confuso?

  • Você recebe um número inteiro positivo via STDIN (ou alternativa mais próxima), argumento de linha de comando ou argumento de função em qualquer formato de entrada conveniente e inequívoco.
  • Você precisa particionar os dígitos decimais do número em grupos contíguos e independentes.
  • A matriz de números representada por esses grupos de dígitos deve ser classificada (na ordem habitual e não decrescente) sem reorganizar os grupos .
  • Nos casos em que existe mais de uma partição, é necessário particionar a entrada no maior número possível. No caso de empate, retorne um desses resultados.
  • Você pode enviar a matriz para STDOUT (ou alternativa mais próxima) ou como um valor de retorno da função. No caso de STDOUT (ou alternativa mais próxima), a matriz deve ser impressa em qualquer formato de lista conveniente e inequívoco.
  • Os números de divisão não devem ter zeros à esquerda. Assim, por exemplo, 1002003não pode ser impresso como um e [1, 002, 003]nem [1, 2, 3]a única resposta válida para isso [100, 2003].

Casos de teste:

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]

Pontuação

Este é o código-golfe, pelo que o código mais curto em bytes vence.

Optimizer
fonte

Respostas:

10

Pyth, 34

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

Experimente online aqui . Observe que isso tem uma complexidade de tempo (e espaço) de O (n). Portanto, o caso de teste 12345678901234567890leva muito tempo no compilador online. Use o offline (1 minuto no meu laptop).

Esta é apenas a minha primeira tentativa. Pode haver algum espaço para melhorias.

Primeiro, algumas idéias de como meu algoritmo funciona.

  • Interpreto a entrada como string e não como um número.
  • Então eu crio todos os subconjuntos possíveis de [0, 1, 2, ..., len(n-1)]
  • Para cada um desses subconjuntos (vamos pegar [1, 4, 5]), divido a string de entrada em parte usando esses números. [input[0:1], input[1, 4], input[4,5], input[5,len(input)]].
  • Depois, tento converter esses números em strings. Pode haver dois problemas. Pyth (ou Python) lança uma exceção para uma sequência vazia e para uma sequência de números que começa com 0. Portanto, eu uso um try - catchbloco (na verdade, loop infinito com uma interrupção imediata). Se a conversão foi bem-sucedida, adiciono o resultado a uma lista Y.
  • Depois de manipular todos os subconjuntos, filtro a lista Yde resultados, que já estão classificados e imprimo o último (o último tem mais grupos).

Agora a explicação detalhada:

                            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)
Jakube
fonte
Você pode usar em aYvez de~Y]
FryAmTheEggman 18/15/15
@FryAmTheEggman eu sempre esqueço a. Não sei porque.
Jakube 18/03/2015
@Jakube Talvez porque não esteja na documentação?
SP3000
Eu tinha uma solução para ~ 45 caracteres. Eu não estava ciente do fato de int("01")ser um erro no Pyth (isso não acontece no Python).
Ou orp
3
@Jakube haha, embora pareça lógico, mas geralmente né o comprimento da entrada.
Optimizer
6

Mathematica, 134 127 bytes

Isso é bastante ineficiente, pois gera muito mais partições do que as válidas. O 324142434445caso de teste é executado em alguns segundos, mas eu não tentaria 12345678901234567890.

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

Isso define uma função sem nome que pega um número inteiro e retorna uma lista de números inteiros.

Explicação

A ordem de leitura deste código está um pouco em todo o lugar, portanto, detalharei a ordem em que ele deve ser lido (e avaliado na maior parte):

  • d=IntegerDigits@#obtenha os dígitos decimais da entrada e atribua esta lista a d.
  • SetPartitions(o que requer Needs@"Combinatorica`";) me fornece todas as partições disso. No entanto, ele retorna muito mais do que eu realmente quero, pois trata a entrada como um conjunto . É isso que o torna ineficiente, mas estou usando isso porque a maneira mais curta que eu conheço para obter todas as partições de lista é muito mais longa. Como exemplo, se a lista fosse {1, 2, 3}a função retornaria:

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

    Observe que a) as partições consecutivas estão na ordem correta eb) as partições são classificadas da mais grossa para a mais fina.

  • Select[...,...&] depois filtra essa lista pela função anônima transmitida como o segundo argumento.
    • Join @@ # == d verifica se realmente temos uma partição de lista em vez de uma partição geral definida.
    • #~FreeQ~{0, __} verifica se nenhuma partição começa com um zero inicial.
    • 0 <= ## & @@ f /@ #é um pouco mais obscuro. Primeiro, mapeamos FromDigitspara cada lista na partição para recuperar os números representados pelos dígitos. Então aplicamos 0 <= ##a esses números, onde ##se refere a todos os números. Se a partição for {1, 23, 45}expandida para 0 <= 1 <= 23 <= 45, verificará se a matriz está classificada.
  • Last@depois me fornece a última partição que resta após a filtragem - isso funciona porque SetPartitionsjá classificamos as partições, de modo que as melhores estão no final.
  • Finalmente, f/@recupera os números das listas de dígitos.
Martin Ender
fonte
5

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

Está um pouco bagunçado, mas tudo bem. O programa apenas gera todas as partições válidas recursivamente. A parte interessante é que, para não permitir zeros à esquerda, tudo o que era necessário era uma or "1">s[i:]>""condição adicional .

Toma entrada como f("12345678901234567890") e retorna uma lista de entradas.

Sp3000
fonte
4

Pyth, 62 61 60

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

Explicação

O algoritmo funciona gerando todos os números binários entre 0(inclusive) e 2^(n-1)(exclusivo), onden é o comprimento da entrada.

Os dígitos binários de cada um são mapeados para um separador (N ) para 1 e nada para 0.

Esses caracteres são inseridos entre cada caractere de entrada e o resultado é dividido por N , produzindo uma lista.

Os valores nas listas são então analisados ​​para números inteiros e as listas são classificadas por tamanho. Tudo o que resta é filtrar os não classificados e os que foram divididos nos zeros à esquerda, depois dos quais a lista mais longa é selecionada.

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
PurkkaKoodari
fonte
1

Python (NÃO COMPETENTE), 25 bytes

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

Experimente online!

Como 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
Freira Furada
fonte
0

J, 109 bytes

Muito longo, mas pelo menos ocupa memória O (n * (2n)!) E tempo O (n * log (n) * (2n)!) Em que n é o comprimento da entrada. (Portanto, não tente executá-lo com mais de 5 dígitos.)

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

A função aceita a entrada como uma sequência.

Exemplos:

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

Método:

  • Adicione o mesmo número de espaços à entrada que ela tenha comprimento.
  • Permita-o de todas as maneiras possíveis.
  • Verifique se a sequência sem espaço é igual à entrada (ou seja, é uma partição dela).
  • Substitua '0' por '_1' para invalidar as soluções zero principais.
  • Avalie cada sequência.
  • Encontre a lista mais longa que também é classificada. Este é o valor de retorno.
randomra
fonte
0

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]

Execução de teste:

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

Como funciona: a função auxiliar fdivide a lista de entradas em todas as listas possíveis de sublistas. gprimeiro descarta aqueles com uma sub-lista começando com 0e depois sem a ordem correta. Emparelhe todas as listas restantes com o seu comprimento, tome o máximo e descarte a parte do comprimento novamente.

nimi
fonte