[Skip Navigation] [CSUSB] / [CNS] / [Comp Sci & Eng Dept] / [R J Botting] / [Samples] / months
[Index] [Contents] [Source Text] [About] [Notation] [Copyright] [Comment/Contact] [Search ]
Thu Nov 20 12:34:19 PST 2008

Contents

    Sample Problem: Find a Simple Way to Encode Three Letter Month Names

      Author
    1. Dick Botting

      History
      1. Started: Wed Jun 21 18:14:02 PDT 1995
      2. Completed: Thu Jun 22 20:32:58 PDT 1995A
      3. Comment from Paul Black Tue Feb 6 09:41 PST 1996
      4. Revision and diagrams: Tue Apr 9 10:07:12 PDT 1996

      Problem

       To develop a function which is given three letters that spell out an abbreviation for a month: Jan, Feb, jan, ... returns as a result the number of the month: Jan+>1, ..., Dec+>12

      There is one nice property of the real data: it is guaranteed to be a real month - it will be output as part of the UNIX 'date' command. So we don't have to worry about words that are not months. Our function can return any number it likes.

      Analysis

      We will encode each letter as a number and add them up the result will be the number of the month.

    2. month=code(let1)+code(let2)+code(let3)

      The fun is in finding a suitable code...

      Since we have 19 unknowns and only 12 constraints we can expect there to be several solutions -- there should be 7 letters that we can have any value we like, and then 12 will be determined by our chosen values. There is of course a possibility that no set of values for our variables can possibly satisfy all 12 constraints. If so we will find a variable that has to have two different values.

      We will write it in algebraic form with single lower case letters standing for the codes of the corresponding character. So we start by listing the months (on a piece of paper) and then the letters that appear in them:

    3. Equations_1::=
      Net{
        For a,b,c,d,e,f,g,j,l,m,n,o,p,r,s,t,u,v,y:Int.
      1. (1): j+a+n = 1.
      2. (2): f+e+b = 2.
      3. (3): m+a+r = 3.
      4. (4): a+p+r = 4.
      5. (5): m+a+y = 5.
      6. (6): j+u+n = 6.
      7. (7): j+u+l = 7.
      8. (8): a+u+g = 8.
      9. (9): s+e+p = 9.
      10. (10): o+c+t = 10.
      11. (11): n+o+v = 11.
      12. (12): d+e+c = 12.

        Now I have several ways to tackle these:

        Alternative Approaches

          Code them up in Prolog and let that do the hard work, by assuming that all that answers are in some sensible range (But what?????)

          Go an buy a linear algebra package.

          Go and hire a mathematician.

          Go to the library and look up the algorithms....

        . . . . . . . . . ( end of section Alternative Approaches) <<Contents | End>>

        A Mistake

        What I chose to do included a couch, some music, a non-alcoholic brew, and a little bit of luck... Then coded up my answers, tested them and did not notice the bug...

        It was only when I came to write up how I found the solutions that I found I had made several errors... including one that should have seen when I tested the code.... But such is the strength of ego that I could not see my own errors....

        Learn from this.... it is not enough to test a program, you have to be able to explain why it works.

        So here is my reconstruction of how I should have tacked it. Please check for mistakes.

        A Better Approach

        First I noticed that some of the months where similar enough that taking the difference between two equations will remove two variables. This is documented by the explanation:
      13. subtract::=Subtract one equation from the other, side by side.

        This works because of one of Euclid's Axioms: subtracting equals from equals gives equals.

        More importantly, the original pair of equations can be replaced by a pair where one is much simpler.

        Jun and Jul are nearly the same.

      14. (6, 7, subtract)|- (13): l-n=1.

        Jun and Jan are nearly the same.

      15. (6, 1, subtract)|- (14): u-a=5.

        Mar and Apr are similar.

      16. (4, 3, subtract)|- (15): p-m=1.

        Mar and May are almost the same.

      17. (5, 3, subtract)|- (16): y-r=2. }=::Equations_1;

        So I have a new set of equations that are indeed similarly to the original set:

      18. Equations_2::=
        Net{
          For a,b,c,d,e,f,g,j,l,m,n,o,p,r,s,t,u,v,y:Int.
        1. (14)|- (2.1): u-a = 5.
        2. (2)|- (2.2): f+e+b = 2.
        3. (3)|- (2.3): m+a+r = 3.
        4. (15)|- (2.4): p-m = 1.
        5. (16)|- (2.5): y-r = 2.
        6. (6)|- (2.6): j+u+n = 6.
        7. (13)|- (2.7): l-n = 1.
        8. (8)|- (2.8): a+u+g = 8.
        9. (9)|- (2.9): s+e+p = 9.
        10. (10)|- (2.10): o+c+t = 10.
        11. (11)|- (2.11): n+o+v = 11.
        12. (13)|- (2.12): d+e+c = 12.

          Now

        13. (2.8, 2.1, subtract)|- (2.13): g+2a = 3.

          I have a visual brain - it needs pictures so I sketched out a picture where each equation with 3 unknowns was a triangle and each equation with two unknowns was a line.

          Simplicial Complex

          I found it easy to place values on this diagram and work out the consequences.

          In the code I assumed the following:

        14. Let{
        15. (2.14): m=r=n=o=c=e=b=0.


        16. (2.14, 2.4)|- (2.15): p=1.
        17. (2.14, 2.5)|- (2.16): y=2.
        18. (2.14, 2.7)|- (2.17): l=1.
        19. (2.14, 2.3)|- (2.18): a=3.
        20. (2.18, 2.13)|- (2.19): g= -3.
        21. (2.18, 2.1)|- (2.20): u=8.
        22. (2.16, 2.14, 2.9)|- (2.21): s=8.
        23. (2.14, 2.2)|- (2.22): f=2.
        24. (2.14, 2.12)|- (2.23): d=12.
        25. (2.14, 2.10)|- (2.24): t=10.
        26. (2.14, 2.11)|- (2.25): v=11.
        27. (2.14, 2.20, 2.6)|- (2.26): j= -2.

        28. }

          These are the values expressed in the code.... [ months.cc ]


        }=::Equations_2.

        Comments by Readers

          From Paul Black Tue Feb 6 09:41 PST 1996

           
           I was reviewing your developement of the "months" function, URL
            http://www.csci.csusb.edu/dick/samples/months.html
           In the final code (beginning with Let{(2.14) ...) I don't see
           any value for the letter "j"!
          

           Paul E. Black  p.black@ieee.org
          

          
Reply:
Thank you - I have added
[ 2.26 ]
above.  I took the oportunity to fix a typo in
[ 2.17 ]
where it used to say n=1 rather than l=1.

          

          Request For Comment
          
Your comments are welcome to be added here with full
citation etc.... Send them me via
[ ../mailme.html ]

          

        . . . . . . . . . ( end of section Comments by Readers)  <<Contents | End>>

        Exercise 1
        
Choose a different set of values for m,r,n,...in step 2.14 and
convince yourself that the same routine generates a set of values
for the rest.

        

        Exercise 2
        
Set up the equations for the days of the week(m+o+n=1,...).  Find a
solution.  Hint: s,u, and t are the central variables here.

        

        Exercise 3
        
Using my code as a basis, and the results of exercise 2 above, produce
a function to decode the days of the week.

        

        Exercise 4
        
Why can you not do this (unless a miracle has occurred) to recognize
the postal symbols for the states in the USA?
Can you recognize both days or the week and months in a single
function using the dame technique?  If so: do it, else, explain why not.

        

        Review Exercise 1
        
Do this after completing the work on arrays.  How can you
use an constant array to replace the int code(char) function neatly?
Do it.

        

        Advanced Exercise 1
        
Embed the tested functions for months and days in a UNIX command
that echoes the number when given a single argument with a three day
abbreviation.

      

      End