Remover zeros circundantes de uma matriz 2D

40

Esta é uma versão bidimensional desta pergunta .

Dada uma matriz / matriz bidimensional não vazia contendo apenas números inteiros não negativos:

[0000000010000010011100000]

Envie a matriz com os zeros circundantes removidos, ou seja, o maior sub-arranjo contíguo sem os zeros circundantes:

[010001111]

Exemplos:

[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 alefalpha
fonte
3
@ MatH Nada é difícil em uma linguagem não esotérica. :)Apenas difícil de abreviar.
User202729
11
Podemos dar uma saída falsey em vez de uma matriz vazia, para o último caso de teste?
sundar - Restabelece Monica
11
Além disso, se a saída puder ser uma matriz não quadrada, adicione um caso de teste para isso.
sundar - Restabelece Monica
11
Um caso de teste que quebrou minha submissão anteriormente: [[0, 0, 0, 0], [0, 0, 0, 0], [1, 1, 1, 1], [0, 0, 0, 0]](o resultado com uma largura / altura 1)
Conor O'Brien
11
Ei, é possível adicionar o caso de teste
[111112311111]
Decay Beta

Respostas:

39

Wolfram Language (Mathematica) , 42 bytes

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

Experimente online!

Autômatos celulares são realmente a resposta para a vida , o universo e tudo . 1

Quão?

CellularAutomatonaceita uma matriz de entrada e um valor de segundo plano opcional. Assim, {#,0}especifica que uma regra de autômato celular deve ser aplicada à entrada, assumindo um fundo de 0s.

Uma coisa interessante aqui é que CellularAutomatoncorta a saída para que nenhuma borda de células de fundo esteja presente (porque, caso contrário, a saída ficará em um plano infinito).

O código aplica a regra {Null, {}, {0, 0}}- aplicar a cabeça Nullao vizinho do raio 0 de cada célula (ou seja, apenas o centro: a própria célula) - exatamente as 0vezes. O resultado disso é a entrada original, mas com o fundo removido (ou seja, cortando os arredores 0).

1. Veja o número de bytes da minha resposta? ;)

JungHwan Min
fonte
6
Bom abuso interno ... bem, o Mathematica tem um built-in, mas não exposto diretamente.
user202729
3
Nenhuma referência ao XKCD 505 ?
Esolanging Fruit
+1 para autômatos celulares e a resposta definitiva.
HighlyRadioactive
14

JavaScript (ES6), 98 bytes

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

Experimente online!

Quão?

Para superar a falta de um zip embutido, definimos uma função g () capaz de operar nas linhas ou nas colunas da matriz de entrada a [] , dependendo do valor do sinalizador global z .

g () olha para o índice mínimo de m e de índice máximo M quer de linhas não-vazia (se z é indefinido) ou colunas não-vazia (se z é definida) e retorna o correspondente fatia de quer da própria matriz ou a uma determinada linha da matriz.

Para resumir:

  • primeiro removemos as linhas invocando g () na matriz com z indefinido
  • removemos as colunas invocando g () em cada linha com z definido, o que leva a isso bastante incomum.map(z=g)

Comentado

(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
fonte
2
Isso é impressionante.
21318 Jack Hales
3
@ Jek, Arnauld vive em uma dimensão totalmente diferente. Mas se você é extremamente sortudo, você pode encontrar ocasionalmente um truque que ele perdeu e postar uma solução mais curto. No processo, você desenvolverá uma compreensão muito profunda do JavaScript.
Rick Hitchcock
4
@ RickHitchcock Eu não sou tão bom em reconhecimento de padrões de código e regularmente sinto falta de muitas coisas, mesmo que já as tenha visto antes. Neste exemplo particular, foi focada na reutilização de g () e perdeu bastante óbvio uma optimização no caminho para actualização m e M (-9 bytes). Concordo plenamente que o código de golfe é uma ótima (e divertida) maneira de aprender muito sobre as sutilezas de um idioma.
Arnauld
7

Haskell , 62 61 bytes

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

Experimente online!

foldr(zipWith(:))ecom e=[]:eé um pouco mais curtotranspose e snd.span(all(<1))elimina as principais listas de zeros de uma lista de listas. Como transposeseguido reverseem uma lista 2D, é igual a uma rotação de 90 °, o código f.f.f.fé apenas quatro vezes menor que as listas principais de zeros e girar .

Laikoni
fonte
5

Brachylog , 24 22 20 19 bytes

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

Experimente online!

Produz a matriz de resultados como uma matriz de matrizes ou false para saída vazia.

(Agradecemos a @Fatalize por sugerir predicado em linha e economizar 1 byte.)

Explicação

Predicado 0 (Principal): 

{...}     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

Predicado 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 - Restabelecer Monica
fonte
Escrever a primeira linha predicado é 1 byte mais curto: {s.h+>0∧.t+>0∧}\↰₁\ . (isso é verdade para praticamente qualquer resposta Brachylog, os predicados em novas linhas são realmente implementados apenas se você quiser escrever coisas mais legíveis).
Fatalize
@Fatalize Obrigado, atualizado (finalmente!). Eu nunca pensei sobre como a sintaxe de predicado em linha é uma aplicação de definição e predicado, muito legal.
sundar - Restabelece Monica
5

R , 96 100 97 bytes

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

Experimente online!

O ~auxiliar pega um vetor não negativo e retorna um vetor com FALSEpara os "exteriores" 0s do vetor e TRUEpara positivos e quaisquer "interiores" 0. Esta função é aplicada às somas de linha e coluna da matriz de entrada.

~e ! use o tratamento do analisador de R dos operadores.

Corrigido de acordo com o comentário de @ DigEmAll, mas com alguns bytes retornados de @ J.Doe

ngm
fonte
11
Eu acho que você deve adicionar drop=Fcomo eu fiz, caso contrário, esses dois testes retornarão um vetor em vez de linha e coluna: Experimente online!
digEmAll
97 bytes com drop=F. Ainda sob uma tonelada!
J.Doe
5

R , 89 79 bytes

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

Experimente online!

Obrigado a @ngm pelo código de casos de teste e a @ J.Doe por salvar 10 bytes!

  • Eu tive que adicionar o drop=Fparâmetro devido ao comportamento padrão do R que transforma a matriz única linha / col em vetores ...
digEmAll
fonte
Eu não percebi que meu código anterior estava falhando as todas de zero casos ... agora ele é fixo, infelizmente, com muito mais bytes :(
digEmAll
11
Eu gostaria de poder +2 isso. Realmente bom uso de fivenum.
JayCe 01/08/19
79 bytes , utilizando rangee ajustando a indexação
J.Doe
11
@ J.Doe: alcance, é claro! ótima ideia obrigado!
precisa saber é o seguinte
3

Python 2 , 71 bytes

Retorna modificando a entrada. Uma lista deve ser passada como entrada.

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

Experimente online!

Python 2 , 77 bytes

Isso também modifica a entrada, mas funciona ....

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

Experimente online!

user202729
fonte
3

Wolfram Language (Mathematica) , 66 bytes

If[Max@#>0,ImageCrop@Image[#~ArrayPad~1,r="Real"]~ImageData~r,{}]&

Experimente online!

Agora funciona preenchendo a matriz com zeros (obrigado @JungHwanMin)!

Um segundo obrigado a @JungHwanMin por salvar 4 bytes

Beta Decay
fonte
2

Wolfram Language (Mathematica) , 48 bytes

Nest[Reverse@Thread@#//.{{0..},a___}->{a}&,#,4]&

Experimente online!

Fazendo da maneira normal.

user202729
fonte
Infelizmente \[Transpose]não pode trabalhar aqui.
user202729
2

Casca , 11 bytes

!5¡(T0mo↔↓¬

Experimente online!

Eu sinto que alguns bytes podem ser removidos encurtando a !5¡parte.

Como funciona

!5¡(

5th

mo↔↓¬

Mapeie a versão atual da entrada e: inverta cada uma, depois de ter eliminado o prefixo mais longo, consitando apenas zeros (a eliminação desse prefixo é realizada usando Husk's ↓, que é uma função que corta a execução mais longa de elementos consecutivos desde o início do lista que produz resultados verdadeiros quando executada em uma função, a saber ¬, não lógica).

T0

Transponha, substituindo as entradas ausentes por 0 .

Mr. Xcoder
fonte
2

Retina , 87 bytes

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

Experimente online! Explicação:

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

Até que pelo menos uma linha não comece com zero ...

\[0, 
[

... remova o zero inicial de cada linha.

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

Até que pelo menos uma linha não termine com zero ...

, 0]
]

... remova o zero à direita de cada linha.

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

Remova as linhas principais de zeros.

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

Remova as linhas finais de zeros ou o último zero restante.

Neil
fonte
11
@RickHitchcock É sensível ao formato, adicione espaços: Experimente on-line!
Neil
2

Carvão , 48 bytes

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

Experimente online! Link é a versão detalhada do código. Inclui 15 bytes para formatação. Explicação:

Ｆ⁴«

Repita 4 vezes.

Ｗ∧θ¬Σ§θ±¹

Repita enquanto a matriz não está vazia, mas sua última linha é igual a zero ...

Σ⊟θ

Remova a última linha da matriz e imprima uma linha do comprimento de sua soma, ou seja, nada.

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

Se a matriz não estiver vazia, transponha-a.

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

Formate a matriz bem para exibição. (Em Ｉθvez disso, seria a saída padrão .)

Neil
fonte
2

JavaScript, 144 140 129 127 bytes

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 bytes, obrigado @Arnauld

Algoritmo

  • Faça duas vezes:
    • Encontre a primeira linha diferente de zero
    • Cortar as linhas anteriores
    • Marcha ré
    • Encontre a primeira linha diferente de zero
    • Cortar as linhas anteriores
    • Marcha ré
    • Transpor

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));
Expandir snippet

MattH
fonte
Você pode salvar 7 bytes usando em some/somevez de findIndex/finde reorganizando as declarações da função auxiliar para se livrar dos parênteses em torno do argumento da função principal (agora único).
Arnauld
Eu acho que você pode salvar mais 4 bytes tendo retorno s[[]] para garantir que t seja capaz de operar w[0].
Arnauld
2

Python 2 , 118 116 bytes

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

Experimente online!

Salvou:

  • -2 bytes, graças a shooqie
TFeld
fonte
11
Você pode salvar dois bytes, atribuindo s=sumem lambda definição
shooqie
2

PHP (> = 5,4), 200 194 186 184 bytes

(-6 bytes retornando em nullvez de matriz vazia)

(-8 bytes graças a Titus )

(-2 bytes com chamada por referência, graças a Titus )

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;}

Experimente online!

Quão?

Localiza o índice mínimo e máximo para linhas ( $m& $M) e colunas ( $n& $N) e substitui a entrada por uma sub-matriz de $m,$npara $M,$N(esta é uma chamada por referência).

Night2
fonte
Salve 6 bytes comif($C){$m>$r&&$m=$r;$M>$r||$M=$r;$n>$c&&$n=$c;$N>$c||$N=$c;}
Titus
... e dois bytes comwhile($m<=$M)$o[]=array_slice($a[$m++],$n,$N-$n+1);
Titus
@ Titus: Obrigado pelas ótimas dicas. Adorei o truque de usar &&e ||tenho certeza de que também poderei usá-lo em outros lugares.
night2
11
Você pode salvar outros dois bytes chamando por referência: em $a=vez de return.
Titus
2

Oitava, 48 49 bytes

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

Experimente online!

Encontre pontos diferentes de zero e reorganize-os em uma nova matriz esparsa.

rahnema1
fonte
@alephalpha Resposta atualizada!
rahnema1
2

J , 24 bytes

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

Experimente online!

Explicação

(|.@|:@}.~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
Conor O'Brien
fonte
2

Ruby , 73 63 bytes

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

Experimente online!

Editar: simplificado, também a versão anterior caiu para todos os 0s

Como funciona:

  • faça 4 vezes:
    • remova a primeira linha enquanto houver uma primeira linha e estiver cheia de 0s
    • gire a matriz no sentido horário 90 °
  • retornar a matriz
Asone Tuhid
fonte
O link está correto, mas sua resposta no bloco de código diz em &.sum<0vez de &.sum<1.
Conor O'Brien
@ ConorO'Brien minha versão nova e ruim não funcionou para uma matriz vazia (nulo <1). Obrigado por perceber de qualquer maneira
Asone Tuhid
1

Oitava , 78 74 bytes

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

Experimente online!

Explicação

Isso gira a matriz em 90graus ( x=rot90(x)) um número suficiente de vezes ( for k=1:... end). O número de rotações é múltiplo de 4, portanto a matriz final tem a orientação original. Especificamente, o número de rotações é 4o número de zeros na matriz ( nnz(~x)*4).

Para cada rotação, se houver uma ou mais colunas à esquerda, consistindo apenas de zeros, elas serão removidas ( x=x(:,~~cumsum(any(x,1)))).

O que resta da matriz após esse processo é gerado pela função ( function x=f(x)).

Luis Mendo
fonte
1

PHP, 188 bytes

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);}

chamada por referência.

demolir

// 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
fonte
1

Python 2 , 86 bytes

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]

Experimente online!

Pega uma lista de listas, retorna uma lista de tuplas.

Explicação

Abusa a compreensão fora da lista. Este é o código expandido equivalente:

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]
Triggernometria
fonte
1

Japonês -h , 23 11 bytes

4Æ=sUb_dà z

Tente

Explicação

                :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
Shaggy
fonte