## Monday, July 25, 2016

### google interview: compute the mininual coins - asymptotic constant version

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

// 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[denom.size()] = INT_MAX;
return cache;
}

// 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 = total / denom;
best[TotalCoinsIdx] = (best + denom) == total ? best : 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             = total / denom;
stack[TotalCoinsIdx] = stack;                     // total coin count
stack[RemTotalIdx]   = total - (stack*denom);  // remaining total
stack[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