README.md

## README.md

      
        

          Raw
        
        
          
            
          
          
            
              README.md
            
          
        
      
    
  
    This small script uses combinatory analysis to figure out the optimal denominations for given number of possible coins to minimize the coins required to produce any amount between 1 cent and 1 dollar.  The candidate set of denominations is reduced to keep the  combinatory possibilities within reason.

  

  

## denom.js
// Candidate denominations
var candidates = [0.02,0.03,0.04,0.05,0.06,0.7,0.08,0.09,0.10,0.12,0.13,0.15,0.20,0.25,0.30,0.35,0.40,0.45,0.50,0.60,0.7,0.8,0.9,1];

// All amounts between one cent and a dollar
var amounts = Array
  .apply(0, Array(100))
  .map(function (element, i) {
       return (i+1)/100;
   });

// Standard combinatory function
function comb(c) {
  var n = candidates.length;
  var s=[];

  function bitprint(u) {
    var s=[];
    for (var n=0; u; ++n, u>>=1)
      if (u&1) s.push(candidates[n]);
    return s;
  }

  function bitcount(u) {
    for (var n=0; u; ++n, u=u&(u-1));
    return n;
  }

  for (var u=0; u<1<<n; u++)
    if (bitcount(u)==c)
      s.push(bitprint(u));
  return s;
}

// Roll through all combinations and pick minimum score
function denom(n) {
  return comb(n-1)
    .reduce(function(p,c) {
      c = c.sort().reverse().concat(0.01);
      var score = amounts.reduce(function(p,s) {
        return p + c.reduce(function(p,d) {
          if (s > 0) {
            p += Math.floor(s/d);
            s = s % d;
          }
          return p;
        },0);
      },0);
      return (p && p.score < score) ? p : { score: score, denom: c};
    });
}

## index.html
<!DOCTYPE html>
<meta charset="utf-8">
<h1>Optimal denominations for a dollar</h1>
<script src="denom.js"></script>
<script>
var numCoins = [2,3,4,5,6];

function next() {
  var n = numCoins.shift();
  if (!n) return;
  var result = denom(n);
  var res = document.createElement('p');
  res.textContent = n+' coins is: '+JSON.stringify(result.denom)+' with a score of '+result.score;
  document.body.appendChild(res);
  setTimeout(next)
}

setTimeout(next)
</script>
</html>

## thumbnail.png

      
        

          Raw
        
        
          
            
          
          
            
              thumbnail.png