Weakened Binary Walls

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

Inspired by Create a binary wall

Given a list of positive integers, we can write them out all above each other like so, for [2, 6, 9, 4] as an example:

0010
0110
1001
0100

We can imagine this as a wall:

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

However, this is a very weak wall, and it has collapsed! Each 1 (#) falls down until it hits the "ground" or another 1 (#). The 0s (.s) are present in spots left by moved 1s.

This becomes the following:

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

Which translates back to:

0000
0000
0110
1111

Which, as a list of numbers, is [0, 0, 6, 15].

Another test case

[10, 17, 19, 23]

This becomes:

01010
10001
10011
10111

which becomes:

00000
10011
10011
11111

translating back to:

[0, 19, 19, 31]

Challenge

Given a list of positive integers, apply this transformation to the list. Input/Output as lists of positive integers in any reasonable format. Standard loopholes apply.

This is a , so the shortest answer in bytes wins!

5 Comments
1 Leaky Nun 07/29/2017
More testcases? You know, non-square testcases would be good.
HyperNeutrino 07/29/2017
@LeakyNun Sure. I'll do that.
Marcus Müller 07/30/2017
That's just a sorting problem for bit arrays.
HyperNeutrino 07/30/2017
@MarcusMüller You're right - I realized that after the MATL answer :P

14 Answers


Suever 07/29/2017.

MATL, 4 bytes

BSXB

Try it at 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 How does this work :o
1 totallyhuman 07/29/2017
Did MATL just out-golf Jelly by 4 bytes? o_O
Leaky Nun 07/29/2017
5 bytes now :-p
HyperNeutrino 07/29/2017
I never thought there'd be a built-in to move the ones to the bottom xD +1
1 JungHwan Min 07/29/2017
@totallyhuman well, wait till Dennis comes

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

Try it 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

Explanation: Suppose two rows of the wall were like this:

0011
0101

The result needs to be this:

0001
0111

In other words, the first row becomes the AND of the two rows and the second row becomes the OR of the two rows. This just needs to be repeated enough times for all the bits to fall to the bottom.


Leaky Nun 07/29/2017.

Jelly, 9 bytes

BUz0Ṣ€ZUḄ

Try it online!


Justin Mariner 07/29/2017.

Japt, 16 bytes

m¤z3 ®¬n qÃz mn2

Try it online! using the -Q flag to format the array result.

Explanation

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
I think you can save a byte with mì2 z3 mn z mì2
Justin Mariner 07/30/2017
@ETHproductions It seems rotating the 2D array, instead of rotating the array of strings, pads each inner array with null instead of spaces. So that doesn't seem to work. And null is sorted to the right of the 1s, unlike spaces, which are sorted to the left.

DanTheMan 07/30/2017.

Mathematica, 64 bytes

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

 is \[Transpose]

This converts the input (a list of numbers) to a list of lists of digits, pads it to be a square matrix, transposes it, sorts the rows so the 1's "fall" to the bottom, transposes back, then converts back into numbers.


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)

Try it online!

Takes input like f(2, 6, 9, 4). Assumes input is non-empty. Uses a lot of tuple unpacking.


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 saves 4 bytes in octave. Works on octave-online.net.
Suever 07/30/2017
@StewieGriffin Thanks!

miles 07/29/2017.

J, 13 bytes

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

Try it online!

Explanation

/:~"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
There's that binary left-padding again, +1. And also, can you explain why you would need to use the inverse of transpose, since it is just transpose?
miles 08/01/2017
@Zacharý The inverses are used to undo the operations used before sorting each row. It's true that the inverse of transpose is just transpose, but another way to see this is as <convert from binary> <transpose> <sort each row> <transpose> <convert to binary> M, where the first two functions are just the inverses of the last two.

Erik the Outgolfer 07/30/2017.

05AB1E, 9 bytes

