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)

 

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]

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)


Google Code jam Solutions: Problem B. Reverse Words

Problem

Given a list of space separated words, reverse the order of the words. Each line of text contains L letters and W words. A line will only consist of letters and space characters. There will be exactly one space character between each pair of consecutive words.

Input

The first line of input gives the number of cases, N.
N test cases follow. For each test case there will a line of letters and space characters indicating a list of space separated words. Spaces will not appear at the start or end of a line.

Output

For each test case, output one line containing “Case #x: ” followed by the list of words in reverse order.

Limits

Small dataset

N = 5
1 ≤ L ≤ 25

Large dataset

N = 100
1 ≤ L ≤ 1000

Sample

Input Output
3
this is a test
foobar
all your base
Case #1: test a is this
Case #2: foobar
Case #3: base your all

C++ Solution:

/*
    Author      :   Sreejith Sreekantan
    Description :   Problem B. Reverse Words https://code.google.com/codejam/contest/351101/dashboard#s=p1
                    
*/

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;


int main(int argc, char const *argv[])
{
    
    int numOfTestInstances;
    cin >> numOfTestInstances;
    
    for (int testInstanceNum = 0; testInstanceNum < numOfTestInstances; ++testInstanceNum)
    {
        istringstream in;
        string s;
        cin >> ws;
        getline(cin ,s);
        replace(s.begin(), s.end(), ' ', '\n');
        in.str(s);
        
        stack stack_s_rev;

        while (in >> s)
        {
            stack_s_rev.push(s);
        }
        cout << "case #" << testInstanceNum+1 << ": ";
        while(!stack_s_rev.empty())
        {
            cout << stack_s_rev.top() << " ";
            stack_s_rev.pop();
        }
        cout << endl;

    }
    return 0;
}


Google Code jam Solutions: Problem A. Alien Language

Problem

After years of study, scientists at Google Labs have discovered an alien language transmitted from a faraway planet. The alien language is very unique in that every word consists of exactly L lowercase letters. Also, there are exactly D words in this language.

Once the dictionary of all the words in the alien language was built, the next breakthrough was to discover that the aliens have been transmitting messages to Earth for the past decade. Unfortunately, these signals are weakened due to the distance between our two planets and some of the words may be misinterpreted. In order to help them decipher these messages, the scientists have asked you to devise an algorithm that will determine the number of possible interpretations for a given pattern.

A pattern consists of exactly L tokens. Each token is either a single lowercase letter (the scientists are very sure that this is the letter) or a group of unique lowercase letters surrounded by parenthesis ( and ). For example: (ab)d(dc) means the first letter is either a or b, the second letter is definitely d and the last letter is either d or c. Therefore, the pattern (ab)d(dc) can stand for either one of these 4 possibilities: add, adc, bdd, bdc.

Input

The first line of input contains 3 integers, L, D and N separated by a space. D lines follow, each containing one word of length L. These are the words that are known to exist in the alien language. N test cases then follow, each on its own line and each consisting of a pattern as described above. You may assume that all known words provided are unique.

Output

For each test case, output

Case #X: K

where X is the test case number, starting from 1, and K indicates how many words in the alien language match the pattern.

Limits

 

Small dataset

1 ≤ L ≤ 10
1 ≤ D ≤ 25
1 ≤ N ≤ 10

Large dataset

1 ≤ L ≤ 15
1 ≤ D ≤ 5000
1 ≤ N ≤ 500

Sample

Input Output
3 5 4
abc
bca
dac
dbc
cba
(ab)(bc)(ca)
abc
(abc)(abc)(abc)
(zyx)bc
Case #1: 2
Case #2: 1
Case #3: 3
Case #4: 0

C++ Solution:

/*
    Author      :   Sreejith Sreekantan
    Description :   Problem A. Alien Language (https://code.google.com/codejam/contest/90101/dashboard#s=p0)

*/

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;


#define rep(v,N) for(int v=0; v<n; v++)="" #define="" <span="" class="hiddenSpellError" pre="define " data-mce-bogus="1">rep2(v,M,N) for(int v=M; v<n; v++)="" #define="" for(v,c)="" for(__typeof(c.begin())="" v="C.begin();" v!="C.end();" ++v)="" vi="" std::vector<int="">
#define vll std::vector
#define pb push_back
#define Sort(C) std::sort(C.begin(), C.end())
#define RSort(C) std::sort(C.rbegin(), C.rend())
#define Copy(ans,out) copy(ans.begin(),ans.end(), ostream_iterator<__typeof(ans[0])>(out, " "))

// #define SMALL
#define LARGE

int main(int argc, char const *argv[])
{
    freopen("a.in", "rt", stdin);
    // freopen("a.out", "wt", stdout);
#ifdef SMALL
    freopen("as.in", "rt", stdin);
    freopen("as.out", "wt", stdout);
#endif

#ifdef LARGE
    freopen("al.in", "rt", stdin);
    freopen("al.out", "wt", stdout);
#endif

    unsigned int L, D, N;
    cin >> L >> D >> N;

    std::vector dict(D);
    std::vector inp(D);
    rep(i, D)
    {
        cin >> dict[i];
    }
    rep(i, N)
    {
        cin >> inp[i];
        replace(inp[i].begin(), inp[i].end(), '(', '[');
        replace(inp[i].begin(), inp[i].end(), ')', ']');
        // cout << inp[i]<< endl;
        int c = 0;
        rep(j, D)
        {
            if (regex_match(dict[j], regex(inp[i])) ) c++;
        }
        cout << "Case #" << i+1 << ": " << c << endl;
        
    }
    return 0;
}

Brain Teaser

T : Number of test cases

M: value of M

N: Number of strings

For each string, ascii value of each character of the string is raised to M and multiplied together. For each test case the sum of above values  is ODD or EVEN

Input:

1

10    2

ac ab

Output:

ODD

 

TIP: Challenge lies in finding the solution without doing all the mathematical operations mentioned in the question. (yes, also called optimizing..!)

 

 

Solution:

#!/usr/bin/python

T = int(raw_input())
while T>0:
    T = T - 1
    tmp = raw_input()
    M = int(tmp.split()[0])
    K = int(tmp.split()[1])
    tmp = raw_input()
    final_odd = False
    for s in tmp.split():
        odd = None
        for i in s:
            if ord(i)%2==0:        # the power is even
                odd = False
            else:                # the power is odd
                if odd==None:            # if odd is True, odd*odd=odd
                    odd = True
        # odd + odd = even
        # odd + even = odd
        # even + even = even
        if final_odd != odd:
            final_odd = True
        else:
            final_odd = False
    if final_odd:
        print "ODD"
    else:
        print "EVEN"

Find the biggest black square from an N*N matrix of black or white squares

Question:

Find the biggest black square from an N*N matrix of squares. 1 means it’s black, 0 means it’s white. Output should be the list of squares which forms the largest black square.

Input     : ‘{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#1#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}’

Output    :    {(3#0,3#1,3#2,3#3),(4#0,4#1,4#2,4#3),(5#0,5#1,5#2,5#3),(6#0,6#1,6#2,6#3)}

 

Solution(Python):

    # Author            :        Sreejith Sreekantan
    # Description        :        

    #                         Find the biggest black square from an N*N matrix of squares. 1 means it's black, 0 means it's white
    #                         Input     : '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#1#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
    #                         Output    :    {(3#0,3#1,3#2,3#3),(4#0,4#1,4#2,4#3),(5#0,5#1,5#2,5#3),(6#0,6#1,6#2,6#3)}
    

#!/usr/bin/python

def largestSquareAt(sq, i, j, k=1):
    if not ( i+k<len(sq) and="" j+k<len(sq[i])="" ):=""   =""    =""  return="" 0=""  for="" x="" in="" range(0,k):=""  if="" sq[i+x][j+k-1]="='0':" y="" sq[i+k-1][j+y]="='0':" 1="" +="" largestsquareat(sq,="" i,="" j,="" k+1)  =""  ="" def="" biggestsquare(input1):="" len(input1)="=0" or="" not="" (="" input1.count('{')="=input1.count('}')" )="" :="" ''=""  i="str(input1)"  j="i" for="" j]=""  resx="-1"  rexy="-1"  ressize="-1"  res="[]" range(0,len(j)):=""  res.append([])="" range(0,len(j[x])):=""  res[x].append(largestsquareat(j,="" x,="" y))="" ressize<res[x][y]:=""  resy="y"  resstring="" ressize="">0:                                
        resstring = "{"
        for x in range(resx,resx+ressize):
            if x>resx:
                resstring += ","
            resstring += "("
            for y in range(resy,resy+ressize):
                if y>resy:
                    resstring += ","
                resstring += (str(x)+"#"+str(y))
            resstring += ")"    
        resstring += "}"
    
    return resstring  

input = '{0#1#1#0,0#1#1#1,0#1#1#1,1#1#1#1}'
input1 = '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#1#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
input2 = '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#0#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
input3= '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,0#1#0#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
input4 = '{0#0#0#0,0#0#0#0,0#0#0#0,0#0#0#0}'
print biggestSquare('')    
print biggestSquare(input1)    
print biggestSquare(input2)        
print biggestSquare(input3)        
print biggestSquare(input4)