Dictionary returning same output Python

Question

I have written the code for testing the input string if it satisfies the Non Deterministic finite state machine/automata. The logic seems fine to me but the code crashes because of stackoverflow because the recursive function is not returning.

The reason is dictionary is always returning same result for an input even though for the same input the dictionary has two different outputs.

def hello(curExist, curTemp, string, dict, accept):

    print "curExist: ", curExist, " curTemp: ", curTemp, " Letter: ", string;

    if(string == ""):
            return curExist in accept;

    elif((curTemp,string[0]) in dict):
        curExist = curTemp = dict[(curTemp,string[0])];

        return hello(curExist, curTemp, string[1:], dict, accept);

    elif((curTemp,'') in dict):
        curTemp = dict[(curTemp, '')];

        return hello(curExist, curTemp, string, dict, accept);

    elif((curExist, '') in dict):
        curTemp = dict[(curExist, '')];

        return hello(curExist, curTemp, string, dict, accept);

    else:
        return False;


dict={(1,'a'):2, (2,''):6, (6,''):4, (2,''):3, (3,'b'):4, (4,'c'):5};

mString = "ac";
accept=[5];

print hello(1,1,mString,dict,accept);

Console Output:

curExist:  1  curTemp:  1  Letter:  ac
curExist:  2  curTemp:  2  Letter:  c
curExist:  2  curTemp:  3  Letter:  c
curExist:  2  curTemp:  3  Letter:  c
curExist:  2  curTemp:  3  Letter:  c // printing this untill crash
.
.
.

How can I solve this problem?

dont use dict as variable name

ndpu
– ndpu

2014-03-08 13:33:11 +00:00
Commented Mar 8, 2014 at 13:33 — ndpu
– ndpu, Commented Mar 8, 2014 at 13:33

Ian Clark · Accepted Answer · 2014-03-08 13:49:23Z

2

Keys in dictionaries need to be unique and immutable (because they're hashed), you can't have 2 identical keys:

>>> foo = { (2, ''): "bar", (2, ''): "zulu" }
>>> foo
{(2, ''): 'zulu'}

Also:

Your conditions don't need to be wrapped in parenthesis
You don't use semi-colons to delimit statement endings, that's what the whitespace is for.
Don't name a variable dict. It's the constructor for dictionaries

edited Mar 8, 2014 at 13:49

answered Mar 8, 2014 at 13:28

Ian Clark

9,3774 gold badges36 silver badges49 bronze badges

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

5 Comments

Umer Farooq Over a year ago

So what can be the solution as Non deterministic automata has different outputs for same input.

Ian Clark Over a year ago

What do you want to do when one input has multiple outputs?

Ian Clark Over a year ago

To be clear: I don't know what a 'Non Deterministic finite state machine/automata' is, but if you tell me what you want your inputs and outputs to be, then I can help.

Umer Farooq Over a year ago

Is there an alternative to dictionaries which doesn't need unique keys and can have tuple as key?

Ian Clark Over a year ago

Not really, your best solution would be to make the values a list of integers rather than simply integers.

Community · Accepted Answer · 2017-05-23 10:33:26Z

0

@IanClark is right, the keys have to be unique. One simple solution will be to turn your dictionary signature to pair -> list. This signature naturally captures Non-Deterministic Automata, (Current State, Symbol) -> (List of Possible Next States). So, your example dict becomes

dictionary={(1,'a'):[2], (2,''):[6, 3], (6,''):[4], (3,'b'):[4], (4,'c'):[5]};

Finally, in your elif branch, loop over all elements in the dictionary entry and recursively call hello. Something like:

elif((curTemp,'') in dict):
    curTempList = dictionary[(curTemp, '')];

    tempBool = False
    for newCurrTemp in currTempList: 
        tempBool = tempBool or hello(curExist, curTemp, string, dictionary, accept);
    return tempBool

Your recursive call returns True or False. THe string is accepted if at least one of those calls is True. Hence the or statement with tempBool.

This approach might still make wasteful recursive calls (Think of calling hello using same inputs but from different branches of if). A better solution would be memoization, e.g. this: What is memoization and how can I use it in Python?

edited May 23, 2017 at 10:33

CommunityBot

11 silver badge

answered Mar 8, 2014 at 13:46

Sudeep Juvekar

5,1183 gold badges31 silver badges35 bronze badges

1 Comment

Umer Farooq Over a year ago

manually grouping the different next states takes away the purpose of my algo. I have already tried the manual grouping method but I wanted to do it without human interventation.

Collectives™ on Stack Overflow

Dictionary returning same output Python

2 Answers 2

5 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related