ylyhlh · August 29, 2015 14:02 · Jun 8, 2014 · Jun 8, 2014 · Jun 8, 2014 · Jun 8, 2014
diff --git a/BoostInt.h b/BoostInt.h
@@ -1,7 +1,6 @@
 //---------
 //Question:
 //---------
-
 /*Assume the US dollar is available in denominations of
  *$100, $50, $20, $10, $5, $1, $0.25, $0.10, $0.05 and 
  *$0.01.  Write a function to return the number of 

diff --git a/BoostInt.h b/BoostInt.h
@@ -1,11 +1,3 @@
-//
-//  BoostInt.h
-//
-//
-//  Created by Liu Hao on 6/3/14.
-//  http://haoliu.org
-//  Copyright (c) 2014 liu hao. All rights reserved.
-//
 //---------
 //Question:
 //---------

diff --git a/BoostInt.h b/BoostInt.h
@@ -6,6 +6,18 @@
 //  http://haoliu.org
 //  Copyright (c) 2014 liu hao. All rights reserved.
 //
+//---------
+//Question:
+//---------
+
+/*Assume the US dollar is available in denominations of
+ *$100, $50, $20, $10, $5, $1, $0.25, $0.10, $0.05 and 
+ *$0.01.  Write a function to return the number of 
+ *different ways to exactly represent an arbitrary value
+ *less than $1,000.00 using any number or 
+ *combination of these denominations.
+ */
+
 
 #ifndef BoostInt_h
 #define BoostInt_h

