Удалить окружающие нули 2d массива

40

Это 2-мерная версия этого вопроса .

Дан непустой 2-мерный массив / матрица, содержащий только неотрицательные целые числа:

[0000000010000010011100000]

Выведите массив с удаленными окружающими нулями, то есть наибольшим непрерывным подмассивом без окружающих нулей:

[010001111]

Примеры:

[0000000010000010011100000]↦[010001111]
Input:
[[0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1], [0, 0, 1, 1, 1], [0, 0, 0, 0, 0]]

Output:
[[0, 1, 0], [0, 0, 1], [1, 1, 1]]

[00000003000005000000]↦[003000500]
Input:
[[0, 0, 0, 0], [0, 0, 0, 3], [0, 0, 0, 0], [0, 5, 0, 0], [0, 0, 0, 0]]

Output:
[[0, 0, 3], [0, 0, 0], [5, 0, 0]]

[123456789]↦[123456789]
Input:
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

Output:
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

[000000000000]↦[]
Input:
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

Output:
[]

[000011110000]↦[1111]
Input:
[[0, 0, 0, 0], [1, 1, 1, 1], [0, 0, 0, 0]]

Output:
[[1, 1, 1, 1]]

[010001000100]↦[111]
Input:
[[0, 1, 0, 0], [0, 1, 0, 0], [0, 1, 0, 0]]

Output:
[[1], [1], [1]]

[111112311111]↦[111112311111]
Input:
[[1, 1, 1, 1], [1, 2, 3, 1], [1, 1, 1, 1]]

Output:
[[1, 1, 1, 1], [1, 2, 3, 1], [1, 1, 1, 1]]
code-golf array-manipulation alephalpha
источник
3
@MattH Нет ничего сложного в неэзотерическом языке. :)Просто сложно сделать это коротким.
user202729
1
Можем ли мы дать вывод Falsey вместо пустой матрицы для последнего контрольного примера?
sundar - Восстановить Монику
1
Кроме того, если выходные данные могут представлять собой неквадратную матрицу, добавьте для этого контрольный пример.
sundar - Восстановить Монику
1
Тестовый пример, который сломал мою предыдущую отправку: [[0, 0, 0, 0], [0, 0, 0, 0], [1, 1, 1, 1], [0, 0, 0, 0]](результат, имеющий ширину / высоту 1)
Конор О'Брайен
1
Эй, можно ли добавить контрольный пример
[111112311111]
Beta Decay

Ответы:

39

Wolfram Language (Mathematica) , 42 байта

#&@@CellularAutomaton[{,{},0{,}},{#,0},0]&

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

Клеточные автоматы действительно являются ответом на жизнь , вселенную и все . 1

Как?

CellularAutomatonпринимает входной массив и необязательное значение фона. Таким образом, {#,0}указывает, что правило клеточного автомата должно применяться к входу, предполагая фон 0s.

Здесь важно урезать CellularAutomatonвывод, чтобы не было границы фоновых ячеек (потому что в противном случае вывод лежит на бесконечной плоскости).

Код применяет правило {Null, {}, {0, 0}}- применяя голову Nullк соседу 0-го радиуса каждой ячейки (то есть только к центру: самой ячейке) - точно 0раз. Результатом этого является исходный ввод, но с удаленным фоном (т.е. обрезка окружающих 0s).

1. Посмотрите на счет моего ответа? ;)

Юнг Хван Мин
источник
6
Хорошее встроенное злоупотребление ... ну у Mathematica есть встроенное, просто не выставленное напрямую.
user202729
3
Нет ссылки на XKCD 505 ?
Esolanging Fruit
+1 за сотовые автоматы и окончательный ответ.
ВысокоРадиоактивный
14

JavaScript (ES6), 98 байт

(a,z)=>(g=A=>A.slice(A.map(m=M=(r,i)=>M=(z?a:r).some(n=>z?n[i]:n)?1/m?i:m=i:M)|m,M+1))(a).map(z=g)

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

Как?

Чтобы преодолеть отсутствие встроенного zip - файла , мы определяем функцию g (), которая может работать со строками или столбцами входной матрицы a [] в зависимости от значения глобального флага z .

g () ищет минимальный индекс m и максимальный индекс M либо непустых строк (если z не определено), либо непустых столбцов (если z определен) и возвращает соответствующий фрагмент либо самой матрицы, либо данной строки матрицы.

Обобщить:

  • мы сначала удаляем строки, вызывая g () для матрицы с неопределенным z
  • затем мы удаляем столбцы, вызывая g () в каждой строке с заданным z , что приводит к этому довольно необычному.map(z=g)

комментарии

(a, z) => (               // a[] = input matrix; z is initially undefined
  g = A =>                // g() = function taking A = matrix or row
    A.slice(              //   eventually return A.slice(m, M + 1)
      A.map(m = M =       //     initialize m and M to non-numeric values
        (r, i) =>         //     for each row or cell r at position i in A:
        M = (z ? a : r)   //       iterate on either the matrix or the row
        .some(n =>        //       and test whether there's at least one
          z ? n[i] : n    //       non-zero cell in the corresponding column or row
        ) ?               //       if so:
          1 / m ? i       //         update the maximum index M (last matching index)
                : m = i   //         and minimum index m (first matching index)
        :                 //       otherwise:
          M               //         let M (and m) unchanged
      ) | m,              //     end of map(); use m as the first parameter of slice()
      M + 1               //     use M+1 as the second parameter of slice()
    )                     //   end of slice()
  )(a)                    // invoke g() on the matrix with z undefined
  .map(z = g)             // invoke g() on each row of the matrix with z defined
Arnauld
источник
2
Это впечатляет.
Джек Хейлз,
3
@Jek, Арно живет в совершенно другом измерении. Но если вам чрезвычайно повезло, вы можете иногда найти трюк, который он пропустил, и опубликовать более короткое решение. В процессе вы получите глубокое понимание JavaScript.
Рик Хичкок
4
@RickHitchcock Я не очень хорош в распознавании кодовых паттернов и регулярно скучаю по многим вещам, даже если видел их раньше. В этом конкретном примере я сосредоточился на возможности повторного использования g () и пропустил довольно очевидную оптимизацию на пути обновления m и M (-9 байт). Я полностью согласен с тем, что игра в код - это отличный (и увлекательный) способ узнать много нового о тонкостях языка.
Арнаулд
7

Haskell , 62 61 байт

f.f.f.f
f=reverse.foldr(zipWith(:))e.snd.span(all(<1))
e=[]:e

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

foldr(zipWith(:))eс e=[]:eэто немного корочеtranspose , и snd.span(all(<1))капли , ведущие списки нулей из списка списка. Как transposeследует reverseиз 2D-списка, равного повороту на 90 °, код f.f.f.fвсего лишь в четыре раза сбрасывает ведущие списки нулей и вращается .

Laikoni
источник
5

Брахилог , 24 22 20 19 байт

{s.h+>0∧.t+>0∧}\↰₁\

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

Выводит матрицу результатов в виде массива массивов или false для пустого вывода.

(Спасибо @Fatalize за предложение встроенного предиката и сохранение 1 байта.)

объяснение

Предикат 0 (основной): 

{...}     Define and call predicate 1 to remove all-zero rows
  \       Transpose the result
   ↰₁     Call pred 1 again, now to remove all-zero columns
     \    Transpose the result to have correct output orientation

Предикат 1:

?s.h+>0∧.t+>0∧
  .           output is
 s              a subsequence of the rows of
?              the input (implicit)
   h          also, output's head element (first row)
    +>0        has a sum > 0 (i.e. has at least one non-zero value)
       ∧.t+>0  and similarly the output's tail element (last row)
