Viewing the contents of a binary file in Visual Studio

The toolset included in Visual Studio is just massive.  I swear that I could use Visual Studio for a lifetime and I still would not have plumbed all its depths.

With that thought in mind, I just realized that I need not look for poor third party applications to look inside a binary file.  I can use my trusty IDE Swiss Army knife, Visual Studio.

There are two ways to view and edit a binary file in Visual Studio:

1. Simply open a file with the extension of .BIN
2. After selecting the file in “Open –> FIle…” but before you click the “Open” button, instead click on the dropdown arrow on the “Open” button and select “Open With …”.  Then select “Binary Editor” from the list.

Either way you are then presented with the standard type of Binary File editor (3 columns, 1- The Offset, 2- The binary data & 3- The ASCII representation of the binary data).

In this editor, you can copy, paste, add, alter and delete bytes!

If only I had known this years ago!

Oracle Greater Than/Less Than calculations in the select list

At work I recently had a simple need.  I had a table with data.  One of the columns is a date-time stamp – lets call it “Last_Login_Date”.  I wanted a “Boolean” column that was a false if the value was less than 60 days old and true if it was older than 60 days. (Yes, I know that Oracle does not have a Boolean data type so how about Zero (0) for false and One (1) for true, OK?)

Ok, you would think that this would be simple: Just add the calculation in the select list, right? SYSDATE - Last_Login_Date > 60 AS Is_Old_Account.

But no, nothing can be easy can it.

With a fairly cryptic combination of Oracle commands I replicated what I wanted.  Here it is:

