Verificar un triángulo electoral

12

Un número de boleta , que etiquetaremos B , es el número de formas de organizar los números del 1 al B (B + 1) / 2 en un triángulo, de modo que cada fila y columna esté en un orden creciente. Los primeros cuatro números de boleta son:

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

a(3)es 2, lo que significa que hay 2 formas de organizar los números del 1 al 3(3+1)/2 = 6en ese triángulo:

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

Vea la entrada de secuencia OEIS para más detalles.

Su desafío, dado un triángulo electoral, es verificar su corrección. Si cumple las condiciones de un triángulo de votación (filas y columnas en aumento), debe indicar cuántas otras formas (excluyendo la de la entrada) hay para organizar el triángulo correctamente. Si el triángulo de entrada está construido incorrectamente, no debería generar nada.

Se permiten nuevas líneas al final.

Entrada

Un triángulo de números, que puede o no ser un triángulo de votación válido. Por ejemplo:

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

Salida

Si la entrada es un triángulo de boleta válido, el número restante de formas de organizar los mismos números en un triángulo de boleta válido. Si la entrada no es un triángulo de votación válido, nada. Por ejemplo, las entradas anteriores producen estas salidas ( <nothing>es un marcador de posición para una salida vacía real):

1                     # the same as a(3)-1

<nothing>

<nothing>

<nothing>

33591                 # the same as a(6)-1

Puntuación

Este es el : como de costumbre, el conteo de bytes más bajo gana. Tiebreaker se publica más temprano.

ArtOfCode
fuente
1
Probablemente debería mencionar que las columnas también están en orden creciente. Eso me confundió hasta que busqué la definición de OEIS.
ballesta25
Entonces, ¿por qué no es 1/4 5/2 3 6válido?
Leaky Nun
Especificación corregida: leí mal la entrada OEIS. @ ballesta25
ArtOfCode
cc @LeakyNun ^
ArtOfCode
¿Podemos suponer que la entrada contendrá los números correctos, incluso si no están en el orden correcto?
Dennis

Respuestas:

4

Jalea , 20 bytes

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

Para triángulos de boleta válidos, el tiempo de ejecución y el uso de memoria son al menos O (n!) , Donde n es el número de entradas del triángulo. Los inválidos se reconocen al estrellarse, por lo que no imprimen nada.

Pruébalo en línea!

Prueba de funcionamiento

A nivel local, pude verificar que a (4) se calcula correctamente.

$ 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

Cómo funciona

;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.
Dennis
fuente
3

Brachylog , 44 bytes

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

Pruébalo en línea!

Esto se ejecuta en un tiempo doblemente exponencial, por lo que para casos de prueba verdaderos, necesitaría creerme que teóricamente produce el resultado correcto, para triángulos con una longitud mayor o igual a 3.

Aún puede hacer pruebas para detectar casos de prueba de falsey, que deberían terminar bastante rápido.

Monja permeable
fuente
Tuve que actualizar la especificación: tanto las filas como las columnas deberían estar aumentando. Resultado de leer incorrectamente la entrada OEIS. Lo siento si eso invalida tu respuesta!
ArtOfCode
@ArtOfCode Eso fue lo que hizo mi respuesta todo el tiempo
Leaky Nun
2

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

Busca en el triángulo una entrada no válida y luego usa una formulación recursiva de la fórmula en OEIS para calcular el resultado.

Neil
fuente
Tuve que actualizar la especificación: tanto las filas como las columnas deberían estar aumentando. Resultado de leer incorrectamente la entrada OEIS. Lo siento si eso invalida tu respuesta!
ArtOfCode
@ArtOfCode No, ya lo estaba comprobando, pero gracias de todos modos.
Neil