Enigmatic Code

Programming Enigma Puzzles

Puzzle #10: Betty’s change

From New Scientist #3237, 6th July 2019 [link] [link]

Betty works at a cash register in the US. When you purchase something from her, Betty always gives you your change the sensible way: by selecting the largest coins that don’t take her over the amount that she owes you. For example, if she owed you 37 cents, she would first pick out a quarter (25 cents), then a dime (10 cents) then two pennies (a cent each).

However, this morning she has run out of nickels (5 cents) to give out as change, though she has plenty of pennies, dimes and quarters. When she gives you your change, you notice that she has given you twice as many coins as she could have done if she hadn’t been so keen to always start with the largest coin. What is the smallest possible monetary value of the change she has given you?

[puzzle#10]

One response to “Puzzle #10: Betty’s change

  1. Jim Randell 6 July 2019 at 8:30 am

    My first thought was to look for an amount a bit greater than 25¢ that can easily be expressed using other coins. 30¢ is the first obvious candidate, which can be expressed using 3× 10¢ coins. And without any 5¢ coins Betty would give the change as 25¢ + 5× 1¢ = 6 coins.

    This Python program demonstrates that this is the smallest possible amount. It runs in 99ms.

    Run: [ @repl.it ]

    from enigma import irange, inf, div, first, printf
    
    # greedy algorithm
    def greedy(t, ds):
      s = list()
      for d in ds:
        n = t // d
        s.append(n)
        t -= d * n
      return (s if t == 0 else None)
    
    # simple algorithm (from denominations.py)
    def express(t, ds, s=[]):
      if t == 0:
        if not(ds):
          yield s
        else:
          yield s + [0] * len(ds)
      elif ds:
        d = ds[0]
        for i in irange(0, t // d):
          yield from express(t - d * i, ds[1:], s + [i])
    
    # solve the puzzle using the specified denominations
    def solve(ds):
    
      # consider total amount
      for t in irange(1, inf):
        # using the greedy algorithm
        g = greedy(t, ds)
        n = sum(g)
    
        # can we express t using half as many coins?
        k = div(n, 2)
        if k is None: continue
        for s in express(t, ds):
          if sum(s) == k:
            printf("t={t} using {ds}: greedy={g}, simple={s}")
            return
    
    # available denominations of coin
    solve([25, 10, 1])
    

    Solution: The smallest amount of change is 30¢.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: