## 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:**

**Unnamed function object****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.

## Project euler 31: Coin sums

https://projecteuler.net/problem=31

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

Solution:

This a very nice Dynamic programming question:

def noOfCoins(coins, n): noOfWays= [x * 0 for x in range(n + 1)] noOfWays[0] = 1 for i in range(len(coins)): for j in range(coins[i], n + 1): noOfWays[j] = noOfWays[j] + noOfWays[j - coins[i]] return noOfWays[n] if __name__ == '__main__': coins = [1,2,5,10,20,50,100,200] n = 200 print(noOfCoins(coins, n))

Answer: 73682

Time Complexity: O(number of available coins * n) ~ o(N)

Space Complexity: O(N)

## Project euler 30: Digit fifth powers

https://projecteuler.net/problem=30

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1^4 + 6^4 + 3^4 + 4^4

8208 = 8^4 + 2^4 + 0^4 + 8^4

9474 = 9^4 + 4^4 + 7^4 + 4^4

As 1 = 1^4 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Solution:

It is straight forward answer.

def powrs(n, pw): prod = 1 for i in range(0, pw): prod *= n return int(prod) def sumdigitpows(n, pw): sum = 0 orig = n while (n > 0): sum +=powrs(int(n % 10), pw) n /= 10 if sum > orig: return 0 return int(sum) def fifthpowers(): pw = 5 sum = 0 for i in range(1000, 10000000): if i == sumdigitpows(i, pw): sum += i print (i) print ("Answr: %s" % str(sum)) if __name__ == '__main__': fifthpowers()

Answr: 443839

## Project euler 29: Distinct powers

Consider all integer combinations of *a*^{b} for 2 ≤ *a* ≤ 5 and 2 ≤ *b* ≤ 5:

2

^{2}=4, 2^{3}=8, 2^{4}=16, 2^{5}=32

3^{2}=9, 3^{3}=27, 3^{4}=81, 3^{5}=243

4^{2}=16, 4^{3}=64, 4^{4}=256, 4^{5}=1024

5^{2}=25, 5^{3}=125, 5^{4}=625, 5^{5}=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by *a*^{b} for 2 ≤ *a* ≤ 100 and 2 ≤ *b* ≤ 100?

def distpowers(n): a={2} # initialize the set d={} # map for total number of elements for each power s=[0 for x in range(n + 1)] for i in range(1, 8): for j in range(2, n + 1): a.add(i * j) d[i]=len(a) tot = 0 for i in range (2, n + 1): if s[i] == 0: prod = i power = 0 while prod <= n: s[prod] = 1 prod *= i power += 1 tot += d[power] print (tot) if __name__ == '__main__': distpowers(100)

Time complexity O(8 * n) ~ O(n)

Space complexity O(n)

Answer: 9183

## Project euler 28: Number spiral diagonals

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

**21** 22 23 24 **25**

20 **7** 8 **9** 10

19 6 **1** 2 11

18 **5** 4 **3** 12

**17** 16 15 14 **13**

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

def diag(n): sum = 0 for i in range(0, int(n / 2) + 1): sum += (2 * i + 1) * (2 * i + 1) sum += (4 * i * i + 1) sum += (2 * i + 1) * (2 * i + 1) - 2 * i sum += (2 * i + 1) * (2 * i + 1) - 6 * i return sum - 3 print (diag(1001))

Answer: 669171001

Time complexity: O(4 * n / 2) ~ O(n)

Space complexity: O(1)

## Project euler 27: Quadratic primes

Euler discovered the remarkable quadratic formula:

*n*² + *n* + 41

It turns out that the formula will produce 40 primes for the consecutive values *n* = 0 to 39. However, when *n* = 40, 40^{2} + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when *n* = 41, 41² + 41 + 41 is clearly divisible by 41.

The incredible formula *n*² − 79*n* + 1601 was discovered, which produces 80 primes for the consecutive values *n* = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n² +an+b, where |a| < 1000 and |b| < 1000where |n| is the modulus/absolute value ofn

e.g. |11| = 11 and |−4| = 4

Find the product of the coefficients, *a* and *b*, for the quadratic expression that produces the maximum number of primes for consecutive values of *n*, starting with *n* = 0.

**Solution:**

It is self explanatory.

#include <iostream> #include <vector> #include <cmath> using namespace std; #define MAX 100000 vector <long> prime(0); bool * seive_helper(bool primes[], int range) { for (int i = 3; i <= range / 2 ; ++i, ++i) { for(int j = i * 3; j <= range ; j += (i << 1)) { primes[j] = true; } } } void seive(int range) { int count = 0; bool primes[MAX] = {false}; for(int i = 4; i <= range; ++i, ++i) { primes[i] = true; } seive_helper(primes, range); for(int i = 2; i <= range; ++i) { if (!primes[i]) { prime.push_back(i); } } } bool isPrime(long num, int range) { int i = 0; while (i <= range) { if (num == prime[i]) return true; else if (num < prime[i]) return false; i++; } return false; } int main() { long long sum = 0; int max_count = 0; int max_a; int max_b; seive(10000); for (int i = -1000; i <= 1000; i++) { for(int j = -1000; j <= 1000; j++) { int n = 0; int count = 0; while(isPrime(n * n + i * n + j, 10000)) { count++; n++; } if (count > max_count) { max_count = count; max_a = i; max_b = j; } } } cout<<"max_a: "<<max_a<<endl; cout<<"max_b: "<<max_b<<endl; cout<<"max_count: "<<max_count<<endl; cout<<"Answer: "<<(max_a * max_b)<<endl; return 0; }

max_a: -61

max_b: 971

max_count: 71

Answer: -59231

real 0m1.584s

user 0m1.528s

sys 0m0.062s

## Project euler 26: Reciprocal cycles

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2 = 0.5

1/3 = 0.(3)

1/4 = 0.25

1/5 = 0.2

1/6 = 0.1(6)

1/7 = 0.(142857)

1/8 = 0.125

1/9 = 0.(1)

1/10 = 0.1

Where 0.1(6) means 0.166666…, and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

**Solution:**

I solved this problem in a bruteforce manner. Divisor keeps incrementing from 2 to 1000.

We store the reminder instead of quotient in an array. When the same reminder repeats we know there is a recurring cycle. The maximum of that recurring cycle is the answer.

#include <iostream> #include <stdio.h> using namespace std; int max(int a, int b) { return (a > b) ? a: b; } int remArray[2000]; int divideByOne(long divisor) { int term = 0; long mul = 1; for(int i = 0; i < 2000; i++) remArray[i] = 0; while (mul != 0 && term < 2000) { term++; mul *= 10; mul %= divisor; if (remArray[mul] != 0) break; remArray[mul] = term; } return term; } int main() { int max_val = 0; for(int i = 2; i <= 1000; i++) max_val = max(max_val, divideByOne(i)); cout<<max_val; return 0; }

time ./a.exe

Answer: 983

real 0m0.087s

user 0m0.030s

sys 0m0.046s