Verzwakte binaire muren

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

Geïnspireerd door Create a binary wall

Gegeven een lijst van positieve gehele getallen, kunnen we ze allemaal boven elkaar opschrijven zoals bijvoorbeeld: [2, 6, 9, 4] als voorbeeld:

0010
0110
1001
0100 

We kunnen ons dit als een muur voorstellen:

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

Dit is echter een erg zwakke muur en is ingestort! Elke 1 ( # ) valt naar beneden totdat deze de "grond" of een andere 1 ( # ) raakt. De 0 s ( . S) zijn aanwezig op plaatsen achtergelaten door verplaatste 1 s.

Dit wordt het volgende:

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

Wat zich vertaalt naar:

0000
0000
0110
1111 

Wat, als een lijst met nummers, [0, 0, 6, 15] .

Nog een testcase

[10, 17, 19, 23] 

Dit wordt:

01010
10001
10011
10111 

wat wordt:

00000
10011
10011
11111 

vertalen terug naar:

[0, 19, 19, 31] 

Uitdaging

Gegeven een lijst met positieve gehele getallen, pas deze transformatie toe op de lijst. Invoer / uitvoer als lijsten met positieve gehele getallen in een redelijk formaat. Standaard mazen zijn van toepassing.

Dit is een , dus het kortste antwoord in bytes wint!

5 Comments
1 Leaky Nun 07/29/2017
Meer testcases? Weet je, niet-vierkante testcases zouden goed zijn.
HyperNeutrino 07/29/2017
@LeakyNun Sure. Ik zal dat doen.
Marcus Müller 07/30/2017
Dat is slechts een sorteerprobleem voor bit-arrays.
HyperNeutrino 07/30/2017
@ MarcusMüller Je hebt gelijk - ik realiseerde me dat na het MATL-antwoord: P

14 Answers


Suever 07/29/2017.

MATL , 4 bytes

BSXB 

Probeer het op 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 Hoe werkt dit: o
1 totallyhuman 07/29/2017
Was MATL net buiten de golf Jelly bij 4 bytes ? o_O
Leaky Nun 07/29/2017
5 bytes nu :-p
HyperNeutrino 07/29/2017
Ik had nooit gedacht dat er een ingebouwde schijf zou zijn om degenen naar de bodem te brengen xD +1
1 JungHwan Min 07/29/2017
@totallyhuman goed, wacht tot Dennis komt

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

Probeer het 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 

Uitleg: Stel dat twee rijen van de muur als volgt waren:

0011
0101 

Het resultaat moet dit zijn:

0001
0111 

Met andere woorden, de eerste rij wordt de AND van de twee rijen en de tweede rij wordt de OF van de twee rijen. Dit hoeft alleen maar genoeg keer herhaald te worden om alle bits naar beneden te laten vallen.


Leaky Nun 07/29/2017.

Jelly , 9 bytes

BUz0Ṣ€ZUḄ 

Probeer het online!


Justin Mariner 07/29/2017.

Japt , 16 bytes

m¤z3 ®¬n qÃz mn2 

Probeer het online! met de vlag -Q om het array-resultaat te formatteren.

Uitleg

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
Ik think je een byte kunt opslaan met mì2 z3 mn z mì2
Justin Mariner 07/30/2017
@ETHproductions Het lijkt erop dat het roteren van de 2D-array, in plaats van het roteren van de array van strings, elke interne array opvult met null plaats van spaties. Dus dat lijkt niet te werken. En null wordt rechts van de 1 s gesorteerd, in tegenstelling tot spaties die naar links zijn gesorteerd.

DanTheMan 07/30/2017.

Mathematica, 64 bytes

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

 is \[Transpose]

Dit converteert de invoer (een lijst met nummers) naar een lijst met cijferlijsten, plaatst deze als een vierkante matrix, transponeert deze, sorteert de rijen zodat de 1's "vallen" naar de bodem, verplaatst zich terug en converteert vervolgens terug naar getallen .


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) 

Probeer het online!

Neemt input zoals f(2, 6, 9, 4) . Gaat ervan uit dat invoer niet leeg is. Gebruikt veel tuple uitpakken .


Suever 07/30/2017.

Octaaf, 29 25 bytes

4 bytes saved thanks to @Stewie

