CODEWITHSUNDEEP
pythoncalgorithmrecursionmemoization
Ishan Jain
Ishan Jain

Reputation: 262

Using memoization but still code runs forever

I am trying to solve the SPOJ problem "Cricket Tournament". I wrote the code in python and also in c. In python it takes about 2 seconds for input 0.0 0/0 300. But in C it runs forever. Code in C is running for some smaller test cases like 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];
}

Code in Python

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

Upvotes: 4

Views: 330

Answers (3)

Daniel Fischer
Daniel Fischer

Reputation: 183868

Your problem is that a lot of the results of the recursion are 0, so

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

fails to return the cached result in many cases, hence you're recomputing many many results, while the check f in saved in Python prevents recomputation of the same values.

I changed your C code to set the initial entries of ans to contain negative numbers (if you know the floating point representation of your platform to be IEEE754, simply changing to memset(ans, 0x80, sizeof ans); will do), and replaced the condition with

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

and got the result immediately:

$ time ./a.out  < spoj_inp.txt 
overs = 0.000000
18.03

real    0m0.023s
user    0m0.020s
sys     0m0.002s

Upvotes: 3

जलजनक
जलजनक

Reputation: 3071

I guess the recursion is to be blamed here. Code does work for smaller targets. Get rid of recursion if possible.

With smaller targets:

input

2
0.0 0/1 10
0.0 2/2 20

output

100.00
99.99

Upvotes: 0

fkl
fkl

Reputation: 5535

The problem is with your use of scanf. It treats space or newline as terminator of an input. Mostly likely you are typing enter after each input. However, problem is that it leaves the \n in the buffer and that is passed to the next input.

If you are not using strict c, you can call

cin.ignore()

after each scanf call. I tried it on your code and was able to get successful output.

Alternately, you can call 

fflush(stdin);

This might be helpful too

scanf at stackoverflow

Upvotes: 0

Related Questions