S2T2

Jim Randell 9:19 am on 28 January 2021 Permalink Reply
Tags: by: N A Phillips ( 5 )   

• 

  Jim Randell 9:20 am on 28 January 2021 Permalink | Reply

  I assumed the denominations of the stamps were all positive integer values.

  We can place lower and upper limits on the values of the stamps.

  The stamps are ordered: B > R > G > V > Y, which gives minimum values of: 5, 4, 3, 2, 1.

  And 5 black stamps are used in making a value of 100, so black must have a value of less than (100 − (3 + 3×2)) / 5 = 18.2.

  Similarly, 5 green stamps are used in making a value of 50, so green must have a value of less than (50 − (5 + 4 + 2 + 1)) / 5 = 7.6.

  So we can write down the following ranges for each denomination:

  B: 5..18
  R: 4..17
  G: 3..7
  V: 2..6
  Y: 1..5

  And we have three equations relating the values. So choosing values for V and Y will give us a set of 5 simultaneous equations that can be solved to find the other values.

  This Python program use the [[ matrix.linear() ]] solver for systems of linear equations from the enigma.py library. It runs in 63ms.

  Run: [ @repl.it ]

  from enigma import (irange, subsets, matrix, as_int, express, group, printf)
  
  # choose values for Y and V
  for (Y, V) in subsets(irange(1, 6), size=2):
  
    # make the equations
    eqs = [
      # B  R  G  V  Y = ???
      ((5, 0, 1, 3, 0), 100), # 100-pim parcel
      ((1, 2, 2, 2, 2),  50), # 1st 50-pim parcel
      ((1, 1, 5, 1, 1),  50), # 2nd 50-pim parcel
      ((0, 0, 0, 0, 1),   Y), # Y value
      ((0, 0, 0, 1, 0),   V), # V value
    ]
  
    # solve the equations for integer values
    # (either matrix.linear() or as_int() may raise a ValueError)
    try:
      (B, R, G, V, Y) = (as_int(x) for x in matrix.linear(*zip(*eqs)))
    except ValueError:
      continue
  
    # check ordering
    if not (B > R > G > V > Y > 0): continue
  
    # find combinations that make 50, grouped by the total number of stamps
    d = group(express(50, [Y, V, G, R, B]), by=sum)
    # output minimal configurations
    k = min(d.keys())
    for (y, v, g, r, b) in d[k]:
      printf("{k} stamps; 50 = {b}x {B} (black), {r}x {R} (red), {g}x {G} (green), {v}x {V} (violet), {y}x {Y} (yellow)")
  

  Solution: A 50-pim parcel can be sent using 5 stamps: 2 black, 1 red, 1 green, 1 yellow.

  The values of the stamps are:

  black = 18 pim
  red = 9 pim
  green = 4 pim
  violet = 2 pim
  yellow = 1 pim

  So each stamp is half (rounded down) the next highest value.

  There are 621 different ways to make 50 using the above denominations.

  ---

  Here’s a manual derivation of the denominations:

  [1] B + 2R + 2G + 2V + 2Y = 50
  [2] B + R + 5G + V + Y = 50

  Taking 2×[2] − [1] gives:

  B + 8G = 50

  And we know G is in the range 3 .. 7, and B is in the range 5 .. 18 and G < B:

  G = 3 ⇒ B = 26 [not possible]
  G = 4 ⇒ B = 18
  G = 5 ⇒ B = 10
  G = 6 ⇒ B = 2 [not possible]
  G = 7 ⇒ B = −6 [not possible]

  And:

  5B + G + 3V = 100

  Where V is in the range 2 .. 6 and V < G:

  G = 4, B = 18 ⇒ V = 2
  G = 5, B = 10 ⇒ V = 15 [not possible]

  So we have: V = 2, G = 4, B = 18.

  From which we see Y = 1, and R = 9.

  LikeLike

  • 

    Jim Randell 5:55 pm on 28 January 2021 Permalink | Reply

    Here’s a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library. It runs in 122ms.

    It operates in base 19 as B ≤ 18.

    The only other restriction I used was that we already know that 50 is possible with 9 stamps, so I limit the numbers used for any single denomination to 8. (We can also do this in my Python program above, by passing [[ qs=irange(0, 8) ]] to the call to [[ express() ]] and that saves a little bit of time).

    We could restrict the other denominations in line with the ranges given above, but it is not necessary for a decent run time.

    Run: [ @repl.it ]

    #! python -m enigma -rr
    
    SubstitutedExpression
    
    --base=19
    --symbols="BRGVYbrgvy"
    --distinct="BRGVY"
    
    # work out the denominations
    "Y > 0"
    "V > Y"
    "G > V"
    "R > G"
    "B > R"
    
    "5 * B + G + 3 * V == 100" # 100 pim parcel
    "B + 2 * (R + G + V + Y) == 50" # 1st 50 pim parcel
    "5 * G + (B + R + V + Y) == 50" # 2nd 50 pim parcel
    
    # find minimal amount to make 50
    "b * B + r * R + g * G + v * V + y * Y == 50"
    
    --answer="((b, r, g, v, y), (B, R, G, V, Y))"
    --code="fmin = lambda ss: min(ss, key=unpack(lambda ns, ds: sum(ns)))"
    --accumulate="fmin"
    
    --verbose=16
    
    # [optional] we already know 50 is possible with 9 stamps
    --invalid="9-18,brgvy"
    

    LikeLike

