Donald E. Knuth in Python, cont'd

[Antti J Ylikoski]

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.ylikoski at gmail.com