Sunday, December 21, 2008

C# - Counting the number of occurrences of a substring

How many times have you needed to find the total number of times a substring has appeared within a string? This common programming problem can be approached from many different angles.

You could write brute force code that walks through the string and looks at it character by character, keeping a tally of how many complete matches with the substring was found.

You could use IndexOf within a while loop, incrementing the counter and moving the start point on each iteration of the loop, exiting the loop when IndexOf returns that there are no more occurrences of the substring.

But, there is only one way that I know how to do it without a loop. Use the Replace method of string.

Here is a code snippet showing how to use this very simple yet powerful way to count the number of occurrences of a substring within a string.


string myString = "Lorem ipsum dolor sit amet, " +
"consectetur adipisicing elit, sed do eiusmod " +
"tempor incididunt ut labore et dolore magna " +
"aliqua. Ut enim ad minim veniam, quis nostrud " +
"exercitation ullamco laboris nisi ut aliquip " +
"ex ea commodo consequat. Duis aute irure " +
"dolor in reprehenderit in voluptate velit " +
"esse cillum dolore eu fugiat nulla pariatur. " +
"Excepteur sint occaecat cupidatat non proident, " +
"sunt in culpa qui officia deserunt mollit anim " +
"id est laborum.";

string mySubString = "dolor";

int Count = (myString.Length -
myString.Replace(mySubString, string.Empty).Length)
/ mySubString.Length;


This will return a count of 4, the correct number without a single loop in your code!

This code is case sensitive. To create a case insensitive version, just move myString and mySubString to lowercase.


string mySubString = "lo";

int Count = (myString.Length -
myString.ToLower().Replace(mySubString.ToLower(),
string.Empty).Length) / mySubString.Length;


The case sensitive version would have only returned 4 because it would not have found the first lo at the beginning because the L in Lorem is capitalized. But with the case insensitive version, the code correctly finds all 5 instances of our substring.

This may seem like such a small thing, but everyday programming is filled with these "Old School" tricks!

Sunday, December 14, 2008

C# - Hiding interface methods (How and Why)

In my attempt to create a "Generic Object Reference Implementation" (I talked about this in a previous post here) version of System.Collections.Generic.LinkedList I needed to implement the ICollection<T> interface.

Well, you will notice that the Frameworks' LinkedList implementation has four methods to add a node: AddFirst, AddBefore, AddAfter and AddLast. Yet, ICollection<T> demands that we have another method called Add.

But, LinkedList does not have and Add method.

And, LinkedList does implement the ICollection<T> interface.

Hmmm.

Well, after some searching and a Usenet post, I found out how it is done.

It is called Implementing the interface method EXPLICITLY for the interface. This is accomplished by placing the name of the interface before the method name, as such:

ICollection<T>.Add

The method Add will now will be only available when the class is cast as ICollection<T>. This gives us the best of both worlds, we get the benefit of implementing ICollection<T> without having to expose a method that may not make sense in the context of the class.

Saturday, December 6, 2008

Switcheroo - An old "Magazine" game in Silverlight, Part 1

In a previous post, I described the game Switcheroo. In this first post we will create a the start splash screen, the game board and the end splash screen.

The splash screen for a very visual game should be striking. Unfortunately, I am not a graphic artist, so the best I could come up with is the name switcheroo rendered using WordArt in Word.

We need to display the splash screen along with a start button. When the start button is clicked, we can then hide the splash screen and display the game board.

If you remember from that previous post, players can either place a piece on the 5x5 gameboard or rotate a row to the left or right, or rotate a column up or down. So, not only do we need a 5x5 checkerboard but we also need a mechanism to allow the players to rotate the columns and rows.

To accomplish this I added an extra column at the start and the end of the gameboard and an extra row to the top and the bottom of the gameboard. I added small golden arrows.

Once the game has been one or lost, on the placement of the winning move, we need to hide the gameboard and show the splash screen again. This time with a button declaring their win or loss and asking if they wish to play again.