• 

  Frits 12:24 pm on 28 January 2021 Permalink | Reply

  from enigma import SubstitutedExpression
  
  # the alphametic puzzle
  p = SubstitutedExpression(
    [
    # try to avoid looping over BL and RE
    "G > V",
    "V > Y",
    # (5, 0, 1, 3, 0)  100-pim parcel
    "(100 - G - 3*V) // 5 = BL",
    
    # (1, 2, 2, 2, 2)  1st 50-pim parcel
    "(50 - BL) // 2  - (G + V + Y) = RE",
    "RE > G",
    "BL > RE",
    # (1, 1, 5, 1, 1)  2nd 50-pim parcel
    "BL + RE + 5*G + V + Y = 50",
    
    # Pick M blacks, N reds, O greens, P violets and Q yellows
    # we already know a 50-pim parcel can be formed with 9 stamps
    "M + N < 10",
    "M + N + O < 10",
    "M + N + O + P < 10",
    "M + N + O + P + Q < 10",
    
    "M*BL + N*RE + O*G + P*V + Q*Y = 50", 
    ],
    answer="M + N + O + P + Q, M, N, O, P, Q",
    distinct="",
    accumulate=min,
    # BL: 5..18  RE: 4..12  G: 3..7  V: 2..6  Y: 1..5 
    d2i=dict([(0, "GVY")] + 
             [(1, "VG")] + 
             [(2, "RBG")] + 
             [(k, "RB") for k in range(3, 6)] +
             [(6, "YRB")] +
             [(7, "YVRB")] +
             [(k, "YVGRBMNOPQ") for k in range(8, 10)]),
  
    reorder=0,
    verbose=0
    )   
    
    
  # solve the puzzle
  r = p.run()
  
  colors = ["black", "red", "green", "violet", "yellow"]
  for (x, y) in zip(list(r.accumulate)[1:], colors):
    if x > 0:
      print(x, y)
  

  LikeLike

• 

  GeoffR 3:04 pm on 28 January 2021 Permalink | Reply

  % A Solution in MiniZinc
  include "globals.mzn";
  
  % black, red, green, violet, yellow stamps
  % ... using Jim's analysis values for all stamp ranges
  var 5..18:B; var 4..17:R; var 3..7: G;
  var 2..6: V; var 1..5:Y;
  
  % stamp values all different and in colour descending values
  constraint all_different([B, R, G, V, Y]);
  constraint B > R /\ R > G /\ G > V /\ V > Y;
  
  % numbers of each colour of stamp to make 50 pim
  var 0..9:NumB; var 0..9:NumG; var 0..9:NumV;
  var 0..9:NumR; var 0..9:NumY;
  
  % three stamp equations stated in teaser description
  % 1. 5 black, one green, and 3 violet stamps for 100 pim
  constraint 5*B + G + 3*V == 100;
  
  % two different equations for stamps of 50 pim
  % 2. one set consisted of 1 black and 2 of each of the other colours
  constraint B + 2*R + 2*G + 2*V + 2*Y == 50;
  
  % 3. other set contained 5 green and 1 of each of other colours 
  constraint B + R + 5*G + V + Y == 50;
  
  % General equation to make 50 pims value
  constraint NumB*B + NumR*R +  NumG*G + NumV*V + NumY*Y == 50;
  
  % minimise total number of coins used to make 50 units value
  solve minimize(NumB + NumR + NumG + NumV + NumY);
  
  output [ "Black stamp value = " ++ show(B) ++ " pim"
  ++ ", Red stamp value = " ++ show(R) ++ " pim"
  ++ "\n" ++ "Green stamp value = " ++ show(G) ++ " pim"
  ++ ", Violet stamp value = " ++ show(V) ++ " pim"
  ++ "\n" ++ "Yellow stamp value = " ++ show(Y) ++ " pim"
  ++ "\n"
  ++ "\n" ++ "Smallest number of stamps needed for a 50-pim parcel" 
  ++ "\n" ++ "[B, R, G, V, Y] =  "
  ++ show (NumB),", ",show(NumR),", ",show(NumG),", ",show(NumV),", ",show(NumY) ];
  
  % Black stamp value = 18 pim, Red stamp value = 9 pim
  % Green stamp value = 4 pim, Violet stamp value = 2 pim
  % Yellow stamp value = 1 pim
  
  % Smallest number of stamps needed for a 50-pim parcel
  % [B, R, G, V, Y] =  2, 1, 1, 0, 1
  % ----------
  % ==========
  
  
  
  

  LikeLike

• 

  John Crabtree 12:07 am on 29 January 2021 Permalink | Reply

  Eq. 1: 5.B + 0.R + 1.G +3.V + 0.Y = 100
  Eq. 2: 1.B + 2.R + 2.G +2.V + 2.Y = 50
  Eq. 3 : 1.B + 1.R + 5.G +1.V + 1.Y = 50
  10 * Eq. 3 – 5 * Eq. 2 – Eq. 1 gives 39.G – 3.V = 150, or 13.G – V = 50
  Assuming integer solutions, G = 4, V = 2 and then B = 18, R + Y = 10 etc

  LikeLike