Usuń otaczające zera z tablicy 2d


40

To jest dwuwymiarowa wersja tego pytania .

Biorąc pod uwagę niepustą 2-wymiarową tablicę / macierz zawierającą tylko nieujemne liczby całkowite:

[0000000010000010011100000]

Wyprowadza tablicę z usuniętymi otaczającymi zerami, tj. Największą ciągłą podtablicę bez otaczających zer:

[010001111]

Przykłady:

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

[00000003)000005000000][003)000500]
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]]

[12)3)456789][12)3)456789]
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]]

[111112)3)11111][111112)3)11111]
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]]

3
@MattH W języku nie-ezoterycznym nic nie jest trudne. :)Po prostu trudno to streścić.
user202729

1
Czy możemy podać wynik falsey zamiast pustej matrycy dla ostatniego przypadku testowego?
Sundar - Przywróć Monikę

1
Ponadto, jeśli dane wyjściowe mogą być macierzą nie kwadratową, dodaj do tego przypadek testowy.
sundar - Przywróć Monikę

1
Przypadek testowy, który złamał moje wcześniejsze zgłoszenie: [[0, 0, 0, 0], [0, 0, 0, 0], [1, 1, 1, 1], [0, 0, 0, 0]](wynik ma szerokość / wysokość 1)
Conor O'Brien

1
Hej, czy można dodać przypadek testowy
[111112)3)11111]
Rozpad Beta

Odpowiedzi:



39

Wolfram Language (Mathematica) , 42 bajty

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

Wypróbuj online!

Automaty komórkowe są rzeczywiście odpowiedzią na życie , wszechświat i wszystko . 1

W jaki sposób?

CellularAutomatonakceptuje tablicę wejściową i opcjonalną wartość tła. {#,0}Określa zatem, że do danych wejściowych należy zastosować regułę automatu komórkowego, przyjmując tło0 s.

Przyjemne jest to, że CellularAutomatonprzycina dane wyjściowe, tak że nie ma granicy komórek tła (ponieważ w przeciwnym razie dane wyjściowe leżą na nieskończonej płaszczyźnie).

Kod stosuje zasadę {Null, {}, {0, 0}}- nakładanie głowy Nullna sąsiada 0-promienia każdej komórki (tj. Tylko środek: sama komórka) - dokładnie 0razy. Wynikiem tego jest oryginalne wejście, ale z usuniętym tłem (tj. Wykadrowanie otaczających 0s).


1. Zobacz bajt mojej odpowiedzi? ;)


6
Ładne wbudowane nadużycie ... cóż, Mathematica ma wbudowane, po prostu nie narażone bezpośrednio.
user202729,

3
Brak odniesienia do XKCD 505 ?
Esolanging Fruit

+1 za Automaty komórkowe i ostateczną odpowiedź.
HighlyRadioactive

14

JavaScript (ES6), 98 bajtów

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

Wypróbuj online!

W jaki sposób?

Aby przezwyciężyć brak wbudowanego zip , definiujemy funkcję g (), która może działać na wierszach lub kolumnach macierzy wejściowej a [] , w zależności od wartości flagi globalnej z .

g () szuka indeksu minimalna m i wskaźnik maksymalnej M z albo bez pustych rzędów (jeśli z jest nieokreślony) lub nie są puste kolumny (jeśli z jest określona) i zwraca odpowiedni plaster samego albo w osnowie albo w danym rzędzie matrycy.

Podsumowując:

  • najpierw usuwamy wiersze, wywołując g () na macierzy z niezdefiniowanym z
  • następnie usuwamy kolumny, wywołując g () w każdym wierszu ze zdefiniowanym z , co prowadzi do tego raczej niezwykłego.map(z=g)

Skomentował

(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

2
To imponujące.
Jack Hales,

3
@Jek, Arnauld żyje w zupełnie innym wymiarze. Ale jeśli jesteś bardzo szczęśliwy, można czasami znaleźć trick że tęsknił i zakładać krótszy rozwiązanie. W ten sposób rozwiniesz bardzo głębokie zrozumienie JavaScript.
Rick Hitchcock,

4
@ RickHitchcock Nie jestem zbyt dobry w rozpoznawaniu wzorców kodów i regularnie brakuje mi wielu rzeczy, nawet jeśli widziałem je wcześniej. W tym konkretnym przykładzie skupiłem się na możliwości ponownego użycia g () i przegapiłem dość oczywistą optymalizację na drodze do aktualizacji m i M (-9 bajtów). W pełni zgadzam się, że golf-code to świetny (i zabawny) sposób, aby dowiedzieć się wiele o subtelnościach języka.
Arnauld

7

Haskell , 62 61 bajtów

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

Wypróbuj online!

foldr(zipWith(:))ez e=[]:ejest nieco krótszytranspose i snd.span(all(<1))usuwa wiodące listy zer z listy. Jak transposenastępuje reversena liście 2D równa się obrotowi o 90 °, kod f.f.f.fjest tylko cztery razy upuszczając wiodące listy zer i obraca się .




5

Brachylog , 24 22 20 19 bajtów

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

Wypróbuj online!

Zwraca macierz wyników jako tablicę tablic lub fałsz dla pustych danych wyjściowych.

(Dzięki @Fatalize za sugerowanie wbudowanego predykatu i oszczędność 1 bajtu.)

Wyjaśnienie

Predykat 0 (główny):

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

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

Pisząc pierwszy źródłowe inline jest 1 bajt krócej: {s.h+>0∧.t+>0∧}\↰₁\ . (dotyczy to praktycznie każdej odpowiedzi Brachylog, predykaty dotyczące nowych linii są tak naprawdę realizowane tylko wtedy, gdy chcesz pisać bardziej czytelne rzeczy).
Fatalize

@Fatalize Thanks, zaktualizowane (w końcu!). Nigdy nie myślałem o tym, jak wbudowana predykatowa składnia jest zarówno definicją, jak i predykatową aplikacją, całkiem fajnie.
Sundar - Przywróć Monikę

5

R , 96 100 97 bajtów

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

Wypróbuj online!

~Pomocnik trwa nieujemną wektor i zwraca wektor zFALSE na „zewnętrzny” 0s wektora i TRUEna pozytywy i wszelkich „wnętrza” 0s. Ta funkcja jest stosowana do sum wierszy i kolumn macierzy wejściowej.

~i ! zastosuj traktowanie parsera R. operatorów.

Poprawiono zgodnie z komentarzem @ DigEmAll, ale niektóre bajty odtworzono z powrotem z @ J.Doe


1
Myślę, że powinieneś dodać drop=Ftak jak ja, w przeciwnym razie te 2 testy zwrócą wektor zamiast wiersza i kolumny: Wypróbuj online!
digEmAll

97 bajtów z drop=F. Nadal poniżej tony!
J.Doe

5

R , 89 79 bajtów

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

Wypróbuj online!

Dzięki @ngm za kod przypadków testowych i @ J.Doe za zapisanie 10 bajtów!

  • Musiałem dodać drop=Fparametr ze względu na domyślne zachowanie R przekształcające macierz pojedynczego wiersza / kolumny w wektory ...

Nie zauważyłem, że mój poprzedni kod
zawodził

1
Chciałbym móc to +2. Naprawdę fajne wykorzystanie fivenum.
JayCe,

79 bajtów przy użyciu rangei ulepszaniu indeksacji
J.Doe

1
@ J.Doe: oczywiście, zasięg! świetny pomysł dzięki!
digEmAll


3

Python 2 , 71 bajtów

Zwraca przez modyfikację wejścia. Lista powinna zostać przekazana jako dane wejściowe.

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

Wypróbuj online!


Python 2 , 77 bajtów

To również modyfikuje dane wejściowe, ale działa ....

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

Wypróbuj online!





2

Łuska , 11 bajtów

!5¡(T0mo↔↓¬

Wypróbuj online!

Wydaje mi się, że niektóre bajty mogłyby zostać wygolone przez skrócenie !5¡części.

Jak to działa

!5¡(

5th

mo↔↓¬

Zamapuj bieżącą wersję danych wejściowych i: odwróć każdą z nich, po upuszczeniu najdłuższego prefiksu składającego się wyłącznie z zer (upuszczenie tego prefiksu odbywa się za pomocą Husky , która jest funkcją, która przycina najdłuższy ciąg kolejnych elementów od początku lista, która daje prawdziwe wyniki po przejściu przez funkcję, a mianowicie ¬logiczna nie).

T0

Transponuj, zastępując brakujące wpisy wartością 0 .


2

Siatkówka , 87 bajtów

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

Wypróbuj online! Wyjaśnienie:

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

Dopóki co najmniej jeden wiersz nie zaczyna się od zera ...

\[0, 
[

... usuń wiodące zero z każdego wiersza.

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

Dopóki co najmniej jeden wiersz nie kończy się na zero ...

, 0]
]

... usuń końcowe zero z każdego wiersza.

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

Usuń wiodące wiersze zer.

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

Usuń końcowe rzędy zer lub ostatnie pozostałe zero.


1
@ RickHitchcock Jest wrażliwy na format, dodaj spacje: Wypróbuj online!
Neil

2

Węgiel drzewny , 48 bajtów

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

Wypróbuj online! Link jest do pełnej wersji kodu. Zawiera 15 bajtów do formatowania. Wyjaśnienie:

F⁴«

Powtórz 4 razy.

W∧θ¬Σ§θ±¹

Powtarzaj, gdy tablica nie jest pusta, ale jej ostatni wiersz sumuje się do zera ...

Σ⊟θ

Usuń ostatni wiersz z tablicy i wypisz wiersz o długości jego sumy, tzn. Nic.

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

Jeśli tablica nie jest pusta, transponuj ją.

⪫[]⪫Eθ⪫[]⪫ι, ¦, 

Ładnie sformatuj tablicę do wyświetlenia. ( IθZamiast tego byłoby wyjście standardowe .)


2

JavaScript, 144 140 129 127 bajtów

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 bajtów, dzięki @Arnauld

Algorytm

  • Zrób dwa razy:
    • Znajdź pierwszy niezerowy wiersz
    • Wytnij poprzednie rzędy
    • Rewers
    • Znajdź pierwszy niezerowy wiersz
    • Wytnij poprzednie rzędy
    • Rewers
    • Transponować

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


Możesz zapisać 7 bajtów , używając some/somezamiast findIndex/findi przestawiając deklaracje funkcji pomocnika, aby pozbyć się nawiasu wokół (obecnie pojedynczego) argumentu funkcji głównej.
Arnauld

Myślę , że możesz zaoszczędzić 4 bajty , zwracając s,[[]] aby zagwarantować, że t będzie w stanie działać w[0].
Arnauld

2

Python 2 , 118 116 bajtów

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

Wypróbuj online!


Zapisano:

  • -2 bajty, dzięki shooqie

1
Możesz zapisać dwa bajty, przypisując s=sumw definicji lambda
shooqie

2

PHP (> = 5,4), 200 194 186 184 bajtów

(-6 bajtów, zwracając nullzamiast pustej tablicy)

(-8 bajtów dzięki Tytusowi )

(-2 bajty z wywołaniem przez odniesienie dzięki Tytusowi )

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

Wypróbuj online!

W jaki sposób?

Znajduje indeks minimalny i maksymalny dla wierszy ( $m& $M) i kolumn ( $n& $N) i zastępuje dane wejściowe tablicą podrzędną od $m,$ndo $M,$N(jest to wywołanie przez odniesienie).


Zaoszczędź 6 bajtów zif($C){$m>$r&&$m=$r;$M>$r||$M=$r;$n>$c&&$n=$c;$N>$c||$N=$c;}
Tytus

... i dwa bajty zwhile($m<=$M)$o[]=array_slice($a[$m++],$n,$N-$n+1);
Tytusem

@Titus: Dzięki za wspaniałe wskazówki. Ładna sztuczka wykorzystania &&i ||I jestem pewien, że będę mógł wykorzystać tę sztuczkę w innych miejscach.
Night2

1
Możesz zapisać kolejne dwa bajty z wywołaniem przez odniesienie: $a=zamiast return.
Tytus

2

Oktawa, 48 49 bajtów

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

Wypróbuj online!

Znajdź niezerowe punkty i uporządkuj je w nowej rzadkiej macierzy.


@alephalpha Odpowiedź zaktualizowana!
rahnema1


2

J , 24 bajty

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

Wypróbuj online!

Wyjaśnienie

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

Ruby , 73 63 bajty

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

Wypróbuj online!

Edycja: uproszczona, także poprzednia wersja uległa awarii dla wszystkich 0s

Jak to działa:

  • zrobić 4 razy:
    • usuń pierwszą linię, gdy jest pierwsza linia i jest pełna 0s
    • obróć tablicę zgodnie z ruchem wskazówek zegara o 90 °
  • zwraca tablicę

Link jest poprawny, ale twoja odpowiedź w bloku kodu mówi &.sum<0zamiast &.sum<1.
Conor O'Brien

@ ConorO'Brien moja zła, nowa wersja nie działała dla pustej tablicy (zero <1). Dzięki za
zgłoszenie

1

Oktawa , 78 74 bajtów

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

Wypróbuj online!

Wyjaśnienie

Spowoduje to obrócenie macierzy o 90stopnie ( x=rot90(x)) wystarczającą liczbę razy ( for k=1:... end). Liczba obrotów jest wielokrotnością 4, więc końcowa matryca ma pierwotną orientację. W szczególności liczba obrotów jest 4pomnożona przez liczbę zer w macierzy ( nnz(~x)*4).

W przypadku każdego obrotu, jeśli po lewej stronie znajduje się jedna lub więcej kolumn zawierających tylko zera, są one usuwane (x=x(:,~~cumsum(any(x,1))) ).

Pozostała część macierzy po tym procesie jest wyprowadzana przez funkcję ( function x=f(x)).



1

PHP, 188 bajtów

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

zadzwoń przez odniesienie.

awaria

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


1

Python 2 , 86 bajtów

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]

Wypróbuj online!

Pobiera listę list, zwraca listę krotek.

Wyjaśnienie

Nadużywa cholernego zrozumienia listy. To jest równoważny rozwinięty kod:

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]

1

Japt -h , 23 11 bajtów

4Æ=sUb_dà z

Spróbuj


Wyjaśnienie

                :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
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.