Archive for the ‘C#’ Category.

## Cross a bridge at night

OK, here is a scenario. Four people on a journey together need to cross a bridge at night as quickly as possible. Among the four of them, they have one flashlight. They cannot continue their journey until all four reach the other side together. Since the bridge is narrow and slippery, and it is pitch black out being night and all, they decide to have two people cross with the flashlight, then one person returns with the flashlight back to the original side, and they continue until everyone is on the other side.

Oh, and also, the people can all walk at different paces, so when two people cross together, it takes them the amount of time that it takes the slower person to cover the distance.

For example, let’s say that the four people that need to cross can cover the distance of the bridge in 1 minute, 2 minutes, 5 minutes, and 10 minutes. What would be the shortest possible time?

The naive solution would be to have the 1 minute person be the primary flashlight runner and send them with the 2 minute person, return, then the 5 minute person, return, and finally cross with the 10 minute person, for a grand total of 19 minutes.

Now of course this is not the optimal solution, but more on that in a minute.

So how would we design an algorithm to solve this problem? Conventional wisdom says to create some kind of tree where you iterate through all of the possible combinations of initial crossings, then off those branches, combinations of reverse crossings, etc. Then once the tree is built, you can walk to all the branch tips and calculate the times, and then just display the shortest time.

But why do something logical? With all this computing power, I say that we implement my favorite algorithm for producing solutions to problems… The Monte Carlo method.

Here is the code for a C# .NET console app I threw together to solve this issue:

```using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;   namespace BridgeAtNight { public class BridgeState { public List<int> peopleOnLeft; public List<int> peopleOnRight; public int totalTime; public string peopleMovement;   public BridgeState(int[] people) { totalTime = 0; peopleMovement = ""; peopleOnLeft = new List<int>(people); peopleOnRight = new List<int>(); }   public void MoveLeftToRight(int leftToRight1, int leftToRight2) { peopleMovement = peopleMovement + string.Format("{0}>> {1}>> ", leftToRight1, leftToRight2); totalTime += Math.Max(leftToRight1, leftToRight2);   peopleOnRight.Add(leftToRight1); peopleOnRight.Add(leftToRight2); peopleOnRight.Sort();   peopleOnLeft.Remove(leftToRight1); peopleOnLeft.Remove(leftToRight2); }   public void MoveRightToLeft(int rightToLeft) { peopleMovement = peopleMovement + string.Format("{0}<< ", rightToLeft); totalTime += rightToLeft;   peopleOnLeft.Add(rightToLeft); peopleOnLeft.Sort();   peopleOnRight.Remove(rightToLeft); }   public void SolveWithNaivete() { peopleOnLeft.Sort(); while (peopleOnLeft.Count > 1) { // move 2 people from the left to the right int leftToRight1 = peopleOnLeft[0]; int leftToRight2 = peopleOnLeft[1]; MoveLeftToRight(leftToRight1, leftToRight2);   // move 1 person from right to left if there are any remaining people on the left if (peopleOnLeft.Count > 0) { int rightToLeft = peopleOnRight[0]; MoveRightToLeft(rightToLeft); } }   Console.WriteLine("Solution with naivete:"); Console.WriteLine(string.Format("Time: {0} minutes", totalTime)); Console.WriteLine(string.Format("Sequence: {0}", peopleMovement)); }   public void SolveRandomly() { Random rnd = new Random(); while (peopleOnLeft.Count > 1) { // move 2 people from the left to the right var leftToRightRandom = peopleOnLeft.OrderBy(x => rnd.Next()).Take(2).ToList(); int leftToRight1 = leftToRightRandom[0]; int leftToRight2 = leftToRightRandom[1]; MoveLeftToRight(leftToRight1, leftToRight2);   // move 1 person from right to left if there are any remaining people on the left if (peopleOnLeft.Count > 0) { var rightToLeftRandom = peopleOnRight.OrderBy(x => rnd.Next()).Take(1).ToList(); int rightToLeft = rightToLeftRandom[0]; MoveRightToLeft(rightToLeft); } } } }   class Program { static void Main(string[] args) { BridgeState naiveBridgeState = new BridgeState(new int[] { 1, 2, 5, 10 }); naiveBridgeState.SolveWithNaivete();   List<string> bestTimeResults = new List<string>(); int bestTime = 999999; for (int idx = 1; idx < 1000000; idx++) { BridgeState randomBridgeState = new BridgeState(new int[] { 1, 2, 5, 10 }); randomBridgeState.SolveRandomly(); if (randomBridgeState.totalTime < bestTime) { Console.WriteLine(string.Format("Better random solution found in pass {0}:", idx)); Console.WriteLine(string.Format("Time: {0} minutes", randomBridgeState.totalTime)); Console.WriteLine(string.Format("Sequence: {0}", randomBridgeState.peopleMovement)); bestTime = randomBridgeState.totalTime; bestTimeResults = new List<string>(); bestTimeResults.Add(randomBridgeState.peopleMovement); } else if (randomBridgeState.totalTime == bestTime) { if (!bestTimeResults.Contains(randomBridgeState.peopleMovement)) { Console.WriteLine(string.Format("Sequence: {0}", randomBridgeState.peopleMovement)); bestTimeResults.Add(randomBridgeState.peopleMovement); } } }   Console.WriteLine("Press any key to exit the application"); Console.ReadKey(); } } }```

There are undoubtedly some optimizations I can make to this code above, such as ordering the times in the MoveLeftToRight function. However, I was kind of surprised to see this run, as sometimes the optimal solution of 17 minutes was found in the first few thousand random walk throughs, and other times it would take a few hundred thousand walk throughs before the 17 minute solution was found. To me, it did not seem like there were enough different combinations that would make it so difficult to randomly find the solution.

For those who cannot/will not run this code, the crux of the biscuit, given the times of the walkers above (1 minute, 2 minutes, 5 minutes, and 10 minutes), is to send the slowest people across together once there is someone faster on the other side. Or in other words, first send 1 and 2 across, then have 1 come back. Then, send 5 and 10 across, and have 2 come back. Then 1 and 2 make the final crossing.

BTW, Happy Talk Like A Pirate Day today.

## Overriding a TargetType Style without a Key in WPF

I have been doing a lot of work in WPF lately, and it is a different animal.

The default styles of a button did not look right for my application, so I came up with the following XAML that styles up all of the button objects in my application:

```<Style TargetType="{x:Type Button}"> <Setter Property="SnapsToDevicePixels" Value="true"/> <Setter Property="OverridesDefaultStyle" Value="true"/> <Setter Property="Background" Value="CornflowerBlue" /> <Setter Property="Template"> <Setter.Value> <ControlTemplate TargetType="{x:Type Button}"> <Border x:Name="Border" CornerRadius="0" BorderThickness="0" Background="{TemplateBinding Background}" BorderBrush="{TemplateBinding Background}"> <ContentPresenter Margin="2" HorizontalAlignment="Center" VerticalAlignment="Center" RecognizesAccessKey="True" /> </Border> <ControlTemplate.Triggers> <Trigger Property="IsMouseOver" Value="true"> <Setter TargetName="Border" Property="Background" Value="#4667A5" /> </Trigger> <Trigger Property="IsPressed" Value="true"> <Setter TargetName="Border" Property="Background" Value="#3C588C" /> </Trigger> <Trigger Property="IsEnabled" Value="false"> <Setter TargetName="Border" Property="Background" Value="LightGray" /> <Setter TargetName="Border" Property="BorderBrush" Value="#AAAAAA" /> <Setter Property="Foreground" Value="DarkGray"/> </Trigger> <Trigger Property="IsEnabled" Value="true"> <Setter Property="Foreground" Value="White"/> </Trigger> </ControlTemplate.Triggers> </ControlTemplate> </Setter.Value> </Setter> </Style>```

As you can see, I am using TemplateBinding to bind to the desired background color.

However, in one of my user controls, I want to be able to change the background color of the button in certain situations. Initially, I just created a copy of the above XAML, gave it a Key, and then used that key name to style up the Buttons that I wanted to.

