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

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

• oeis.org/A027907 – Peter Taylor Jun 19 '13 at 17:37
• This is very insightful. I have a working solution in c# which compiles to the requirements outlined within the problem. I'm merely curious if someone can come up with a more compact solution than what I have. Cheers! – glthomas Jun 19 '13 at 20:07

@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. ## 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))  ## 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);}}  • You can save one more byte by changing k<1?k+1 to k==0?1. It might be possible to save another if --n could somehow be moved to the front of the expression, i.e. return--n... – primo Jun 21 '13 at 6:24 • @primo, unfortunately that alters the output, because k can sometimes be -1 because of the T(n,k-2) method call. Therefore we must check for k<1. – glthomas Jun 21 '13 at 18:50 • I don't think it will. The k<0s will be allowed to propagate, true, but they will eventually be quenched when n reaches zero. Because a k that is less than zero cannot produce a k equal to zero in the successive calls, it cannot change the result. – primo Jun 21 '13 at 19:03 • @primo I was incorporating both your second suggestion along with your first suggestion. The idea to return--n.. was interfering with my testing. I agree you can save a byte by converting k<1?k+1 to k==0?1. It appears the reason it doesn't work to move --n to the front of the expression is due to order of operation. The condition on k takes precedent over the condition on n. Wait until you see my post on 193 bytes :) – glthomas Jun 21 '13 at 19:50 • Nice. Here's 7 bytes more: Func<float,float,float>W=null;W=(n,k) => Func<float,float,float>W=(n,k). – primo Jun 21 '13 at 21:04 ## 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. • 209 Bytes, you missed an easy 4 bytes :) 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]);}} – glthomas Jun 19 '13 at 21:55 • @user1177611, it wasn't clear that that was permitted. I've edited the question and, among other changes, made that explicit. – Peter Taylor Jun 19 '13 at 22:33 • An anonymous user suggested saving a character in the iterative version by defining t=new int[99]. Technically with the current spec one could get away with t=new int[35], but I think that limiting the value of n to no more than 16 is a pointless restriction. – Peter Taylor Jun 20 '13 at 13:39 • Prior to being reworded, this problem started as an NFL win total combinatorics question. As such, 16 is currently the highest Win Total a team can achieve over one season. Though there has been a lot of debate regarding the expansion to an 18 game season. So, t=new int[99] is virtually future proof (at least as it pertains to the NFL) – glthomas Jun 20 '13 at 14:10 ## GolfScript (39 chars) '.'/(~2*@,+[1]@{[0.@0+{@2$2\$++@@}/+]}*=


Online demo

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