I have cracked the asymptotically constant version of the min coin counts algorithm ..
// http://www.impactinterview.com/2009/10/140-google-interview-questions/#software_engineer
//
// Given a set of coin denominators, find the minimum number of coins to give a
// certain amount of change.
#include <cstdint>
#include <climits>
#include <vector>
#include <iostream>
#include <functional>
#include <chrono>
#include <memory>
#include <list>
#include <queue>
// I knew there was an asymptotically constant version of algorithm i just cracked
// it using top down dynamic programming combined squeeze theorem (the same way
// that Archimedes found pi)
//
// https://en.wikipedia.org/wiki/Squeeze_theorem
// https://betterexplained.com/articles/prehistoric-calculus-discovering-pi/
// how it works:
// First off we are going to search with a dynamic programming version of the
// depth first search. We are searching by choosing a count for a coin
// denomination and then moving to the next denomination searching all the way
// down this branch until we exhaust it. Since the algorithm is a dynamic
// version of DFS it means we are using a stack, not recursion.
// Also note that we are using squeeze theorem that means we need to track an
// upperBoound(the know best) and a lowerBound the theoretical floor that an
// unknown branch might achieve
// So by using DFS we can get down to the last coin denomination and get a
// solid result quickly and that potentially tightens the upperBound more. As
// the upperbound tightens we are able to trim the search tree more, and as a
// result speed up the overall search more.
// 1) first we set the best and the initial upperBounds to the max number of
// coins possible + 1. The upperbounds is the same as our best known min coins
// count. which at the start inst anything. Remember when the upperBounds on
// coin count is exceed the search will stop looking at that branch as a
// possible answer
// 2) Next initialize the stack. We only stack partial computation steps.
// The first item to add is the max coins we could have for the largest coin,
// later we will decrement from this until we reach zero
//
// 3) Now start the iteration loop. Pop off the current working item (note the
// actual algorithm is optimized and only pops from the stack if it really has
// finished that denomination). There are 2 updates to make to the stack
//
// 3a) make a copy of the current item and reduce the coin count in it for the
// current denomination then compute the theoretical lowerBound for the
// remaining largest denomination of coins (ie compute the max coins for
// highest remaining denomination excluding current denomination and better), if
// the theoretical lowerBound of coins that have to be used plus the current
// used coins is greater than the upperBound prune the entire branch.. it can
// not possibly bet the current known min. But if it is better than or equal
// we should push that back onto the stack as it may bet the current best
//
// 3b) Then make another copy of the current item as the next item. moving to
// the next highest coin denomination (excluding to ones which we have already
// chosen coins for) and compute the max coins that it can use and add it to a
// next item. Then check if its a terminal case (all coins used) if it inst
// terminal push that to the stack (it will pop off the stack as the next
// current) if it is the terminal then compare it to the upperBound if it can
// bet that update the best min and the upperBound
//
// repeat until the stack runs out.. then return the best min,
// So lets get started note i have the greedy and bot up with reach pruning
// versions for comparison
// A greedy implementation - a quick greedy way to the answer is to maximize
// the largest coin
//
// Note this can give the *wrong* answer
// Note expects reverse sorted coins (largest to smallest in denom)
std::vector<uint32_t> minCoins_greedy(uint32_t total,
const std::vector<uint32_t>& denom)
{
std::vector<uint32_t> res(denom.size()+1,0);
if (total == 0) return res;
for(int i = 0; i < denom.size(); ++i)
{
uint32_t count = total / denom[i];
total -= (count * denom[i]);
res[i] = count;
res[denom.size()] += count;
}
if (total != 0) res[denom.size()] = INT_MAX;
return res;
}
// ok so we can improve the bottom up DP version and shave a bit more time by
// visiting items in the order of current coin count as a result we will create
// a BFS style pruned search
//
// Note expects reverse sorted coins (largest to smallest in denom)
std::vector<uint32_t> minCoins_botUpReach(uint32_t total,
const std::vector<uint32_t>& denom)
{
// we are dividing by making the full decistion for each coin and then removing it from the list
if (total == 0) return std::vector<uint32_t>(denom.size()+1, 0);
// setup memory
std::vector< std::vector<uint32_t> > cache(total + 1, std::vector<uint32_t>(denom.size()+1, 0));
std::list<uint32_t> queue;
queue.push_back(0);
while(not queue.empty())
{
uint32_t curTotal = queue.front();
queue.pop_front();
for(int i = 0; i < denom.size(); ++i)
{
uint32_t newTotal = curTotal + denom[i];
if (newTotal <= total and
cache[newTotal][denom.size()] == 0)
{
// ok its empty
cache[newTotal] = cache[curTotal];
++(cache[newTotal][i]);
++(cache[newTotal][denom.size()]);
if (newTotal == total)
return cache[total];
queue.push_back(newTotal);
}
}
}
// impossible case
cache[0][denom.size()] = INT_MAX;
return cache[0];
}
// ok another idea we can reformulation top down upperBound and lowerBound
// squeeze tree pruning. greedy initialization of the upperbound
//
// Note expects reverse sorted coins (largest to smallest in denom)
std::vector<uint32_t> minCoins_topSqueeze(uint32_t total,
const std::vector<uint32_t>& denom)
{
const int LastIdx = denom.size() - 1;
const int TotalCoinsIdx = denom.size();
const int RemTotalIdx = denom.size() + 1;
const int WorkingIdx = denom.size() + 2;
const int Size = denom.size() + 3;
// prune the total of 0 corner case
if (total == 0) return std::vector<uint32_t>(denom.size()+1, 0);
std::vector<uint32_t> best(Size);
best[TotalCoinsIdx] = INT_MAX;
// remove 1 coin corner case
if (denom.size() < 2)
{
if (denom.size() == 1)
{
best[0] = total / denom[0];
best[TotalCoinsIdx] = (best[0] + denom[0]) == total ? best[0] : INT_MAX;
}
return best;
}
// whats my best guess min (upperbounds)
// dont use INT_MAX we are doing maths on it (make it overflowed max)
uint32_t upperBounds = total + 1;
// since we move through the denom vector its size is also the upper limit to
// the stack size
std::vector< std::vector<uint32_t> > stack(denom.size(), std::vector<uint32_t>(Size));
int stackTopIdx = 0;
// compute the max coins for the first layer thats the starting point
stack[0][0] = total / denom[0];
stack[0][TotalCoinsIdx] = stack[0][0]; // total coin count
stack[0][RemTotalIdx] = total - (stack[0][0]*denom[0]); // remaining total
stack[0][WorkingIdx] = 0; // denom working offset
while (stackTopIdx >= 0)
{
if (stackTopIdx >= stack.size()) std::cout << "Stack size assumption failed!\n";
std::vector<uint32_t>& current = stack[stackTopIdx];
uint32_t workingIdx = current[WorkingIdx];
// first generate the current coins reduction case for this level
if (current[workingIdx] > 0) // we have coin left in this layer
{
// compute is the absolute lower bonds the next coin level..
uint32_t nextCoinsLowerBounds
= current[RemTotalIdx] / denom[workingIdx+1];
// can this new count and the lower bounds of the next level of coins
// possibly bet the curent upper bounds?
if (current[TotalCoinsIdx]-1 + nextCoinsLowerBounds <= upperBounds)
{
// update the current top but first push a copy ahead of it
// for the next level of coins computation.
stack[stackTopIdx+1] = current;
// ok so remove one of current levels coins
current[workingIdx] -= 1;
current[TotalCoinsIdx] -= 1;
current[RemTotalIdx] += denom[workingIdx];
// move stack forward
++stackTopIdx;
}
}
// now generate the max case for the next level
++workingIdx;
std::vector<uint32_t>& next = stack[stackTopIdx];
// compute the max coins we can use for it and queue that
next[workingIdx] = next[RemTotalIdx] / denom[workingIdx];
next[TotalCoinsIdx] += next[workingIdx];
next[RemTotalIdx] -= denom[workingIdx] * next[workingIdx];
next[WorkingIdx] = workingIdx;
// check if this result is a terminal of the search
if (next[RemTotalIdx] == 0)
{
// it was the end and solves the problem
// remove it from the stack
--stackTopIdx;
// check if it bets the best
if (upperBounds > next[TotalCoinsIdx])
{
best = next;
upperBounds = best[TotalCoinsIdx];
}
}
else if(workingIdx == LastIdx) // because it can fail!
{
// its on the last coin and didnt correctly match totals. So its a
// broken version. Remove it.
--stackTopIdx;
}
}
return best;
}
void test(const char* label,
std::function<std::vector<uint32_t> (uint32_t, const std::vector<uint32_t>&)> func,
uint32_t n,
const std::vector<uint32_t>& denom)
{
auto start = std::chrono::system_clock::now();
std::vector<uint32_t> res = func(n, denom);
auto end = std::chrono::system_clock::now();
std::cout << label << ": result:";
for (int i = 0; i < denom.size(); ++i)
std::cout << denom[i] << "x" << res[i] << " ";
std::cout << " count:" << res[denom.size()] << "\n";
std::cout << " -- time:"
<< std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count()
<< " nSec\n";
}
void testSet(uint32_t n,
const std::initializer_list<uint32_t>& dlist)
{
std::vector<uint32_t> denom(dlist);
std::cout << "\n*** test set for " << n << " *** \n";
if (n < 2001) test("botUpReach", minCoins_botUpReach ,n, denom);
else std::cout << "skipped botUpReach\n";
test("topSqueeze", minCoins_topSqueeze, n, denom);
}
int main()
{
// breakers
testSet(0, {20,15,5,4,1});
testSet(1, {2});
testSet(23, {20,15,5,4,1}); // attack greedy
testSet(31, {20,15,5,4,1}); // attack greedy
testSet(43, {20,15,5,4,1}); // attack greedy
testSet(46, {20,15,5,4,1}); // attack greedy
testSet(100, {20,15,5,4,1}); // attack bottom up
testSet(1000, {20,15,5,4,1});
testSet(1000, {13,7,1});
testSet(2000, {20,15,5,4,1});
testSet(10000, {20,15,5,4,1});
testSet(100000000, {20,15,5,4,1});
testSet(100000023, {20,15,5,4,1});
testSet(100000031, {20,15,5,4,1});
testSet(100000043, {20,15,5,4,1});
testSet(100000046, {20,15,5,4,1});
testSet(100000100, {20,15,5,4,1});
}
*** test set for 0 ***
botUpReach: result:20x0 15x0 5x0 4x0 1x0 count:0
-- time:4100 nSec
topSqueeze: result:20x0 15x0 5x0 4x0 1x0 count:0
-- time:1614 nSec
*** test set for 1 ***
botUpReach: result:2x0 count:2147483647
-- time:14201 nSec
topSqueeze: result:2x0 count:2147483647
-- time:2656 nSec
*** test set for 23 ***
botUpReach: result:20x0 15x1 5x0 4x2 1x0 count:3
-- time:49285 nSec
topSqueeze: result:20x0 15x1 5x0 4x2 1x0 count:3
-- time:17680 nSec
*** test set for 31 ***
botUpReach: result:20x0 15x2 5x0 4x0 1x1 count:3
-- time:60896 nSec
topSqueeze: result:20x0 15x2 5x0 4x0 1x1 count:3
-- time:21468 nSec
*** test set for 43 ***
botUpReach: result:20x1 15x1 5x0 4x2 1x0 count:4
-- time:96826 nSec
topSqueeze: result:20x1 15x1 5x0 4x2 1x0 count:4
-- time:21117 nSec
*** test set for 46 ***
botUpReach: result:20x2 15x0 5x1 4x0 1x1 count:4
-- time:99908 nSec
topSqueeze: result:20x2 15x0 5x1 4x0 1x1 count:4
-- time:26414 nSec
*** test set for 100 ***
botUpReach: result:20x5 15x0 5x0 4x0 1x0 count:5
-- time:187759 nSec
topSqueeze: result:20x5 15x0 5x0 4x0 1x0 count:5
-- time:15795 nSec
*** test set for 1000 ***
botUpReach: result:20x50 15x0 5x0 4x0 1x0 count:50
-- time:2350739 nSec
topSqueeze: result:20x50 15x0 5x0 4x0 1x0 count:50
-- time:18175 nSec
*** test set for 1000 ***
botUpReach: result:13x76 7x1 1x5 count:82
-- time:2124334 nSec
topSqueeze: result:13x76 7x1 1x5 count:82
-- time:19523 nSec
*** test set for 2000 ***
botUpReach: result:20x100 15x0 5x0 4x0 1x0 count:100
-- time:4793008 nSec
topSqueeze: result:20x100 15x0 5x0 4x0 1x0 count:100
-- time:21261 nSec
*** test set for 10000 ***
skipped botUpReach
topSqueeze: result:20x500 15x0 5x0 4x0 1x0 count:500
-- time:22749 nSec
*** test set for 100000000 ***
skipped botUpReach
topSqueeze: result:20x5000000 15x0 5x0 4x0 1x0 count:5000000
-- time:23337 nSec
*** test set for 100000023 ***
skipped botUpReach
topSqueeze: result:20x5000000 15x1 5x0 4x2 1x0 count:5000003
-- time:65017 nSec
*** test set for 100000031 ***
skipped botUpReach
topSqueeze: result:20x5000000 15x2 5x0 4x0 1x1 count:5000003
-- time:50749 nSec
*** test set for 100000043 ***
skipped botUpReach
topSqueeze: result:20x5000001 15x1 5x0 4x2 1x0 count:5000004
-- time:42286 nSec
*** test set for 100000046 ***
skipped botUpReach
topSqueeze: result:20x5000002 15x0 5x1 4x0 1x1 count:5000004
-- time:44130 nSec
*** test set for 100000100 ***
skipped botUpReach
topSqueeze: result:20x5000005 15x0 5x0 4x0 1x0 count:5000005
-- time:14530 nSec
No comments:
Post a Comment