Converting this recursive algorithm into iterative one

Question

I was having a look at this stackoverflow question: Game of 2/9 (Interview at Facebook)

In one of the answers it is stated that by comparing with a recursive solution it is possible to find this algorithm:

def win29(n):
    if n<=9: return True
    n-=1
    while n>=18:
        n = n//18
    return n==1 or 4<=n<=8

I guess the recursive algorithm would be this one:

 F(i, j) = true; if (2^i * 9^j * 9) >= N
       !(F(i+1, j) && F(i, j+1)); otherwise

What would be the mechanism or procedure (or comparison) to convert this recursive algorithm into the iterative one above?

Your recursive algorithm does not do the same as the above algorithm. — Ivaylo Strandjev
– Ivaylo Strandjev, Commented Jan 2, 2014 at 11:44
It seems it does the same when you call F(0,0) and n=N. At least it seems it should give the same answer, according to the link I give. — jbgs
– jbgs, Commented Jan 2, 2014 at 11:46
Call me stupid, but this pseudo-code style is really confusing to me. Is this any standard, or de-facto standard. I mean n = n//18 ... or if n<=9: return True but in the latter code example F(i, j) = true; if .... Da hell? — luk32
– luk32, Commented Jan 2, 2014 at 11:58
Please have a look at the question I am referencing. I think it is not the same language (or pseudocode) for both. But it is easy to understand what each algorithm does. — jbgs
– jbgs, Commented Jan 2, 2014 at 12:01

Vikram Bhat · Accepted Answer · 2014-01-02 17:58:08Z

1

here is what i can explain of algorithm :

N < 18^k*x and x>8 & x<18 : then player two wins because he can force a win by making put powers of 18 till x remains
N < 18*k*x*9 and x>8 & x<18 or N<18*k*2*x and x>8 & x<18 : Using same analogy as 1. where player 1 makes moves 2 or 9 and then wins using 1. as he is player two in next move. Simplifying for remainder in both equations we get r>=9*8/18>=4 and r<9*18/18<=8 and r>=9*2/18>=1 and r<18*2/18<2 for player 1 to win

Hence divide by 18 successively then check n>=4 and n<=8 or n==1 for player 1 to win

If compare properly my explanation though i came to it by another way but it is comparable to recursive solution where 2^i*9^j*9 can be visualized as 18^k*x and F(i+1,j) as 2*18^k*x and F(i,j+1) as 9*18^k*x

edited Jan 2, 2014 at 17:58

answered Jan 2, 2014 at 17:18

Vikram Bhat

6,3063 gold badges22 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Converting this recursive algorithm into iterative one

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related