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.

Becoming a Star!!!

Everybody has a story for themselves. Story in which He/She is the hero/heroine. We always want to be heroes. The ones who is correct, good and shiny all the time. That is quite important when it comes to life since it is the motivation for us to get things done and dusted. But is that all ? Will that 'Being the Star' motive will make you happy ? Will it make you feel the way you want to ? That is a question lies beneath.

When we are small we see people who inspires us the most and say 'I will be like him one day'. But when we grow up we will find out that the person which we were looking forward to be is not what he was or we will find someone who is the trend and we change our motive once again. After living more than twenty odd years in my life I had so many 'Stars' that I aways want to be. But after reflecting on that long years and my motivations it was pretty obvious for me that it is not the 'Star' it was something else that we were looking forward to be when we say 'He's my star'.

After all is it easy to be a Star ? No, it is true that it is the long hours of trying hard and not letting yourself down will bring you up and make you a star. But if that Star can not bring you the happiness you want then why will you push hard. Why should we have a motive to be a Star ? Then I am pretty sure that it is the Ego in our self, or the insider in our self who always want to be in-charge of everything is the reason to us to becoming a star.

But might not be the best of choice to let that inner-person win in every situation. It is true that we need that ego and the inner person to make us the toughest competitor. But we should not let him drive our life. After all we are human begins. We are 'Homo sapiens', a valuable product of 'Nature'. So we need to understand that in nature we are all the same. If we analyze the 'Environment' its all about the relationships, the helps in which it depends. So as something of the environment it is our relationships, emotions and morals which will make us winners in our lives.

 Being a star is good. But being human is what matters.

Spring Webflux - Part 3

Reactive Programming is the newest trend in programming world. In this article series of Spring Webflux I have been discussing on how to build a Reactive Application  using  Spring Webflux. In the Part 2 we have discussed how to build a simple reactive application using Spring Boot. Lets dig deep into more advanced routing methods and filter functions in this article.

Context Path for Application

In Spring MVC can give a context path to our application. In Spring Webflux we don't have a configuration for that. But we can set a context-path for multiple routes. Following is how we can do that. 

@Configuration
public class RouterWithContext {
    @Bean
    public RouterFunction<ServerResponse> routeWithContext(SampleHandler handler) {
        return nest(path("/context"),
                route(GET("/sample"), handler::handleNestedRoute));
    }
}

RouterFunctions.nest(...) will let you build nested routes in your application. It will take a RequestPredicate and a RouterFunction as arguments. Nested route is analogous to having a context path in Spring MVC.

Up to now we have just tried out HTTP GET Method in our application. What happen if we want to have request-body and we want to use it in our application. Lets do add a functionality to our application to accept a request-body and echo it back with some modifications. For this we will use a HTTP POST with a simple request body.

Our Request body should look as follows.

public class RequestBody {
    private String name;
    private int age;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }
}

The handler function should first take out the request body and reshape the content and sends back the response. We can do it in imperative way using ServerRequest.bodyToMono(...).block() method which will give us the request-body. And the we can reshape it and generate the response. But since we are doing reactive programming using Mono.block() is an anti-pattern. What we can do is we can reshape the request-body in a more functional way.

    public Mono<ServerResponse> handleRequestWithABody(ServerRequest request) {
        return request
                .bodyToMono(RequestBody.class)
                .flatMap(requestBody -> {
                    ResponseBody responseBody = new ResponseBody();
                    responseBody.setStatus("Success");
                    responseBody.setDescription("Successfully Handled the request");
                    responseBody.setRequestBody(requestBody);
                    return ServerResponse.ok().body(fromObject(responseBody));
                })
                .switchIfEmpty(
                        ServerResponse.status(HttpStatus.BAD_REQUEST).build());
    }

We will first acquire the request-body as a stream using ServerRequest.bodyToMono(...). And then we can apply a 'flatmap' on that data-stream and reshape the content and get a data-stream. Finally there is some magic-code, the 'switchIfEmpty' which will check whether the data-stream is empty and send a default ServerResponse. Now we done with the handler-function. So, we have add the route now. This route has some specialty in it. This route consumes a request-body. So, it is preferable if we could mention the media-type which is accepted by this route. So, we can configure our route as follows.

