¿Cuántos dulces puedes comer?

14

Crédito a Geobits en TNB por la idea

Una publicación sin suficientes detalles recientemente presentó un juego interesante:

2 niños se sientan frente a una variedad de dulces. Cada pieza de dulce está numerada del 1 al x, xsiendo la cantidad total de dulce presente. Hay exactamente 1 aparición de cada número.

El objetivo del juego es que los niños coman dulces y multipliquen los valores de los dulces que han comido para llegar a un puntaje final, ganando el puntaje más alto.

Sin embargo, la publicación original omitió información clave, como cómo se seleccionan los dulces, por lo que los niños de nuestra historia decidieron que el niño mayor es el primero y puede comer hasta la mitad de los dulces, sin embargo, una vez que anuncia el final de su turno, No puede cambiar de opinión.

A uno de los niños en este juego no le gustan los dulces, por lo que quiere comer lo menos posible, y una vez vio a su padre escribir un código una vez, y cree que puede usar las habilidades obtenidas de eso para calcular la cantidad de dulces necesita comer para asegurar la victoria, mientras sigue comiendo lo menos posible.

El reto

Dada la cantidad total de dulces x, su programa o función debería generar la menor cantidad de dulces que tiene que comer para garantizar la victoria n, incluso si su oponente se come todos los dulces restantes.

Naturalmente, los números más grandes hacen números más grandes, así que sea cual sea la cantidad que le des, él se comerá los nnúmeros más grandes.

Las normas

  • xsiempre será un número entero positivo en el rango 0 < x! <= ldonde lestá el límite superior de las capacidades de manejo de números de su idioma
  • Se garantiza que el niño siempre comerá los nnúmeros más grandes, por ejemplo para x = 5y n = 2, comerá 4y5

Casos de prueba

x = 1
n = 1
(1 > 0)

x = 2
n = 1
(2 > 1)

x = 4
n = 2
(3 * 4 == 12 > 1 * 2 == 2)

x = 5
n = 2
(4 * 5 == 20 > 1 * 2 * 3 == 6)

x = 100
n = 42
(product([59..100]) > product([1..58]))

x = 500
n = 220
(product([281..500]) > product([1..280]))

Puntuación

Desafortunadamente, nuestro valiente concursante no tiene nada con lo que escribir su código, por lo que tiene que organizar los dulces en los caracteres del código, como resultado, su código debe ser lo más pequeño posible, ¡el código más pequeño en bytes gana!

Skidsdev
fuente
14
¿Cuántos dulces puedo comer? Todo ello. Todos los dulces.
AdmBorkBork
3
Nuevo título: "¿Cuántos dulces necesitas comer?"
Sparr
@Skidsdev x = 0También se debe manejar, 0! = 1¿ desde entonces ? (¿Quizás xtambién debería especificarse como un número entero positivo?)
Chronocidal
@Chronocidal agregó un entero "positivo"
Skidsdev
Tiré 10k piezas de dulces al suelo. Una pequeña figura cavó un hoyo en el suelo y encontró una caverna gigante de dulces por mi culpa. ):
moonheart08

Respuestas:

9

Python 3 , 76 bytes

F=lambda x:x<2or x*F(x-1)
f=lambda x,n=1:x<2or n*(F(x)>F(x-n)**2)or f(x,n+1)

Pruébalo en línea!

Se basa en el hecho de que para comer norte caramelos aún gana y el número total de caramelos es X , X!(X-norte)!>(X-norte)!debe ser cierto, lo que significaX!>((X-norte)!)2.

-1 de Skidsdev

-3 -6 de BMO

-3 de Sparr

+6 para arreglar x = 1

nedla2004
fuente
1
Puede guardar 1 byte reemplazando la función superior confrom math import factorial as F
Skidsdev
1
Puede reescribir estas recursiones utilizando un comportamiento de cortocircuito, por ejemplo. para el segundo: n*(F(x)>F(x-n)**2)or f(x,n+1). Del mismo modo x<2or x*F(x-1)para el primero que es más corto que la importación.
ბიმო
1
Las tres son buenas sugerencias, gracias. (Y agregado)
nedla2004
1
-3 bytes con los import math;F=math.factorialque probablemente debería buscar los meta consejos de Python para mencionar ...
Sparr
2
@Sparr: ¿Pero F=lambda x:x<2or x*F(x-1)son tres bytes menos?
ბიმო
5

JavaScript (ES6), 53 bytes

n=>(g=p=>x<n?g(p*++x):q<p&&1+g(p/n,q*=n--))(q=x=1)||n

Pruébalo en línea!

Rango de trabajo

