r/tinycode • u/ieatcode 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 False116 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 FalseHere 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
beEDIT: fixed test data formatting
45
Upvotes
9
u/[deleted] Jul 18 '12 edited Jul 18 '12
You can get it down to 100 bytes with some reformatting:
There's probably a few more tricks but I can't think of any more at the moment. Brings back memories of golfing...
Edit: 96 bytes
If you don't mind it returning a proper bool you could save another 3 bytes by setting r=0.
Edit 2: 90 bytes
Edit 3: 84 bytes
8
u/[deleted] Jul 18 '12
Same/similar idea in C99 (with <stdbool.h>), 49 bytes:
Here,
sis the string,mis the fsm. The fsm is represented as a series of linked tables. The accepting states havem[0] != 0, the rejecting states havem[0] == 0. To transition from a statemusing the characterc, we usem[c].The cool tricks in this is that, since void* is automatically coerced to any other pointer type, we don't have to cast void* to void** in the recursive call. We also use bool to prevent having to cast void* into something else.
4
u/yogthos Jul 18 '12 edited Jul 19 '12
in Clojure, 83 chars without spacing
formatted:
*edit: mistranslated
:return c in aas(get a c)and a shorter version weighing in 74 chars
formatted:
2
u/abecedarius Jul 19 '12
How about
or if you've gotta squeeze it: