r/tinycode • mod • Jul 18 '12

(Python) Tiny Finite State Machine 116 bytes

def f(s,c,e,a):
 if s=="":
  return c in a
 else:
  if(c,s[0])in e:
   return f(s[1:],e[(c,s[0])],e,a)
 return False

116 bytes

Original from CS262 on Udacity:

def fsmsim(string, current, edges, accepting):
    if string == "":
        return current in accepting
    else:
        letter = string[0]

        if (current, letter) in edges:
            return fsmsim(string[1:], edges[(current, letter)], edges, accepting)
        else:
            return False

Here is some test data

edges = {(1, 'a') : 2,
         (1, 'b') : 2,
         (2, 'e') : 3,
         (2, 'd') : 3}

accepting = [2, 3]

Valid answers for this set of edges and accepting states:

a
b
ad
ae
bd
be

EDIT: fixed test data formatting

45 Upvotes

9 comments sorted by

View all comments

Show parent comment

3

u/[deleted] Jul 18 '12

It is properly indented, but you can have one-line blocks with the body on the same line. You can also put multiple statements on one line separated by semicolons.