Desafio
Dada uma matriz não vazia de números inteiros, por exemplo:
[5, 2, 7, 6, 4, 1, 3]
Primeiro, divida-o em matrizes onde nenhum item é maior que o anterior (ou seja, matrizes não ascendentes):
[5, 2] [7, 6, 4, 1] [3]
Em seguida, inverta cada matriz:
[2, 5] [1, 4, 6, 7] [3]
Por fim, concatene-os todos juntos:
[2, 5, 1, 4, 6, 7, 3]
Isso deve ser o que o programa sai / função retorna. Repita esse procedimento várias vezes e a matriz será totalmente classificada.
Regras
- A entrada e a saída podem ser fornecidas por qualquer método padrão e podem estar em qualquer formato razoável de matriz.
- A matriz de entrada nunca estará vazia, mas pode conter negativos e / ou duplicatas.
- O valor absoluto de cada número inteiro sempre será menor que 2 31 .
Casos de teste
Esperemos que estes abranjam todos os casos extremos:
[1] -> [1]
[1, 1] -> [1, 1]
[1, 2] -> [1, 2]
[2, 1] -> [1, 2]
[2, 3, 1] -> [2, 1, 3]
[2, 1, 3] -> [1, 2, 3]
[2, 1, 2] -> [1, 2, 2]
[2, 1, 1] -> [1, 1, 2]
[3, 1, 1, 2] -> [1, 1, 3, 2]
[3, 2, 1, 2] -> [1, 2, 3, 2]
[3, 1, 2, 2] -> [1, 3, 2, 2]
[1, 3, 2, 2] -> [1, 2, 2, 3]
[1, 0, 5, -234] -> [0, 1, -234, 5]
[1, 0, 1, 0, 1] -> [0, 1, 0, 1, 1]
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
[5, 4, 3, 2, 1] -> [1, 2, 3, 4, 5]
[2, 1, 5, 4, 3] -> [1, 2, 3, 4, 5]
[2, 3, 1, 5, 4] -> [2, 1, 3, 4, 5]
[5, 1, 4, 2, 3] -> [1, 5, 2, 4, 3]
[5, 2, 7, 6, 4, 1, 3] -> [2, 5, 1, 4, 6, 7, 3]
[-5, -2, -7, -6, -4, -1, -3] -> [-5, -7, -2, -6, -4, -3, -1]
[14, 5, 3, 8, 15, 7, 4, 19, 12, 0, 2, 18, 6, 11, 13, 1, 17, 16, 10, 9] -> [3, 5, 14, 8, 4, 7, 15, 0, 12, 19, 2, 6, 18, 11, 1, 13, 9, 10, 16, 17]
Pontuação
Isso é código-golfe , então o código mais curto em bytes vence.
code-golf
array-manipulation
sorting
ETHproductions
fonte
fonte
O(n^2)
O(n)
. troque o primeiro e o último elementos, depois troque o segundo e o segundo últimos elementos, etc., quando você chegar à parada do meio.O(n)
, mas a reversão pode ser incorporada diretamente no algoritmo (é o que minha resposta JS faz); como cada iteração faz um loop sobre cada item da matriz uma vez, uma única iteração éO(n)
. (Eu acho que ...) #Respostas:
JavaScript (ES6), 64 bytes
Recursão FTW! O algoritmo básico em uso aqui é acompanhar a execução atual não ascendente em uma matriz, "retornando" sempre que um elemento ascendente for encontrado. Fazemos isso recursivamente, concatenando continuamente os resultados, até ficar sem itens. Ao criar cada execução em sentido inverso (em
[n,...z]
vez de[...z,n]
), podemos evitar a longa.reverse()
sem nenhum custo.Snippet de teste
Mostrar snippet de código
fonte
[n,...a]
. O que én
? Esse é apenas o primeiro item da sua matriz?n
é o primeiro item da matriz ea
é o restante da matriz. Você pode encontrar mais informações aqui ....a
? É só assim que você pode tirar proveiton
? Mais uma coisa, quando você chamaf(a,q)
, éq
definido como o parâmetroz
?f=([n])=>...
capturaria apenas o primeiro elemento ef=([n,a])=>...
capturaria apenas o primeiron
e o segundoa
. Outra maneira de fazer of=([n,...a])=>,,,
que seriaf=a=>(n=a.unshift(),...
.z
é o segundo parâmetro na função, quandof(a,q)
é chamado, of
vê comoz
. Espero que isto ajude!Python 3 , 63 bytes
Experimente online!
fonte
Gelatina , 8 bytes
Experimente online!
Explicação:
fonte
JavaScript (ES6), 70 bytes
Claro, isso já é derrotado pela resposta da ETHproductions , mas é o melhor que eu poderia chegar até agora sem usar recursão.
Nota: A inicialização de ambos
r
eo
exatamente do mesmo objeto comr = o = []
pode parecer uma ideia perigosa. Mas é seguro fazer isso aqui porquer
é imediatamente atribuída sua própria instância (contendo o primeiro elemento dea
) na primeira iteração comr = [n, ...r]
.Casos de teste
Mostrar snippet de código
fonte
MATL , 15 bytes
Entrada é um vetor de coluna, com o formato
[5; 2; 7; 6; 4; 1; 3]
(ponto e vírgula é o separador de linhas).Experimente online!
Tome a entrada
[5; 2; 7; 6; 4; 1; 3]
como um exemplo.Explicação
fonte
Mathematica,
3027 bytes3 bytes salvos devido ao @Martin Ender .
Função anônima. Pega uma lista de números como entrada e retorna uma lista de números como saída.
fonte
Python 2, 100 bytes
Um golfe realmente péssimo, mas eu queria postar minha solução (não se supera simplesmente Dennis) ...
Teste em repl.it!
A entrada deve ser fornecida como uma lista literal de Python, como
[5, 3, 4, 2, 6, 1]
.A idéia básica é fazer uso pesado da sintaxe de fatia do Python, cortando cada seção necessária da matriz, revertendo-a e adicionando-a à nova matriz.
fonte
d,L,x=input(),[],0;d+=...
.Pyke,
118 bytes ( versão antiga )Experimente aqui! (funciona na versão mais recente)
fonte
Retina , 163 bytes
Sim, eu sei como isso é horrível. Apoiar zeros e negativos foi super divertido. A contagem de bytes assume a codificação ISO 8859-1.
Experimente online
Explicação:
fonte
05AB1E ,
19181614 bytesEconomizou 2 bytes usando o truque de classificação de Luis Mendo
Experimente online!
Explicação
Exemplo de entrada
[5, 2, 7, 6, 4, 1, 3]
Solução anterior de 16 bytes
fonte
JavaScript (ECMA 6),
121128125119108 bytesA expressão lambda usa um único
Array
parâmetroa
,.Obrigado a @ETHproductions por me ajudar a ver meu primeiro erro.
fonte
return(b+","+c).split`,`
para salvar alguns bytes no final.c.unshift
vez dec.push
remover a necessidade de reverterc
. Depois disso, obtive 94 bytes .Ruby,
6055 bytesPraticamente o que o desafio pediu. Eu defini um lambda
s
, que pega um arrayx
e o divide (fatias) em pedaços menores, onde o seguinte elemento seria maior que. Isso retorna um enumerador, que podemos chamar de mapear e reverter a ordem das peças, antes de finalmente juntar tudo com achatar, que concatena os elementos da ordem definida em uma matriz.Testes
fonte
Braquilog , 10 bytes
Experimente online!
Explicação
fonte
c
, quando executados ao contrário, necessariamente tentam se dividir em menos listas primeiro?Dyalog APL ,
715 bytesRequer
⎕ML←3
, que é padrão em muitos sistemas. *∊
alistar-se (achatar)⌽¨
cada um invertido⍵⊂⍨
o argumento particionado * cortando onde cada elemento correspondente é maior que seu antecessor em1+
um mais⍵-
o argumento menos⌊/⍵
o menor elemento do argumentoA solução antiga de 7 bytes falha com números inteiros não positivos:
Requer
⎕ML←3
, que é padrão em muitos sistemas. *∊
alistar (achatar) o⌽¨
cada um invertido⊂⍨
particionado automaticamente ** Partition (
⊂
) é uma função que corta seu argumento da direita onde o argumento da esquerda correspondente é maior que o anterior. (Infelizmente, ele aceita apenas números inteiros não negativos e zero tem um significado especial.) Na versão 16, essa funcionalidade de⊂
está disponível em todos os sistemas (mesmo naqueles em que⎕ML≠3
), usando o glifo⊆
.fonte
Haskell, 49 bytes
Exemplo de uso:
(%[]) [5,2,7,6,4,1,3]
->[2,5,1,4,6,7,3]
.Abordagem recursiva. A função
%
leva a lista de entrada como seu primeiro parâmetro e um acumuladorl
que monitora até agora o pedaço não ascendente (em ordem inversa). O caso base é alcançado quando a lista de entrada está vazia e o resultado é o acumulador. Se a lista de entrada não estiver vazia e o primeiro elementoa
não se encaixar no chunk atual (any(<a)l
), retorne o acumulador e acrescente uma chamada recursiva no restante da lista ea
como o novo acumulador (l++b%[a]
). Caso contrário, faça uma chamada recursiva no restante da lista ea
anexado ao acumulador (b%(a:l)
). A função principal(%[])
chama%
com um acumulador vazio.fonte
Retina , 98 bytes
A contagem de bytes assume a codificação ISO 8859-1.
Experimente online!
fonte
R, 64 bytes
Lê a entrada de stdin. Dividimos a entrada em uma lista de vetores usando a
split()
qual requer uma variável de fator que agrupa a entrada. O fator é criado pela soma cumulativa do vetor lógico para o qual a diferença é positiva.Considere o vetor:
Agora, pegar a diferença e preceder
F
executandoy=c(F,diff(x)>0)
geraria o seguinte vetor lógico:Tomando a soma cumulativa
cumsum(y)
produz um vetor em que cada grupo é representado por um fator único sobre o qual podemos combinar com asplit
função:fonte
diffinv
vez decumsum
.Oitava,
7544 bytesBaseado na resposta MATL de @LuisMendo
Experimente Online!
Resposta anterior
Experimente Online!
inverter a matriz
tome a primeira diferença de
f
encontre a posição de onde o próximo elemento é menor que o elemento anterior
primeira diferença das posições retorna o comprimento de cada sub-matriz
use o comprimento de cada sub-matriz
mat2cell
para dividir a matriz em uma lista aninhada de matrizesreverter a lista aninhada
achatar a lista aninhada
fonte
Pitão - 15 bytes
Experimente online aqui .
fonte
Perl 6 , 59 bytes
Solução baseada em Regex.
Porque este é
SpartaPerl !!m/ /
: Stringify a matriz de entrada e corresponda a uma regex contra ela.(\-? \d+)
: Combine um número e capture-o como$0
.<?{ [>=] $0 }>
: Asserção de largura zero que corresponde apenas se todas as$0
capturadas até agora na sub-correspondência atual estiverem em ordem não crescente.([ ] +)+
: Repita as duas últimas etapas o mais rápido possível; caso contrário, inicie uma nova sub-correspondência.map , [0]
: Itera sobre as sub-correspondências.|+«*.[0].reverse
: Para cada um, pegue a lista de valores correspondidos por$0
, inverta-os, force os valores a números (+«
) e coloque-os na lista externa (|
).Perl 6 , 63 bytes
Solução de processamento de lista recursiva.
Mais trabalhoso do que eu esperava.
Mesmo que o idioma tenha muitos recursos convenientes, parece não haver nenhum para particionamento de lista (por exemplo, como Ruby
slice_when
ou HaskelltakeWhile
).fonte
Empilhados , não concorrentes, 34 bytes
Ainda constantemente desenvolvendo essa linguagem.
O argumento está no TOS. Experimente aqui!
chunkby
pega uma função e coleta matrizes de dados contíguos que satisfazem a função. A função então é:Isso fornece uma matriz estritamente decrescente.
$revmap
é basicamente[rev]map
e reverte cada item.flat
finalmente nivela a matriz.Alguma diversão para realmente classificar a matriz:
Isso gera (por exemplo):
fonte
Python,
151139 bytesGuardado 12 bytes graças a @ Flp.Tkc!
Em nenhum lugar perto de @ Flp.Tkc, muito menos ...
fonte
+= data,
a vírgula à direita cria implicitamente uma tupla, que é concatenada com a lista, adicionando os dados como o último elemento da lista. Nesse contexto, façar+=l[i:j+1][::-1],
Python 2, 74 bytes
Entrada
a
, saída emc
fonte
Python 3, 191 bytes
Não tenho certeza se o uso da
sorted
função para verificação é permitido aqui, mas não consegui pensar em uma boa razão para isso, e isso reduziu minha contagem de bytes em ~ 30 bytes.fonte
Clojure, 105 bytes
Partições em pares em números consecutivos, coloca
true
oufalse
entre elas, as partiçõesnot
paratrue
e números se tornamfalse
efalse
true
, inverte as partições e mantém os valores numéricos.fonte