Matrycy przemiennego znak jest nw nmatrycy składającej się z liczb 1, 0, 1, takie, że:

• Suma każdego wiersza i kolumny to 1
• Niezerowe wpisy w każdym wierszu i kolumnie występują naprzemiennie w znaku

Macierze te uogólniają macierze permutacyjne, a liczba takich macierzy dla danego nbyła przez pewien czas przedmiotem zainteresowania. Występują one naturalnie podczas kondensacyjnej metody obliczania macierzy (kondensatora Dodgsona) (nazwanej na cześć Charlesa Dodgsona, lepiej znanego jako Lewis Carroll).

Oto kilka przykładów macierzy naprzemiennych 4 na 4:

 0  1  0  0          1  0  0  0          0  0  1  0          0  0  1  0    
 0  0  1  0          0  0  1  0          0  1 -1  1          1  0 -1  1
 1  0  0  0          0  1 -1  1          1 -1  1  0          0  1  0  0
 0  0  0  1          0  0  1  0          0  1  0  0          0  0  1  0

A oto kilka przykładów macierzy 4 na 4, które nie są naprzemiennymi macierzami znaków:

 0  1  0  0
 0  0  0  1
 1  0  0  0
 0  0  1 -1    (last row and last column don't add to 1)

 0  0  0  1
 1  0  0  0
-1  1  1  0
 1  0  0  0    (third row does not alternate correctly)

Twój program lub funkcja będzie podawany był nprzez nmatrycę ( n >= 1) z -1s, 0 i 1 - wyprowadzenia wartości truthy jeśli dana macierz jest macierzą zmienny znak, inaczej wyjście A wartość falsy.

To jest golf golfowy , więc celem jest zminimalizowanie liczby używanych bajtów.

Przypadki testowe

Poniższe przypadki testowe podano w formacie listy 2D w stylu Pythona.

Prawda:

[[1]]
[[1,0],[0,1]]
[[0,1],[1,0]]
[[0,1,0],[0,0,1],[1,0,0]]
[[0,1,0],[1,-1,1],[0,1,0]]
[[0,1,0,0],[0,0,1,0],[1,0,0,0],[0,0,0,1]]
[[1,0,0,0],[0,0,1,0],[0,1,-1,1],[0,0,1,0]]
[[0,0,1,0],[0,1,-1,1],[1,-1,1,0],[0,1,0,0]]
[[0,0,1,0],[1,0,-1,1],[0,1,0,0],[0,0,1,0]]
[[0,0,1,0,0],[0,1,-1,1,0],[1,-1,1,0,0],[0,1,0,-1,1],[0,0,0,1,0]]
[[0,0,1,0,0,0,0,0],[1,0,-1,0,1,0,0,0],[0,0,0,1,-1,0,0,1],[0,0,1,-1,1,0,0,0],[0,0,0,0,0,0,1,0],[0,0,0,0,0,1,0,0],[0,1,-1,1,0,0,0,0],[0,0,1,0,0,0,0,0]]
[[0,0,0,0,1,0,0,0],[0,0,1,0,-1,1,0,0],[0,0,0,1,0,0,0,0],[1,0,0,-1,1,-1,1,0],[0,1,-1,1,-1,1,0,0],[0,0,0,0,1,0,0,0],[0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1]]

Falsy:

[[0]]
[[-1]]
[[1,0],[0,0]]
[[0,0],[0,1]]
[[-1,1],[1,0]]
[[0,1],[1,-1]]
[[0,0,0],[0,0,0],[0,0,0]]
[[0,1,0],[1,0,1],[0,1,0]]
[[-1,1,1],[1,-1,1],[1,1,-1]]
[[0,0,1],[1,0,0],[0,1,-1]]
[[0,1,0,0],[0,0,0,1],[1,0,0,0],[0,0,1,-1]]
[[0,0,1,0],[0,0,1,0],[1,0,-1,1],[0,1,0,0]]
[[0,0,0,1],[1,0,0,0],[-1,1,1,0],[1,0,0,0]]
[[1,0,1,0,-1],[0,1,0,0,0],[0,0,0,0,1],[0,0,0,1,0],[0,0,0,0,1]]
[[0,0,1,0,0],[0,1,-1,1,0],[1,-1,1,0,0],[0,1,1,-1,0],[0,0,-1,1,1]]
[[0,-1,0,1,1],[1,-1,1,-1,1],[0,1,1,0,-1],[1,1,-1,1,-1],[-1,1,0,0,1]]
[[0,0,1,0,0,0,0,0],[1,0,1,0,1,0,0,0],[0,0,0,1,-1,0,0,1],[0,0,1,-1,1,0,0,0],[0,0,0,0,0,0,1,0],[0,0,0,0,0,1,0,0],[0,1,-1,1,0,0,0,0],[0,0,1,0,0,0,0,0]]

Siatkówka , 62 58 56 53 bajtów

Liczba bajtów zakłada kodowanie ISO 8859-1 i \tnależy je zastąpić rzeczywistymi tabulatorami (0x09, które w przeciwnym razie byłyby zamienione na spacje przez SE).

$
\t$`¶
O$#`...(?<=^[^\t]*(.+))
$.1
T` 0
^(1(-11)*\s)+$

Format wejściowy to macierz, w której każda kolumna używa trzech znaków wyrównanych do prawej, np .:

  0  0  1  0
  1  0 -1  1
  0  1  0  0
  0  0  1  0

Dane wyjściowe to 0(fałsz) lub 1(prawda).

Zestaw testowy. (Kilka pierwszych wierszy przekształca format wejściowy i pozwala Retinie na uruchomienie kilku przypadków testowych jednocześnie.)

Wyjaśnienie

Na szczęście dane wejściowe są matrycą kwadratową: transpozycja kwadratów jest prawie wykonalna w siatkówce, podczas gdy transpozycja prostokątów jest ogromnym bólem.

$
\t$`¶

Zaczynamy od dodania tabulacji, całego wejścia ponownie (przy użyciu prefiksu $`), a następnie zakończenia linii na końcu (przy użyciu aliasu Retina ¶). Używamy tabulatorów, aby oddzielić dwie kopie, abyśmy mogli rozróżnić je podczas transpozycji jednego z nich, a używając znaku spacji, możemy później zapisać kilka bajtów.

O$#`...(?<=^[^\t]*(.+))
$.1

To jest najtrudniejszy bit: transpozycja pierwszej kopii matrycy. Chodzi o to, aby dopasować komórki w pierwszej kopii, a następnie posortować je (stabilnie) według pozycji poziomej. Dopasowujemy komórki do ...(ponieważ mają one zawsze trzy znaki szerokości), a następnie mierzymy pozycję poziomą za pomocą (.+)środka spojrzenia. Następnie, aby upewnić się, że transponujemy tylko pierwszą kopię, sprawdzamy, czy możemy dotrzeć do początku ciągu bez przechodzenia obok karty.

Możesz zauważyć, że dopasuje to również niektóre trzy bajtowe ciągi (które nawet nie wyrównują się z komórkami) w pierwszym rzędzie drugiej kopii, ponieważ .+mogą przechodzić przez kartę. Nie stanowi to jednak problemu, ponieważ pozioma pozycja tych dopasowań jest ściśle większa niż jakakolwiek wewnątrz pierwszej kopii, więc dopasowania te pozostają na swoim miejscu.

Reszta jest dość prosta:

T` 0

Usuwamy spacje i zera z danych wejściowych.

^(1(-11)*\s)+$

I na koniec sprawdzamy, czy całe dane wejściowe składają się z zakończonych białymi wierszami formularza 1(-11)*, tj. Naprzemiennej sekwencji 1i -1zaczynającej się i kończącej na 1(bo inaczej nie sumuje się 1).

Galaretka, 15 bajtów

;Zḟ€0;€-;@€-IFP

Wypróbuj online!

;Zḟ€0;€-;@€-IFP   Main monadic chain. Argument: z

;Z                Concatenate with its transpose.
  ḟ€0             Remove zeros from each sub-list. At this point,
                  one expects lists of the form [1, -1, 1, -1, ..., 1] for truthy,
                  and any other arrays containing purely 1 and -1 for falsey.
     ;€-          Append -1 to each sub-list.
        ;€@-      Prepend -1 to each sub-list.
            I     Compute the difference between each term. At this point,
                  for truthy, one expects arrays filled with 2, and arrays
                  containing 0 otherwise.
             FP   Product of every item. This checks if any item is equal to zero.

Pyth, 16 bajtów

!sm-sM._+d_1U2+C

Wypróbuj online: pakiet demonstracyjny lub testowy

Wyjaśnienie:

!sm-sM._+d_1U2+CQQ   two implicit Qs (=input matrix) at the end
              +CQQ   zip Q and connect it with Q (=list of columns and rows)
  m                  map each column/row d to:
        +d_1            append -1 to d
      ._                compute all prefixes of ^
    sM                  compute the sums of the prefixes
   -        U2          remove zeros and ones
                        a column/row is correct, if this gives an empty list 
 s                   connect up all resulting lists
!                    check, if this result is empty

Galaretka , 11 bajtów

;Zj-+\ṚQḄ=2

Zwraca 1 dla naprzemiennych macierzy znaków, w przeciwnym razie 0 . Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

tło

Bez względu na zera, każdy wiersz i kolumna musi składać się ze wzoru (1, -1) * 1 , tzn. Naprzemiennie występujących 1 i -1 , rozpoczynających się i kończących na 1 (więc suma wynosi 1 ).

Aby to sprawdzić, bierzemy tablicę wszystkich wierszy i kolumn i łączymy je za pomocą -1 jako separatora. Ponieważ wszystkie punkty końcowe mają wartość 1 , wynikowa płaska tablica spełnia wzór (1, -1) * 1 wtedy i tylko wtedy, gdy spełniają to wiersze i kolumny.

Dla rzeczywistego testu obliczamy skumulowaną sumę tablicy. Na matrycy znak przemiennego wynikiem będzie tablica 0 „S 1 ” S, która kończy się 1 .

Odwracamy sumę skumulowaną i deduplikujemy ją, zachowując kolejność początkowych wystąpień wszystkich unikalnych elementów. W przypadku prawdziwych danych wejściowych wynikiem będzie lista [1, 0] .

Aby wyprowadzić odpowiedni Boolean, konwertujemy zduplikowane sumy skumulowane z wartości binarnych na liczby całkowite i sprawdzamy, czy wynikiem jest 2 .

Jak to działa

;Zj-+\ṚQḄ=2  Main link. Argument: M (matrix / 2D array)

 Z           Zip; transpose M's rows and columns.
;            Concatenate M and zipped M.
  j-         Join, separating by -1.
    +\       Take the cumulative sum of the result.
      Ṛ      Reverse the array of partial sums.
       Q     Unique; deduplicate the partial sums.
        Ḅ    Unbinary; convert from base 2 to integer.
         =2  Test for equality with 2.

MATL, 18 16 15 13 bajtów

3 bajty zapisane dzięki @Luis

t!h"@s1=@Xzdv

To rozwiązanie przyjmuje tablicę 2D jako dane wejściowe i wyświetla tablicę prawdy lub falseya . Należy zauważyć, że w MATL tablica prawdy składa się ze wszystkich niezerowych elementów, podczas gdy wynik falsey ma co najmniej jeden element zerowy. Oto kolejna demonstracja tablic true / falsey .

Wypróbuj online

Zmodyfikowana wersja, aby pokazać wszystkie przypadki testowe

Wyjaśnienie

        % Implicitly grab input matrix
t!      % Duplicate and transpose input
h       % Horizontally concatenate input with transpose. This allows us to 
        % process only columns since now the columns *also* contain the rows.
"       % For each column (of our column/row combined matrix)
  @s1=  % Compute the sum and ensure it is equal to 1
  @Xz   % Get the non-zeros
  d     % Compute the element-to-element difference. The 1 and -1 alternate only if
        % all these differences are non-zero
  v     % Vertically concatenate everything on the stack
        % Implicit end of loop and implicitly display truthy/falsey value

Julia, 36 bajtów

!x=[x^0 x^0;-x -x'][:]|>cumsum⊆0:1

Wypróbuj online!

JavaScript (ES6), 112 100 bajtów

a=>!/(^|,)(?!0*10*(-10*10*)*(,|$))/.test(a.map(b=>b.join``)+','+a.map((_,i)=>a.map(b=>b[i]).join``))

Spłaszcza tablicę i jej transpozycję do ciągów, a następnie (ignorując 0s) sprawdza wzorzec 1-11...1-11w każdym ciągu.

Edycja: Zapisano 12 bajtów dzięki @PeterTaylor.

Python 2, 63 60 bajtów

s=0;x=input()
for r in x+zip(*x):
 for n in(-1,)+r:s+=[n][s]

Dane wejściowe to lista krotek.

Kończy się to kodem wyjścia 0 dla naprzemiennych macierzy znaków i kodem wyjścia 1 w przeciwnym razie. Co to jest prawda i fałsz i - jak pokazano w sekcji weryfikacji - może być rzeczywiście użyte jako warunek np. W skrypcie Bash.

Weryfikacja

test-skrzynki.txt

[(1,)]
[(1, 0), (0, 1)]
[(0, 1), (1, 0)]
[(0, 1, 0), (0, 0, 1), (1, 0, 0)]
[(0, 1, 0), (1, -1, 1), (0, 1, 0)]
[(0, 1, 0, 0), (0, 0, 1, 0), (1, 0, 0, 0), (0, 0, 0, 1)]
[(1, 0, 0, 0), (0, 0, 1, 0), (0, 1, -1, 1), (0, 0, 1, 0)]
[(0, 0, 1, 0), (0, 1, -1, 1), (1, -1, 1, 0), (0, 1, 0, 0)]
[(0, 0, 1, 0), (1, 0, -1, 1), (0, 1, 0, 0), (0, 0, 1, 0)]
[(0, 0, 1, 0, 0), (0, 1, -1, 1, 0), (1, -1, 1, 0, 0), (0, 1, 0, -1, 1), (0, 0, 0, 1, 0)]
[(0, 0, 1, 0, 0, 0, 0, 0), (1, 0, -1, 0, 1, 0, 0, 0), (0, 0, 0, 1, -1, 0, 0, 1), (0, 0, 1, -1, 1, 0, 0, 0), (0, 0, 0, 0, 0, 0, 1, 0), (0, 0, 0, 0, 0, 1, 0, 0), (0, 1, -1, 1, 0, 0, 0, 0), (0, 0, 1, 0, 0, 0, 0, 0)]
[(0, 0, 0, 0, 1, 0, 0, 0), (0, 0, 1, 0, -1, 1, 0, 0), (0, 0, 0, 1, 0, 0, 0, 0), (1, 0, 0, -1, 1, -1, 1, 0), (0, 1, -1, 1, -1, 1, 0, 0), (0, 0, 0, 0, 1, 0, 0, 0), (0, 0, 1, 0, 0, 0, 0, 0), (0, 0, 0, 0, 0, 0, 0, 1)]
[(0,)]
[(-1,)]
[(1, 0), (0, 0)]
[(0, 0), (0, 1)]
[(-1, 1), (1, 0)]
[(0, 1), (1, -1)]
[(0, 0, 0), (0, 0, 0), (0, 0, 0)]
[(0, 1, 0), (1, 0, 1), (0, 1, 0)]
[(-1, 1, 1), (1, -1, 1), (1, 1, -1)]
[(0, 0, 1), (1, 0, 0), (0, 1, -1)]
[(0, 1, 0, 0), (0, 0, 0, 1), (1, 0, 0, 0), (0, 0, 1, -1)]
[(0, 0, 1, 0), (0, 0, 1, 0), (1, 0, -1, 1), (0, 1, 0, 0)]
[(0, 0, 0, 1), (1, 0, 0, 0), (-1, 1, 1, 0), (1, 0, 0, 0)]
[(1, 0, 1, 0, -1), (0, 1, 0, 0, 0), (0, 0, 0, 0, 1), (0, 0, 0, 1, 0), (0, 0, 0, 0, 1)]
[(0, 0, 1, 0, 0), (0, 1, -1, 1, 0), (1, -1, 1, 0, 0), (0, 1, 1, -1, 0), (0, 0, -1, 1, 1)]
[(0, -1, 0, 1, 1), (1, -1, 1, -1, 1), (0, 1, 1, 0, -1), (1, 1, -1, 1, -1), (-1, 1, 0, 0, 1)]
[(0, 0, 1, 0, 0, 0, 0, 0), (1, 0, 1, 0, 1, 0, 0, 0), (0, 0, 0, 1, -1, 0, 0, 1), (0, 0, 1, -1, 1, 0, 0, 0), (0, 0, 0, 0, 0, 0, 1, 0), (0, 0, 0, 0, 0, 1, 0, 0), (0, 1, -1, 1, 0, 0, 0, 0), (0, 0, 1, 0, 0, 0, 0, 0)]

test-suite.sh

while read; do
        if python2 asmv.py <<< "$REPLY"; then
                echo "true"
        else
                echo "false"
        fi
done < test-cases.txt 2>&- | uniq -c

Wynik

$ bash test-suite.sh
     12 true
     17 false

Jak to działa

Pomijając zera, każdy wiersz i kolumna musi składać się ze wzoru (1, -1) * 1 , tzn. Naprzemiennie występujących 1 i -1 , rozpoczynających się i kończących na 1 (więc suma jest1 ).

Aby to sprawdzić, spakowujemy / transponujemy macierz wejściową M , dołączamy wynik do M (teraz składający się z listy wierszy i kolumn) i poprzedzamy -1 do każdego wiersza / kolumny.

Na przykład jeśli M jest jedną z następujących macierzy (poprawna, niepoprawna)

     0  1  0         0  0  0
     0  0  1         1  0  0
     1  0  0         0  1 -1

wyniki są

-1 | 0  1  0    -1 | 0  0  0
-1 | 0  0  1    -1 | 1  0  0
-1 | 1  0  0    -1 | 0  1 -1
------------    ------------
-1 | 0  0  1    -1 | 0  1  0
-1 | 1  0  0    -1 | 0  0  1
-1 | 0  1  0    -1 | 0  0 -1

Odczyt wygenerowanej macierzy wierszowo musi skutkować płaską sekwencją ze wzorem (-1, 1) * . Aby to sprawdzić, bierzemy sumę wszystkich wpisów, zaczynając od górnego rzędu.

W przypadku przykładowych macierzy daje to wynik

-1 -1  0  0 -1 -1 -1  0 -1  0  0  0 -1 -1 -1  0 -1  0  0  0 -1 -1  0  0
-1 -1 -1 -1 -2 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -2 -3 -3 -3 -2 -3 -3 -3 -4

W przypadku prawidłowej macierzy znaków przemiennych dane wyjściowe będą składać się z -1 i 0 oraz - ponieważ każde -1 anuluje poprzednie 1 i odwrotnie - żadnych innych liczb.

Na pierwszy rzut oka może się to nie sprawdzać, czy ostatnia kolumna kończy się na 1 . Jednak w przypadku macierzy n × n zawierającej k zer, prawidłowe wiersze będą zawierać n + k jedynek. Gdyby wszystkie kolumny oprócz ostatniej były również poprawne , w kolumnach byłoby n + k - 1 , co jest niemożliwe.

Aby sprawdzić, czy nie ma innych liczb, przechowujemy sumy częściowe w zmiennej s i aktualizujemy je dla każdego wpisu z wygenerowaną macierzą za pomocą s+=[n][s].

Jeśli s = 0 lub s = -1 , jest to równoważne z s+=n. Jednak dla wszystkich innych wartości s powoduje błąd IndexErr , więc Python natychmiast kończy działanie z kodem wyjścia 1 . Jeśli tak się nie stanie, program kończy się z kodem wyjścia 0 .

R, 54 bajty

Funkcja anonimowa, wykorzystuje tę samą logikę, co odpowiedzi Pytona 2, Galaretki i Julii Dennisa.

function(x)all(abs(cumsum(rbind(-1,cbind(t(x),x))))<2)