Eine Wahlnummer , die wir als B bezeichnen , gibt die Anzahl der Möglichkeiten an, die Zahlen von 1 bis B (B + 1) / 2 in einem Dreieck anzuordnen, sodass jede Zeile und Spalte in aufsteigender Reihenfolge angezeigt wird. Die ersten vier Wahlnummern sind:

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

a(3)ist 2, was bedeutet, dass es zwei Möglichkeiten gibt, die Zahlen von 1 bis 3(3+1)/2 = 6in einem solchen Dreieck anzuordnen:

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

Weitere Informationen finden Sie im OEIS-Sequenzeintrag .

Angesichts eines Wahldreiecks besteht Ihre Herausforderung darin, die Richtigkeit zu überprüfen. Wenn es die Bedingungen eines Stimmzetteldreiecks erfüllt (Zeilen und Spalten nehmen zu), sollten Sie ausgeben, wie viele andere Möglichkeiten (mit Ausnahme der in der Eingabe) vorhanden sind, um das Dreieck richtig anzuordnen. Wenn das Eingabedreieck falsch konstruiert ist, sollten Sie nichts ausgeben.

Nachgestellte Zeilenumbrüche sind zulässig.

Eingang

Ein Dreieck von Zahlen, das ein gültiges Wahldreieck sein kann oder nicht. Beispielsweise:

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

Ausgabe

Wenn es sich bei der Eingabe um ein gültiges Wahldreieck handelt, wird die verbleibende Anzahl von Möglichkeiten zum Anordnen derselben Zahlen in einem gültigen Wahldreieck angegeben. Wenn die Eingabe kein gültiges Wahldreieck ist, nichts. Zum Beispiel erzeugen die obigen Eingaben diese Ausgaben ( <nothing>ist ein Platzhalter für eine tatsächliche leere Ausgabe):

1                     # the same as a(3)-1

<nothing>

<nothing>

<nothing>

33591                 # the same as a(6)-1

Wertung

Das ist Code-Golf : Wie üblich gewinnt die niedrigste Byteanzahl. Tiebreaker ist am frühesten gebucht.

Gelee , 20 Bytes

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

Bei gültigen Abstimmungsdreiecken betragen Laufzeit und Speicherauslastung mindestens O (n!) , Wobei n die Anzahl der Einträge des Dreiecks ist. Ungültige werden durch Absturz erkannt und es wird nichts gedruckt.

Probieren Sie es online!

Testlauf

Vor Ort konnte ich überprüfen, ob a (4) korrekt berechnet wurde.

$ 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

Wie es funktioniert

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

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

Probieren Sie es online!

Dies läuft in einer doppelt exponentiellen Zeit, so dass Sie mir für wahrheitsgemäße Testfälle glauben müssten, dass es theoretisch das richtige Ergebnis für Dreiecke mit einer Länge von größer oder gleich liefert 3.

Sie können immer noch auf falsche Testfälle testen, diese sollten ziemlich schnell enden.

JavaScript (ES6), 143 Byte

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

Durchsucht das Dreieck nach ungültigen Einträgen und verwendet dann eine rekursive Formulierung der Formel in OEIS, um das Ergebnis zu berechnen.