Un numéro de bulletin de vote , que nous appellerons B , est le nombre de façons d'organiser les numéros de 1 à B (B + 1) / 2 dans un triangle, de sorte que chaque ligne et colonne est dans un ordre croissant. Les quatre premiers numéros de bulletin de vote sont:

a(0) = 1
a(1) = 1
a(2) = 1
a(3) = 2

a(3)est 2, ce qui signifie qu'il existe 2 façons d'organiser les nombres de 1 à 3(3+1)/2 = 6dans un tel triangle:

1          1
2 3    or  2 4
4 5 6      3 5 6

Voir l' entrée de séquence OEIS pour plus de détails.

Votre défi, étant donné un triangle de vote, est de vérifier son exactitude. S'il satisfait aux conditions d'un triangle de vote (les lignes et les colonnes augmentent), vous devez afficher le nombre d' autres façons (à l'exception de celle en entrée) qu'il existe pour organiser correctement le triangle. Si le triangle d'entrée n'est pas construit correctement, vous ne devez rien produire.

Les sauts de ligne sont autorisés.

Contribution

Un triangle de chiffres, qui peut être ou non un triangle de scrutin valide. Par exemple:

1
2 3
4 5 6

1
10 5 
9 8 2
7 6 4 3

1
3 2

9
2 11
14 3 5
12 8 1 7
15 13 10 4 6

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21

Production

Si l'entrée est un triangle de scrutin valide, le nombre restant de façons d'organiser les mêmes nombres dans un triangle de scrutin valide. Si l'entrée n'est pas un triangle de vote valide, rien. Par exemple, les entrées ci-dessus produisent ces sorties ( <nothing>est un espace réservé pour une sortie vide réelle):

1                     # the same as a(3)-1

<nothing>

<nothing>

<nothing>

33591                 # the same as a(6)-1

Notation

C'est le code-golf : comme d'habitude, le nombre d'octets le plus bas l'emporte. Tiebreaker est le plus tôt publié.

Gelée , 20 octets

;Zµ⁼Ṣ€
ẋÇFŒ!ṁ€⁸ÇÐfL’

Pour les triangles de scrutin valides, le temps d'exécution et l'utilisation de la mémoire sont au moins O (n!) , Où n est le nombre d'entrées du triangle. Les non valides sont reconnus par un plantage, n'imprimant ainsi rien.

Essayez-le en ligne!

Essai

Localement, j'ai pu vérifier qu'un (4) est calculé correctement.

$ time jelly eun ';Zµ⁼Ṣ€¶ẋÇFŒ!ṁ€⁸ÇÐfL’' '[1],[2,3],[4,5,6],[7,8,9,10]'
11

real    6m9.829s
user    6m7.930s
sys     0m2.579s

Comment ça fonctionne

;Zµ⁼Ṣ€         Helper link. Argument: T (triangular array)

 Z             Zip/transpose T.
;              Concatenate the original and the transposed copy.
  µ            Begin a new monadic chain, with the previous result (R) as argument.
    Ṣ€         Sort each array in R.
   ⁼           Test for equality with R.
               This returns 1 if T is a ballot triangle, 0 if not.

ẋÇFŒ!ṁ€⁸ÇÐfL’  Main link. Argument: A (triangular array)

 Ç             Call the helper link with argument A.
ẋ              Repeat A that many times.
               This yields an empty array if A is not a ballot triangle.
  F            Flatten the result.
   Œ!          Generate all permutations of the digits of A.
     ṁ€⁸       Mold each permutation like A, i.e., give it triangular form.
               This crashes if permutation array is empty.
        ÇÐf    Filter; keep permutations for which the helper link returns 1.
           L’  Compute the length and decrement it.

Brachylog , 44 octets

{:{o?}a,?z:2a},?ly+yb:3flw
p~c.:laBtybB,.:1&

Essayez-le en ligne!

Cela fonctionne en temps exponentiel double, donc pour des cas de test véridiques, vous devrez me croire que cela produit théoriquement le résultat correct, pour des triangles de longueur supérieure ou égale à 3.

Vous pouvez toujours tester les cas de test falsey, ceux-ci devraient se terminer assez rapidement.

JavaScript (ES6), 143 octets

a=>a.some((b,i)=>b.some((c,j)=>c<b[j-1]||i&&c<a[i-1][j]))?'':(f=n=>n<2||n*f(n-1),g=(n,m=f(n*n+n>>1))=>n<2?m:g(--n,m*f(n)/f(n+n+1)),g(a.length))

Recherche dans le triangle une entrée non valide, puis utilise une formulation récursive de la formule dans OEIS pour calculer le résultat.