Código de golf: Distribuir las bolas (I)

12

Desafío

En esta tarea, ha calculado la cantidad de formas en que podemos distribuir las bolas A en las celdas B y cada celda tiene al menos una bola.

Las entradas A y B se dan en una sola línea separada por un espacio en blanco, las entradas son terminadas por EOF.

Es posible que desee comprobar sus soluciones aquí .

Entrada

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

Salida

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

Restricciones

  • Cada A y B puede ser distinguible.
  • 0 <= A, B <= 20
  • Puedes usar cualquier idioma de tu elección
  • ¡La solución más corta gana!
Quijotesco
fuente
1
¿Hay límites de tiempo?
@Tim Nordenfur: Actualizado :-)
Quixotic
Ese enlace no es válido para mí.
mellamokb
3
@Debanjan No me gusta la idea de pegar preguntas de SPOJ aquí. La gente envía su código para competir allí y sería injusto para ellos.
fR0DDY
1
@Debanjan, veo tu referencia y te planteo Mathworld (la ecuación 5 dice que S(n,0)es 1si n=0y de 0otra manera). Si lo desea, puedo encontrar una referencia para la afirmación más fuerte de que Stirling2 está en el subgrupo asociativo del grupo exponencial de Riordan.
Peter Taylor

Respuestas:

4

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/

Obviamente, cualquier lenguaje basado en matemáticas como APL me vencerá debido a la verbosidad de la sintaxis y la falta de construcciones matemáticas integradas :)

Editar Además, no tengo ninguna funcionalidad relacionada con la entrada, excepto los parámetros pasados ​​a la función, no estoy seguro de cómo usar la entrada estándar con JavaScript ...

Editar: moverse i--a la m=m*expresión; mover n*=-1en for; comience r=1a combinar las tareas y elimine las extrañas al regresar (guardar 3 caracteres)

mellamokb
fuente
Se podría utilizar la cáscara spidermonkey - que al menos tiene readliney print. No sé lo que otros usan aquí.
Jesse Millikan
@Jesse: Interesante. Voy a perder de todos modos jajaja.
mellamokb
prompty alertson el io "estándar" de JavaScript, ya que son las llamadas io de bloqueo típicas, a pesar del hecho de que nunca se suele usar io de bloqueo con JavaScript.
zzzzBov
4

Golfscript - 56 50 49 48 41 40 38 37 caracteres

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

Nota: esto maneja múltiples líneas de entrada, es rápido (1/8 segundos para hacer los casos de prueba) y no interrumpe ninguna entrada legal.

(La primera versión también fue mi primer programa Golfscript; gracias a eBusiness por señalar varios trucos que me perdí).

Para hacer de esto una publicación educativa útil también, aquí hay una explicación de cómo funciona. Comenzamos con la recurrencia f(n, k) = k * (f(n-1, k) + f(n-1, k-1)). Esto puede entenderse combinatoriamente como decir que para colocar nbolas distinguibles en kcubos distinguibles de modo que cada cubo contenga al menos una bola, usted elige uno de los kcubos para la primera bola ( k *) y luego contendrá al menos una bola más ( f(n-1, k)) o no lo hará ( f(n-1, k-1)).

Los valores resultantes de esto forman una cuadrícula; tomando ncomo índice de fila y kcomo índice de columna e indexando ambos desde 0 comienza

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

Entonces volviendo al programa,

n%{~ <<STUFF>> }/

divide la entrada en líneas y luego para cada línea la evalúa, colocando ny ken la pila, y luego llama <<STUFF>>, que es como sigue:

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

Esto calcula las primeras k+1entradas de la n+1fila th de esa cuadrícula. Inicialmente la pila es n k.
),da una pila de n [0 1 2 ... k]
{!}%da una pila de n [1 0 0 ... 0]donde hay k0s.
\{ <<MORE STUFF>> }*trae el na la cima y lo convierte en el número de veces que ejecutamos <<MORE STUFF>>.
Nuestra pila actualmente es una fila de la tabla: [f(i,0) f(i,1) ... f(i,k)]
0.@pone un par de ceros antes de esa matriz. El primero será jy el segundo será f(i,j-1).
{ <<FINAL LOOP>> }/recorre los elementos de la matriz; para cada uno lo coloca en la parte superior de la pila y luego ejecuta el cuerpo del bucle.
.@+2$*@)@es aburrida la manipulación de la pila para tomar ... j f(i,j-1) f(i,j)y ceder ... j*(f(i,j-1)+f(i,j)) j+1 f(i,j)
;;]pops de los sobrantesk+1 f(i,k)y reúne todo en una matriz, listo para la próxima ronda del ciclo.
Finalmente, cuando generamos la nfila th de la tabla,
)p;toma el último elemento, lo imprime y descarta el resto de la fila.

Para la posteridad, tres soluciones de 38 caracteres sobre este principio:
n%{~),{!}%\{0.@{.@+@.@*\)@}/;;]}*)p;}/
n%{~),{!}%\{0:x\{x\:x+1$*\)}/;]}*)p;}/
n%{~),{!}%\{0.@{@1$+2$*\@)}/;;]}*)p;}/

Peter Taylor
fuente
1
Bastante bueno para un principiante, hay algunas posibles reducciones a pequeña escala, inmediatamente encuentro [0]-> 1,, el espacio después de zip simplemente se puede eliminar, y el otro espacio se puede eliminar si solo se almacena en un operador en lugar de k. Todavía no he revisado su código, pero sospecho que podría salirse con la suya simplemente usando un valor sin ponerlo en una matriz en algunos de los lugares.
aaaaaaaaaaaa
1
+ 1, no entiendo Golfscript, pero esto parece lo suficientemente rápido y, sin embargo, muy corto.
Quixotic
@eBusiness y @Peter Taylor: En una nota diferente ... ¿cuánto valoran ustedes Golfscript en la escala de fácil de aprender?
Quixotic
@Debanjan, depende de lo que ya sabes. Es un lenguaje funcional basado en pila. He usado lenguajes funcionales antes (SML - además he escrito código de estilo funcional en lenguajes OO), y he usado lenguajes basados ​​en pila antes (código de bytes Java ensamblado con Jasmin, PostScript), por lo que el único obstáculo real Me enfrento a aprender qué operadores están disponibles. Si solo conoce idiomas de la familia Algol (C, Java, etc.), tendrá tres obstáculos para saltar de una vez.
Peter Taylor
@Debanjan: es mucho más fácil de lo que parece, puede comenzar a escribir código casi de inmediato, pero, por supuesto, lleva algún tiempo aprender todos los pequeños trucos.
aaaaaaaaaaaa
3

J, 40

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

P.ej

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

<1 segundo para todos los casos de prueba.

Ediciones

  • (52 → 47) Reducir con en -/lugar de alternar (1 _1)*(idea de JB)
  • (47 → 53) Requisito de entrada multilínea notado: - /
  • (53 → 48) Exploit simetría de binomios.
  • (48 → 48) ¡ Haz tácito!
  • (48 → 41)
  • (41 → 40) Incremento de compresión + conversión en1x+
Eelvex
fuente
1
¡Oye! Esa fue mi idea! O :-)
JB
Ok, robaré eso 1x+entonces, pero eso solo me devuelve 1 personaje, ¡mientras que tomaste 5!
JB
3

Lisp común (83)

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

Parece que debería haber una forma más corta de probar los casos base, pero no se me ocurre nada de improviso.

Dr. Pain
fuente
3

J, 38 a 42

Dependiendo de sus preferencias estrictas sobre los idiomas interactivos y la presentación de salida, elija entre el espectro de soluciones J:

  • 38 interactivo más corto: 4 :'|-/(!&y*^&x)i.1x+y'/&".;._2(1!:1)3
    ejecute jconsole, ingréselo y luego pegue la entrada (termine con Cd). Notará que la salida está separada por espacios (J es un lenguaje vectorial, realiza el cálculo de toda la entrada como un todo y lo devuelve como un vector 1D, cuya presentación predeterminada está en una sola línea). Considero que está bien, el espíritu de este problema es el cálculo, no la presentación. Pero si insiste en tener nuevas líneas en su lugar:
  • 39 más interactivo: 4 :'|-/(!&y*^&x)i.1x+y'/&.".;._2(1!:1)3
    Reemplazar Compose ( &) con Under ( &.) devuelve un vector de cadenas, cuya presentación termina en líneas separadas.
  • 42 modo por lotes: 4 :'echo|-/(!&y*^&x)i.1x+y'/&".;._2(1!:1)3
    ejecutar desde la línea de comandos como$ jconsole balls.ijs < balls.in

Si votó por esto, es posible que también quiera darle algo de crédito a la solución de Eelvex .