route(POST("/echo").and(contentType(MediaType.APPLICATION_JSON)), handler::handleRequestWithABody);

As you can see here RequestPredicates can be concatenated and return a RequestPredicate. Here we have concatenated RequestPredicate which checks for HTTP Method and a RequestPredicate which checks for Content-Type Header.

Adding a Filter

Most often than not we want to secure our APIs. Spring Security has a more precise ways of securing an application, but here we want to have a simple key-base authentication for our application. For that we can use a simple filter function. First of all we have write an authenticator. Authenticator is a filter-function which will take ServerRequest and a HandlerFunction as arguments and return a ServerResponse.

@Component
public class Authenticator {
    @Value("${configuration.api.access-key}")
    private String apiKey;

    public Mono<ServerResponse> filterRoute(ServerRequest request, HandlerFunction<ServerResponse> handlerFunction){
        if (request.headers().asHttpHeaders().containsKey("x-api-key")) {
            if (request.headers().asHttpHeaders().get("x-api-key").get(0).equals(apiKey)) {
                return handlerFunction.handle(request);
            }
            return ServerResponse.status(HttpStatus.UNAUTHORIZED).build();
        } else {
            return ServerResponse.status(HttpStatus.UNAUTHORIZED).build();
        }
    }
}

Finally you can add the filter to the router.

    @Bean
    public RouterFunction<ServerResponse> routeWithContext(SampleHandler handler) {
        return nest(path("/context"),
                sampleRoute(handler)
                        .and(handleRequestBodyRoute(handler)))
                .filter(authenticator::filterRoute);
    }

You can find the sample code here.

Spring Webflux - Part 2

Reactive Programming is one of the most popular programming paradigms now a days. Spring Webflux is the newest flavor of Spring Framework with the taste of Reactive Programming. In my first article I have discussed about the building boxes of Spring Webflux. So, in this article we will build a simple application with Spring Webflux.

Application Structure

We will create a Spring-boot Application as a Maven Project. Add the following dependencies to Maven-POM. 

<dependencies>
 <dependency>
  <groupId>org.springframework.boot</groupId>
  <artifactId>spring-boot-starter-webflux</artifactId>
 </dependency>
 <dependency>
  <groupId>org.projectlombok</groupId>
  <artifactId>lombok</artifactId>
  <optional>true</optional>
 </dependency>
 <dependency>
  <groupId>org.springframework.boot</groupId>
  <artifactId>spring-boot-starter-test</artifactId>
  <scope>test</scope>
 </dependency>
 <dependency>
  <groupId>io.projectreactor</groupId>
  <artifactId>reactor-test</artifactId>
  <scope>test</scope>
 </dependency>
</dependencies>

Annotate the Spring-Boot-Application class with @EnableWebFlux. Adding this annotation to an '@Configuration class' or 'Spring-Boot-Application class' imports the Spring Web Reactive configuration from WebFluxConfigurationSupport.

@SpringBootApplication
@EnableWebFlux
public class WebfluxSampleApplication {

 public static void main(String[] args) {
  SpringApplication.run(WebfluxSampleApplication.class, args);
 }
}

Building the Application

Spring-Boot is so simple as you can use Spring-Webflux as you use Spring-MVC. You can just use Spring-Controllers. Following is a sample how to use controllers with Spring-Webflux.

@RestController
public class IndexController {
    @GetMapping("/index")
    public Mono<String> getIndex() {
        return Mono.just("Hello World!");
    }
}

If you run the application and access 'http://localhost:8080/index' in your browser you will get a response of 'Hello World!'. And it is what you have to do to say 'Hello World!' in Reactive. But this is the most traditional way you do in Spring. But Reactive Programming is always comes with Functional Programming.

