Podziękowania dla Geobitów w TNB za pomysł

Postu bez dostatecznej szczegółowości niedawno zakładał ciekawą grę:

2 dzieci siedzą przed tablicą cukierków. Każdy kawałek cukierka jest ponumerowany od 1 do x, przy xczym całkowita ilość cukierków jest obecna. Występuje dokładnie 1 wystąpienie każdej liczby.

Celem gry jest zjedzenie przez dzieci słodyczy i pomnożenie wartości zjedzonych przez nich cukierków, aby osiągnąć końcowy wynik, przy czym wygrywa wyższy wynik.

Jednak w oryginalnym poście brakowało kluczowych informacji, takich jak sposób wybierania cukierków, więc dzieci w naszej historii zdecydowały, że starsze dziecko pójdzie pierwsze i będzie mogło zjeść do połowy słodyczy, jednak gdy ogłosi koniec swojej tury, nie może zmienić zdania.

Jedno z dzieciaków w tej grze nie lubi słodyczy, więc chce jeść tak mało, jak to możliwe, i raz widział, jak tata pisze kod, i uważa, że ​​może wykorzystać nabyte umiejętności, aby obliczyć, ile słodyczy musi jeść, aby zapewnić sobie zwycięstwo, a jednocześnie jeść jak najmniej.

Wyzwanie

Biorąc pod uwagę całkowitą liczbę cukierków x, twój program lub funkcja powinna wydać najmniejszą ilość cukierków, jaką musi zjeść, aby zapewnić zwycięstwo n, nawet jeśli jego przeciwnik zje wszystkie pozostałe cukierki.

Naturalnie większe liczby tworzą większe liczby, więc bez względu na to, ile mu dasz, zje nnajwięcej.

Zasady

• xzawsze będzie dodatnią liczbą całkowitą w zakresie, w 0 < x! <= lktórym lznajduje się górna granica możliwości obsługi liczb w Twoim języku
• Gwarantujemy, że dziecko będzie zawsze jeść nnajwięcej, na przykład dla x = 5i n = 2będzie jeść 4i5

Przypadki testowe

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

Punktacja

Niestety, nasz dzielny zawodnik nie ma nic do pisania kodu, więc musi ułożyć kawałki cukierków w znaki kodu, w wyniku czego twój kod musi być tak mały, jak to możliwe, najmniejszy kod w bajtach wygrywa!

Python 3 , 76 bajtów

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)

Wypróbuj online!

Opiera się na tym, że za zjedzenie $n$ cukierków, aby wygrać, a całkowita liczba cukierków wynosi $x$ , $\frac{x!}{(x-n)!}>(x-n)!$musi być prawdą, co oznacza$x!>((x-n)!)^2$ .

-1 od Skidsdev

-3 -6 z BMO

-3 od Sparr

+6 do naprawienia x = 1

JavaScript (ES6), 53 bajty

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

Wypróbuj online!

Zakres pracy

Co ciekawe, różnice między produktami dla dzieci są zawsze na tyle duże, że utrata precyzji związana z kodowaniem IEEE 754 nie stanowi problemu.

W rezultacie działa dla $0 \le n \le 170$ . Poza tym zarówno mantysa, jak i przepełnienie wykładnika (wydajność + Nieskończoność ) i potrzebowalibyśmy BigInts (+1 bajt).

W jaki sposób?

Niech $p$ będzie produktem cukierkowym drugiego dziecka i niech $q$ będzie naszym własnym produktem cukierkowym.

1. Zaczynamy od $p=n!$(wszystkie cukierki dla drugiego dziecka) i $q=1$ (nic dla nas).

2. Powtarzamy następujące operacje, aż $q\ge p$ :

   • podziel $p$ przez $n$
   • pomnóż $q$ przez $n$
   • zmniejszenie $n$

Wynikiem jest liczba wymaganych iteracji. (Przy każdej iteracji „bierzemy następny najwyższy cukierek od drugiego dziecka”).

Skomentował

Jest to zaimplementowane jako pojedyncza funkcja rekurencyjna, która najpierw oblicza $n!$a następnie wchodzi w pętlę opisaną powyżej.

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