JB
fuente
Necesita un Under &.para que funcione correctamente en modo interactivo.
Eelvex
@Eelvex debe tener una interpretación diferente de "correctamente". Comienzo jconsole, pego código, pego entrada, Cd y recibo la salida. No debajo de lo necesario. ¿Lo que es tuyo?
JB
Nuestros códigos combinados: 4 :'|-/(!&y*^&x)i.1x+y'/&.".;._2(1!:1)3. 39 caracteres
Eelvex
Sin echo o Under obtengo la salida en una sola línea (en lugar de varias líneas).
Eelvex
@Eelvex de hecho, pero eso no está explícitamente prohibido.
JB
3

GolfScript - 45 38 36 caracteres

Relación de recurrencia de implementación sucia de fuerza media ( 38 36 caracteres):

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

La relación de recurrencia que robé de la solución de Peter Taylors es así:

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

Con casos especiales si cualquiera de las variables es 0.

Mi implementación no reutiliza resultados anteriores, por lo que cada llamada de función se bifurca a dos llamadas nuevas, a menos que se haya alcanzado uno de los casos cero. Esto da el peor de los casos de llamadas de función 2 ^ 21-1 que toma 30 segundos en mi máquina.

Solución en serie de fuerza de luz (45 caracteres):

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

J, 55 caracteres

(wd@(4 :'(y^x)--/(!&y*^&x)|.i.y')/@".@,&'x');._2(1!:1)3
  • Pasa los casos de prueba actuales. Yo creo que entiendo las matemáticas ...
  • j602, solo consola ( wd). Entrada en stdin, salida en stdout.

Script de prueba de Bash:

jconsole disballs.ijs <<END
12 4
6 3
END
Jesse Millikan
fuente
¿Qué hace ese j6xx wd?
JB
Realmente quise decir j602 ... Supongo que también está en j601. Se define como echo, que se define como 0 0&$@(1!:2&2). No estoy seguro de lo que eso significa, pero hace algo así como elementos bonitos de rango 1 con un salto de línea. (Ahora mismo me doy cuenta de que usa 2 en lugar de 4 ... Creo que al menos sigue siendo estándar en modo consola).
Jesse Millikan
Tengo problemas para ejecutar este código. ¿Solo lo escribo en la consola?
mellamokb
@mellamokb He usado algo como el script de prueba anterior, con el programa guardado como disballs.ijs y la ruta correcta a j602 / bin / jconsole.
Jesse Millikan
@Jesse: estoy ejecutando esto en Windows. Lo << was unexpected at this time. siento, soy nuevo en la entrada J, siempre la usé en modo consola.
mellamokb
2

Golfscript - 26 caracteres

Advertencia: el caso 12 4 necesita mucha memoria (aunque no tanto como la respuesta a continuación) y tarda bastante en ejecutarse

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

Obviamente esta respuesta tiene algunos problemas, pero la dejaré aquí porque los comentarios se refieren a ella y la respuesta de mellamokb se basa en ella.

Golfscript - 24 caracteres

Advertencia: el caso 12 4 necesita mucha memoria y tarda bastante en ejecutarse

~:o)\?,{o)base[0]-,o=},,
gnibbler
fuente
2
No puedo entender cómo se te ocurrió ese código, no solo este método se quedará sin memoria para entradas grandes, sino que tampoco puedo entender para qué son buenos los operadores de incremento. Que realmente alcances el objetivo durante 6 3 parece ser nada más que suerte.
aaaaaaaaaaaa
¡Eso no es payaso, es mi esposa!
Jesse Millikan
2
No entiendo Golfscript, pero como dijiste y estoy de acuerdo, tu enfoque es demasiado lento.
Quixotic
3
@mellamokb, bien por ti para resolver cómo se suponía que debía funcionar :) Solo tomó 2 caracteres adicionales para solucionar ese error. Ahora estamos en el área turbia donde el código más corto puede ser correcto pero no práctico. Code-golf está plagado de respuestas increíblemente ineficientes, pero los microsegundos frente a segundos generalmente no importan. Este es un caso extremo ( mucha memoria también). Debanjan ha indicado que las respuestas deben ser más rápidas, pero este sitio no es SPOJ, esta pregunta está etiquetada code-golf
gnibbler
1
@gnibbler, 0 0debería producir 1; 0 kpor cualquier otro kdebe producir 0; n 1para n > 0debe producir 1.
Peter Taylor
2

Python 140 Chars

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())))
fR0DDY
fuente
2

dc, 100 caracteres

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

Por desgracia, dc no parece estar respaldado por ideone. Puede haber un personaje o dos para exprimir, pero es hora de acostarse.