As always, there is a better way. I found that there was a way to use a BasedOn in my new style to pull in the style from the global resources and just change what I needed, here is what it looks like:

```<Style x:Key="SpecialButton" TargetType="Button" BasedOn="{StaticResource {x:Type Button}}"> <Setter Property="Width" Value="20" /> <Setter Property="Visibility" Value="Collapsed" /> <Setter Property="Content" Value=">" /> <Setter Property="IsTabStop" Value="False" /> <Setter Property="Background" Value="LightGray" /> </Style>```

BTW, Happy Birthday to Eugene Levy, by far one of the funniest actors out there.

## DBNull string field handling

Let’s say for the sake of argument that you are using a SQL Server Compact database in your C# .NET application, and your User table has nvarchar fields that are nullable, and your User class doesn’t care if those fields are null, it just wants empty strings instead.

Sadly to say, you are eventually going to end up with nulls in those fields, and as a result, if you use a SqlCeDataReader to step through a record set, this kind of stuff will (at some point) give you a runtime error:

`myUser.UserName = (string)dataReader["UserName"]);`

So I started looking for the best way to handle this problem. What I didn’t want to do was this for every single string field assignment:

`myUser.UserName = (System.DBNull.Value == dataReader["UserName"] ? "" : dataReader["UserName"]);`

This seems a bit wasteful to me, as the data reader is accessed twice. Sure, I could have encapsulated this into a function to pretty up the code a bit, but that would just be hiding the ugliness. Then, it occurred to me to try the Convert class to see what would happen, and it turns out that this code knows how to convert a DBNull to an empty string:

`myUser.UserName = Convert.ToString(dataReader["UserName"]);`

The Convert class may in fact do the same thing as I have shown above, but I would hope that Microsoft would make their built in function better than something that I would just hack together.

BTW, I hope everyone out there has voted, this is an important election. (Finally, tomorrow I can watch TV or get the mail without being bombarded by increasingly stupider campaign and “issue” advertisements.)

## How to dynamically generate a TrackBallInfoTemplate

The Telerik ChartView control is nice, but if you cannot create your XAML ahead of time (or in other words, you don’t know how many LineSeries you are going to have on your chart), then you are in uncharted territory. Especially if you are not super solid in WPF and data binding as I am.

Using their example code, I was able to get the track ball info to show the date and value of the data points (basically the X and Y values of the data point), but instead I wanted to show a label for that LineSeries along with the Y value. Initially I tried to use a DataTemplate in the Resources of my user control, but I could not get the binding to work the way I wanted to.

Finally, to solve this issue, I had to resort to build the XAML in my code and set the TrackBallInfoTemplate. Here is what it looks like:

```// the class holding the data for the chart... public class SalesInfo { public string Employee { get; set; } public DateTime Time { get; set; } public int Value { get; set; } }   // then, further on down the code... Color[] colorArray = { Colors.Red, Colors.Green, Colors.Blue, Colors.Yellow };   // and... data = new RadObservableCollection(data.OrderBy(x => x.Time)); Color dataColor = colorArray[loopCounter % 4]; LineSeries line = new LineSeries(); line.Stroke = new SolidColorBrush(dataColor); line.StrokeThickness = 2; line.CategoryBinding = new PropertyNameDataPointBinding() { PropertyName = "Time" }; line.ValueBinding = new PropertyNameDataPointBinding() { PropertyName = "Value" }; line.ItemsSource = data;   StringBuilder templateString = new StringBuilder(); templateString.Append("<DataTemplate xmlns='http://schemas.microsoft.com/winfx/2006/xaml/presentation'>"); templateString.Append("<StackPanel Orientation='Horizontal'>"); templateString.Append("<TextBlock Text='" + u + "' />"); // u refers to the name of this line series (Employee) templateString.Append("<TextBlock Text=': ' />"); templateString.Append("<TextBlock Text='{Binding DataPoint.Value}' />"); templateString.Append("</StackPanel>"); templateString.Append("</DataTemplate>");   var xml = XmlReader.Create(new StringReader(templateString.ToString())); var tbiTemplate = (DataTemplate)XamlReader.Load(xml) as DataTemplate; line.TrackBallInfoTemplate = tbiTemplate; myTelerikChartView.Series.Add(line);```

