Zeller's Congruence in C#

In "Problems for Computer Solution" by Fred Gruenberger and George Jaffray, one of the problems revolved around determining what day of the week for any date. The algorithm is called Zeller's Congruence.

In this day and age, where finding the day of the week is as simple as DateTime.Now.DayOfWeek programmers may not realize that in the early days of computing it was much more difficult. One way was to code an implementation of Zeller's Congruence. Towards the end of the 19th century, Christian Zeller formulated an algorithm that could calculate the day of the week.

Back in the 60's, second year computer science students used the problem of implementing this algorithm as a semester project. Yet, now even if we do not use the .Net Framework, implementing the algorithm is the work of a few minutes.

The Algorithm:

D = Day of the month
M = Month (With a trick, March is the first month of the year, January and February then being the 11th and 12th month of the previous year)
X = Decade (With a trick - see Month above)
C = Century (With a trick - see Month above)

(int(2.6 * M - 0.2) + D + X + int(X / 4) + int(C / 4) - (2 - C)) modulo 7

One cool trick in the code below is calculating the the month of the year (Including the trick above) using only a math, no logic.

Here it is step by step:

Start with the months as numbers: 1,2,3 ... 11,12
Add 9 to each month: 10,11,12 ... 20,21
Modulo each month by 12 (%): 10,11,0 ... 8,9
Add 1: 11,12,1 ... 9,10

So now we have what we wanted, Jan = 11, Feb = 12, Mar = 1 ... Nov = 9, Dec = 10

Here is the full algorithm:

string[] DaysOfTheWeek =
    {"Sunday", "Monday", "Tuesday",
    "Wednesday", "Thursday", "Friday", "Saturday"};

int Day = DateTime.Now.Day;
int Month = ((DateTime.Now.Month + 9) % 12) + 1;

int YearsInCentury = Month > 10 ?
    (DateTime.Now.Year - 1) % 100 :
    DateTime.Now.Year % 100;

int Century = YearsInCentury == 99 && Month > 10 ?
    (DateTime.Now.Year - 100) / 100 :
    DateTime.Now.Year / 100;

int DayOfWeek = ((((int)((2.6 * (float)Month) - 0.2)
    + Day + YearsInCentury + (YearsInCentury / 4)
    + (Century / 4) - (2 * Century))) % 7);

Console.Write(DaysOfTheWeek[DayOfWeek]);
Console.Read();

LINQ to the rescue!

If you have ever had multiple data sources that you pull into DataTables, you know that you can use the .Merge function to combine the data. But, what if there are dupicates? What about sorting the merged data?

Well, using LINQ to data, you can use the power of LINQ without needing SQL Server or a database at all, for that matter. Here is a simple example using LINQ to data, to sort and pull only distinct records in the merged DataTable.

static void Main()
{
    var dtFirst = new DataTable();
    var dtSecond = new DataTable();

    dtFirst.Columns.Add("Value", Type.GetType("System.Int32"));
    dtSecond.Columns.Add("Value", Type.GetType("System.Int32"));

    var row = new object[1];

    for (var i = 25; i >= 0; i--)
    {
        row[0] = i;
        dtFirst.Rows.Add(row);
        row[0] = i+5;
        dtSecond.Rows.Add(row);
    }

    dtFirst.Merge(dtSecond);

    IEnumerable MyTable = dtFirst.AsEnumerable();

    var dtLinqData = (from
            MyRow
        in
            MyTable
        orderby
            MyRow.Field("Value")
        ascending
        select
            MyRow.Field("Value")).Distinct().ToArray();

    Console.WriteLine("Original Data");

    foreach (DataRow dr in dtFirst.Rows)
        Console.Write(dr["Value"] + " ");

    Console.WriteLine();
    Console.WriteLine("Linq Data");

    foreach (var dr in dtLinqData)
        Console.Write(dr + " ");

    Console.Read();
}

Where have all the colors gone?

If you are programming in Silverlight, you probably have seen all the colors available in the XAML. Want a line that is AliceBlue, no problem, but if you want to create the same line programatically in C#, good luck.

The Colors class is just a small subset of all the HTML named colors, so the only way to add AliceBlue is to use Color.FromArgb, so you go out to a website that lists all the colors' RGB values. AliceBlue is #F0F8FF, so you paste the RGB value into Color.FromArgb.

But wait! Color.FromArgb expects 4 bytes, not a single number (The first byte is the Alpha value - i.e. the transparentcy of the color, hence the A in front of the RGB) and our color is only 3 bytes. We can add #FF in front of #F0F8FF but Color.FromArgb expects them to be separate values separated by a comma.

Color.FromArgb(#FF, #F0, #F8, #FF) will not work because C# does not recognize them as numbers. The key to having C# recognize them as hex numbers is to replace the hash(#) with 0x. So AliceBlue is now Color.FromArgb(0xFF, 0xF0, 0xF8, 0xFF).

Too much work you say? I agree. I just want to use my named colors. So, I created my own Color class that in Silverlight will output named colors!

The code looks like this:


private class MyColors
{
    public static Color Aliceblue
    {
        get
        {
            return GenerateColorStruct(0xFFF0F8FF);
        }
    }

    .
    .
    .

    private static Color GenerateColorStruct
                                    (uint color)
    {
        var mask = 0x000000FF;
        var returnval = new Color
        {
            A = ((byte)((color >> 24) & mask)),
            R = ((byte)((color >> 16) & mask)),
            G = ((byte)((color >> 8) & mask)),
            B = ((byte)((color) & mask))
        };

        return returnval;
    }
}

The entire .cs file can be found here. Since this is a private class that you can add to any Silverlight page.cs file that needs named colors , you can also add your own named colors that you want to use all the time!

You can also compile it to its own dll, but I like it better in the page.cs file. For size of outputs sake, right before you publish you can remove all the unused colors.

Old Games In Silverlight

It continually amazes me how many great games were published in the 80's and 90's in hobby programming magazines. Sure, they are not the type of games that a company like Electronic Arts would be interested in and are definitely not up to the standards of today's games on the PC, but casual gaming on the web and mobile devices has possibly created a new home for these games.

In one of my old programming magazines (Compute's! Gazette, June 1986 - Issue 36, Vol. 4, No. 6) described a game called Switcheroo, by Kevin Mykytyn and Mark Tuttle. A simple connect 5 on a 5x5 grid (horizontally or vertically, no diagonals) with a twist. The player can place a piece of his color on an empty space or he may shift a column up or down, or shift a row left or right. Any pieces that are removed from the board by the shift are places in at the end of the column or row in the newly vacant space.

I think that this game would be a great coding test for Silverlight, so I will be posting a multi-part blog entry on writing Switcheroo in Silverlight2.0.

Unfortunately, all the games published in Compute's! Gazette were in a version of Machine Language called "MLX", so the effort would be heroic to try to adjust the code to a more modern platform such as Silverlight. And, with the fact that there was no AI (It was a 2 player game) and we will want to play against the computer, we will be starting from scratch.

Permutations

In "Problems for Computer Solution" by Fred Gruenberger and George Jaffray, permutation was a topic for one of the problems.

Now everyone that has made it through the most basic classes in computer science had a class that at least touched on the concept of combinations and permutations. For those that have never take computer math class, permutation is the concept of showing every sequence that can be created using every element in the set only once.

For example: A set containing three characters, 'A', 'B' and 'C'. There are six different permutations of this set: 'ABC', 'ACB', 'CAB', 'BAC', 'BCA', 'CBA'

Click here for a more complete description of Permutation

If you add another character 'D' the number of permutations go to 24. So that pattern goes:

1 character = 1 permutation
2 characters = 2 permutations
3 characters = 6 permutations
4 characters = 24 permutations

Now anyone see the pattern? 1 x 2 x 3 x 4? Or 4! (factorial). Another way to write 4! is 4 x (3 x (2 x 1)) or 4! = 4 x 3! Basic computer science professors use factorials as the basic example in recursion.

private int Factorial(int Number)
{
    if(Number == 0) return 1;
    else return Number * Factorial(Number - 1);
}

The problem in the book does not involve factorials but the actual generation of all the possible permutations of the elements in the set. I've already hinted that it involves recursion, can you figure it out?

Take a few minutes before reading any further.

OK, if you got it then good for you. now implement it. While your doing that, I'll explain it to everyone else.

So, if we are going to use recursion we need to take into account two things:

1. Solving a subset of the problem helps solve the entire problem
2. There must be a base case where the answer is known

Lets take the second point first. If a set only contains a single element then that set can only have a single permutation, so this can be our base case.

Next, how can a subset of the problem help solve the entire problem? It may be easier to understand in an example:

If you have the set 'A' 'B', all the permutations are are: 'AB' and 'BA'.

If you now add the character 'C', you can take each previous permutation and add the new character to the front of the string. Then you just cycle the new letter through each position in the string until it is at the end. A manual example looks like this:

C AB - A C B - AB C
C BA - B C A - BA C

The book suggests you write separate functions for a single character string, a two character string, a three character string and a four character string with the four first calling the three which first calls the two which first calls the single character string function.

Once you get to writing the three and four character string function you will notice that 99% of your code looks the same in these two functions. Now you can, if it does not do so already, alter the two character function to work just like the three and four character functions.

Now you should be able to roll these all together to get a recursive function that generates all permutations of a string of any length.

But, this is dot net! We are object oriented, so we should be able to now alter the function to accept an array of object arrays and output a new array of object arrays. Through in a little bit of generics and you will have a completely reusable permutation generator!

This was a fun little function to write and it got my recursive juices flowing. Maybe I'll attack a simple maze generator and solver next! Who knows?

Welcome to "Taking Dot Net 'Old School'"

This may not be what you first think of when you see the term "Old School". Then again it might.

I, like many programmers, have opinions on "how" things should be done. I had never really formalized my thoughts until I read this blog post by Scott at:

http://headinside.blogspot.com/2008/04/early-days-of-computing.html

And specifically the quote:

"If you want to develop something that is perceived as new and original, start by going through the older works in the field, not the newest."

I see the truth of this all the time at my job. I see programmers that jump on the latest tool with wild abandon yet refuse to learn the grounding technologies that would teach them the proper way to use this new tool.

You all know about the old saw, "If the only tool in the programmers toolbox is a hammer, every problem is a nail."? Well I have a corollary, "If the programmer only knows how to use a hammer, he will try to drive a nail with every tool". One programmer on my team, a long time ago and thankfully not working for the company anymore, was like that.

I once explained his poor coding to my wife with my corollary finishing with "... so now he has this new tool, call it a high price worm drive power saw, and he is using it to drive nails into 2 by 4s." Of course my wife giggled at the mental image. It is a case of using a cool tool for the cool tools sake and to say he did, rather than taking the time to understand the underlying technology and using it where it is most appropriate.

But, I digress. With this blog I will explore programming with dot net: new tools, old concepts and just trying things with my favorite platform.

From Scott's blog I followed a rather crooked path (I could not even begin to retrace that path) and wound up finding a reference to an OLD computer science book filled with computer problems.

The title? "Problems for Computer Solution" by Fred Gruenberger and George Jaffray

The book is filled with problems from the early days of computing (circa 1965, one year before I was born!). Some of the problems confused me and some bored me but most of the amazed me.

For example: How many people know how to calculate the day of the week that a specific date falls on? Neither did I. The book explained that one way is to use a simple algorithm called "Zeller's Congruence". It did not just have an explanation of the equation, but also ways to explore the concept further. Unfortunately, they all revolve around the base language (FORTRAN) and the base system (An IBM 1620*) that the writers used when developing these problems.

As the posts to this blog unfold I will, among all the other things I want to do here, is explore selected problems from this book.

Secondly, I have quite a few old computer programming magazines and I would like to go farther than Scott and explore some of the programs (I'm astounded by how many cool games were published that would make great Silverlight web games!).

I hope that you find my posts as interesting as I do, thanks.

______________________________________________________

* Believe it or not, the IBM 1620 was a decimal computer, i.e. it thought in decimal (0 through 9) instead of binary (0 and 1)!