Enigmatic Code

Programming Enigma Puzzles

Puzzle #24: Three stamps

From New Scientist #3250, 5th October 2019 [link] [link]

I’m on holiday in the lovely country of Philitaly, and planning to send plenty of postcards because postage is very cheap. But the country only allows up to three stamps on any letter.

Can you tell me which three denominations of stamps would allow me to cover any cost of postage from 1 cent to 15 cents inclusive?

And which four stamp denominations would allow all values from 1 to 24 cents?

[puzzle#24]

6 responses to “Puzzle #24: Three stamps

  1. Jim Randell 5 October 2019 at 8:49 am

    The following Python program calculates the smallest value that it is not possible to make using only three stamps of given denominations. It then looks for sets of denominations that satisfy the requirements of the puzzle. It runs in 101ms.

    Run: [ @repl.it ]

    from enigma import subsets, irange, inf, printf
    
    # find the smallest value that can not be made
    # using no more than <k> of each denomination in <ds>
    def solve(k, ds):
      # calculate possible totals
      ts = set(sum(s) for s in subsets(ds, min_size=1, max_size=k, select="R"))
      # find the first total not in s
      for t in irange(1, inf):
        if t not in ts: return t
    
    # find n denominations that allow me to make amounts from 1 to t
    def find(n, t, k):
      for ds in subsets(irange(2, t - 1), size=n - 1):
        ds = (1,) + ds
        r = solve(k, ds)
        if r < t + 1: continue
        yield (ds, r)
    
    # solve both parts of the puzzle
    for (n, t) in [(3, 15), (4, 24)]:
      for (ds, r) in find(n, t, 3):
        printf("{ds} -> {r}")
        break
    

    Solution: Denominations of (1, 4, 5) can make values from 1 to 15. Denominations of (1, 4, 7, 8) can make values from 1 to 24.

    The smallest denomination needs to be 1, and if the largest possible amount is made from the 3 copies of the largest denomination then that denomination needs to be a third of the largest possible amount.

  2. Thomas Knight 18 October 2019 at 5:05 pm

    So. Where is enigma and can I install it with pip?

  3. arthurvause 19 October 2019 at 7:42 pm

    By coincidence (or possibly not), both the September and October puzzles from IBM Ponder This are “change making” puzzles.

    My solution to Three Stamps is adapted from my solution to the October Ponder This, which in turn is adapted from the Dynamic Programming section of pythonDS, https://runestone.academy/runestone/books/published/pythonds/Recursion/DynamicProgramming.html

    from itertools import combinations
    
    # starting point for change making search is a solution with all pennies
    allpennies = [ [1]*n for n in xrange(100) ]
    
    def MakeChange(denoms, maxcoins):
      bestchange = allpennies[:]
    
      for amt in xrange(1,100):
        bestlen = len(bestchange[amt])
        for d in denoms:
          if d > amt:
            break
          if bestlen > 1 + len(bestchange[amt-d]):
            bestchange[amt] = bestchange[amt-d][:]
            bestchange[amt].append(d)
            bestlen = len(bestchange[amt])
        if bestlen > maxcoins:
          break
        
      return bestchange[:amt]
    
    def findsolutions(maxvalue, maxdenoms, maxcoins):
      for s in combinations(range(2,maxvalue+1),maxdenoms-1):
        denoms = (1,)+ s
        mc = MakeChange(denoms , maxcoins)
        if len(mc) >= maxvalue+1:
          print "\n", maxvalue, denoms
            
    findsolutions(15,3,3)
    findsolutions(24,4,3)
    

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: