## Puzzle : Count possible combinations of coins

Q. Given a sum of value S and infinite supply of coins each of value C = { C1, C2, .. , Cn}, how many ways can you make the change? The order of coins doesn’t matter.

For example, for S = 5 and S = {1,2}, there are three solutions:  (1, 1, 1, 1, 1), (1, 1, 1, 2), (1, 2, 2) . So output should be 3. For S = 10 and C = {2, 5, 3, 6}, there are five solutions: (2,2,2,2,2), (2,2,3,3), (2,2,6), (2,3,5) and (5,5). So the output should be 5.

Yes, I agree; this question is hard. But can we simplify it to come up with a solution that will solve this tough one!

What if C was { 1 } and S was 10? Number of combinations possible is 1; Ten times 1 is the only way to form the sum 10. That was quick and easy, right? 😀

Lets take it to next level. This time, lets try with more coins: 1 and 2 and same sum: 10. Yes, many combinations flashed my mind too. Lets cross this bridge one step at a time. Lets first list out all the combinations How do I convert this to a program!!! Lets walk through the process that happened in my brain when I wrote down those combinations.

1. I took zero 2 and tried to form the remaining sum with all 1. I could use ten 1 to form the sum.
2. I took one 2 and tried to form the rest of the sum with all 1.
3. Took three 2 and got six 1
4. Took four 2 and got four 1
5. Took five 2 and got two 1
6. Took six 2 and got zero 1

Good question (if this already came up in your mind)! what if I tried to find the count of 2 by giving values to number of 1. Lets work it out. Both cases, I did nothing but iterate from 0 till a number which when multiplied with the chosen coin (2 in first case and 1 in second case) is larger than sum. In every step, I tried to form the remaining “sum” with rest of the denominations.

We encountered more steps than in the previous one but at the end it turned out to be the same number of combinations. Obvious! Trying out both ways helped us discover an optimization: Larger Denominations First. Lets shorten it to LDF 😉

So lets transform our knowledge to algorithm now. For that, lets set some terminologies.

Terminologies:

1. D : All denominations(coins) in ascending order. Why sorting? Sorting is just to implement LDF (Larger Denominations First) and is optional.
2. D[i] : value of i-th coin . Assume that index starts with 1.
3. S : sum to be formed.
4. F(i, S) : Returns the maximum combinations possible with first ‘i’ denominations to form sum ‘S’
5. F(i, n, S) : Returns the maximum combinations possible with first ‘i’ denominations using i-th denomination ‘n’ times. This function is to find the maximum combinations possible with remaining denominations while keeping the count of i-th denomination to a particular value.

For our case where D = { 1, 2 } and S = 10:

• F(2, 10) should give us 6 since there are 6 different ways to form a sum of 10 with 1 and 2
• F(1, 10) should give 1.
• F(2, 0, 10) should give 1
• F(2, 1, 10) should give 1
• F(2, 2, 10) should give 1
• F(2, 3, 10) should give 1
• F(2, 4, 10) should give 1
• F(2, 5, 10) should give 1
• F(2, 6, 10) should give 0
• F(2, 7, 10) should give 0

Lets try to define F(i, S) in terms of F(i, n, S). This is nothing but mathematical representation of a for-loop with variable x iterating from 0 to (S/D[i]),  beyond which the x*D[i] will be greater than S.

Now we should define F(i, n, S). As stated before, F(i, n, S) is the maximum number of combinations possible with D[i] used ‘n’ times. With the number of D[i] fixed to n, we just need to iterate through the rest of the coins. So it can be defined as It is a recursive function which reduces the sum by D[i]*n and finds the maximum combinations with rest of the coins. But what should it do when it reaches the last denomination? It should be able to divide the sum without any remainder; if not, there is no possible combination with the chosen numbers. Simple! Now, lets try to apply our new algorithm.

```F(2, 10) = F(2, 0, 10) +
F(2, 1, 10) +
F(2, 2, 10) +
F(2, 3, 10) +
F(2, 4, 10) +
F(2, 5, 10)
= F(1, 0, 10) + F(1, 2, 10) + F(1, 3, 10) + F(1, 4, 10) + F(1, 5, 10) + F(1, 6, 10) + F(1, 7, 10) ++ F(1, 8, 10) + F(1, 9, 10) + F(1, 10, 10) +           F(1, 0, 8) + F(1, 1, 8) + F(1, 2, 8) + F(1, 3, 8) + F(1, 4, 8) + F(1, 5, 8) + F(1, 6, 8) + F(1, 7, 8) ++ F(1, 8, 8) +
F(1, 0, 8) + F(1, 1, 8) + F(1, 2, 8) + F(1, 3, 8) + F(1, 4, 8) + F(1, 5, 8) + F(1, 6, 8) + F(1, 7, 8) ++ F(1, 8, 8) +
F(1, 0, 6) + F(1, 1, 6) + F(1, 2, 6) + F(1, 3, 6) + F(1, 4, 6) + F(1, 5, 6) + F(1, 6, 6) +
F(1, 0, 4) + F(1, 1, 4) + F(1, 2, 4) + F(1, 3, 4) + F(1, 4, 4) +
F(1, 0, 2) + F(1, 1, 2) + F(1, 2, 2) +
F(1, 0, 0)
= 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 1 +
0 + 0 + 0 + 0 + 0 + 0 + 0 + 1 +
0 + 0 + 0 + 0 + 0 + 1 +
0 + 0 + 0 + 1 +
0 + 1 +
1
= 6

```

That worked!

Lets write some Java now..

```package fun.puzzles;

import java.util.Arrays;
import java.util.List;

public class CoinCombinationsPuzzle {

private final List<Integer> coins;

public CoinCombinationsPuzzle(List<Integer> coins) {
this.coins = coins;
}

public int maximumPossibleCombinations(int numOfCoins, Integer sum) {
coins.sort(null);
int maxIteration = sum/coins.get(numOfCoins);
int maxPossibleCombinations = 0;
for (int i = 0; i <= maxIteration; i++) {
maxPossibleCombinations += maximumPossibleCombinations(numOfCoins, i, sum);
}
return maxPossibleCombinations;
}

public int maximumPossibleCombinations(int numOfCoins, int count, Integer sum) {
// safety check
if (numOfCoins < 0) { return 0;    }
if (numOfCoins < 1) {
if (count * coins.get(numOfCoins) == sum) {
return 1;
}
else {
return 0;
}
}
// Reduce the fixed denomination from sum
sum -= (count * coins.get(numOfCoins));
int maxIteration = sum/coins.get(numOfCoins-1);
int maxPossibleCombinations = 0;
for (int i = 0; i <= maxIteration; i++) {
maxPossibleCombinations += maximumPossibleCombinations(numOfCoins-1, i, sum);
}
return maxPossibleCombinations;
}

public int maximumPossibleCombinations(Integer sum) {
return maximumPossibleCombinations(coins.size()-1, sum);
}

public void printMaximumPossibleCombinations(Integer sum) {
System.out.printf("Coins: %-50s Sum: %-5d MaximumPossibleCombinations: %-5d\n",
coins, sum, maximumPossibleCombinations(coins.size()-1, sum));
}

public static void main(String[] args) {
List<Integer> coins;
CoinCombinationsPuzzle ccp;

coins = Arrays.asList(1, 2);
ccp = new CoinCombinationsPuzzle(coins);
ccp.printMaximumPossibleCombinations(5);

coins = Arrays.asList(1, 2);
ccp = new CoinCombinationsPuzzle(coins);
ccp.printMaximumPossibleCombinations(10);

coins = Arrays.asList(1, 2, 3);
ccp = new CoinCombinationsPuzzle(coins);
ccp.printMaximumPossibleCombinations(100);

coins = Arrays.asList(1, 2, 5, 10);
ccp = new CoinCombinationsPuzzle(coins);
ccp.printMaximumPossibleCombinations(1074);
}
}```

Output: This solution can still be optimized by caching the results of recursive method: maximumPossibleCombinations(int numOfCoins, int count, Integer sum)

## Python CGI in Apache httpd server

Pre-requisite: Working Apache Server.

In httpd-vhosts.conf:

Add below content inside <VirtualHost …>

```ScriptAlias /cgi-bin/ "/cgi-bin/"
<directory "<httpd-installed-path="">/cgi-bin/">
AllowOverride None
Require all granted
```

Now create a new file ‘test.py’ in /cgi-bin/  with content:

```#!/usr/bin/env python

import cgi
cgi.test()```

Make sure the below line is not commented in httpd.conf

`LoadModule cgi_module modules/mod_cgi.so`

Start/Restart apache server.

You can verify the loaded cgi module using the command:

`sudo [path/]apachectl -M | grep cgi`

Try below url in web-browser:

```http://<ip/hostname>:/cgi-bin/test.py

eg:
http://localhost:1025/cgi-bin/test.py
http://localhost:80/cgi-bin/test.py```

You will get a page with details on current working directory, command line arguments, etc..

## Configure VMs which talk to each other.

Hi,

This blog will walk you through setting up three different fedora VMs : ram, daisy and rincy; who will be talking to each other and also with the host machine; very soon…

Pre-requirements:

• See mine below. Name doesn’t matter much. You may use your own. My VMs run fedora OS. Depending on your OS, you may have to Google a little more on how to set different configurations. I am sure, Google will be happy to help you. A little help with my vocabulary:

```host machine : machine which runs VirtualBox
VM           : Virtual Machine```

First we need a Host-Only Adapter. This needs to be created in the Virtual Box and not in any particular VMs. So lets do that first.

Go to the preference of VirtualBox. Mine is a Mac. Don’t confuse with the screenshots if you are using another host OS. Go to the “Network” tab and choose “Host-only Networks” sub-tab and create a new Adapter by clicking on the green plus sign you see on the right side of the window. There comes the new adapter “vboxnet0” Double-click “vboxnet0” or click on the screw-driver icon on the right side of the window after highlighting “vboxnet0”  to see it’s settings. Below are the default values and we are fine with it unless you really want to change it. You can see the “Lower Address Bound and “Upper Address Bound”. We can choose IP from this range for our machines. Press “OK” if you made some change else “OK” or “Cancel” as you like and we have a working “Host-only Adapter” now.

Now we should connect it to all three VMs.

Highlight a VM and click “Settings” (on the top of the window between “New” and “Show”) Select the “Network” tab from the window which appeared. Leave “Adapter 1” as we need it to be Attached to “NAT” for accessing internet via host machine. Select “Adapter 2” and select “Host-only Adapter” option from the drop down menu of “Attached to:”. Ofcourse the value for “Name:” is our newly created “vboxnet0”. Set “Promiscuous Mode:” to “Allow All” or “Allow VMs”. Putting it to “Deny” will stop any communication via this Adapter. Hope you too don’t want that as our intention is otherwise. Now we need to boot into the VMs and assign a static-IP for each.

I will start will “ram” VM.

In RedHat/Fedora we can use “system-config-network” for this purpose.

Install it using the below command. You should have root privilege or sudo privilege for this. Once installed, run “system-config-network” command to start assigning the static IP. That will take you to something like this: Highlight “Device Configuration” from it using arrow keys and press “Enter/Return” key. We need to edit “vboxnet0”, so highlight it. If you don’t see that, you may highlight “” and press Enter.

Make sure your settings match the below ones. You may choose any IP from the range we saw earlier. I go for 192.168.56.[101-103]. Need not be adjacent ones.

Use tab and arrow keys to highlight the “OK” button and press Enter after the changes. Then “Save&Quit” With this, we have assigned static-IP 192.168.56.101 to VM: ram.

Now lets do a small trick to ease our path ahead; a small DNS resolution.

Lets use the names ram, daisy and rincy instead of the IPs.

For that, open the /etc/hosts file.

Like wise, assign 192.168.56.102 to daisy and 192.168.56.103 to rincy and update the /etc/hosts file.

Now reboot all the VMs to be on the safer side. and try the below commands in all three VMs and host machine.

```ping -c 3 ram
ping -c 3 daisy
ping -c 3 rincy
```

You will get the below output which means rincy, ram and daisy started talking to each other.. Try from the host machine and you will see Big-Daddy can talk to his children now.. So there comes an end to this blog..

## LDAP_CONTROL_RELAX undeclared while installing python-ldap

ERROR:

Modules/constants.c: In function ‘LDAPinit_constants’:
Modules/constants.c:158: error: ‘LDAP_OPT_DIAGNOSTIC_MESSAGE’ undeclared (first use in this function)
Modules/constants.c:158: error: (Each undeclared identifier is reported only once
Modules/constants.c:158: error: for each function it appears in.)
Modules/constants.c:380: error: ‘LDAP_CONTROL_RELAX’ undeclared (first use in this function)
error: command ‘gcc’ failed with exit status 1

Solution:
Install openldap24-libs & openldap24-libs-devel :
sudo yum install openldap24-libs-devel
sudo yum install openldap24-libs

Run the below commands and get the unique list of directories from the output:
Add those folders to setup.cfg file in the below section:
[_ldap]
library_dirs = /opt/openldap-RE24/lib /usr/lib
include_dirs = /opt/openldap-RE24/include /usr/include/sasl /usr/include

Now run the installation command:
python setup.py install

If you get below error while starting nginx

error:

nginx/sbin/nginx: error while loading shared libraries: libpcre.so.1: cannot open shared object file: No such file or directory

nginx couldn’t find the library by itself.
Specify the path of libpcre.so.1 in LD_LIBRARY_PATH and nginx will work fine

How to do specify the path?

`export LD_LIBRARY_PATH=\$LD_LIBRARY_PATH:<absolute-path-of-libpcre.so.1>`

## Transform A,B,…AA,AB,.. to 1,2,..27,28,..

NOTE: Below code is Python 3.

```base = 26
def transform(row):
res = []
for field in [tmp.strip() for tmp in row.split(',')]:
ival = 0
power = 0
for c in field[::-1]:
ival += pow(base,power)*(ord(c)-ord('A')+1)
power += 1
res.append(ival)
return res

print(transform("A, B, Z, AA, AB, AAA"))

```

Output:

```[1, 2, 26, 27, 28, 703]
```

## apachectl status – How to solve lynx: command not found

apachectl status” will not work if you don’t have lynx ; text-based web browser.

You realize that when you get below message while using the command.

```Error

Install the lynx and tell it to Apache httpd, he will surely understand.

Download the lynx from here. Change your working directory to the extracted folder and run the command:

```./configure --prefix=<path-to-install-lynx>
make
make install```

During lynx installation, it may stop with an error:

`configure: error: No curses header-files found`

Run the below command before proceeding:

`sudo yum search ncurses-devel`

Now it’s time to tell httpd about lynx.

In apachectl file (either in bin or conf directory), change the line starting with LYNX=”lynx -dump” to LYNX=”<lynx-installed-path>/lynx -dump”

apachectl status will start working..

During Apache httpd installation if you get below error, that means Apache Portable Run-time environment was not found or not installed.

```checking for APR... no

and/or

```checking for APR-util... no

So install APR and APR-util and give httpd those paths. Httpd will be happy to run for you after that… 🙂

Go further if you want to know how to install APR.

Then extract those to separate folders.

First change to the extract APR directory and install it. (Tip: cd command to change directory)

```sudo ./configure --prefix=<apr-path>

sudo make

sudo make install```

So you have a working APR. Next is APR-util.

Change to the extract APR-Util directory and install it. (Tip: cd command to change directory)

```sudo ./configure --prefix=<apr-util-path> --with-prefix=<apr-path>

sudo make

sudo make instal```

Install zlib packages with the command (optional; you can turn this off at your will):

`yum install zlib zlib-devel`

Apart from APR and APR-Util, you may need to install pcre too. So download it from here first.

Change to the directory and use the below commands to install.

```sudo ./configure --prefix=<pcre-path>

sudo make

sudo make install```

Now lets make httpd understand that we have a working pcre, APR and APR-util.

`./configure --enable-file-cache --enable-cache --enable-disk-cache --enable-mem-cache --enable-deflate --enable-expires --enable-headers --enable-usertrack --enable-cgi --enable-vhost-alias --enable-rewrite --enable-so --prefix=<httpd-path> --with-apr=<apr-path> --with-apr-util=<apr-util-path> --with-pcre=<pcre-path>`

# Rest is history make make install

## Change the Java (JVM) used by tomcat.

Enterprise systems will have different versions of Java installed in it. A system administrator may have to set up Tomcat to use a particular one out of it. By default Tomcat uses the OS default; ie. the one installed into OS path. So how can we make it run with another version of Java.

This is easily achieved using the below commands(Open a terminal and run the below commands, don’t close it.):

`export JAVA_HOME=<path-to-java>`

or

`export JRE_HOME=<path-to-java>`

Run the start-up script from the same terminal and you will see from the logs that Tomcat picked up the Java from the path you set.

Notes:

JRE_HOME is set to JAVA_HOME if not set. So setting any of these variables suffice.