@(x)bi2de(sort(de2bi(x))) 
2 comments
Stewie Griffin 07/30/2017
de2bi/bi2de slaat 4 bytes op in octaaf. Werkt op octave-online.net.
Suever 07/30/2017
@StewieGriffin Bedankt!

miles 07/29/2017.

J , 13 bytes

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

Probeer het online!

Uitleg

/:~"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
Er is weer die binaire linkervulling, +1. En ook, kun je uitleggen waarom je de inverse van transpose zou moeten gebruiken, omdat het gewoon getransponeerd is?
miles 08/01/2017
@ Zacharý De invers worden gebruikt om de bewerkingen ongedaan te maken die zijn gebruikt voor het sorteren van elke rij. Het klopt dat de inverse van transpose gewoon transpose is, maar een andere manier om dit te zien is als M , waarbij de eerste twee functies slechts de inverses van de laatste twee.

Erik the Outgolfer 07/30/2017.

05AB1E , 9 bytes

bí0ζR€{øC 

Probeer het online!

Nog een ander algoritme van Magic's.

3 comments
Magic Octopus Urn 07/31/2017
ζ , verdomme. Mijn verwijderd, mijn +1.
Erik the Outgolfer 07/31/2017
@MagicOctopusUrn Waarom heb je de jouwe verwijderd? Niet nodig.
Magic Octopus Urn 07/31/2017
Het is niet echt veel anders (in termen van algoritme) en dit was 25% beter.

Zacharý 07/30/2017.

Dyalog APL, 24 21 19 bytes

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

Probeer het online! (zo aangepast dat TryAPL het als geldig accepteert)

Hoe?

  • geëvalueerde input (arrays zijn spatie gescheiden)
  • 2⊥⍣¯1⊢ converteert elk van de argumenten naar binair (getransponeerd van wat in de vraag staat)
  • verandert een 2D-array in een vector van vectoren
  • {⍵[⍋⍵]}¨ sorteert elk van de elementen van de vector
  • zet de vector van vectoren opnieuw in een 2D-array
  • 2⊥ converteren van binair (aangezien het een soort van transpositie is, komen we tot het juiste resultaat)

James Heslip 07/30/2017.

Dyalog APL (23 tekens)

NO 
  1. Converteer de invoerargumenten naar een binaire matrix
  2. Splits de matrix in kolommen
  3. Sorteer de kolommen in oplopende volgorde
  4. Converteer de gesorteerde rijen terug naar decimaal

Voorbeeld

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

Bedankt aan Zacharý voor het corrigeren van mij op deze.

5 comments
Zacharý 07/30/2017
U kunt vervangen door (⊥⍣¯1)⍵ met ⊥⍣¯1⊢⍵ . Ik denk ook niet dat je de asspecificatie op splitsen nodig hebt ( ↓[1] => ).
Zacharý 07/30/2017
Oh, en je zou het moeten omzetten naar een lijst!
Zacharý 07/30/2017
Dit is ongeldig.
James Heslip 07/30/2017
Bedankt, Zacharý, ik werkte gisteravond laat aan en ik denk dat ik het probleem verkeerd heb gelezen. Ik heb mijn oplossing nu aangepast.
1 Zacharý 07/30/2017
Nou, goed gedaan! ( ⊥⍣¯1 echt een ingebouwde zijn). En bedankt dat je mijn gebruikersnaam juist hebt.

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

Probeer het online

-2 bytes thanks to Cows quack

1 comments
Cows quack 07/29/2017
(1< kan 2**c&e

Dopapp 07/30/2017.

Python 2, 142 bytes

... en nog steeds golfen ... hopelijk - Alle hulp op prijs gesteld!

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

Een groot deel hiervan is voor het opvullen van de nummers met nullen.

Leesbaarder:

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

Hiermee wordt een array met de binaire tekenreeksrepresentaties gemaakt, met een pad geplaatst, 90 graden met de klok mee gedraaid, elke rij gesorteerd, 90 graden naar achteren geroteerd en vervolgens gehele getallen uit elke rij gemaakt.

2 comments
Mr. Xcoder 07/30/2017
142 bytes , je hebt wat overbodige haakjes.
Dopapp 07/30/2017
@ Mr.Xcoder, oh ja dat was stom

Related questions

Hot questions

Language

Popular Tags