Enigmatic Code

Programming Enigma Puzzles

Enigma 1057: Recycled change

From New Scientist #2213, 20th November 1999 [link]

The denominations of coins currently in circulation are 200, 100, 50, 20, 10, 5, 2 and 1p. When we pay for an item we quite often exchange fewer coins when change is given than when the exact amount is offered. For instance, an item costing 91p would require at least four coins (50+20+20+1) for the exact amount, but the purchase can be made with the exchange of only three coins (100+1–10) if change is given.

Harry, Tom and I each bought an identical item that cost less than 100p. None of us offered the exact amount, but we each exchanged fewer coins than if we had done so. In fact, we each exchanged the minimum number of coins possible for an item of that price even though we each offered a different amount of money in payment.

I paid first, and Harry and Tom each included a different one of the coins I had received in my change among the coins that they offered.

How much did the item cost?

[enigma1057]

2 responses to “Enigma 1057: Recycled change

  1. Jim Randell 18 June 2018 at 8:31 am

    I simplified the code by only allowing a single minimal combination of coins for any amount (which is true for the coins and amounts considered by the puzzle).

    This Python program runs in 79ms.

    Run: [ @repl.it ]

    from itertools import count, combinations_with_replacement, permutations, combinations
    from collections import defaultdict
    from enigma import irange, join, printf
    
    # denominations of coins
    coins = (200, 100, 50, 20, 10, 5, 2, 1)
    
    # possible amounts
    amounts = set(irange(1, 99))
    
    # generate amounts that can be made with increasing minimal numbers of coins
    # yields (k, r, m) where:
    # k - number of coins
    # r - collection of minimal amount -> coins with k coins
    # m - collection of minimal amount -> coins with fewer than k coins
    def minimal(coins, amounts=None):
    
      # record minimum size combinations
      m = dict()
    
      # consider amounts that can be made with k coins
      for k in count(1):
      
        # collect new amounts that can be made with k coins
        r = dict()
        for s in combinations_with_replacement(coins, k):
          t = sum(s)
          if t not in m:
            assert t not in r # check for unique minimal combinations
            r[t] = s
    
        yield (k, r, m)
    
        # add in the new minimal amounts
        m.update(r)
    
        # have we considered all possible amounts?
        if amounts and amounts.issubset(m.keys()): return
    
    
    # consider amounts that can be made with k coins
    for (k, r, m) in minimal(coins, amounts):
    
      # consider possible amounts (x) for the item
      for (x, coins_x) in r.items():
        if x not in amounts: continue
    
        # consider possible change amounts (y), made with fewer than k coins
        # record (coins payed, coins recieved as change) by total number of coins in the transaction
        s = defaultdict(list)
        for (y, coins_y) in m.items():
          # so we pay an amount (x + y), using fewer than k coins
          coins_xy = m.get(x + y, None)
          if coins_xy is None: continue
          # and the total number of coins used in the exchange must also be less than k
          t = len(coins_xy) + len(coins_y)
          if not(t < k): continue
          s[t].append((coins_xy, coins_y))
    
        # D, T, H transactions each used a minimal number of coins in different ways
        if not s: continue
        t = min(s.keys())
        # consider possible exchanges (amounts payed and change received)
        for ((Dp, Dc), (Tp, Tc), (Hp, Hc)) in permutations(s[t], 3):
          # but D gives 2 coins from his change to T and H
          for (gT, gH) in combinations(Dc, 2):
            if gT in Tp and gH in Hp:
              # output solution
              fmt = lambda s: join(s, sep='+')
              printf(
                "amount={x} [D pays {Dp} change {Dc}; {gT} -> T pays {Tp} change {Tc}; {gH} -> H pays {Hp} change {Hc}]",
                Dp=fmt(Dp), Dc=fmt(Dc), Tp=fmt(Tp), Tc=fmt(Tc), Hp=fmt(Hp), Hc=fmt(Hc)
              )
    

    Solution: The item cost 83p.

    The minimum number of coins to pay for the item exactly is 5 (50p + 20p + 10p + 2p + 1p = 83p).

    Dick buys the first item, paying with one 100p coin. He receives change of 17p = 10p + 5p + 2p. So 4 coins are exchanged.

    Dick gives the 5p coin to Tom, who pays with 2 coins, 100p + 5p = 105p, and receives 20p + 2p = 22p as change. Again 4 coins are exchanged.

    Dick gives the 2p coin to Harry, who pays with 3 coins, 100p + 2p + 1p = 103p, and receives one 20p coin as change. Again 4 coins are exchanged.

    (Tom and Harry are indistinguishable, so there is also a solution where Dick gives the 5p coin to Harry and the 2p coin to Tom).

    If Dick didn’t need to help out Tom and Harry out using his own change it would be possible for the item to cost 84p, 86p or 87p, each of which takes 5 coins to pay for exactly, but Dick, Tom and Harry could each buy an item paying a different amount with a transaction that uses just 4 coins.

  2. Brian Gladman 19 June 2018 at 9:48 am
    from itertools import combinations_with_replacement as cwr
    from itertools import permutations, product
    from collections import defaultdict
    
    # the coin denominations
    denom = (200, 100, 50, 20, 10, 5, 2, 1)
     
    # find the minimum number of coins to pay amounts
    # less than 100 exactly (i.e. without change)
    def exact(amount):
      if not amount:
        return []
      else:
        for c in denom:
          if c <= amount:
            return [c] + exact(amount - c)
    a2minc = {x:len(exact(x)) for x in range(1, 100)}
    
    # now find the minimum number of coins exchanged
    # in paying sums less than 100
    a2mc = defaultdict(lambda:defaultdict(list))
    # consider increasing numbers of coins exchanged
    for nc in range(1, max(a2minc.values())):
      # the number of coins given in payment (nc - ng in change)
      for ng in range(1, nc + 1):
        # now find combinations of coins given and coins recieved 
        # in change for each amount less than 100, including only
        # combinations that use less coins than in paying exactly
        for cg, cr in product(cwr(denom, ng), cwr(denom, nc - ng)):
          sm = sum(cg) - sum(cr)
          # we must use less coins than in paying the exact amount
          if 0 < sm < 100 and nc < a2minc[sm]:
            a2mc[sm][nc].append((cg, cr))
    
    # consider amounts less than 100
    for am in sorted(a2mc.keys()):
      # we need the minimum number of coins for this amount
      cmin = a2mc[am][min(a2mc[am])]
      # ... and there must be at least three different ways of paying
      if len(cmin) >= 3:
        # consider possible coins given and coins received for Dick, Harry and Tom
        for (dg, dr), (hg, hr), (tg, tr) in permutations(cmin, 3):
          # find coins in Dick's change that are in what Tom and Harry give
          t, h = set(dr).intersection(hg), set(dr).intersection(tg)
          # Tom and Harry each use one of coins in Dick's change  
          if len(t) == len(h) == 1 and len(t | h) == 2:
            print(f'amount {am}; D[{dg}, {dr}]; H[{hg}, {hr}]; T[{tg}, {tr}]')
    

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: