Osłabione ściany binarne

21

Zainspirowany przez Utwórz ścianę binarną

Biorąc pod uwagę listę dodatnich liczb całkowitych, możemy zapisać je wszystkie nad sobą tak, na [2, 6, 9, 4]przykład:

0010
0110
1001
0100

Możemy to sobie wyobrazić jako ścianę:

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

Jest to jednak bardzo słaby mur, który się zawalił! Każda 1( #) spada, aż uderzy w „ziemię” lub inną 1( #). W 0s ( .a) są obecne w miejscach pozostawionych przez przenoszonych 1s.

Staje się to następujące:

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

Co przekłada się z powrotem na:

0000
0000
0110
1111

Który jako lista liczb jest [0, 0, 6, 15].

Kolejny przypadek testowy

[10, 17, 19, 23]

Staje się to:

01010
10001
10011
10111

który staje się:

00000
10011
10011
11111

tłumacząc z powrotem na:

[0, 19, 19, 31]

Wyzwanie

Biorąc pod uwagę listę dodatnich liczb całkowitych, zastosuj tę transformację do listy. Dane wejściowe / wyjściowe jako listy liczb całkowitych dodatnich w dowolnym rozsądnym formacie. Obowiązują standardowe luki.

To jest , więc wygrywa najkrótsza odpowiedź w bajtach!

HyperNeutrino
źródło
Sandbox Post
HyperNeutrino
1
Więcej przypadków testowych? Wiesz, niekwadratowe przypadki testowe byłyby dobre.
Leaky Nun
@LeakyNun Sure. Zrobię to.
HyperNeutrino
To tylko problem z sortowaniem tablic bitowych.
Marcus Müller
@ MarcusMüller Masz rację - zdałem sobie sprawę, że po odpowiedzi MATL: P
HyperNeutrino

Odpowiedzi:

29

MATL , 4 bajty

BSXB

Wypróbuj w MATL Online

Wyjaśnienie

    % 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
źródło
o_O Jak to działa: o
HyperNeutrino
1
Czy MATL wyprzedził galaretkę o 4 bajty ? o_O
totalnie ludzki,
5 bajtów teraz :-p
Leaky Nun
Nigdy nie myślałem, że będzie wbudowany, aby przenieść te na dół xD +1
HyperNeutrino
1
@ całkowicie ludzki, poczekaj, aż przyjdzie Dennis
JungHwan Min
5

Python , 68 bajtów

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

Wypróbuj online!

Anders Kaseorg
źródło
5

JavaScript (ES6), 50 bajtów

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

Objaśnienie: Załóżmy, że dwa rzędy ściany wyglądały tak:

0011
0101

Wynik musi być następujący:

0001
0111

Innymi słowy, pierwszy rząd staje się AND z dwóch rzędów, a drugi rząd staje się OR z dwóch rzędów. Należy to powtórzyć tyle razy, aby wszystkie bity spadły na dno.

Neil
źródło
2

Japt , 16 bajtów

m¤z3 ®¬n qÃz mn2

Wypróbuj online! używając -Qflagi do sformatowania wyniku tablicy.

Wyjaśnienie

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
źródło
Myślę , że możesz zaoszczędzić bajt dziękimì2 z3 mn z mì2
ETHproductions
@ETHproductions Wydaje się, że obracanie tablicy 2D zamiast obracania tablicy ciągów powoduje wstawienie każdej tablicy wewnętrznej nullzamiast spacji. Więc to nie działa. I nulljest posortowany na prawo od 1s, w przeciwieństwie do spacji, które są posortowane na lewo.
Justin Mariner
2

Mathematica, 64 bajty

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

 jest \[Transpose]

Konwertuje to dane wejściowe (listę liczb) na listę list cyfr, wstawia je do macierzy kwadratowej, transponuje, sortuje wiersze, tak aby „1” opadło na dół, transponuje z powrotem, a następnie przekształca z powrotem w liczby .

DanTheMan
źródło
2

Oktawa, 29 25 bajtów

4 bajty zapisane dzięki @Stewie

@(x)bi2de(sort(de2bi(x)))
Suever
źródło
de2bi/bi2dezapisuje 4 bajty w oktawie. Działa na octave-online.net.
Stewie Griffin,
@StewieGriffin Thanks!
Suever
1

J , 13 bajtów

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

Wypróbuj online!

Wyjaśnienie

/:~"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
mile
źródło
Znowu jest to binarne lewe dopełnienie, +1. A także, czy możesz wyjaśnić, dlaczego musiałbyś użyć odwrotnej transpozycji, skoro to tylko transpozycja?
Zacharý
@ Zacharý Odwrotności służą do cofnięcia operacji użytych przed posortowaniem każdego wiersza. To prawda, że ​​odwrotność transpozycji jest po prostu transpozycją, ale można to zobaczyć inaczej <convert from binary> <transpose> <sort each row> <transpose> <convert to binary> M, gdy dwie pierwsze funkcje są tylko odwrotnością dwóch ostatnich.
mile
1

05AB1E , 9 bajtów

bí0ζR€{øC

Wypróbuj online!

Trochę inny algorytm niż Magic's.

Erik the Outgolfer
źródło
ζ, cholera. Usunąłem moją, weź moje +1.
Magic Octopus Urn
@MagicOctopusUrn Dlaczego usunąłeś swój? Nie trzeba.
Erik the Outgolfer,
Nie różni się tak naprawdę (pod względem algorytmu), a było to o 25% lepsze.
Magic Octopus Urn
1

Dyalog APL, 24 21 19 bajtów

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

Wypróbuj online! (zmodyfikowany, więc TryAPL akceptuje go jako prawidłowy)

W jaki sposób?

  • oceniane dane wejściowe (tablice są oddzielone spacjami)
  • 2⊥⍣¯1⊢ konwertuje każdy z argumentów na binarny (transponowany z pytania)
  • zamienia tablicę 2D w wektor wektorów
  • {⍵[⍋⍵]}¨ sortuje każdy z elementów wektora
  • ponownie przekształca wektor wektorów w tablicę 2D
  • 2⊥ konwersja z pliku binarnego (ponieważ w pewnym sensie transponuje go, dochodzimy do prawidłowego wyniku)
Zacharý
źródło
1

Dyalog APL (23 znaki)

{2⊥¨↓⍉↑{⍵[⍋⍵]}¨↓2⊥⍣¯1⊢⍵}
  1. Konwertuj argumenty wejściowe na macierz binarną
  2. Podziel macierz na kolumny
  3. Posortuj kolumny w porządku rosnącym
  4. Konwertuj posortowane wiersze z powrotem na dziesiętne

Przykład

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

Dzięki Zacharýowi za poprawienie mnie w tym.

James Heslip
źródło
Można wymienić (⊥⍣¯1)⍵z ⊥⍣¯1⊢⍵. Poza tym nie sądzę, żebyś potrzebował specyfikacji osi dla podziału ( ↓[1]=> ).
Zacharý
Aha, i powinieneś przekonwertować go z powrotem na listę!
Zacharý
To jest nieprawidłowe
Zacharý
Dziękuję, Zacharý, pracowałem nad tym późnym wieczorem i myślę, że źle zrozumiałem problem. Zmodyfikowałem teraz moje rozwiązanie.
James Heslip
1
Dobra robota! ( ⊥⍣¯1naprawdę musi być wbudowany). I dziękuję, że właściwie poprawiliście moją nazwę użytkownika.
Zacharý
0

JavaScript, 127 125 bajtów

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

Wypróbuj online

-2 bajty dzięki kwakowi krów


źródło
(1<<c)&emoże zostać2**c&e
Kritixi Lithos
0

Python 2, 142 bajty

... i wciąż gra w golfa ... mam nadzieję –– Każda pomoc doceniona!

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

Duża część tego służy do uzupełniania liczb zerami.

Bardziej czytelny:

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

Tworzy to tablicę reprezentacji ciągów binarnych, wypełnia ją, obraca o 90º zgodnie z ruchem wskazówek zegara, sortuje każdy rząd, obraca go o 90º do tyłu, a następnie tworzy liczby całkowite z każdego rzędu.

Daniel
źródło
142 bajty , masz zbędny nawias.
Pan Xcoder,
@ Mr.Xcoder, och tak, to było głupie
Daniel