DECODE(GREATEST(FLOOR(SYSDATE – NVL(LAST_LOGIN_DATE, TO_DATE('2000/01/01', 'yyyy/mm/dd')), 60), 60, 0, 1) AS IS_OLD_ACCOUNT

And, here is the breakdown:

First NVL incase the field had never been populated.

Next, FLOOR to turn the difference into an integer (probably not needed, but during debugging, having an integer was easier to deal with.

Then, GREATEST takes two values, the date difference and my max value.  So, if the date difference is less than 60, the  GREATEST function will return 60.

Lastly DECODE will look at the value and say – If it is 60 return 0, else return 1. 

So, the end result is if the value is 60 or less, the value is 0 else it is 1.

Note:  I could have ran the SQL twice with a JOIN command and add to the where clauses the filters of  SYSDATE - Last_Login_Date > 60 and SYSDATE - Last_Login_Date <= 60 and a dummy column in the select list added in out “Boolean” column IS_OLD ACCOUNT, but this did not seem very efficient.

Calculating the average of two angles (two bearings actually)

I recently needed to find the average of two angles.  I was programmatically creating a irregular polygon. I wanted to draw a small square at the points of the polygon, and I wanted the squares to be rotated to the average of the two lines that met at that point.

The issue is that if you have two bearings, one at 20° and one at 350°, or one at 15° and one at 315°. If you just average the two numbers, you get 185°, but the more appropriate number is 5°.  This is called by some a “Wraparound issue” and if you search the web you will see lots of ways to solve this problem. Unfortunately they mostly try to solve it using a mathematical equation.  Now for people that have read this blog for awhile know that I am not allergic to math, but if we can solve this problem simply with an algorithm, we should … that’s what computers are for, right?

So, here is my algorithm and the thought behind it.

---

(Assumptions: 0 >= bearings < 360)

First if you look at the difference between the two bearings, you will see that there are two possibilities, the actual difference is greater than 180° or less than 180°.  Since we are only concerned about “fixing” the issue when the difference is greater than 180°, that is the first thing we will check.

We will call the smaller value bearing bearingA and the larger value bearing bearingB.

Since we know that bearingB has a larger value and that the difference is greater than 180, so bearingB > 180.

So, if we subtract 360  –  bearingB, then just add bearingA + bearingB and divide the total in half, we are 90% there.

One last check. If the result is less than 0, we need to add 360 back in.

So, example #1 20° & 350° 350 – 20 > 180 350 – 360 = –10 (–10 + 20) / 2 = 5 5 ≥ 0 = 5 °

So, example #2 15° & 315° 315 – 15 > 180 315 – 360 = –45 (-45 + 15) / 2 = –30 –30 < 0–30 + 360 = 354°

And here is the code:

Code Snippet

1. private static double GetAverageBearing(double bearingA, double bearingB)
2.         {
3.             if (bearingA > bearingB)
4.             {


5.                 var temp = bearingA;
6.                 bearingA = bearingB;


7.                 bearingB = temp;
8.             }
9.  
10.             if (bearingB - bearingA > 180) bearingB -= 360;
11.  
12.             var finalBearing = (bearingB + bearingA)/2;
13.  
14.             if (finalBearing < 0) finalBearing += 360;
15.             
16.             return finalBearing;
17.         }

StrSpn & StrCSpn in C#

After converting the c/c++ string tokenizing command strtok to c#, I thought I would look around to see there were any other interesting string commands in c/c++ that had not been integrated into c#. What I found was strspn and strcspn.

strspn (String Span) Returns the length of the longest substring that begins at the start of the string and consists only of the characters found in the supplied character array.

Code Snippet

1. private int strspn(string InputString, char[] Mask)


2. {


3.     int count = 0;


4.  


5.     foreach (var c in InputString)


6.     {


7.         if (!Mask.Contains(c)) break;


8.  


9.         count++;


10.     }


11.     return count;


12. }

strcspn (String Complement Span) Returns the length of the longest substring that begins at the start of the string and contains none of the characters found in the supplied character array.

Code Snippet

1.     private int strcspn(string InputString, char[] Mask)


2.     {


3.         int count = 0;


4.  


5.         foreach (var c in InputString)


6.         {


7.             if (Mask.Contains(c)) break;


8.  


9.             count++;


10.         }


11.         return count;


12.     }


13. }

C# Yields a better StrTok Command

Here is another use of the Yield command which allows us to create looping functions that return a value for each iteration. That is actually a great description of the StrTok command in C/C++.

The C/C++ StrTok command takes two parameters, an input string and a string of delimiting characters. After the first call to StrTok, the C/C++ programmer passes a null for the input string and StrTok returns the next Token in the original input string. Sounds like an attempt to create an Enumerable function. Unfortunately standard C/C++ does not have enumerable functions.

Here is a C# enumerable function that you allows you to iterate through the tokens found in the input string. This C# version takes two parameters as well, the input string and an array of delimiting charaters.

Then using built-in power from the .net framework we:

We split the string into a string array using the delimiting characters and we yield return each element in the string array where the element in the string arrays length is greater than 0.

Code Snippet

1. 
   private IEnumerable<string> StrToken(string TokenizableString, char[] Delimiters)


2. {


3.     foreach (var Token in TokenizableString.Split(Delimiters, StringSplitOptions.RemoveEmptyEntries))


4.     {


5.         yield return Token;


6.     }


7.  


8.     yield break;


9. }

A Checkers Rules Engine in C#

One of the things I've always wanted to program is a game using a Genetic Algorithm to generate the AI. Well at work I was talking about AI coding and my aforementioned desire came up and as we talked about it, the idea of using game of Checkers as the game I could use with a GA surfaced.

When I got home that evening and was relaxing after diner, I booted up the laptop and started cruising around the web. I was started looking around for a rules engine for checkers - hopefully in C#. You see my thought was, if I could find a rules engine that, from a given game board configuration and who's move it was, it would output all valid moves.

Well, no matter how I arranged the words in Google, I could not find a rules engine for checkers. I found a few complete C# checkers games but the rules were too integrated into the rest of the game for me to filter out.

So, I decided to write one.

I started with an enum to define the two players:
public enum PlayerColors { Black, Red }

Then I wrote a class to hold each checker piece:

CheckerPiece has a single constructor:
CheckerPiece(PlayerColors MyPlayerColor, int MyPieceLocation, bool MyIsKing)

Four properties:
public int PieceLocation { get; set; }
public bool IsKing { get; set; }
public PlayerColors PlayerColor { get; set; }
public List PossibleMoveLocations { get; set; }

and Three methods:
public char GetPlayCharacter()
public void FindAllMoves(char[] GameboardArray)
public void FindAllJumps(char[] GameboardArray)

The constructor sets the PlayerColor, PieceLocation, and IsKing.

PlayerColor defines which side the piece belongs to.
PieceLocation is an int from 0 to 63 defining each square of the game board.
IsKing is a bool that determines if the piece is a king or not.

GetPlayCharacter returns a lowercase r for a red piece, a lowercase b for a black piece, an uppercase R for a red king piece and an uppercase B for a black king piece.

a game board array is a char[64] array that can hold on of these chars 'r', 'R', 'b', 'B' or ' ' (a space).

FindAllMoves and FindAlJumps take in a GameboardArray and sets the PossibleMoveLocations list with all the possible Moves or Jumps.

Now with that built, I created the CheckersRulesEngine class.

CheckersRulesEngine has a single constructor:
public CheckersRulesEngine(char[] gameboardarray)

A static char array that holds a starting game board configuration for convenience:
static public readonly char[] StartingGameboardArray =
" b b b bb b b b b b b b r r r r r r r rr r r r ".ToCharArray();

Three properties:
public List MovablePieces { get; set; }
public List Pieces { get; set; }
public char[] GameboardArray { get; set; }

And Three Methods:
public void GetPiecesWithMoves(PlayerColors CurrentPlayer)
public void GetPiecesWithJumps(PlayerColors CurrentPlayer)
public string OutputAsciiBoard()

The constructor the GameboardArray and creates a CheckerPiece entry into Pieces for each piece defined in the GameboardArray.

GetPiecesWithMoves and GetPiecesWithJumps works its way through the Pieces collection and loads MovablePieces with the pieces that qualify.

OutputAsciiBoard is a helper function that outputs an ascii board showing the location of all the pieces.

You can get the c# code for the CheckersRulesEngine here! Or, you can download a Visual Studio 2008 solution that also includes a console program that plays a game of checkers against itself using random moves! The solution can be downloaded Here!

A c# class to convert between bases

Ever needed to work with numbers in base 17, or base 3? I have always wanted to write a Genetic algorithm that used base 3 numbers to represent the board - 0 empty, 1 my piece, 2 opponent piece. Recently at work, we needed to work with base 36 numbers. While doing some searching I also learned that some people needed numbers that were alpha-int (Where the letters preceded the numbers) instead of the standard int-alpha.

Here is a class that I think Microsoft left out. We work different systems and different numbers every day, so why didn't Microsoft include a base converter class? It probably was just too low on their list of priorities.

Well, here is my interpretation. It is a static class that exposes three overloaded functions:
Encode(long Value, sbyte Base)
Encode(long Value, sbyte Base, bool NumeralsFirst)
Decode(string Input, sbyte Base)
Decode(string Input, sbyte Base, bool NumeralsFirst)
BetweenBases(string Value, sbyte FromBase, sbyte ToBase)
BetweenBases(string Value, sbyte FromBase, sbyte ToBase, bool NumeralsFirst)

By using the BetweenBases function, you can convert directly from one base to another without decoding to a long in between.

The complete code for the class can be downloaded here.

The "Weekly" Newsgroup post #2

This is my second "Weekly" (Oh, that's a laugh) Newsgroup post.

In this post, we have what seems like a simple question: How to ensure that at most there is one occurrence of each character from a list of characters.

Or, to be more specific, Byron gave this example:

For example, a string [starting with a capital 'D' and a dash - ed] can have up to 4 unique digits between 1 and 4.

The following strings should pass:
D-1
D-14
D-1234
D-41

The following should fail:
D- (no digit)
D-0 (out of range)
D-5 (out of range)
D-11 (repeated digit)
D-1 2 (embedded space)
D-12345 (out of range and too long)

The first reply was by Peter Duniho, who instead of trying to answer the question suggested that Bryon try using C# instead. Many other replies sought to answer the question with brute force, the same way that C# would have to.

Now, I did not select this post because I contributed to it, but I did suggest using lookaheads and a true RegEx guru came up with the an amazingly elegant solution.

Which Peter immediately to exception to. Now, I would be the first to say that Peter is an amazing C# programmer and he leaves me in the dust, but it is BECAUSE he is such a great C# programmer that he seems to look at everything through C# goggles.

His argument boils down to Regular Expressions are hard and some people do not understand them, so do not use them.

Well, I agree that if you do not understand Regular Expressions, you should not use them, but the same holds true to C#, if you do not understand a language you should not be programming in it.

But, Peter points out, look how long it took this group to find an elegant solution. That definitely shows how hard Regular Expressions are. Well, this is a C# group not a Regular Expression group so it makes sense that it could take us awhile. I bet if we asked a non-trivial question on a Regular Expression group it would take quite a few iterations till they came up with an elegant C# solution.

Why did I not point this out to Peter in the post? I've found that you never really win an argument with him ... it is just best to smile, nod your head slowly and back out of the discussion.

So, with Peter's straw man firmly destroyed, lets take a look at this "elegant" Regular Expression by Jesse Houwing:

^D-(?:([1234])(?!.*\1)){1,4}$

The beginning is fairly straight forward, the string must start with a "D-"

Then we see, at the innermost set of parenthesis is ([1234]). This is a capture group that simply means, the next character I find must be in the set of 1 through 4 and then save it as a capture. Since the capture is not named, it can be referred to by its number. Since it is the first capture, it is #1, or \1, in RegEx speak.

Next we see another set of parenthesis, but the opening paren is immediately followed by "?!". This turns the RegEx code inside the parenthesis into what is called a Negative Lookahead. What it does is, it scans the rest of the string and if a match is found for the lookahead, the entire Regular Expression fails.

The RegEx code for the Lookahead is: .*\1

This simply says can I find a match to the character I found in the capture with any number of characters before it? Or, i.e. does the character ever appear again?

All of this is surrounded by a set of parens with the opening paren immediately followed by "?:". This says that we do not want to capture, i.e. remember the strings that RegEx would normally keep as a sub-group.

last but not least, "{1,4}$" informs the RegEx engine that the string must end with 1 to 4 matches from the parens that we said we did not want to keep track of for later.

This amazing little bit of code will fulfill all the requirements the original requester asked for and teach a bit as well!

How to make Asymmetrical Board Game maps in Silverlight

Or, how I spent my evenings at MIX09 in Las Vegas.

Last year, I began looking into writing board games with an asymmetrical map boards. I started with Awful Green Things from Outer Space (AGTFOS), a classic beer and pretzels game by Tom Wham. I started with an alternate game board graphic I downloaded from boardgamegeeks.com.



But, since the map is asymmetrical, there is no simple math function that, given an X,Y coordinate, would tell me what room in the spaceship I clicked on.

After a lot of googling, I found that boardgame programmers use a 2D array where every every element in the array corresponds to a pixel in the map image. Then set al the array elements to values that equal what room that pixel is in. This worked great, but it has a problem - No scaling. I could not scale the graphic and still know what room I was in.

WPF and Silverlight to the rescue!

So, as a proof of concept, I took a states map of the USA in SVG from Wikipedia and used ZamlTune to convert the SVG to XAML. Since all the elements in WPF are scalable and clickable, I was able to, with just a few lines of code, make the map aware of what element I was clicking and change its fill color.

That solved half of the problem of a asymmetrical board game map. The other issue is for movement and conflict. We need to know what states directly border the selected state. For this we need to go back to Comp Sci 350 - Data Structures. We need a graph.

Graphs have Vertexes and Edges. A vertex can be thought of as a location and the Edges as the roads to and from these locations. So, if we had a Graph with a vertex for each State and an edge to each bordering State, we could easily find out what States border each other.

Unlike previous silverlight examples I've posted, this one cannot be embeded since it needs to resize, so you need to open the link to run my example USA map. If we wanted to play Risk on a USA map, this would be a large positive step towards that goal.

As, you can see in the image the selected State is in Blue and the bordering States are in Light Blue. (Click on Image to Open The Silverlight Application)


Unfortunately the Graph object I wrote for this proof of concept is not nearly as full featured a Graph object as per my previous post.

And here is a zip file containing the entire Visual Studio 2008 Project.

The "Weekly" Newsgroup post #1

When I decided to become more active in the dot net community, I did a number of things:

I started this blog,
I started to attend the monthly meetings of our local users group ( omahamtg.com )
I started writing articles for codeproject.com (None of which I've finished yet - Bad Lee)

And, I started to hang out in the C# and ASP.net newsgroups as well as the forums at asp.net and silverlight.net in the hope that with my feeble knowledge I could help someone that the more experienced and knowledgeable would pass over as not worth their time.

Well, first thing I learned was that all the "Experts" on these newsgroups/forums are so helpful that I was only able to help a few people, and only then because their questions dovetailed exactly into my knowledge base.

But the big thing I learned was home much I could learn by reading the posted questions and answers. People are out there trying to do things with Dot Net that I never even thought of trying and reading in the replies how achieve those things has expanded my knowledge of all things Dot Net.

I used to think (and still do) that reading others source code was a great way to learn. When I found a link to Scott Hanselman's Weekly Source Code blog entries, I was forever indebted to Scott for searching the web and finding those few source code gems in the vast sea that is the Web.

I the same vein as Scott's Weekly Source Code posts, I'd like to start a "Weekly" posting of one or more Newsgroup/Forum questions that really deserve more focus than they received.

And Now: Question of the Week #1
================================
is there shorter way to code this

In this series of questions and answers, rodchar asks how he can get to two properties (Id and Text) of three different controls. His example shows the brute force way of taking an Object and through a series of IF statements determining if the Object "IS" of a certain type, then casting it to that type so as to access its ID and Text properties.

On reading the answers the Experts gave, it is obviously a perfect problem to be solved by an Interface. I chose this question because in my dealings with other programmers, Interfaces are the hardest part of OOP for them to grasp. Here in this one simple question, we have nearly the perfect example of how and where to use an interface.

Since there is now common parent that exposes the Text property, rodchar cannot just cast the Object to the parent. But, since they all already implement a Text property and an Id property, we can define an Interface that declares these two properties.

Here is the Interface suggested by DabblerNL

public interface ITextAndID 
{ 
string Text {get;set;} 
string ID{get;set;} 
}

Now, All that is needed is to have the Objects implement the interface. Since they technically have already done so, they only need to be declared.

public class InterfacedTextBox: TextBox, ITextAndID {} 
public class InterfacedCheckBox: CheckBox, ITextAndID {}

And viola! Just replace your old TextBox and CheckBox with the new versions and then all you need to do is cast the new controls "AS" your new interface: ITextAndID as so!

var TheId = (ITextAndID)TheObject).ID;
var TheText = (ITextAndID)TheObject).Text;

Being able to access these properties through the interface, and being able to implement the interface with no actual code other than the declarations makes this a pure example of interfaces!

Sudoku in Silverlight

You know how it is, you learn a skill (Programming in my case) because you see the results of others. Looking at the fruits of their labors, you say, "wow! I want to be able to do that." So you start learning, take some classes, read some books, maybe like me you enroll in the Computer Science program. If you get good, you may even get a job using your new found skill. But, did the learning of this skill lead you to the place you wanted to be, all those long years ago?

When I first started programming, it was to automate the games I was already playing. Then I moved into trying to replicate the types of games that I had played before on the computer. But as it usually happens, the real world got in the way. Instead of learning how to animate sprites, I had to learn how to connect to a database. Instead of graphics, I had to learn about algorithms.

Now, I'm not knocking my job and the work I do. I rarely go to "Work" since I get to indulge in my passion for programming every day. But, I feel this need to give more than lip service to the original reason that I got into the "Biz" in the first place.

Believe me, in 25 years the landscape of game programming has changed so much that I hardly recognize it! And, I've tried to keep my feet wet in the technology the entire time. The time when the ability to draw a digital stick figure and write a great game around it (Lode Runner) is long gone. When I first made up my mind to bite the bullet and truly try to learn game programming, in depth, the technology seemed so complicated that I almost quit.

But Rome was not built in a day and neither were any of my favorite games. Like I tell all of my junior programmers, "Start at the beginning, then just program each little piece until it is done”, I decided to start with the smallest bite I could “chew” and then just keep going. The first "Game" I wrote was a Sudoku generator with a Javascript back end. I Wrapped a website around it and launched it a couple of years ago.

Well, here is the thing about games, the are not all created equal. Sure Sudoku is a "Game" per se, but not really related to my true love, boardgames. So http://www.freedailygames.net languished for a few years without any upkeep. I even thought of just shutting it down, but according to Google analytics, I have a few very loyal customers. And, now with the new technology of Silverlight, I thought that updating my site with a Silverlight implementation of Sudoku would help me build my skills and give freedailygames.net a tech boost.

Well, here is my take on Sudoku in Silverlight.



And here is a zip file containing the entire Visual Studio 2008 Project.

So finish something already!

Now most of the better programmers love to code. Most Professional programmers love a challenge. So, to play to these twin desires, a lot of us have hard drives littered with the five-to-fifteen minute test bed projects that we create as we tackle a programming challenge.

This post is not about those projects.

This post is about the three quarters written Pente game that has been languishing on your hard drive for three years or the redesign to your website that you can never seem to quite finish or cool little app that just needs that last bit of spit and polish before you can release it to the world. These are the projects this post is about.

And why are they not done? The challenge to create them in the first place was exciting! Why is the bloom gone from the rose?

I think that this is a critical flaw in the personality of most programmers (Myself included). We love the challenge at the start. The puzzle that needs solving. We may spend hours or days working out how to do a single coding trick that we needed at the time. We sweat blood trying to breath a form of life into our creations.

Then when we get to the equivalent of getting our creations through Junior High, we look down on our creations and say we'll finish it later. We've got this other idea that we want to work on right now. And, so the cycle repeats itself, over and over again.

But, why do we abandon our nearly completed creations? Some say that it is because the creation process is done and now we need to polish and primp our creation so that it is truly finished and this is not nearly as fun as the process of creation. That may be true, but are we just big adolescents then, chasing after a series of "Oh shinny!" objects, that once we catch them are not nearly as fulfilling as we thought? Or are we intellectually lazy and when we get to the parts we do not find as fun we wander off in search of new challenges?

Could it be how we are trained to code in the first place?

From the moment we start we are bombarded with code snippets on how to do this or that. Homework assignments are fragments that do this or that function, never a complete application. If we are ever given an assignment to write a complete application, it is a class long project and is given such grading weight that we are almost forced to understand that "A complete application is so hard, we need to make it a very substantial part of your grade".

I do not know the answer to my question for myself, let alone everyone else. But, I can tell you that the last little bit of getting finished software out the door is about as fun to me as doing the dishes after a fine meal. but, just like those dishes, if you do you work and finish what you start then it gets easier the next time. After a few iterations, you will find yourself cranking our completed projects like copies out a Xerox machine. And if you think the high from solving a problem is great, then you will love the feeling of having your software being used the world over.

So, have you finished something today?

Tic Tac Toe in Silverlight

When I first started looking Silverlight, I looked around for tutorials that focused on topics I find interesting. I have found that I typically learn better if I'm applying learning to topics for which I have a passion.

I love games and one of the simplest is Tic Tac Toe. I thought if I could find a tutorial on implementing Tic Tac Toe in Silverlight, it would not only teach the basics of Silverlight development but would also teach how to interact with graphics. Unfortunately I could not find such a tutorial.

I eventually waded my way through much less entertaining tutorials and got my programming feet wet with Silverlight. As a test of my learning I wrote a two player Tic Tac Toe game.

After finishing my first AI post on Rock/Paper/Scissors I started looking for my next AI project. Well I had that two player Silverlight game laying around, how about I write an AI opponent for it?

What could be easier?

Well a lot of things could be easier, like "Hello World", but once I get my teeth into a project I see it to the end. Well, first things first, how have others designed AI opponents for Tic Tac Toe? A quick google search proved that I was definitely not blazing an new trails here. I found tons of examples for just about every type of AI for Tic Tac Toe.

But this webpage gives a simple set of patterns for matching. Best of all, they could be implemented using Regular Expressions!

So, here is my Silverlight AI Tic Tac Toe game where the pattern matching AI is implemented using Regular Expressions.



And here is a zip file containing the entire Visual Studio 2008 Project.

Programmers must continue to stand on the shoulders of giants

Many of the greatest thinkers credit their accomplishments to those that came before them by stating the old saying that even a dwarf can see farther than a giant when the dwarf stands on the shoulder of the giant. Or, in other words, they came to their breakthroughs by understanding the research and works created by notable thinkers of the past.

How can that help modern programmers? Simple, when was the last time you read a computer book or magazine? It does not matter what the subject was, just the fact you read it added a little bit to your knowledge and experience. It is amazing what great little tidbits you can find to enhance your abilities.

For me, that two that come to mind the fastest are from Programming Pearls by Jon Bentley, first published in 1986 and Expert C Programming: Deep C Secrets by Peter Van Der Linden first published in 1994.

From Programming Pearls, I learned the lesson that a senior developer should never answer the question that he was asked, but instead answer the base need that spawned the question. In Programming Pearls, the programmer asked how to do a disk-based merge sort. Now, yes I know that coding things like that went out of style a looooong time ago, but the underlying process that the author used to help the programmer has stayed with me ever since. This is because the author did not show the programmer how to implement the disk-based merge sort, but instead learned what the base problem the sort was supposed to fix and with his greater programming and analyst experience came up with a much faster and more elegant solution. No, I’m not going to tell you want the solution was, go read the book!

From Expert C Programming: Deep C Secrets, I learned a very simple programming principle: look at a problem from both directions. Where from one direction, a problem may include complex tracking code, worked the other way, the problem may be quite simple to code.

What does that exactly mean? Let us look at an example:

Say you need to build a comma delimited list of numbers from some input. You could say “I need a comma after every number except the last”. This is the normal view and leads to either adding a comma after every entry and then removing the last one once you have exited the loop, or checking in every iteration if its time it is the last element so that you do not add the comma.

But if you look at it from the other end and say “I need a comma before every number except the first”. Once stated this way, the problem is simple. It’s much easier to code a beginning edge case than an ending edge case.

The point of this post was not just to share these two fun little facts, but to show that we, as senior level developers, and those that wish to become senior level developers need to continue reading and learning. As long as we do that, the giants that we stand on will keep getting taller.

The simplest AI in C#

Creating board games on the computer is easy, creating an opponent to play the game against is hard.

A lot of us programmers out there are also board game enthusiasts. We would like nothing better than to sit down in front of the computer and spend a few hours out maneuvering some truly diabolical AI opponents. Whether it’s crushing the Axis in Axis and Allies, dominating Europe in Diplomacy or simply enjoying a quick game of world conquest in Risk, we get to enjoy our favorite board games without the need to coordinate a date and time with up to five or six of your friends. Even when you can take on each other online, sometimes getting everyone together is harder than winning the games you wish to play.

Well with a good AI, all your games become playable by yourself and with a great AI, they become obsessive as you try to, at first barley hold your own and later to finally dominate these awesome challengers. Yet, how are these opponents created? Other than creating a completely random opponent, writing an AI to play a board game at a high level is one of the hardest things in programming you could do.

Which brings me to my point: I’m not going to show you how to create a diabolical AI opponent. I’m not even going to say if I even know how to. What I want to show you though, is how to take that first step in writing AI’s, by creating what could possibly be the simplest AI opponent ever … for the game of “Rock, paper and scissors”.

There are many types of AI opponents, but in “Rock, paper and scissors” the only type of opponent is one that tries to predict his opponent’s next move. So let’s create a predictive AI.

What is the one piece of data that a predictive AI needs to calculate a decision? His opponents’ prior moves. So, as play of “Rock, paper and scissors” continues, we will need to accumulate the human player’s prior moves. The easiest way to do that is to hold them in a string, each character (‘R’, ‘P’ or ‘S’) representing a move.

To keep it simple, my AI will look for three move patterns. It will take the last two moves off the end of the string and add each of the three possible moves, in turn, on the end and do a string search to find how many times the human opponent played the same three move pattern previously. The IA will assume that the pattern with the highest count will be the one the human plays and will choose the move to beat it. If there was a tie (Even if that it is a tie of zero count for all three possible patterns) a move is picked randomly among the tied choices. Just to through a bit of confusion in, 10% of the time, the AI’s move will be completely random.

Now, this AI is by no means unbeatable, but playing against it in a race for the first to win 100 games, it is a very tough opponent, just like AI opponents should be.

The complete code for a console application implementing the “Rock, paper and scissors” AI can be downloaded here.

C# Yields a better Fibonacci Sequence

In the title of this blog entry I've done a bit of punning. This quick blog entry is about an alternate usage of the Yield command and how, for example, it can help build a better FibonacciSequence() function.

With the addition of the Yield command, we can now create looping functions that return a value for each iteration. Ever need to walk through a sequence and perform some fuction for each element? Now it is as easy as pie!

private IEnumerable FibonacciSequence(int MaxIterations)
{
    decimal i = 0;
    decimal j = 1;

    while(true)
    {
        yield return j;
        MaxIterations--;

        if (MaxIterations==0) yield break;

        var temp = (ulong) j;
        j = temp+i;
        i = temp; 
    }
}

private IEnumerable FibonacciSequence()
{
    return FibonacciSequence(49);
}

C# latin squares or shuffling a 2D array

Another problem in "Problems for Computer Solution" by Fred Gruenberger and George Jaffray concerns Latin Squares. Latin Squares are essentially two dimensional array that is shuffled in both dimensions.

I believe an example is now in order:

If you start with a set of numbers:
    1,2,3
Then shuffle them:
    3,1,2
You then have an array shuffled in a single dimension, but if you have a two dimensional array where your set of numbers:
    1,2,3
is repeated for each row:
    1,2,3
    1,2,3
    1,2,3

A possible suffling of this two dimensional array could look like this:
    3,1,2
    1,2,3
    2,3,1

The numbers are now shuffled so that each row and column is different from every other row and column and - here is the most important part - no member of the set is repeated in a row or column.

One possible way to progammatically generate a Latin Square is to use this trick - Use the first row not only as data but as the rule on how to place the values for all the rest of the rows.

I believe another example is now in order:

If you start with our shuffled set of numbers:
    3,1,2

Now look at the data and say:
In the first row the 2 is in the 3rd column.
In the second row the 2 is in the 1st column.
In the third row the 2 is in the 2nd column.

3rd column, 1st column, 2nd column - thats our first row! 3,1,2!

Now rotate the first row by taking the first value and placing at the end - 1,2,3 - and do the same thing to the original data. So, lets look at the data and say:
In the first row the 3 is in the 1st column.
In the second row the 3 is in the 2nd column.
In the third row the 3 is in the 3rd column.

Rotate one last time - 2,3,1 - and do the same thing to the original data. So, lets look at the data and say one last time:
In the first row the 1 is in the 2nd column.
In the second row the 1 is in the 3rd column.
In the third row the 1 is in the 1st column.

So using the rules above we generated:
    3,1,2
    2,3,1
    1,2,3

Here is a 9x9 array shuffled using the above trick:
    3,2,6,5,9,4,1,7,8
    5,6,7,8,4,2,3,1,9
    8,7,1,9,2,6,5,3,4
    9,1,3,4,6,7,8,5,2
    4,3,5,2,7,1,9,8,6
    2,5,8,6,1,3,4,9,7
    6,8,9,7,3,5,2,4,1
    7,9,4,1,5,8,6,2,3
    1,4,2,3,8,9,7,6,5

And, here is the code that can generate Latin Squares using the above trick:

using System;
using System.Collections;

class LatinSquare
{
    static void Main()
    {
        var LatinSquare = new int[9, 9];
        var Pattern = new int[] {1,2,3,4,5,6,7,8,9};

        Pattern = Shuffle(Pattern);
        
        //Use the first row as a pattern for the rest 
        //of the Latin Square
        for (int i = 0; i < 9; i++)
        {
            {LatinSquare[i,0] = Pattern[i];
        } 
            
        for (int x = 0; x < 9; x++)
        {
            for (int y = 1; y < 9; y++)
            {
                LatinSquare[Pattern[y] - 1, y] = 
                    LatinSquare[LatinSquare[x, 0] - 1, 0];
            }

            Pattern = RotatePattern(Pattern);
        }

        PrintLatinSquare(LatinSquare);

        Console.Read();
    }

    private static T[] Shuffle(T[] OriginalArray)
    {
        var matrix = new SortedList();
        var r = new Random();

        for (int x = 0; x <= OriginalArray.GetUpperBound(0); x++)
        {
            int i = r.Next();

            if (!matrix.ContainsKey(i)) 
            {
                matrix.Add(i, OriginalArray[x]);
            }
        }

        var OutputArray = new T[OriginalArray.Length];

        var counter = 0;
        foreach (DictionaryEntry entry in matrix)
        {
            OutputArray[counter++] = (T)entry.Value;
        }

        return OutputArray;
    }

    private static int[] RotatePattern(int[] Pattern)
    {
        int temp = Pattern[0];

        ;for (int y = 0; y < 9 - 1; y++)
        {
            Pattern[y] = Pattern[y + 1];
        }

        Pattern[9 - 1] = temp;

        return Pattern;
    }

    private static void PrintLatinSquare(int[,] LatinSquare)
    {
        //Print out the Latin Square
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                Console.Write(LatinSquare[j, i].ToString().PadLeft(3));
            }
            Console.WriteLine();
        }
    }
}

The code also available here!

Dr. Dobb's Journal CD, for the really nerdy "Old School" Dot Netters

I remember way back when I was just starting my computer science education. I would get the latest edition of Dr. Dobb's Journal, first at the news stand then later in the mail, and I would read it from cover to cover. Not that I understood a lot of what I was reading, but I realized that this was information that I would someday need to know.

My freshman level language was Pascal and I had not gotten to learning about pointers yet. Even though the published source code was in C, just reading the descriptions of the various algorithms that Dr. Dobb's Journal published helped my understanding of how complex data structures were built.

As I went from Computer Science class to Computer Science class I kept using my back issues as reference material. In a way, Dr. Dobb's Journal was, for me, the equivalent of Computer Science version of Scientific American. Well, like they say, three moves is the same as a fire, and I've moved may more times than three, so I have no idea where all my old DDJ's are or if I even still own them.

One day though, I got a letter asking me to re-subscribe, with the offer of all the issues from January 1988 through December 2000 on CD. Well that was just too good to pass up! I re-subscribed, got my CD and stashed it away.

Well, when Dot Net came out it had all those nifty System.Collection classes. Without any work I had a Stack, a Queue, a Hashtable and an ArrayList that was kinda like a cross between a linked list and an array. What need did I have for any of those "roll your own" abstract data types?

