Sunday Times Teaser 3152 – Stamps of Approval

by BRG on February 18, 2023

by Colin Vout

Published Sunday February 19 2023 (link)

I really like the postcards that a friend of mine has sent me each of the last three years from her annual holiday in Farflung. Each card had six stamps on it, involving the same four denominations, and at least one of each denomination was present on each card. These four denominations were all different and coloured differently, and of course represented whole numbers of pecahans. I can’t read what the denominations are, but my friend had remarked the postage totals for the three years were 23, 32 and 36 pecahans.

What were the four denominations, in decreasing order?

From → Uncategorized

4 Comments Leave one →

Brian Gladman permalink


from itertools import combinations_with_replacement as cr

# the postage costs for the three years
costs = (23, 32, 36)

# generate sequences of <n> incrceasing integers that sum to <v>
def partition(v, n, seq=()):
  if n == 1 and (not seq or v > seq[-1]):
    yield seq + (v, )
  else:
    for x in range(1 if not seq else seq[-1] + 1, v + 1):
      yield from partition(v - x, n - 1, seq + (x, ))  

# consider possible sums for the four different stamps
for s in range(10, costs[0] - 1):
  # and consider possible stamps with these sums 
  for stamps in partition(s, 4):
    # collect combinations of two stamps that combine with
    # the four others to give one of the three postage costs
    c4, ds = sum(stamps), [[], [], []]
    for i, c6 in enumerate(costs):
      ds[i] = tuple(s2 for s2 in cr(stamps, 2) if sum(s2) + c4 == c6) 
    
    # it must be possible to make all three postage costs
    if all(ds):
      # collect numbers of each stamp (high to low)
      cnts = list(tuple((stamps + s2).count(s) for s in stamps[::-1])
                for d in ds for s2 in d)
      
      print(f"Stamps: {stamps[::-1]}")
      for c, cs in zip(costs, cnts):
        print(f" {c}:    {cs[0] if len(cs) == 1 else cs}")

from itertools import combinations_with_replacement as cr

# the postage costs for the three years

costs = (23, 32, 36)

# generate sequences of <n> incrceasing integers that sum to <v>

def partition(v, n, seq=()):

if n == 1 and (not seq or v > seq[-1]):

yield seq + (v, )

else:

for x in range(1 if not seq else seq[-1] + 1, v + 1):

yield from partition(v - x, n - 1, seq + (x, ))

# consider possible sums for the four different stamps

for s in range(10, costs[0] - 1):

# and consider possible stamps with these sums

for stamps in partition(s, 4):

# collect combinations of two stamps that combine with

# the four others to give one of the three postage costs

c4, ds = sum(stamps), [[], [], []]

for i, c6 in enumerate(costs):

ds[i] = tuple(s2 for s2 in cr(stamps, 2) if sum(s2) + c4 == c6)

# it must be possible to make all three postage costs

if all(ds):

# collect numbers of each stamp (high to low)

cnts = list(tuple((stamps + s2).count(s) for s in stamps[::-1])

for d in ds for s2 in d)

print(f"Stamps: {stamps[::-1]}")

for c, cs in zip(costs, cnts):

print(f" {c}: {cs[0] if len(cs) == 1 else cs}")

John Z permalink


from itertools import combinations
from itertools import product

# min stamp value: 1
# max stamp value: 15: 1.3 + 2.1 + 3.1 + 15.1 = 23

# targets for stamp total of 6 stamps
s6 = (23, 32, 36)

# max multiplier value: 3 for example: stamps 'aaabcd'
# create list of possible multipliers of each stamp
mm = tuple(m for m in product(range(1, 4), repeat = 4) if sum(m) == 6)

