Creating a COM Object for Classic ASP

Summary

This blog post will show you how to create a COM (Component Object Model) object in C# that you can use in your classic ASP code.  Why would anybody do that?  Amazing as it might seem, there is a lot of classic ASP code out there in the form of legacy applications.  It’s monstrously difficulty to replace this code due to the fact that classic ASP isn’t compatible with anything and it doesn’t play nice with any other language.  So I’m going to show the basic mechanics of how to create a COM object in C# and how to incorporate it in your ASP code.

Writing Your First COM Program

First, let’s write the simplest program possible: Hello World.  I am going to follow a similar path as this article (which is where I learned some of this from):

Creating a COM object from scratch with C# 

There are a couple of changes I’m going to make because VS 2012 and above have a built-in GUID generator and I want to show how you can build something with no parameters, just to keep it ultra-simple.

Step 1 – Create your C# program

Create a new C# class library project.  You’ll need to add a using statement for the interop services library to the top of your code:

using System.Runtime.InteropServices;

Step 2: Construct the Class

For my example, I’m going to make this just a simple class with one method:

public class Launcher
{
    public string Hello()
    {
        return Hello world“;
    }
}

I’m leaving out the constructor, since it’s not used anyway.

Step 3: Presenting our Class Through an Interface

In order to access any methods or classes inside the COM module, we need to provide an interface.

public interface ILauncher
{
    string Hello();
}

You’ll also need to add the interface name as the base class for the Launcher object.


Step 4: Making the Connection

We need to add an attribute to our class to make sure it doesn’t automatically generate another interface (we want to use the interface we typed up manually):

[ClassInterface(ClassInterfaceType.None)]
public class Launcher : ILauncher
{
    public string Hello()
    {
        return Hello world“;
    }
}


Next, I’m going to deviate from the original article and allow early and late binding by adding the InterfaceIsDual attribute:

[InterfaceType(ComInterfaceType.InterfaceIsDual)]
public interface ILauncher
{
    string Hello();
}

Step 5: Making them Unique

This is where I’m really going to deviate from the original article.  You’ll need to generate GUID’s for both the interface and the class. Now go to the “Tools” menu and select “Create GUID”:

Choose #5, and click on the “Copy” button.  Then paste it into your code:

[Guid(“6216B529-3E4A-4FE8-8F7A-BE99C33DB1F1“),
 InterfaceType(ComInterfaceType.InterfaceIsDual)]
public interface ILauncher
{
    string Hello();
}

[Guid(41027763-2E19-415A-8525-F48F604EE810),
 ClassInterface(ClassInterfaceType.None)]
public class Launcher : ILauncher
{
    public string Hello()
    {
        return Hello world“;
    }
}


You might have to remove the square brackets to make the syntax correct (as shown above).


Step 6: Going Underground with Cryptography

This is where you’ll have to drag out the “sn” utility and give your assembly a strong name.  You’ll have to search your hard drive for the sn utility and there are probably more than one version.  I found mine at this path:

“C:Program Files (x86)Microsoft SDKsWindowsv8.1AbinNETFX 4.5.1 Toolssn”

