16

Une matrice de signe alternatif est une matrice npar ncomposée des nombres -1, 0, 1, telle que:

La somme de chaque ligne et colonne est 1
Les entrées non nulles dans chaque ligne et colonne alternent dans le signe

Ces matrices généralisent les matrices de permutation, et le nombre de telles matrices pour une donnée nétait intéressant depuis un certain temps. Ils se produisent naturellement lors de la méthode de condensation de Dodgson pour calculer les déterminants matriciels (du nom de Charles Dodgson, mieux connu sous le nom de Lewis Carroll).

Voici quelques exemples de matrices de signes alternés 4 x 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

Et voici quelques exemples de matrices 4 par 4 qui ne sont pas des matrices de signes alternées:

 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)

Votre programme ou la fonction sera donnée une npar nmatrice ( n >= 1) de -1S, 0 et de 1 - sortie une valeur de truthy si la matrice est une matrice donnée de signe alterné, sinon sortie une valeur falsy.

Il s'agit de code-golf , donc l'objectif est de minimiser le nombre d'octets utilisés.

Cas de test

Les cas de test suivants sont donnés dans un format de liste 2D de type Python.

Vérité:

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

Faux:

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

code-golf array-manipulation decision-problem matrix Sp3000
la source

1

En relation

Peter Taylor

3

Rétine , 62 58 56 53 octets

Le nombre d'octets suppose le codage ISO 8859-1, et le \tdevrait être remplacé par des tabulations réelles (0x09 qui seraient transformées en espaces par SE sinon).

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

Le format d'entrée est une matrice où chaque colonne utilise trois caractères alignés à droite, par exemple:

La sortie est soit 0(fausse) soit 1(vraie).

Suite de tests. (Les premières lignes transforment le format d'entrée et permettent à Retina d'exécuter plusieurs cas de test à la fois.)

Explication

Heureusement, l'entrée est une matrice carrée: la transposition de carrés est à peu près faisable dans la rétine, tandis que la transposition de rectangles est une douleur énorme.

