14
\$\begingroup\$

Credit to Geobits in TNB for the idea

A post without sufficient detail recently posited an interesting game:

2 children sit in front of an array of candy. Each piece of candy is numbered 1 to x, with x being the total amount of candy present. There is exactly 1 occurrence of each number.

The goal of the game is for the children to eat candy and multiply the values of the candy they have eaten to arrive at a final score, with the higher score winning.

However the original post missed key information, such as how candy is selected, so the kids in our story decided that the older kid gets to go first, and can eat up to half the candy, however once he announces the end of his turn, he can't change his mind.

One of the kids in this game doesn't like candy, so he wants to eat as little as possible, and he once watched his dad write some code once, and figures he can use the skills gained from that to work out how much candy he needs to eat to ensure victory, whilst still eating as little as possible.

The Challenge

Given the total number of candy x, your program or function should output the smallest amount of candy he has to eat to ensure victory, n, even if his opponent eats all the remaining candy.

Naturally bigger numbers make bigger numbers, so whatever amount you'll give him, he'll eat the n largest numbers.

The Rules

  • x will always be a positive integer in the range 0 < x! <= l where l is the upper limit of your language's number handling capabilities
  • It is guaranteed that the kid will always eat the n largest numbers, for example for x = 5 and n = 2, he will eat 4 and 5

Test cases

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

Scoring

Unfortunately, our brave contestant has nothing to write his code with, so he has to arrange the pieces of candy into the characters of the code, as a result, your code needs to be as small as possible, smallest code in bytes wins!

\$\endgroup\$
  • 14
    \$\begingroup\$ How much candy can I eat? All of it. All of the candy. \$\endgroup\$ – AdmBorkBork Dec 12 '18 at 21:10
  • 3
    \$\begingroup\$ New title: "How much candy need you eat?" \$\endgroup\$ – Sparr Dec 12 '18 at 21:44
  • \$\begingroup\$ @Skidsdev Should x = 0 also be handled, since 0! = 1? (Perhaps x should also be specified as a Positive Integer?) \$\endgroup\$ – Chronocidal Dec 13 '18 at 12:00
  • \$\begingroup\$ @Chronocidal added "positive" integer \$\endgroup\$ – Skidsdev Dec 13 '18 at 14:07
  • \$\begingroup\$ I threw 10k pieces of candy on the ground. A little figure dug a hole into the ground and found a giant candy cavern because of me. ): \$\endgroup\$ – moonheart08 Dec 13 '18 at 14:54

19 Answers 19

9
\$\begingroup\$

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)

Try it online!

Relies on the fact that for eating \$n\$ candies to still win and the total number of candies being \$x\$, \$\frac{x!}{(x-n)!}>(x-n)!\$ must be true, which means \$x!>((x-n)!)^2\$.

-1 from Skidsdev

-3 -6 from BMO

-3 from Sparr

+6 to fix x = 1

\$\endgroup\$
  • 1
    \$\begingroup\$ You can save 1 byte by replacing the top function with from math import factorial as F \$\endgroup\$ – Skidsdev Dec 12 '18 at 21:31
  • 1
    \$\begingroup\$ You can rewrite these recursion using short-circuiting behaviour, eg. for the second one: n*(F(x)>F(x-n)**2)or f(x,n+1). Similarly x<2or x*F(x-1) for the first one which is shorter than the import. \$\endgroup\$ – ბიმო Dec 12 '18 at 21:37
  • 1
    \$\begingroup\$ All three of those are nice suggestions, thanks. (And added) \$\endgroup\$ – nedla2004 Dec 12 '18 at 21:40
  • 1
    \$\begingroup\$ -3 bytes with import math;F=math.factorial which I should probably go find the python tips meta to mention... \$\endgroup\$ – Sparr Dec 12 '18 at 21:51
  • 2
    \$\begingroup\$ @Sparr: But F=lambda x:x<2or x*F(x-1) is three bytes less? \$\endgroup\$ – ბიმო Dec 12 '18 at 21:58
2
\$\begingroup\$

Haskell, 52 51 bytes

Using the straightforward approach: We check whether the product of the last \$n\$ numbers, which is \$\frac{x!}{(x-n)!}\$ is less than the product of the first \$n\$ numbers, namely \$(x-n)!\$ and takes the least \$n\$ for which this is true.

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Nice answer! You can golf 3 bytes like this without breaking input 1. If the if-statement is truthy, it will push index N to the stack and exit the program (outputting that index implicitly). For input 1 the if-statement will be falsey, but it will output its input 1 implicitly after that single-iteration loop. \$\endgroup\$ – Kevin Cruijssen Dec 13 '18 at 9:35
  • 1
    \$\begingroup\$ Actually, 4 bytes can be saved instead of 3: Try it online 11 bytes. The input will be used implicitly for the first factorial !, now that the stack is empty since we no longer duplicate/triplicate the if-result. \$\endgroup\$ – Kevin Cruijssen Dec 13 '18 at 9:45
  • 1
    \$\begingroup\$ Thanks for these ideas. Although I didn't get to this idea of printing at the end, I did think of ending the for loop early. After looking for break, end, quit and escape, I just thought I wasn't understanding the way loops work correctly. Somehow terminate never occured to me. \$\endgroup\$ – nedla2004 Dec 13 '18 at 23:18
  • 1
    \$\begingroup\$ Your answer was already pretty good. It's usually easier to golf an existing answer further, then to golf it yourself from nothing. If I would have done this challenge myself I probably would have ended up at 15 or 14 bytes as well. I used your idea of breaking and replaced it with a terminate and implicit output instead, after that I tried a few things, and in the end I saw I didn't need the duplicate anymore, which would also fix test case 1 outputting the input implicitly when the stack is empty. :) \$\endgroup\$ – Kevin Cruijssen Dec 14 '18 at 7:53
  • 1
    \$\begingroup\$ FYI: I've posted a 7 bytes alternative by porting Dennis♦' Jelly answer. As always, Dennis♦ is able to perform magic in terms of Jelly code-golfing.. ;p \$\endgroup\$ – Kevin Cruijssen Dec 14 '18 at 12:54
