Gol
Escriba una función o programa, ordene una matriz de enteros en orden descendente por el número de 1 presente en su representación binaria. No es necesaria una condición de clasificación secundaria.
Ejemplo de lista ordenada
(usando enteros de 16 bits)
Dec Bin 1's
16375 0011111111110111 13
15342 0011101111101110 11
32425 0111111010101001 10
11746 0010110111100010 8
28436 0000110111110100 8
19944 0100110111101000 8
28943 0000011100011111 8
3944 0000011111101000 7
15752 0011110110001000 7
825 0000000011111001 6
21826 0101010101000010 6
Entrada
Una matriz de enteros de 32 bits.
Salida
Una matriz de los mismos enteros ordenados como se describe.
Tanteo
Este es el código de golf para el menor número de bytes que se seleccionará en una semana.
Respuestas:
J (11)
Esta es una función que toma una lista:
Si quieres darle un nombre, cuesta un personaje adicional:
Explicación:
\:
: ordenar hacia abajo+/
: la suma de"1
: cada fila de#:
: representación binariafuente
\:1#.#:
que ahorra unos pocos bytes.JavaScript, 39
Actualización: ahora más corto que Ruby.
40
Explicación:
q es una función recursiva. Si x o y son 0, devuelve
x-y
(un número negativo si x es cero o un número positivo si y es cero). De lo contrario, elimina el bit más bajo (x&x-1
) de x e y y se repite.Versión anterior (42)
fuente
~y
funcionar en lugar de-!y
?!x|-!y
vuelve distinta de cero.~
realmente no encaja ya que no es cero para muchas entradas (incluido cero)Rubí 41
Prueba:
fuente
Python 3 (44):
fuente
Lisp común, 35
logcount
devuelve el número de bits 'en' en un número. Para una listal
, tenemos:Como una función independiente, y en lo que basaré la cuenta de bytes:
fuente
Python 3,
90777267 caracteres.Nuestra solución toma una entrada de la línea de comando e imprime el número en orden descendente (67 caracteres) o ascendente (66).
Orden descendiente
Gracias a @daniero , por la sugerencia de usar un menos en el recuento de 1 para revertirlo, en lugar de usar un corte para revertir la matriz al final. Esto efectivamente ahorró 5 caracteres.
Solo por el hecho de publicarlo, la versión de orden ascendente (que fue la primera que hicimos) tomaría un personaje menos.
Orden ascendente :
Gracias a @Bakuriu por la clave = lambda x ... sugerencia. ;RE
fuente
0
siempre será una parte de su producción; Eso no es correctoraw_input()
y soltar algunos caracteres?[]
interiorsorted
. Además, la salida de este programa es el número de 1s en los números de entrada ordenados, pero debe generar el número que recibió en la entrada, ordenados usando el número de1
s. Algo así como:print(sorted(input().split(), key=lambda x:bin(int(x)).count('1')))
sería correcto.JavaScript [76 bytes]
donde
a
es una matriz de entrada de números.Prueba:
fuente
..
funciona? Tengo entendido que six = 5
luego seeval(x + r)
convierte en loeval(5..toString(2).match(/1/g).length)
que, supongo, no es válido. Gracias.'string'.length
o[1,2,3].pop()
. En el caso de los números, puede hacer lo mismo, pero debe tener en cuenta que después de un solo punto, el analizador buscará una parte fraccionaria del número que espera un valor flotante (como en123.45
). Si utiliza un número entero que debe "decir" al analizador que una parte fraccionaria está vacía, el establecimiento de un punto extra antes de abordar una propiedad:123..method()
.match(/1/g).length
conreplace(/0/g,"")
.a.sort(function(x,y){r='..toString(2).match(/1/g).length';return eval(y+r+-x+r)})
Mathematica 30
Uso:
fuente
k [15 caracteres]
Ejemplo 1
Ejemplo 2 (todos los números son 2 ^ n -1)
fuente
Mathematica 39
IntegerDigits[#,2]
convierte un número base 10 en una lista de 1 y 0.Tr
suma los dígitos.Caso de prueba
fuente
Java 8 -
87/11381/11160/8060/74/48 caracteresEste no es un programa completo de Java, es solo una función (un método, para ser exactos).
Asume eso
java.util.List
yjava.lang.Long.bitCount
se importan, y tiene 60 caracteres:Si no se permiten elementos preimportados, aquí tiene 74 caracteres:
Agregue más 7 caracteres si fuera necesario
static
.[4 años después] O si lo prefiere, podría ser un lambda (gracias @KevinCruijssen por la sugerencia), con 48 bytes:
fuente
Integer.bitCount(x)<Integer.bitCount(y)?-1:1;
? ¿Necesitas el-1,0,1
comportamiento?<Integer>
espacio?Long
, que ahorra algo de espacio :)a.sort((x,y)->Long.bitCount(x)-Long.bitCount(y));
Python 2.x - 65 caracteres (bytes)
En realidad, son 66 caracteres, 65 si lo hacemos una función (entonces necesita algo para llamarlo que es más difícil de presentar).
Demostración en Bash / CMD:
fuente
sum(int(d)for d in bin(x)[2:])
asum(map(int,bin(x)[2:]))
print sorted(input(),key=lambda x:-bin(x).count('1'))
Matlab, 34
Entrada en 'a'
Funciona para números no negativos.
fuente
C - 85 bytes (
108106 bytes)Versión portátil en GCC / Clang / donde
__builtin_popcount
esté disponible (106 bytes):Versión ultra condensada, no portátil, apenas funcional MSVC (85 bytes):
Primera línea nueva incluida en el recuento de bytes debido a que
#define
, los otros no son necesarios.La función para llamar está de
s(array, length)
acuerdo con las especificaciones.Puede codificar
sizeof
en la versión portátil para guardar otros 7 caracteres, como hicieron algunas otras respuestas de C. No estoy seguro de cuál vale más en términos de relación longitud-usabilidad, usted decide.fuente
sizeof l
Guarda un byte. Lo horriblemente feo#define p-__builtin_popcount(
puede ayudar a salvar a otro.PowerShell v3,
615853El ScriptBlock para el
Sort-Object
cmdlet devuelve una matriz de 1 para cada 1 en la representación binaria del número.Sort-Object
ordena la lista en función de la longitud de la matriz devuelta para cada número.Ejecutar:
fuente
$f={
es redundante,while
->for
,-band1
->%2
,-des
->-d
y otros trucos de golf. Está vacío. ¿Puedes explicar cómo trabajar$args|sort{@(1,1,...,1)}
? ¡Es trabajo! ¿Cómo se compara el ordenamiento de matrices sin explícito.Count
? ¿Dónde leer al respecto? ¡Gracias!help Sort-Object -Parameter property
No sé dónde se define la propiedad de clasificación predeterminada para los tipos, pero para las matrices es Count o Length.$args|sort{while($_){if($_-band1){$_};$_=$_-shr1}}-des
da un resultado incorrecto. Por lo tanto, no lo esCount
. Es muy interesante. Gracias de nuevo.ECMAScript 6, 61
Asume
z
es la entradaDatos de prueba
Gracias, cepillo de dientes para la solución más corta.
fuente
z.sort((a,b)=>{c=d=e=0;while(++c<32)d+=a>>c&1,e+=b>>c&1},e-d)
(y gracias por el voto positivo).R ,
1329694888475735351 bytes-20 gracias a la implementación de J.Doe -2 más gracias a Giuseppe
Mi post original:
Pruébalo en línea!
Probé varios métodos diferentes antes de llegar a este resultado.
Método de matriz: Creé una matriz de dos columnas, una columna con el vector de entrada, una de la suma de la representación binaria, luego ordené la suma de binario.
No matricial: me di cuenta de que podía descartar la función matricial y en su lugar crear un vector de valores binarios, sumarlos, ordenarlos y luego usar los valores ordenados para reordenar el vector de entrada.
Cambios menores
Más cambios menores Convertir todo en una línea de código en lugar de dos separadas por un punto y coma.
Método de suma En lugar de agregar las columnas con
colSums
la matriz binaria creada porsapply
, agregué los elementos en la columna antes desapply
"terminar".Disminuir a Rev Realmente quería acortar la disminución, pero R me grita si trato de acortar
decreasing
laorder
función, que era necesaria para obtener el orden deseado comoorder
valores predeterminados para aumentar, luego recordé larev
función de invertir un vector. EUREKA !!! El último cambio en la solución final fuefunction
apryr::f
salvar más de 2 bytesfuente
Haskell, 123C
Esta es la primera forma en que pensé en resolver esto, pero apuesto a que hay una mejor manera de hacerlo. Además, si alguien conoce una forma de jugar al golf con las importaciones de Haskell, me interesaría mucho escucharla.
Ejemplo
Versión sin golf (con explicaciones)
fuente
mod
,n`mod`2
? Tiene la misma precedencia que la multiplicación y la división.CoffeeScript (94)
Código legible (212):
Optimizado (213):
Ofuscando (147):
Los operadores ternarios son excesivamente largos (129):
Demasiado tiempo aún, deja de lanzar (121):
Final (94):
fuente
Smalltalk (Smalltalk / X), 36 (o tal vez 24)
entrada en a; clasifica destructivamente en un:
versión funcional: devuelve una nueva matriz ordenada:
Incluso hay una variante más corta (pasando el nombre o la función como argumento) en 24 caracteres. Pero (suspiro) se ordenará más alto al final. Como entendí, esto no fue solicitado, así que no lo tomo como puntaje de golf:
fuente
PHP 5.4+ 131
Ni siquiera sé por qué me molesto con PHP, en este caso:
Uso:
fuente
Scala, 58
fuente
DFSORT (producto de clasificación de mainframe de IBM) 288 (cada línea de origen tiene 72 caracteres, debe tener espacio en la posición uno)
Solo por diversión y sin matemáticas.
Toma un archivo (podría ejecutarse desde un programa que utilizó una "matriz") con los enteros. Antes de ordenar, traduce los enteros a bits (en un campo de 16 caracteres). Luego cambia los ceros en los bits a nada. ORDENAR Desciende según el resultado de los bits modificados. Crea el archivo ordenado solo con los enteros.
fuente
do
fuente
C #,
8889Editar: el orden descendente agrega un carácter.
fuente
Javascript 84
Inspirado en otras respuestas de JavaScript, pero sin eval y regex.
fuente
Javascript (82)
fuente
Postdata, 126
Debido a que la lista de valores por la que clasificamos se conoce de antemano y es muy limitada (32), esta tarea se puede hacer fácilmente incluso si no hay una función incorporada para ordenar, eligiendo valores coincidentes para 1..32. (¿Es O (32n)? Probablemente).
El procedimiento espera una matriz en la pila y devuelve una matriz 'ordenada'.
O, despojado ritualmente de espacios en blanco y legibilidad:
Luego, si se guarda en
bits.ps
él, puede usarse así:Creo que efectivamente es lo mismo que este Perl (todavía no hay Perl aquí también):
Aunque eso , a diferencia de PostScript, se puede jugar fácilmente:
fuente
C -
124111Implementado como método y utilizando la biblioteca estándar para la clasificación. Un puntero a la matriz y el tamaño deben pasarse como parámetros. Esto solo funcionará en sistemas con punteros de 32 bits. En los sistemas de 64 bits, algunos caracteres deben gastarse especificando definiciones de puntero.
Sangría para legibilidad
Llamada de muestra:
fuente
Java 8: 144
En forma expandida:
Como puede ver, esto funciona convirtiendo
args
a aStream<String>
, luego convirtiendo a aStream<Integer>
con laInteger::decode
referencia de función (más corta queparseInt
ovalueOf
), y luego ordenando porInteger::bitCount
, luego colocándolo en una matriz e imprimiéndolo.Las transmisiones hacen que todo sea más fácil.
fuente