$
\t$`¶

Nous commençons par ajouter un onglet, l'entrée entière à nouveau (en utilisant le préfixe $` ) puis un saut de ligne à la fin (en utilisant l'alias de Retina ¶). Nous utilisons un onglet pour séparer les deux copies afin de pouvoir les distinguer lorsque nous transposons l'une d'entre elles, et en utilisant un espace, nous pouvons économiser quelques octets plus tard.

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

C'est le bit le plus délicat: transposer la première copie de la matrice. L'idée est de faire correspondre les cellules de la première copie, puis de les trier (de manière stable) par position horizontale. Nous faisons correspondre les cellules avec ...(car elles ont toujours trois caractères de large), puis mesurons la position horizontale avec l' (.+)intérieur du regard. Ensuite, pour nous assurer que nous ne transposons que la première copie, nous vérifions que nous pouvons atteindre le début de la chaîne sans passer devant un onglet.

Vous remarquerez peut-être que cela correspondra également à certaines chaînes de trois octets (qui ne s'alignent même pas avec les cellules) dans la première ligne de la deuxième copie, car elles .+peuvent passer par l'onglet. Cependant, ce n'est pas un problème car la position horizontale de ces correspondances est strictement supérieure à celle de la première copie, de sorte que ces correspondances restent à leur position.

Le reste est assez simple:

T` 0

Nous supprimons les espaces et les zéros de l'entrée.

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

Et enfin, nous vérifions que la totalité de l'entrée est constituée de lignes terminées par des espaces du formulaire 1(-11)*, c'est-à-dire une séquence alternée de 1et -1qui commence et se termine par 1(car sinon, elle ne résume pas 1).

Martin Ender
la source

3

Gelée, 15 octets

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

Essayez-le en ligne!

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

Leaky Nun
la source

3

Pyth, 16 octets

!sm-sM._+d_1U2+C

Essayez-le en ligne: démonstration ou suite de tests

Explication:

!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

Jakube
la source

3

Gelée , 11 octets

;Zj-+\ṚQḄ=2

Renvoie 1 pour les matrices de signe alternées, 0 sinon. Essayez-le en ligne! ou vérifiez tous les cas de test .

Contexte

Sans tenir compte des zéros, chaque ligne et colonne doit être constituée du motif (1, -1) * 1 , c'est-à-dire alterner les occurrences de 1 et -1 , commençant et se terminant par 1 (la somme est donc 1 ).

Pour vérifier que c'est le cas, nous prenons le tableau de toutes les lignes et colonnes et les joignons en utilisant -1 comme séparateur. Puisque tous les points de terminaison sont à 1 , le tableau plat résultant satisfait le modèle (1, -1) * 1 si et seulement si les lignes et les colonnes le font.

Pour le test réel, nous calculons la somme cumulée du tableau. Pour une matrice de signe alternée, le résultat sera un tableau de 0 et de 1 qui se termine par un 1 .

Nous inversons la somme cumulée et la dédupliquons, en conservant l'ordre des occurrences initiales de tous les éléments uniques. Pour une entrée véridique, le résultat sera la liste [1, 0] .

Pour sortir le booléen correspondant, nous convertissons les sommes cumulées dupliquées de binaire en entier et testons si le résultat est 2 .

Comment ça fonctionne

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

Dennis
la source

2

MATL, 18 16 15 13 octets

3 octets économisés grâce à @Luis

t!h"@s1=@Xzdv

Cette solution accepte un tableau 2D en entrée et produira un tableau véridique ou falsey . Il est important de noter qu'en MATL, un tableau véridique est composé de tous les éléments non nuls tandis qu'un résultat de falsey a au moins un élément zéro. Voici une autre démonstration des tableaux truey / falsey .

Essayez-le en ligne

Version modifiée pour afficher tous les cas de test

Explication

        % 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

Suever
la source

2

Julia, 36 octets

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

Essayez-le en ligne!

Dennis
la source

1

JavaScript (ES6), 112 100 bytes

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

Aplatit le tableau et sa transposition en chaînes, puis (en ignorant 0s) vérifie le motif 1-11...1-11dans chaque chaîne.

Edit: 12 octets enregistrés grâce à @PeterTaylor.

Neil
la source

1

Vous n'avez pas besoin de vérifier le modèle -11-1...-11-1parce que depuis les entrées de remplacement et ont somme positive, il doit y avoir un plus 1que -1, de sorte que le modèle doit être 1-11...1-11.

Peter Taylor

@PeterTaylor Ugh, c'est la deuxième fois que j'ai mal lu la question. (Les commentaires relatifs à la première fois ont depuis été supprimés.)

Neil

L'en-tête indique 110 octets, mais ce n'est que 100

Peter Taylor

1

@PeterTaylor Au moins les "12 octets enregistrés grâce à @PeterTaylor" étaient corrects.

Neil

1

Python 2, 63 60 octets

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

L'entrée est une liste de tuples.

Cela se termine par le code de sortie 0 pour les matrices de signe alternées et le code de sortie 1 sinon. C'est ce que font le vrai et le faux , et - comme indiqué dans la section de vérification - cela peut en effet être utilisé comme condition dans, par exemple, un script Bash.

Vérification

test-cases.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

Production

$ bash test-suite.sh
     12 true
     17 false

Comment ça fonctionne

Sans tenir compte des zéros, chaque ligne et colonne doit être constituée du motif (1, -1) * 1 , c'est-à-dire alterner les occurrences de 1 et -1 , commençant et se terminant par 1 (la somme est donc 1 ).

Pour vérifier que c'est le cas, nous compressons / transposons la matrice d'entrée M , ajoutons le résultat à M (maintenant composé d'une liste de lignes et de colonnes) et ajoutons un -1 à chaque ligne / colonne.

Par exemple, si M est l'une des matrices suivantes (valide, non valide)

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

les résultats sont

-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

La lecture de la matrice générée en ligne doit entraîner une séquence plate avec le motif (-1, 1) * . Pour vérifier que c'est le cas, nous prenons la somme cumulée de toutes les entrées, en commençant par la ligne du haut.

Pour les exemples de matrices, cela se traduit par

-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

Pour une matrice de signe alternatif valide, la sortie sera composée de -1 et de 0 et - puisque chaque -1 annule le 1 précédent et vice versa - aucun autre nombre.

À première vue, cela peut sembler ne pas réussir à vérifier si la dernière colonne se termine par un 1 . Cependant, pour une matrice n × n contenant k zéros, les lignes valides contiendront n + k uns. Si toutes les colonnes sauf la dernière étaient également valides, il y en aurait n + k - 1 dans les colonnes, ce qui est impossible.

Pour vérifier qu'il n'y a pas d'autres nombres, nous stockons les sommes partielles dans une variable s et les mettons à jour pour chaque entrée de avec la matrice générée avec s+=[n][s].

Si s = 0 ou s = -1 , cela équivaut à s+=n. Cependant, pour toutes les autres valeurs de s , il provoque une IndexError , donc Python se termine immédiatement avec le code de sortie 1 . Si cela ne se produit à aucun moment, le programme se termine proprement avec le code de sortie 0 .

Dennis
la source

0

R, 54 octets

La fonction anonyme utilise la même logique que les réponses de Dennis Python 2, Jelly et Julia.

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

rturnbull
la source

Vérification de la matrice des signes alternés

Cas de test

Réponses:

Rétine , 62 58 56 53 octets

Explication

Gelée, 15 octets

Pyth, 16 octets

Explication:

Gelée , 11 octets

Contexte

Comment ça fonctionne

MATL, 18 16 15 13 octets

Julia, 36 octets

JavaScript (ES6), 112 100 bytes

Python 2, 63 60 octets

Vérification

Comment ça fonctionne

R, 54 octets