Produit de longueur de crochet

27

Un diagramme de Young est un arrangement de boîtes dans des lignes justifiées à gauche et des colonnes justifiées en haut. Pour chaque case, tous les espaces au-dessus et à gauche sont occupés.

XXXXX
XXX
XXX
X

La longueur de crochet d'une boîte est le nombre de boîtes à sa droite dans sa ligne, et en dessous dans sa colonne, se comptant également une fois. Par exemple, la deuxième boîte a une longueur de crochet de 6:

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

Voici toutes les longueurs de crochet:

86521
532
421
1

Votre objectif est de calculer le produit des longueurs de crochet, ici 8*6*5*2*1*5*3*2*4*2*1*1 = 115200.

(Lisez la formule de la longueur du crochet si vous souhaitez savoir pourquoi cette expression est importante.)

Entrée: collection de tailles de lignes sous forme de nombres comme [5,3,3,1]ou sous forme de symbole unaire répété comme [[1,1,1,1,1], [1,1,1], [1,1,1], [1]]ou "XXXXX XXX XXX X". Vous pouvez vous attendre à ce que la liste soit triée par ordre croissant ou décroissant, comme vous le souhaitez. La liste sera non vide et ne contiendra que des entiers positifs.

Sortie: Le produit des longueurs de crochet, qui est un entier positif. Ne vous inquiétez pas des débordements d'entiers ou de l'exécution.

Les éléments intégrés traitant spécifiquement des diagrammes de Young ou des partitions entières ne sont pas autorisés.

Cas de test:

[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
la source

Réponses:

13

CJam, 20 19 octets

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

Cela prend la liste unaire de style CJam dans un ordre croissant. Par exemple:

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

donne

115200

Comment ça marche

Cette version est fournie par Dennis et utilise le fait qu'un Block ArrayList %fonctionne toujours dans 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.

Ceci est la version originale de 20 octets

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

Cela prend une liste de tailles de lignes de style CJam dans un ordre croissant. Par exemple:

[1 3 3 5]

donne

115200

Comment ça marche

Si nous le regardons, la longueur de crochet de chaque bloc dans un diagramme de blocs Young est la somme de l'index de ce bloc dans sa ligne et sa colonne, en comptant à rebours. c'est-à-dire démarrer l'index dans chaque ligne du côté droit et démarrer l'index dans chaque colonne du bas.

Nous prenons l'entrée en ordre croissant de taille de ligne afin de démarrer facilement l'index du bas dans chaque colonne. Tout d'abord, nous obtenons l'indice par ligne et l'inversons. Ensuite, nous transposons. Étant donné que l'ordre des lignes d'origine a été inversé, la prise d'index dans ce diagramme transposé donnera directement l'index de bas en haut.

Expansion du code

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

Essayez-le en ligne ici

Optimiseur
la source
{ee::+W%}_q~%z%:+:*(19 octets) Format d'entrée:[[1][1 1 1][1 1 1][1 1 1 1 1]]
Dennis
@Dennis Nice (ab) utilisation de l'ordre d'arité pour %: P
Optimizer
6

J, 24 octets

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

25 octets (avec explication):

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

Prend la saisie sous forme de liste de listes ascendantes de chiffres unaires similaires à l'exemple [[1], [1,1,1], [1,1,1], [1,1,1,1,1]].

Usage:

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

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

Méthode

  • Créer une matrice binaire à partir de l'entrée
  • Calculez les différences de fonctionnement dans les deux dimensions.
  • Pour chaque cellule, additionnez les deux résultats, soustrayez 1, prenez la valeur absolue (pour mapper les cellules initialement nulles à 1)
  • Ravelez la matrice et prenez le produit des nombres.

Résultats intermédiaires affichés sur l'entrée 1 1 1 1 1;1 1 1;1 1 1;1 (5,3,3,1 in unary)( c'est pour une version précédente avec des longueurs décroissantes mais en utilisant la même méthode ):

   ]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