∧              (don't implicitly unify that 0 with the output)
sundar - Восстановить Монику
источник
Записав первый предикат встроенный в 1 байт короче: {s.h+>0∧.t+>0∧}\↰₁\ . (это верно практически для любого ответа на брахилоге, предикаты на новых строках действительно реализуются только в том случае, если вы хотите написать более читаемые вещи).
Фатализировать
@Fatalize Спасибо, обновлено (наконец-то!). Я никогда не думал о том, что встроенный синтаксис предикатов является одновременно определением и приложением предикатов, довольно круто
sundar - Восстановить Монику
5

R , 96 100 97 байт

function(m)m[~m,~t(m),drop=F]
"~"=function(x,z=seq(r<-rowSums(x)))z>=min(y<-which(r>0))&z<=max(y)

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

~Помощник принимает неотрицательный вектор и возвращает вектор с FALSEдля «внешнего вида» 0S вектора и TRUEдля позитивов и любого «интерьера» 0с. Эта функция применяется к суммам строк и столбцов входной матрицы.

~и ! использовать синтаксический анализ операторов R.

Исправлено в соответствии с комментарием @ DigEmAll, но с некоторыми байтами, возвращенными из @ J.Doe

НГМ
источник
1
Я думаю, что вы должны добавить, drop=Fкак я сделал, иначе эти 2 теста вернут вектор вместо строки и столбца: попробуйте онлайн!
digEmAll
97 байт с drop=F. Все еще под тонной!
J.Doe
5

R , 89 79 байт

function(m,y=apply(which(m>0,T),2,range)){y[!1/y]=0;m[y:y[2],y[3]:y[4],drop=F]}

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

Спасибо @ngm за код тестовых случаев и @ J.Doe за сохранение 10 байтов!

  • Мне пришлось добавить drop=Fпараметр из-за поведения R по умолчанию, превращающего одну строку / матрицу col в векторы ...
digEmAll
источник
Я не заметил, что мой предыдущий код не работал с нулями ... теперь он, к сожалению, исправлен с гораздо большим количеством байтов :(
digEmAll
1
Я хотел бы +2 это. Действительно хорошее использование FiveNum.
JayCe
79 байтов, используя rangeи настраивая индексацию
J.Doe
1
@ J.Doe: диапазон, конечно! отличная идея, спасибо!
digEmAll
3

Python 2 , 71 байт

Возвращает путем изменения ввода. Список должен быть передан в качестве ввода.

def f(a):exec'while a and 1>sum(a[-1]):a.pop()\na[:]=zip(*a)[::-1]\n'*4

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

Python 2 , 77 байт

Это также изменяет ввод, но это работает ....

def f(a):exec'while a and 1>sum(a[-1]):a.pop()\na=zip(*a)[::-1]\n'*4;return a

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

user202729
источник
2

Шелуха , 11 байт

!5¡(T0mo↔↓¬

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

Я чувствую, что некоторые байты можно сбрить, укоротив !5¡часть.

Как это работает

!5¡(

Повторно применяйте функцию, описанную ниже, собирая результаты в бесконечном списке. Затем получите5гоэлемент. Другими словами, примените функцию к входу 4 раза.

mo↔↓¬

Отобразите текущую версию входных данных и: переверните каждый из них после удаления самого длинного префикса, содержащего только нули (удаление этого префикса выполняется с помощью функции Husk's ↓, которая обрезает самый длинный цикл последовательных элементов с начала список, который дает правдивые результаты при запуске через функцию, а именно ¬, логическое нет).

T0

Транспонировать, заменяя отсутствующие записи на 0 .

Мистер Xcoder
источник
2

Сетчатка , 87 байт

/.\[(?!0,)/^+`\[0, 
[
/(?<! 0)]./^+`, 0]
]
\[(\[0(, 0)*], )+
[
(, \[0(, 0)*])+]|\[0]]
]

Попробуйте онлайн! Объяснение:

/.\[(?!0,)/^+`

Пока хотя бы один ряд не начинается с нуля ...

\[0, 
[

... удалить ведущий ноль из каждого ряда.

/(?<! 0)]./^+`

Пока хотя бы один ряд не заканчивается нулем ...

, 0]
]

... удалить конечный ноль из каждой строки.

\[(\[0(, 0)*], )+
[

Удалить ведущие ряды нулей.

(, \[0(, 0)*])+]|\[0]]
]

Удалите конечные ряды нулей или последний оставшийся ноль.

Нил
источник
1
@RickHitchcock Формат чувствителен, добавьте пробелы: попробуйте онлайн!
Нил
2

Древесный уголь , 48 байтов

Ｆ⁴«Ｗ∧θ¬Σ§θ±¹Σ⊟θ¿θ≔⮌Ｅ§θ⁰Ｅ觧θνλθ»⪫[]⪫Ｅθ⪫[]⪫ι, ¦,

Попробуйте онлайн! Ссылка на подробную версию кода. Включает 15 байтов для форматирования. Объяснение:

Ｆ⁴«

Повторите 4 раза.

Ｗ∧θ¬Σ§θ±¹

Повторите, пока массив не пуст, но его последняя строка суммируется с нулем ...

Σ⊟θ

Удалите последнюю строку из массива и выведите строку длины его суммы, то есть ничего.

¿θ≔⮌Ｅ§θ⁰Ｅ觧θνλθ»

Если массив не пустой, транспонируйте его.

⪫[]⪫Ｅθ⪫[]⪫ι, ¦,

Отформатируйте массив для отображения. (Стандартный вывод будет Ｉθвместо этого.)

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

JavaScript, 144 140 129 127 байт

w=>(t=w=>(q=(s=w=>w.some((r,j)=>r.find(e=>e,i=j))?w.slice(i).reverse():[[]])(s(w)))[0].map((e,j)=>q.map((e,i)=>q[i][j])))(t(w))

140 -> 129 байт, спасибо @Arnauld

Алгоритм

  • Сделать дважды:
    • Найти первую ненулевую строку
    • Вырежьте предыдущие строки
    • Обратный
    • Найти первую ненулевую строку
    • Вырежьте предыдущие строки
    • Обратный
    • Транспонирование

f = w=>(t=w=>(q=(s=w=>w.some((r,j)=>r.find(e=>e,i=j))?w.slice(i).reverse():[[]])(s(w)))[0].map((e,j)=>q.map((e,i)=>q[i][j])))(t(w));

w1 = [[0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1], [0, 0, 1, 1, 1], [0, 0, 0, 0, 0]];
w2 = [[0, 0, 0, 0], [0, 0, 0, 3], [0, 0, 0, 0], [0, 5, 0, 0], [0, 0, 0, 0]];
w3 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
w4 = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]];