Live and learn I guess, but not all Stacks, etc, are built alike. The Dot Net version is array based. Now, I'm not saying that that is bad, just that it is not pointer (or Object Reference) based so it has different characteristics. Plus, where is my binary tree or red-black tree or skip list? How about a nice graph?

Well, out comes the CD. A quick search and I've got a nice bit of source code to start a C# version of a skip list.

Truth be told, for a complete toolbox for Dot Net and C# specifically, the System.Collection namespace should contain abstract data types based on (When Possible):

An Object based Array Implementation

A Generic Array Implementation

A Object based Object Reference Implementation

A Generic Object Reference Implementation

A Object based Pointer (unsafe) Implementation

A Generic Pointer (unsafe) Implementation

Since they all have different performance, security and memory concerns.

Maybe, someday, with the help of my trusty DDJ CD I'll even get around to coding all those ADT's!

Shuffling arrays in C#

Have you ever had a need to output some array of objects in a random order? Say a array of strings ... with 52 elements that each represent a playing card?

Well, if you have ever had a need to shuffle the elements in an array, you have probably found that there are only a few different algorithms: Either card swapping or assigning a random Key to each element and then sorting by the key.

Unfortunately there are quite a few issues involved with the swap shuffle so I wanted a to use the sort version. Well, what has tuples? Hashtables? Hashtables! So, how do you sort a Hashtable? Hmmmm, maybe I need to think harder about this.

Hey, did everyone realize their is a sorted version called a SortedList?

OK, So we will use the SortedList. Now I want this function to use Generics so that it will take an array of any type. So lets try!

(Mind you that this is not nearly as small as the implementation here but I am not posting here to show how to shuffle in the least number of lines or use the latest technology, but with an eye towards the most understandable source.)

private static T[] Shuffle <T> (T[] OriginalArray)
{
    var matrix = new SortedList();
    var r = new Random();

    for (var x = 0; x <= OriginalArray.GetUpperBound(0); x++)
    {
        var i = r.Next();

        while (matrix.ContainsKey(i)) { i = r.Next(); }

        matrix.Add(i, OriginalArray[x]);
    }

    var OutputArray = new T[OriginalArray.Length];

    matrix.Values.CopyTo(OutputArray, 0);

    return OutputArray;
}

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();