Version explicite de même longueur:

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

Essayez-le en ligne ici.

randomra
la source
4

Pyth - 21 octets

Je perd beaucoup d'octets dans le calcul vertical. Je vais me concentrer sur le golf.

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

Prend l'entrée comme [5, 3, 3, 1].

Essayez-le ici en ligne .

Maltysen
la source
4

Pyth, 18 octets

*Fsm.e+k-bdf>TdQeQ

Prend les entrées dans l'ordre croissant, comme [1, 3, 3, 5].

Manifestation.


Solution alternative, 19 octets

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

Python 2, 89 88 octets

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

(Merci à @xnor pour un octet fou sauvegardé en combinant pet j)

Le d.getme semble un peu suspect, mais sinon je suis relativement heureux avec cela. J'ai essayé d'autres approches, comme la récursivité et le zippage, mais c'est la seule que j'ai réussi à obtenir moins de 100.

Prend l'entrée de STDIN comme une liste dans l'ordre croissant, par exemple [1, 3, 3, 5].

Sp3000
la source
3

Haskell, 68 octets

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

Exemple d'utilisation: p [5,4,3,2,1]->4465125

fbalaye de gauche à droite en multipliant la longueur du crochet le plus à l'extérieur par un appel récursif à lui-même où chaque élément de la liste d'entrée est réduit de 1(en le supprimant en atteignant 0). pbalaye de haut en bas en multipliant fla liste entière par pla queue.

nimi
la source
2

R, 174 octets

Alors ... Cette solution est assez longue et pourrait probablement être plus jouée. Je vais y penser !

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

Non 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
la source
1

Python 2, 135 128 octets

Cela prend une liste de types 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

Il s'agit d'une implémentation très canonique, mais je n'ai jusqu'à présent rien trouvé de plus intelligent. J'ai le sentiment qu'il y aura des solutions beaucoup plus courtes même avec de "vrais" langages de programmation.

Nous obtenons le nombre de cases dans chaque ligne en entrée. Cette solution compte d'abord le nombre de cases dans chaque colonne, qui est stocké dans c(c'est en fait le nombre moins 1 pour simplifier son utilisation dans le calcul ultérieur). Ensuite, il itère sur toutes les cases et multiplie les longueurs de crochet. La longueur du crochet lui-même est triviale à calculer une fois que vous avez le nombre de cases dans chaque ligne et colonne.

Reto Koradi
la source
1
On dirait que vous n'utilisez pas m?
xnor
Aurait juré que je l'ai supprimé! Je me souviens avoir remarqué que je ne l'utilisais qu'une seule fois et substituer la seule utilisation. Mais alors j'ai dû manquer de supprimer la variable. :(
Reto Koradi
1

JavaScript ( ES6 ) 69

Une fonction prenant un tableau d'entiers dans l' ordre croissant .

Exécutez l'extrait de code pour tester (Firefox uniquement)

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
la source
1

Python, 95 91 octets

Ceci est une implémentation Python de la réponse Haskell de nimi . Suggestions de golf bienvenues.

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
la source
Bienvenue au golf Python! Vous pouvez faire z and _ or 1comme z==[]or _quand zest une liste, en utilisant le fait que True==1. Les déclarations de fonctions de Python sont plus verbeuses que Haskell, donc cela donne souvent un bon gain pour définir une seule fonction récursive qui fait à la fois les boucles récursives intérieure et extérieure, bien que je ne sache pas dans quelle mesure cela est possible ici.
xnor
@xnor "Bienvenue au golf Python"?
Sherlock9
Oh, désolé, vous faites du golf en Python. Je vous associe en fait.
xnor
@xnor Long, bien avant de commencer en fait, je jouais au golf en Python. Je suis un peu vexé que tu ne te souviennes pas: P
Sherlock9
Je ne peux pas parler pour xnor, mais je reconnais les utilisateurs principalement par leur avatar.
Dennis