Enigmatic Code

Programming Enigma Puzzles

Puzzle #52: Bus change

From New Scientist #3275, 28th March 2020 [link] [link]

I am about to get on the bus, but I don’t have the exact money for the £1 fare. The driver doesn’t give change so I hand over more than £1 and they keep the excess.

Once I have sat down, I realise that even though I didn’t hand over all my coins, the amount of money I had with me was the largest possible amount I could have had in change without being able to pay £1 (or any multiple of £1) exactly.

How much did I have?

[puzzle#52]

5 responses to “Puzzle #52: Bus change

  1. Jim Randell 28 March 2020 at 9:19 am

    We can’t use any coin that is a multiple of £1, so the denominations we are left with are: 50p, 20p, 10p, 5p, 2p, 1p. (The 25p crown isn’t in common circulation).

    Using a “greedy” strategy we can write down a collection of coins that seems like a reasonable maximum.

    I also wrote a program that verifies that this is indeed the maximum possible by exhaustive search:

    Run: [ @repl.it ]

    from enigma import Accumulator, printf
    
    # generate collections of coins worth more than 100, but can't make 100
    # ds = denominations
    # cs = coins available
    # ss = change that can be made
    def solve(ds, cs=[], ss=set([0])):
      if ds:
        # try adding an extra coin
        d = ds[0]
        s = set(d + x for x in ss)
        if 100 not in s:
          cs1 = cs + [d]
          t = sum(cs1)
          if t > 100: yield (t, cs1)
          yield from solve(ds, cs1, ss.union(s))
        # try a different denomination
        yield from solve(ds[1:], cs, ss)
    
    # find the maximum amount of change
    r = Accumulator(fn=max)
    
    for (t, cs) in solve([50, 20, 10, 5, 2, 1]):
      r.accumulate_data(t, cs)
    
    printf("max = {r.value} {r.data}")
    

    Solution: You had £1.43.

    The amount is composed of: 1× 50p, 4× 20p, 1× 5p, 4× 2p.

    Although you cannot make £1 exactly you can make £1.01, so you don’t lose out too badly.

    • Jim Randell 3 April 2020 at 11:59 am

      The “greedy” strategy it to start with the largest denomination coin, and add as many copies of that coin to the collection of coins, provided that doesn’t mean you can make exactly £1 from the collection. Then move on to the next largest denomination.

      Manually we add: 1× 50p, 4× 20p, 0× 10p, 1× 5p, 4× 2p, 0× 1p = 143p.

      Here it is as a program:

      from enigma import subsets, printf
      
      # greedy algorithm
      def greedy(ds, n):
        cs = list()
        while ds:
          d = ds.pop(0)
          while True:
            if all(sum(s) + d != n for s in subsets(cs, select="mC")):
              cs.append(d)
            else:
              break
        return cs
      
      cs = greedy([50, 20, 10, 5, 2, 1], 100)
      printf("total = {sum(cs)} {cs}")
      
  2. GeoffR 3 April 2020 at 3:07 pm

    Out of interest, I tried to look at the numerical data in the Accumulator for Puzzle 52 – but a straight print out had two instances of squeezed text, so not possible easily. In both cases there were 130+ lines of squeezed text which, if expanded, would have stalled the monitor display.

    I therefore thought I might add a dictionary to Jim’s 1st posting to see how the number of coin values varied between 101p and 143p.

    The code extra lines below made the number of coin distributions clear for the totals:

    # Code before Line 20 (1st posting) applies
    # Line 20 - find the maximum amount of change
    r = Accumulator(fn=max)
    
    from collections import defaultdict    # add extra line
    D = defaultdict(list)    # add extra line
    
    for (t, cs) in solve([50, 20, 10, 5, 2, 1]):
      D[t]+= [cs]     # add extra line
      r.accumulate_data(t, cs)
    
    printf("max = {r.value} {r.data}")
    
    # add two extra lines
    for k,v in sorted(D.items()):
      print(f" Value(pence) = {k}, Number of ways to make value = {len(v)}")
    
    '''
    max = 143 [50, 20, 20, 20, 20, 5, 2, 2, 2, 2]
     Value(pence) = 101, Number of ways to make value = 147  # explains' squeezed lines'
     Value(pence) = 103, Number of ways to make value = 147  # ditto
     Value(pence) = 110, Number of ways to make value = 1
     Value(pence) = 111, Number of ways to make value = 1
     Value(pence) = 112, Number of ways to make value = 2
     Value(pence) = 113, Number of ways to make value = 2
     Value(pence) = 114, Number of ways to make value = 3
     Value(pence) = 115, Number of ways to make value = 4
     Value(pence) = 116, Number of ways to make value = 5
     Value(pence) = 117, Number of ways to make value = 6
     Value(pence) = 118, Number of ways to make value = 7
     Value(pence) = 119, Number of ways to make value = 8
     Value(pence) = 121, Number of ways to make value = 1
     Value(pence) = 123, Number of ways to make value = 1
     Value(pence) = 130, Number of ways to make value = 1
     Value(pence) = 131, Number of ways to make value = 1
     Value(pence) = 132, Number of ways to make value = 2
     Value(pence) = 133, Number of ways to make value = 2
     Value(pence) = 134, Number of ways to make value = 3
     Value(pence) = 135, Number of ways to make value = 4
     Value(pence) = 136, Number of ways to make value = 5
     Value(pence) = 137, Number of ways to make value = 6
     Value(pence) = 138, Number of ways to make value = 7
     Value(pence) = 139, Number of ways to make value = 8
     Value(pence) = 141, Number of ways to make value = 1
     Value(pence) = 143, Number of ways to make value = 1
    '''
    

    Jim has pointed out to me that using multiset (after importing it) from Enigma.py library, it
    is also possible to look at the number of ways coin totals can occur, again modifying the last part of the 1st posting::

    # previous lines of code applicable in 1st posting
    # find the maximum amount of change, and number of ways for each amount
    r = Accumulator(fn=max)
    m = multiset() # [modified]
    
    for (t, cs) in solve([50, 20, 10, 5, 2, 1]):
      r.accumulate_data(t, cs)
      if r.value == t: printf("[{t} -> {cs}]")
      m.add(t) # [modified]
    
    printf("max = {r.value} {r.data}")
    
    # [modified]
    for k in sorted(m.keys()):
      printf("total = {k} -> {m[k]} ways")
    
    
  3. J. Pijnenburg 5 April 2020 at 11:12 am

    The author of this puzzle is clearly UK-centric, therefore not informing the international readers of the actual denominations that are legal tender. Not knowing the actual denominations, I checked Wikipedia and found that the present legal tender denomination are 1, 2, 5, 20, 25, 50p and 1 and 2 pounds.
    The passenger might be carrying one 50, one 25p, 4 20p and 4 2p-coins. That would bring the total to 1.63. Hopefully I do not make a silly mistake.
    Funny that by adding a denomination, you make it more difficult to get to the correct amount.

    • Jim Randell 5 April 2020 at 11:30 am

      Yes, if you add a 25p coin to the allowable denominations then 163p is the maximum.

      The greedy strategy gives you: 1×50p, 1×25p, 4×20p, 4× 2p.

      But it can also be made as: 3×25p, 4×20p, 4× 2p.

      I live in the UK and can say you never see a 25p crown being used to make purchases. They are special limited edition coins for collectors.

      Even though New Scientist is a UK based magazine, the setter of the puzzle should really have mentioned the denominations we should consider (especially in the International Edition).

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: