Eliminar ceros circundantes de una matriz 2d

40

Esta es una versión bidimensional de esta pregunta .

Dada una matriz / matriz bidimensional no vacía que contiene solo enteros no negativos:

[0 00 00 00 00 00 00 00 010 00 00 00 00 010 00 01110 00 00 00 00 0]

Salida de la matriz con ceros circundantes eliminados, es decir, el subconjunto contiguo más grande sin ceros circundantes:

[0 010 00 00 01111]

Ejemplos:

[0 00 00 00 00 00 00 00 010 00 00 00 00 010 00 01110 00 00 00 00 0]↦[0 010 00 00 01111]
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]]

[0 00 00 00 00 00 00 030 00 00 00 00 05 50 00 00 00 00 00 0]↦[0 00 030 00 00 05 50 00 0]
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]]

[1234 45 56 67 789]↦[1234 45 56 67 789]
Input:
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

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

[0 00 00 00 00 00 00 00 00 00 00 00 0]↦[]
Input:
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

Output:
[]

[0 00 00 00 011110 00 00 00 0]↦[1111]
Input:
[[0, 0, 0, 0], [1, 1, 1, 1], [0, 0, 0, 0]]

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

[0 010 00 00 010 00 00 010 00 0]↦[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
fuente
3
@MattH Nada es difícil en un lenguaje no esotérico. :)Simplemente difícil hacerlo corto.
usuario202729
1
¿Podemos dar una salida falsey en lugar de una matriz vacía, para el último caso de prueba?
sundar - Restablecer Monica
1
Además, si la salida puede ser una matriz no cuadrada, agregue un caso de prueba para eso.
sundar - Restablecer Monica
1
Un caso de prueba que rompió mi presentación anterior: [[0, 0, 0, 0], [0, 0, 0, 0], [1, 1, 1, 1], [0, 0, 0, 0]](el resultado tiene un ancho / alto de 1)
Conor O'Brien
1
Hola, ¿es posible agregar el caso de prueba
[111112311111]
Decadencia Beta

Respuestas:

39

Wolfram Language (Mathematica) , 42 bytes

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

Pruébalo en línea!

Los autómatas celulares son, de hecho, la respuesta a la vida , el universo y todo . 1

¿Cómo?

CellularAutomatonacepta una matriz de entrada y un valor de fondo opcional. Por lo tanto, {#,0}especifica que se debe aplicar una regla de autómata celular a la entrada, suponiendo un fondo de 0s.

Una cosa interesante aquí es que CellularAutomatonrecorta la salida para que no haya ningún borde de las celdas de fondo (porque de lo contrario la salida se encuentra en un plano infinito).

El código aplica la regla {Null, {}, {0, 0}}- aplicando la cabeza Nullal vecino de radio 0 de cada celda (es decir, solo el centro: la celda misma) - exactamente las 0veces. El resultado de esto es la entrada original, pero con el fondo eliminado (es decir, recortando los alrededores 0).

1. ¿Ves el recuento de mi respuesta? ;)

JungHwan Min
fuente
66
Buen abuso incorporado ... bueno, Mathematica tiene una función incorporada, pero no se expone directamente.
user202729
3
No hay referencia XKCD 505 ?
Esolanging Fruit
+1 para autómatas celulares y la respuesta definitiva.
HighRadioactive
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)

Pruébalo en línea!

¿Cómo?

Para superar la falta de un zip incorporado, definimos una función g () que puede operar en las filas o en las columnas de la matriz de entrada a [] , dependiendo del valor de la bandera global z .

g () busca el índice mínimo my el índicemáximo M de filas no vacías (si z no está definida) o columnas no vacías (sise define z ) y devuelve el corte correspondientede la matriz o de una fila dada de la matriz.

Para resumir:

  • primero eliminamos filas invocando g () en la matriz con z indefinido
  • luego eliminamos las columnas invocando g () en cada fila con z definida, lo que lleva a esto bastante inusual.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
fuente
2
Eso es impresionante.
Jack Hales
3
@Jek, Arnauld vive en una dimensión completamente diferente. Pero si tienes mucha suerte, de vez en cuando puedes encontrar un truco que se perdió y publicar una solución más corta. En el proceso, desarrollará una comprensión muy profunda de JavaScript.
Rick Hitchcock
44
@RickHitchcock No soy tan bueno en el reconocimiento de patrones de código y regularmente me faltan muchas cosas, incluso si las he visto antes. En este ejemplo particular, que estaba centrado en la reutilización de g () y se perdió toda una optimización evidente en la manera de actualizar m y M (-9 bytes). Estoy totalmente de acuerdo en que el golf de código es una forma excelente (y divertida) de aprender mucho sobre las sutilezas de un idioma.
Arnauld
7

