# Enigmatic Code

Programming Enigma Puzzles

## Puzzle #24: Three stamps

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)
```

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