bí0ζR€{øC

Try it online!

Kinda different algorithm from Magic's.

3 comments
Magic Octopus Urn 07/31/2017
ζ, damnit. Deleted mine, take my +1.
Erik the Outgolfer 07/31/2017
@MagicOctopusUrn Why did you delete yours? No need to.
Magic Octopus Urn 07/31/2017
It's not really much different (in terms of algorithm) and this was 25% better.

Zacharý 07/30/2017.

Dyalog APL, 24 21 19 bytes

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

Try it online! (modified so TryAPL accepts it as valid)

How?

  • evaluated input (arrays are space separated)
  • 2⊥⍣¯1⊢ converts each each of the arguments to binary (transposed of what is in the question)
  • turns a 2D array into a vector of vectors
  • {⍵[⍋⍵]}¨ sorts each of the elements of the vector
  • turns the vector of vectors into a 2D array again
  • 2⊥ convert from binary (since it sort of transposes it, we arrive at the correct result)

James Heslip 07/30/2017.

Dyalog APL (23 characters)

{2⊥¨↓⍉↑{⍵[⍋⍵]}¨↓2⊥⍣¯1⊢⍵}
  1. Convert the input arguments into a binary matrix
  2. Split the matrix into columns
  3. Sort the columns into ascending order
  4. Convert the sorted rows back into decimal

Example

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

Thanks to Zacharý for correcting me on this one.

5 comments
Zacharý 07/30/2017
You can replace with (⊥⍣¯1)⍵ with ⊥⍣¯1⊢⍵. Also, I don't think you need the axis specification on split (↓[1]=>).
Zacharý 07/30/2017
Oh, and you're supposed to convert it back to a list!
Zacharý 07/30/2017
This is invalid.
James Heslip 07/30/2017
Thank you, Zacharý, I was working on this late last night and I think I misread the problem. I've modified my solution now.
1 Zacharý 07/30/2017
Well, good job! (⊥⍣¯1 really needs to be a builtin). And thank you for actually getting my username right.

ThePirateBay 07/29/2017.

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

Try it online

-2 bytes thanks to Cows quack

1 comments
Cows quack 07/29/2017
(1<<c)&e can become 2**c&e

Dopapp 07/30/2017.

Python 2, 142 bytes

... and still golfing... hopefully –– Any help appreciated!

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

A big chunk of this is for padding the numbers with zeroes.

More readable:

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

This creates an array of the binary string representations, pads it, rotates it 90º clockwise, sorts each row, rotates it back 90º, and then creates integers out of each row.

2 comments
Mr. Xcoder 07/30/2017
142 bytes, you have some redundant parenthesis.
Dopapp 07/30/2017
@Mr.Xcoder , oh yes that was silly

HighResolutionMusic.com - Download Hi-Res Songs

1 (G)I-DLE

POP/STARS flac

(G)I-DLE. 2018. Writer: Riot Music Team;Harloe.
2 The Chainsmokers

Beach House flac

The Chainsmokers. 2018. Writer: Andrew Taggart.
3 Ariana Grande

​Thank U, Next flac

Ariana Grande. 2018. Writer: Crazy Mike;Scootie;Victoria Monét;Tayla Parx;TBHits;Ariana Grande.
4 Nicki Minaj

No Candle No Light flac

Nicki Minaj. 2018. Writer: Denisia “Blu June” Andrews;Kathryn Ostenberg;Brittany "Chi" Coney;Brian Lee;TJ Routon;Tushar Apte;ZAYN;Nicki Minaj.
5 Clean Bandit

Baby flac

Clean Bandit. 2018. Writer: Jack Patterson;Kamille;Jason Evigan;Matthew Knott;Marina;Luis Fonsi.
6 Imagine Dragons

Bad Liar flac

Imagine Dragons. 2018. Writer: Jorgen Odegard;Daniel Platzman;Ben McKee;Wayne Sermon;Aja Volkman;Dan Reynolds.
7 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
8 BTS

Waste It On Me flac

BTS. 2018. Writer: Steve Aoki;Jeff Halavacs;Ryan Ogren;Michael Gazzo;Nate Cyphert;Sean Foreman;RM.
9 BlackPink

Kiss And Make Up flac

BlackPink. 2018. Writer: Soke;Kny Factory;Billboard;Chelcee Grimes;Teddy Park;Marc Vincent;Dua Lipa.
10 Fitz And The Tantrums

HandClap flac

Fitz And The Tantrums. 2017. Writer: Fitz And The Tantrums;Eric Frederic;Sam Hollander.
11 Backstreet Boys

Chances flac

Backstreet Boys. 2018.
12 Kelly Clarkson

Never Enough flac

Kelly Clarkson. 2018. Writer: Benj Pasek;Justin Paul.
13 Diplo

Close To Me flac

Diplo. 2018. Writer: Ellie Goulding;Savan Kotecha;Peter Svensson;Ilya;Swae Lee;Diplo.
14 Anne-Marie

Rewrite The Stars flac

Anne-Marie. 2018. Writer: Benj Pasek;Justin Paul.
15 Little Mix

Woman Like Me flac

Little Mix. 2018. Writer: Nicki Minaj;Steve Mac;Ed Sheeran;Jess Glynne.
16 Imagine Dragons

Machine flac

Imagine Dragons. 2018. Writer: Wayne Sermon;Daniel Platzman;Dan Reynolds;Ben McKee;Alex Da Kid.
17 Little Mix

The Cure flac

Little Mix. 2018.
18 Bradley Cooper

Always Remember Us This Way flac

Bradley Cooper. 2018. Writer: Lady Gaga;Dave Cobb.
19 Rita Ora

Velvet Rope flac

Rita Ora. 2018.
20 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.

Related questions

Hot questions

Language

Popular Tags