Archive

Posts Tagged ‘programming’

Functional programming and Declarative programming


Imperative programming paradigm contains the description of each step need to be performed to solve a problem. This approach is also referred as an algorithmic approach to solve a given problem. Most well-known languages like c, c++ or java are imperative type programming languages.

Functional programming is implementation of a certain task in the form of composition of different functions.

In a very simple terms, we can understand the difference between the above two as Imperative languages describe “how to” accomplish a goal and functional programming describes “what to” aspect of it. That means imperative programming languages contain loops, conditional statements, methods whereas, functional paradigm contains functions (recursions).

The main difficulty to transition to the functional programming is many are quite familiar with the declarative method of thinking style. Functional programming requires a different set of mind set to describe the problems in the form of functions.

Many imperative languages (such as C++11) are providing ways and means to add the support for the functional programming paradigm to their language tool kit. This allows the developers to easily make use the best of the both worlds.

 

The following are very few language constructs provided by C++ language (C++ 11) to facilitate the functional programming paradigm.

auto key word:

ex: auto a = 10;


#include <iostream>
#include <stdio.h>
using namespace std;

int main(void)
{
	auto n = 10;
	cout << n << endl;
	getchar();
}

Output: 10

#include <iostream>
#include <stdio.h>
using namespace std;

int main(void)
{
	auto str = "Hi!";
	cout << str << endl;
	getchar();
}

Output: Hi!

The above code makes declaring a variable much cleaner and much easier.

Lambda functions: (Source from http://en.cppreference.com/w/cpp/language/lambda)

Characteristics:

  1. Unnamed function object
  2. Captures scope in its closures

Syntax:

[ capture-list ] ( params ) mutable(optional) exception attribute -> ret { body }

[ capture-list ] ( params ) -> ret { body }

[ capture-list ] ( params ) { body }

[ capture-list ] { body }

1) Full declaration.

2) Declaration of a const lambda: the objects captured by copy cannot be modified.

3) Omitted trailing-return-type: the return type of the closure’s operator() is determined according to the following rules:

§  if the body consists of nothing but a single return statement with an expression, the return type is the type of the returned expression (after lvalue-to-rvalue, array-to-pointer, or function-to-pointer implicit conversion);

§  otherwise, the return type is void.

(until C++14)
The return type is deduced from return statements as if for a function whose return type is declared auto. (since C++14)

4) Omitted parameter list: function takes no arguments, as if the parameter list was ().

mutable – allows body to modify the parameters captured by copy, and to call their non-const member functions
exception – provides the exception specification or the noexcept clause for operator() of the closure type
attribute – provides the attribute specification for operator() of the closure type

capture-list – a comma-separated list of zero or more captures, optionally beginning with a capture-default.
Capture list can be passed as follows (see below for the detailed description):
 [a,&b] where a is captured by value and b is captured by reference.
 [this] captures the this pointer by value
 [&] captures all automatic variables odr-used in the body of the lambda by reference
 [=] captures all automatic variables odr-used in the body of the lambda by value
 [] captures nothing
params – The list of parameters, as in named functions, except that default arguments are not allowed(until C++14). if auto is used as a type of a parameter, the lambda is a generic lambda (since C++14)
ret – Return type. If not present it’s implied by the function return statements ( or void if it doesn’t return any value)
body – Function body

#include <iostream>
#include <stdio.h>
using namespace std;

int main(void)
{
	auto min = [](int a, int b) { return a < b ? a : b; };
	cout<< min(12, 34) << endl;
	getchar();
}

Output: 12

In the above example: the closure is empty that means it is not capturing anything but only two parameters are passed, this function takes a and b and returns the minimum.

Example: Caputure by value


#include
#include
using namespace std;

#include <iostream>
#include <stdio.h>
using namespace std;

int main(void)
{
	int divisor = 10;
	auto divideAllSum = [divisor](int a, int b) { return a / divisor + b / divisor; };
	cout<< divideAllSum(30, 40) << endl;
	getchar();
}


In the above example divisor was captured by value hence this value cannot be changed inside the lambda function.
Output: 7
Example: Caputure by reference


#include <iostream>
#include <stdio.h>
using namespace std;

int main(void)
{
	int divisor = 10;
	auto divideAllSum = [&divisor](int a, int b) { divisor = 5;  return a / divisor + b / divisor; };
	
	cout<< divideAllSum(30, 40) << endl;
	cout << "divisor : " << divisor << endl;
	getchar();

}

Output:
14
divisor : 5
In the above example no matter what the value being sent to the function the function is changing it to 5 and returning the value.
Capture all the scope as reference:

#include <iostream>
#include <stdio.h>
using namespace std;

