12
\$\begingroup\$

A ballot number, which we'll label B, is the number of ways of arranging the numbers from 1 through B(B+1)/2 into a triangle, such that each row and column is in any increasing order. The first four ballot numbers are:

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

a(3) is 2, which means that there are 2 ways of arranging the numbers from 1 to 3(3+1)/2 = 6 in such a triangle:

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

See the OEIS sequence entry for more details.

Your challenge, given a ballot triangle, is to verify its correctness. If it satisfies the conditions of a ballot triangle (rows and columns increasing), you should output how many other ways (excluding the one in the input) there are to arrange the triangle correctly. If the input triangle is incorrectly constructed, you should output nothing.

Trailing newlines are allowed.

Input

A triangle of numbers, which may or may not be a valid ballot triangle. For example:

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

Output

If the input is a valid ballot triangle, the remaining number of ways to arrange the same numbers in a valid ballot triangle. If the input is not a valid ballot triangle, nothing. For example, the inputs above produce these outputs (<nothing> is a placeholder for an actual empty output):

1                     # the same as a(3)-1

<nothing>

<nothing>

<nothing>

33591                 # the same as a(6)-1

Scoring

This is : as usual, lowest byte-count wins. Tiebreaker is earliest posted.

\$\endgroup\$
  • 1
    \$\begingroup\$ You should probably mention that the columns are also in increasing order. That confused me until I looked up the OEIS definition. \$\endgroup\$ – ballesta25 Aug 14 '16 at 17:00
  • \$\begingroup\$ Then why isn't 1/4 5/2 3 6 valid? \$\endgroup\$ – Leaky Nun Aug 14 '16 at 17:32
  • \$\begingroup\$ Spec fixed - I read the OEIS entry wrong. @ballesta25 \$\endgroup\$ – ArtOfCode Aug 14 '16 at 18:51
  • \$\begingroup\$ c.c. @LeakyNun ^ \$\endgroup\$ – ArtOfCode Aug 14 '16 at 18:51
  • \$\begingroup\$ Can we assume that the input will contain the correct numbers, even if not in the correct order? \$\endgroup\$ – Dennis Aug 14 '16 at 19:01
4
\$\begingroup\$

Jelly, 20 bytes

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

For valid ballot triangles, run time and memory usage are at least O(n!), where n is the number of entries of the triangle. Invalid ones are recognized by crashing, thus printing nothing.

Try it online!

Test run

Locally, I was able to verify that a(4) is calculated correctly.

$ 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

How it works

;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.
\$\endgroup\$
3
\$\begingroup\$

Brachylog, 44 bytes

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

Try it online!

This runs in double-exponential time, so for truthy testcases you would need to believe me that it theoretically produces the correct result, for triangles with length greater than or equal to 3.

You can still test for falsey testcases, those should terminate rather quickly.

\$\endgroup\$
  • \$\begingroup\$ I've had to update the spec - both rows and columns should be increasing. Result of me reading the OEIS entry incorrectly. Sorry if that invalidates your answer! \$\endgroup\$ – ArtOfCode Aug 14 '16 at 18:50
  • \$\begingroup\$ @ArtOfCode That was what my answer does all along \$\endgroup\$ – Leaky Nun Aug 14 '16 at 19:02
2
\$\begingroup\$

JavaScript (ES6), 143 bytes

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

Searches the triangle for an invalid entry and then uses a recursive formulation of the formula in OEIS to calculate the result.

\$\endgroup\$
  • \$\begingroup\$ I've had to update the spec - both rows and columns should be increasing. Result of me reading the OEIS entry incorrectly. Sorry if that invalidates your answer! \$\endgroup\$ – ArtOfCode Aug 14 '16 at 18:50
  • \$\begingroup\$ @ArtOfCode No, I was already checking that, but thanks anyway. \$\endgroup\$ – Neil Aug 14 '16 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.