Python recursive graph traversal refuses to work and gives out Runtime Error

Question

My code doesn't seem to work at all on CodeForces.

When I got RE for the first time , I increased the maximum recursion depth and tried again. There was no improvement. I tried to print out the error using try except block, but there was no output. I'm out of ideas as to what caused the RE although I do suspect the recursion depth to be the culprit. Any help/suggestion will be helpful

Code without increased MaximumRecusrionDepth:-

Code with increased recursion depth:-

Code with some optimization and lower RunTime:-

import sys
from sys import stdin, stdout
sys.setrecursionlimit(4000000)
n=int(input())
adjli=[];inp={};parent=[];output=[];ty=[]
for i in range(n):
    adjli.append([]);parent.append(-1);output.append(-1)
for i in range(n):
    x=list(stdin.readline().strip().split(' '))
    if len(x)==3:
        t1,t2,t3=x[0],x[1],x[2]
        adjli[i].append(int(t2)-1);parent[int(t2)-1]=i;
        adjli[i].append(int(t3)-1);parent[int(t3)-1]=i;
        if t1=="AND":
            ty.append(1)
        elif t1=="OR":
            ty.append(2)
        elif t1=="XOR":
            ty.append(3)
    if len(x)==2:
        t1,t2=x[0],x[1]
        if t1=="NOT":
            adjli[i].append(int(t2)-1);parent[int(t2)-1]=i;
            ty.append(4)
        elif t1=="IN":
            ty.append(5);inp[i]=int(t2)

#print(adjli)
#print(parent)
#print(ty)
#print(inp)

def assignout(x):
    global adjli,output
    if len(adjli[x])==2:
        if ty[x]==1:#AND
            assignout(adjli[x][0]);assignout(adjli[x][1])
            output[x]=output[adjli[x][0]]&output[adjli[x][1]]
        if ty[x]==2:#OR
            assignout(adjli[x][0]);assignout(adjli[x][1])
            output[x]=output[adjli[x][0]]|output[adjli[x][1]]
        if ty[x]==3:#XOR
            assignout(adjli[x][0]);assignout(adjli[x][1])
            output[x]=output[adjli[x][0]]^output[adjli[x][1]]
    elif len(adjli[x])==1:
        assignout(adjli[x][0])
        output[x]= output[adjli[x][0]]^1
    elif len(adjli[x])==0:
        output[x]=inp[x]
assignout(0)
ans=""
#print(output)


def getnew(ind):
    cf=output[ind];cf=cf^1
    while True:
        #print(ind,cf)
        baap=parent[ind];bt=ty[baap];bkb=adjli[baap];
        if baap==-1:
            return cf
            break
        if len(bkb)==2:
            c1=ind;c2=-1;
            if bkb[0]==c1:
                c2=bkb[1]
            else:
                c2=bkb[0]
            if bt==1:
                cf=cf&output[c2]
            if bt==2:
                cf=cf|output[c2]
            if bt==3:
                cf=cf^output[c2]
            ind=baap
        if len(bkb)==1:
            cf=cf^1
            ind=baap
        if cf==output[baap]:
            return output[0]
try:
    for i in inp:
        ans+=str(getnew(i))
except BaseException as e:
    print(e,"ERROR")
print(ans)

Input:-(The entire input is not given, However the number of input lines is given)

1000000
NOT 372184
NOT 940908
NOT 59086
NOT 229025
IN 0
NOT 42130
NOT 411794
NOT 995474
NOT 872431
NOT 554205
AND 387115 701144
NOT 261440
IN 0
NOT 758246
IN 1
NOT 758645
NOT 230272
AND 694079 64950
NOT 23776
IN 0
IN 1
NOT 587099
NOT 967592
NOT 519539
IN 1
NOT 573893
NOT 592845
NOT 390452
NOT 636185
NOT 505487
XOR 109272 632046
NOT 180211
NOT 840521
IN 0
NOT 659437
NOT 284909
NOT 250405
NOT 376365
NOT 188939
NOT 311363
NOT 826221
NOT 459050
NOT 771490
NOT 724469
...

What is the question? I'll try to summarize it as much as possible:-

How to interpret the input? The first line of the input contains n , the number of vertices in the graph. It is followed by N-lines, where the i-th line tells us if that vertex is AND,OR,XOR,NOT or an input denoted by IN. It is followed by two integers in case of AND,OR,XOR where the two integers point to the vertices whose output are taken as input for the current vertex. The final output vertex is always 1.The given graph is a tree.

Basically:-

operation input1 input2 (AND,OR,XOR)

operation input1 (NOT)

IN input-value (INPUT)

Now we have to complement the value of each of the input gates and record the final output at 1. The recorded values are concatenated as a string and displayed The question Link In case my explanation leaves any doubts:-Question

Could you please post here the minimum code require and the last use case that fails with the RE? — dWinder, Aug 23 '18 at 07:32
Please don't just link to code hosted on external sites. Instead create a [mcve] to illustrate your question and include it directly as nicely formatted text. Other users should basically be able to understand your question without consulting external resources. Otherwise your question and the answers are rendered useless, should those off site resources become unavailable. Of course, it's always welcome to add links to external resources in order to provide _additional_ context. — anothernode, Aug 23 '18 at 07:33
I'm sorry for the insufficient question. If anything else is needed, I'll try my best. — , Aug 23 '18 at 15:09
Thanks for improving your question! I retracted my down vote. — anothernode, Aug 23 '18 at 15:40

score 0 · Answer 1 · answered Aug 25 '18 at 14:49

A few things:

The code is very hard to read. Before posting, please add comments, use explicit variable names etc.. You're much more likely to get a (correct) answer.
Test your code first on short examples, particularly the one provided on the webpage. Don't try a huge input first, it will be impossible to debug.
It seems like your getnew() function tries to get the updated outputs by changing only the bits that need to change. A much easier solution would be to simply reuse the graph traversal you wrote for the initial bit assignment (assignout)! Something like :

def getnew(i):
   global inp
   inp_bak = inp.copy()  # backup the original inputs
   inp[i] = inp[i]^1     # invert the select input
   assignout(0)          # run your graph traversal like you did above (!)
   inp = inp_bak.copy()  # restore your original inputs for the next iteration
   return output[0]      # return the final output

You cannot get the same output as expected because in your code inp is a dictionary, and you assume it is ordered when you iterate like this:

   for i in inp:
      ans+=str(getnew(i))

Instead, you should use an ordered dictionary. This should give you the correct results.

Python recursive graph traversal refuses to work and gives out Runtime Error

1 Answers1