Défi

Dans cette tâche, vous devez calculer le nombre de façons dont nous pouvons répartir les boules A dans les cellules B, chaque cellule ayant au moins une balle.

Les entrées A et B sont données sur une seule ligne séparée par un blanc, les entrées sont terminées par EOF.

Vous voudrez peut-être vérifier vos solutions ici .

Contribution

0 0
1 0
12 4
6 3
18 17
20 19
15 13
18 9
20 20
17 14
9 2
14 13
18 11

Production

1
0
14676024
540
54420176498688000
23112569077678080000
28332944640000
38528927611574400
2432902008176640000
21785854970880000
510
566658892800
334942064711654400

Contraintes

• Chaque A et B peut être distingué.
• 0 <= A, B <= 20
• Vous pouvez utiliser la langue de votre choix
• La solution la plus courte gagne!

JavaScript (90 93 )

function f(a,b){n=m=r=1;for(i=b;i>0;n*=-1){r+=n*m*Math.pow(i,a);m=m*i/(b-i--+1)}return--r}

http://jsfiddle.net/RDGUn/2/

De toute évidence, tout langage mathématique tel que APL me battra à cause de la verbosité de la syntaxe et du manque de constructions mathématiques intégrées :)

Modifier En outre, je n'ai aucune fonctionnalité liée à l'entrée, à l'exception des paramètres passés dans la fonction, je ne sais pas comment utiliser l'entrée standard avec JavaScript ...

Edit: Déplacer i--dans l' m=m*expression; déplacer n*=-1en for; commencer r=1à combiner les affectations et en supprimer une superflue au retour. (enregistrer 3 caractères)

Golfscript - 56 50 49 48 41 40 38 37 caractères

n%{~),{!}%\{0.@{.@+2$*@)@}/;;]}*)p;}/

Remarque: cela gère plusieurs lignes d'entrée, est rapide (1/8 s pour faire les cas de test) et ne se casse pour aucune entrée légale.

(La première version était également mon tout premier programme Golfscript; merci à eBusiness d'avoir signalé plusieurs trucs que j'ai manqués).

Afin d'en faire également un poste éducatif utile, voici une explication de son fonctionnement. Nous commençons par la récurrence f(n, k) = k * (f(n-1, k) + f(n-1, k-1)). Ceci peut être compris de manière combinatoire comme disant que pour placer ndes boules distinctes dans kdes seaux reconnaissables de telle sorte que chaque seau contient au moins une balle, vous choisissez l'un des kseaux pour la première balle ( k *), puis soit il contiendra au moins une balle supplémentaire ( f(n-1, k)) ou ce ne sera pas ( f(n-1, k-1)).

Les valeurs qui en résultent forment une grille; prenant ncomme l'index de ligne et kcomme l'index de colonne et l'indexation à la fois à partir de 0, il commence

1   0   0   0    0    0   0 ...
0   1   0   0    0    0   0 ...
0   1   2   0    0    0   0 ...
0   1   6   6    0    0   0 ...
0   1  14  36   24    0   0 ...
0   1  30 150  240  120   0 ...
0   1  62 540 1560 1800 720 ...
.   .   .   .    .    .   . .
.   .   .   .    .    .   .  .
.   .   .   .    .    .   .   .

Passons donc au programme,

n%{~ <<STUFF>> }/

divise l'entrée en lignes, puis pour chaque ligne l'évalue, en mettant net ksur la pile, puis appelle <<STUFF>>, comme suit:

),{!}%\{0.@{.@+2$*@)@}/;;]}*)p;