Curiosamente, las diferencias entre los productos para niños siempre son lo suficientemente grandes como para que la pérdida de precisión inherente a la codificación IEEE 754 no sea un problema.

Como resultado, funciona para 0 0norte170 . Más allá de eso, tanto la mantisa como el exponente se desbordan (produciendo + Infinito ) y necesitaríamos BigInts (+1 byte).

¿Cómo?

Deje que pag sea ​​el producto dulce del otro niño y que q sea ​​nuestro propio producto dulce.

  1. Comenzamos con pag=norte!(todos los dulces para el otro niño) y q=1 (nada para nosotros).

  2. Repetimos las siguientes operaciones hasta qpag :

    • dividir pag por norte
    • multiplicar q por norte
    • decremento norte

El resultado es el número de iteraciones requeridas. (En cada iteración, 'tomamos el siguiente dulce más alto del otro niño').

Comentado

Esto se implementa como una sola función recursiva que primero calcula norte!y luego entra en el bucle descrito anteriormente.

n => (           // main function taking n
  g = p =>       // g = recursive function taking p
    x < n ?      //   if x is less than n:
      g(         //     this is the first part of the recursion:
        p * ++x  //     we're computing p = n! by multiplying p
      )          //     by x = 1 .. n
    :            //   else (second part):
      q < p &&   //     while q is less than p:
      1 + g(     //       add 1 to the final result
        p / n,   //       divide p by n
        q *= n-- //       multiply q by n; decrement n
      )          //
)(q = x = 1)     // initial call to g with p = q = x = 1
|| n             // edge cases: return n for n < 2
Arnauld
fuente
4

Jalea , 9 bytes

ḊPÐƤ<!€TL

Pruébalo en línea! O vea el conjunto de pruebas .

¿Cómo?

ḊPÐƤ<!€TL - Link: integer, x                   e.g. 7
Ḋ         - dequeue (implicit range of x)           [   2,   3,   4,   5,   6,   7]
  ÐƤ      - for postfixes [all, allButFirst, ...]:
 P        -   product                               [5040,2520, 840, 210,  42,   7]
      €   - for each (in implicit range of x):
     !    -   factorial                             [   1,   2,   6,  24, 120, 720, 5040]
    <     - (left) less than (right)?               [   0,   0,   0,   0,   1,   1, 5040]
          -   -- note right always 1 longer than left giving trailing x! like the 5040 ^
       T  - truthy indices                          [                       5,   6, 7   ]
        L - length                                  3
Jonathan Allan
fuente
1
eso es impresionante, pero sería más educativo si se explicara
Setop 12/12/18
Será ... :)
Jonathan Allan
@Setop - agregado.
Jonathan Allan
gusta ! y debe ser rápido en comparación con todas las soluciones con toneladas de factoriales
Setop 12/1218
No, todavía calcula todos esos productos y factoriales (más que algunas otras soluciones).
Jonathan Allan
3

R , 70 41 38 bytes

-29 porque Dennis conoce todas las funciones internas

-3 cambio a entrada scan ()

sum(prod(x<-scan():1)<=cumprod(1:x)^2)

Pruébalo en línea!

Implementación R bastante simple de la respuesta Python3 de nedla2004 .

Siento que hay una implementación más limpia del manejo de 1, y me gustaría perder las llaves.

Estoy enojado porque no volví a usar ese enfoque, más enojado porque usé un estricto menor que, pero aún más enojado porque no sabía que había una cumprod()función. Gran optimización por Dennis.

Criminalmente vulgar
fuente
3

APL (Dyalog Unicode) , 10 bytes

+/!≤2*⍨!∘⍳

Pruébalo en línea!

La respuesta del puerto de Dennis . Gracias a, bueno, Dennis por ello.

Cómo:

+/!≤2*⍨!∘⍳  Tacit function, takes 1 argument (E.g. 5)
           Range 1 2 3 4 5
       !∘   Factorials. Yields 1 2 6 24 120
    2*⍨     Squared. Yields 1 4 36 576 14400
  !         Factorial of the argument. Yields 120.
           Less than or equal to. Yields 0 0 0 1 1
+/          Sum the results, yielding 2.

Como esta respuesta no fue estrictamente hecha por mí, conservaré mi respuesta original a continuación.


APL (Dyalog Unicode) , 14 12 11 bytes

(+/!>×\)⌽∘⍳

Pruébalo en línea!

Función de prefijo tácito. Básicamente un puerto Dyalog de la respuesta de Jonathan .

Gracias a ngn y H.PWiz por la ayuda en el chat. Gracias a ngn también por salvarme un byte.