You can use Webflux in more functional way. You can write your own router functions and handlers for those routes. Routes are more likely the resource-paths. When you do a request to the resource path with the correct HTTP method the handler will handle the request and respond.

First lets write the handler function. A handler function will take a ServerRequest and returns Mono<ServerResponse>.

@Component
public class SampleHandler {
    public Mono<ServerResponse> handleRequest(ServerRequest request) {
        return ServerResponse.ok().body(Mono.just("Sample Route Successful!"), String.class);
    }
}

Now we can write the router for the handler. Whenever a request comes to the resource-path of the router it will calls the handler function and respond to the request.

@Configuration
public class SampleRouter {
    @Bean
    public RouterFunction<ServerResponse> sampleRoute(SampleHandler handler) {
        return route(GET("/simple-route"), handler::handleRequest);
    }
}

Now if you run the application and access 'http://localhost:8080/simple-route' from your browser, you will get 'Sample Route Successful!' as the response. So, that is how we can be more functional in Spring Webflux. In the next article we will discuss about more advance routing functions. The complete source code for this article can be found here.

Going Reactive with Spring - Spring WebFlux - Part 1

Spring is one of the most popular frameworks used by Java-Developers. Manageable learning curve of Spring has lift it to the top of most-used Java-Framework through out the world. The latest of Spring Family has arrived recently with the flavor of Reactive-Programming in-built to it. This article series is about building a robust-reactive API using spring-webflux.

What is Reactive-Programming ?

Reactive Programming is a programming paradigm where you program with asynchronous-data-streams. In Imperative-Programming we get the data and perform actions on it. But in Reactive-Programming we don't wait for data to present to perform actions rather we instruct what to do when data is available. If you are new to Reactive-Programming I would recommend you to first go through my-article on Reactive-Programming before you start here.

The basic-building blocks of Reactive-Programming is Data-Streams. Data-Stream is like a pipe. From one end we put-data into it and from the other end we will retrieve the data. But we will not pull out the data, but the data will be pushed when it is available. 

In Spring-Webflux, there are two types of Data-Streams, namely Mono and Flux. As the name infers Mono is a data-stream which contains at most one element. In the other hand Flux is a data-stream containing more-than one element. Mono and Flux are derived from Project-Reactor as Spring-Webflux is built on top of Reactor.

Starting with Reactor

Before we dive into Spring-Webflux we should first understand the concept of Mono and Flux. 

So, lets take a look at how we can compose a Mono.

  Mono<String> sampleMono = Mono.just("sample_mono");

As we can see, this is a Mono which is composed with a single String in it. If we can only use single elements in a data-stream then the concept becomes useless. So that is how Flux come into play. Lets see how we can compose a Flux.

Flux<String> sampleFlux = Flux.just("sample1", "sample2", "sample3");

So, we can compose a data-stream of any type(reference-type) using Mono.just(...) and Flux.just(...). But, in Reactive world a data-stream is the laziest person you can find. Even though you composes and apply some functions on the data, stream might not give you the result unless you have subscribed to the stream. This means data-stream would do nothing unless you have subscribed to it. Lets see how we can subscribe and get the data out.

sampleMono.subscribe(data -> System.out.println(data));

So, if you run the code you will see sample_mono will be printed out in the console. But, this is just a shorthand of writing a Subscriber. A Subscriber is composed with four-functions. onSubscription, onNext, onError and onComplete which will be called out in different stages in subscription. onSubscription will be called when the subscription is started. onNext will be called when the next data item is available in the stream. onError as the name propose will be called when an error occurred in the stream. And finally onComplete will be called when the subscription is completed.

In Reactor there is a Subscriber interface which you can implement and provide as a subscriber to stream. Lest see how we can implement a subscriber for our sampleFlux.

        Subscriber<String> subscriber = new Subscriber<String>() {
            @Override
            public void onSubscribe(Subscription subscription) {
                System.out.printf("Subscription Started");
            }

            @Override
            public void onNext(String s) {
                System.out.println("Next : "+s);
            }

            @Override
            public void onError(Throwable throwable) {
                throw new RuntimeException(throwable);
            }

            @Override
            public void onComplete() {
                System.out.printf("Subscription Completed");
            }
        };
        sampleFlux.subscribe(subscriber);