int main(void)
{
	int divisor = 10;
	auto divideAllSum = [&](int a, int b) { divisor = 5;  return a / divisor + b / divisor; };
	
	cout<< divideAllSum(30, 40) << endl;
	cout << "divisor : " << divisor << endl;
	getchar();

}

In the above case entire the calling function scope has been captured as a reference hence it is possible to modify the divisor variable to 5.
Capture whole scope as a value:

#include <iostream>
#include <stdio.h>
using namespace std;

int main(void)
{
	int divisor = 10;
	auto divideAllSum = [=](int a, int b) { return a / divisor + b / divisor; };
	cout<< divideAllSum(30, 40) << endl;
	getchar();

}

In the above example “=” is part of closure signifies that the whole scope has been passed as a value hence can use all the variables part of the calling scope.

Using lambda functions as an argument to functions:


#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main(void)
{
	vector<int> l;
	for (auto i = 11; i >= 0; i--)
		l.push_back(i);
	sort(l.begin(), l.end(), [](int a, int b) {
		return a >= 5? (a < b) : a > b;
	});
	auto print = [](vector<int> myl) {for (auto i = myl.begin(); i != myl.end(); i++) cout << *i << " "; };
	print(l);
	getchar();
}

Output:
5 6 7 8 9 10 11 4 3 2 1 0

In the above example:
To sort function the lambda function is passed as our own comparator.

Advertisements

Project euler problem 20


This problem is very simple one liner in python.

n! means n × (n − 1) × … × 3 × 2 × 1

For example, 10! = 10 × 9 × … × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

import math
print sum([int(x) for x in  str(math.factorial(100))])

Answer: 648

real 0m0.164s
user 0m0.031s
sys 0m0.108s

Here documents in bash


In my day to day work oftentimes I work with C, Bash scripting and Cross compiling for ARM and other interesting stuff. I feel programming is an art so as bash scripting. There are many things we come across after seeing the scripts written by highly experienced bash programmers. One of such concept was a here document.

In simple terms,

here documents can be treated as multiple line input provided to a command in a shell script.

Let us discuss here documents with simple examples:

Example 1:

wc -l << COUNT_LINES
Vasanth Raja
Chittampally
!!
COUNT_LINES

In the above example the start and end of the here document are specified with “COUNT_LINES“. Input to “wc -l” command is the three lines in between the COUNT_LINES. As expected the output to this is “3“.

Example 2:

Oftentimes I see the here documents used in conjunction with cat. This is because when we want to print set of lines to the terminal, this comes in handy. For example

cat << USAGE_HELP

The invoked script name: $0
This invoked script direcotry: `dirname $0`
This is a second line

USAGE_HELP

Few important points are

1. In here documents we can substitute command outputs.

In the above example $0 and `dirname $0` are replaced with the command outputs.

2. All the text in the here document will be printed exactly to the standard output. That means leading tabs, spaces are preserved exactly.

Suppose if you wish to remove the leading tabs from the here document, the same can be achieved in the following manner

cat << – USAGE_HELP

The invoked script name: $0
This invoked script direcotry: `dirname $0`
This is a second line

USAGE_HELP

Just use a ‘-‘ symbol just after the symbol “<<“.

In a nutshell, here documents comes very hand when you want to give multiple line input to a command. Moreover, here documents are simple to use and easy to understand.

vim backspace issue quick fix


vim is one of the extraordinary editors that I’ve ever used. One of the best thing I enjoy is the total customization it offers from fonts to key bindings, backgrounds and a lot more.

Recently I’ve came across backspace not working on vim editor even after the backspace is set in ~/.vimrc.

When I first started using vim I’ve encountered this issue and the quick thing which fixed is the following line.

set backspace=2

you can find more description in the vim tips here.

Even after adding this I’ve found my colleagues facing the same issue. Then the quick fix was to add the following line in your .vimrc

set backspace=indent,eol,start
indent  allow backspacing over autoindent
eol     allow backspacing over line breaks (join lines)
start   allow backspacing over the start of insert; CTRL-W and CTRL-U
        stop once at the start of insert.

The above line has proved proper solution for many. But I’ve seen cases where even after having those lines backspace prints “^?”.

This was rather annoying to many. one other quick fix for this is as follows

stty erase ^?

Run the above command on the shell and try appending the above two lines in your ~/.vimrc as follows

set backspace=2

set backspace=indent,eol,start

Enjoy editing in vim. If you find any other better fix for this issue please leave a comment below. Thanks for reading this post.

Different types of data types


There actually different types of datatypes as the programming languages specify them. Here I’m going to specify four types of them, Almost all predominant languages should have datatypes belonging to the following four kinds of datatypes

1) Statically typed language

2) Dynamically typed language

3) Strongly typed language

4) Weakly typed language

Statically typed language:

In this kind of languages variables should be assigned types at the compile time itself( and fixed at compile time).  All the variables must be used before using them.

ex: Java, C, C++ ect.,

Dynamically typed language

It is exactly opposite to that of statically typed language. The type of the variable is decided at the runtime rather than at compile time.

ex:VBscript, Python

Strongly typed language

These kind of typed language don’t allow you to change the type of a variable once the type is decided(at runtime or at compile time). Once a variable is declared as String in Java during runtime you cannot convert the type of the variable without explicit type conversion.

ex: Python, Java

Weakly typed language

This type of languages are exactly opposite to that of Strongly typed languages, you can change the type of the variable at anytime during the execution of the program.

ex: VBScript

Divide and Conquer method Illustrated


Divide and Conquer is one of the famous algorithmic techniques. It works with the philosophy that divide the whole problem into smaller managable chunks of subproblems and work out these small subproblems there by combining the intermediate partial solutions.

There are many famous examples which use the Divide and Conqure strategy, for example Binary search, Merge sort, Insertion sort, Quick sort etc.,

Let us take a small example of finding minimum and maximum elements in a given array. If we adapt a normal methodology it takes atleast 2*(n-1) comparisions. We can decrease the number of comparisions using this technique which results in [ Ceil(3*n/2)-2 ] comparisions.

The below is the code for finding MIN and MAX of the given array which was compiled and tested using GNU g++compiler.

//Author: Vasanth Raja Chittampally
#include <iostream>

using namespace std;

void findMin(int [],int, int,int &amp;, int &amp;);

int main()

{

int n,min,max;

cout<<"Enter n:";

cin>>n;

int a[n];

for(int i=0;i<n;i++)

{

cout<<"Enter a["<<i<<"]:";

cin>>a[i];

}

findMin(a,0,n-1,min,max);

cout<<"Minimun of the given array is: "<<min<<;endl;

cout<<"Maximum of the gvien arrays is: "<<max<<endl;

return 0;

}

void findMin(int a[], int left, int right, int &amp;min, int &amp;max)

{

if(left==right)

{

min=a[left];

max=a[right];

}

else

{

int mid=(left+right)/2;

findMin(a,left,mid,min,max);

int left_min=min;

int left_max=max;

findMin(a,mid+1,right,min,max);

int right_min=min;

int right_max=max;

if(left_min&lt;right_min)

min=left_min;

else

min=right_min;

if(left_max&gt;right_max)

max=left_max;

else

max=right_max;

}

}

In this example it divides whole array into two equal parts recursively and tries to compare partial solutions to find the minimum and maximum elements.

T(n)=2T(n/2) + 2 —–>(2 comparisions are needed one for minimum and the other of maximum)

.

.

.

.

number of comparisions = [ Ceil(3*n/2)-2 ]

The above number of comparisions can be verified by substituting in T(n)

T(n)=2*[3*n/(2*2) – 2]+2

T(n)=3n/2-2 (hence verfied)

Sorting is easy!!!


One of the most common questions in many interviews is the sorting techniques. There are many sorting techniques, I am going to explain some of them in the coming posts.

We will start off with, the basic and simplest of all the sorting techniques, Bubble sort

Bubble Sort

Method: Bubble sort compares two adjacent elements and swaps if the first element is greater than the second one. After every pass the largest element in that pass bubbles up to the last position.

Example:

suppose the array elements are

5  7  8  3  2

pass1:

5  7 8  3  2  (compare 5 & 7)  (No Exchange)

5  7  8 3  2  (compare 7 & 8 )  (No Exchange)

5  7 8 3 2  (compare 8 & 3)  (Exchange)

5  7 3 8 2 (compare 8 & 2)  (Exchange)

5  7 3  2  8    (End of the pass1, the largest element is in its corresponding position the array)

pass2:

5 7 3 2 8 (compare 5 & 7)  (No Exchange)

5  7 3 2 8 (compare 7 & 3)  (Exchange)

5 3 7 2 8 (compare 7 & 2)  (Exchange)

5  3 2 7 8 (End of the pass2, the largest element in the pass2 is bubbled up to its corresponding position)

pass 3:

5  3 2 7 8 (compare 5 & 3)  (Exchange)

3 5  2 7 8 (compare 5 & 2)  (Exchange)

3  2 5 7 8 (End of the pass3, the largest element in this pass is bubbled up to its corresponding position)

pass 4:

3  2 5 7 8 (compare 3 &2 ) (Exchange)

2 3 5 7 8 (End of the pass4, all elements sorted)

Algorithm

#include<stdio.h>
#include<conio.h>
int main(void)
{
int a[]={1,12,2,11,3},i,j,n=5,temp;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(i=0;i<n;i++)
printf(“%d “,a[i]);
getch();
return 0;
}

compiled on: dev c++,  gcc, Turbo C

Analysis:

Worst Case: O(N2)        Average Case: O(N2)