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\$
  • 1
    \$\begingroup\$ We can assume the coins are perfect and there's an even chance of getting heads or tails? \$\endgroup\$ – Juan Feb 27 '11 at 17:18
  • \$\begingroup\$ Do we need to print the output to stdout? \$\endgroup\$ – Dogbert Feb 27 '11 at 18:24
  • \$\begingroup\$ @Juan yes. @Dogbert yes. \$\endgroup\$ – david4dev Feb 27 '11 at 18:37
  • \$\begingroup\$ Could we get some more test cases to verify our solutions? \$\endgroup\$ – Dogbert Feb 27 '11 at 19:44
  • \$\begingroup\$ @Dogbert - done \$\endgroup\$ – david4dev Feb 27 '11 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\$
  • \$\begingroup\$ This gives an error for me: 0 1|domain error: script | %/ >:i.&.(".@stdin)_ \$\endgroup\$ – david4dev Mar 1 '11 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 '11 at 17:46
3
\$\begingroup\$

Pari/GP - 32 30 34 chars

print(binomial(n=input(),n\2)/2^n)
\$\endgroup\$
  • \$\begingroup\$ Wow, I didn't consider a programming language having a built in binomial function. \$\endgroup\$ – david4dev Feb 27 '11 at 18:38
  • \$\begingroup\$ 32 characters: print(binomial(n=input,n\2)/2^n). \$\endgroup\$ – Charles Apr 28 '15 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\$
  • 2
    \$\begingroup\$ Excel actually implements the ^ properly, so you can cut out a few characters that way. \$\endgroup\$ – SuperJedi224 Jun 8 '15 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\$
  • \$\begingroup\$ I get an error: Undefined variable "readln" \$\endgroup\$ – david4dev Feb 28 '11 at 16:42
  • \$\begingroup\$ @david4dev the 'L' in readLn is a capital one. \$\endgroup\$ – J B Feb 28 '11 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 '15 at 20:57
  • \$\begingroup\$ Indeed. Merging, thanks! \$\endgroup\$ – J B May 27 '15 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\$
  • \$\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\$ – Peter Taylor Feb 28 '11 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\$ – aaaaaaaaaaaa Feb 28 '11 at 14:30
  • \$\begingroup\$ @Peter, what eBusiness said :) \$\endgroup\$ – gnibbler Feb 28 '11 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\$
  • \$\begingroup\$ This calculates nCr not the probability. \$\endgroup\$ – david4dev Feb 27 '11 at 19:24
  • \$\begingroup\$ @david4dev, fixed. \$\endgroup\$ – Dogbert Feb 27 '11 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\$
  • \$\begingroup\$ The question asks for input from STDIN, not a function. \$\endgroup\$ – Dogbert Feb 28 '11 at 10:26
  • \$\begingroup\$ @Dogbert: I know; I forgot to mention this. I intended to update it... \$\endgroup\$ – Eelvex Feb 28 '11 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\$
  • \$\begingroup\$ Is the last character supposed to be a square? \$\endgroup\$ – J B Feb 28 '11 at 19:43
  • \$\begingroup\$ Yes it should be the quad symbol. \$\endgroup\$ – jpjacobs Feb 28 '11 at 19:46
  • \$\begingroup\$ I get �[token]: � undefined \$\endgroup\$ – david4dev Mar 1 '11 at 17:31
  • \$\begingroup\$ I guess this is a coding issue. In NARS2000 you can copy paste it as is. \$\endgroup\$ – jpjacobs Mar 5 '11 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, privacy policy and cookie policy

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