Friday, March 6, 2015

Matrix permutation

I came across this interesting problem when I was solving a coursera assignment (8-puzzle) on Algorithms & Data Structures. This isn't related to the 8-puzzle where you need to visualize the solution as a game tree data structure.

I think this is related to the game tree.

Consider you have a \(2 \times 2\) grid where there is an \(X\) in one of the squares. You can make children of that figure only by moving \(X\) it to the adjacent square either left, right, top, bottom. How many iterations do I need to ensure that \(X\) has been through all the locations. It is possible that you can get the \(X\) in a previous position by making a child of child (from the previous iteration: avoid such repetition.

Here is a figure that shows the case for the grid in question:

This is a very trivial example. What could be the solution for a larger grid?

Wednesday, February 25, 2015

writing code for doing combinations

Combination is a common problem in mathematics which deals with different ways via which we can select r objects given n, where r < n. So we have n distinct objects and we can't have repetitions. For e.g., if we are to select 3 letters from the string ABCD, we have the following


So there are a total of 4 ways of selecting 3 objects.

Perfectly follows the formula,
\[{n \choose r} = \frac{n!}{r! \times (n-r)!}\]
A more simplified version of the above formula is,
\[{n \choose r}= \frac{n(n-1)(n-2)...(n-r+1)}{r!}\]
This is actually better for computations.

But how to write code to output the various selection as we've done above?

I'd take to pseudo code but you can't implement the pseudo code in one language and see the results immediately. Hence I've taken to python. I am not python-biased...I just like the simplicity of expressing logic. It models pseudo code fairly well...

There are better ways to write can use a generator instead of a loop that creates and returns an array. "Generator" is a concept that is available on most of the popular programming languages. You can explore my other gists to see how this is done in python and java.

Meanwhile, happy programming.

Friday, November 21, 2014

javascript promises

I used to wonder what are promises for a long time...then I saw a video regarding the topic...and one thing comes to mind...

Code Cleanup...

Or rather, it aids in easy understanding, readability, and thus making it more manageable.

Now here is my explanation. I assume you have worked with jQuery show, hide, fadeIn, fadeOut api's. Here is how a fadeIn works.

This is a simple example. However, there is an overload for fadeIn which enables us to execute code once the animation completes as shown in the below example...
Now say there are few elements you want to show up one-after-another. Shown below is the traditional way of coding for this requirement:

You can see there are a lot of nested callbacks. At a look its hard to follow what is happening. Imagine writing the same for a variable number of li elements...

Here is the refactored version that uses promises:
So we had to write a bit of deferred functions and function wrappers...hence there is a bit of extra code...But it tries to convey, what our objective was...

Or doesn't it?! Do share your thoughts...

There is a lot more to promises than what's shown here. You should go check the jquery page on $.Deferred() usage and various scenarios.

If you are in a mood to be tested with what you've gained from reading this post, I suggest you try writing code to sequentially fadeIn variable number of li elements...

Happy coding...

Tuesday, March 25, 2014

making testable database access layer

Although I am a C# developer, the principles advocated here can apply to any language/platform. 

Why is testing important?

The question is very subjective and its answer depends on the profile of the person asking.

If its a product manager, he'd probably answer, testing is something done to see if the product works fine (in a very broad sense so the end-user/business function is not impeded).

If its an independent tester trying to answer this question; he'd have various responsibilities which sort of answer these questions:

  • are all the use cases of the product are satisfied?
  • has the product or software satisfied all non-functional requirements?
  • etc..
So for one such person described above, testing is important to ensure if the software does what its designed to do. 

Now, if you happen to be writing a lot of code, and "you" ask this all good probability it means you are a novice software developer. 

If this is disheartening to learn, take solace in the fact that you reading this post is some indication you want to achieve professional excellence. "You want to write good code". :) But, be warned, being a software engineer/developer encompasses a much greater responsibility than just writing good code.

So what is testing to a developer/software engineer?

I'll digress a bit here to say something about writing testable code "in general". Many of the projects that people land into these days are not exactly new development, or, from-the-scratch deal. Of course, this is a decision, a senior manager/architect has to decide. This decision affects project schedules. People actually start with fixating the schedules first. These things are usually negotiated after engaging with client/end-users, or, decided after studying market trends where people decide a suitable release date. After the schedules are fixed a conscious decision is made on the amount of engineering required and level of quality that is acceptable.

Therefore, not every software development can afford to be engineered well enough, and, thereby, the level of quality will also show itself that way.

As a software engineer/developer, writing testable code ensures that your code does what it is supposed to do. Therefore, we have to carefully plan and foresee what sort of inputs should go into a particular program, what inputs make sense, and what inputs will fail, etc. We are also trying to see if the program does exactly does what it is supposed to do (without errors).

Testing your data access layer (DAL)

Here is a small idea to help you understand how testing your DAL works. Say you are writing a blog engine. One crucial thing to test for might be, to see if the submitted blog post is saved in database correctly. The database identifies each post with a unique postID. Your test procedures would be:
  1. to "post" a blog (with title and post body) to database and retrieve its postID.
  2. retrieve a post with the above postID
  3. check if the post title and post body match with what you started with.
If you happen to encounter error anywhere in the above steps it means your code fails, and you have to investigate further.

Repository pattern - independently testing your DAL

We are going to focus on segregating all your data access to another layer (DAL). So that your application code need not concern itself with directly talking to the database. There are multiple advantages to this - one of them is being able to test it independently. 

So suppose we take the blog engine as an example. We'd design our dal as follows:

1. Entities and interfaces first

public class BlogPost
 public int PostID { get; set; }
 public string PostTitle { get; set; }
 public string PostBody { get; set; }
 public List<Comment> Comments { get; set; }
 public DateTime PostedOn { get; set; }
 public User BlogUser { get; set; }

public class Comment
 public int CommentID { get; set; }
 public strimg CommentText { get; set; }
 public DateTime CommentedOn { get; set; }

public class User
 public int UserID { get; set; }
 public string UserFullName { get; set; }
 public string UserNickname { get; set; }

public interface IBlogEngine
 void InsertPost(BlogPost newPost);
 void AddComment(Comment newComment);
 List<BlogPost> GetPosts();
 BlogPost GetPostById(int PostID);

2. Concrete implementation

public class BlogEngineMsSql: IBlogEngine
 public void InsertPost(BlogPost newPost)
  int newPostId;
  //SQL server data access code...
  //new post id is retrieved from db somehow...
  newPost.PostID = newPostId;
 //other implementstions follow

3. Test code