And so now, here is what my chart view looks like with the customized track ball info:

BTW, Happy Birthday to Ty Tabor.

EDIT: I would like to take a moment to say thanks to Yavor from Telerik, he responded to my posting on the Telerik forums and pointed out that the DataPoint object has a DataItem object child that is the object that created the DataPoint. As a result, in my XAML Resources, I can bind to DataPoint.DataItem.Employee, and it works as expected. Here is that link:

Creating LineSeries programmatically with custom TrackBallInfoTemplate

## Azure + SSL

Sorry about the delay in between posts kiddies, I have been very busy at work with Routzy and playing baseball at Pirates Fantasy Camp. Hopefully soon the Routzy app will be approved and I will be able to return to a more normal pattern of posting.

In the mean time, if you have a Windows Azure web site or services, and you want to secure them with an SSL certificate, I found this blog post to be indispensable:

Windows Azure: Secure Site with SSL certificate

BTW, a big shout out to Ohio’s own John Glenn, who, 50 years ago today, orbited the earth for almost 5 hours, a tremendous feat for the time.

## Compound comparison in a LINQ join statement

I’ve been doing pretty much iPhone only postings recently, so this might change it up a bit.

So I am trying to go into our web application’s C# code to make some changes to the administration area of the web site.  (This is usually the only place I feel comfortable making changes, as this is not an area that customers actually use.)  We have a page that uses a store procedure to pull data from our SQL Server database and presents it on the page.

I needed to get more information out of the database than the store procedure was giving me, and I didn’t feel like modifying the procedure and then trying to rebuild the DBML, so I decided to convert it to a LINQ statement and bind to that instead of binding to the results of the stored procedure.

These things never go as planned.  I took a similar LINQ statement that I found in the application, but it did not do exactly what I wanted to do.  Basically, the LINQ statement I found used a simple comparison.  I needed to check for two different things in my comparison, so after a bit of research and trial and error, here is what I came up with:

```var p = (from ord in dc.orders join ordSt in dc.orderStatus on new { ord.orderID, b = true } equals new { ordSt.orderID, b = ordSt.isDeleted } where ord.customerID == custID select new { ord.orderID, ordSt.deletionDate } );```

I had to add the little “b = true” and “b = ordSt.isDeleted” parts because it would not let me use just the “true” in the comparison.  Ah, isn’t it great that LINQ is so simple?

## Don’t try, don’t catch

Have you ever had a situation where all of those nested try/catch blocks just get in your way when trying to chase down a problem? I just hate that.

Luckily, in Visual Studio 2008 (and other versions, I am sure), there is a handy dandy way to disable all of the try/catch blocks when you run the application in debug mode from the IDE.  Just go to the Debug menu, select Exceptions, click the box under the Thrown column for Common Language Runtime Exceptions (or others if that is what you are looking for), and click OK.  Now when the code has a problem, you see it right away instead of trying to work backwards through nested try/catch blocks in different classes and modules.

Just don’t forget to put it back to the way it was when you are done. I am not a huge fan of try/catch blocks, but their normal use definitely has its place.

## 2010 Central Ohio Day of .NET

A co-worker and I attended the Central Ohio Day of .NET on June 5, 2010. There was quite a bit of good content at the conference, which is a real tribute to the organizers, volunteers, and presenters.

The highlights of my day were sitting in on Matt Casto’s regular expressions talk, Phil Japikse’s M-V-VM primer, discussing the etymology of the MongoDB project with Sam Corder (I still say it was named such after the character in Blazing Saddles), Michael Eaton’s talk on WPF, and Parag Joshi’s demonstration of XNA/Windows Phone 7 game development.

## Demo days (CONDG meeting, December 14, 2009)