The only problem with this is from a aesthetic point. When we place the winning piece, rotate the winning piece into place or our opponents move defeats us, we do not want to immediately flash to the splash page. The player may not have been able to even see that the move was a winning move or what their opponent even did to win, so we need to include a delay upon determining that the game is in fact over.

In the code for this first part, the both splash screens will work as they are supposed to, but since we have not created any game logic yet, we will consider any click on the gameboard to be the winning move and after our short delay the "You lose" version of the splash screen will display.

If you click on the button, the gameboard will display again and the whole process will start again, but the code will rotate between the "You win" and "You lose" messages to verify that both code paths work.

As you can see, instead of a lot of repetitive XAML, the only hardcoded XAML sets up the grid that will contain the gameboard and the elements for the splash screen.
<UserControl x:Class="Switcheroo.Page"
xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
Width="300" Height="300">
<Grid x:Name="LayoutRoot"
Tag="Bob">
<Grid.ColumnDefinitions>
<ColumnDefinition Width='25' />
<ColumnDefinition Width='50' />
<ColumnDefinition Width='50' />
<ColumnDefinition Width='50' />
<ColumnDefinition Width='50' />
<ColumnDefinition Width='50' />
<ColumnDefinition Width='25' />
</Grid.ColumnDefinitions>
<Grid.RowDefinitions>
<RowDefinition Height='25' />
<RowDefinition Height='50' />
<RowDefinition Height='50' />
<RowDefinition Height='50' />
<RowDefinition Height='50' />
<RowDefinition Height='50' />
<RowDefinition Height='25' />
</Grid.RowDefinitions>
<Image x:Name="XamlBoard"
Grid.RowSpan='7'
Grid.ColumnSpan='7'
Source='Splash.png' />
<StackPanel VerticalAlignment="Center"
HorizontalAlignment="Center"
Grid.RowSpan="7"
Grid.ColumnSpan="7">
<Button Click="Start_Click"
Content="Start"></Button>
</StackPanel>
</Grid>
</UserControl>

The XAML code also available here!

using System;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Input;
using System.Windows.Markup;
using System.Windows.Media;
using System.Windows.Shapes;
using System.Windows.Threading;