console.log(f(w1).join("\n"));
console.log(f(w2).join("\n"));
console.log(f(w3).join("\n"));
console.log(f(w4));
Развернуть фрагмент

Matth
источник
Вы можете сохранить 7 байтов , используя some/someвместо findIndex/findи переупорядочивая объявления вспомогательных функций, чтобы избавиться от круглых скобок вокруг (теперь единственного) аргумента основной функции.
Арно
Я думаю, что вы можете сохранить еще 4 байта , возвращая s,[[]] так что t гарантированно сможет работать w[0].
Арно
2

Python 2 , 118 116 байт

f=lambda a,n=4,s=sum:n and f(zip(*a[max(i for i in range(len(a))if s(s(a[:i],()))<1):][::-1]),n-1)or(s(s(a,()))>0)*a

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

Добавлено:

  • -2 байта, благодаря shooqie
TFeld
источник
1
Вы можете сохранить два байта, присваивая s=sumв лямбда-определении
shooqie
2

PHP (> = 5,4), 200 194 186 184 байта

(-6 байт, возвращая nullвместо пустого массива)

(-8 байт благодаря Титу )

(-2 байта с вызовом по ссылке благодаря Титу )

function R(&$a){$m=$n=1e9;foreach($a as$r=>$R)foreach($R as$c=>$C)if($C){$m>$r&&$m=$r;$M>$r||$M=$r;$n>$c&&$n=$c;$N>$c||$N=$c;}for(;$m<=$M;)$o[]=array_slice($a[$m++],$n,$N-$n+1);$a=$o;}

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

Как?

Находит минимальный и максимальный индекс для строк ( $m& $M) и столбцов ( $n& $N) и заменяет входные данные вложенным массивом из $m,$nto $M,$N(это вызов по ссылке).

night2
источник
Сохранить 6 байтов сif($C){$m>$r&&$m=$r;$M>$r||$M=$r;$n>$c&&$n=$c;$N>$c||$N=$c;}
Тит
... и два байта сwhile($m<=$M)$o[]=array_slice($a[$m++],$n,$N-$n+1);
Тит
@ Titus: Спасибо за отличные советы. Мне понравился трюк с использованием, &&и ||я уверен, что смогу использовать этот трюк и в других местах.
Night2
1
Вы можете сохранить еще два байта при вызове по ссылке: $a=вместо return.
Тит
2

Октава, 48 49 байт

@(a)sparse(1-min([x y v]=find(a))+x,1-min(y)+y,v)

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

Найдите ненулевые точки и переставьте их в новую разреженную матрицу.

rahnema1
источник
@alephalpha Ответ обновлен!
rahnema1
2

J , 24 байта

(|.@|:@}.~0=+/@{.)^:4^:_

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

объяснение

