For solving problem 3 (Kick Start - Google’s Coding Competitions) of Round B of Google Kickstart 2020 I have used exactly the same algorithm as mentioned in its analysis section. However, I’m getting correct answer in Test set 1 and WA in case of Test set 2. I’m using Python 3.8 and have used the following code. Can anyone tell me whats going wrong?
T = int(input())
def brc_match(P):
L,D,l=[],{},len(P)
for i in range(l):
if P[i] == '(':
D[i]=0
L.append(i)
elif P[i] == ')':
D[L.pop()] = i
return D
def new_pos(ch,cw,cmd):
done = False
if ch==1000000000 and cmd=='E':
ch=1
done = True
elif ch==1 and cmd=='W':
ch=1000000000
done = True
if cw==1000000000 and cmd=='S':
cw=1
done = True
elif cw==1 and cmd=='N':
cw=1000000000
done = True
if done == False:
if cmd=='E':
ch+=1
elif cmd=='W':
ch-=1
if cmd=='N':
cw-=1
elif cmd=='S':
cw+=1
return ch,cw
def evaluate(L,R,roboh=1,robow=1):
global P,cbracket
cursor=L
while cursor<=R:
if P[cursor] in 'NEWS':
roboh,robow = new_pos(roboh,robow,P[cursor])
cursor+=1
elif P[cursor] in '23456789':
D = int(P[cursor])
F = evaluate(cursor+2,cbracket[cursor+1]-1,roboh,robow)
dx,dy=F[0]-roboh,F[1]-robow
roboh,robow = (roboh+D*dx)%1000000000,(robow+D*dy)%1000000000
cursor = cbracket[cursor+1]+1
return roboh,robow
for i in range(1,T+1):
P = input()
cbracket,lim = brc_match(P),len(P)-1
roboh,robow = evaluate(0,lim)
print('Case #{}: {} {}'.format(i,roboh,robow))