24
\$\begingroup\$

Most tip calculator apps simply take a flat percentage of the meal price. So, for example, if your meal is $23.45, you can leave a 15% tip = $3.52, or a more generous 20% tip = $4.69.

Convenient enough for credit card users. But not so if you prefer to leave cash tips, in which case these oddball cent amounts get in the way. So let's modify the idea to be more convenient for cash users.

Your assignment

Write, in as few bytes as possible, a program or function that takes as input:

  • Price of the meal
  • Minimum tip percentage
  • Maximum tip percentage

And output any tip amount within the range [price * min_percentage / 100, price * max_percentage / 100] that minimizes the number of bills/banknotes and coins required.

Assume the US monetary denominations of 1¢, 5¢, 10¢, 25¢, $1, $5, $10, $20, $50, and $100.

Example

Here is a non-golfed example program in Python:

import math
import sys

# Do the math in cents so we can use integer arithmetic
DENOMINATIONS = [10000, 5000, 2000, 1000, 500, 100, 25, 10, 5, 1]

def count_bills_and_coins(amount_cents):
    # Use the Greedy method, which works on this set of denominations.
    result = 0
    for denomination in DENOMINATIONS:
        num_coins, amount_cents = divmod(amount_cents, denomination)
        result += num_coins
    return result

def optimize_tip(meal_price, min_tip_percent, max_tip_percent):
    min_tip_cents = int(math.ceil(meal_price * min_tip_percent))
    max_tip_cents = int(math.floor(meal_price * max_tip_percent))
    best_tip_cents = None
    best_coins = float('inf')
    for tip_cents in range(min_tip_cents, max_tip_cents + 1):
        num_coins = count_bills_and_coins(tip_cents)
        if num_coins < best_coins:
            best_tip_cents = tip_cents
            best_coins = num_coins
    return best_tip_cents / 100.0

# Get inputs from command-line
meal_price = float(sys.argv[1])
min_tip_percent = float(sys.argv[2])
max_tip_percent = float(sys.argv[3])
print('{:.2f}'.format(optimize_tip(meal_price, min_tip_percent, max_tip_percent)))

Some sample input and output:

~$ python tipcalc.py 23.45 15 20
4.00
~$ python tipcalc.py 23.45 15 17
3.55
~$ python tipcalc.py 59.99 15 25
10.00
~$ python tipcalc.py 8.00 13 20
1.05
\$\endgroup\$
15
  • 8
    \$\begingroup\$ If you're not using a credit card then you are paying in cash, right? Wouldn't the total of check+tip be the relevant amount then, not just the tip? \$\endgroup\$
    – Sparr
    Jul 26, 2018 at 5:31
  • 4
    \$\begingroup\$ a program that takes as input (stdin, command-line arguments, or GUI input box, whichever is most convenient in your language) Is this intended to override our defaults for inputs and outputs? That is, would e.g. a function that takes three numbers and returns the result be allowed? \$\endgroup\$
    – Laikoni
    Jul 26, 2018 at 7:02
  • 3
    \$\begingroup\$ Am I correct in saying that 3.51 and 3.75 are also valid outputs for the test case 23.45 15 17? They use the same amount of coins and are also inside the range. \$\endgroup\$ Jul 26, 2018 at 7:37
  • 3
    \$\begingroup\$ @Sparr Even people who pay the bill by card like to leave a cash tip; there are various reasons given for this so I won't repeat them here. \$\endgroup\$
    – Neil
    Jul 26, 2018 at 7:53
  • 3
    \$\begingroup\$ @Laikoni: I have edited the requirements to use the site-default "program or function", and so am retroactively accepting the existing function-only answers. \$\endgroup\$
    – dan04
    Jul 27, 2018 at 1:17

10 Answers 10

6
\$\begingroup\$

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
\$\endgroup\$
0
4
\$\begingroup\$

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)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Some quick golfing to get it to 185 bytes \$\endgroup\$
    – Jo King
    Jul 26, 2018 at 10:00
4
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ I don't think this is technically valid at the moment since the question specifies a program, but the OP hasn't clarified. \$\endgroup\$
    – Οurous
    Jul 26, 2018 at 8:55
  • 1
    \$\begingroup\$ OP has clarified functions are now allowed, so you don't need to worry about doubling the size. \$\endgroup\$
    – Οurous
    Jul 27, 2018 at 5:11
3
\$\begingroup\$

Charcoal, 60 bytes

Nθ≔×θNη≔×θNζ≔⁰θFI⪪”;‴üφ↷Σ↗SEX&¿h'⊟”³«W‹θη≧⁺ιθ¿›θζ≧⁻ιθ»﹪%.2fθ

Try it online! Takes input as decimals. Link is to verbose version of code. Explanation:

Nθ

Input the bill.

≔×θNη≔×θNζ

Input the tip decimal fractions and compute the minium and maximum tip.

≔⁰θ

Start with zero tip.

FI⪪”;‴üφ↷Σ↗SEX&¿h'⊟”³«

The SEXy string expands to 10050.20.10.5.01.0.250.1.05.01 which is split into groups of three characters and cast to float.

