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

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

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]

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.

Google Code jam Solutions: Problem A. Store Credit

Problem

You receive a credit C at a local store and would like to buy two items. You first walk through the store and create a list L of all available items. From this list you would like to buy two items that add up to the entire value of the credit. The solution you provide will consist of the two integers indicating the positions of the items in your list (smaller number first).

Input

The first line of input gives the number of cases, N. N test cases follow. For each test case there will be:

  • One line containing the value C, the amount of credit you have at the store.
  • One line containing the value I, the number of items in the store.
  • One line containing a space separated list of I integers. Each integer P indicates the price of an item in the store.
  • Each test case will have exactly one solution.

Output

For each test case, output one line containing “Case #x: ” followed by the indices of the two items whose price adds up to the store credit. The lower index should be output first.

Limits

5 ≤ C ≤ 1000
1 ≤ P ≤ 1000

Small dataset

N = 10
3 ≤ I ≤ 100

Large dataset

N = 50
3 ≤ I ≤ 2000

Sample

Input Output
3
100
3
5 75 25
200
7
150 24 79 50 88 345 3
8
8
2 1 9 4 4 56 90 3
Case #1: 2 3
Case #2: 1 4
Case #3: 4 5

C++ Solution:

/*
Author      :   Sreejith Sreekantan
Description :   https://code.google.com/codejam/contest/351101/dashboard#s=p0

*/

#include 
#include 
#include 
#include 

using namespace std;

int main(int argc, char const *argv[])
{

    int numOfTestInstances;
    cin >> numOfTestInstances;
    std::vector itemWeight;
    for (int testInstanceNum = 0; testInstanceNum < numOfTestInstances; ++testInstanceNum)
    {
        int limit;
        cin >> limit;

        int numOfItems;
        cin >> numOfItems;

        itemWeight.clear();
        itemWeight.reserve(numOfItems);

        for (int itemNum = 0; itemNum < numOfItems; ++itemNum)
        {
            cin >> itemWeight[itemNum];
        }

        cout << "Case #" << testInstanceNum + 1 << ": ";

        for (int i = 0; i < numOfItems; ++i)
        {
            for (int j = i + 1; j < numOfItems; ++j)
            {
                if (itemWeight[i] > limit)
                {
                    break;
                }
                if (itemWeight[j] > limit)
                {
                    continue;
                }
                if (itemWeight[i] + itemWeight[j] == limit)
                {
                    if (i < j)
                    {
                        cout << i + 1 << " " << j + 1 << endl;
                    }
                    else
                    {
                        cout << j + 1 << " " << i + 1 << endl;
                    }
                }
            }
        }

    }
    return 0;
}

Python Solution:

#! /usr/bin/python

numOfInstances = int(raw_input())

for x in xrange(1,numOfInstances+1):
    limit = int(raw_input())
    numOfItems = int(raw_input())
    d = dict()
    items = [int(x) for x in raw_input().split()]
    for y in xrange(1,numOfItems+1):
        if items[y-1] not in d:
            d[items[y-1]] = set() 
        d[items[y-1]].add(y)

     print d

    for x in d.keys():
        if x <= limit:
            index = d[x].pop()
            if (limit-x) in d and len(d[limit-x])>0:
                index2=d[limit-x].pop()
                d[limit-x].add(index2)
                print min(index, index2), max(index, index2)
            d[x].add(index)