If you run this code you will see that onSubcription will be called in the first place. And for every element in the stream onNext will be called after every element is over onComplete will be called. You can find out some interesting samples on reactor in this article.

Spring MVC : The Framework - Part 2

Spring-MVC Sample

As I described in the previous segment, spring-mvc is a framework that is really useful in developing web-applications. So, to demonstrate the abilities of Spring-MVC lest start with a sample application for library-management-system and understand the building boxes of Spring-MVC. 

Initializing Project

1. In this sample project we will use 'Maven' as our dependency management tool. So, initialize a maven-project and add the dependency for 'spring-mvc' in the 'pom' file.
2. Then Create a directory-structure as follows :

Configurations for Spring-MVC

First of all as I explained in the last chapter we have to map the servlet which our application going to fit. To that we have to create a 'web.xml' file inside 'spring-mvc-sample/src/main/webapp/WEB-INF' directory and add the following configurations to it : 

This configuration will tell the 'DispatcherServlet' to handle the requests coming from the configured URL pattern. After initializing the 'DispatcherSevlet' the frame-work will try to load the 'application-context' from a file named '[servlet-name]-servlet.xml' file which should also be located at 'webapp/WEB-INF' directory by default (to configure this spring-mvc has a mechanism which I will describe in the next chapter).  So, for the application-context to load add a file named 'spring-sample-servlet.xml' into spring-mvc-sample/src/main/webapp/WEB-INF' directory and add the following lines to it.

'context-component-scan' is the place Spring starts searching for the configurations. Usually we will give the 'group-ID' or the 'Base-Package' of our project as base-package. 

The next configuration is for the view-resolver which resolves views when a view-name is given. So, according to this configurations it will resolve views in the path 'WEB-INF/jsp' and with the '.jsp' prefix.

Then add a controller class 'HomeController' inside the 'spring-mvc-sample /src /main /java /com /springmvc /sample /controller' direcotory and add the following lines to it. 

@Controller annotation will tell that this class should be setved as 'Spring-MVC-Controller'. @RequestMapping annotation on top of the 'getHomePage' method will inform Spring where to map the request and according to which HTTP-method.  

And then create a 'home.jsp' file inside 'webapp/WEB-INF' directory and add sample HTML content into it.

And the sample app is done. You can checkout the full-project here. 

Git Commit Messages

Why Messages ?

Git is a Version-Control system to track the  changes to the files in your computer. It is a tool to control and keep track of the changes to software products.  Git Commit  is where you put some specific changes to files into the Git Local Repository.  It is compulsory to put message when you do a Git-Commit. 

A message is a communication  medium. What are we going to communicate through a 'Git-Message' ? Is it really important to put a message to a commit ? To whom are we going to communicate ? 

When talking about git we always remember a software-project where multiple developers are working. So, a commit-message is going to communicate the group of developers about what has been changed in the project. In a software project a group of people works to achieve a common goal. So, it is really important to all of them to know what has happened to the project. But the message should be much more meaningful and descriptive. 

Some Standards

If we search internet we could find some standard ways to put git-messages. In this article I would cover some basic standards which I use. 

A change to the software project can be a new-feature, update to an existing feature or a bug-fix. So, if you to write a commit message it would be much easier to others if we could let them know to which category of above was the change belongs to. So, when you write a message always start it with either one of these three prefixes. 

1. New : (if a change was a new feature)
2. Fix : (if change is a bug fix)
3. Update :  (if change is an update to an existing feature)

After the  prefix then put a semi-colon and write your message. After the message you have to convey whether the change is finished or not. If the change is finished put a full-stop (.) after the message. If the change is unfinished you can put a comma (,) and wip which stands for 'work in progress'. 

Eg : 

       Fix : Login Page changed.

       New : User registration validation added, wip