Galaretka , 9 bajtów

ḊPÐƤ<!€TL

Wypróbuj online! Lub zobacz pakiet testowy .

W jaki sposób?

Ḋ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 bajtów

-29, ponieważ Dennis zna wszystkie funkcje wewnętrzne

-3 przejście do wejścia scan ()

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

Wypróbuj online!

Dość prosta implementacja R odpowiedzi Python3 na nedla2004 .

Wydaje mi się, że jest czystsza implementacja obsługi 1 i chciałbym stracić nawiasy klamrowe.

Jestem wściekły, że nie wróciłem do tego, które podejście, bardziej wściekłe, że zastosowałem mniej niż, ale jeszcze bardziej wściekłe, że nie wiedziałem, że jest jakaś cumprod()funkcja. Świetna optymalizacja Dennisa.

APL (Dyalog Unicode) , 10 bajtów

+/!≤2*⍨!∘⍳

Wypróbuj online!

Odpowiedź Portu Dennisa . Dzięki, cóż, Dennisowi za to.

W jaki sposób:

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

Ponieważ ta odpowiedź nie była przeze mnie ściśle udzielona, ​​poniżej zachowam oryginalną odpowiedź.

APL (Dyalog Unicode) , 14 12 11 bajtów

(+/!>×\)⌽∘⍳

Wypróbuj online!

Funkcja ukrywania przedrostka. Zasadniczo port Dyalog odpowiedzi Jonathana .

Dzięki ngn i H.PWiz za pomoc na czacie. Dzięki ngn również za uratowanie mi bajtu.

Dzięki Dennisowi za wskazanie, że mój oryginalny kod był nieprawidłowy. Okazuje się, że zaoszczędził mi 2 bajty.

Zastosowania ⎕IO←0.

W jaki sposób:

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

Stosując proste podejście: Sprawdzamy, czy produkt ostatniego $n$ liczby, czyli $\frac{x!}{(x-n)!}$ jest mniejszy niż iloczyn pierwszego $n$ liczby, a mianowicie $(x-n)!$ i bierze najmniej $n$ dla których to prawda.

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

Wypróbuj online!

Galaretka , 7 bajtów

R!²<!ċ0

Wypróbuj online!

Jak to działa

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]

Try it online!

It's is a lot faster than some other solutions - 0(N) multiplications instead of O(N²) - but I can't manage to reduce code size.

-27 from Jo King

Clean, 57 bytes

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

Try it online!

A straight-forward solution.

05AB1E, 15 11 bytes

E!IN-!n›iNq

Try it 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

Uses the same approach as my Python submission. Very new to 05AB1E so any tips on code or explaination greatly appreciated.

-4 bytes thanks to Kevin Cruijssen

Jelly, 14 bytes

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

Try it online!

Handles 1 correctly.

Charcoal, 20 bytes

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

Try it online! Link is to verbose version of code. Explanation:

Ｎθ                      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

Product on an empty list in Charcoal returns None rather than 1, so I have to logically Or it.

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;

Try it online!

Uses the same $x^2>((x-1)!)^2$ method as others have used.

Uses the factorial function from the PHP submission for this challenge (thanks to @donutdan4114)

Wolfram Language (Mathematica), 43 bytes

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

Try it online!

05AB1E, 7 bytes

L!ns!@O

Port of Dennis♦' Jelly answer, so make sure to upvote him if you like this answer!

Try it online or verify all test cases.

Explanation:

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 of Dennis' Jelly solution.

Only works in practice up to n=4 as we get into scientific notation above that.

õÊ®²¨U²

Try it

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

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

Try it online!

Based off of @Arnauld's javascript answer.

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

Try it online!

Edit: trading bytes against mults, no doing 2*x mults instead of x+n

Edit: moving back to int instead of long through macro. Would fail at 34 with long.

Well I have this in C. Fails at 21.

There is a possible ambiguity as to whether the good kid wants to always win or never lose... what do you think?

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

Try it online!

74 bytes version

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

but this version overflowed for 500...