W‹θη≧⁺ιθ

Add as many of the current denomination as necessary to reach the minimum tip.

¿›θζ≧⁻ιθ»

Remove one denomination if the maximum tip has been exceeded.

﹪%.2fθ

Format the tip for display.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I don't think the formatting was a requirement (rather just something the example code does). \$\endgroup\$ Jul 28, 2018 at 23:09
  • \$\begingroup\$ @JonathanAllan Well in that case you could save 4 bytes by using instead of ﹪%.2f. \$\endgroup\$
    – Neil
    Jul 28, 2018 at 23:16
3
\$\begingroup\$

Clean, 207 156 bytes

Swapping to a function saved 51 bytes, unsurprisingly.

import StdEnv
d=[10000,2000,1000,500,100,25,10,5,1]
$n u l=snd(hd(sort[(sum[foldl(rem)m(d%(0,i))/k\\k<-d&i<-[-1..]],toReal m)\\m<-map toInt[n*u..n*l]]))/1E2

Try it online!

\$\endgroup\$
2
  • 2
    \$\begingroup\$ OP clarified that functions are now allowed. \$\endgroup\$
    – Laikoni
    Jul 27, 2018 at 4:56
  • \$\begingroup\$ @Laikoni Thanks for letting me know :) Saves a lot of bytes - full programs are expensive in Clean! \$\endgroup\$
    – Οurous
    Jul 27, 2018 at 5:09
2
\$\begingroup\$

Python (264 222 bytes)

Slightly more golfed.

m=[.01,.05,.1,.25,.5,1,5,10,20,50,100]
def f(a,i,j):
 t,u=9**9,a*j
 def g(s,d,c):
  nonlocal t
  if(a*i<s<u)+(c>t):t=min(c,t);return c,s
  return(t+1,s)if(s>u)+(d>9)else min(g(s+m[d],d,c+1),g(s,d+1,c))
 return g(0,0,0)[1]

Try it Online!

\$\endgroup\$
2
\$\begingroup\$

Perl 6, 93 92 89 bytes

{.01*($^a*$^b+|0...$a*$^c).min:{$!=$_;sum '✐ᎈߐϨǴd
'.ords>>.&{($!%=$_)xx$!/$_}}}

Try it online!

Anonymous code block that takes three arguments (price, minimum percentage, and maximum percentage) and returns the tip.

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 105 bytes

This will give all the solutions with minimal coin count.

MinimalBy[NumberDecompose[#,d=100{100,50,20,10,5,1,.25,.10,.05,.01}]&/@Range[Ceiling[#2#],#3#],Tr].d/100&

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Kotlin, 215 bytes

{p:Double,l:Int,h:Int->val d=listOf(10000,5000,2000,1000,500,100,25,10,5,1)
var m=Int.MAX_VALUE
var r=0.0
(Math.ceil(p*l).toInt()..(p*h).toInt()).map{var a=it
var c=0
d.map{c+=a/it
a%=it}
if(c<m){m=c
r=it/100.0}}
r}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Jelly,  33  32 bytes

“ñṇzi;’b⁴×H¥\ɓ_>Ƈ-Ṫ
PĊ1¦r/ÇƬL$ÞḢ

A monadic link accepting a list [cost in cents, [minimum ratio, maximum ratio]] which yields a tip amount in cents.

Try it online!

How?

The first line is a helper Link which yields the amount given less the largest denomination note/coin:

“ñṇzi;’b⁴×H¥\ɓ_>Ƈ-Ṫ - Link 1, get next lower amount: integer, V
“ñṇzi;’             - base 250 number = 112835839060
       b⁴           - to base 16 = [1,10,4,5,8,10,4,4,5,4]
            \       - cumulative reduce with:       e.g.: 1,10   5,4   10,5   25,8
           ¥        -   last two links as a dyad:
         ×          -     multiply                        10     20    50     200
          H         -     halve                            5     10    25     100
                    - ...yielding: [1,5,10,25,100,500,1000,2000,5000,10000]
             ɓ      - start a new dyadic link with swapped arguments
              _     - subtract (vectorises) ...i.e. [V-1,V-5,V-10,...]
                Ƈ   - filter keep those which satisfy:
                 -  -   literal -1
               >    -   greater than? (i.e. if V-X > -1)
                  Ṫ - tail (tailing an empty list yields 0)

The number of calls required in order to reach zero is used to sort the range of tip amounts, and then the leftmost is yielded:

PĊ1¦r/ÇƬL$ÞḢ - Main Link: [cost, [min, max]]
P            - product = [cost*min, cost*max]
   ¦         - sparse application...
  1          - ...to indices: 1
 Ċ           - ...what: ceiling   -> [ceil(cost*min), cost*max]
     /       - reduce by:
    r        -   inclusive range (implicit floor of arguments)
          Þ  - sort by:
         $   -   last two links as a monad:
       Ƭ     -     repeat collecting results until a fixed point is reached:
      Ç      -       last link (1) as a monad  (e.g. 32 -> [32,7,2,1,0])
        L    -     length (i.e. coins/notes required + 1)
           Ḣ - head
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.