I chose the latest version that was installed on my PC.  You’ll need to open a console window (go to your start menu and type “command” in the search box.  Then navigate to the project directory of your application.  Then execute the sn utility with the “-k key.snk” parameter:

“C:Program Files (x86)Microsoft SDKsWindowsv8.1AbinNETFX 4.5.1 Toolssn” -k key.snk

You’ll need to keep the path name quoted since it has spaces in it.  Once you execute this command there will be a file generated in your project directory named “key.snk”.  Now you need to add this file to your project as a link.  So right-click on your project and select “Add -> Existing Item”.  Don’t hit the “add” button, on the add button there is a down-arrow that allows you to select a different option:

Select “Add As Link”.  To use this file, we need to go to the project properties (right-click on your project and select “Properties”).  Then select the “Signing” tab.  Now click on the “Sign the assembly” check box and choose the “key.snk” file from the drop-down list:


Save your changes.


Step 7: Wrapping it All Up

Before building your solution we need to modify some settings.  In Deutschzuid’s article that I cited at the beginning of this blog post, you are directed to change your target build version at this point.  I’m going to leave it at “any” (the default).    Go back to your project properties and select the “Application” tab.  Click on the “Assembly Information” button.  Check the “Make Assembly COM-Visible” check box.

Now switch to the “Build” tab and check the “Register for COM interop” check box.


Step 8: Compiling it and Taking it for a Walk

Now you can build the solution.

First, let’s try this in ASP.  Make sure you have IIS installed and running on your PC.  Create a sub-directory in your C:inetpub directory named “aspcom”.  You can startup the IIS control panel (go to your start menu and type “iis” in the search box) and create a new application under your default website.  Name your application “aspcom” and point the directory to the new directory you just created.  You’ll need to click on “Edit permissions” and the directory properties window will pop-up.  Click on the “Security” tab.  Click “Edit” then “Add”, then type in “IUSR” and click “Check Names”.  Then click “OK”, then check the “allow full control” check box.  Then “OK”, 

Then repeat: “Edit”, “Add”, type “IIS_IUSRS” and click “Check Names”.  You might need to change your domain to the local PC domain for this to check right.  Then “OK”, then “allow full access”, then “OK” and last “OK” to close the properties window.

Now you’ll need to add those same two rights to the directory that contains your COM object project.  Just navigate to your project directory and right-click on it.  Then repeat the steps above to give full rights to “IUSR” and IIS_IUSRS”.

Restart IIS.

Now create a text file inside the C:inetpubaspcom directory named “home.asp” and type (or copy) this in:

<%
Dim MyComObject
Dim MyText

Set MyComObject = Server.CreateObject(“Launcher.Launcher”)

MyText = MyComObject.Hello()

%>
<html>
<head></head>
<body>
    <%=MyText %>
</body>
</html>

In the IIS control panel is a link called “browse” with a url on it.  You can click this link to get to the ASP directory, but you’ll have to add home.asp to the end of the path.  Then you should see “hello world” printed on your browser.

Next, create a text file on your desktop and name it “test.html”.  Now type or copy this into it:

<HTML>
<HEAD>
<SCRIPT language=”javascript”>
function Test() {
var objTest = new ActiveXObject(“Launcher.Launcher”);
alert(objTest.Hello());
}
</SCRIPT>
</HEAD>
<BODY>
<INPUT Type=”button” onClick=”Test()” Value=”Click here to test!”>
</BODY>
</HTML>


Now save it and double-click on the html file.  You’ll have to allow blocked content then click the button.  Then answer yes to the active-x control warning and you’ll see a text box displaying “hello world” in it.


Step 9: Deploying the dll on Another Machine

If you want to deploy the dll on another machine, you’ll have to add your dll to the registry by using the regasm utility.  First, copy your dll to the target machine (just the dll).  Then you need to find the regasm program on your pc, just like you did with the sn utility above.  Choose the latest version.  Navigate to your dll’s location and use this command:

regasm ComClassExample.dll /codebase /tlb /nologo

For testing purposes, you don’t need to use regasm.


Troubleshooting Tricks

OK, now there is an issue if you are attempting to change your COM program after you have executed it from an ASP program.  That issue is that IIS has the DLL locked and you can’t re-compile.  So you’ll need to reset your IIS before you re-build your application.  Then you can run your ASP program again.

Next, you are going to want to know what is going on while you are troubleshooting this project.  Especially if it doesn’t work the first time.  So in the IIS console, click on your application (aspcom), double-click on the ASP icon:


Expand your “Debugging Properties” section and change “Enable Client-side Debugging” to true and also change “Enable Server-side Debugging” to true.  Click on “apply”.  

Now, if something blows up, you can attach a debugger and see where it breaks in Visual Studio.  You can also get a good error message, like “permission denied”.

Don’t forget about the IIS log files.  They are located in the C:inetpublogs directory.  These are usually pretty cryptic, but sometimes they can shine some light on what’s wrong.

You can also open your home.asp page in Visual Studio and put a break-point on it.  Then choose “Debug -> Attach to Process…”, then select w3wp.exe and click the “attach” button.  Refresh the web page and the breakpoint should be hit.  You cannot get tool tip help in asp, but you can put a variable in your watch list and see what is contained in the variable.

One other annoying thing you might run into.  If you click the “Restart” button in the IIS control panel and your IIS does’t restart (it just sits there scanning, like it’s waiting for something) that means that there is a w3wp.exe process holding it up.  Just CTRL-ALT-Delete and start task manager.  Then find all w3wp.exe processes and “end process”.  You’ll notice that your IIS control panel will suddenly respond.


Download the Source

You can download the source code from my GitHub account by clicking here.

 

Web Sessions

Summary

I’m going to create a series about how Microsoft handles sessions for VB.Net and C# web applications.  The purpose of these posts will be to provide a clearing-house of all the information needed to get a common session system going between multiple languages.

The Problem

Web sites typically use session data to keep track of who is logged in and what state they are in.  I’m not going to go into details on why sessions are used or how to use them to build a website.  Instead, I’m going to assume you are already familiar with this technique and you’re saddled with a large amount of legacy code that cannot be converted in one shot.  Let’s say you have a website in PHP and you’re attempting to migrate into a C# environment.  How do you go from one web page in PHP running on a Unix server into a C# program running on an IIS server?

There are many solutions, such as cookies, tokens passed in the URL, a GUID stored in a hidden field, etc.  The smoothest solution would be to somehow share the session data between different languages so that one page at a time can be converted and the URL from the old page can be redirected to the new page with a smooth and secure transition.  The first thing to recognize is that we’re going to have to store the session data in a database that is shared by all web sites that will be connected into one web application.  Microsoft provides this capability through their own session management.  

Using MS SQL Server to Store Session Data

For Dot Net applications, you can setup a SQL server to store the session data.  The following link is probably your best article for getting SQL setup with the ASPState database and redirecting your application to point to the new database:

Configuring ASP session state on SQL server 

Once you have set this up, you’ll need to make sure your user rights are setup in the ASPState and the tempdb database.  The session data is actually stored in the tempdb database in two tables: ASPStateTempApplications and ASPStateTempSessions.  The ASPStateTempApplications table contains the name of the application and the unique app id used by the session cookie (I’m going to assume you’re using the cookie mode in iis, since it is the default).  The ASPStateTempSessions table contains one record per session created.  All of the session data is encoded and stored in a binary field in this table called SessionItemShort (or if it’s larger than 7k, then it’ll be in SessionItemLong which is an image data type).


The Session Cookie

When your application creates a session, a cookie is created with the application id and a unique session id.  The default cookie name is “ASP.NET_SessionId”.  If you look at the session id the tempdb.ASPStateTempSessions table, you’ll discover that it is a large alphanumeric string.  That string represents two parts: The session GUID and the application ID.  The application ID is in hex in the ASPStateTempSessions table and it is in decimal in the ASPStateTempApplication.appid field.  If you are going to read the session data from the tempdb database ASPStateTempSessions table, then you’ll need to add the application ID to the end the cookie value.  Take your application name and read the application id from the ASPStateTempApplications table.  Convert this to hex, then append to the cookie value.  This will be the primary key of the ASPStateTempSessions table for your session data.

If your googling skills are savvy enough, you will have discovered most of this information from this article: Session State Providers.  

The next thing to note about this session setup is that the cookie is a non-persistent cookie.  There is no expire date and this type of cookie will remain until you close your browser.

If you dig into your SQL server and you look at your SQL Server Agent jobs, you’ll see a new one called ASPState_Job_DeleteExpiredSessions.  This job will execute the stored procedure: DeleteExpiredSessions once per minute.  The sole purpose of this stored procedure is to delete all cookies where the expires field is beyond the current date/time.  This will cause the session to expire.  If you look at this date/time in the
ASPStateTempSessions table, then refresh your browser, you’ll notice that the time updates.  The time will always be 20 minutes into the future (if your session is set to expire in 20 minutes, which is the default).  If your web page goes idle for more than 20 minutes, then you’re toast.


Sharing Session Data Between VB.Net and C#

The easy method of sharing between two languages is to set the application name to the same name in the global.asax file for both programs:

Session State shares session across subdomain, VB.NET website C# MVC 4 Application


Session Data

The session data that is stored in the tempdb.ASPStateTempSessions table is an encoded version of all the session variables and data used by your program.  There is this code in C#, which can decode this data into a list of variables:

christian-blades-cb/ASPSessionDecoder 

This code does not handle objects, but it does demonstrate the complexity of how this is encoded.  Creating an encoder and decoder for this data for a multitude of languages would be very handy.  Especially if you wanted to use many languages in one large monolithic application.  I believe the reason that Microsoft encoded this data into one large field instead of using a sub-table of fields and data, is that they can store the session data for each session in one record.  This prevents a lot of table locking issues with deleting records and it also reduces the amount of time it takes to read and write to the database (assuming they had a database in mind when they designed this system.  If you look closely at the DeleteExpiredSessions stored procedure inside the ASPState database, you’ll see that a query of all the expired sessions is put into a temp table.  Then the temp table is looped through and each session record is re-checked as it is deleted, just in case it was updated or deleted while this operation was in progress.


Wrap up

For this blog post, that’s all I’m going to go into.  Armed with this information anybody can make a decision on how they want to pursue sessions with legacy code and new code.  For instance, you could design your own session system to mimic what Microsoft does and use child records to store your variables.  I am unsure how this will perform or what issues you’ll run into with this method.  You could write encoders and decoders for the session data and use the data that Microsoft stores (avoiding the need for converters and decoders from VB.Net and C# (i.e. you could write a codec for PHP, Classic ASP, Java).  By storing your session in the database, you can use different IIS applications for each language (or divide your systems into multiple applications).  You can also prevent your session from clearing when an IIS server is re-cycled, or if you have a server farm, you don’t need to worry about which server the web request returns to.  

 

Visual Studio 2015 – Smart Unit Tests

Summary

I’ve been reviewing the new Visual Studio 2015.  I currently use both 2013 Professional (at work) and 2012 professional (at home).  So I’m going to blog about a feature I stumbled across while I was examining the unit testing enhancements of VS 2015.

About Visual Studio 2015

The version of VS 2015 that I’m looking at is the Preview version.  Unfortunately, there is only one version of the preview and that is the Ultimate version.  So I’m not sure which features will make it into the Professional version, which will most likely be the version that I’ll purchase in the future.  The Professional Version of VS 2013 without MSDN is currently (as of this writing) selling for $499.  The Ultimate version sells for $13,299.  Yikes!  Premium sells for $6,119.  Also Yikes!  I can’t imagine a company trying to staff a dozen or more developers with a per-seat cost that high.  The cost of the PC becomes an accounting round-off.

OK, I’m going to stop complaining about the price. The feature that is only available in the Ultimate and Premium that I would like to see in the Professional version is the code coverage unit testing feature.  This seems like a basic function of code testing and there are a lot of third party add-on packages that are a cheaper than $6k.  Here’s the feature comparison chart for VS 2013: Feature Comparison

Code Coverage

This is a slight diversion from my original blog topic, but I’m going to show how the code coverage works and why I like it so much.  First, I created an object called MyMathClass, and I created two methods: Divide and Multiply, which perform the functions that you would expect.  Then I created unit tests for the Divide method but not the multiply method.  Under the “Test” menu is a menu item “Analyze Code Coverage” and “All Tests”, which runs the unit tests and shows a “Code Coverage Results” window at the bottom of the screen:


Next, I navigated to the object by double-clicking on the Multiple in the code coverage results screen and the coverage is shown in colored highlights:

As you can see, the code that is not covered by any unit tests shows as red.  All code covered by unit tests is a pale blue/green color.  This is a very trivial example, but I loaded a large program with lots of unit tests into VS 2015 and ran this feature.  I could see instantly which methods and code inside methods was not covered.
Smart Unit Tests
So I was reading through the VS 2015 features website: VS 2015 Features and I stumbled across a feature called “Smart Unit Tests”.  This feature will generate unit tests to cover all cases for each method in an object.  Basically, you right-click inside the object (but outside your methods) and select “Smart Unit Tests”.  This will create unit tests grouped by the method name.  Be aware that there is a drop-down in the smart unit tests window to select which group of tests to view:

If you select a method from this drop-down, then select all the tests in the window and hit the save button (right-click and save, or click on the floppy-disk icon in the smart unit tests window), a unit test project with all the unit test code will be stored:
The code for each unit test is stored in the individual .g.cs sub-files, which are auto-generated.  You’ll need to select each method in the smart unit tests windows drop-down, select all tests and hit the save button for each method in order to add all methods to this test project (yeah, it was painful).  As you can see from my screenshot above, I have added both the unit tests for the divide and the multiply methods.
I was actually surprised at the unit tests that were created for my methods.  For the divide operation, which I purposely made an integer divide, it created a unit test to include an int.MinValue as the numerator and a -1 for the denominator, which caused the method to overflow.  Even though the unit tests are computer generated (and include a lot of messy auto-generated code), I can get an idea of what should be tested.  My big question now, is what kind of unit tests would be generated for complex real-world methods?
I loaded the battleship game AI demo from one of my previous blog posts, changed the object and methods to public (just to allow unit testing) and ran the smart unit test.  I noticed that there are a lot of complex problems that the “smart” unit tester cannot figure out.  First, there was a problem with the Sunk() method tests.  This method tests the playing board to determine if a ship has been sunk.  The issue with the unit tests is that the board was not initialized.  Technically, this is an actual coding issue, since I built this program as a throw-away  console application.  So the map data should have been contained in an object that would be instantiated with some data.  The unit tests would still need to have knowledge of what the object represents and unless ships are mapped to positions in the map board, then a true or false cannot be correctly tested.  In addition to that, the unit tests ran with input values 0, 1, 2 and 6.  There is no length of ship 0 and it missed ship lengths for 4 and 5.  This occurred because the unit test generator had no knowledge of what the Sunk() method is supposed to do.
Another issue I ran into was called “path bounds exceeded” and a unit test was not created for the input used.  The case ran for too many iterations and the smart unit test program thought there was a possible endless loop.  There is a message that indicates that I can select “Fix” from the menu (right-click on the test) and it will change the setting to use 20,000 iterations.  That did not solve the problem and technically, this method does not need a unit test since it doesn’t return a value and it performs no function except to test the maximum searches needed to sink random ship locations.
My conclusion on this feature (and this is just my initial quick-pass) is that it would be handy as an additional check on the unit tests that the developer creates to see if there are possible fence-post values that were missed for inputs, or input combinations that could cause a failed unit test.  Another possible use is to generate a set of unit tests that can be copied into the actual unit test project and cleaned up (i.e. more human readable).  Then the unit tests can be analyzed to make sure they make sense.  Otherwise, it appears to me that the unit tests that are generated are making assumptions about the methods under test that are not correct.  Which is no better than having no unit tests at all.

For more information on this feature you can click here.
 


 

Game Algorithms (Part 3)

Introduction

In my previous two blog posts on game algorithms, I showed how to search for a ship in a battleship game.  Now, I’m going to show how to sink a ship as soon as your search algorithm gets a hit.  In this article, I’m only going to discuss possible algorithms, there will be no accompanying code.

Ship Length and Direction Unknown

One of the challenges to battleship is that you don’t know what size the ship is that you hit, once you have made the first hit.  You also don’t know which direction it is facing.  So the first step is to figure out the direction (and hope it’s a PT boat, so you can sink it at the same time you discover the direction).

So the first thing to do is find the direction.  We all learned this technique after playing battleship the first few times in our lives.  Basically, we fire on each square above, below, to the left and right of the location that we got a hit.  Ignoring any squares that are already hit.  I usually follow a circular pattern until I get another hit, but you can do a cross pattern too.  In order to reduce the amount of shots you need to take, you can do some analysis of the board and determine if you need to shoot each square, or possibly, any remaining ship is too long to fit in the direction that you might test.  For example, here is a 5×5 map with one destroyer:

We managed to get a hit at square 1,1.  If we next fire on square 0,1, we might get a hit, but we could also get a miss.  Same with square 1,0.  However, if you shoot at square 1,2 or square 2,1, you’ll notice that we will get a hit, no matter where the destroyer is positioned (remember a destroyer occupies 3 squares).  So we only need to fire on 1,2 and if that was a miss, then 2,1 to find the direction of the destroyer.  

This indicates that we could create an algorithm that checks each possible position of a destroyer that contains square 1,1 and determine what the probability is that it would be located in any of the possible surrounding squares.  Then we can choose the most probable squares first.

Now, let’s assume we shot square 1,2 and got another hit.  We’re also assuming that we only have one destroyer on the board.  So the board looks like this:

Now we have a 50% chance that we can sink the ship by firing on square 1,0 and a 50% chance that we can sink the ship by firing on square 1,3.  So we just take a chance and shoot one side, then, if that didn’t sink the ship, fire on the other side.  Ship sunk.


Multiple Ships on Map

OK, now we have a map containing two or more ships, let’s say a destroyer and a PT boat on the same 5×5 map.  Now, what would happen if the map looked like the above map and you fired on square 1,0 and 1,3 and both missed?

You guessed it.  There’s a PT boat facing vertical on the right side of a vertically facing destroyer.  The PT boat is a no-brainer, since there is only room for it to fit in squares 0,2 and 1,2.  The destroyer could still occupy 0,1 or not.

So we would need an algorithm to determine that if we shot on both sides of a ship and it didn’t sink, then we hit two ships.  The algorithm could get a bit tricky once we have figured out that we hit more than one ship, because the second ship could be facing the other way.  However, any ship facing horizontally, will eventually get sunk.  According to the rules of battleship you must announce which ship was sunk.  So now we’ll also need to verify that the ship sunk matches the number of squares shot at.  Here’s an example:


In this example, once square 1,3 is shot the announcement that the PT boat was sunk should indicate that square 1,1 doesn’t belong to the PT boat (assuming we fired square 1,3 last).  At this point, we would know that the destroyer is vertical with one of the squares on location 1,1.

Here’s another scenario:

In this scenario we got our first hit on square 1,1, then we fired 1,2 followed by 1,3, then sunk a destroyer at 1,4.  So now, the cell at 1,1 is the PT boat.  However, it could still occupy any of the remaining 3 squares (0,1 or 1,0 or 2,1).

Other possibilities include scenarios where several ships are lined up in parallel, causing a row of hits that don’t sink any ship, but are actually hits on many ships.

Conclusion

I believe I have covered all possible scenarios that will occur in battleship.  However, it would be wise to write a simulator that randomly positioned all the ships on a 10×10 map and then used the seek until hit algorithm followed by the algorithms described above to sink your ships.  Executing this simulator in a loop thousands of times followed by a test that scans the map and ensures that all ships have been sunk would be a good way to verify your algorithms are correct.

Also, if you are writing the game itself, then unit tests are a must.  You should set up each scenario and run a unit test based on the scenario to make sure each algorithm executes correctly.

One other aspect to keep in mind (assuming you’re going to write a battleship game and use these algorithms) is that this will be a very hard game to beat.  So you might want to have an adjustable game difficulty and dumb down a few of the algorithms when in easy mode.  You’ll also want to randomize your shots when seeking ships.  If you don’t, then the algorithm will always shoot in the same pattern and the person playing the game could catch on to the best places to hide their ships.

To make the game more difficult, you could get even more sophisticated and record the patterns that the human player uses when they hide their ships (assuming it’s only one person playing the game).  After a few dozen games, ship position rankings can be recorded, like battleship positioned near edge of map 80% of the time, or PT boat positioned near the middle of the map 60% of the time.  Then the computer can take random shots near the edge or in the middle first to increase the likelihood of hitting a ship early.

One other detail to note: I didn’t mention if each side takes one shot per turn or multiple shots per turn.  The algorithms described above assumed one shot per turn.  If you’re taking multiple shots per turn, then the above algorithms still apply, except it’s best to try and sink the discovered ship as quickly as possible.  If you can determine the direction that the ship is probably facing, then you can shoot an entire line to try and hit any possible positions that the ship is in.  It’s better to waste a shot or two and sink a ship as fast as possible, which would reduce the number of shots the enemy can take.
 




 

Game Algorithms (Part 2)

Introduction

If you read my last game algorithm blog post you’re probably screaming at me “Where’s the rest of the game AI ?!!”  So in this post I’m going to go more in depth on searching for a ship to sink.  In a future post, I’ll show how to figure out where to fire once a ship has been hit once in order to sink it with the fewest moves possible.

What About the Destroyer?

First, I’m going to demonstrate what happens if the size of the ship has changed.  If you downloaded the sample code from the last game algorithm blog post, you’ll see that there is a variable name that you can pass into the main method called lengthOfShip.  If you change that to a 3, you’ll see a resulting map firing solution like this:

Which is not the solution we’re looking for.  We are expecting something like this:

Which is one less shot and equal to 25 / 3 (rounding up to capture the last location).  The reason for the mapping error is due to the fact that we have more than one possible arrangement for choosing the next shot.  In this case the edge shots are all equally ranked and the algorithm went off course when it chose the first edge case of 0,2.  Here’s what the list looked like at this point:

0,2 [3]
0,3 [3]
1,4 [3]
2,0 [3]
2,4 [3]
3,0 [3]
4,1 [3]
4,2 [3]
0,0 [2]
0,1 [2]
0,4 [2]
1,0 [2]
1,3 [2]
3,1 [2]
3,4 [2]
4,0 [2]
4,3 [2]
4,4 [2]
1,2 [1]
2,1 [1]
2,3 [1]
3,2 [1]


If the algorithm had chosen 0,1 or 0,3 first, then it would have worked out.  In order to ensure that we get the best outcome, we could implement a look-ahead algorithm, but I’m going to move on for now, because there are other issues to consider and this whole problem could work out on its own.

So I ran this with a battleship (4 spaces) and this is the resulting pattern:

It appears that ships with even number lengths work and odd does not.  I can try a carrier, but I’ll have to increase the map size, otherwise it’s just a trivial diagram.

My purpose in pointing out the fact that even numbered ships happen to work out is that we are going to eventually be searching for the PT boat (unless we get lucky when we search for another ship and hit it early on).  Let’s say we start with the carrier and we get a hit, then we switch to the battleship and we get a hit (I’m assuming we don’t hit a different ship).  Once the carrier and battleship are sunk we can search every 3 squares to find the destroyer and sub.  The problem with this algorithm is that we will eventually start hitting odd numbered squares.  If we start by searching by every four squares, we’re guaranteed to hit a carrier or a battleship.  For a 10×10 box, we will hit both of these within 26 shots.  Then we can switch to the 2 square search mode and we are guaranteed to hit the remaining ships within an additional 34 shots (for a total of 50 shots).

But, I’m not happy to just guess at which search algorithm would be best, so I’m going to write a dumb and dirty program to randomly position all the ships on a 10×10 board and use a step-down pattern of 5,4,3 and 2 to see how many shots it would take to sink all ships.  Then I’m going to try and use only even numbered patterns 4 and 2) to do the same.  Then I’ll compare.  To make sure I get the maximum shots, I’ll have to loop and put in random ship positions thousands of times.  I could create a program that finds every combination of ship positions, but I think random positions will save time and get close.

So I ran the loop 20,000 times for each algorithm to see what I could come up with.  Then I re-ran each algorithm several times to see if the max number would change and I came up with this:

Step down algorithm (5,4,3,2,): 59 shots, max
Even algorithm (4,2): 40 shots, max

The difference between the two algorithms is much larger than I expected, but it seems conclusive to me that an algorithm that searches every 4 squares until the largest un-sunk ship is a length of three, then every 2 squares is the most efficient algorithm.


Download the Code

If you want to experiment with the code yourself, or you want to use my methods as part of your own battleship game, you can download the code from my GitHub account by clicking here.

 

Accessing Private Methods From Unit Tests

Summary

In this post, I’m going to show how to write a unit test that can access a private method of an object under test.  There is a lot of debate about whether private methods should be accessed from unit tests or that they should be either not tested, or made public.  I’m going to ignore the “debate” and just show the mechanics.  I’ll leave it up to you to decide if this is evil or not.

Non-Static Private Methods

I setup a demo application to show how to do both static and non-static.  I’m going to start with the non-static implementation.  Here’s the object I’m going to use.  I’ve dumbed it down to something really easy:

public class Mathinator
{
    private double AddList(double[] inputs)
    {
        double total = 0;

        foreach (var item in inputs)
        {
            total += item;
        }

        return total;
    }
}

You can use your imagination on how the “AddList” method is used as an internal object method and there is some reason you want to protect this method from being executed from another object.  Anyway, here’s how to write a unit test to execute this method and test the return value:

[TestMethod]
public void TestPrivateMethod()
{
    double [] input = new double [3];
    input[0] = 3;
    input[1] = 12.4;
    input[2] = 3.45;

    Mathinator mathinator = new Mathinator();
    var mathinatorObject = new PrivateObject(mathinator);
    double result = (double)mathinatorObject.Invoke(“AddList“,input);

    Assert.AreEqual(18.85, result);
}

The object “mathinator” can be used in your unit test to call any public methods as well, and all internal object results are updated when the Invoke command is called.  In this instance, I’m only Invoking the private method, recording the result and executing an assert command.


Static Private Methods

Now it’s time to show an example of how to execute a static private method.  Here’s the example object I used for this unit test:

public static class  StaticMathinator
{
    private static double AddNumbers(double[] inputs)
    {
        double total = 0;

        foreach (var item in inputs)
        {
            total += item;
        }

        return total;
    }
}

Again, this is a very simple example.  In order to invoke the static private method you’ll need to use the PrivateType instead of PrivateObject:

[TestMethod]
public void TestStaticPrivateMethod()
{
    double[] input = new double[3];
    input[0] = 3;
    input[1] = 12.4;
    input[2] = 3.45;

    var privateHelperType = new PrivateType(typeof(StaticMathinator));
    double result = (double)privateHelperType.InvokeStatic(“AddNumbers“, input);

    Assert.AreEqual(18.85, result);
}

Note: 

You can use the Invoke and InvokeStatic methods without parameters for private methods that don’t require parameters, and you can ignore the return parameter if your private method does not return a value.


Download the Sample Code

You can download the sample code at my github account by clicking here and experiment with it.


 

Game Algorithms

Intro

I have a few blog post subjects in progress, but they’re going to take some time to develop the sample applications that I’ll need in order to explain the techniques that I’ll be blogging about.  In the mean time, and due to a little A.D.D. on my part, I’m going to do a blog subject that is more of an analysis process.  I’ll show some of the complex ideas that go into designing an algorithm and ensuring it’s success.

Battleship

So I was playing battleship on my iPad.  It’s a great time-killer and my goal is to beat the enemy with as few moves as possible.  In this rendition of Battleship, you start with 5 ships and you get one shot per ship per turn.  So you start the game with 5 shots per turn, until the enemy sinks one of your ships, then you only get four shots per turn.  The strategy of this version is a bit different from the one-shot-per turn variety.  First of all, if you expect to win, you need to cut down the number of shots that your enemy gets to take per turn, so it takes him longer to find your ships.  So that means that as soon as you get a hit, you need to sink that ship immediately, even if you waste a few shots.

Before I get to the strategy of what to do when you get a hit, I’m going to discuss how to minimize your shots to get that first hit.  In order to hit all ships with a minimum number of shots, you’ll need to account for the PT boat.  This is the smallest ship in the fleet and it takes up 1 square by 2 squares.  That means that you can technically shoot every other square in a checkerboard pattern and hit a PT boat with a maximum of 50 shots (10 x 10 / 2).  Here’s what the pattern might look like:

If the game board contained only one PT boat and you followed this pattern, then eventually, you’ll hit that boat within 50 shots.  This is much more efficient than just randomly shooting on the board because any shots next to each other is a wasted shot.

There is something else here worth considering.  First of all, what are the chances that a PT boat is in the upper left corner?  Since there are only two possible positions that a PT boat could occupy the corner square, there are only two possibilities of hitting a PT boat in that corner.  Contrast this with a square that is on the edge of the map and then there are three possibilities that PT boat is in that position.  If the boat is away from the edge, then there is the possibility that a PT boat could be positioned from four directions.  So it would seem that an algorithm that shoots the edges of the map and the corners last will eliminate more positions that the PT boat could be in.  Of course, this would make for a weak algorithm because sooner or later the opponent is going to catch on to this strategy and position their PT boat in one of the corners.  But let’s ignore that for now and go on the assumption that we want to fire the next shot and maximize the possibility of hitting the PT boat.

The first algorithm we’re going to need is to collect a list of each possible location of a PT boat on the board.  I’m going to cut the map down to a 5 by 5 map to make this easier to visualize, but here’s the list of possible PT boat locations:

0,0 (Vertical)
0,0 (Horizontal)
1,0 (Vertical)
1,0 (Horizontal)
2,0 (Vertical)
2,0 (Horizontal)
3,0 (Vertical)
4,0 (Vertical)
0,1 (Vertical)
0,1 (Horizontal)
1,1 (Vertical)
1,1 (Horizontal)
2,1 (Vertical)
2,1 (Horizontal)
3,1 (Vertical)
4,1 (Vertical)
0,2 (Vertical)
0,2 (Horizontal)
1,2 (Vertical)
1,2 (Horizontal)
2,2 (Vertical)
2,2 (Horizontal)
3,2 (Vertical)
4,2 (Vertical)
0,3 (Horizontal)
1,3 (Horizontal)
2,3 (Horizontal)
0,4 (Horizontal)
1,4 (Horizontal)
2,4 (Horizontal)

As you can see, I’m starting at zero, and the max coordinate is 4.  Now, let’s get all the cells that each of these ships could occupy and make a sorted list of these cells and how many times the cell can be occupied by a PT boat.  This is just a brute-force program designed to prove a point that we already know.  So here goes:

0,0 [2]
0,1 [3]
0,2 [3]
0,3 [3]
0,4 [2]
1,0 [3]
1,1 [4]
1,2 [4]
1,3 [4]
1,4 [3]
2,0 [3]
2,1 [4]
2,2 [4]
2,3 [4]
2,4 [3]
3,0 [3]
3,1 [4]
3,2 [4]
3,3 [4]
3,4 [3]
4,0 [2]
4,1 [3]
4,2 [3]
4,3 [3]
4,4 [2]


OK, so now we can see that squares like 0,0 (corner square) only occur twice and squares that are not near the edges (like 1,1 and 3,1) occur four times.  What this means is that if the user randomly positions their PT boat at any of the possible coordinates and orientations, then there is a greater chance of hitting that boat at square 1,1 than at square 0,0.

Here’s what a corner square looks like (showing 2 possible locations of a PT boat):


By creating an algorithm that spits out this list and then ordering the list by largest occurrences to smallest, we can choose which square to shoot.  Now we need to enhance this algorithm to ignore any squares that have already been shot.

So let’s say that position 2,2 was shot last turn and it was a miss.  Now what possible locations are left for our PT boat and what is the occurrences?

0,0 [2]
0,1 [3]
0,2 [3]
0,3 [3]
0,4 [2]
1,0 [3]
1,1 [4]
1,2 [3]
1,3 [4]
1,4 [3]
2,0 [3]
2,1 [3]
2,3 [3]
2,4 [3]
3,0 [3]
3,1 [4]
3,2 [3]
3,3 [4]
3,4 [3]
4,0 [2]
4,1 [3]
4,2 [3]
4,3 [3]
4,4 [2]

Notice how there are only 24 squares above.  That’s because we’ve already shot at square 2,2 and that doesn’t appear in the list anymore due to the fact that a PT boat can’t be located at that square.  Also notice how square 1,2 (adjacent to 2,2) has been reduce to a 3 from a 4.

What would happen if our algorithm was changed so that we would just grab the first largest hit count square and fired a shot, then recomputed and continued until all hit counts reached zero?  Would the computer take 25/2 shots in total?  What would be the shot pattern that results?

Here are the results:

1,1
1,3
2,2
3,1
3,3
0,2
2,0
2,4
4,2
0,0
0,4
4,0
4,4


That’s 13 shots, which is correct and here’s what it would look like on the map:


The next algorithm to consider is an algorithm to sink a ship after it has been discovered, but I’m not going to go over that algorithm in this blog post.


Get the Code

You can download the code at my GitHub account here.  I have commented logging as I went along but you can uncomment the log statements and view the raw data in the log file which will be located in the C:logs directory.