Ослабленные бинарные стены

21

Вдохновленный Создать бинарную стену

Учитывая список натуральных чисел, мы можем выписать их все друг над другом, например, так [2, 6, 9, 4]:

0010
0110
1001
0100

Мы можем представить это как стену:

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

Однако это очень слабая стена, и она рухнула! Каждый 1( #) падает, пока не достигнет "земли" или другого 1( #). В 0ы ( .ы) присутствуют в местах , оставленных перемещаемых 1с.

Это становится следующим:

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

Что переводится обратно в:

0000
0000
0110
1111

Который, как список чисел, является [0, 0, 6, 15].

Еще один тест

[10, 17, 19, 23]

Это становится:

01010
10001
10011
10111

который становится:

00000
10011
10011
11111

перевод обратно на:

[0, 19, 19, 31]

Вызов

Учитывая список натуральных чисел, примените это преобразование к списку. Ввод / вывод в виде списков натуральных чисел в любом приемлемом формате. Применяются стандартные лазейки.

Это , поэтому выигрывает самый короткий ответ в байтах!

HyperNeutrino
источник
1
Еще тесты? Вы знаете, неквадратные тестовые случаи были бы хороши.
Утренняя монахиня
@ LeakyNun Конечно. Я это сделаю.
HyperNeutrino
Это просто проблема сортировки для битовых массивов.
Маркус Мюллер
@ MarcusMüller Вы правы - я понял, что после ответа MATL: P
HyperNeutrino

Ответы:

29

MATL , 4 байта

BSXB

Попробуйте это на MATL Online

объяснение

    % 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
источник
o_O Как это работает: o
HyperNeutrino
1
Мэтл только что выиграл у желе 4 байта ? o_O
полностью человек
5 байтов сейчас :-p
Leaky Nun
Я никогда не думал, что будет встроенный, чтобы переместить те на дно xD +1
HyperNeutrino
1
@totallyhuman хорошо, подожди, пока Деннис не придет
JungHwan Мин
5

JavaScript (ES6), 50 байт

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

Пояснение: Предположим, что два ряда стены были такими:

0011
0101

Результат должен быть таким:

0001
0111

Другими словами, первая строка становится И двух строк, а вторая строка ИЛИ двух строк. Это просто нужно повторить достаточно раз, чтобы все биты упали на дно.

Нил
источник
2

Japt , 16 байт

m¤z3 ®¬n qÃz mn2

Попробуйте онлайн! используя -Qфлаг для форматирования результата массива.

объяснение

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
Джастин Маринер
источник
Я думаю, что вы можете сохранить байт сmì2 z3 mn z mì2
ETHproductions
@ETHproductions Кажется, что вращение двумерного массива вместо вращения массива строк дополняет каждый внутренний массив nullвместо пробелов. Так что это не похоже на работу. И nullсортируется справа от 1s, в отличие от пробелов, которые сортируются слева.
Джастин Маринер
2

Mathematica, 64 байта

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

 это \[Transpose]

Это преобразует входные данные (список чисел) в список списков цифр, дополняет их квадратной матрицей, транспонирует их, сортирует строки так, чтобы единицы "падали" вниз, транспонирует назад, затем преобразует обратно в числа ,

DanTheMan
источник
2

Октава, 29 25 байт

4 байта сохранены благодаря @Stewie

@(x)bi2de(sort(de2bi(x)))
Suever
источник
de2bi/bi2deсохраняет 4 байта в октаве. Работает на octave-online.net.
Стьюи Гриффин
@StewieGriffin Спасибо!
Suever
1

J , 13 байт

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

Попробуйте онлайн!

объяснение

/:~"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
миль
источник
Снова двоичный отступ слева, +1. А также, можете ли вы объяснить, почему вам нужно использовать обратное транспонирование, поскольку это просто транспонирование?
Захари
@ Zacharý Обратное используется для отмены операций, выполняемых перед сортировкой каждой строки. Это правда, что инверсия транспонирования - это просто транспонирование, но другой способ увидеть это так <convert from binary> <transpose> <sort each row> <transpose> <convert to binary> M: первые две функции - это инверсии двух последних.
миль
1

05AB1E , 9 байтов

bí0ζR€{øC

Попробуйте онлайн!

В некотором роде алгоритм отличается от Magic.

Эрик Outgolfer
источник
ζ, черт. Удалил мой, возьми мой +1.
Волшебная Осьминог Урна
@MagicOctopusUrn Почему ты удалил свой? Не нужно.
Эрик Outgolfer
Это не очень отличается (с точки зрения алгоритма), и это было на 25% лучше.
Волшебная Осьминог Урна
1

Дьялог АПЛ, 24 21 19 байт

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

Попробуйте онлайн! (изменено, поэтому TryAPL принимает его как действительный)

Как?

  • оцененный ввод (массивы разделены пробелом)
  • 2⊥⍣¯1⊢ преобразует каждый из аргументов в двоичный (транспонированный из того, что в вопросе)
  • превращает 2D массив в вектор векторов
  • {⍵[⍋⍵]}¨ сортирует каждый из элементов вектора
  • снова превращает вектор векторов в двумерный массив
  • 2⊥ конвертировать из двоичного кода (поскольку он как бы транспонирует его, мы получаем правильный результат)
Zachary
источник
1

Dyalog APL (23 символа)

{2⊥¨↓⍉↑{⍵[⍋⍵]}¨↓2⊥⍣¯1⊢⍵}
  1. Преобразовать входные аргументы в двоичную матрицу
  2. Разделить матрицу на столбцы
  3. Сортировать столбцы в порядке возрастания
  4. Преобразуйте отсортированные строки обратно в десятичные

пример

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

Спасибо Захари за то, что поправили меня.

Джеймс Хеслип
источник
Вы можете заменить (⊥⍣¯1)⍵на ⊥⍣¯1⊢⍵. Кроме того, я не думаю, что вам нужна спецификация оси для split ( ↓[1]=> ).
Захари
О, и вы должны преобразовать его обратно в список!
Захари
Это неверно
Захари
Спасибо, Захари, я работал над этим поздно вечером и думаю, что неправильно понял проблему. Я изменил свое решение сейчас.
Джеймс Хеслип
1
Ну, хорошая работа! ( ⊥⍣¯1действительно должен быть встроенным). И спасибо за то, что вы правильно поняли мое имя пользователя.
Захари
0

Python 2, 142 байта

... и все еще играю в гольф ... надеюсь - любая помощь оценена!

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

Большая часть этого для заполнения чисел нулями.

Более читабельно:

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

Это создает массив представлений двоичной строки, дополняет его, поворачивает на 90º по часовой стрелке, сортирует каждую строку, поворачивает ее назад на 90º, а затем создает целые числа из каждой строки.

Даниил
источник
142 байта , у вас есть лишняя скобка.
Мистер Кскодер
@ Mr.Xcoder, о да, это было глупо
Даниэль