Matrix Traversal with Backtracking

 Problem

Recently I came across this problem of matrix-traversal where I have to find a path from the starting index to last index. Here what I needed to do is to find whether path exists or not. Matrix is full of '0's and '1's. '1' means you could not go forward. '0' means you could go forward. You could move 'right', 'left', 'up' or 'down'. No diagonal moves allowed.

My Approach

Initially I could not decode this because I had only 10 minutes to provide a solution for this. My thought process was just as a usual programmer. I was thinking imperatively. My initial matrix looked like this.

I was trying to run two-loops (loop inside a loop). But could not get the thing done with the given time. Then after my assignment I tried to solve this again. I found a solution which has the basic traversal with forward moves (go-right and go-down). And one of the main concern was I could not do back-tracking (go-left or go-up).

In my assignment I was given a hint to think on this with regards to recursion. So, I started to rethink with recursion.

Recursive Solution

So, if you think recursively you have to think in a way to divide this problem into smaller pieces of it-self. What we could divide is the matrix. Initially I was miss-guided to think that I will have to divide this matrix physical (I mean actually create a partial matrix from the current matrix). But later I identified this division should be logical.

If you go through the above diagram. You might see that the logical division of initial matrix would look similar to it. If the right-cell is not blocked traversal could do via right-move. If right-cell is blocked but cell below the initial-cell is not blocked then we could proceed through down-move traversal. If both of them are blocked then we do not have a move. 

Lets think that move-down is possible. Then our latest logical matrices would be like follows.

If you think in this way you might see that if you move forward there will be four logical matrices created when you consider all the moves possible.

You might notice that there are two new logical matrices which we could identify here. Namely we have Left-Move and Move-Up (mainly for back-tracking purposes). Following would be my recursive algorithm.

Imperative Solution

When we thinking about a recursive solution we are always in danger with stack-overflow or out-of-memory due to the depth of function calls could recur (check here for more information).  So, it is better to implement an imperative solution to a problem rather than a recursive solution. 

So, I tried to improve my initial solution (with imperative approach) which has two for-loops.

In the above algorithm you could see that there is a problem. You could not back-track (in other words you could not go up or left). Issue here is with the structure of the for-loop and the logic I was thinking about the proceeding to next position of the matrix. 

So, what I thought was mixing dynamic matrix manipulation (updating traversing-matrix dynamically) & integrating traversing logic of recursive algorithm. 

The key difference here is I have replaced the for-loops with while-loops. And the logical matrix which the loop is operating will be changed dynamically. 

Java Implementation for above algorithm could be found here.

State Design Pattern

State Design Pattern

If you are a programmer, Design Pattern are some main aspects that you need to study and grow up on. Even though number of Design-Pattern exists in this article we are going to explore a Behavioral Design Pattern called State Pattern. 

According to Wikipedia  state pattern is a behavioral software design pattern that implements a state machine in an object-oriented way. With the state pattern, a state machine is implemented by implementing each individual state as a derived class of the state pattern interface, and implementing state transitions by invoking methods defined by the pattern's super-class.

If you are familiar with State Machines, then State Pattern is not a harder aspect that you cannot master. State Pattern is well suited when the behavior of an object changes in accordance with the internal state of the object.  So, if anyone wants to build an Object-Oriented State Machine, then the most suitable structure to be used is State Pattern.

Structure of State Pattern

In State Pattern we have an 'Context' class which interact with client. You can think of this like the 'State Machine'. Then define an 'State' Abstract Class. Implement this class for different states that the Machine should change. Define an Abstract State Specific Behavior in 'State' class and override it in every sub-class. Have a pointer to 'Current State' inside the 'Context' Class. When the internal state of the machine should change, adjust the 'Current State' pointer to the next specified state of the machine. 

State Pattern does not specify where state transitions will be defined. There are two choices: inside the 'Context' class or Each individual state derived class. Advantage of the latter is that we can add new states easily. But each State derived class has knowledge of its siblings, which introduces a dependency between sub-classes.  

Here is the Class Diagram for State Pattern.

Is it a Good Choice ? 

Any concept is a good choice in its own domain. So, use this Pattern if an only if the behavior of objects in the domain is dependent of the internal state of the object.

Here is a code example for State Pattern. 

Why Go Reactive?

Reactive Programming

Computer Programming is the process of creating instruction that can tell a computer to execute some tasks. Basically we can identify three types of computer programs in modern world. Namely Transformational Programs, Interactive Programs and Reactive Programs. Transformational Programs are pretty simple. They take set of inputs and produce an output. Interactive is bit different which interacts with users and other programs in its own speed and produce outputs. Reactive is also interacting with users and produces outputs, this time around not in its speed but in the speed of the user. 

Reactive Programming is where you implement computer programs to be reactive. It is an Asynchronous Programming Paradigm which is oriented around Data Streams. Data Stream is like a pipe where some service inputs the data from one end and another service receives data in the other end. And most importantly Reactive also means that it is event-driven. In Reactive Programming the program reacts to any occurred event and fetches the relevant data when data is ready in the data-stream. 

For an example think about the expression [ a = b + c]. In Imperative Programming to take the value of [ a ] we have to recalculate the mentioned expression again and again whenever the values of [ b ] and [ c ] are changed.  But in Reactive whenever the values of [ b ] and [ c ] changes the value of [ a ] will be automatically update without executing the expression. Whenever the change-event for [ b ] or [ c ] occurs the [ a ] which is listening to the data-stream then will automatically update it-self.

Reactive Principles

There are four major principles to be applied when programming re-actively. More than principles we can think of these are constraints on Reactive Realm.

• Responsive
• Reactive mean responding to interactions. The program has to respond to user interactions in the speed of user.
• Resilient
• Program should be able to maintain and run the service with the occurence of faults.
• Scalable
• The service should be able to scale-up and scale-out with maintainig the responsiveness.
• Event-Driven
• Reactive is always works whenever event occurs. Program should listens to interactions and works accordingly.

Push or Pull

In programming, there are three mechanisms to take inputs. Push, Pull or Pull-and-Push. Pulling is when the program needs the data it waits until data is ready. Pushing is program executes asynchronously and fetch the data whenever data is ready. Hence Reactive Programming uses data-streams it uses 'Pulling' to fetch data. 

More on Data Streams

Data-Streams are extremely powerful. They are asynchronous. You can execute expressions on data when they are in a data-stream. Executing expressions or functions on data-streams means you can shape the data into the shape which applications needs it to be. Linux pipe-lining is a good example for a data-stream where you inject output from one function into another. And Java-Streaming API is another good example. 

Should or Should Not ?   

There are some good frameworks for Reactive Programming. ReactiveX has produced Reactive Extensions for major programming languages. React is another good Reactive JavaScript Framework. 

Even-though lot of programming paradigms available we should use them very carefully only in accordance with the requirement. So, it is not good to go 'reactive' every where. But if the requirement is event-driven, responsive program then it is better to use 'reactive'.  Please refer to this blog post and ReactiveX home page for more details.