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

## ActiveMQ Producer and Consumer in Java

Use this post as a reference for those who work with Apache ActiveMQ middle-ware.

Use this link to get through the installation, configuration and starting of ActiveMQ: Getting Started

You should have Java installed in your machine.I am using ActiveMQ 5.9.0.

Once you bring up the ActiveMQ instance, provided you left all the configurations as default,ActiveMQ will support TCP connections at port 61616. We are going to make use of this port to make our Producer and Consumer classes connect to ActiveMQ.

Disclaimer: ActiveMQ instance and Producer and Consumer programs run on the same machine. Therefore programs can use the URL tcp://localhost:61616 to connect to the ActiveMQ instance.

Producer Class is nothing but a java class which will connect to ActiveMQ and send a message to it specifying the queue to which the message should be en-queued.

Consumer Class is the one which connects to ActiveMQ to retrieve a message from a particular queue.

Lets get to the code now. I used Eclipse IDE to create this java project.
Producer Class(AMQProducer):

```import java.sql.Timestamp;
import java.util.Date;

import javax.jms.*;

import org.apache.activemq.ActiveMQConnectionFactory;

public class AMQProducer implements Runnable{
// Use the same factory for all the producer threads.
static ActiveMQConnectionFactory activeMQConnectionFactory =
new ActiveMQConnectionFactory("tcp://localhost:61616");
@Override
public void run() {
try {
// Create a JMS connection from the ActiveMQ server
Connection connection = activeMQConnectionFactory.createConnection();
connection.start();

// Create a session to send message
Session session = connection.createSession(false, Session.AUTO_ACKNOWLEDGE);

// destination represents the message queue to which the message is en-queued
Destination destination = session.createQueue("HelloMoto");

// MessageProducer is used to send messages
// Refer http://docs.oracle.com/javaee/1.4/api/javax/jms/MessageProducer.html for more
MessageProducer messageProducer = session.createProducer(destination);

// Sets the producer's default delivery mode.
messageProducer.setDeliveryMode(DeliveryMode.NON_PERSISTENT);

// Message defines the message header and the acknowledge method used for all JMS messages
String text = "Hello Motorola from producer " + Thread.currentThread().hashCode() + "..."
+ new Timestamp((new Date()).getTime());
Message message = session.createTextMessage(text);

messageProducer.send(message);

") : Sent \'" + text + "\'");

// Clean up
messageProducer.close();
session.close();
connection.close();

}
catch (Exception e) {
}
}
}```

Consumer Class(AMQConsumer.java):

```import javax.jms.*;

import org.apache.activemq.ActiveMQConnectionFactory;
public class AMQConsumer implements Runnable, ExceptionListener  {
// Use the same factory for all the consumer threads.
static ActiveMQConnectionFactory activeMQConnectionFactory =
new ActiveMQConnectionFactory("tcp://localhost:61616");

@Override
public void run() {
try {
// Create a JMS connection from the ActiveMQ server
Connection connection = activeMQConnectionFactory.createConnection();
connection.setExceptionListener(this); // override "void onException(JMSException arg0)" method
connection.start();

// Create a session to receive message
Session session = connection.createSession(false, Session.AUTO_ACKNOWLEDGE);

Destination destination = session.createQueue("HelloMoto");

// MessageConsumer is used to receive messages
// Refer http://docs.oracle.com/javaee/1.4/api/javax/jms/MessageConsumer.html for more
MessageConsumer messageConsumer = session.createConsumer(destination);

// receive(long timeout) - Receives the next message that arrives within the specified
// timeout interval

// if the received message is text message, display it on console
if (message instanceof TextMessage ) {
TextMessage textMessage = (TextMessage)message;
") : Recieved \'" + textMessage.getText() + "\'");
} else {
") : Dont have any message to display");
}

// Clean up
messageConsumer.close();
session.close();
connection.close();

} catch (Exception e) {
}
}

// If a JMS provider detects a serious problem with a connection, it informs the connection's
// ExceptionListener,
@Override
public void onException(JMSException arg0) {
+ "Shutting down client.");
}
}```

Main Class(AMQMain):

```import org.sree.activemqeg.AMQConsumer;
import org.sree.activemqeg.AMQProducer;

public class AMQMain {

public static void main(String[] args) throws InterruptedException {
}
}```

Output: Neglect the log4j warnings for the time being…

You can analyze the statistics of the various queues of ActiveMQ from a browser with the URL http://localhost:8161 (replace ‘localhost’ with the IP of the machine if ActiveMQ is in a different system). Have a look at the queue we created with our program. Meet you in my next post “ActiveMQ Producer and Client in Java using Spring Framework” which will make things more configurable and professional. 😉

## Essential Coding Standards in Java

• What is the need of coding standards and comments?
Coding standards and comments are for the programmer’s ease of understanding the program. They improve the readability of the software.
Another good reason for the need of coding standards and appropriate comments in the program is that, more than 75% of the lifetime cost of a piece of software goes to maintenance and any software is hardly maintained by its original author for its whole life. In this case, appropriate comments in the program will help the new engineers understand the logic of the original author of the program, quickly and thoroughly and take the project further. It will also be helpful to the author of the program in recollecting the logic he has used in it, in a later point of time.
• Do the comments in the program get compiled into the final executable file?
No, all the comments and blank spaces put into program as part of indentation are filtered out at the time of compiling.

Coding Standards
1. Packages
• Package names should help in understanding the program and functions of the files in it.
• Package name should have a proper hierarchy and should be in all-lowercase.
• Files of similar functionality should be put into same package.
• Use different sub packages if needed, instead of putting all your source files into one package.
• Prefix of a package name should always be one of the top-level domain names: com, edu, gov, mil, org or English two-letter codes of countries according to ISO Standard 3166, 1981 and rest of the package name can be according to the internal naming convention of the organization, it can specify division, department, working-unit, etc.
• Eg:
com.infosys.tvm.ped.apple
2. Files
• Files can have maximum of 2000 lines of code.
• Separate different sections of your file with a blank line.
• Write an optional comment for each section for identifying it.
2.1. Source files
• Source files can contain a single public class or interface.
• Private classes and interfaces associated with public classes can be put in the same source file as the public class.
• Public class or interface should be in the beginning of the source file.
• Source file structure:
o Source file should start with a comment of format given below:
/*
*Class name:
*
*Version information:
*
*Date:
*
*/
 Eg:
/*
*
*HelloWorld.java 1.09 11th Oct 1989
*
*/
o Package and import statements:
package com.infosys.ped.apple;
import java.util.*;
o Class and Interface declarations.
2.1.1. Classes
• Class names should be nouns, in mixed case with the first letter of every word capitalized.
Eg:
class Infosys;
class InfosysEmployee
• Class names should be simple and descriptive.
• Use only widely used abbreviations and acronyms in class names; rest of the words should be as whole-words.
• Comment for the class:
/*
*Class description:
*
*Version:
*
*Author:
*/
2.1.2. Interfaces
• Interface name should follow all the standards as class names.
• Eg:
interface Car;
interface InfosysClient;
2.1.3. Methods
• Method names should be verbs in mixed cases, with starting letter lowercase and first letter of all internal words capitalized.
Eg:
erase();
getName();
averageWorkHours();

• Methods should be prefixed with a comment, describing the purpose of it, its argument list and its return value.
• Separate methods with a blank line.
• There should not be space between method name and parenthesis and opening curly braces need to be in the same line as method header; use a new line for closing curly brace.
Eg:
void sayHelloToWorld() {
String stringToPrint = “Hello World… “;
. . .
if (conditional_expression) {
System.out.println();
. . .
}
. . .
}

2.1.4. Variables
• Variable names should be in mixed case with starting letter lowercase and first letter of all internal words capitalized.
• Variable names should be short and meaningful. It should indicate the intent of its use.
• Variable names should not start with underscore (“_”) or dollar sign (“\$”) even though it’s possible.
• Do not wait to declare variables until their first use.
• Variables of one character length should be avoided except for temporary variables. Common practice is to use i, j, k, m and n for integers and c, d and e for characters.
Eg:
int i;
char c;
float mySalary;
• Prefer tabs to space between data type and variables. This will make your program look aligned.
Eg:
String unitName; //preferred
int noOfEmployees; //preferred

String unitName; //not a good practice
int noOfEmployees; //not a good practice
• Using a new line for every declaration and commenting it is a good practice.
Eg:
int myAge; //present age of the user
float mySalary //annual income of the user
• Avoid declaration different types in same line.
Eg:
String name, nicknames; //Wrong
2.1.5. Constants
• Constant variable’s name should be fully capitalized with words separated by underscore (“_”)
• Eg:
static final int MAX_AGE_LIMIT=65;
3. Indentation
• Avoid lines longer than 80 characters. Programs should be readable without scrolling horizontally.
• Break expressions, either after a comma or before an operator, which does not fit in a single line. Indent it properly to avoid confusion.
• Eg:
var = myFunction1( myParameter1, myParameter2, myParameter3,
myParameter4, myParameter5);
Good programming practices
• Use library utilities wherever possible, instead of coding your own logic. Library utilities are optimized for speed and performance and use of these will make the program perform better.
• var1++; var2++; //Wrong practice

var1++; //Correct
var2++ //Correct
• Always use curly braces with “ if ” conditions and “ for ” statements even if there is only one statement inside the block.
• Separate expressions in a “ for ” statement with a blank space.
Eg:
for (expression1; expression2; expression3)
• Do not declare any of the class or instance variables as public unless its unavoidable.
• Avoid using of the instance variables to access class variables.
• zoo.var1 = boo.var2 = 2; //Wrong; makes the program complicated to read
• if (c==d && d==e) //Wrong practice
if ((c==d) && (d==e)) //Correct
• i == 1 ? 100 : 0; //Wrong practice
(i==1) ? 100 : 0; //Correct