Producto de longitud de gancho

27

Un diagrama de Young es una disposición de cuadros en filas justificadas a la izquierda y columnas justificadas en la parte superior. Para cada cuadro, todos los espacios encima y a su izquierda están ocupados.

XXXXX
XXX
XXX
X

La longitud del gancho de una caja es el número de cajas a su derecha en su fila, y debajo de ella en su columna, contando una sola vez. Por ejemplo, el segundo cuadro tiene una longitud de gancho de 6:

X****
X*X
X*X
X

Aquí están todas las longitudes de gancho:

86521
532
421
1

Su objetivo es calcular el producto de las longitudes de gancho, aquí 8*6*5*2*1*5*3*2*4*2*1*1 = 115200.

(Lea sobre la fórmula de longitud de gancho si está interesado en por qué es importante esta expresión).

Entrada: Una colección de tamaños de fila como números como [5,3,3,1]o como un símbolo unario repetido como [[1,1,1,1,1], [1,1,1], [1,1,1], [1]]o "XXXXX XXX XXX X". Puede esperar que la lista se ordene ascendente o descendente, según lo desee. La lista no estará vacía y solo contendrá enteros positivos.

Salida: El producto de las longitudes de gancho, que es un entero positivo. No se preocupe por los desbordamientos de enteros o el tiempo de ejecución.

No se permiten los elementos integrados que tratan específicamente con diagramas de Young o particiones enteras.

Casos de prueba:

[1] 1
[2] 2
[1, 1] 2
[5] 120
[2, 1] 3
[5, 4, 3, 2, 1] 4465125
[5, 3, 3, 1] 115200
[10, 5] 798336000
xnor
fuente

Respuestas:

13

CJam, 20 19 bytes

{ee::+W%}_q~%z%:+:*

Esto toma la lista unaria de estilo CJam en orden ascendente. Por ejemplo:

[[1] [1 1 1] [1 1 1] [1 1 1 1 1]]

da

115200

Cómo funciona

Dennis proporciona esta versión y utiliza el hecho de que a Block ArrayList %todavía funciona en CJam: D

{       }_             e# Put this block on stack and make a copy
          q~           e# Read the input and evaluate it to put the array of arrays on stack
            %          e# Use the copy of the block and map the array using that block
 ee                    e# Here we are mapping over each unary array in the input. ee converts
                       e# the array to [index value] pair.
   ::+                 e# Add up each index value pair. Now we have the horizontal half of
                       e# hook length for each row
      W%               e# Reverse the array to make sure the count is for blocks to the right
             z%        e# Transpose and do the same mapping for columns
               :+      e# Now we have all the hook lengths. Flatten the array
                 :*    e# Get the product of all hook lengths.

Esta es la versión original de 20 bytes.

1q~:,Wf%z:ee{:+)*}f/

Esto toma una lista de tamaños de fila de estilo CJam en orden ascendente. Por ejemplo:

[1 3 3 5]

da

115200

Cómo funciona

Si lo miramos, la longitud del gancho de cada bloque en un diagrama de bloques Young es la suma del índice de ese bloque en su fila y columna, contando hacia atrás. es decir, comience el índice en cada fila desde el lado derecho y comience el índice en cada columna desde la parte inferior.

Tomamos la entrada en orden ascendente de tamaño de fila para comenzar fácilmente el índice desde abajo en cada columna. Primero, obtenemos el índice por fila y lo invertimos. Luego nos transponemos. Como se invirtió el orden de las filas originales, tomar el índice en este diagrama transpuesto dará directamente el índice de abajo hacia arriba.

Expansión de código

1                       e# This serves as the initial term for product of hook lengths
 q~                     e# Read the input and eval it to put an array on stack
   :,                   e# For each row-size (N), get an array of [0..N-1]
     Wf%                e# Reverse each row so that each row becomes [N-1..0]
        z               e# Transpose for the calculation of blocks below each block
         :ee            e# Enumerate each row. Convert it into array of [index value] pairs
            {    }f/    e# Apply this mapping block to each cell of each row
             :+         e# Add the index value pair. Here, index is the blocks below the
                        e# block and value is the blocks to the right of it in the Young diag
               )        e# Increment the sum by 1 to account for the block itself
                *       e# Multiply it with the current holding product, starting with 1

Pruébalo en línea aquí

Optimizador
fuente
{ee::+W%}_q~%z%:+:*(19 bytes) Formato de entrada:[[1][1 1 1][1 1 1][1 1 1 1 1]]
Dennis
@Dennis Nice (ab) uso del orden de arity para %: P
Optimizer
6

J, 24 bytes

*/@,@(1|@-+/\."1++/\)@:>

25 bytes (con explicación):

*/@,@(+/\."1|@<:@++/\)@:>

Toma la entrada como una lista de listas ascendentes de dígitos unarios similar al ejemplo [[1], [1,1,1], [1,1,1], [1,1,1,1,1]].

Uso:

   f=.*/@,@(+/\."1|@<:@++/\)@:>

   f 1;1 1 1;1 1 1;1 1 1 1 1
115200

Método

  • Crear una matriz binaria a partir de la entrada
  • Calcule las diferencias de ejecución en ambas dimensiones.
  • Para cada celda sume los dos resultados, reste 1, tome el valor absoluto (para mapear las celdas originalmente cero a 1)
  • Desentraña la matriz y toma el producto de los números.

Los resultados intermedios se muestran en la entrada 1 1 1 1 1;1 1 1;1 1 1;1 (5,3,3,1 in unary)( esto es para una versión anterior con longitudes descendentes pero utilizando el mismo método ):

   ]c=.1 1 1 1 1;1 1 1;1 1 1;1
┌─────────┬─────┬─────┬─┐
│1 1 1 1 1│1 1 1│1 1 1│1│
└─────────┴─────┴─────┴─┘

   (>)  c
1 1 1 1 1
1 1 1 0 0
1 1 1 0 0
1 0 0 0 0

   (+/\.@:>)  c
4 3 3 1 1
3 2 2 0 0
2 1 1 0 0
1 0 0 0 0

   (+/\."1@:>)  c
5 4 3 2 1
3 2 1 0 0
3 2 1 0 0
1 0 0 0 0

   ((+/\."1++/\.)@:>)  c
9 7 6 3 2
6 4 3 0 0
5 3 2 0 0
2 0 0 0 0

   ((+/\."1<:@++/\.)@:>)  c
8  6  5  2  1
5  3  2 _1 _1
4  2  1 _1 _1
1 _1 _1 _1 _1

   ((+/\."1|@<:@++/\.)@:>)  c
8 6 5 2 1
5 3 2 1 1
4 2 1 1 1
1 1 1 1 1

   (,@(+/\."1|@<:@++/\.)@:>)  c
8 6 5 2 1 5 3 2 1 1 4 2 1 1 1 1 1 1 1 1

   (*/@,@(+/\."1|@<:@++/\.)@:>)  c
115200

Versión explícita de la misma longitud:

3 :'*/,|<:(+/\."1++/\)>y'

Pruébelo en línea aquí.

randomra
fuente
4

Pyth - 21 bytes

Estoy perdiendo muchos bytes en el cálculo vertical. Me voy a centrar en jugar al golf.

*Fs.em+lf>Td>Qkt-bdbQ

Toma entrada como [5, 3, 3, 1].

Pruébalo aquí en línea .

Maltysen
fuente
4

Pyth, 18 bytes

*Fsm.e+k-bdf>TdQeQ

Toma la entrada en orden ascendente, como [1, 3, 3, 5].

Demostración.


Solución alternativa, 19 bytes.

*Fs.em+s>Rd<Qk-bdbQ
isaacg
fuente
3

Python 2, 89 88 bytes

p=j=-1;d={}
for n in input():j+=1;i=0;exec"a=d[i]=d.get(i,j);p*=n-i+j-a;i+=1;"*n
print-p

(Gracias a @xnor por guardar un byte loco combinando py j)

El d.getparece un poco sospechoso para mí, pero por lo demás estoy relativamente contento con esto. Intenté algunos otros enfoques, como la recursión y la compresión, pero este es el único que logré tener menos de 100.

Toma información de STDIN como una lista en orden ascendente, por ejemplo [1, 3, 3, 5].

Sp3000
fuente
3

Haskell, 68 bytes

f[]=1
f g@(h:t)=(h+length t)*f[x-1|x<-g,x>1]
p[]=1
p g@(_:t)=f g*p t

Ejemplo de uso: p [5,4,3,2,1]->4465125

fescanea de izquierda a derecha multiplicando la longitud del gancho externo con una llamada recursiva a sí mismo donde cada elemento de la lista de entrada se reduce 1(cayéndolo al llegar 0). pescanea de arriba a abajo multiplicando fla lista completa con pla cola.

nimi
fuente
2

R, 174 bytes

Entonces ... Esta solución es bastante larga y probablemente podría ser más golfizada. Lo pensare !

v=c();d=length;m=matrix(-1,l<-d(a<-scan()),M<-max(a));for(i in 1:l)m[i,(1:a[i])]=c(a[i]:1);for(j in 1:M)m[,j]=m[,j]+c((((p=d(which(m[,j]>0)))-1)):0,rep(0,(l-p)));abs(prod(m))

Sin golf:

v=c()          #Empty vector
d=length       #Alias

m=matrix(-1,l<-d(a<-scan()),M<-max(a)) #Builds a matrix full of `-1`

for(i in 1:l)
    m[i,(1:a[i])]=c(a[i]:1) #Replaces each row of the matrix by `n` to 1, `n` being the 
                            #corresponding input : each number is the number of non-empty
                            #cells at its left + itself

for(j in 1:M)
    m[,j]=m[,j]+c((((p=d(which(m[,j]>0)))-1)):0,rep(0,(l-p)))

    #This part calculates the number of "non-empty" (i.e. without `-1` in a column), -1,
    #because the count for the cell itself is already done.
    # Then, it creates a vector of those count, appending 0's at the end if necessary 
    #(this avoids recycling)

abs(prod(m)) #Outputs the absolute value of the product (because of the `-1`'s)
Frédéric
fuente
1

Python 2, 135128 bytes

Esto toma una lista de tipo Python de stdin:

r=input()
c=[-1]*r[0]
for a in r:
 for b in range(a):c[b]+=1
s=1
y=0
for a in r:
 for x in range(a):s*=a-x+c[x]-y
 y+=1
print s

Esta es una implementación muy canónica, pero hasta ahora no he encontrado nada mucho más inteligente. Tengo la sensación de que habrá soluciones mucho más cortas incluso con lenguajes de programación "reales".

Obtenemos el número de cajas en cada fila como entrada. Esta solución primero cuenta el número de cuadros en cada columna, que se almacena c(en realidad es el recuento menos 1 para simplificar su uso en el cálculo posterior). Luego itera sobre todos los cuadros y multiplica las longitudes de gancho. La longitud del gancho en sí es trivial para calcular una vez que tiene el recuento de cuadros en cada fila y columna.

Reto Koradi
fuente
1
Parece que no estás usando m?
xnor
¡Podría haber jurado que lo eliminé! Recuerdo haber notado que solo lo estaba usando una vez, y sustituir el único uso. Pero entonces debo haber fallado para eliminar realmente la variable. :(
Reto Koradi
1

JavaScript ( ES6 ) 69

Una función que toma una matriz de enteros en orden ascendente .

Ejecute el fragmento para probar (solo Firefox)

F=x=>x.map(r=>{for(i=-1;++i<r;p[i]=-~p[i])t*=r-i+~~p[i]},p=[],t=1)&&t

// TEST
out=x=>O.innerHTML += x + '\n';

test=[
 {y:[1], h: 1}
,{y:[2], h: 2}
,{y:[1, 1], h: 2}
,{y:[5], h: 120}
,{y:[2, 1], h: 3}
,{y:[5, 4, 3, 2, 1], h: 4465125}
,{y:[5, 3, 3, 1], h: 115200}
,{y:[10, 5], h: 798336000}
]

test.forEach(t=>{ 
  t.y.reverse(); // put in ascending order
  r=F(t.y);
  out((r==t.h? 'Ok':'Fail')+' Y: ['+t.y+'] Result:'+r+' Check:'+t.h)
})  
<pre id=O></pre>

edc65
fuente
1

Python, 95 91 bytes

Esta es una implementación de Python de la respuesta Haskell de nimi . Sugerencias de golf bienvenidas.

f=lambda z:z==[]or(z[0]+len(z)-1)*f([i-1for i in z if~-i])
p=lambda z:z==[]or f(z)*p(z[1:])
Sherlock9
fuente
Bienvenido a Python golf! Puede hacer z and _ or 1como z==[]or _cuando zes una lista, utilizando el hecho de que True==1. Las declaraciones de funciones de Python son más verbales que Haskell, por lo que a menudo resulta útil definir una sola función recursiva que realiza los bucles recursivos internos y externos, aunque no sé qué tan factible es eso aquí.
xnor
@xnor "Bienvenido al golf de Python"?
Sherlock9
Oh, lo siento, haces golf en Python. Te asocio con En realidad.
xnor
@xnor Mucho, mucho antes de comenzar en realidad, estaba jugando golf en Python. Estoy un poco molesto que no recuerdes: P
Sherlock9
No puedo hablar por xnor, pero reconozco a los usuarios principalmente por su avatar.
Dennis