10
\$\begingroup\$

Write a program that, given a small positive even integer from standard input, calculates the probability that flipping that many coins will result in half as many heads.

For example, given 2 coins the possible outcomes are:

HH HT TH TT

where H and T are heads and tails. There are 2 outcomes (HT and TH) that are half as many heads as the number of coins. There are a total of 4 outcomes, so the probability is 2/4 = 0.5.

This is simpler than it looks.

Test cases:

2 -> 0.5
4 -> 0.375
6 -> 0.3125
8 -> 0.2734375
\$\endgroup\$
6
  • 1
    \$\begingroup\$ We can assume the coins are perfect and there's an even chance of getting heads or tails? \$\endgroup\$
    – Juan
    Feb 27, 2011 at 17:18
  • \$\begingroup\$ Do we need to print the output to stdout? \$\endgroup\$
    – Dogbert
    Feb 27, 2011 at 18:24
  • \$\begingroup\$ @Juan yes. @Dogbert yes. \$\endgroup\$
    – david4dev
    Feb 27, 2011 at 18:37
  • \$\begingroup\$ Could we get some more test cases to verify our solutions? \$\endgroup\$
    – Dogbert
    Feb 27, 2011 at 19:44
  • \$\begingroup\$ @Dogbert - done \$\endgroup\$
    – david4dev
    Feb 27, 2011 at 20:02

20 Answers 20

3
\$\begingroup\$

J, 22 19 (killer approach)

I got down to this while golfing my Haskell answer.

%/@:>:@i.&.(".@stdin)_

(same I/O as my other J answer)

\$\endgroup\$
2
  • \$\begingroup\$ This gives an error for me: 0 1|domain error: script | %/ >:i.&.(".@stdin)_ \$\endgroup\$
    – david4dev
    Mar 1, 2011 at 17:22
  • \$\begingroup\$ @david4dev Ouch. My leftover script file didn't work either. I don't remember where I messed up, but the version you tested is faulty indeed. It's now fixed. \$\endgroup\$
    – J B
    Mar 1, 2011 at 17:46
3
\$\begingroup\$

Pari/GP - 32 30 34 chars

print(binomial(n=input(),n\2)/2^n)
\$\endgroup\$
2
  • \$\begingroup\$ Wow, I didn't consider a programming language having a built in binomial function. \$\endgroup\$
    – david4dev
    Feb 27, 2011 at 18:38
  • \$\begingroup\$ 32 characters: print(binomial(n=input,n\2)/2^n). \$\endgroup\$
    – Charles
    Apr 28, 2015 at 14:49
3
\$\begingroup\$

Python 53 Characters

i=r=1.;exec"r*=(2*i-1)/i/2;i+=1;"*(input()/2);print r
\$\endgroup\$
3
\$\begingroup\$

Excel, 25

Not quite according to spec, though :)

Name a cell n and then type the following into another cell:

=COMBIN(n,n/2)/POWER(2,n)
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Excel actually implements the ^ properly, so you can cut out a few characters that way. \$\endgroup\$ Jun 8, 2015 at 20:40
3
\$\begingroup\$

Haskell, 39 43 46

main=do x<-readLn;print$foldr1(/)[1..x]

Demonstration:

$ runhaskell coins.hs <<<2
0.5
$ runhaskell coins.hs <<<4
0.375
$ runhaskell coins.hs <<<6
0.3125
$ runhaskell coins.hs <<<8
0.2734375
\$\endgroup\$
4
  • \$\begingroup\$ I get an error: Undefined variable "readln" \$\endgroup\$
    – david4dev
    Feb 28, 2011 at 16:42
  • \$\begingroup\$ @david4dev the 'L' in readLn is a capital one. \$\endgroup\$
    – J B
    Feb 28, 2011 at 16:54
  • \$\begingroup\$ I think main=do x<-readLn;print$foldr1(/)[1..x] does the same thing and saves 3 bytes? \$\endgroup\$
    – Lynn
    May 17, 2015 at 20:57
  • \$\begingroup\$ Indeed. Merging, thanks! \$\endgroup\$
    – J B
    May 27, 2015 at 21:30
2
\$\begingroup\$

J, 25 (natural approach)

((!~-:)%2&^)&.(".@stdin)_

Sample use:

$ echo -n 2 | jconsole coins.ijs 
0.5
$ echo -n 4 | jconsole coins.ijs
0.375
$ echo -n 6 | jconsole coins.ijs
0.3125
$ echo -n 8 | jconsole coins.ijs 
0.273438

It's all self-explanatory, but for a rough split of responsibilities:

  • !~ -: could be thought of as binomial(x,x/2)
  • % 2&^ is "divided by 2^x"
  • &. (". @ stdin) _ for I/O
\$\endgroup\$
2
\$\begingroup\$

GNU Octave - 36 Characters

disp(binopdf((n=input(""))/2,n,.5));
\$\endgroup\$
2
\$\begingroup\$

Ruby, 39 characters

p 1/(1..gets.to_i).inject{|a,b|1.0*b/a}
\$\endgroup\$
2
\$\begingroup\$

Golfscript - 30 chars

Limitation - only works for inputs less than 63

'0.'\~..),1>\2//{{*}*}%~\/5@?*

test cases

$ echo 2 | ruby golfscript.rb binom.gs 
0.50
$ echo 4 | ruby golfscript.rb binom.gs 
0.3750
$ echo 6 | ruby golfscript.rb binom.gs 
0.312500
$ echo 8 | ruby golfscript.rb binom.gs 
0.27343750

Analysis

'0.' GS doesn't do floating point, so we'll fake it by writing an integer after this
\~ Pull the input to the top of the stack and convert to an integer
.. Make 2 copies of the input
),1>Create a list from 1..n
\2//Split the list into 1..n/2 and n/2+1..n
{{*}*}%Multiply the elements of the two sublists giving (n/2)! and n!/(n/2)!
~Extract those two numbers onto the stack
\Swap the two numbers around
/Divide
5@?*Multiply by 5**n. This is the cause of the limitation given above

\$\endgroup\$
3
  • \$\begingroup\$ I'm curious as to why the limitation. Are you using Gosper's hack to generate all the combinations? The idea occurred to me (and the spec doesn't say anything about execution time). \$\endgroup\$ Feb 28, 2011 at 12:05
  • \$\begingroup\$ Golfscript doesn't have a float point variable class, so what he does is calculate an integer that written after the string 0. is the decimal part of the answer, but that method leaves out the required 0 when the chance grows less than 10%. \$\endgroup\$ Feb 28, 2011 at 14:30
  • \$\begingroup\$ @Peter, what eBusiness said :) \$\endgroup\$
    – gnibbler
    Feb 28, 2011 at 23:45
2
\$\begingroup\$

TI-BASIC, 10

This will take more than ten bytes of calculator memory because there is a program header, but there are only ten bytes of code.

binompdf(Ans,.5,.5Ans

//Equivalently:

2^~AnsAns nCr (.5Ans

This takes input in the form [number]:[program name]; adding an Input command uses three more bytes. ~ is the unary minus token.

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

Ruby - 50 57 54 chars

p (1..(n=gets.to_i)/2).reduce(1.0){|r,i|r*(n+1-i)/i/4}
\$\endgroup\$
2
  • \$\begingroup\$ This calculates nCr not the probability. \$\endgroup\$
    – david4dev
    Feb 27, 2011 at 19:24
  • \$\begingroup\$ @david4dev, fixed. \$\endgroup\$
    – Dogbert
    Feb 27, 2011 at 19:52
1
\$\begingroup\$

J, 20

f=:(]!~[:<.2%~])%2^]

examples:

f 2
0.5
f 4
0.375
f 6
0.3125
f 8
0.273438
\$\endgroup\$
2
  • \$\begingroup\$ The question asks for input from STDIN, not a function. \$\endgroup\$
    – Dogbert
    Feb 28, 2011 at 10:26
  • \$\begingroup\$ @Dogbert: I know; I forgot to mention this. I intended to update it... \$\endgroup\$
    – Eelvex
    Feb 28, 2011 at 10:37
1
\$\begingroup\$

APL 21 15 chars

((N÷2)!N)÷2*N←⎕

For where it doesn't render right

((N{ColonBar}2)!N){ColonBar}2*N{LeftArrow}{Quad}

Where everything in {} are APL specific symbols like here.

\$\endgroup\$
4
  • \$\begingroup\$ Is the last character supposed to be a square? \$\endgroup\$
    – J B
    Feb 28, 2011 at 19:43
  • \$\begingroup\$ Yes it should be the quad symbol. \$\endgroup\$
    – jpjacobs
    Feb 28, 2011 at 19:46
  • \$\begingroup\$ I get �[token]: � undefined \$\endgroup\$
    – david4dev
    Mar 1, 2011 at 17:31
  • \$\begingroup\$ I guess this is a coding issue. In NARS2000 you can copy paste it as is. \$\endgroup\$
    – jpjacobs
    Mar 5, 2011 at 11:42
1
\$\begingroup\$

Windows PowerShell, 45

($p=1)..($n="$input"/2)|%{$p*=(1+$n/$_)/4}
$p

Meh.

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

MATLAB, 29

n=input('');binopdf(n/2,n,.5)
\$\endgroup\$
0
\$\begingroup\$

PostScript, 77

([)(%stdin)(r)file token{2 idiv}if def
1
1 1[{[exch div 1 add 4 div mul}for
=
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 19

f=2^-# #!/(#/2)!^2&
\$\endgroup\$
0
\$\begingroup\$

Javascript, 86 bytes

a=prompt(f=function(n){return n?n*f(n-1):1});alert(f(a)/(f(a/2)*f(a/2)*Math.pow(2,a)))
\$\endgroup\$
0
\$\begingroup\$

Python 3, 99

This is a naive approach, I suppose, and fR0DDY's solution is much cooler, but at least I am able to solve it.

Try it here

from itertools import*
n=int(input())
print(sum(n/2==i.count("H")for i in product(*["HT"]*n))/2**n)

Python 2, 103

from itertools import*
n=int(raw_input())
print sum(n/2==i.count("H")for i in product(*["HT"]*n))/2.**n
\$\endgroup\$
0
\$\begingroup\$

Objective-C:

152 148 bytes for just the function.

Class methods, headers, and UI are not included within the code.

Input: an int value determinining the number of coins.

Output: a float value determining the probability.

-(float)calcPWithCoins:(int)x {int i=0;int j=0;for (int c=x;c<1;c+-){i=i*c;} for(int d=x/2;d<1;d+-){j=j*d;} return (((float)i/(float)j)/powf(2,x));}

Ungolfed:

-(float)calcPWithCoints:(int)x
{
    int i = 0;
    int j = 0;
    for (int c = x; c < 1; c+-) {
         i = i * c;
    }
    // Calculate the value of x! (Factorial of x)

    for (int d = x / 2; d < 1; d+-)
         j = j * d;
    }
    // Calculate (x/2)! (Factorial of x divided by 2)

    return (((float)i / (float)j) / powf(2, x));
    /* Divides i! by (i/2)!, then divides that result (known as the nCr) by 2^x.
    This is all floating-point and precise. If I didn't have casts in there,
    It would be Integer division and, therefore, wouldn't have any decimal
    precision. */
}

This is based off of the Microsoft Excel answer. In C and Objective-C, the challenge is in hard-coding the algorithms.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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