Gracias a Dennis por señalar que mi código original estaba equivocado. Resulta que me ahorró 2 bytes.

Usos ⎕IO←0.

Cómo:

+/(!>×\)∘⌽∘⍳  Tacit function, taking 1 argument (E.g. 5).
             Range 0 1 2 3 4
         ⌽∘   Then reverse, yielding 4 3 2 1 0
  (    )∘     Compose with (or: "use as argument for")
   !          Factorial (of each element in the vector), yielding 24 6 2 1 1
     ×\       Multiply scan. Yields 4 12 24 24 0
    >         Is greater than. Yields 1 0 0 0 1
+/            Finally, sum the result, yielding 2.
J. Sallé
fuente
1
si +/va dentro de los paréntesis, una de las composiciones se pueden omitir:(+/!>×\)⌽∘⍳
ngn
2

Haskell , 52 51 bytes

norteX!(X-norte)!norte(X-norte)!norte

g b=product[1..b]
f x=[n|n<-[1..],g(x-n)^2<=g x]!!0

Pruébalo en línea!

falla
fuente
2

Jalea , 7 bytes

R!²<!ċ0

Pruébalo en línea!

Cómo funciona

R!²<!ċ0  Main link. Argument: n

R        Range; yield [1, ..., n].
 !       Map factorial over the range.
  ²      Take the squares of the factorials.
    !    Compute the factorial of n.
   <     Compare the squares with the factorial of n.
     ċ0  Count the number of zeroes.
Dennis
fuente
2

Python 3 , 183 176 149 bytes

R=reversed
def M(I,r=1):
 for i in I:r*=i;yield r
def f(x):S=[*range(1,x+1)];return([n for n,a,b in zip([0]+S,R([*M(S)]),[0,*M(R(S))])if b>a]+[x])[0]

Pruébalo en línea!

Es mucho más rápido que otras soluciones: multiplicaciones 0 (N) en lugar de O (N²), pero no puedo reducir el tamaño del código.

-27 de Jo King

Setop
fuente
1

05AB1E , 15 11 bytes

E!IN-!n›iNq

Pruébalo en línea!

E!IN-!n›iNq

E                For loop with N from [1 ... input]
 !               Push factorial of input    
  IN-            Push input - N (x - n)
     !           Factorial
      n          Square
       ›         Push input! > (input - N)^2 or x! > (x - n)^2
        i        If, run code after if top of stack is 1 (found minimum number of candies)
         N       Push N
          q      Quit, and as nothing has been printed, N is implicitly printed

Utiliza el mismo enfoque que mi Python envío de . Muy nuevo en 05AB1E, por lo que cualquier sugerencia sobre código o explicación es muy apreciada.

-4 bytes gracias a Kevin Cruijssen

nedla2004
fuente
¡Buena respuesta! Puedes jugar golf 3 bytes como este sin romper la entrada 1. Si la declaración if es verdadera, empujará el índice Na la pila y saldrá del programa (generando ese índice implícitamente). Para la entrada, 1la instrucción if será falsey, pero generará su entrada 1implícitamente después de ese ciclo de iteración única.
Kevin Cruijssen
1
En realidad, se pueden guardar 4 bytes en lugar de 3: Pruébelo en línea 11 bytes . La entrada se usará implícitamente para el primer factorial !, ahora que la pila está vacía ya que ya no duplicamos / triplicamos el resultado if.
Kevin Cruijssen
1
Gracias por estas ideas. Aunque no llegué a esta idea de imprimir al final, sí pensé en terminar el ciclo for temprano. Después de buscar descanso, finalización, abandono y escape, pensé que no estaba entendiendo la forma en que los bucles funcionan correctamente. De alguna manera terminar nunca se me ocurrió.
nedla2004
1
Tu respuesta ya fue bastante buena. Por lo general, es más fácil jugar una respuesta existente, luego jugarla tú mismo de la nada. Si hubiera hecho este desafío yo mismo, probablemente también habría terminado en 15 o 14 bytes. Usé su idea de romper y lo reemplacé con una salida terminada e implícita, después de eso probé algunas cosas y al final vi que ya no necesitaba el duplicado, lo que también solucionaría el caso de prueba que 1genera la entrada implícitamente Cuando la pila está vacía. :)
Kevin Cruijssen
1
FYI: publiqué una alternativa de 7 bytes portando Dennis ♦ 'Jelly answer. Como siempre, Dennis ♦ es capaz de realizar magia en términos de golf de código Jelly ..; p
Kevin Cruijssen
0

Carbón de leña , 20 bytes

NθI⊕ΣEθ‹Π⊕…ιθ∨Π…¹⊕ι¹

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