(|.@|:@}.~0=+/@{.)^:4^:_
            +/                sum
              @               of
               {.             the first row
          0=                  is zero? (1 = true, 0 = false)
       }.~                    chop off that many rows from the front
 |.@|:@                       rotate by 90 deg (transpose then reverse)
(                )^:4         repeat this process 4 times (rotating a total of 360 deg)
                     ^:_      fixpoint - repeat until no change
Конор О'Брайен
источник
2

Рубин , 73 63 байта

->a{4.times{_,*a=a while a[0]&.sum==0;a=a.reverse.transpose};a}

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

Редактировать: упрощено, также предыдущая версия рухнула для всех 0 х

Как это работает:

  • сделать 4 раза:
    • удалить первую строку, пока есть первая строка, и она полна 0 s
    • повернуть массив по часовой стрелке на 90 °
  • вернуть массив
Асоне Тухид
источник
Ссылка верна, но ваш ответ в блоке кода говорит &.sum<0вместо &.sum<1.
Конор О'Брайен
@ ConorO'Brien мой плохой, новая версия не работает для пустого массива (ноль <1). Спасибо, что все равно заметили
Asone Tuhid
1

Октава , 78 74 байта

function x=f(x)
for k=1:nnz(~x)*4,x=rot90(x);x=x(:,~~cumsum(any(x,1)));end

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

объяснение

Это поворачивает матрицу на 90градусы ( x=rot90(x)) достаточное количество раз ( for k=1:... end). Число поворотов кратно 4, поэтому конечная матрица имеет исходную ориентацию. В частности, число вращений 4умножается на количество нулей в матрице (nnz(~x)*4 ).

Для каждого поворота, если есть один или несколько столбцов слева, состоящих только из нулей, они удаляются (x=x(:,~~cumsum(any(x,1))) ).

То, что осталось от матрицы после этого процесса, выводится функцией ( function x=f(x)).

Луис Мендо
источник
1

PHP, 188 байт

function f(&$a){for($s=array_shift;!max($a[0]);)$s($a);for($p=array_pop;!max(end($a));)$p($a);for($w=array_walk;!max(($m=array_map)(reset,$a));)$w($a,$s);while(!max($m(end,$a)))$w($a,$p);}

звоните по ссылке.

сломать

// call by reference
function f(&$a)
{
    // while first row is all zeroes, remove it
    while(!max($a[0]))array_shift($a);
    // while last row is all zeroes, remove it
    while(!max(end($a)))array_pop($a);
    // while first column is all zeroes, remove it
    while(!max(array_map(reset,$a)))array_walk($a,array_shift);
    // while last column is all zeroes, remove it
    while(!max(array_map(end,$a)))array_walk($a,array_pop);
}
Titus
источник
1

Python 2 , 86 байт

lambda a,l=1:a if l>4else([a.pop()for b in a if sum(a[-1])<1],f(zip(*a[::-1]),l+1))[1]

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

Принимает список списков, возвращает список кортежей.

объяснение

Злоупотребляет чертовски из списка понимания. Это эквивалентный расширенный код:

def f(a,l=1):
    # after 4 rotations, the list is back in its original orientation, return
    if l > 4:
        return a
    else:
        # helper variable to store return values
        ret = []
        # "trim" all rows from "bottom" of list that only contain 0s
        # since we are always checking le that item in the list, don't need range(len(a))
        # since we are only removing at most one item per iteration, will never try to remove more than len(a) items
        # brackets surrounding generator force it to be consumed make a list, and therefore actually pop() list items
        ret.append([a.pop() for b in a if sum(a[-1]) < 1])
        # rotate the array, increase the number of rotations, and recursively call this function on the new array/counter
        ret.append(f(zip(*a[::-1]), l + 1)))
        # we only put both items in a list in order to stay in the one-line lambda format
        # discard the popped items and return the value from the recursive call
        return ret[1]
Triggernometry
источник
1

Japt -h , 23 11 байт

4Æ=sUb_dà z

Попытайся

объяснение

                :Implicit input of 2D-array U
4Æ              :Map the range [0,4)
   s            :  Slice U from
    Ub          :   The first index in U where
      _dà      :    Any element is truthy (not zero)
          z     :  Rotate 90 degrees
  =             :  Reassign to U for the next iteration
                :Implicitly output the last element
мохнатый
источник