The Central Ohio .NET Developers Group held their final meeting of the year last night at the Microsoft office in Polaris. Four people gave short demos of Xbox, Zune HD, Windows Mobile, and iPhone, and talked about developing for each platform.

The highlight of the evening was my name being drawn as winning the year’s final and perhaps most craptastic door prize, which I then gave to my coworker who was attending the meeting with me. He is into free t-shirts.

## Battleship AI contest on Stack Overflow

Recently there was a contest running on Stack Overflow to design the best Battleship AI. Here is a link to the page:

What is the best Battleship AI?

I must admit that I am still smarting over this contest, as my BP7 contest entry did awesomely well and incredibly poor at the same time. Here is the code:

```namespace Battleship { using System; using System.Collections.Generic; using System.Drawing; using System.Linq;   public class BP7 : IBattleshipOpponent { public string Name { get { return "BP7"; } } public Version Version { get { return this.version; } }   Random rand = new Random(); Version version = new Version(0, 7); Size gameSize; List<Point> scanShots; List<NextShot> nextShots; int wins, losses; int totalWins = 0; int totalLosses = 0; int maxWins = 0; int maxLosses = 0; int matchWins = 0; int matchLosses = 0;   public enum Direction { VERTICAL = -1, UNKNOWN = 0, HORIZONTAL = 1 }; Direction hitDirection, lastShotDirection;   enum ShotResult { UNKNOWN, MISS, HIT }; ShotResult[,] board;   public struct NextShot { public Point point; public Direction direction; public NextShot(Point p, Direction d) { point = p; direction = d; } }   public struct ScanShot { public Point point; public int openSpaces; public ScanShot(Point p, int o) { point = p; openSpaces = o; } }   public void NewGame(Size size, TimeSpan timeSpan) { this.gameSize = size; scanShots = new List<Point>(); nextShots = new List<NextShot>(); fillScanShots(); hitDirection = Direction.UNKNOWN; board = new ShotResult[size.Width, size.Height]; }   private void fillScanShots() { int x; for (x = 0; x < gameSize.Width - 1; x++) { scanShots.Add(new Point(x, x)); }   if (gameSize.Width == 10) { for (x = 0; x < 3; x++) { scanShots.Add(new Point(9 - x, x)); scanShots.Add(new Point(x, 9 - x)); } } }   public void PlaceShips(System.Collections.ObjectModel.ReadOnlyCollection<Ship> ships) { foreach (Ship s in ships) { s.Place( new Point( rand.Next(this.gameSize.Width), rand.Next(this.gameSize.Height)), (ShipOrientation)rand.Next(2)); } }   public Point GetShot() { Point shot;   if (this.nextShots.Count > 0) { if (hitDirection != Direction.UNKNOWN) { if (hitDirection == Direction.HORIZONTAL) { this.nextShots = this.nextShots.OrderByDescending(x => x.direction).ToList(); } else { this.nextShots = this.nextShots.OrderBy(x => x.direction).ToList(); } }   shot = this.nextShots.First().point; lastShotDirection = this.nextShots.First().direction; this.nextShots.RemoveAt(0); return shot; }   List<ScanShot> scanShots = new List<ScanShot>(); for (int x = 0; x < gameSize.Width; x++) { for (int y = 0; y < gameSize.Height; y++) { if (board[x, y] == ShotResult.UNKNOWN) { scanShots.Add(new ScanShot(new Point(x, y), OpenSpaces(x, y))); } } } scanShots = scanShots.OrderByDescending(x => x.openSpaces).ToList(); int maxOpenSpaces = scanShots.FirstOrDefault().openSpaces;   List<ScanShot> scanShots2 = new List<ScanShot>(); scanShots2 = scanShots.Where(x => x.openSpaces == maxOpenSpaces).ToList(); shot = scanShots2[rand.Next(scanShots2.Count())].point;   return shot; }   int OpenSpaces(int x, int y) { int ctr = 0; Point p;   // spaces to the left p = new Point(x - 1, y); while (p.X >= 0 && board[p.X, p.Y] == ShotResult.UNKNOWN) { ctr++; p.X--; }   // spaces to the right p = new Point(x + 1, y); while (p.X < gameSize.Width && board[p.X, p.Y] == ShotResult.UNKNOWN) { ctr++; p.X++; }   // spaces to the top p = new Point(x, y - 1); while (p.Y >= 0 && board[p.X, p.Y] == ShotResult.UNKNOWN) { ctr++; p.Y--; }   // spaces to the bottom p = new Point(x, y + 1); while (p.Y < gameSize.Height && board[p.X, p.Y] == ShotResult.UNKNOWN) { ctr++; p.Y++; }   return ctr; }   public void NewMatch(string opponenet) { wins = 0; losses = 0; }   public void OpponentShot(Point shot) { }   public void ShotHit(Point shot, bool sunk) { board[shot.X, shot.Y] = ShotResult.HIT;   if (!sunk) { hitDirection = lastShotDirection; if (shot.X != 0) { this.nextShots.Add(new NextShot(new Point(shot.X - 1, shot.Y), Direction.HORIZONTAL)); }   if (shot.Y != 0) { this.nextShots.Add(new NextShot(new Point(shot.X, shot.Y - 1), Direction.VERTICAL)); }   if (shot.X != this.gameSize.Width - 1) { this.nextShots.Add(new NextShot(new Point(shot.X + 1, shot.Y), Direction.HORIZONTAL)); }   if (shot.Y != this.gameSize.Height - 1) { this.nextShots.Add(new NextShot(new Point(shot.X, shot.Y + 1), Direction.VERTICAL)); } } else { hitDirection = Direction.UNKNOWN; this.nextShots.Clear(); // so now this works like gangbusters ?!?!?!?!?!?!?!?!? } }   public void ShotMiss(Point shot) { board[shot.X, shot.Y] = ShotResult.MISS; }   public void GameWon() { wins++; }   public void GameLost() { losses++; }   public void MatchOver() { if (wins > maxWins) { maxWins = wins; }   if (losses > maxLosses) { maxLosses = losses; }   totalWins += wins; totalLosses += losses;   if (wins >= losses) { matchWins++; } else { matchLosses++; } }   public void FinalStats() { Console.WriteLine("Games won: " + totalWins.ToString()); Console.WriteLine("Games lost: " + totalLosses.ToString()); Console.WriteLine("Game winning percentage: " + (totalWins * 1.0 / (totalWins + totalLosses)).ToString("P")); Console.WriteLine("Game losing percentage: " + (totalLosses * 1.0 / (totalWins + totalLosses)).ToString("P")); Console.WriteLine(); Console.WriteLine("Matches won: " + matchWins.ToString()); Console.WriteLine("Matches lost: " + matchLosses.ToString()); Console.WriteLine("Match winning percentage: " + (matchWins * 1.0 / (matchWins + matchLosses)).ToString("P")); Console.WriteLine("Match losing percentage: " + (matchLosses * 1.0 / (matchWins + matchLosses)).ToString("P")); Console.WriteLine("Match games won high: " + maxWins.ToString()); Console.WriteLine("Match games lost high: " + maxLosses.ToString()); Console.WriteLine(); } } }```

The thing I find odd about this was that against the winning entry, Dreadnought, my AI was far and away the most successful, winning about 40% of the individual games. The next closest competitor to Dreadnought was BSKiller, crafted by my compatriot in crime, John Boker, winning 20% in the initial round robin and 12% and 14% in the knockout round.

And yet, BP7 stunk against most of the other real submissions, which is a bit mysterious to me. I understand that there is some random fortune involved here (for example, in the round robin, BSKiller defeated BP7 121 games to 80, even though in my own testing, BP7 was winning about 54% of the games over BSKiller), but to be defeated at almost every turn?

Oh well. Here is my VS2008 solution and class files, if you would care to try it out for yourself:

Battleship solution

Also, when I was first looking into this problem, I created some graph paper to help me visualize certain situations. Here is the PDF file of this graph paper:

Battleship Graph Paper

Happy Thanksgiving everyone! (For those outside the U.S., Happy November 26th.)