Nθ                      Input `n`
    Σ                   Sum of
      θ                 `n`
     E                  Mapped over implicit range
        Π               Product of
           ι            Current value
          …             Range to
            θ           `n`
         ⊕              Incremented
       ‹                Less than
              Π         Product of
                ¹       Literal 1
               …        Range to
                  ι     Current value
                 ⊕      Incremented
             ∨          Logical Or
                   ¹    Literal 1
   ⊕                    Incremented
  I                     Cast to string
                        Implicitly print

Producten una lista vacía en el carbón regresa en Nonelugar de 1, así que tengo que lógicamente Or.

Neil
fuente
¿Estás seguro de que estos personajes son de 8 bits cada uno?
RosLuP
@RosLuP Charcoal es uno de los muchos idiomas que puedes encontrar aquí que usa una página de códigos personalizada en lugar de, por ejemplo, ASCII. Esto significa que cada valor de ocho bits se asigna a un símbolo personalizado; estos símbolos están diseñados para ayudar al programador a recordar qué hace cada byte un poco más fácil que si se dispersaran aleatoriamente entre una de las páginas de códigos estandarizadas. No dude en solicitar más detalles en el chat PPCG .
Phlarx
0

PHP , 107 bytes

<?php $x=fgets(STDIN);function f($i){return $i==0?:$i*f($i-1);}$n=1;while(f($x)<f($x-$n)**2){$n++;}echo $n;

Pruébalo en línea!

Usa lo mismo X2>((X-1)!)2 método como otros han usado.

Utiliza la función factorial del envío de PHP para este desafío (gracias a @ donutdan4114)

NK1406
fuente
0

05AB1E , 7 bytes

L!ns!@O

Puerto de Dennis ♦ 'Jelly respuesta , ¡así que asegúrate de votarlo si te gusta esta respuesta!

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

Explicación:

L          # List in the range [1, (implicit) input]
 !         # Take the factorial of each
  n        # Then square each
   s!      # Take the factorial of the input
     @     # Check for each value in the list if they are larger than or equal to the
           # input-faculty (1 if truthy; 0 if falsey)
      O    # Sum, so determine the amount of truthy checks (and output implicitly)
Kevin Cruijssen
fuente
0

Japt -x, 7 bytes

Solución de gelatina del puerto de Dennis.

Solo funciona en la práctica hasta que n=4entramos en notación científica por encima de eso.

õÊ®²¨U²

Intentalo

õ           :Range [1,input]
 Ê          :Factorial of each
  ®         :Map
   ²        :  Square
    ¨       :  Greater than or equal to
     U²     :  Input squared
            :Implicitly reduce by addition
Lanudo
fuente
0

C # (.NET Core) , 93 bytes

n=>{int d(int k)=>k<2?1:k*d(k-1);int a=1,b=d(n),c=n;for(;;){a*=n;b/=n--;if(a>=b)return c-n;}}

Pruébalo en línea!

Basado en la respuesta de JavaScript de @ Arnauld.

Encarnación de la ignorancia
fuente
0

C (gcc) , 68 bytes

n;f(x){int i=2,j=x,b=1,g=x;while(i<j)b*i>g?g*=--j:(b*=i++);n=x-j+1;}

Pruébalo en línea!

Editar: intercambiando bytes contra mults, no hacer 2 * x mults en lugar de x + n

Editar: volver a int en lugar de largo a través de macro. Fallaría a los 34 con mucho tiempo.

Bueno, tengo esto en C. Falla a los 21.

Existe una posible ambigüedad en cuanto a si el niño bueno siempre quiere ganar o nunca perder ... ¿qué opinas?

Balzola
fuente
Por lo general, no permitimos que la forma en que ha definido T sea de ningún tipo. Puede obtener 72 bytes eliminando todas las referencias a T, pero debe reenviar la declaración de i / j / b / g. Pruébalo en línea!
LambdaBeta
OK, puse de nuevo la versión con int, que todavía tiene 68 bytes. Así que en realidad no estaba haciendo trampa;)
Balzola
Dejaría la versión T allí, así como una alternativa. Es interesante probar tipos más grandes / más pequeños. Buena presentación sin embargo!
LambdaBeta
0

Python 3 , 75 bytes

f=lambda n:n<1or f(n-1)*n
n=lambda x:x-sum(f(n)**2<f(x)for n in range(1,x))

Pruébalo en línea!

Versión de 74 bytes

f=lambda n:n<1or f(n-1)*n
n=lambda x:1+sum(f(n)>f(x)**.5for n in range(x))

pero esta versión se desbordó por 500 ...

david
fuente