Velocity Reviews > Donald E. Knuth in Python, cont'd

Donald E. Knuth in Python, cont'd

Antti J Ylikoski
Guest
Posts: n/a

 04-11-2012

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
http://www.velocityreviews.com/forums/(E-Mail Removed)

Grant Edwards
Guest
Posts: n/a

 04-11-2012
On 2012-04-11, Antti J Ylikoski <(E-Mail Removed)> wrote:

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

--
Grant Edwards grant.b.edwards Yow! I'm RELIGIOUS!!
at I love a man with
gmail.com a HAIRPIECE!! Equip me
with MISSILES!!

Antti J Ylikoski
Guest
Posts: n/a

 04-11-2012
On 11.4.2012 16:23, Grant Edwards wrote:
> On 2012-04-11, Antti J Ylikoski<(E-Mail Removed)> wrote:
>
>> 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...
>
>
>

))))))

As to AI in Python, see

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

kind regards, Andy Y. alias Dr. Why

mwilson@the-wire.com
Guest
Posts: n/a

 04-11-2012
Antti J Ylikoski wrote:

>
> 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
Guest
Posts: n/a

 04-11-2012
On 4/11/2012 6:03 AM, Antti J Ylikoski wrote:
>
> 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
Guest
Posts: n/a

 04-11-2012
On 11.4.2012 23:20, John Nagle wrote:
> On 4/11/2012 6:03 AM, Antti J Ylikoski wrote:
>>
>> 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
Guest
Posts: n/a

 04-16-2012
On 04/11/2012 03:20 PM, John Nagle wrote:
> On 4/11/2012 6:03 AM, Antti J Ylikoski wrote:
>>
>> 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.

--
-----------------------------------------------------------------------
Tim Daneliuk

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Juhani Ylikoski Python 2 11-13-2012 07:52 AM Ministries In Faith Java 0 07-11-2009 07:05 PM Annika1980 Digital Photography 2 05-01-2008 09:05 PM Lawrence D'Oliveiro NZ Computing 2 04-29-2008 11:16 AM Noah Roberts C++ 4 09-28-2003 06:12 PM

Advertisments