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
// 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