Tuesday, August 14, 2018

Functional Programming - Finding valleys

If we were from ASP.Net Web Forms world and tasted the ASP.Net MVC at least once, it is very difficult to go back. It is similar when we go from imperative world to functional programming world. This post is a continuation of Functional Programming series. The advantages of FP has already discussed in earlier posts. 
The problems are mainly taken from HackerRank and trying to solve using FP methods. The main intention is to understand how to solve problems functionally which otherwise considered as 'solvable only imperatively'.

The Problem

Input is a sequence of D and U characters. D means one step down down and U means up. A person named Gary is hiking from sea level and end at sea level. We need to find out how many valleys he covered. If he is in a deep valley and had a small hill and again went down, it is counted as one valley. Detailed description can be found in original link

Traditional solution

The traditional (FP was there for long, but not in main stream) ie if someone comes from imperative programming world, they get it as state machine problem. Yes there are states where Gary reaches after each step. The state has to be mutated based on the rules.

In functional programming, mutation is not an appreciated word. So lets see how can we do this without mutating the state.

Functional way

Language used is JavaScript

function countingValleys(n, s) {
  
  var res = s.split('').reduce((context, value,index,arr) => {
    //console.log(context)
    if(value === 'D') {
      if(context.s === 0 ) { return {v:context.v+=1,s:context.s-=1}}
      else return {v:context.v, s:context.s-=1}
    }
    if(value ==='U'){
      return {v:context.v,s:context.s+=1}
    }
    else {
      //console.log('error');
    }
  }, {
    v: 0,
    s: 0
  });
  return res.v
}

Here n means number of steps and s is the input character sequence. If we enter this into HackerRank browser based editor, with their auto generated wiring code, this returns the number of valleys covered.

How it runs

It uses the Fold concept of FP which is implemented in JavaScript using reduce() function. Initial state is given to the reduce function, when the function progress through each element, it create new states (context variable hold the state) from existing state with the modification required. Yes as per FP, mutation is evil not creation of object from another. Also notice that -= and += is not mutating the state, instead its a transformation when assigning value during creation.

The commented console.log lines will help to under the flow it allowed those to run.

Happy functional coding...

No comments: