Counting ways of scoring k points in n games with half-points for draws

Question

If a game can result in a win, worth one point; a draw, worth half a point; or a loss, worth no points; how many ways are there of scoring k points in n games?

Applicable scenarios include NFL and chess.

• Input is via stdin, and consists of n and k on separate lines.
• n will be a non-negative integer. (n ≤ 16)
• k will be either a non-negative integer or a non-negative integer plus a half. (k ≤ n)
• Output is to stdout. It may, but does not have to, include a trailing newline.

Test cases

In each case, the first two lines are user-supplied input and the third line is the program output.

10
4.5
8350

16
8
5196627

16
13.5
13328

12
12
1

Answer 1

Perl 59 bytes

@0=map"$v"+($v=$u)+($u=$_),@0,0,0for(@0=1)x<>;print@0[<>*2]

Iteratively generates each row of the triangle of trinomial coefficients up to n, and then prints the correct term, 2k.

---

Ruby 73 bytes

r=*1
gets.to_i.times{r<<0<<u=v=0;r.map!{|t|v+(v=u)+u=t}}
p r[gets.to_f*2]

Largely equivalent to the Perl solution above.

---

Python 84 bytes

r=[1]
exec"r=map(sum,zip(r+[0],[0]+r,[0,0]+r))+[1];"*input()
print r[int(input()*2)]

Same method as both solutions above.

---

PHP 91 bytes

<?for($n=+fgets(STDIN);(${$j--}+=$$j+${$j-1})?:$n--*$j=$i+=2;${0}=1);echo${fgets(STDIN)*2};

Despite being the longest, this was actually the most fun to work on.

Answer 2

R - 81

cat(sum(rowSums(do.call(expand.grid,replicate(scan(n=1),0:2,s=F)))==2*scan(n=1)))

A bit longer (106) but I also enjoyed writing it as a recursion:

Z=function(n,k)if(n<1|k<0)0 else if(n<2&k<3)1 else Z(n-1,k)+Z(n-1,k-1)+Z(n-1,k-2);Z(scan(n=1),2*scan(n=1))

Answer 3

C# (189 bytes)

Collaborative results from @glthomas, @recursive, @PeterTaylor and @primo

Best Solution (189 Bytes)
@glthomas and @recursive each found an additional 2 Bytes over the weekend. (We're convinced that this is the optimal solution using .Net 4.0 and compiling in VS 2010)!

using S=System.Console;class C{static void Main(){S.Write(G(G(),2*G()));}
static float G(float L=-1,float T=1){return L<0?float.Parse(S.ReadLine())
:T==0?1:--L<0?0:G(L,T)+G(L,T-1)+G(L,T-2);}}

Improved Solution (193 Bytes)

using System;class C{static void Main(){Func<float,float,float>W=null;W=(n,k)=>n<0?
k*float.Parse(Console.ReadLine()):k==0?1:--n<0?0:W(n,k)+W(n,k-1)+W(n,k-2);
Console.Write(W(W(-1,1),W(-1,2)));}}

The additional Byte was saved by combining the input acquisition and static recursive method into a single multipurpose Func<>. Input acquisition is triggered when we pass in a negative value of n

Original Solution (195, 194)

using K=System.Console;class C{static void Main(){K.Write(T(int.Parse(K.ReadLine
()),2*float.Parse(K.ReadLine())));}static float T(int n,float k){return k==1?1:--
n<0?0:T(n,k)+T(n,k-1)+T(n,k-2);}}

Answer 4

C# (210 209 chars)

More efficient: iterative approach (209 chars):

using K=System.Console;class C{static void Main(){int
n=int.Parse(K.ReadLine()),k=(int)(2*float.Parse(K.ReadLine())),j;var t=new
int[k+3];for(t[2]=1;n-->0;)for(j=k+2;j>1;)t[j]+=t[--j]+t[j-1];K.Write(t[k+2]);}}

Less efficient: recursive approach (210 chars);

using K=System.Console;class C{static void Main(){int
n=int.Parse(K.ReadLine()),k=(int)(2*float.Parse(K.ReadLine()));K.Write(T(n,k));}static
int T(int n,int k){return k<1?k+1:--n<0?0:T(n,k)+T(n,k-1)+T(n,k-2);}}

Note that if k is non-integral, it should be supplied in a format applicable to the locale. In my case that means that I have to format the input using , as the decimal separator.

Answer 5

GolfScript (39 chars)

'.'/(~2*@,+[1]@{[0.@0+{@2$2$++@@}/+]}*=

Online demo

Based on my answer to a previous question about binomial coefficients.

Answer 6

APL (22)

+/(2×⎕)=+⌿(N⍴3)⊤⍳3*N←⎕

It's not exactly efficient though (set your workspace size to a couple of gigabytes if you want it to actually work up to N=16).