I wrote about a straightforward way to program D. E. Knuth in Python, and received an excellent communcation about programming Deterministic Finite Automata (Finite State Machines) in Python.
The following stems from my Knuth in Python programming exercises, according to that very good communication. (By Roy Smith.) I'm in the process of delving carefully into Knuth's brilliant and voluminous work The Art of Computer Programming, Parts 1--3 plus the Fascicles in Part 4 -- the back cover of Part 1 reads: "If you think you're a really good programmer -- read [Knuth's] Art of Computer Programming... You should definitely send me a résumé if you can read the whole thing." -- Bill Gates. (Microsoft may in the future receive some e-mail from me.) But now for programming Knuth with the DFA construct. Following is a working Python program which (almost) calculates the date of the Easter in the given year. See Donald E. Knuth: The Art of Computer Programming, VOLUME 1, 3rd Edition, p. 160, Algorithm E, Date of Easter. I chose something trivial because I want the programming methodology to be as clearly visible as possible. The program contains quite a ballet between integers and floats, but I wanted to do this as meticulously as possible. ------------------------------------------------------------------------ # Date of Easter from D. E. Knuth. Antti J Ylikoski 04-11-2012. # # See Donald E. Knuth: The Art of Computer Programming, VOLUME 1, 3rd # Edition, ISBN 0-201-89683-4, ADDISON-WESLEY 2005, p. 160. # # The following stems from Roy Smith in the news:comp.lang.python. # # ------------------------------------------------------------------------ # #When I've done FSMs in Python, I've found the cleanest way is to make #each state a function. Do something like: # #def a1(input): # # (Do the work of Phase A1.) # if <zap>: # return a5 # goto state a5 # else: # return a1 # stay in the same state # ## and so on for the other states. # #next_state = a1 #for input in whatever(): # next_state = next_state(input) # if next_state is None: # break # #You can adjust that for your needs. Sometimes I have the states return #a (next_state, output) tuple. You could use a distinguished done() #state, or just use None for that. I wrote the example above as global #functions, but more commonly these would be methods of some StateMachine #class. # # ------------------------------------------------------------------------ # # The program calculates correctly after D. E. Knuth but it has the # actual # yearly calendar Easter dates wrong. See Knuth's text. # import math def E1(): # Phase E1 in Knuth's text. global G, Y G = (Y % 19) +1 return E2 # next state: E2 def E2(): # Phase E2 in Knuth's text. global Y, C C = math.floor(float(Y)/100.0) + 1 return E3 # next state: E3 def E3(): # Phase E3 in Knuth's text. global X, Z, C X = math.floor((3.0*float(C))/4.0) Z = math.floor((8.0*float(C) + 5.0)/25.0) - 5 return E4 # next state: E4 def E4(): # Phase E4 in Knuth's text. global D, X D = math.floor((5.0*float(Y))/4.0) - X - 10 return E5 # following state: E5 def E5(): # Phase E5 in Knuth's text. global E, G, Z auxE = (11*G + 20 + Z - X) if auxE < 0: auxE += 30 E = auxE % 30 if (E == 25 and G > 11) or E == 24: E += 1 return E6 # following state: E6 def E6(): # Phase E6 in Knuth's text. global N, E N = 44 - E if N < 21: N = N + 30 return E7 # next state: E7 def E7(): # Phase E7 in Knuth's text. global N, D N = N + 7 - ((D + N) % 7) return E8 # following state: E8 def E8(): # Phase E8 in Knuth's text. global N, Y if N > 31: print(int((N - 31)), "th ", "APRIL, ", Y) else: print(int(N), "th ", "MARCH, ", Y) return None # No following state # Next, the main function: # #next_state = a1 #for input in whatever(): # next_state = next_state(input) # if next_state is None: # break def Easter(Year): global G, Y, C, X, Z, D, N, E Y = Year nextState = E1 continueLoop = 1 while continueLoop: nextState = nextState() if nextState is None: break if __name__ == '__main__': inp0 = int(input("The year: ")) Easter(inp0) # Plaudite cives, acta est fabula. # # AJY 04-11-2012. ------------------------------------------------------------------------ kind regards, Antti J Ylikoski Helsinki, Finland, the EU http://www.tkk.fi/~ajy/ http://www.tkk.fi/~ajy/diss.pdf antti.yliko...@gmail.com -- http://mail.python.org/mailman/listinfo/python-list
