Dank an Geobits in TNB für die Idee

Ein Post ohne ausreichende Details hat kürzlich ein interessantes Spiel aufgestellt:

2 Kinder sitzen vor einer Reihe von Süßigkeiten. Jedes Bonbonstück ist mit 1 bis 1 nummeriert x, xwobei die Gesamtmenge der vorhandenen Bonbons angegeben ist. Es gibt genau 1 Vorkommen von jeder Zahl.

Das Ziel des Spiels ist es, dass die Kinder Süßigkeiten essen und die Werte der Süßigkeiten, die sie gegessen haben, multiplizieren, um zu einer endgültigen Punktzahl zu gelangen, wobei die höhere Punktzahl gewinnt.

In der ursprünglichen Veröffentlichung fehlten jedoch wichtige Informationen wie die Auswahl der Süßigkeiten, sodass die Kinder in unserer Geschichte entschieden haben, dass das ältere Kind zuerst gehen und bis zur Hälfte der Süßigkeiten essen kann. er kann seine Meinung nicht ändern.

Eines der Kinder in diesem Spiel mag keine Süßigkeiten, deshalb möchte er so wenig wie möglich essen, und er hat einmal seinem Vater beim Schreiben von Code zugesehen. Er kann die daraus gewonnenen Fähigkeiten nutzen, um herauszufinden, wie viel Süßigkeiten vorhanden sind Er muss essen, um den Sieg zu sichern, während er immer noch so wenig wie möglich isst.

Die Herausforderung

Angesichts der Gesamtzahl der Süßigkeiten xsollte Ihr Programm oder Ihre Funktion die kleinste Menge Süßigkeiten ausgeben, die er essen muss, um den Sieg zu sichern.n , auch wenn sein Gegner alle verbleibenden Süßigkeiten isst.

Natürlich machen größere Zahlen größere Zahlen. Egal, wie viel du ihm gibst, er wird das essen n größten Zahlen.

Die Regeln

• xwird immer eine positive ganze Zahl in dem Bereich sein, 0 < x! <= lin deml die Obergrenze der Funktionen zur Verarbeitung von Zahlen in Ihrer Sprache liegt
• Es ist garantiert, dass das Kind immer die ngrößten Mengen isst , zum Beispiel für x = 5und n = 2, er wird essen 4und5

Testfälle

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

Wertung

Leider hat unser tapferer Kandidat nichts, womit er seinen Code schreiben kann, also muss er die Bonbonstücke in die Zeichen des Codes einordnen. Daher muss Ihr Code so klein wie möglich sein, der kleinste Code in Bytes gewinnt!

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)

Probieren Sie es online!

Verlässt sich auf die Tatsache, dass für das Essen $n$ Süßigkeiten noch gewinnen und die Gesamtzahl der Süßigkeiten $x$ , $\frac{x!}{(x-n)!}>(x-n)!$muss wahr sein, wasxbedeutet! >((x-n)!)2$x!>((x-n)!)^2$ .

-1 von Skidsdev

-3 -6 von BMO

-3 von Sparr

+6 zu beheben x = 1

JavaScript (ES6), 53 Byte

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

Probieren Sie es online!

Arbeitsbereich

Interessanterweise sind die Unterschiede zwischen den Produkten der Kinder immer so groß, dass der mit der IEEE 754-Codierung verbundene Genauigkeitsverlust kein Problem darstellt.

Infolgedessen funktioniert es für $0 \le n \le 170$ . Darüber hinaus laufen sowohl die Mantisse als auch der Exponent über (was + Infinity ergibt ), und wir benötigen BigInts (+1 Byte).

Wie?

Sei $p$ das Süßigkeitenprodukt des anderen Kindes und sei $q$ unser eigenes Süßigkeitenprodukt.

1. Wir beginnen mit $p=n!$(alle Süßigkeiten für das andere Kind) und $q=1$ (nichts für uns).

2. Wir wiederholen die folgenden Operationen bis $q\ge p$ :

   • dividiere $p$ durch $n$
   • $q$ mit n multiplizieren$n$
   • Dekrement $n$

Das Ergebnis ist die Anzahl der erforderlichen Iterationen. (Bei jeder Iteration nehmen wir dem anderen Kind die nächsthöhere Süßigkeit.)

Kommentiert

Dies wird als einzelne rekursive Funktion implementiert, die zuerst $n!$ berechnet ! und betritt dann die oben beschriebene Schleife.

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

Gelee , 9 Bytes

ḊPÐƤ<!€TL

Probieren Sie es online! Oder sehen Sie sich die Testsuite an .

Wie?

Ḋ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

R , 70 41 38 Bytes

-29 weil Dennis alle internen Funktionen kennt

-3 Umschalten auf die Eingabe scan ()

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

Probieren Sie es online!

Ziemlich einfache R-Implementierung der Python3- Antwort von nedla2004 .

Ich habe das Gefühl, dass es eine sauberere Implementierung des 1-Handlings gibt, und ich möchte die geschweiften Klammern verlieren.

Ich bin wütend, dass ich nicht zurückgegangen bin, um welchen Ansatz es sich handelt, und noch wütender, dass ich nicht wusste, dass es eine cumprod()Funktion gibt. Tolle Optimierung von Dennis.

APL (Dyalog Unicode) , 10 Bytes

+/!≤2*⍨!∘⍳

Probieren Sie es online!

Port of Dennis 'Antwort . Danke an Dennis dafür.

Wie:

+/!≤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.

Da diese Antwort nicht von mir stammt, behalte ich meine ursprüngliche Antwort unten.

APL (Dyalog Unicode) , 14 12 11 Bytes

(+/!>×\)⌽∘⍳

Probieren Sie es online!

Präfix implizite Funktion. Grundsätzlich eine Dyalog-Portierung von Jonathans Antwort .

Danke an ngn und H.PWiz für die Hilfe im Chat. Danke an ngn, dass du mir auch ein Byte gespart hast.

Vielen Dank an Dennis für den Hinweis, dass mein ursprünglicher Code falsch war. Es stellte sich heraus, dass mir 2 Bytes gespart wurden.

Verwendet ⎕IO←0.

Wie:

+/(!>×\)∘⌽∘⍳ ⍝ 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.

Haskell , 52 51 Bytes

Mit dem einfachen Ansatz: Wir prüfen, ob das Produkt der letzten $n$ Zahlen, das ist $\frac{x!}{(x-n)!}$ ist weniger als das Produkt des ersten $n$ Zahlen, nämlich $(x-n)!$ und nimmt am wenigsten $n$ für die dies wahr ist.

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

Probieren Sie es online!

Gelee , 7 Bytes

R!²<!ċ0

Probieren Sie es online!

Wie es funktioniert

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.

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]

Probieren Sie es online!

Es ist viel schneller als einige andere Lösungen - 0 (N) Multiplikationen anstelle von O (N²) - aber ich kann es nicht schaffen, die Codegröße zu reduzieren.

-27 von Jo King

Sauber , 57 Bytes

import StdEnv
$x=while(\e=prod[1..x-e]^2>prod[1..x])inc 1

Probieren Sie es online!

Eine einfache Lösung.

05AB1E , 15 11 Bytes

E!IN-!n›iNq

Probieren Sie es online!

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

Verwendet den gleichen Ansatz wie meine Python- Übermittlung. In 05AB1E sehr neu, daher sind alle Tipps zu Code oder Erklärungen sehr willkommen.

-4 Bytes dank Kevin Cruijssen

Jelly , 14 Bytes

ạ‘rP>ạ!¥
1ç1#«

Probieren Sie es online!

Behandelt 1 richtig.

Holzkohle , 20 Bytes

ＮθＩ⊕ΣＥθ‹Π⊕…ιθ∨Π…¹⊕ι¹

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

Ｎθ                      Input `n`
    Σ                   Sum of
      θ                 `n`
     Ｅ                  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
  Ｉ                     Cast to string
                        Implicitly print

Productauf einer leeren Liste in Charcoal kehrt Noneeher als 1, also muss ich es logisch Ormachen.

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;

Probieren Sie es online!

Verwendet das gleiche $x^2>((x-1)!)^2$ Methode, wie andere verwendet haben.

Verwendet die Fakultätsfunktion aus der PHP- Übermittlung für diese Herausforderung (danke an @ donutdan4114)

Wolfram Language (Mathematica) , 43 Byte

Min[n/.Solve[#!>(#-n)!^2, Integers]]/.n->1&

Probieren Sie es online!

05AB1E , 7 Bytes

L!ns!@O

Port of Dennis ♦ 'Jelly antworte , also stelle sicher, dass du ihn positiv bewertest, wenn dir diese Antwort gefällt!

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Erläuterung:

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)

Japt -x , 7 Bytes

Port von Dennis 'Jelly-Lösung.

Funktioniert in der Praxis nur bis zu n=4dem Punkt, an dem wir uns darüber mit wissenschaftlicher Notation befassen.

õÊ®²¨U²

Versuch es

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

C # (.NET Core) , 93 Byte

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;}}

Probieren Sie es online!

Basierend auf der JavaScript-Antwort von @ Arnauld.

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;}

Probieren Sie es online!

Edit: tausche Bytes gegen Mults, mache keine 2 * x Mults anstelle von x + n

Bearbeiten: Zurück zu int anstelle von long through macro. Würde bei 34 mit lang ausfallen.

Nun, ich habe dies in C. Scheitert am 21.

Es gibt eine mögliche Unklarheit, ob das gute Kind immer gewinnen oder nie verlieren will ... was denkst du?

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

Probieren Sie es online!

74-Byte-Version

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

aber diese Version lief für 500 über ...