Ceci calcule les premières k+1entrées de la n+1e ligne de cette grille. Initialement, la pile est n k.
),donne pile de n [0 1 2 ... k]
{!}%donne pile d' n [1 0 0 ... 0]où il y a des k0.
\{ <<MORE STUFF>> }*amène le nhaut et le fait le nombre de fois que nous exécutons <<MORE STUFF>>.
Notre pile est actuellement une ligne du tableau: [f(i,0) f(i,1) ... f(i,k)]
0.@met quelques 0 avant ce tableau. Le premier sera jet le second sera f(i,j-1).
{ <<FINAL LOOP>> }/boucle à travers les éléments du tableau; pour chacun, il le place en haut de la pile puis exécute le corps de la boucle.
.@+2$*@)@est la manipulation de la pile ennuyeuse pour prendre ... j f(i,j-1) f(i,j)et donner lieu ... j*(f(i,j-1)+f(i,j)) j+1 f(i,j)
;;]apparaît sur les restesk+1 f(i,k)et rassemble tout dans un tableau, prêt pour le prochain tour de boucle.
Enfin, lorsque nous avons généré la ne ligne du tableau,
)p;prend le dernier élément, l'imprime et supprime le reste de la ligne.

Pour la postérité, trois solutions de 38 caractères sur ce principe:
n%{~),{!}%\{0.@{.@+@.@*\)@}/;;]}*)p;}/
n%{~),{!}%\{0:x\{x\:x+1$*\)}/;]}*)p;}/
n%{~),{!}%\{0.@{@1$+2$*\@)}/;;]}*)p;}/

J, 40

4 :'|-/x(^~*y!~])i.1x+y'/&.".;._2(1!:1)3 

Par exemple

4 :'-/((x^~|.@:>:)*y&(!~))i.y'/x:".>{.;:(1!:1)3
15 13
28332944640000

<1 s pour tous les cas de test.

Modifications

• (52 → 47) Réduire avec -/au lieu d'alterner (1 _1)*(idée de JB)
• (47 → 53) Exigence d'entrée multiligne remarquée: - /
• (53 → 48) Exploitez la symétrie des binômes.
• (48 → 48) Faites tacite!
• (48 → 41)
• (41 → 40) Incrément de compression + conversion en1x+

Lisp commun (83)

(defun b (x y)
  (if (= (* x y) 0)
      (if (= (+ x y) 0) 1 0)
      (* y (+ (b (decf x) y) (b x (1- y)))))))

Il semble qu'il devrait y avoir un moyen plus court de tester les cas de base, mais rien ne me vient à l'esprit.

J, 38 à 42

Selon vos préférences de rigueur concernant les langages interactifs et la présentation des résultats, faites votre choix dans le spectre J des solutions:

• 38 le plus court interactif: 4 :'|-/(!&y*^&x)i.1x+y'/&".;._2(1!:1)3
  Lancez jconsole, entrez-le, puis collez l'entrée (terminez par Cd). Vous remarquerez que la sortie est séparée par des espaces (J est un langage vectoriel, il effectue le calcul sur l'ensemble de l'entrée dans son ensemble et le renvoie comme un vecteur 1D, dont la présentation par défaut est sur une seule ligne). Je considère que ok, l'esprit de ce problème est le calcul, pas la présentation. Mais si vous insistez pour avoir à la place des sauts de ligne:
• 39 plus interactif: le 4 :'|-/(!&y*^&x)i.1x+y'/&.".;._2(1!:1)3
  remplacement de Compose ( &) par Under ( &.) renvoie un vecteur de chaînes dont la présentation se termine sur des lignes distinctes.
• 42 mode batch: 4 :'echo|-/(!&y*^&x)i.1x+y'/&".;._2(1!:1)3
  Exécuter à partir de la ligne de commande en tant que$ jconsole balls.ijs < balls.in

Si vous avez voté pour cela, vous voudrez peut-être aussi donner du crédit à la solution d'Eelvex .

GolfScript - 45 38 36 caractères

Relation de récurrence d'implémentation de force moyenne ( 38 36 caractères):