Haskell , 62 61 bytes

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

Pruébalo en línea!

foldr(zipWith(:))ewith e=[]:ees un poco más cortotranspose y snd.span(all(<1))elimina las principales listas de ceros de una lista de listas. Como se transposesigue reverseen una lista 2D, es igual a una rotación de 90 °, el código f.f.f.fes solo cuatro veces soltar listas iniciales de ceros y rotar .

Laikoni
fuente
5

Brachylog , 24 22 20 19 bytes

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

Pruébalo en línea!

Emite la matriz de resultados como una matriz de matrices, o falso para salida vacía

(Gracias a @Fatalize por sugerir un predicado en línea y guardar 1 byte).

Explicación

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 - Restablecer a Monica
fuente
Escribir la primera línea de predicados es de 1 byte más corto: {s.h+>0∧.t+>0∧}\↰₁\ . (esto es cierto para casi cualquier respuesta de Brachylog, los predicados en nuevas líneas realmente solo se implementan si desea escribir cosas más legibles).
Fatalize
@Fatalize Gracias, actualizado (¡finalmente!). Nunca pensé en cómo la sintaxis de predicado en línea es tanto una definición como una aplicación de predicado, bastante genial.
sundar - Restablece a Mónica el
5

R , 96100 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)

Pruébalo en línea!

El ~ayudante toma un vector no negativo y devuelve un vector con FALSElos "exteriores" 0del vector y los TRUEpositivos y cualquier "interior" 0. Esta función se aplica a las sumas de fila y columna de la matriz de entrada.

~y ! usar el tratamiento analizador R de los operadores.

Corregido según el comentario de @ DigEmAll, pero con algunos bytes devueltos por @ J.Doe

ngm
fuente
1
Creo que debería agregar drop=Fcomo lo hice, de lo contrario, estas 2 pruebas devolverán un vector en lugar de una fila y una columna: ¡ Pruébelo en línea!
digEmAll
97 bytes con drop=F. Todavía menos de una 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]}

Pruébalo en línea!

¡Gracias a @ngm por el código de casos de prueba y a @ J.Doe por guardar 10 bytes!

  • Tuve que agregar drop=Fparámetros debido al comportamiento predeterminado de R que convierte la matriz de una sola fila / columna en vectores ...
