Paredes binarias debilitadas

HyperNeutrino 08/18/2017. 14 answers, 1.278 views
code-golf number binary binary-matrix

Inspirado por Crear un muro binario

Dada una lista de enteros positivos, podemos escribirlos todos juntos uno encima del otro como así, para [2, 6, 9, 4] como ejemplo:

0010
0110
1001
0100 

Podemos imaginar esto como una pared:

..#.
.##.
#..#
.#.. 

Sin embargo, esta es una pared muy débil, ¡y se ha colapsado! Cada 1 ( # ) cae hasta que golpea el "suelo" u otro 1 ( # ). Los 0 s ( . S) están presentes en los lugares que dejó el movimiento de 1 s.

Esto se convierte en lo siguiente:

....
....
.##.
#### 

Lo cual se traduce a:

0000
0000
0110
1111 

Que, como una lista de números, es [0, 0, 6, 15] .

Otro caso de prueba

[10, 17, 19, 23] 

Esto se convierte en:

01010
10001
10011
10111 

que se convierte en:

00000
10011
10011
11111 

traducción de nuevo a:

[0, 19, 19, 31] 

Reto

Dada una lista de enteros positivos, aplique esta transformación a la lista. Entrada / Salida como listas de enteros positivos en cualquier formato razonable. Lagunas estándar se aplican.

Este es un , ¡así que la respuesta más corta en bytes gana!

5 Comments
1 Leaky Nun 07/29/2017
¿Más testcases? Ya sabes, los testcase no cuadrados serían buenos.
HyperNeutrino 07/29/2017
@LeakyNun Sure. Yo haré eso.
Marcus Müller 07/30/2017
Eso es solo un problema de clasificación para arreglos de bits.
HyperNeutrino 07/30/2017
@ MarcusMüller Tienes razón, me di cuenta de que después de la respuesta de MATL: P

14 Answers


Suever 07/29/2017.

MATL , 4 bytes

BSXB 

Pruébalo en MATL Online

Explanation

% Implicitly grab input as an array 
    %   STACK: [10, 17, 19, 23]
B   % Convert each element to binary where each decimal number results in a row
    %   STACK: [0 1 0 1 0;
    %           1 0 0 0 1;
    %           1 0 0 1 1;
    %           1 0 1 1 1]
S   % Sort each column, placing all of the 1's at the bottom of each column
    %   STACK: [0 0 0 0 0;
    %           1 0 0 1 1;
    %           1 0 0 1 1;
    %           1 1 1 1 1] 
XB  % Convert each row from its binary representation to its decimal number
    %   STACK: [0, 19, 19, 31]
    % Implicitly display the result 
5 comments
HyperNeutrino 07/29/2017
o_O ¿Cómo funciona esto ?: o
1 totallyhuman 07/29/2017
¿MATL acaba de superar a Jelly en 4 bytes ? o_O
Leaky Nun 07/29/2017
5 bytes ahora :-p
HyperNeutrino 07/29/2017
Nunca pensé que habría un built-in para mover los que están en la parte inferior xD +1
1 JungHwan Min 07/29/2017
@totallyhuman, espera a que Dennis llegue

Anders Kaseorg 07/29/2017.

Python , 68 bytes

 f=lambda a:a and[x|y&a[0]for x,y in zip([0]+f(a[1:]),f(a[1:])+[-1])] 

¡Pruébalo en línea!


Neil 07/29/2017.

JavaScript (ES6), 50 bytes

f=a=>a.map(_=>a.map((e,i)=>a[a[i]|=a[--i],i]&=e))&&a 

Explicación: Supongamos que dos filas de la pared son así:

0011
0101 

El resultado debe ser esto:

0001
0111 

En otras palabras, la primera fila se convierte en el AND de las dos filas y la segunda fila se convierte en el OR de las dos filas. Esto solo necesita repetirse suficientes veces para que todos los bits caigan al fondo.


Leaky Nun 07/29/2017.

Jelly , 9 bytes

BUz0Ṣ€ZUḄ 

¡Pruébalo en línea!


Justin Mariner 07/29/2017.

Japt , 16 bytes

m¤z3 ®¬n qÃz mn2 

¡Pruébalo en línea! usando el indicador -Q para formatear el resultado de la matriz.

Explicación

m¤z3 ®¬n qÃz mn2    Implicit: U = input array.
                        [10, 17, 19, 23]
m¤z3                Map U to binary strings and rotate the array left 90°
                         1010       0111
                        10001   ->  1011
                        10011       0001
                        10111       1000
                                     111
®¬n qà              Sort each binary string, putting 0s and spaces at the start
                        0111
                        0111
                        0001
                        0001
                         111
z mn2               Rotate right 90° and convert each back to a number
                         0000       0
                        10011   ->  19
                        10011       19
                        11111       31
                    Implicit output of resulting array 
2 comments
ETHproductions 07/30/2017
think que puedes guardar un byte con mì2 z3 mn z mì2
Justin Mariner 07/30/2017
@ETHproductions Parece que girar la matriz 2D, en lugar de rotar la matriz de cadenas, rellena cada matriz interna con null lugar de espacios. Entonces eso no parece funcionar. Y null está ordenado a la derecha de 1 s, a diferencia de los espacios, que están ordenados a la izquierda.

DanTheMan 07/30/2017.

Mathematica, 64 bytes

#~FromDigits~2&/@(Sort/@(PadLeft[#~IntegerDigits~2&/@#]))& 

 es \[Transpose]

Esto convierte la entrada (una lista de números) en una lista de dígitos, la almohadilla para que sea una matriz cuadrada, la transpone, ordena las filas para que el 1 "caiga" al fondo, transponga hacia atrás, luego se convierta nuevamente en números .


xnor 07/30/2017.

Python 3.5 , 60 bytes

 def f(a,*t):
 if t:b,*r=f(*t);t=f(a|b,*r);a&=b
 return(a,*t) 

¡Pruébalo en línea!

Toma entrada como f(2, 6, 9, 4) . Asume que la entrada no está vacía. Utiliza un montón de desempaquetado de tuplas .


Suever 07/30/2017.

Octave, 29 25 bytes

4 bytes saved thanks to @Stewie

@(x)bi2de(sort(de2bi(x))) 
2 comments
Stewie Griffin 07/30/2017
de2bi/bi2de guarda 4 bytes en octava. Funciona en octave-online.net.
Suever 07/30/2017
@StewieGriffin ¡Gracias!

miles 07/29/2017.

J , 13 bytes

/:~"1&.|:&.#: 

¡Pruébalo en línea!

Explicación

/:~"1&.|:&.#:  Input: array M
           #:  Convert each in M to binary with left-padding
       |:&     Transpose
/:~"1&         Sort each row
     &.|:      Inverse of transpose (which is just transpose)
         &.#:  Inverse of converting to binary 
2 comments
Zacharý 07/30/2017
Hay ese relleno binario izquierdo de nuevo, +1. Y también, ¿puedes explicar por qué necesitarías usar la inversa de la transposición, ya que solo se transpone?
miles 08/01/2017
@ Zacharý Los inversos se utilizan para deshacer las operaciones utilizadas antes de ordenar cada fila. Es cierto que el inverso de la transposición es simplemente transponer, pero otra forma de ver esto es como M , donde las primeras dos funciones son solo las inversos de los dos últimos.

Erik the Outgolfer 07/30/2017.

05AB1E , 9 bytes

bí0ζR€{øC 

¡Pruébalo en línea!

Algún algoritmo diferente de Magic's.

3 comments
Magic Octopus Urn 07/31/2017
ζ , maldita sea Eliminado el mío, toma mi +1.
Erik the Outgolfer 07/31/2017
@MagicOctopusUrn ¿Por qué eliminaste el tuyo? No hay necesidad de.
Magic Octopus Urn 07/31/2017
No es realmente muy diferente (en términos de algoritmo) y esto fue un 25% mejor.

Zacharý 07/30/2017.

Dyalog APL, 24 21 19 bytes

2⊥↑{⍵[⍋⍵]}¨↓2⊥⍣¯1⊢⎕ 

¡Pruébalo en línea! (modificado para que TryAPL lo acepte como válido)

¿Cómo?

  • entrada evaluada (las matrices están separadas por espacios)
  • 2⊥⍣¯1⊢ convierte cada uno de los argumentos en binarios (transpuesta de lo que está en la pregunta)
  • convierte una matriz 2D en un vector de vectores
  • {⍵[⍋⍵]}¨ clasifica cada uno de los elementos del vector
  • convierte el vector de vectores en una matriz 2D de nuevo
  • 2⊥ conversión de binario (ya que de alguna manera lo transpone, llegamos al resultado correcto)

James Heslip 07/30/2017.

Dyalog APL (23 caracteres)

NO 
  1. Convierte los argumentos de entrada en una matriz binaria
  2. Divida la matriz en columnas
  3. Ordenar las columnas en orden ascendente
  4. Convierte las filas ordenadas de nuevo en decimal

Ejemplo

{2⊥¨↓⍉↑{⍵[⍋⍵]}¨↓2⊥⍣¯1⊢⍵}10 17 19 23
      0 19 19 31 

Gracias a Zacharý por corregirme en este caso.

5 comments
Zacharý 07/30/2017
Puede reemplazar con (⊥⍣¯1)⍵ con ⊥⍣¯1⊢⍵ . Además, no creo que necesite la especificación del eje en split ( ↓[1] => ).
Zacharý 07/30/2017
Ah, y se supone que debes convertirlo de nuevo a una lista!
Zacharý 07/30/2017
Esto no es válido
James Heslip 07/30/2017
Gracias, Zacharý, estuve trabajando en esto anoche y creo que leí mal el problema. Modifiqué mi solución ahora.
1 Zacharý 07/30/2017
Bueno, buen trabajo! ( ⊥⍣¯1 realmente necesita ser un ⊥⍣¯1 - ⊥⍣¯1 ). Y gracias por realmente obtener mi nombre de usuario correcto.

ThePirateBay 07/29/2017.

JavaScript, 127 125 bytes

a=>a[m='map'](_=>b[m]((n,i)=>n&&(b[i]--,d|=1<a[m](e=>d+=!!(2**c&e),d=0)&&d)).reverse() 

Pruébalo en línea

-2 bytes thanks to Cows quack

1 comments
Cows quack 07/29/2017
(1< puede convertirse en 2**c&e

Dopapp 07/30/2017.

Python 2, 142 bytes

... y aún jugando al golf ... con suerte - ¡Cualquier ayuda apreciada!

 def c(l):b=[bin(n)[2:]for n in l];print[int(n,2)for n in map(''.join,zip(*map(sorted,zip(*['0'*(len(max(b,key=len))-len(x))+x for x in b]))))] 

Una gran parte de esto es para rellenar los números con ceros.

Más legible

 def collapse(nums):
    bins = [bin(n)[2:] for n in nums]
    bins = [('0'*(len(max(bins, key = len)) - len(x))) + x for x in bins]
    print [int(n, 2) for n in map(''.join, zip(*map(sorted, zip(*bins))))] 

Esto crea una matriz de representaciones de cadenas binarias, las almohadillas, las rota 90º en el sentido de las agujas del reloj, ordena cada fila, la gira 90º hacia atrás y luego crea enteros de cada fila.

2 comments
Mr. Xcoder 07/30/2017
142 bytes , tiene algunos paréntesis redundantes.
Dopapp 07/30/2017
@ Mr.Xcoder, oh sí, eso fue una tontería

Related questions

Hot questions

Language

Popular Tags