Geschwächte binäre Wände

21

Inspiriert von Erstellen Sie eine binäre Wand

Ausgehend von einer Liste positiver Ganzzahlen können wir sie wie folgt übereinander schreiben [2, 6, 9, 4]:

0010
0110
1001
0100

Wir können uns das als Wand vorstellen:

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

Dies ist jedoch eine sehr schwache Mauer, die eingestürzt ist! Jedes 1( #) fällt herunter, bis es auf den "Boden" oder ein anderes 1( #) trifft . Die 0s ( .s) sind an Stellen vorhanden, die von bewegten 1s übrig bleiben .

Dies wird wie folgt:

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

Was übersetzt zurück zu:

0000
0000
0110
1111

Was als Liste von Zahlen ist [0, 0, 6, 15].

Ein weiterer Testfall

[10, 17, 19, 23]

Dies wird:

01010
10001
10011
10111

was wird:

00000
10011
10011
11111

zurück zu übersetzen:

[0, 19, 19, 31]

Herausforderung

Wenden Sie diese Transformation bei einer Liste positiver Ganzzahlen auf die Liste an. Eingabe / Ausgabe als Liste positiver Ganzzahlen in einem beliebigen Format. Es gelten Standardlücken.

Dies ist ein , also gewinnt die kürzeste Antwort in Bytes!

HyperNeutrino
quelle
Sandbox Post
HyperNeutrino
1
Weitere Testfälle? Sie wissen, nicht quadratische Testfälle wären gut.
Undichte Nonne
@LeakyNun Sicher. Ich werde das tun.
HyperNeutrino
Das ist nur ein Sortierproblem für Bit-Arrays.
Marcus Müller
@ MarcusMüller Du hast Recht - das habe ich nach der MATL-Antwort festgestellt: P
HyperNeutrino

Antworten:

29

MATL , 4 Bytes

BSXB

Probieren Sie es bei MATL Online aus

Erläuterung

    % 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
Suever
quelle
o_O Wie funktioniert das
?
1
Hat MATL Jelly gerade um 4 Bytes übertroffen ? o_O
totalhuman
5 Bytes jetzt :-p
Leaky Nun
Ich hätte nie gedacht, dass es eine integrierte Funktion geben würde, um diejenigen nach unten zu verschieben.
XD
1
@totallyhuman na ja, warte bis Dennis kommt
JungHwan Min 29.07.17
5

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

Probieren Sie es online!

Anders Kaseorg
quelle
5

JavaScript (ES6), 50 Byte

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

Erläuterung: Angenommen, zwei Zeilen der Wand lauten wie folgt:

0011
0101

Das Ergebnis muss sein:

0001
0111

Mit anderen Worten wird die erste Zeile zum UND der beiden Zeilen und die zweite Zeile zum ODER der beiden Zeilen. Dies muss nur so oft wiederholt werden, dass alle Bits auf den Grund fallen.

Neil
quelle
2

Japt , 16 Bytes

m¤z3 ®¬n qÃz mn2

Probieren Sie es online! Verwenden Sie das -QFlag, um das Array-Ergebnis zu formatieren.

Erläuterung

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
Justin Mariner
quelle
Ich denke, Sie können ein Byte speichern mitmì2 z3 mn z mì2
ETHproductions
@ETHproductions Es scheint, als würde das 2D-Array gedreht, anstatt das String-Array zu drehen, und jedes innere Array mit nullLeerzeichen aufgefüllt . Das scheint also nicht zu funktionieren. Und nullist rechts vom 1s sortiert, im Gegensatz zu Leerzeichen, die links sortiert sind.
Justin Mariner
2

Mathematica, 64 Bytes

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

 ist \[Transpose]

Dies wandelt die Eingabe (eine Liste von Zahlen) in eine Liste von Ziffernlisten um, füllt sie als quadratische Matrix auf, transponiert sie, sortiert die Zeilen so, dass die Einsen nach unten fallen, transponiert zurück und wandelt sie dann wieder in Zahlen um .

DanTheMan
quelle
2

Oktave, 29 25 Bytes

4 Bytes gespart dank @Stewie

@(x)bi2de(sort(de2bi(x)))
Suever
quelle
de2bi/bi2deSpeichert 4 Bytes in Oktave. Funktioniert auf octave-online.net.
Stewie Griffin
@StewieGriffin Danke!
Suever
1

J , 13 Bytes

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

Probieren Sie es online!

Erläuterung

/:~"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
Meilen
quelle
Es gibt wieder dieses binäre Links-Padding, +1. Und können Sie auch erklären, warum Sie die Umkehrung der Transponierung verwenden müssen, da es sich nur um eine Transponierung handelt?
Zacharý
@ Zacharý Die Inversen werden verwendet, um die vor dem Sortieren jeder Zeile verwendeten Vorgänge rückgängig zu machen. Es ist wahr, dass die Umkehrung der Transponierung nur eine Transponierung ist, aber eine andere Art, dies zu sehen, ist <convert from binary> <transpose> <sort each row> <transpose> <convert to binary> M, dass die ersten beiden Funktionen nur die Umkehrungen der letzten beiden Funktionen sind.
Meilen
1

05AB1E , 9 Bytes

bí0ζR€{øC

Probieren Sie es online!

Ein bisschen anderer Algorithmus als bei Magic.

Erik der Outgolfer
quelle
ζ, verdammt. Meins gelöscht, nimm mein +1.
Magic Octopus Urn
@MagicOctopusUrn Warum hast du deine gelöscht? Kein Notwendigkeit für.
Erik der Outgolfer
Es ist nicht wirklich viel anders (in Bezug auf den Algorithmus) und das war 25% besser.
Magic Octopus Urn
1

Dyalog APL, 24 21 19 Bytes

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

Probieren Sie es online! (so geändert, dass TryAPL es als gültig akzeptiert)

Wie?

  • ausgewertete Eingabe (Arrays sind durch Leerzeichen getrennt)
  • 2⊥⍣¯1⊢ konvertiert jedes Argument in ein Binärargument (umgesetzt von dem, was in Frage kommt)
  • verwandelt ein 2D-Array in einen Vektor von Vektoren
  • {⍵[⍋⍵]}¨ sortiert jedes der Elemente des Vektors
  • verwandelt den Vektor von Vektoren wieder in ein 2D-Array
  • 2⊥ konvertiere von binär (da es es irgendwie transponiert, kommen wir zum richtigen Ergebnis)
Zacharý
quelle
1

Dyalog APL (23 Zeichen)

{2⊥¨↓⍉↑{⍵[⍋⍵]}¨↓2⊥⍣¯1⊢⍵}
  1. Konvertieren Sie die Eingabeargumente in eine binäre Matrix
  2. Teilen Sie die Matrix in Spalten auf
  3. Sortieren Sie die Spalten in aufsteigender Reihenfolge
  4. Konvertieren Sie die sortierten Zeilen wieder in Dezimalzahlen

Beispiel

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

Vielen Dank an Zacharý für die Korrektur.

James Heslip
quelle
Sie können mit (⊥⍣¯1)⍵mit ersetzen ⊥⍣¯1⊢⍵. Ich glaube auch nicht, dass Sie die Achsenspezifikation beim Teilen ( ↓[1]=> ) benötigen .
Zacharý
Oh, und du solltest es zurück in eine Liste konvertieren!
Zacharý
Dies ist ungültig.
Zacharý
Vielen Dank, Zacharý, ich habe letzte Nacht daran gearbeitet und ich glaube, ich habe das Problem falsch verstanden. Ich habe meine Lösung jetzt geändert.
James Heslip
1
Gut gemacht! ( ⊥⍣¯1Muss wirklich eingebaut sein). Und vielen Dank, dass Sie meinen Benutzernamen richtig eingegeben haben.
Zacharý
0

JavaScript, 127 125 Bytes

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

Probieren Sie es online aus

-2 Bytes dank Kühe quaken


quelle
(1<<c)&ekann werden2**c&e
Kritixi Lithos
0

Python 2, 142 Bytes

... und immer noch Golf spielen ... hoffentlich –– Jede Hilfe wird geschätzt!

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

Ein großer Teil davon dient zum Auffüllen der Zahlen mit Nullen.

Besser lesbar:

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

Dadurch wird ein Array der binären Zeichenfolgendarstellungen erstellt, aufgefüllt, um 90 ° im Uhrzeigersinn gedreht, jede Zeile sortiert, um 90 ° zurückgedreht und dann aus jeder Zeile Ganzzahlen erstellt.

Daniel
quelle
142 Bytes , haben Sie einige redundante Klammern.
Mr. Xcoder
@ Mr.Xcoder, oh ja, das war albern
Daniel