5
\$\begingroup\$

JavaScript (ES6), 53 bytes

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

Try it online!

Working range

Interestingly, the differences between the kids' products are always big enough that the loss of precision inherent to IEEE 754 encoding is not an issue.

As a result, it works for \$0 \le n \le 170\$. Beyond that, both the mantissa and the exponent overflow (yielding +Infinity) and we'd need BigInts (+1 byte).

How?

Let \$p\$ be the candy product of the other kid and let \$q\$ be our own candy product.

  1. We start with \$p=n!\$ (all the candy for the other kid) and \$q=1\$ (nothing for us).

  2. We repeat the following operations until \$q\ge p\$:

    • divide \$p\$ by \$n\$
    • multiply \$q\$ by \$n\$
    • decrement \$n\$

The result is the number of required iterations. (At each iteration, we 'take the next highest candy from the other kid'.)

Commented

This is implemented as a single recursive function which first compute \$n!\$ and then enters the loop described above.

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Jelly, 14 bytes

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

Try it online!

Handles 1 correctly.

\$\endgroup\$
4
\$\begingroup\$

Jelly, 9 bytes

ḊPÐƤ<!€TL

Try it online! Or see the test-suite.

How?

Ḋ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
\$\endgroup\$
  • 1
    \$\begingroup\$ that's impressive but would be more educative if explained \$\endgroup\$ – Setop Dec 12 '18 at 22:52
  • \$\begingroup\$ It will be... :) \$\endgroup\$ – Jonathan Allan Dec 12 '18 at 22:53
  • \$\begingroup\$ @Setop - added. \$\endgroup\$ – Jonathan Allan Dec 12 '18 at 23:13
  • \$\begingroup\$ like it ! and it must be fast compare to all solutions with tons of factorials \$\endgroup\$ – Setop Dec 12 '18 at 23:17
  • \$\begingroup\$ Nah, still calculates all those products and factorials (more than some other solutions). \$\endgroup\$ – Jonathan Allan Dec 12 '18 at 23:29
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

Jelly, 7 bytes

R!²<!ċ0

Try it online!

How it works

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.
\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog Unicode), 10 bytes

+/!≤2*⍨!∘⍳

Try it online!

Port of Dennis' answer. Thanks to, well, Dennis for it.

How:

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

Since this answer wasn't strictly made by me, I'll keep my original answer below.


APL (Dyalog Unicode), 14 12 11 bytes

(+/!>×\)⌽∘⍳

Try it online!

Prefix tacit function. Basically a Dyalog port of Jonathan's answer.

Thanks to ngn and H.PWiz for the help in chat. Thanks to ngn also for saving me a byte.

Thanks to Dennis for pointing out that my original code was wrong. Turns out it saved me 2 bytes.

Uses ⎕IO←0.

How:

+/(!>×\)∘⌽∘⍳ ⍝ 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.
\$\endgroup\$
  • 1
    \$\begingroup\$ if +/ goes inside the parentheses, one the compositions can be omitted: (+/!>×\)⌽∘⍳ \$\endgroup\$ – ngn Dec 14 '18 at 18:49
3
\$\begingroup\$

R, 70 41 38 bytes

-29 because Dennis knows all the internal functions

-3 switching to scan() input

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

Try it online!

Pretty simple R implementation of nedla2004's Python3 answer.

I feel like there's a cleaner implementation of the 1-handling, and I'd like to lose the curly-braces.

I'm mad I didn't go back to using a which approach, madder that I used a strict less-than, but even madder still that I didn't know there's a cumprod() function. Great optimisation by Dennis.

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 20 bytes

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

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

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

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

\$\endgroup\$
  • \$\begingroup\$ Are you sure these characters are 8 bit each? \$\endgroup\$ – RosLuP Dec 13 '18 at 20:37
  • \$\begingroup\$ @RosLuP Charcoal is one of many languages you might find here that uses a custom code page instead of, say, ASCII. This means that each eight-bit value is mapped to a custom symbol; these symbols are designed to help the programmer remember what each byte does a little easier than if they were just randomly dispersed among one of the standardized code pages. Feel free to ask for more details in the PPCG chat. \$\endgroup\$ – Phlarx Dec 13 '18 at 21:14
0
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Typically we don't allow the way you've defined T to be any type. You can get 72 bytes by removing all references to T, but you have to forward declare i/j/b/g still. Try it online! \$\endgroup\$ – LambdaBeta Dec 17 '18 at 16:07
  • \$\begingroup\$ OK I put back the version with int, which is still 68 bytes. So I was not actually cheating ;) \$\endgroup\$ – Balzola Dec 17 '18 at 16:15
  • \$\begingroup\$ I'd leave the T version in there as well as an alternative. It's interesting to try out larger/smaller types. Good submission though! \$\endgroup\$ – LambdaBeta Dec 17 '18 at 17:14
0
\$\begingroup\$

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)

\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 43 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.