Paredes Binárias Enfraquecidas

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

Inspirado por criar uma parede binária

Dada uma lista de inteiros positivos, podemos escrevê-los todos acima uns dos outros assim, para [2, 6, 9, 4] como exemplo:

0010
0110
1001
0100 

Podemos imaginar isso como uma parede:

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

No entanto, esta é uma parede muito fraca e entrou em colapso! Cada 1 ( # ) cai até atingir o "chão" ou outro 1 ( # ). Os 0 s ( . S) estão presentes em pontos deixados por 1 s movidos.

Isso se torna o seguinte:

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

Que traduz de volta para:

0000
0000
0110
1111 

Que, como uma lista de números, é [0, 0, 6, 15] .

Outro caso de teste

[10, 17, 19, 23] 

Isso se torna:

01010
10001
10011
10111 

que se torna:

00000
10011
10011
11111 

traduzindo de volta para:

[0, 19, 19, 31] 

Desafio

Dada uma lista de inteiros positivos, aplique essa transformação à lista. Entrada / Saída como listas de inteiros positivos em qualquer formato razoável. Brechas padrão se aplicam.

Este é um , então a resposta mais curta em bytes ganha!

5 Comments
1 Leaky Nun 07/29/2017
Mais testes? Sabe, testcases não quadradas seriam boas.
HyperNeutrino 07/29/2017
@LeakyNun Claro. Eu farei isso.
Marcus Müller 07/30/2017
Isso é apenas um problema de classificação para matrizes de bits.
HyperNeutrino 07/30/2017
@ MarcusMüller Você está certo - percebi que após a resposta MATL: P

14 Answers


Suever 07/29/2017.

MATL , 4 bytes

BSXB 

Experimente no 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 Como isso funciona: o
1 totallyhuman 07/29/2017
MATL acabou de sair da Jelly por 4 bytes ? o_O
Leaky Nun 07/29/2017
5 bytes agora :-p
HyperNeutrino 07/29/2017
Eu nunca pensei que haveria um built-in para mover os para o fundo xD +1
1 JungHwan Min 07/29/2017
@totallyhuman bem, espere até Dennis vem

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

Experimente online!


Neil 07/29/2017.

JavaScript (ES6), 50 bytes

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

Explicação: Suponha que duas linhas da parede fossem assim:

0011
0101 

O resultado precisa ser isso:

0001
0111 

Em outras palavras, a primeira linha se torna o AND das duas linhas e a segunda linha se torna a OR das duas linhas. Isso só precisa ser repetido o suficiente para que todos os bits caiam para o fundo.


Leaky Nun 07/29/2017.

Geléia , 9 bytes

BUz0Ṣ€ZUḄ 

Experimente online!


Justin Mariner 07/29/2017.

Japt , 16 bytes

m¤z3 ®¬n qÃz mn2 

Experimente online! usando o sinalizador -Q para formatar o resultado da matriz.

Explicação

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
Eu think você pode salvar um byte com mì2 z3 mn z mì2
Justin Mariner 07/30/2017
@ETHproductions Parece que girar o array 2D, em vez de girar o array de strings, preenche cada array interno com null vez de espaços. Então isso não parece funcionar. E null é classificado à direita dos 1 s, diferentemente dos espaços, que são classificados à esquerda.

DanTheMan 07/30/2017.

Mathematica, 64 bytes

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

 é \[Transpose]

Isso converte a entrada (uma lista de números) em uma lista de listas de dígitos, posiciona-a em uma matriz quadrada, transpõe-a, classifica as linhas para que o 1 "caia" na parte inferior, transponha de volta e converta novamente em 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) 

Experimente online!

Recebe entrada como f(2, 6, 9, 4) . Assume que a entrada é não vazia. Usa muita tupla para desempacotar .


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 economiza 4 bytes em oitava. Funciona em octave-online.net.
Suever 07/30/2017
@StewieGriffin Obrigado!

miles 07/29/2017.

J , 13 bytes

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

Experimente online!

Explicação

/:~"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
Há aquele binário de preenchimento à esquerda novamente, +1. E também, você pode explicar por que você precisaria usar o inverso da transposição, já que é apenas transposição?
miles 08/01/2017
@ Zacharý As inversas são usadas para desfazer as operações usadas antes de classificar cada linha. É verdade que o inverso da transposição é apenas transposição, mas outra maneira de ver isso é como M , onde as duas primeiras funções são apenas inversos dos dois últimos.

Erik the Outgolfer 07/30/2017.

05AB1E , 9 bytes

bí0ζR€{øC 

Experimente online!

Algum algoritmo diferente do de Magic.

3 comments
Magic Octopus Urn 07/31/2017
ζ , droga. Excluído o meu, pegue o meu +1.
Erik the Outgolfer 07/31/2017
@MagicOctopusUrn Por que você deletou o seu? Não precisa de.
Magic Octopus Urn 07/31/2017
Não é muito diferente (em termos de algoritmo) e isso foi 25% melhor.

Zacharý 07/30/2017.

Dyalog APL, 24 21 19 bytes

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

Experimente online! (modificado para que o TryAPL o aceite como válido)

Como?

  • entrada avaliada (matrizes são separadas por espaço)
  • 2⊥⍣¯1⊢ converte cada um dos argumentos em binários (transposto do que está na questão)
  • transforma um array 2D em um vetor de vetores
  • {⍵[⍋⍵]}¨ classifica cada um dos elementos do vetor
  • transforma o vetor de vetores em uma matriz 2D novamente
  • 2⊥ converter de binário (uma vez que meio que o transpõe, chegamos ao resultado correto)

James Heslip 07/30/2017.

Dyalog APL (23 caracteres)

NO 
  1. Converta os argumentos de entrada em uma matriz binária
  2. Divida a matriz em colunas
  3. Classifique as colunas em ordem crescente
  4. Converta as linhas ordenadas de volta em decimal

Exemplo

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

Graças a Zacharý por me corrigir neste.

5 comments
Zacharý 07/30/2017
Você pode substituir por (⊥⍣¯1)⍵ por ⊥⍣¯1⊢⍵ . Além disso, não acho que você precise da especificação do eixo na divisão ( ↓[1] => ).
Zacharý 07/30/2017
Ah, e você deve convertê-lo de volta para uma lista!
Zacharý 07/30/2017
Isso é inválido.
James Heslip 07/30/2017
Obrigado, Zacharý, eu estava trabalhando nisso ontem à noite e acho que interpretei mal o problema. Eu modifiquei minha solução agora.
1 Zacharý 07/30/2017
Bom trabalho! ( ⊥⍣¯1 realmente precisa ser construído). E obrigado por realmente ter meu nome de usuário correto.

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() 

Experimente online

-2 bytes thanks to Cows quack

1 comments
Cows quack 07/29/2017
(1< pode se tornar 2**c&e

Dopapp 07/30/2017.

Python 2, 142 bytes

... e ainda jogando golfe ... esperançosamente - Qualquer ajuda 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]))))] 

Um grande pedaço disso é para preencher os números com zeros.

Mais legível:

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

Isso cria uma matriz das representações de strings binárias, pressiona-as, rotaciona-as 90º no sentido horário, classifica cada linha, rotaciona-a de volta 90º e depois cria inteiros de cada linha.

2 comments
Mr. Xcoder 07/30/2017
142 bytes , você tem alguns parênteses redundantes.
Dopapp 07/30/2017
@ Mr.Xcoder, oh sim, isso foi bobo

Related questions

Hot questions

Language

Popular Tags