.Open Sample Problem: Find a Simple Way to Encode Three Letter Month Names . Author Dick Botting . History .Box Started: Wed Jun 21 18:14:02 PDT 1995 Completed: Thu Jun 22 20:32:58 PDT 1995A Comment from Paul Black Tue Feb 6 09:41 PST 1996 Revision and diagrams: Tue Apr 9 10:07:12 PDT 1996 .Close.Box . 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. 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: 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): j+a+n = 1. (2): f+e+b = 2. (3): m+a+r = 3. (4): a+p+r = 4. (5): m+a+y = 5. (6): j+u+n = 6. (7): j+u+l = 7. (8): a+u+g = 8. (9): s+e+p = 9. (10): o+c+t = 10. (11): n+o+v = 11. (12): d+e+c = 12. Now I have several ways to tackle these: .Open 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.... .Close Alternative Approaches . 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: 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. (6,7, subtract)|-(13): l-n=1. Jun and Jan are nearly the same. (6,1, subtract)|-(14): u-a=5. Mar and Apr are similar. (4,3, subtract)|-(15): p-m=1. Mar and May are almost the same. (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: Equations_2::=Net{ For a,b,c,d,e,f,g,j,l,m,n,o,p,r,s,t,u,v,y:Int. (14)|-(2.1): u-a = 5. (2)|-(2.2): f+e+b = 2. (3)|-(2.3): m+a+r = 3. (15)|-(2.4): p-m = 1. (16)|-(2.5): y-r = 2. (6)|-(2.6): j+u+n = 6. (13)|-(2.7): l-n = 1. (8)|-(2.8): a+u+g = 8. (9)|-(2.9): s+e+p = 9. (10)|-(2.10): o+c+t = 10. (11)|-(2.11): n+o+v = 11. (13)|-(2.12): d+e+c = 12. Now (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. .Image months.gif Simplicial Complex I found it easy to place values on this diagram and work out the consequences. In the code I assumed the following: Let{ (2.14): m=r=n=o=c=e=b=0. (2.14, 2.4)|-(2.15): p=1. (2.14, 2.5)|-(2.16): y=2. (2.14, 2.7)|-(2.17): l=1. (2.14, 2.3)|-(2.18): a=3. (2.18, 2.13)|-(2.19): g= -3. (2.18, 2.1)|-(2.20): u=8. (2.16, 2.14, 2.9)|-(2.21): s=8. (2.14, 2.2)|-(2.22): f=2. (2.14, 2.12)|-(2.23): d=12. (2.14, 2.10)|-(2.24): t=10. (2.14, 2.11)|-(2.25): v=11. (2.14, 2.20,2.6)|-(2.26): j= -2. } These are the values expressed in the code.... .See ./months.cc }=::Equations_2. .Open Comments by Readers . From Paul Black Tue Feb 6 09:41 PST 1996 .As_is I was reviewing your developement of the "months" function, URL .As_is http://www.csci.csusb.edu/dick/samples/months.html .As_is In the final code (beginning with Let{(2.14) ...) I don't see .As_is any value for the letter "j"! .As_is .As_is Paul E. Black p.black@ieee.org Reply: Thank you - I have added .See 2.26 above. I took the oportunity to fix a typo in .See 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 .See ../mailme.html .Close Comments by Readers . 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.