diff --git a/test.cpp b/test.cpp
@@ -0,0 +1,60 @@
+//
+//  test.cpp
+//
+//
+//  Created by Liu Hao on 6/3/14.
+//  http://haoliu.org
+//  Copyright (c) 2014 liu hao. All rights reserved.
+//
+
+#define BOOST_TEST_DYN_LINK
+#define BOOST_TEST_MODULE Hello
+#include <boost/test/unit_test.hpp>
+#include "BoostInt.h"
+#include "MoneyChanger.h"
+
+//-- 1 dollar test return 1
+BOOST_AUTO_TEST_CASE(oneDollar)
+{
+    MoneyChanger mc;
+    BOOST_CHECK(mc.howManyCombinations(1) == 243);
+}
+
+//-- 0 dollar test return 1
+BOOST_AUTO_TEST_CASE(zeroDollar)
+{
+    MoneyChanger mc;
+    BOOST_CHECK(mc.howManyCombinations(0) == 1);
+}
+
+//-- less that 5 cents return 1
+BOOST_AUTO_TEST_CASE(onlyOneCent)
+{
+    MoneyChanger mc;
+    BOOST_CHECK(mc.howManyCombinations(0.04) == 1);
+}
+
+//-- negative teat
+BOOST_AUTO_TEST_CASE(negativeException)
+{
+    MoneyChanger mc;
+    BOOST_CHECK_THROW(mc.howManyCombinations(-1), MoneyChangerException);
+}
+
+//-- not whole cent test
+BOOST_AUTO_TEST_CASE(notWholeCentException)
+{
+    MoneyChanger mc;
+    BOOST_CHECK_THROW(mc.howManyCombinations(1.02354235), MoneyChangerException);
+}
+
+#ifdef ___USING___LONGLONG___
+//-- overflowing test, checked only when long long used
+BOOST_AUTO_TEST_CASE(overflowingException)
+{
+    MoneyChanger mc;
+    BOOST_CHECK_THROW(mc.howManyCombinations(10000), MoneyChangerException);
+}
+#endif
+
+
diff --git a/Makefile b/Makefile
@@ -0,0 +1,37 @@
+#Change this to your boost path
+BOOST_INCLUDE=/usr/local/Cellar/boost/1.55.0_1/include/
+BOOST_LIB=/usr/local/Cellar/boost/1.55.0_1/lib
+
+#Flags no need to change
+GMP_FLAG=gmp
+BOOST_TEST_FLAG=boost_unit_test_framework
+RUN_BOOST_FLAGS=-l$(GMP_FLAG)
+RUN_FLAGS=
+TEST_FLAGS=-l$(GMP_FLAG) -l$(BOOST_TEST_FLAG)
+C_FLAGS=-std=c++11
+
+
+# use main to run and get output from stdout
+.PHONY: run
+run: main.cpp MoneyChanger.o
+	$(CXX) $(C_FLAGS) -I$(BOOST_INCLUDE) -L$(BOOST_LIB) $(RUN_FLAGS) $^ -o $@
+	./$@
+
+# use main to run and get output from stdout
+.PHONY: runboost
+runboost: main.cpp MoneyChanger.o
+	$(CXX) $(C_FLAGS) -I$(BOOST_INCLUDE) -L$(BOOST_LIB) $(RUN_BOOST_FLAGS) $^ -o $@
+	./$@
+
+# use boost unit test to run and test
+.PHONY: test
+test: test.cpp MoneyChanger.o
+	$(CXX) $(C_FLAGS) -I$(BOOST_INCLUDE) -L$(BOOST_LIB) $(TEST_FLAGS) $^ -o $@
+	./$@
+
+MoneyChanger.o:MoneyChanger.cpp
+	$(CXX) -c $(C_FLAGS) -I$(BOOST_INCLUDE) -L$(BOOST_LIB) $? -o $@
+
+
+clean:
+	rm -rf *.o test run
diff --git a/main.cpp b/main.cpp
@@ -0,0 +1,72 @@
+//
+//  main.cpp
+//
+//
+//  Created by Liu Hao on 6/3/14.
+//  http://haoliu.org
+//  Copyright (c) 2014 liu hao. All rights reserved.
+//
+
+#include <iostream>
+#include <vector>
+#include "BoostInt.h"
+#include "MoneyChanger.h"
+
+// the test function of MoneyChanger class
+void testMoneyChanger(double dollar, MoneyChanger* mc = NULL) {
+    try {
+        if (mc == NULL)
+            mc = new MoneyChanger();
+        BoostInt count = mc->howManyCombinations(dollar);
+        std::cout<<"The count of " << dollar << " is " << count << std::endl;    }
+    catch (std::exception& e)
+    {
+        std::cout << e.what() << '\n';
+    }
+}
+
+int main(int argc, const char * argv[])
+{
+    //get a new MoneyChanger
+
+    //==============
+    // Normal tests
+    //==============
+    //-- 0 test return 1
+    testMoneyChanger(0);
+    //-- 1 test return 243
+    testMoneyChanger(1);
+    //-- less that 5 cents return 1
+    testMoneyChanger(0.04);
+    //-- largest number test
+    testMoneyChanger(1000);
+
+    //==============
+    // Reuse tests
+    //==============
+    //-- the third one return very fast
+    MoneyChanger mc;
+    testMoneyChanger(1000, &mc);
+    testMoneyChanger(1300, &mc);
+    testMoneyChanger(1000, &mc);
+
+    //===============
+    //Exception tests
+    //===============
+    //-- negative teat
+    testMoneyChanger(-1);
+    //-- not whole cent test
+    testMoneyChanger(1.02354235);
+#ifdef ___USING___LONGLONG___
+    //-- overflowing test, checked only when long long used
+    testMoneyChanger(10000, &mc);
+#endif
+
+    //================
+    // print the table
+    //================
+    //mc.printCombinationTable();
+
+    return 0;
+}
+
diff --git a/BoostInt.h b/BoostInt.h
@@ -0,0 +1,27 @@
+//
+//  BoostInt.h
+//
+//
+//  Created by Liu Hao on 6/3/14.
+//  http://haoliu.org
+//  Copyright (c) 2014 liu hao. All rights reserved.
+//
+
+#ifndef BoostInt_h
+#define BoostInt_h
+
+/*************************************************/
+#include <boost/multiprecision/gmp.hpp>
+
+// using the multiprecision int from boost library
+typedef boost::multiprecision::mpz_int BoostInt;
+#define LOCAL_MAX 0
+/**************************************************/
+
+/*************************************************
+#define ___USING___LONGLONG___
+#define LOCAL_MAX LLONG_MAX
+typedef long long BoostInt;
+**************************************************/
+
+#endif
diff --git a/MoneyChanger.cpp b/MoneyChanger.cpp
@@ -0,0 +1,87 @@
+//
+//  MoneyChanger.cpp
+//
+//
+//  Created by Liu Hao on 6/3/14.
+//  http://haoliu.org
+//  Copyright (c) 2014 liu hao. All rights reserved.
+//
+
+#include "MoneyChanger.h"
+#include <iostream>
+
+
+BoostInt MoneyChanger::howManyCombinations(double dollors) {
+    //change it to cents and call combination function cents
+    int cents = int(dollors*100);
+    if (cents/100.0 != dollors) {
+        throw MoneyChangerException("The input Money of MoneyChanger object cannot be represented by integer in cents");
+    }
+    //if overfloating, forward the exception as MoneyChangerException
+    try {
+        return howManyCombinationsInCents(cents);
+    } catch (std::overflow_error &e) {
+        std::string message = std::string("In computing for ")
+                            + std::to_string(dollors) + std::string(". ")
+                            + e.what();
+        throw MoneyChangerException(message);
+    }
+
+}
+
+BoostInt MoneyChanger::howManyCombinationsInCents(int cents) {
+    // zero fast return
+    if (cents == 0)
+        return 1;
+    // negative check
+    if (cents < 0) {
+        throw MoneyChangerException("The input Money of MoneyChanger object is negative");
+    }
+    // vectore memory check
+    if (numOfCombinations.size() < cents + 1) {
+        try {
+            numOfCombinations.resize(cents + 1);
+        } catch (std::bad_alloc& ba) {
+            throw MoneyChangerException("bad_alloc caught in howManyCombinationsInCents");
+        }
+    }
+    //find last calculated cents
+    int startCents = maxCentsAvailavle / SKIP_STEP * SKIP_STEP;
+    // begin the computing
+    // Loop over cents
+    for (int p = startCents; p <= cents; p += SKIP_STEP) {
+        // get new space
+        try {
+            numOfCombinations[p].resize(NUM_OF_DENOMINATIONS + 1);
+        } catch (std::bad_alloc& ba) {
+            throw MoneyChangerException("bad_alloc caught in howManyCombinationsInCents");
+        }
+        numOfCombinations[p][1] = 1;
+        // Loop over number of denominations to use
+        for (int q = 2; q <= NUM_OF_DENOMINATIONS; ++q) {
+            int lastDenomination = denominations[q - 1];
+            // do dynamic programming bottom-up here
+            if (lastDenomination < p)
+                numOfCombinations[p][q] = safeADD(numOfCombinations[p-lastDenomination][q], numOfCombinations[p][q - 1]);
+            else if(lastDenomination == p)
+                numOfCombinations[p][q] = safeADD(1, numOfCombinations[p][q - 1]);
+            else
+                numOfCombinations[p][q] = numOfCombinations[p][q-1];
+        }
+        // TODO: here can save some memory if needed
+        // set next (SKIP_STEP - 1) elements point to same vectors
+        for (int offset = 1; offset < SKIP_STEP ; ++offset)
+            numOfCombinations[p+offset] = numOfCombinations[p];
+    }
+    maxCentsAvailavle = maxCentsAvailavle < cents ? cents : maxCentsAvailavle;
+    return numOfCombinations[cents][NUM_OF_DENOMINATIONS];
+}
+
+void MoneyChanger::printCombinationTable() {
+    for (int p = 0; p <=maxCentsAvailavle; p+=1) {
+        for (int q = 0; q <= NUM_OF_DENOMINATIONS; ++q)
+            std::cout <<numOfCombinations[p][q] <<",";
+        std::cout<<std::endl;
+    }
+}
+
diff --git a/MoneyChanger.h b/MoneyChanger.h
@@ -0,0 +1,80 @@
+//
+//  MoneyChanger.h
+//
+//
+//  Created by Liu Hao on 6/3/14.
+//  http://haoliu.org
+//  Copyright (c) 2014 liu hao. All rights reserved.
+//
+
+
+#ifndef __MoneyChanger__
+#define __MoneyChanger__
+
+#define NUM_OF_DENOMINATIONS 10
+#define DENOMINATIONS {1,5,10,25,100,500,1000,2000,5000,10000}
+#define SKIP_STEP 5
+
+
+#include "BoostInt.h"
+#include <exception>
+#include <string>
+#include <vector>
+
+
+// The exception for MoneyChanger
+class MoneyChangerException: public std::exception
+{
+    std::string message;
+public:
+    MoneyChangerException(std::string message) {
+        this->message = "[Exception] in MoneyChanger: ";
+        this->message += message;
+    }
+    virtual const char* what() const throw()
+    {
+        return message.c_str();
+    }
+};
+
+
+//MoneyChanger to get the number of combinations
+class MoneyChanger {
+    // Denominations in cents
+    std::vector<int> denominations;
+    // numOfCombinations[n][k] store the number of
+    // cimmbinations for n cents with first k denominations
+    std::vector<std::vector<BoostInt> > numOfCombinations;
+    // max number of cents have been calculated
+    int maxCentsAvailavle;
+    // use for safty adding
+    BoostInt safeADD(BoostInt x, BoostInt y){
+#ifdef  ___USING___LONGLONG___
+        if( x < LOCAL_MAX - y)
+            return x + y;
+        else
+            throw std::overflow_error("Overflowing in computation");
+#else
+        return x + y;
+#endif
+    }
+public:
+    MoneyChanger(){
+        //init attributes
+        maxCentsAvailavle = 0;
+        denominations = std::vector<int>(DENOMINATIONS);
+        // malloc the space for 0 cent, and calloc will init it with 0
+        numOfCombinations.resize(1);
+        numOfCombinations[0].resize(NUM_OF_DENOMINATIONS + 1);
+        numOfCombinations[0] = {0};
+    }
+    // return the number of combination of given 'dollars'
+    BoostInt howManyCombinations(double dollors);
+    // return the number of combination of given 'cents'
+    BoostInt howManyCombinationsInCents(int cents);
+    void printCombinationTable();
+
+};
+
+
+#endif /* defined(__MoneyChanger__) */