Wednesday, May 12, 2010

Little Distraction: Knight vs Keypad

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

Friday, May 7, 2010

Day 1

Preface to definition of the program

     Last night lecture at physics class was quite slow, so I did some brainstorming on paper and came up with an idea for the program. As I said in "The begging," I was looking for something useful. One thing that always been annoying me working in windows is the repetitive traversal or browsing of folders or directories to access files spread around the computer. Some people like to use special programs like "Explorer" or "Windows Commander" or even in command prompt or shell when working with the file-system, but the thing is when I am not actually working on the computer I like to be in comfort... I like clicking, drag and dropping... easy approaches. Some create tons of shortcuts to folders on their desktop, but I like to keep my desktop clean and nice. So I ended up thinking in dashboard/toolbar style direction. It will be more clear when Ill define it more technically. Yeah and the pic above is the great sketch in my notepad. Now you can tell I'm not and artist.
  
Definition of the program.

    The program will consist of a main window and a windows tray icon. The main window will allow to drag and drop folders, files, hyperlinks and plain text on it. For any of those it will generate a specific icon. Dashboard window will have a nice toolbar that will allow to create, switch and select tabs/pages.  All tabs and entries are saved. The window itself will be draggabable, resizeable, and what is most important dockable so that the user can attach it to sides of the screen. Clicking on the windows tray icon will show the main window on top of all windows or will hide it.
   
   So far Ill stick with folders and files only. Clicking on these will open them as if they were links. Also when holding the mouse over the certain part of a folder element it will populate a sub-window with the contents of that folder, similar to how windows Start worked in Windows XP. This behavior should persist for the sub-windows as well.

   The toolbar will have buttons to add add and remove tabs, switch between these, pin/keep on top button and options button which will pop up configuration window. I want to keep the main window as simple as possible.

    Right click on the main window will populate a context menu, something like
  • Add
  • Configure
  • Hide
  • About
  • Quit
    Same kind of(maybe exactly the same) menu will pop up when right clicking the task-bar icon.

   For now Ill stick with creating rather simple interface, but later on I want to make it customizable... For example letting user to customize how many rows or columns of elements they want... list layout or item layout... maybe even allowing them to set it look like the Mac OS dashboard as a option. Also I want to make it skinnable later on.

   One last thing.... the name of the program will be "instaLink"... just cause I want so.

   So the way I want to proceed with this is that first Ill build up the UI(user interface) in WPF(windows presentation foundation), then Ill add the business logic, and then... then Ill try to add all cool customization features. Next post will cover the whole process of building the user interface.


Sunday, May 2, 2010

The beginning

Greetings!

Me! memememe:


I am a 21 year old student majoring in Computer Science. Currently I attend one of Los Angeles community colleges with hope to transfer to a university in near future. I do freelance programming projects on known online freelance sites. In my free time I try to learn programming on my own and sharpen my skills, since the only thing that school teaches me is to hate it... more and more. Also I play competitive online fps when at computer and the most important rest of the time I try to live a decent student life and get most out of it.

Why? What? How?

I am here because I want to conduct a little experiment. I want to learn a new technology which is the WPF. I have about 1 month before the end of this semester and I will be very busy with schoolwork these times, but I still want to learn the basics in this next month. The way I want to do it is by writing a simple yet useful program utilizing this technology. I will use this blog to post each step of the development from design to the final product and if everything goes well I will post the project on SourceForge in the end. The main point of the experiment is to see how much time do I spend on each stage of development. It is also interesting to write down the ideas and review in the end... and it will be even more interesting to read the whole nonsense lets say 5 years after this and have a good laugh about it... and Ill be happy if this will be useful for someone on the net.

Technical side:

I will be programming this in C# since it is my strongest. I guess I'll be using .Net 4.0 framework. I work in Visual Studio 2010, I will use SVN (AnkhSVN/VisualSVN) for subversioning and Ill probably use NSIS scriptable installer in the end for deployment.

Philosophy and conventions:


In this blog I will be using my casual language, and I won't hesitate to express my anger and excitement. I often use IRC slang and I can't help it. My grammar may be poor... hopefully spell checker will help me out on this. I haven't decided yet what the exciting project will be... Maybe even Ill be reinventing the wheel, but even if so that's OK since the point is learning. I don't really want to use any 3rd party libraries or rip-off code from net, because again the point is learning. I won't focus on creating a test driven 1337 enterprise application but rather something simple and useful. Ill do my best to write correct code and I promise to state clearly if I write peace of a bad code to the best of my knowledge. Design is important and Ill take my time to design the application the best I can.

My next post will define the application... I will try to think of something interesting. Ill start with research and Ill define the design of the application before I actually start programming. That's it for today.