Supprimer les zéros environnants d'un tableau 2D

40

Ceci est une version en 2 dimensions de cette question .

Étant donné un tableau / matrice à deux dimensions non vide ne contenant que des entiers non négatifs:

[0000000010000010011100000]

Affiche le tableau avec les zéros environnants supprimés, c’est-à-dire le plus grand sous-tableau contigu sans zéros:

[010001111]

Exemples:

[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
la source
3
@MattH Rien n'est difficile dans un langage non ésotérique. :)Juste difficile de faire court.
user202729
1
Pouvons-nous donner une sortie Falsey au lieu d’une matrice vide, pour le dernier cas de test?
dimanche - Réintégrer Monica
1
De plus, si la sortie peut être une matrice non carrée, veuillez ajouter un scénario de test pour cela.
dimanche - Réintégrer Monica
1
Un cas test qui a cassé ma soumission précédente: [[0, 0, 0, 0], [0, 0, 0, 0], [1, 1, 1, 1], [0, 0, 0, 0]](le résultat ayant une largeur / hauteur de 1)
Conor O'Brien
1
Hé, est-il possible d'ajouter le cas de test
[111112311111]
Beta Decay

Réponses:

39

Wolfram Language (Mathematica) , 42 octets

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

Essayez-le en ligne!

Les automates cellulaires sont en effet la réponse à la vie , à l'univers et à tout . 1

Comment?

CellularAutomatonaccepte un tableau d'entrée et une valeur d'arrière-plan facultative. Ainsi, {#,0}spécifie qu’une règle d’automate cellulaire doit être appliquée à l’entrée, en supposant que l’arrière-plan de 0s.

Une chose intéressante ici est que CellularAutomatonle résultat est découpé de sorte qu'aucune bordure de cellules d'arrière-plan ne soit présente (sinon, le résultat se situe sur un plan infini).

Le code applique la règle {Null, {}, {0, 0}}- appliquant la tête Nullau voisin de rayon 0 de chaque cellule (c'est-à-dire uniquement le centre: la cellule elle-même) - exactement l' 0heure. Le résultat est l'entrée d'origine, mais avec l'arrière-plan supprimé (c.-à- 0d. Le rognage autour de s).

1. Voir le décompte de ma réponse? ;)

JungHwan Min
la source
6
Abus incorporé gentil… bien Mathematica a un incorporé, juste pas exposé directement.
user202729
3
Aucune référence XKCD 505 ?
Esolanging Fruit
+1 pour les automates cellulaires et la réponse ultime.
Hautement radioactif le
14

JavaScript (ES6), 98 octets

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

Essayez-le en ligne!

Comment?

Pour surmonter le manque de zip intégré, nous définissons une fonction g () capable d’opérer sur les lignes ou les colonnes de la matrice d’entrée a [] , en fonction de la valeur du drapeau global z .

g () recherche l'index minimal m et l'index maximal M de lignes non vides (si z n'est pas défini) ou de colonnes non vides (si z est défini) et renvoie la tranche correspondantede la matrice elle-même ou d'une ligne donnée. de la matrice.

Résumer:

  • nous supprimons d’abord les lignes en appelant g () sur la matrice avec z non défini
  • nous supprimons ensuite les colonnes en appelant g () sur chaque ligne avec z défini, ce qui conduit à cette situation plutôt inhabituelle.map(z=g)

Commenté

(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
la source
2
C'est impressionnant.
Jack Hales
3
@Jek, Arnauld vit dans une toute autre dimension. Mais si vous êtes extrêmement chanceux, vous pouvez parfois trouver un truc qu'il a raté et poster une solution plus courte. Au cours de ce processus, vous développerez une compréhension très approfondie de JavaScript.
Rick Hitchcock le
4
@RickHitchcock Je ne suis pas très bon en reconnaissance de modèles de code et il me manque régulièrement beaucoup de choses, même si je les ai déjà vues auparavant. Dans cet exemple particulier, je me concentrais sur la possibilité de réutiliser g () et manquais une optimisation assez évidente de la mise à jour de m et M (-9 octets). Je suis tout à fait d'accord avec le fait que le code-golf est un excellent moyen (et amusant) d'en apprendre beaucoup sur les subtilités d'une langue.
Arnauld
7

Haskell , 62 61 octets

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

Essayez-le en ligne!

foldr(zipWith(:))ewith e=[]:eest légèrement plus courttranspose et snd.span(all(<1))supprime les listes de zéros en tête de liste. Comme transposesuivi par reversesur une liste 2D équivaut à une rotation de 90 °, le code f.f.f.fn’est que quatre fois l’ abandon des listes de zéros et la rotation .

Laikoni
la source
5

Brachylog , 24 22 20 19 octets

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

Essayez-le en ligne!

Affiche la matrice de résultats sous forme de tableau de tableaux ou false pour une sortie vide.

(Merci à @Fatalize pour avoir suggéré un prédicat en ligne et économisé 1 octet.)

Explication

Prédicat 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

Prédicat 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 - Rétablir Monica
la source
Écrire la première ligne prédicat est 1 octet plus courte: {s.h+>0∧.t+>0∧}\↰₁\ . (Ceci est vrai pour pratiquement toutes les réponses à Brachylog, les prédicats sur les nouvelles lignes ne sont réellement implémentés que si vous voulez écrire des choses plus lisibles).
Fataliser
@ Fatalize Merci, mis à jour (enfin!). Je n'ai jamais pensé à la façon dont la syntaxe de prédicat en ligne est à la fois une définition et une application de prédicat, plutôt cool.
dimanche
5

R , 96 100 97 octets

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

Essayez-le en ligne!

L' ~assistant prend un vecteur non négatif et renvoie un vecteur avec FALSEles "extérieurs" 0du vecteur et les TRUEpositifs et tous les "intérieurs" 0. Cette fonction est appliquée aux sommes des lignes et des colonnes de la matrice en entrée.

~et ! utiliser le traitement d'analyse des opérateurs par R.

Corrigé conformément au commentaire de @ DigEmAll, mais avec quelques octets renvoyés de @ J.Doe

ngm
la source
1
Je pense que vous devriez ajouter drop=Fcomme je l’ai fait, sinon ces 2 tests renverront un vecteur au lieu de ligne et colonne: Essayez-le en ligne!
digEmAll
97 octets avec drop=F. Encore moins d'une tonne!
J.Doe
5

R , 89 79 octets

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

Essayez-le en ligne!

Merci à @ngm pour le code des cas de test et à @ J.Doe pour avoir économisé 10 octets!

  • J'ai dû ajouter un drop=Fparamètre en raison du comportement par défaut de R en transformant une matrice ligne / colonne en vecteurs ...
digEmAll
la source
Je n'ai pas remarqué que mon code précédent a échoué le tout zéro cas ... maintenant il est fixé , malheureusement , avec beaucoup plus d' octets :(
digEmAll
1
J'aimerais pouvoir +2 ceci. Très bonne utilisation de fivenum.
JayCe
79 octets utilisant rangeet peaufinant l'indexation
J.Doe
1
@ J.Doe: gamme, bien sûr! bonne idée merci!
digEmAll
3

Python 2 , 71 octets

Retourne en modifiant l'entrée. Une liste devrait être passée en entrée.

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

Essayez-le en ligne!

Python 2 , 77 octets

Cela modifie également l'entrée, mais cela fonctionne ....

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

Essayez-le en ligne!

utilisateur202729
la source
3

Wolfram Language (Mathematica) , 66 octets

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

Essayez-le en ligne!

Fonctionne maintenant en remplissant le tableau avec des zéros (merci @JungHwanMin)!

Un second merci à @JungHwanMin pour avoir économisé 4 octets

Beta Decay
la source
2

Wolfram Language (Mathematica) , 48 octets

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

Essayez-le en ligne!

Le faire de manière normale.

utilisateur202729
la source
Malheureusement, \[Transpose]je ne peux pas travailler ici.
user202729
2

Coque , 11 octets

!5¡(T0mo↔↓¬

Essayez-le en ligne!

Je sens que certains octets pourraient être supprimés en raccourcissant la !5¡partie.

Comment ça marche

!5¡(

5th

mo↔↓¬

Carte sur la version actuelle de l'entrée et: inverser chaque, après avoir laissé tomber le plus long préfixe consiting de zéros uniquement (chute ce préfixe est effectué à l'aide Husk de ↓, qui est une fonction que les cultures le plus long terme d'éléments consécutifs depuis le début de la liste qui donne des résultats véridiques lorsqu’elle est exécutée dans une fonction, à savoir ¬, logique non).

T0

Transposer, en remplaçant les entrées manquantes par 0 .

M. Xcoder
la source
2

Rétine , 87 octets

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

Essayez-le en ligne! Explication:

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

Jusqu'à ce qu'au moins une ligne ne commence pas par zéro ...

\[0, 
[

... supprime le zéro de chaque ligne.

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

Jusqu'à ce qu'au moins une ligne ne se termine pas par zéro ...

, 0]
]

... supprimer le zéro final de chaque ligne.

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

Supprimer les premières lignes de zéros.

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

Supprimez les dernières lignes de zéros, ou le dernier zéro restant.

Neil
la source
1
@RickHitchcock Le format est sensible, ajoutez des espaces: essayez-le en ligne!
Neil
2

Charbon de bois , 48 octets

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

Essayez-le en ligne! Le lien est vers la version verbeuse du code. Inclut 15 octets pour le formatage. Explication:

Ｆ⁴«

Répétez 4 fois.

Ｗ∧θ¬Σ§θ±¹

Répétez l'opération tant que le tableau n'est pas vide mais que sa dernière ligne est égale à zéro ...

Σ⊟θ

Supprime la dernière ligne du tableau et affiche une ligne de la longueur de sa somme, c’est-à-dire rien.

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

Si le tableau n'est pas vide, transposez-le.

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

Formatez bien le tableau pour l'affichage. (La sortie standard serait à la Ｉθplace.)

Neil
la source
2

JavaScript, 144 140 129 127 octets

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 octets, merci @Arnauld

Algorithme

  • Faire deux fois:
    • Trouver la première ligne non nulle
    • Trancher les lignes précédentes
    • Sens inverse
    • Trouver la première ligne non nulle
    • Trancher les lignes précédentes
    • Sens inverse
    • Transposer

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));
Développer l'extrait

MattH
la source
Vous pouvez enregistrer 7 octets en utilisant au some/somelieu de findIndex/findet en réarrangeant les déclarations de fonctions d'aide pour se débarrasser de la parenthèse autour du principal argument de la fonction (maintenant unique).
Arnauld
Je pense que vous pouvez économiser de 4 octets de plus en ayant de retour de [[]]sorte que t est garanti de pouvoir opérer w[0].
Arnauld
2

Python 2 , 118 116 octets

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

Essayez-le en ligne!

Enregistré:

  • -2 octets, merci à shooqie
TFeld
la source
1
Vous pouvez économiser deux octets en attribuant une s=sumdéfinition lambda
shooqie
2

PHP (> = 5.4), 200 194 186 184 octets

(-6 octets en retournant à la nullplace d'un tableau vide)

(-8 octets grâce à Titus )

(-2 octets avec appel par référence grâce à 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;}

Essayez-le en ligne!

Comment?

Trouve les index min et max pour les lignes ( $m& $M) et les colonnes ( $n& $N) et remplace l'entrée par un sous-tableau de $m,$nto $M,$N(il s'agit d'un appel par référence).

Nuit2
la source
Économisez 6 octets avecif($C){$m>$r&&$m=$r;$M>$r||$M=$r;$n>$c&&$n=$c;$N>$c||$N=$c;}
Titus le
... et deux octets avecwhile($m<=$M)$o[]=array_slice($a[$m++],$n,$N-$n+1);
Titus
@ Titus: Merci pour les bons conseils. J'ai adoré le truc d'utilisation &&et ||je suis sûr que je pourrai utiliser ce truc ailleurs.
Night2
1
Vous pouvez enregistrer deux autres octets avec appel par référence: $a=au lieu de return.
Titus
2

Octave, 48 à 49 octets

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

Essayez-le en ligne!

Recherchez des points non nuls et réorganisez-les dans une nouvelle matrice fragmentée.

rahnema1
la source
@alephalpha Réponse mise à jour!
rahnema1
2

J , 24 octets

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

Essayez-le en ligne!

Explication

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

Ruby , 73 63 octets

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

Essayez-le en ligne!

Edit: simplifiée, également la version précédente est écrasé pour tous 0s

Comment ça marche:

  • faire 4 fois:
    • enlever la première ligne alors qu'il y a une première ligne et c'est plein de 0s
    • faire pivoter la matrice de 90 ° dans le sens des aiguilles d'une montre
  • retourner le tableau
Asone Tuhid
la source
Le lien est correct, mais votre réponse dans le bloc de code dit &.sum<0au lieu de &.sum<1.
Conor O'Brien
@ ConorO'Brien ma mauvaise nouvelle version ne fonctionnait pas pour un tableau vide (nil <1). Merci d'avoir remarqué quand même
Asone Tuhid
1

Octave , 78 74 octets

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

Essayez-le en ligne!

Explication

Cela fait pivoter la matrice de 90degrés ( x=rot90(x)) un nombre suffisant de fois ( for k=1:... end). Le nombre de rotations étant un multiple de 4, la matrice finale a l'orientation initiale. Plus précisément, le nombre de rotations est 4multiplié par le nombre de zéros dans la matrice ( nnz(~x)*4).

Pour chaque rotation, s'il existe à gauche une ou plusieurs colonnes composées uniquement de zéros, elles sont supprimées ( x=x(:,~~cumsum(any(x,1)))).

Ce qui reste de la matrice après ce processus est sorti par la fonction ( function x=f(x)).

Luis Mendo
la source
1

PHP, 188 octets

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

appeler par référence.

panne

// 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
la source
1

Python 2 , 86 octets

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]

Essayez-le en ligne!

Prend une liste de listes, retourne une liste de tuples.

Explication

Abuse au diable de la compréhension de la liste. C'est le code développé équivalent:

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]
Triggernométrie
la source
1

Japt -h , 23 11 octets

4Æ=sUb_dà z

L'essayer

Explication

                :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
Hirsute
la source