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