n%{~{.2$*{\(.2$f\2$(f+*}{=}if}:f~p}/

La relation de récurrence que j'ai volé de la solution de Peter Taylors, ça se passe comme ceci:

f(x, y) = y * ( f(x-1, y) + f(x-1, y-1) )

Avec des cas spéciaux si l'une des variables est 0.

Mon implémentation ne réutilise pas les résultats précédents, donc chaque branche d'appel de fonction à deux nouveaux appels, sauf si l'un des zéro cas a été atteint. Cela donne le pire cas d'appels de fonction 2 ^ 21-1 qui prend 30 secondes sur ma machine.

Solution série Light-force (45 caractères):

n%{~.),0\{.4$?3$,@[>.,,]{1\{)*}/}//*\-}/p;;}/

J, 55 caractères

(wd@(4 :'(y^x)--/(!&y*^&x)|.i.y')/@".@,&'x');._2(1!:1)3

• Réussit les cas de test actuels. Je pense que je comprends les mathématiques ...
• j602, console uniquement ( wd). Entrée sur stdin, sortie sur stdout.

Script de test Bash:

jconsole disballs.ijs <<END
12 4
6 3
END

Golfscript - 26 caractères

Avertissement: le boîtier 12 4 a besoin de beaucoup de mémoire (mais pas autant que la réponse ci-dessous) et prend un certain temps à s'exécuter

~:)\?:x,{x+)base(;.&,)=},,

Évidemment, cette réponse a quelques problèmes, mais je vais la laisser ici parce que les commentaires y font référence et la réponse de mellamokb est basée sur elle.

Golfscript - 24 caractères

Avertissement: le boîtier 12 4 a besoin de beaucoup de mémoire et prend un certain temps à s'exécuter

~:o)\?,{o)base[0]-,o=},,

Python 140 caractères

import sys
f=lambda n,k:(n and k and n>=k and k*(f(n-1,k-1)+f(n-1,k)))or(n+k==0 and 1)or 0
for l in sys.stdin:print f(*(map(int,l.split())))

dc, 100 caractères

[0q]s5[1q]s6[l2l3>5l3 0>5l2 0=6l2 1-S2l3dS3 1-S3l1xL3s9l1xL2s9+L3*]s1[?z0=5S3S2l1xL3L2+s9fs9l4x]ds4x

Hélas, dc ne semble pas être soutenu par ideone. Il peut y avoir un ou deux personnages à éliminer, mais c'est l'heure du coucher.

Remarque: cela prend en charge plusieurs lignes d'entrée, a une précision suffisante pour donner la sortie correcte même pour 20 19(maudissez-vous, Perl, pour le temps que j'ai perdu à déboguer ma solution!), Et donne la sortie correcte pour 0 0.

Les suggestions de Nabb permettent de raccourcir au moins

[0q]sZ[1q]sI[?z0=ZSkSn[lnlk>Zlk0>Zln0=Iln1-SnlkdSk1-SklFxLks9lFxLns9+Lk*]dsFxfs9l4x]ds4x

au prix de laisser du courrier indésirable dans les piles de registres (et donc de manquer de mémoire si nous calculons des milliards de réponses).

Golfscript (28 31 37 )

