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

1464_1

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.

1464_2

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).

1464_3

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

1464_4

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!

1464_5

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:

1464_6

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/">
         Options Indexes FollowSymLinks ExecCGI
         AddHandler cgi-script .cgi .py
         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:

  • 3VMs already setup inVirtualBox.
    • 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.

Screen Shot 2015-03-15 at 9.29.44 pm

 

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.

Screen Shot 2015-03-15 at 8.49.51 pmGo 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”

Screen Shot 2015-03-15 at 8.50.23 pm

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.

Screen Shot 2015-03-15 at 8.51.04 pm

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”)

Screen Shot 2015-03-15 at 8.51.41 pm

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”.

Screen Shot 2015-03-15 at 8.52.14 pm

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.

Screen Shot 2015-03-15 at 8.52.39 pm

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.Screen Shot 2015-03-15 at 9.18.47 pmOnce installed, run “system-config-network” command to start assigning the static IP.

Screen Shot 2015-03-15 at 9.19.24 pmThat will take you to something like this:

Screen Shot 2015-03-15 at 9.19.34 pm

Highlight “Device Configuration” from it using arrow keys and press “Enter/Return” key.

Screen Shot 2015-03-15 at 9.19.53 pmWe 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.

Screen Shot 2015-03-15 at 9.20.03 pmClick “Save”.

Screen Shot 2015-03-15 at 9.20.26 pm

Then “Save&Quit”

Screen Shot 2015-03-15 at 9.20.37 pm

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.

Screen Shot 2015-03-15 at 9.21.30 pmAnd add below lines to it.Screen Shot 2015-03-15 at 9.21.51 pm

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..

Screen Shot 2015-03-15 at 9.23.12 pmTry from the host machine and you will see Big-Daddy can talk to his children now..

Screen Shot 2015-03-15 at 9.24.52 pmSo 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

nginx: error while loading shared libraries: libpcre.so.1

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]