digEmAll
fuente
No me di cuenta de que mi código anterior estaba fallando los casos de todo cero ... ahora, lamentablemente, se solucionó con muchos más bytes :(
digEmAll
1
Desearía poder hacer +2 en esto. Muy buen uso de fivenum.
JayCe
79 bytes usando rangey ajustando la indexación
J.Doe
1
@ J.Doe: rango, por supuesto! gran idea gracias!
digEmAll el
3

Python 2 , 71 bytes

Regresa modificando la entrada. Se debe pasar una lista como entrada.

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

Pruébalo en línea!

Python 2 , 77 bytes

Esto también modifica la entrada, pero funciona ...

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

Pruébalo en línea!

usuario202729
fuente
3

Wolfram Language (Mathematica) , 66 bytes

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

Pruébalo en línea!

¡Ahora funciona rellenando la matriz con ceros (gracias @JungHwanMin)!

Un segundo gracias a @JungHwanMin por guardar 4 bytes

Decaimiento Beta
fuente
2

Casco , 11 bytes

!5¡(T0mo↔↓¬

Pruébalo en línea!

Siento que algunos bytes podrían reducirse acortando la !5¡parte.

Cómo funciona

!5¡(

5 5th

mo↔↓¬

Mapee sobre la versión actual de la entrada y: invierta cada una, después de haber eliminado el prefijo más largo que consiste solo en ceros (la eliminación de este prefijo se realiza utilizando Husk's ↓, que es una función que recorta la ejecución más larga de elementos consecutivos desde el comienzo del lista que produce resultados verdaderos cuando se ejecuta a través de una función, es decir ¬, lógico no).

T0

Transponer, reemplazando las entradas que faltan con 0 .

Sr. Xcoder
fuente
2

Retina , 87 bytes

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

Pruébalo en línea! Explicación:

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

Hasta que al menos una fila no comience con cero ...

\[0, 
[

... elimine el cero inicial de cada fila.

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

Hasta que al menos una fila no termine con cero ...

, 0]
]

... elimine el cero final de cada fila.

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

Eliminar las primeras filas de ceros.

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

Elimine las filas finales de ceros, o el último cero restante.

Neil
fuente
1
@RickHitchcock Es sensible al formato, agregue espacios: ¡ Pruébelo en línea!
Neil
2

Carbón , 48 bytes

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

Pruébalo en línea! El enlace es a la versión detallada del código. Incluye 15 bytes para formatear. Explicación:

Ｆ⁴«

Repite 4 veces.

Ｗ∧θ¬Σ§θ±¹

Repita mientras la matriz no está vacía pero su última fila suma a cero ...

Σ⊟θ

Elimine la última fila de la matriz e imprima una línea de la longitud de su suma, es decir, nada.

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

Si la matriz no está vacía, transpórtala.

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

Formatee la matriz muy bien para su visualización. (La salida estándar sería en su Ｉθlugar).

Neil
fuente
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, gracias @Arnauld

Algoritmo

  • Haz dos veces:
    • Encuentra la primera fila que no sea cero
    • Cortar las filas anteriores
    • Marcha atrás
    • Encuentra la primera fila que no sea cero
    • Cortar las filas anteriores
    • Marcha atrás
    • Transponer

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 fragmento

MattH
fuente
Puede guardar 7 bytes utilizando en some/somelugar de findIndex/findy reorganizando las declaraciones de la función auxiliar para deshacerse del paréntesis en torno al argumento de la función principal (ahora único).
Arnauld
Yo creo que se puede ahorrar más de 4 bytes por tener s retorno [[]]de manera que t se garantiza que sea capaz de operar sobre w[0].
Arnauld
2

Python 2 , 118116 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

Pruébalo en línea!

Salvado:

  • -2 bytes, gracias a shooqie
TFeld
fuente
1
Puede guardar dos bytes asignando s=sumen definición lambda
shooqie
2

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

(-6 bytes devolviendo en nulllugar de matriz vacía)

(-8 bytes gracias a Titus )

(-2 bytes con llamadas por referencia gracias 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;}

Pruébalo en línea!

¿Cómo?

Encuentra el índice mínimo y máximo para las filas ( $m& $M) y las columnas ( $n& $N) y reemplaza la entrada con una matriz secundaria de $m,$na $M,$N(esta es una llamada por referencia).

Noche2
fuente
Ahorre 6 bytes conif($C){$m>$r&&$m=$r;$M>$r||$M=$r;$n>$c&&$n=$c;$N>$c||$N=$c;}
Titus
... y dos bytes conwhile($m<=$M)$o[]=array_slice($a[$m++],$n,$N-$n+1);
Titus
@Titus: Gracias por los buenos consejos. Me encantó el truco de usar &&y ||y estoy seguro de que también podré usar ese truco en otros lugares.
Noche2
1
Puede guardar otros dos bytes con llamada por referencia: en $a=lugar de return.
Titus
2

Octava, 48 49 bytes

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

Pruébalo en línea!

Encuentre puntos distintos de cero y reorganícelos en una nueva matriz dispersa.

rahnema1
fuente
@alephalpha ¡Respuesta actualizada!
rahnema1
2

J , 24 bytes

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

Pruébalo en línea!

Explicación

(|.@|:@}.~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
fuente
2

Ruby , 73 63 bytes

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

Pruébalo en línea!

Editar: simplificado, también la versión anterior se bloqueó para todos los 0s

Cómo funciona:

  • hacer 4 veces:
    • elimine la primera línea mientras haya una primera línea y esté llena de 0s
    • gire la matriz en sentido horario 90 °
  • devolver la matriz
Asone Tuhid
fuente
El enlace es correcto, pero su respuesta en el bloque de código dice en &.sum<0lugar de &.sum<1.
Conor O'Brien
@ ConorO'Brien, mi mala versión nueva no funcionó para una matriz vacía (nula <1). Gracias por notarlo de todos modos
Asone Tuhid
1

Octava , 78 74 bytes

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

Pruébalo en línea!

Explicación

Esto gira la matriz en 90grados ( x=rot90(x)) un número suficiente de veces ( for k=1:... end). El número de rotaciones es un múltiplo de 4, por lo que la matriz final tiene la orientación original. Específicamente, el número de rotaciones es 4multiplicado por el número de ceros en la matriz ( nnz(~x)*4).

Para cada rotación, si hay una o más columnas a la izquierda que consisten solo en ceros, se eliminan ( x=x(:,~~cumsum(any(x,1)))).

Lo que queda de la matriz después de este proceso es generado por la función ( function x=f(x)).

Luis Mendo
fuente
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);}

llame por referencia.

Descompostura

// 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
fuente
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]

Pruébalo en línea!

Toma una lista de listas, devuelve una lista de tuplas.

Explicación

Abusa de la comprensión fuera de la lista. Este es el 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]
Triggernometry
fuente
1

Japt -h , 23 11 bytes

4Æ=sUb_dà z

Intentalo

Explicación

                :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
Lanudo
fuente