Tembok Biner yang Lemah

21

Terinspirasi oleh Buat dinding biner

Diberikan daftar bilangan bulat positif, kita dapat menuliskan semuanya di atas satu sama lain seperti itu, [2, 6, 9, 4]sebagai contoh:

0010
0110
1001
0100

Kita bisa membayangkan ini sebagai tembok:

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

Namun, ini adalah dinding yang sangat lemah, dan telah runtuh! Setiap 1( #) jatuh hingga menyentuh "tanah" atau yang lain 1( #). The 0s ( .s) yang hadir di tempat yang ditinggalkan terharu 1s.

Ini menjadi sebagai berikut:

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

Yang diterjemahkan kembali ke:

0000
0000
0110
1111

Yang, sebagai daftar angka, adalah [0, 0, 6, 15].

Kasus uji lain

[10, 17, 19, 23]

Ini menjadi:

01010
10001
10011
10111

yang menjadi:

00000
10011
10011
11111

menerjemahkan kembali ke:

[0, 19, 19, 31]

Tantangan

Diberikan daftar bilangan bulat positif, terapkan transformasi ini ke daftar. Input / Output sebagai daftar bilangan bulat positif dalam format apa pun yang masuk akal. Celah standar berlaku.

Ini adalah , jadi jawaban tersingkat dalam byte menang!

HyperNeutrino
sumber
Sandbox Post
HyperNeutrino
1
Lebih banyak testcases? Anda tahu, testis non-persegi akan bagus.
Leaky Nun
@ LeakyNun Tentu. Saya akan melakukannya.
HyperNeutrino
Itu hanya masalah penyortiran untuk bit array.
Marcus Müller
@ MarcusMüller Anda benar - saya menyadari bahwa setelah jawaban MATL: P
HyperNeutrino

Jawaban:

29

MATL , 4 byte

BSXB

Cobalah di MATL Online

Penjelasan

    % 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
sumber
o_O Bagaimana cara kerjanya: o
HyperNeutrino
1
Apakah MATL baru saja mengeluarkan Jelly dari golf sebanyak 4 byte ? o_O
manusiawi
5 byte sekarang :-p
Leaky Nun
Saya tidak pernah berpikir akan ada built-in untuk memindahkan yang ke bawah xD +1
HyperNeutrino
1
@ benar-benar tidak manusiawi, tunggu sampai Dennis datang
JungHwan Min
5

Python , 68 byte

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

Cobalah online!

Anders Kaseorg
sumber
5

JavaScript (ES6), 50 byte

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

Penjelasan: Misalkan dua baris dinding seperti ini:

0011
0101

Hasilnya harus seperti ini:

0001
0111

Dengan kata lain, baris pertama menjadi DAN dari dua baris dan baris kedua menjadi ATAU dari dua baris. Ini hanya perlu diulangi cukup kali agar semua bit jatuh ke bawah.

Neil
sumber
2

Japt , 16 byte

m¤z3 ®¬n qÃz mn2

Cobalah online! menggunakan -Qbendera untuk memformat hasil array.

Penjelasan

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
sumber
Saya pikir Anda dapat menyimpan byte denganmì2 z3 mn z mì2
ETHproduksi
@ ETHproductions Tampaknya memutar array 2D, alih-alih memutar array string, mengisi setiap array batin dengan nullbukannya spasi. Jadi sepertinya itu tidak berhasil. Dan nulldisortir ke kanan 1s, tidak seperti spasi, yang disortir ke kiri.
Justin Mariner
2

Mathematica, 64 byte

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

 adalah \[Transpose]

Ini mengkonversi input (daftar angka) ke daftar daftar digit, membalutnya menjadi matriks persegi, mentransposasikannya, mengurutkan baris sehingga 1's "jatuh" ke bawah, transposes kembali, kemudian mengubah kembali menjadi angka .

DanTheMan
sumber
2

Oktaf, 29 25 byte

4 byte disimpan berkat @Stewie

@(x)bi2de(sort(de2bi(x)))
Suever
sumber
de2bi/bi2demenghemat 4 byte dalam oktaf. Bekerja di octave-online.net.
Stewie Griffin
@StewieGriffin Terima kasih!
Suever
1

J , 13 byte

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

Cobalah online!

Penjelasan

/:~"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
mil
sumber
Ada padding kiri biner itu lagi, +1. Dan juga, dapatkah Anda menjelaskan mengapa Anda perlu menggunakan invers dari transpose, karena itu hanya transpose?
Zacharý
@ Zacharý invers digunakan untuk membatalkan operasi yang digunakan sebelum mengurutkan setiap baris. Memang benar bahwa kebalikan dari transpos hanya transpos, tetapi cara lain untuk melihat ini adalah <convert from binary> <transpose> <sort each row> <transpose> <convert to binary> M, di mana dua fungsi pertama hanyalah kebalikan dari dua yang terakhir.
mil
1

05AB1E , 9 byte

bí0ζR€{øC

Cobalah online!

Agak berbeda algoritma dari Magic.

Erik the Outgolfer
sumber
ζ, sial. Hapus milik saya, ambil +1 saya.
Guci Gurita Ajaib
@MagicOctopusUrn Mengapa Anda menghapus milik Anda? Tidak perlu untuk.
Erik the Outgolfer
Tidak jauh berbeda (dalam hal algoritma) dan ini 25% lebih baik.
Guci Gurita Ajaib
1

Dyalog APL, 24 21 19 byte

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

Cobalah online! (dimodifikasi sehingga TryAPL menerimanya sebagai valid)

Bagaimana?

  • input yang dievaluasi (array dipisahkan oleh ruang)
  • 2⊥⍣¯1⊢ mengonversi setiap argumen menjadi biner (mengubah apa yang ada dalam pertanyaan)
  • mengubah array 2D menjadi vektor vektor
  • {⍵[⍋⍵]}¨ mengurutkan masing-masing elemen vektor
  • mengubah vektor vektor menjadi array 2D lagi
  • 2⊥ mengkonversi dari biner (karena itu semacam transpos itu, kita sampai pada hasil yang benar)
Zacharý
sumber
1

Dyalog APL (23 karakter)

{2⊥¨↓⍉↑{⍵[⍋⍵]}¨↓2⊥⍣¯1⊢⍵}
  1. Ubah argumen input menjadi matriks biner
  2. Membagi matriks menjadi kolom
  3. Urutkan kolom ke dalam urutan menaik
  4. Ubah baris yang diurutkan kembali menjadi desimal

Contoh

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

Terima kasih kepada Zacharý karena mengoreksi saya tentang hal ini.

James Heslip
sumber
Anda dapat mengganti dengan (⊥⍣¯1)⍵dengan ⊥⍣¯1⊢⍵. Juga, saya tidak berpikir Anda memerlukan spesifikasi sumbu pada split ( ↓[1]=> ).
Zacharý
Oh, dan Anda seharusnya mengubahnya kembali menjadi daftar!
Zacharý
Ini tidak valid.
Zacharý
Terima kasih, Zacharý, saya telah mengerjakannya tadi malam dan saya pikir saya salah membaca masalahnya. Saya telah memodifikasi solusi saya sekarang.
James Heslip
1
Yah, kerja bagus! ( ⊥⍣¯1Benar-benar harus builtin). Dan terima kasih telah benar-benar mendapatkan nama pengguna saya dengan benar.
Zacharý
0

JavaScript, 127 125 byte

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

Cobalah online

-2 byte berkat Sapi dukun


sumber
(1<<c)&edapat menjadi2**c&e
Kritixi Lithos
0

Python 2, 142 byte

... dan masih bermain golf ... semoga –– Bantuan apa pun dihargai!

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

Sebagian besar dari ini adalah untuk mengisi angka dengan nol.

Lebih mudah dibaca:

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

Ini menciptakan array dari representasi string biner, membalutnya, memutarnya 90º searah jarum jam, mengurutkan setiap baris, memutarnya kembali 90º, dan kemudian membuat bilangan bulat dari setiap baris.

Daniel
sumber
142 byte , Anda memiliki beberapa tanda kurung yang berlebihan.
Tn. Xcoder
@ Mr.Xcoder, oh ya itu konyol
Daniel