# consider combinations of 4 stamp values from 15 to 1 (for decreasing order)
for sv in combinations(range(15, 0, -1), 4):
 
  mx = [()] * 3 # initialise empty list of stamp multiples

  # consider how many of each stamp
  for m in mm:

    # total postage
    tp = sum(a * b for a, b in zip(sv, m))
    
    # is the total postage in the target list?
    if tp in s6:
      mx[s6.index(tp)] = m # insert successful multipliers
      
  if all(mx): # Can each postage value be made up?
    print('stamps:', sv, *['\n    ' + str(ss)[1:-1] for ss in zip(s6, mx)])

from itertools import combinations

from itertools import product

# min stamp value: 1

# max stamp value: 15: 1.3 + 2.1 + 3.1 + 15.1 = 23

# targets for stamp total of 6 stamps

s6 = (23, 32, 36)

# max multiplier value: 3 for example: stamps 'aaabcd'

# create list of possible multipliers of each stamp

mm = tuple(m for m in product(range(1, 4), repeat = 4) if sum(m) == 6)

# consider combinations of 4 stamp values from 15 to 1 (for decreasing order)

for sv in combinations(range(15, 0, -1), 4):

mx = [()] * 3 # initialise empty list of stamp multiples

# consider how many of each stamp

for m in mm:

# total postage

tp = sum(a * b for a, b in zip(sv, m))

# is the total postage in the target list?

if tp in s6:

mx[s6.index(tp)] = m # insert successful multipliers

if all(mx): # Can each postage value be made up?

print('stamps:', sv, *['\n ' + str(ss)[1:-1] for ss in zip(s6, mx)])

BRG permalink

Nice one John, straightforward and quite fast!

Reply

Frits permalink

Under 2 ms with PyPy.
Initial code has been generated with SubstitutedExpression() from Jim Randell’s enigma.py.


# check if we pick twice a number from <ns> that the sum can equal <t>
def check(t, ns):
  return any((t - n) in ns for n in ns)
      
# A <= 2 as (3, 4, 5, 6) can't make 23 
for A in [1, 2]:
  # B <= 5 as (x, 6, 7, 8) can't make 23 
  for B in range(A + 1, 6):
    # C <= 8 as (1, 2, 9, 10) can't make 23 
    for C in range(B + 1, 9):
      # D >= 7 as (3, 4, 5, 6) can't make 36
      # max stamp value: 15: 1.3 + 2.1 + 3.1 + 15.1 = 23
      for D in range(max(C + 1, 7), 16):
        ABCD = A + B + C + D
        if 2 * A + ABCD > 23: continue
        if ABCD + 2 * D < 36: continue
        # can we make x with A, B, C, D and 2 extra stamps out of A, B, C, D?
        if not check(23 - ABCD, {A, B, C, D}): continue
        if not check(36 - ABCD, {A, B, C, D}): continue
        if not check(32 - ABCD, {A, B, C, D}): continue
        
        print("answer:", (D, C, B, A))

# check if we pick twice a number from <ns> that the sum can equal <t>

def check(t, ns):

return any((t - n) in ns for n in ns)

# A <= 2 as (3, 4, 5, 6) can't make 23

for A in [1, 2]:

# B <= 5 as (x, 6, 7, 8) can't make 23

for B in range(A + 1, 6):

# C <= 8 as (1, 2, 9, 10) can't make 23

for C in range(B + 1, 9):

# D >= 7 as (3, 4, 5, 6) can't make 36

# max stamp value: 15: 1.3 + 2.1 + 3.1 + 15.1 = 23

for D in range(max(C + 1, 7), 16):

ABCD = A + B + C + D

if 2 * A + ABCD > 23: continue

if ABCD + 2 * D < 36: continue

# can we make x with A, B, C, D and 2 extra stamps out of A, B, C, D?

if not check(23 - ABCD, {A, B, C, D}): continue

if not check(36 - ABCD, {A, B, C, D}): continue

if not check(32 - ABCD, {A, B, C, D}): continue

print("answer:", (D, C, B, A))

Sunday Times Teaser 3152 – Stamps of Approval

by Colin Vout

Published Sunday February 19 2023 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta