[Skip Navigation] [CSUSB] / [CNS] / [Comp Sci & Eng Dept] / [R J Botting] / [Samples] / months
Thu Nov 20 12:34:19 PST 2008

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

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