Last night I was browsing posted projects one of freelance programming website and I came across one project which they described as "classical knight problem." These was very interesting for me, because I have never solved a problem like this, nor I had a clue how to solve it. So I started from scratch and went till the very end without looking up previous solutions. I like to learn things this way. On top of it the guy offered $250 for this program, which would be an awesome bonus. Briefly the problem is to calculate all possible combination of code for a security keypad where the keys each next key-press has to be a 'knight-move' from previous key. Someone with solid knowledge in discreet math would probably recognize the algorithm right away, but I didn't which made it even more interesting. One of the requirements was that the program hast to be in C# .Net 2.0, so I couldn't take advantage of LINQ, which didn't really affect the process. So I will write here how I solved this problem.... Btw I just drew the knight figure above which was lots of fun... he the 1337 keypad bruteforcer knight!
Rules:
- We can move on the keypad only in 'knight-moves' ie., 2 keys vertically and 1 key horizontally, or 2 keys horizontally and 1 key vertically.
- We can start from any key
- Length of the key-code is 10 keys
- Only 2 vowels allowed in each key-code
- Layout of the keypad is the picture on the right
- ***********************************
- FIND all possible key-codes
Understanding the problem:
So whats going on? Nothing really complicated... we get to start from any key, and for each key we get a set of keys where we can move next. So the problem is to walk each possible knight route with length 10, and of course we have to check that the route is valid in terms of our rules, which in this case is that it contains no more than 2 vowels. From now on I will refer to the keypad as a 'board', and the keys will be 'cells', and the key-presses will be 'moves', I guess its little more intuitive in chess terms.
So first of all it would be cool to get the set of possible moves foe each cell. We can see clearly that for A the set will be {L, H}, for B it will be {I, M, K} for M {F, B, D, J} and so on... I have no idea what would be the most efficient way to set up the data structures for this, but my choice was following: values of cells namely A,B,C...3 as strings; the sets of values like List
, and the association of each key with the set Dictionary>. Ok... so now with this setup in order to solve the problem we will have to walk the dictionary in following manner: for each key in the dictionary -> take the key and add to sequence then for each value in subset(list) take the value add to sequence and that's the next key so take the subset and do the same for each value until we get a sequence of length 10... once we got it we check if it matches the condition of 2 vowels if so then this sequence is a solution. Smells like a recursion... be we haven't got there yet :P
Design of the program
Ok so lets stop the math/structure nonsense and start program design :D
Like any programmer that wants to be a good programmer I wanted to design this program to be bit more abstract... so we can solve for any kind of board and any rule of moves. So my approach in design was to write following classes and structures:
- Cell2D - just a pair of x,y coordinates.
- Board - encapsulates our values and their coordinates on the board, provides means to access values by given coordinates, determine if coordinates, or a cell is a valid cell for this board, provides means to access the coordinates(cell) of the a value. (Important, I assume that there are no duplicate values)
- Figure - and abstract class for a figure... it encapsulates the position of the figure on the board, and what most important the moves of a figure.
- Knight - a concrete implementation of knight figure. (Inherits figure)
Implementation
Ill start with implementation of classes, and then the solution calculation routine will follow.
Cell2D structure is pretty simple
struct Cell2D
{
public int X;
public int Y;
public Cell2D(int c1, int c2)
{
X = c1;
Y = c2;
}
}
The Board class is little more complex. Some notes:
Constructor takes a 2 dimensional array as a parameter, and the 'empty' parameter is string which designates cells which should not be considered as part of the board.
class Board
{
public int SizeX { get; private set; } //maximal width
public int SizeY { get; private set; } //maximal height
public string Empty { get; set; } //empty string value
private string[,] arr;
Dictionary < string, Cell2D > coords=new Dictionary < string, Cell2D >();
public Board(string[,] Array, string emptyCellString="")
{
arr = Array;
SizeX = arr.GetLength(0);
SizeY = arr.GetLength(1);
Empty = emptyCellString;
buildCoords();
}
private void buildCoords()
{
for(int i=0 ; i< SizeX ;i++)
for (int j = 0; j < SizeY; j++)
{
Cell2D cel = new Cell2D(i, j);
if (IsValid(cel))
coords.Add(GetValue(cel), cel);
}
}
public bool IsValid(int x, int y)
{
if ((x < 0) || (y < 0))
return false;
if (arr == null)
return false;
if((x>=arr.GetLength(0))||(y>=arr.GetLength(1)))
return false;
if(arr[x,y]==Empty)
return false;
return true;
}
public bool IsValid(Cell2D cell)
{
return IsValid(cell.X, cell.Y);
}
public string GetValue(int x, int y)
{
if (IsValid(x, y))
return arr[x, y];
else
throw new System.ArgumentOutOfRangeException();
}
public string GetValue(Cell2D cell)
{
return GetValue(cell.X, cell.Y);
}
public Cell2D GetCoords(string value)
{
Cell2D cel=new Cell2D();
if (coords.ContainsKey(value))
cel = coords[value];
return cel;
}
}
As you can see a Figure takes a Board parameter, and initial position of the figure on the board. List of delegates to encapsulate figure moves here is something I pride myself... this way for each concrete implementation we just can write functions for all possible kinds of moves.
abstract class Figure
{
protected delegate Cell2D Move(Cell2D position);
private Board myBoard;
protected List < Move> moves=new List < Move>();
public Cell2D Position{get;set;}
public Figure(Board board, Cell2D position)
{
this.Position = position;
myBoard = board;
SetMoves();
}
public Figure(Board board, int x, int y)
{
this.Position = new Cell2D(x,y);
myBoard = board;
SetMoves();
}
public List < string> AvailableMoves()
{
List < string> list=new List < string>();
foreach (Move m in moves)
{
Cell2D cell = m(Position);
if(myBoard.IsValid(cell))
list.Add(myBoard.GetValue(cell));
}
return list;
}
protected abstract void SetMoves();
}
And here is the Knight class... notice the delegates to anonymous methods. Basically moves are functions, which take the current position of the figure and return a cell where the figure can be moved. Clearly one way to improve this is to allow each move function to return a set of cells. After all all that routine could be done by one function call I guess... but I believe this strategy is better.
class Knight: Figure
{
public Knight(Board board,Cell2D cell)
: base(board, cell)
{
}
public Knight(Board board, int x, int y)
: base(board, x, y)
{
}
protected override void SetMoves()
{
moves.Add(delegate(Cell2D cel){return new Cell2D(cel.X+1,cel.Y+2);});
moves.Add(delegate(Cell2D cel){return new Cell2D(cel.X+2,cel.Y+1);});
moves.Add(delegate(Cell2D cel){return new Cell2D(cel.X+2,cel.Y-1);});
moves.Add(delegate(Cell2D cel){return new Cell2D(cel.X+1,cel.Y-2);});
moves.Add(delegate(Cell2D cel){return new Cell2D(cel.X-1,cel.Y-2);});
moves.Add(delegate(Cell2D cel){return new Cell2D(cel.X-2,cel.Y-1);});
moves.Add(delegate(Cell2D cel){return new Cell2D(cel.X-2,cel.Y+1);});
moves.Add(delegate(Cell2D cel){return new Cell2D(cel.X-1,cel.Y+2);});
}
}
So that much for the design...
Now the actual program
string[,] arr = { {"A","B","C","D","E"},
{"F","G","H","I","J"},
{"K","L","M","N","O"},
{"","1","2","3",""} };
Board myBoard = new Board(arr, "");
Knight myKnight = new Knight(myBoard, new Cell2D(0, 0));
TimeSpan ts = new TimeSpan();
DateTime startTime;
TextWriter tw = new StreamWriter("knight.txt", false);
Console.WriteLine("Generating...");
startTime = DateTime.Now;
prinTheValidSequencesFile(myBoard,myKnight,tw); //does the calculations
ts = DateTime.Now - startTime;
tw.WriteLine("Execution time: {0} min {1} sec {2} millisec", ts.Minutes, ts.Seconds,ts.Milliseconds);
tw.Close();
Console.WriteLine("Done");
The following method builds the dictionaries of possible moves and calls the recursive function sequencerFile that actually creates the sequences of possible moves.
static void prinTheValidSequencesFile(Board board, Knight knight,TextWriter wt)
{
Dictionary < string, List < string > > dic = new Dictionary < string, List < string > >();
int count = 0;
for (int i = 0; i < board.SizeX; i++)
for (int j = 0; j < board.SizeY; j++)
{
if (board.IsValid(i, j))
{
knight.Position = new Cell2D(i, j);
List < string > moves = knight.AvailableMoves();
dic.Add(board.GetValue(i, j), moves);
}
}
foreach (KeyValuePair < string, List < string> > pair in dic)
{
sequencerFile(dic, 0, new List < string > (), pair.Key, ref count,wt);
}
wt.WriteLine("Total count: " + count);
}
So here it is the magic recursive method that pretty much does the job. Notice it calls checkSequence which checks if the sequence is valid and outputs to a file
static void sequencerFile(Dictionary < string, List < string > > dic, int depth, List < string > sequence, string key, ref int count,TextWriter writer)
{
sequence.Add(key);
if (depth == 9)
{
if (checkSequence(sequence))
{
foreach (string s in sequence)
writer.Write(s + " ");
writer.WriteLine();
count++;
}
return;
}
foreach (string s in dic[key])
sequencerFile(dic, depth + 1, new List < string>(sequence), s, ref count,writer);
}
And the last but not the least important method to check for valid sequence. All we have to do here is to check that the sequence doesn't contain more than 2 vowels
int Count=0;
foreach (string s in seq)
{
if ((s == "A") || (s == "E") || (s == "I") || (s == "O"))
Count++;
}
//var i = (from x in seq where (x == "A" || x == "E" || x == "I" || x == "O") select x).ToList();
if (Count > 2)
return false;
else
return true;
The Result
The result is a 21 megs large file which contains all possible combinations that match the requirements. Also the number of those combinations and the time it took to run... here they are:
Total count: 1013398
Execution time: 0 min 2 sec 702 millisec
I just hope I got it all right :D
Performance-wise ~3 secs IMHO is ok for this problem, however it can be drastically improved utilizing multithreading. My guess is that it would do in half of this time if we'd launch 4 threads each of them doing the recursive routine... the only problem there is to remember about 1 mb stack size limit...
PS
The code clearly needs some heavy re-factoring... and design can use some enhancement. To be honest I have no plans on working on it... it was just a small experiment. The program was written by a n00b programmer in 3 hours all I can say. Funny thing is that I just spent more time writing this post than actually writing the program... makes me double question why in the world do I do this blogging.
However any comments are welcome... if there are some mistakes on my side I'm willing to fix those. If someone needs the whole source code, just let me know Ill upload the VS project somewhere. If you need to help understanding the code again just let me know.
PPS
I never got any money for this project D: but I still enjoyed wasting my time on it ;)
