Donald E. Knuth in Python, cont'd

Discussion in 'Python' started by Antti J Ylikoski, Apr 11, 2012.

  1. 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 J Ylikoski, Apr 11, 2012
    #1
    1. Advertising

  2. On 2012-04-11, Antti J Ylikoski <> 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!!
    Grant Edwards, Apr 11, 2012
    #2
    1. Advertising

  3. On 11.4.2012 16:23, Grant Edwards wrote:
    > On 2012-04-11, Antti J Ylikoski<> 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
    Antti J Ylikoski, Apr 11, 2012
    #3
  4. Antti J Ylikoski

    Guest

    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.
    , Apr 11, 2012
    #4
  5. Antti J Ylikoski

    John Nagle Guest

    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
    John Nagle, Apr 11, 2012
    #5
  6. 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.
    Antti J Ylikoski, Apr 11, 2012
    #6
  7. Antti J Ylikoski

    Tim Daneliuk Guest

    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
    Tim Daneliuk, Apr 16, 2012
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Noah Roberts

    OT: knuth

    Noah Roberts, Sep 28, 2003, in forum: C++
    Replies:
    4
    Views:
    498
    Noah Roberts
    Sep 28, 2003
  2. gelbeiche
    Replies:
    6
    Views:
    423
    CrayzeeWulf
    Apr 25, 2005
  3. Ministries In Faith

    Thank you Mr. Donald J. Trump

    Ministries In Faith, Jul 11, 2009, in forum: Java
    Replies:
    0
    Views:
    301
    Ministries In Faith
    Jul 11, 2009
  4. Antti J Ylikoski
    Replies:
    12
    Views:
    312
    Dennis Lee Bieber
    Mar 19, 2012
  5. Juhani Ylikoski
    Replies:
    2
    Views:
    186
    Juhani Ylikoski
    Nov 13, 2012
Loading...

Share This Page