public class UnitTest1
 public void TestBlogInsert()
  BlogPost testPost = new BlogPost() { 
   PostTitle = "test",
   PostBody = "test",
   BlogUser = new User() { UserID = 123, UserNickname = "Mock", UserFullName = "Mock" }
  IBlogEngine db = new BlogEngineMsSql();
  var id = testPost.PostID;
  var post = db.GetPostById(id);
  Assert.AreEqual(testPost.Title, post.Title);
  Assert.AreEqual(testPost.Body, post.Body);

So in this example, we've created a simple blog engine. Note the interface and its concrete implementation. (For now assume its Sql Server specific code). The use of an interface allows us to mask the underlying implementation. In other words, I can make my application code completely unaware of the db implementation like this:

IBlogEngine db = BlogEngineFactory.GetMsSqlInstance();

...or even better, if I used some DI pattern:

IBlogEngine db = BlogEngineFactory.GetEngineInstance();

This way my unit test code is independent of the underlying db implementation.

The repository pattern is simply the act of exposing or channelling your database access code via interfaces. The dual advantage of this is,

(a) you can write test code which is fairly independent of the underlying implementation, and
(b) enforces a modular approach.

If tomorrow we want to run the same tests against an oracle database, we just add the corresponding dal assembly in our project and run the tests. If we are using some dependency injection, we'd change our application configuration to reflect likewise.

This decoupled nature, allows us to write test code, and, the actual implementation code, in parallel. And in theory, no person should write both; he should write code for any one - either the implementation or the test code. But if you are stuck with yourself, then the only go is to write the tests first, then actual implementation. This should progress incrementally, method after method. You write a test for the method; write the implementation, test it; fix errors and re-test, else move to the next method, and repeat as necessary.

Thursday, February 20, 2014

bootstrap extensions for mvc 4

You are probably thinking that the world is moving ahead with ASP.NET MVC 5.1. So why is this post still "stuck" with mvc 4? Well, that just happens to be the IDE I am working with. Anyway enough with those kind of limitations.

My professional work has taken me through a joy ride with many frameworks to be used along with mvc like knockout.js, kendo, bootstrap, etc. Kendo is something that has caught my fancy at the moment. And it has something to do with the following lines of code:

    .Columns(columns =>
        columns.Bound(m => m.Title);
        columns.Bound(m => m.Author).Width(250);
        columns.Bound(m => m.PublicationDate).Width(250);
    .DataSource(dataSource => dataSource.Ajax().Read(read => read.Action("GetItems", "Home")))
    .Selectable(selectable => selectable.Mode(GridSelectionMode.Single))

Notice the stuff we write as argument to the Columns method call. Of course there is intellisense support when you write such code in Visual Studio. But the underlying idea is generics - lot of generics!

And then there is bootstrap.

I notice that bootstrap has a lot of components - like a menu, navigation bar, dropdowns, etc. The amount of code you have to write for them is also sort of plethoric. Hence, I thought there must be simpler way to reduce the amount of code you write for them.

Therefore, I started up a github repo for the same purpose. How will this be useful? Well, at least for me, its like toolkit I can carry around with me.

Saturday, December 28, 2013

javascript internals: scopes

Now here is something that can definitely tease the programmer in you.

Someone in stackoverflow asked a question related to javascript. It goes something like this:

Snippet 1:

<script type="text/javascript">
	function MyFunc() {
	var f1 = MyFunc;	
	function MyFunc() {
<script type="text/javascript">

<script type="text/javascript">

f1() outputs 2 in a message box. This is acceptable and expected.

Snippet 2: 

<script type="text/javascript">
    function MyFunc() {
    var f1 = MyFunc;
<script type="text/javascript">
    function MyFunc() {
<script type="text/javascript">
 f1() outputs 1.

Wait...what the hell just happened? Isn't the above two snippets equivalent?

You can try it out at jsbin, or jsfiddle, or whatever place, but you'd still end up with the same observation.

My answer relates the idea of scoping that takes place in a script block. A whole new scope is created for the entire code inside a script block to run in. Hence for our 2nd case, we have MyFunc defined in scope 1 - i.e. the scope of the first script block. So MyFunc is now an object which is created with scope 1. f1 now points to this object.

When the second script block is executed, we have MyFunc created in a new scope. Hence a new object is created in that scope. So the MyFunc created in the first scope is not the same MyFunc created in the second scope. They are essentially two separate objects. And now since f1 points of the first object created; calling the method pointed by it will output a message box saying 1.

In the first snippet. The object is created only once. However, MyFunc is defined twice in the same scope. Hoisted I believe is the correct term to use here. So, one object is created, and, that object, is associated with the most recent definition. Hence the call to f1 will output a message box saying 2.

Upvote my answer if you agree with the explanation, else you can provide your own comments there.

Happy programming...

Thursday, October 10, 2013

the csv file problem?!

Do you know what a csv file is...? Even if you don't have experience, you could at least try some cloud based spreadsheet app like Google Spreadsheet. Even products like MS Excel give you options to save your worksheet to a CSV format. Basically open one such app, type in data in a few contiguous columns and rows...and then when it comes to saving you have the option of saving it as a Comma Separated Value or CSV.

The final result will look similar to this when opened in a plain vanilla text editor:

So now you know why its "comma" separated...however to be more generic, people can be a little uneasy with that character, hence they resolve to use some other character like a tab ('\t'), or a pipe ('|'), etc.

Hence to be more generic we should be calling this pattern of data storage Delimiter-Separated-Value or DSV. This pattern of storage is meant to store tabular data via a series of delimiters (to separate columns) and row-terminators (or line-terminators).

Now comes the more tricky problem...

Imagine there is program that would parse dsv files given its delimiter and row-terminator. You are only provided with a dsv file with no knowledge of the above two do you write a program to find those two things out?!

Drop in a comment if you happen to figure this out or if you want an answer to it.

Happy programming.