~):$\.($\?:@;?,{@+}%{$base$,\-[0]=},,

Modification de gnibblerla solution GolfScript de. Je pense que c'est une solution de travail - testée avec [3,2], [4,2], [6,3] et [9,2] avec des réponses correctes. (J'ai utilisé $et @pour les variables pour resserrer l'espace autour du basemot - clé).

Il existe deux problèmes avec gnibblerla solution actuelle de.

1. Vérifier la longueur après avoir retiré [0] ne garantit pas une solution, car [1,1,1,1] serait valable pour l'entrée [4,2], même si les 4 billes sont dans la même cellule (1). J'ai donc modifié pour vérifier également que tous les chiffres sont utilisés, c'est-à-dire que le tableau contient 1-2, donc chaque cellule contient au moins une boule.
2. Dans le cas de l'entrée [4,2], le format base 3 des nombres 0-27 est inférieur à 4 chiffres et les 0 les plus à gauche ne sont pas inclus. Cela signifie que [1,1] est inclus comme une solution valide, même s'il s'agit techniquement de [0,0,1,1], ce qui signifie que les deux premières boules ne sont placées nulle part. Je corrige en ajoutant 3 ^ 3 à chaque entrée (génériquement k ^ n-1 au tableau des k ^ n entrées) de sorte que les premières entrées soient décalées vers le haut pour avoir au moins n chiffres au format base-k, et la dernière les entrées seront de toute façon automatiquement invalides et n'affecteront pas la solution (car le deuxième chiffre sera toujours 0).

Éditer

~:@\?:$,{$+}%{@base(;@,\-,0=},,

`~:@\?:$,{$+@base(;@,\-,0=},,`

Meilleure solution encore! Pas besoin d'incrémenter, il suffit d'ajouter à tous les nombres pour qu'ils commencent par [1], et aucun chiffre ne manquera (y compris le remplissage gauche de 0) une fois que vous déconnerez ce premier chiffre. Cette solution devrait fonctionner et a été testée avec les mêmes entrées ci-dessus. C'est aussi beaucoup plus rapide car nous n'incrémentons pas avant de prendre l'exposant pour générer le tableau (mais il souffre toujours du même problème de performances / mémoire pour une entrée plus grande).

Modifier : utilisez gnibblerl'idée de déplacer l'ajout de l' $intérieur du filtre au lieu d'une étape supplémentaire. (économisez 3 caractères).

05AB1E , 19 octets

#D`ULX.Œʒ€gßĀ}gs_P+

REMARQUE: il est extrêmement lent et expire déjà 12 4. Cependant, cela fonctionne comme prévu. Va voir si je peux trouver une méthode alternative qui fonctionne pour tous les cas de test dans un délai raisonnable. Voir ci-dessous pour une version beaucoup plus rapide qui exécute tous les cas de test en moins d'une seconde.

Essayez-le en ligne ou vérifiez quelques autres cas de test (parmi les plus petits) .

Explication:

#               # Split the (implicit) input-string by spaces
 D              # Duplicate it
  `             # Push both values to the stack
   U            # Pop and store the second value in variable `X`
    L           # Create a list in the range [1,n] for the first value
     X.Π       # Create a list of all possible ways to divide this list into `X` partitions
                # (including empty sublists, so we'll have to filter them out:)
        ʒ       # Filter this list of lists of partition-lists by:
         €g     #  Get the length of each partition-list
           ß    #  Get the minimum length
            Ā   #  Truthify; 0 remains 0 (falsey); anything else becomes 1 (truthy)
             }g # After the filter, take the length to get the amount left
 s              # Swap so the duplicated input-list is at the top of the stack again
  _             # Check for each value if they're equal to 0 (1 if truthy; 0 if falsey)
   P            # Take the product of the two to check if both input-values are 0
    +           # And add it to the earlier calculated product (edge case for [0,0] = 1)
                # (After which the result is output implicitly)

05AB1E , 29 octets

Voici une version beaucoup plus rapide qui fonctionne pour tous les cas de test en environ 0,5 seconde sur TIO:

Î#R`V©LRvyYmX*NÈ·<*+Xy*®y->÷U

Port de @mellamokb la réponse JavaScript , alors assurez-vous de voter pour lui!

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

Î                    # Push (result=) 0 and the input
 #                   # Split the input by spaces
  R`                 # Push the values to the stack reversed
    V                # Pop and store the first value in variable `Y`
     ©               # Store the second value in variable `®` (without popping)
      LRv            # Loop `y` in the range [`®`,1], with index `N` in the range [0,`®`):
         yYm         #  Calculate `y` to the power `Y`
            X*       #  Multiply it by `X`
                     #  (Note: `X` is 1 before setting it to another value initially)
              NÈ     #  Check if index `N` is even (1 if truthy; 0 if falsey)
                ·<   #  Double it; and decrease it by 1 (1 if truthy; -1 if falseY0
                  *  #  Multiply it to the earlier number
                   + #  And add it to the result
         Xy*         #  Push `X` multiplied by `y`
         ®y->        #  Push `®` - `y` + 1
             ÷       #  Integer divide them
              U      #  Pop and store it as new variable `X`
                     # (output the result at the top of the stack implicitly after the loop)

REMARQUE: fonctionne pour le cas de bord 0 0dans ce cas (contrairement à la réponse JavaScript à partir de laquelle j'ai porté cette méthode), car la fonction Lintégrée créera une liste [0,1].