namespace Switcheroo
{
public partial class Page
{
private class MyColors
{
public static Color Aliceblue { get { return GenerateColorStruct(0xFFF0F8FF); } }
public static Color Cyan { get { return GenerateColorStruct(0xFF00FFFF); } }
public static Color Darkcyan { get { return GenerateColorStruct(0xFF008B8B); } }
public static Color Darkgoldenrod { get { return GenerateColorStruct(0xFFB8860B); } }
public static Color Gold { get { return GenerateColorStruct(0xFFFFD700); } }

private static Color GenerateColorStruct(uint color)
{
var mask = 0x000000FF;

var returnval = new Color
{
A = ((byte)((color >> 24) & mask)),
R = ((byte)((color >> 16) & mask)),
G = ((byte)((color >> 8) & mask)),
B = ((byte)((color) & mask))
};

return returnval;
}
}

private class GameBoard
{
internal readonly int[,] Board = new int[5, 5];

public GameBoard()
{
for (var i = 0; i < 5; i++)
{
for (var j = 0; j < 5; j++)
{
Board[i, j] = -1;
}
}
}
}

readonly DispatcherTimer dt = new DispatcherTimer();

private bool GameOver;
private int GameWinner = -1;
private GameBoard Switcheroo = new GameBoard();

public Page()
{
InitializeComponent();
}

private void Start_Click(object sender, RoutedEventArgs e)
{
Switcheroo = new GameBoard();
LayoutRoot.Children.Clear();
CreateGameBoard();
GameOver = false;
}

private void dt_Tick(object sender, EventArgs e)
{
dt.Stop();
DisplayGameOverSplash();
}

private void Canvas_MouseLeftButtonDown(object sender, MouseButtonEventArgs e)
{
GameOver = true;

GameWinner = GameWinner == 0 ? 1 : 0;

if (GameOver)
{
dt.Interval = new TimeSpan(0, 0, 0, 0, 500); // 500 Milliseconds
dt.Tick += dt_Tick;
dt.Start();
}
}

private void CreateGameBoard()
{
var CellColor = false;
Canvas c;

for (var i = 0; i < 7; i++)
{
for (var j = 0; j < 7; j++)
{
if (i != 0 && i != 6 && j != 0 && j != 6)
{
c = new Canvas
{
Tag = (i + ":" + j),
Background =
(CellColor
? new SolidColorBrush(MyColors.Aliceblue)
: new SolidColorBrush(MyColors.Darkcyan))
};
}
else
{
c = new Canvas
{
Tag = (i + ":" + j),
Background = new SolidColorBrush(MyColors.Cyan)
};


if (j == 6 && i != 0 && i != 6)
{
var p = new Polygon
{
Fill = new SolidColorBrush(MyColors.Gold),
Stroke = new SolidColorBrush(MyColors.Darkgoldenrod)
};

p.Points.Add(new Point(10, 5));
p.Points.Add(new Point(40, 5));
p.Points.Add(new Point(25, 15));

c.Children.Add(p);
}
else if (j == 0 && i != 0 && i != 6)
{
var p = new Polygon
{
Fill = new SolidColorBrush(MyColors.Gold),
Stroke = new SolidColorBrush(MyColors.Darkgoldenrod)
};

p.Points.Add(new Point(10, 20));
p.Points.Add(new Point(40, 20));
p.Points.Add(new Point(25, 10));

c.Children.Add(p);

}
else if (i == 6 && j != 0 && j != 6)
{
var p = new Polygon
{
Fill = new SolidColorBrush(MyColors.Gold),
Stroke = new SolidColorBrush(MyColors.Darkgoldenrod)
};

p.Points.Add(new Point(5, 10));
p.Points.Add(new Point(5, 40));
p.Points.Add(new Point(15, 25));

c.Children.Add(p);

}
else if (i == 0 && j != 0 && j != 6)
{
var p = new Polygon
{
Fill = new SolidColorBrush(MyColors.Gold),
Stroke = new SolidColorBrush(MyColors.Darkgoldenrod)
};

p.Points.Add(new Point(20, 10));
p.Points.Add(new Point(20, 40));
p.Points.Add(new Point(10, 25));

c.Children.Add(p);

}
}

c.MouseLeftButtonDown += Canvas_MouseLeftButtonDown;
Grid.SetColumn(c, i);
Grid.SetRow(c, j);

LayoutRoot.Children.Add(c);

CellColor = !CellColor;
}
}
}

private void DisplayGameOverSplash()
{
string ButtonText = GameWinner != 0 ? "You Win! Play Again?" : "You Loose! Play Again?";

const string Splash = "<Image xmlns='http://schemas.microsoft.com/winfx/2006/xaml/presentation' " +
"xmlns:x='http://schemas.microsoft.com/winfx/2006/xaml' " +
"x:Name='XamlBoard' Grid.RowSpan='7' Grid.ColumnSpan='7' Source='Splash.png' /> ";

const string Stack = "<StackPanel xmlns='http://schemas.microsoft.com/winfx/2006/xaml/presentation' " +
"xmlns:x='http://schemas.microsoft.com/winfx/2006/xaml' VerticalAlignment='Center' " +
"HorizontalAlignment='Center' Grid.RowSpan='7' Grid.ColumnSpan='7' />";

string Button = "<Button xmlns='http://schemas.microsoft.com/winfx/2006/xaml/presentation' " +
"xmlns:x='http://schemas.microsoft.com/winfx/2006/xaml' Content='" + ButtonText + "'></Button>";

LayoutRoot.Children.Clear();
LayoutRoot.Children.Add((Image)XamlReader.Load(Splash));
LayoutRoot.Children.Add((StackPanel)XamlReader.Load(Stack));
((StackPanel)LayoutRoot.Children[1]).Children.Add((Button)XamlReader.Load(Button));
((Button)((StackPanel)LayoutRoot.Children[1]).Children[0]).Click += Start_Click;
}
}
}

The C# code also available here!

Monday, December 1, 2008

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!