Bloquear orden aleatorio
La ordenación aleatoria de bloques es un método (más bien artificial) de ordenar una lista. Funciona de la siguiente manera, ilustrada por un ejemplo.
[6, 1, 0, 3, 2, 4, -2, -1]
Break list into contiguous blocks
[6][1, 0][3, 2, 4][-2, -1]
Sort each block
[6][0, 1][2, 3, 4][-2, -1]
Sort blocks lexicographically
[-2, -1][0, 1][2, 3, 4][6]
Concatenate
[-2, -1, 0, 1, 2, 3, 4, 6]
La partición en bloques contiguos se puede elegir arbitrariamente. Sin embargo, no todas las opciones de bloques producirán una lista ordenada al final:
[6, 1, 0, 3, 2, 4, -2, -1]
[6, 1, 0][3, 2, 4][-2, -1]
[0, 1, 6][2, 3, 4][-2, -1]
[-2, -1][0, 1, 6][2, 3, 4]
[-2, -1, 0, 1, 6, 2, 3, 4]
Si todos los bloques tienen longitud 1, o si solo hay un bloque, entonces el resultado se ordenará, por supuesto. Pero estos son casos bastante extremos. En este desafío, su tarea es encontrar un equilibrio entre el número de bloques y la longitud máxima de un bloque.
La tarea
Su entrada es una lista no vacía de enteros L , tomada en cualquier formato razonable. Su salida será el número entero más pequeño N tal que L puede ser bloque aleatoria ordenadas de modo que el número de bloques y la longitud de cada bloque están en más N .
El conteo de bytes más bajo en cada idioma gana. Aplican reglas estándar de código de golf .
Casos de prueba
[5] -> 1
[1,2] -> 2
[0,2,1,-1] -> 3
[-1,0,2,1] -> 2
[9,3,8,2,7] -> 4
[9,2,8,3,7] -> 3
[5,9,3,7,2,4,8] -> 7
[-1,-2,1,2,-1,-2,7] -> 4
[6,1,0,3,2,4,-2,-1] -> 4
[12,5,6,-6,-1,0,2,3] -> 3
[1,0,1,0,1,0,1,0,1,0] -> 6
[1,2,1,3,1,2,3,2,4,3] -> 5
[7,7,7,7,8,9,7,7,7,7] -> 4
Brachylog , 17 bytes
Pruébalo en línea!
Explicación
Esta es una respuesta propia; Diseñé este desafío con Brachylog en mente y encontré
~c₎{…}ᵈ
una construcción interesante.El incorporado
c
concatena una lista de listas. Si se le da un subíndiceN
, se requiere el número de listasN
. El símbolo₎
modifica un incorporado para tomar un par como entrada y usar su elemento correcto como subíndice. Por lo tanto,c₎
toma un par[L,N]
, requiere que el número de listas enL
esN
y devuelve la concatenación deL
. Cuando se ejecuta en reversa,~c₎
toma una listaL
y devuelve un par[P,N]
, dondeP
hay una particiónL
enN
bloques. Se enumeran en orden creciente deN
.El metapredicado
ᵈ
transforma un predicado ordinario en uno que verifica una relación entre los dos elementos de un par. Más explícitamente,{…}ᵈ
toma un par[A,B]
, comprueba que seA{…}B
mantiene y emiteB
. Lo uso para verificar queP
se puede ordenar por bloques y solo contiene listas de longitud como máximoN
.Tenga en cuenta que
P
puede contener listas vacías. Esto garantiza la corrección también en aquellos casos en que la longitud máxima de un bloque es mayor que el número de bloques.fuente
Python 2 ,
186146bytesPruébalo en línea!
La segunda función es tomada de este consejo por feersum .
fuente
Ruby , 158 bytes
Pruébalo en línea!
fuente
Pyth ,
24 2320 bytesBanco de pruebas.
Cómo funciona
fuente
APL (Dyalog Classic) ,
7167 bytes⎕IO
debe ser0
Pruébalo en línea!
¿Cómo?
⌊/
- Encuentra el mínimo de ...(⌈/≢,≢¨)
- ... el máximo de la longitud y el número de elementos ...¨
- ... de cada elemento de ...T/⍨
- ... los elementos que ...{S[⍋S]≡∊⍵[⍋↑⍵]}¨
- ... se ordenan cuando se aplanan, de ...T←{⍵[⍋⍵]}¨¨
- ... los elementos ordenados de los elementos de ...⊂∘S¨(-≢S)↑¨2⊥⍣¯1¨⍳2*≢S←⍵
- ... las particiones del argumento (junto con algo de basura)fuente