Using memoization, but still the code runs forever

Question

I am trying to solve the problem of an SPOJ cricket tournament . "I wrote the code in python as well as in c. In python it takes about 2 seconds to enter 0.0 0/0 300. But in C it works forever. The code in C works for some smaller ones test cases such as 19.5 0/0 1

Code in C

#include<stdio.h> float ans[10][120][300]={0}; float recursion(int balls, int reqRuns, int wickets); int readScore(void); int main() { int t; scanf("%d",&t); while(t--) { memset(ans,0,sizeof(ans)); float overs; int myruns,wickets,target; scanf("%f",&overs); myruns=readScore(); scanf("%d",&wickets); //printf("%d %d\n",myruns,wickets ); scanf("%d",&target); //printf("%d %d %d\n",myruns,wickets,target); if(myruns>=target) { printf("%s\n","100.00"); continue; } else if(wickets>=10) { printf("%s\n", "0.00"); continue; } printf("overs = %f\n", overs); int ov = (int) overs; int ball = (int)(overs*10)%10; int totballs = 6*ov+ball; //printf("%d %d\n",ov,ball ); //printf("%d %d %d\n",totballs, target- myruns,wickets ); float finalAns = recursion(totballs,target-myruns, wickets)*100; printf("%.2f\n",finalAns); } return 0; } int readScore() { char ch; int ans2=0; ch = getchar(); //ch = getchar(); //ans = ans*10 + ch-'0'; //printf("sadasdas %d\n",ch ); while(ch!='/') { ch=getchar(); //printf(" ch = %d\n", ch-'0'); if(ch!='/') ans2 = ans2*10 + ch-'0'; } //printf("%d\n",ans ); return ans2; } float recursion(int balls, int reqRuns, int wickets) { if (reqRuns<=0) return 1; if (balls==120||wickets==10) return 0; if(ans[wickets][balls][reqRuns]!=0) return ans[wickets][balls][reqRuns]; ans[wickets][balls][reqRuns] = (recursion(balls+1, reqRuns,wickets)+recursion(balls+1, reqRuns-1,wickets)+ recursion(balls+1, reqRuns-2,wickets)+recursion(balls+1, reqRuns-3,wickets)+ recursion(balls+1, reqRuns-4,wickets)+recursion(balls+1, reqRuns-5,wickets)+ recursion(balls+1, reqRuns-6,wickets)+recursion(balls+1, reqRuns,wickets+1)+ 2*recursion(balls, reqRuns-1,wickets))/10; return ans[wickets][balls][reqRuns]; } 

Python code

 from __future__ import division saved = {} t = input() def func(f): if f in saved: return saved[f] x,y,z,n = f if z >= n: return 1 if x == 120: return 0 if y == 10: return 0 saved[f] = (func((x+1,y+1,z,n)) + func((x+1, y,z,n)) + func((x+1,y,z+1,n)) + func((x+1, y, z+2,n)) + func((x+1, y, z+3,n)) + func((x+1, y, z+4,n)) + func((x+1, y, z+5,n))+ func((x+1, y, z+6,n))+ func((x,y,z+1,n)) + func((x,y,z+1,n))) / 10 return saved[f] def converter(f): v = f.index('.') x,y = int(f[:v]), int(f[-1]) return x*6+(y) for i in range(t): x,y,z = raw_input().split() v = y.index('/') q = int(y[:v]) x,y,z = converter(x), int(y[(v+1):]), int(z) print '%.2f' % (100 * func((x,y,q,z))) 

Answer 1

Your problem is that many recursion results are 0, so

 if(ans[wickets][balls][reqRuns]!=0) return ans[wickets][balls][reqRuns]; 

in many cases, it is not possible to return the cached result, so you recalculate the results of many many , and checking f in saved in Python prevents recalculating the same values.

I changed my C code to set the initial ans entries to contain negative numbers (if you know that your platform’s floating point representation will be IEEE754, it will just change to memset(ans, 0x80, sizeof ans); ) and replace the condition with

 if (ans[wickets][balls][reqRuns] >= 0) 

and immediately got the result:

 $ time ./a.out < spoj_inp.txt overs = 0.000000 18.03 real 0m0.023s user 0m0.020s sys 0m0.002s 

Answer 2

The problem is using scanf. It treats the space or newline as an input terminator. Most likely, you enter an input after each input. However, the problem is that it leaves \ n in the buffer and is passed to the next input.

If you do not use strict c, you can call

cin.ignore()

after each call to scanf. I tried this on your code and was able to get a successful exit.

Alternatively you can call

 fflush(stdin); 

It may be useful as well.

fooobar.com/questions/1437266 / ...

Answer 3

I assume that here you need to blame recursion. The code works for small purposes. Get rid of recursion if possible.

For smaller purposes:

entrance

 2 0.0 0/1 10 0.0 2/2 20 

Output

 100.00 99.99