Nota: esto admite múltiples líneas de entrada, tiene la precisión suficiente para dar la salida correcta incluso para 20 19(¡maldito seas, Perl, por el tiempo que desperdicié depurando mi solución!), Y da la salida correcta para 0 0.

Las sugerencias de Nabb permiten acortar al menos hasta

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

a costa de dejar basura en las pilas de registros (y así quedarse sin memoria si calculamos miles de millones de respuestas).

Peter Taylor
fuente
Los registros son siempre caracteres únicos (puede usar cualquier carácter, lo que hará que el código sea más legible), por lo que l11se analiza como l1 1(puede usarlo Kcomo un token de carácter único 0si no va a cambiar la precisión de todos modos). Puede cambiar el bucle de entrada a ?[...?z1=4]. Puede alinear la macro en el registro 1. Y probablemente puedas guardar muchos más personajes en general, pero esperaré a que sea más corto para comprenderlo.
Nabb
@Nabb, ah, no leí la página del manual con suficiente cuidado. Solo estoy usando 8 o 9 registros, por lo que no me encontré con las consecuencias de mi malentendido. Gracias.
Peter Taylor
1

Golfscript (28 31 37 )

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

Modificación a gnibblerla solución GolfScript. Creo que esta es una solución que funciona, probada con [3,2], [4,2], [6,3] y [9,2] con las respuestas correctas. (Utilicé $y @para variables para ajustar el espacio alrededor de la basepalabra clave).

Hay dos problemas con gnibblerla solución actual.

  1. Comprobar la longitud después de eliminar [0] no garantiza una solución, porque [1,1,1,1] sería válido para la entrada [4,2], aunque las 4 bolas estén en la misma celda (1). Así que he modificado para verificar también que se utilizan todos los dígitos, es decir, la matriz contiene 1-2, por lo que cada celda contiene al menos una bola.
  2. En el caso de la entrada [4,2], el formato base-3 de los números 0-27 tiene menos de 4 dígitos, y los 0 más a la izquierda no están incluidos. Eso significa que [1,1] se incluye como una solución válida, aunque técnicamente es en realidad [0,0,1,1], lo que significa que las dos primeras bolas no se colocan en ningún lado. Arreglo agregando 3 ^ 3 a cada entrada (genéricamente k ^ n-1 a la matriz de k ^ n entradas) para que las primeras entradas se desplacen hacia arriba para tener al menos n dígitos en formato base-k, y el último las entradas serán automáticamente inválidas de todos modos y no afectarán la solución (porque el segundo dígito siempre será 0).

Editar

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

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

¡Mejor solución todavía! No es necesario incrementar, solo agregue a todos los números para que comiencen con [1], y no faltarán dígitos (incluido el relleno izquierdo de 0) una vez que descontamine ese primer dígito. Esta solución debería funcionar y se ha probado con las mismas entradas anteriores. También es mucho más rápido porque no estamos incrementando antes de tomar exponente para generar la matriz (pero aún sufre el mismo problema de rendimiento / memoria para entradas más grandes).

Editar : Use gnibblerla idea de mover la adición del $interior del filtro en lugar de como un paso adicional. (guardar 3 caracteres)

mellamokb
fuente
Saltos en la entrada 0 0.
Peter Taylor
También parece manejar solo una línea de entrada.
Peter Taylor
Y se rompe n 1por cualquier n, hace que se cuelgue. hmm ..
mellamokb
1
convertir números a base 1 hará eso :)
gnibbler
@gnibbler: ¿Tienes alguna sugerencia? ¿Tendré que agregar algunas declaraciones if al principio para detectar esos casos? Parece que perderé mucho terreno de esa manera.
mellamokb
0

05AB1E , 19 bytes

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

NOTA: Es extremadamente lento y ya agota el tiempo de espera 12 4. Sin embargo, está funcionando según lo previsto. Veré si puedo encontrar un método alternativo que funcione para todos los casos de prueba en un tiempo razonable. Vea a continuación una versión mucho más rápida que ejecuta todos los casos de prueba en menos de un segundo.

Pruébelo en línea o verifique algunos casos de prueba más (de los más pequeños) .

Explicación:

#               # 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 bytes

Aquí una versión mucho más rápida que funciona para todos los casos de prueba en aproximadamente 0.5 segundos en TIO:

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

La respuesta de JavaScript del puerto de @mellamokb , ¡así que asegúrese de votarlo!

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

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

NOTA: Funciona para el caso de borde 0 0en este caso (a diferencia de la respuesta de JavaScript de la que porté este método), porque el Lincorporado creará una lista [0,1].

Kevin Cruijssen
fuente