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 #
# ------------------------------------------------------------------------
#
#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
(e-mail address removed)

 

[Grant Edwards]

I wrote about a straightforward way to program D. E. Knuth in Python,

Yikes. I think if you're going to try to write AI in Pyton, you might
want to start out programming something a bit simpler...

 

[Antti J Ylikoski]

Yikes. I think if you're going to try to write AI in Pyton, you might
want to start out programming something a bit simpler...

))))))

As to AI in Python, see

http://code.google.com/p/aima-python/

kind regards, Andy Y. alias Dr. Why

 

[mwilson]

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. [ ... ]
#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.
# [ ... ]
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

def Easter (year):
global Y
Y = year
nextState = E1
while nextState is not None:
nextState = nextState()


would be a little cleaner. As you say, to be really clean, make a class.

Mel.

 

[John Nagle]

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.)

You don't need those books as much as you used to.
You don't have to write collections, hash tables, and sorts much
any more. Those are solved problems and there are good libraries.
Most of the basics are built into Python.

Serious programmers should read those books, much as they should
read von Neumann's "First Draft of a Report on the EDVAC", for
background on how things work down at the bottom. But they're
no longer essential desk references for most programmers.

John Nagle

 

[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.)

You don't need those books as much as you used to.
You don't have to write collections, hash tables, and sorts much
any more. Those are solved problems and there are good libraries.
Most of the basics are built into Python.

Serious programmers should read those books, much as they should
read von Neumann's "First Draft of a Report on the EDVAC", for
background on how things work down at the bottom. But they're
no longer essential desk references for most programmers.

John Nagle

Well -- so far I have read about a half of the Part I -- and for an
individual with a modern computer science education, the contents are
rather familiar and easy.

Andy Y.

 

[Tim Daneliuk]

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.)

You don't need those books as much as you used to.
You don't have to write collections, hash tables, and sorts much
any more. Those are solved problems and there are good libraries.
Most of the basics are built into Python.

Serious programmers should read those books, much as they should
read von Neumann's "First Draft of a Report on the EDVAC", for
background on how things work down at the bottom. But they're
no longer essential desk references for most programmers.

John Nagle

I strongly disagree with this.

There is a LOT of sloppy and incorrect code in the world because ill-taught
"programmers" do not understand the basics of algorithms, data structures,
and time/space complexity. One does not have to go to school to become so
educated, references like Knuth are timeless and still very much relevant
to the profession.

Yes, you can trust the libraries to do much, but have a mental model
for how things work with a deeper understanding of things like
the aforementioned makes a huge difference when working on your
own code.

P.S. Jon Bentley's "Programming Pearls" are also must reads for serious
programmers.