Calculate a tip using the smallest number of coins

JavaScript (ES6), 93 bytes

(x,m,M)=>(g=(t,c=1e4)=>t>x*M?0:t<x*m?[...'1343397439'].some(d=>g(t+(c/=-~d/2)))*r:r=t)(0)/100

Try it online!

How?

We recursively compute a sum of bill/coin values until it falls within the acceptable range, always trying the highest value first.

This is guaranteed to use the minimum amount of bills and coins because for any solution \$\{b_0,\dots,b_n\}\$ returned by this algorithm:

  • all terms \$b_0\$ to \$b_n\$ are required, otherwise the algorithm would have selected \$\{b_0,\dots,b_{k-1},x\}\$ with \$x \ge b_k\$ for some \$0 \le k < n\$
  • for any \$0 \le k < n\$ and any \$x \le b_n\$, \$\{b_0,\dots,b_{k-1},b_k-x,b_{k+1},\dots,b_n\}\$ cannot be a solution, otherwise \$\{b_0,\dots,b_{n-1}\}\$ would have been selected
  • there may exist some \$0 < x < b_n\$ such that \$\{b_0,\dots,b_{n-1},x\}\$ is also valid, but that would not use less bills/coins than the selected solution

The bill/coin values \$c_n\$ expressed in cents are computed with:

$$\begin{cases}c_0=10000\\c_{n+1}=\dfrac{c_n}{(d_n+1)/2}\end{cases}$$

where \$(d_0,\dots,d_9) = (1,3,4,3,3,9,7,4,3,9)\$.

 n | c(n)  | d(n) | k = (d(n)+1)/2 | c(n+1) = c(n)/k
---+-------+------+----------------+-----------------
 0 | 10000 |   1  | (1+1)/2 = 1    |      10000
 1 | 10000 |   3  | (3+1)/2 = 2    |       5000
 2 |  5000 |   4  | (4+1)/2 = 2.5  |       2000
 3 |  2000 |   3  | (3+1)/2 = 2    |       1000
 4 |  1000 |   3  | (3+1)/2 = 2    |        500
 5 |   500 |   9  | (9+1)/2 = 5    |        100
 6 |   100 |   7  | (7+1)/2 = 4    |         25
 7 |    25 |   4  | (4+1)/2 = 2.5  |         10
 8 |    10 |   3  | (3+1)/2 = 2    |          5
 9 |     5 |   9  | (9+1)/2 = 5    |          1

Python 3.x: 266 185 bytes

A straightforward modification to my example program in the question. Note that the output is no longer formatted to require 2 decimal places.

Edit: Thanks to Jo King for making it smaller.

import sys
p,m,M,T=*map(float,sys.argv[1:]),0
C=p*M
for t in range(-int(-p*m),int(p*M)+1):
 n,a=0,t
 for d in 1e4,5e3,2e3,1e3,500,100,25,10,5,1:n+=a//d;a%=d
 if n<C:T,C=t,n
print(T/100)

Java 10, 186 185 bytes

(p,m,M)->{double r=0,t,Q=99,q;for(m*=p+.02;m<M*p;m+=.01){q=0;t=m;for(var c:new double[]{100,50,20,10,5,1,.25,.1,.05,.01})for(;t>=c;t-=c)q++;if(q<Q){Q=q;r=m;}}return"".format("%.2f",r);}

Takes the minimum and maximum percentages as /100 decimals (i.e. 15% as 0.15).

-1 byte to fix the issue with 3.51 as potential output and golfing the way to fix rounding errors by 1 byte at the same time.

Try it online.

Explanation:

(p,m,M)->{                // Method with three double parameters and String return-type
  double r=0,             //  Result-double, starting at 0
         t,               //  Temp-double
         Q=99,            //  Min amount of coins, starting at 99
         q;               //  Temp-double for the amount of coins
  for(m*=p-.02;m<M*p;     //  Loop in the range [`m*p-0.02`, `M*p`]
           m+=.01){       //  in steps of 0.01 (1 cent) per iteration
                          //  (the -0.02 (minus 2 cents) is to fix rounding errors)
    q=0;                  //   Reset `q` to 0
    t=m;                  //   Reset `t` to the current iteration `m`
    for(var c:new double[]{100,50,20,10,5,1,.25,.1,.05,.01})
                          //   Loop over the coins (largest to smallest)
      for(;t>=c;          //    As long as `t` is larger than or equal to the current coin
          t-=c)           //     Remove the coin from the value `t`
          q++;            //     And increase the quantity-counter by 1
      if(q<Q){            //   If the quantity-counter is smaller than the current smallest
        Q=q;              //    Replace the smallest with the current
        r=m;}}            //    And replace the result with the current `m`
  return"".format("%.2f",r)l;}
                          //  Return the result with 2 decimal places

Tags:

Code Golf

Recent Posts