1
\$\begingroup\$

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
\$\endgroup\$
  • 4
    \$\begingroup\$ oeis.org/A027907 \$\endgroup\$ – Peter Taylor Jun 19 '13 at 17:37
  • \$\begingroup\$ 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! \$\endgroup\$ – glthomas Jun 19 '13 at 20:07
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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

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);}}
\$\endgroup\$
  • \$\begingroup\$ 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... \$\endgroup\$ – primo Jun 21 '13 at 6:24
  • \$\begingroup\$ @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. \$\endgroup\$ – glthomas Jun 21 '13 at 18:50
  • \$\begingroup\$ 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. \$\endgroup\$ – primo Jun 21 '13 at 19:03
  • \$\begingroup\$ @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 :) \$\endgroup\$ – glthomas Jun 21 '13 at 19:50
  • \$\begingroup\$ Nice. Here's 7 bytes more: Func<float,float,float>W=null;W=(n,k) => Func<float,float,float>W=(n,k). \$\endgroup\$ – primo Jun 21 '13 at 21:04
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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]);}} \$\endgroup\$ – glthomas Jun 19 '13 at 21:55
  • \$\begingroup\$ @user1177611, it wasn't clear that that was permitted. I've edited the question and, among other changes, made that explicit. \$\endgroup\$ – Peter Taylor Jun 19 '13 at 22:33
  • \$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Jun 20 '13 at 13:39
  • \$\begingroup\$ 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) \$\endgroup\$ – glthomas Jun 20 '13 at 14:10
1
\$\begingroup\$

GolfScript (39 chars)

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

Online demo

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

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

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

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