S2T2

Jim Randell 9:21 am on 9 May 2021 Permalink Reply
Tags: by: F. Moore ( 2 )   

• 

  Jim Randell 9:21 am on 9 May 2021 Permalink | Reply

  (See also: Enigma 460).

  This Python program runs in 51ms.

  Run: [ @replit ]

  from enigma import (irange, inf, printf)
  
  # make k purchases from an (x, y) rectangle
  def solve(k, x, y, t, ss=[]):
    # perform checks:
    n = len(ss)
    # the 2nd purchase is divisible by 3 and is greater than 6
    if n == 2 and not (ss[1] > 6 and ss[1] % 3 == 0): return
    # the 4th purchase is the 2nd less 6
    if n == 4 and not (ss[3] == ss[1] - 6): return
    # the 5th purchase is divisible by 2
    if n == 5 and not (ss[4] % 2 == 0): return
    # the 6th purchase is (2/3) the 2nd
    if n == 6 and not (ss[5] * 3 == ss[1] * 2): return
    # after the 7th purchase 1/3 of the original sheet is sold
    if n == 7 and not (sum(ss) * 3 == t): return
    # the 12th purchase is half the 5th
    if n == 12 and not (ss[11] * 2 == ss[4]): return
  
    # are we done?
    if k == 0:
      yield ss
    else:
      if y > 1:
        # buy a row of x stamps
        yield from solve(k - 1, x, y - 1, t, ss + [x])
      if x > 1:
        # buy a column of y stamps
        yield from solve(k - 1, x - 1, y, t, ss + [y])
  
  # diagonal enumeration of (x, y) pairs, x > y
  def pairs(a, b):
    # consider the sum of the dimensions
    for t in irange(a, b):
      # values for y
      for y in irange(1, t // 2):
        yield (t - y, y)
  
  def run():
    # consider (x, y) rectangles
    for (x, y) in pairs(12, inf):
      # attempt 12 purchases
      for ss in solve(12, x, y, x * y):
        yield (x, y, ss)
  
  for (x, y, ss) in run():
    printf("x={x} y={y}: {ss} -> {t}", t=sum(ss))
    break
  

  Solution: The original sheet consisted of 21 × 18 stamps (= 378 stamps in total). Between them, the 12 customers purchased 208 stamps.

  The individual purchases were (1st – 12th): 21, 21, 21, 15, 20, 14, 14, 18, 18, 18, 18, 10.

  The following diagram shows one way the original sheet could have been sold. Each purchase is numbered, and the number of stamps bought is given in brackets.

  

  Initially there are 378 stamps in the sheet.

  After the first 7 purchases (shown in red) the yellow and green squares remain. A total of 252 stamps, which is 2/3 of the original 378 stamps, so 1/3 have been sold.

  After all 12 purchases (red and yellow) only the green squares remain. A total of 170 stamps, so 208 stamps have been sold in all.

  LikeLike

  • 

    Frits 10:41 am on 1 June 2021 Permalink | Reply

    You can already skip (x, y) combinations in run() if x * y is not a multiple of 3.

    LikeLike

• 

  Frits 11:20 am on 2 June 2021 Permalink | Reply

  Only one (x, y) rectangle is possible (without even considering purchases as the 6th).
  Second question is not dealt with.

  from enigma import irange
    
  # the 2nd purchase is divisible by 3 and is greater than 6
  # the 4th purchase is the 2nd less 6
  # the 5th purchase is divisible by 2
  # the 6th purchase is (2/3) the 2nd
  # after the 7th purchase 1/3 of the original sheet is sold
  # the 12th purchase is half the 5th
   
  # diagonal enumeration of (x, y) pairs, x > y
  def pairs(a, b):
    # consider the sum of the dimensions
    for t in irange(a, b):
      # values for y
      for y in irange(1, t // 2):
        yield (t - y, y)
        
  for (x, y) in pairs(12, 196):              # assume x < 100
    # consider x, y with y + 3 <= x <= y + 7 (purchase 2 and 4 rules)
    # and                x % 3 != 2          (purchase 2 rule)
    # purchase 7 rule makes x * y a multiple of 3
    if (x * y) % 3 or x < y + 3 or x > y + 7 or x % 3 == 2: continue
    
    # 2nd purchase comes from initial long side
    # 4th purchase comes from initial short side 
    for a in range(1, 7): 
      b = 7 - a
      # after the 7th purchase 1/3 of the original sheet is sold
      if (x - a) * (y - b) * 3 != 2 * (x * y): continue
         
      # if only 2nd purchase made from initial long side (b = 1)
      if b == 1:
        # 1st purchase is made from the initial short side 
        if (x - 1) % 3: continue
        
        # if y is odd then the 5th purchase is odd, impossible
        if y % 2: continue
        
        # purchases 3 - 7 must be equal to 2nd purchase - 6 (and even)
        # so 2nd purchase must be even as well
        if x % 2: continue
        
      
      # if only 4th purchase made from initial short side (a = 1)
      if a == 1:
        # x must be three higher than y (the 4th purchase is the 2nd less 6)
        if x != y + 3: continue
      
      # if initial long side is a multiple of 3 
      if x % 3 == 0: 
        # the 1st purchase must be made from the long side 
        # after the first 2 purchases the short side has decremented with 2
        if x > y + 4: continue    # 4th purchase rule
        
        if x == y + 4:
          # the 3rd purchase must be made from the initial short side 
          # (difference between sides may not become higher than 6)
          # so both sides after 4 purchases have decremented with 2
          if x % 2 and y % 2: continue    # 5th purchase must be even
     
      print(f"{(x, y) = } {(a, b) = } remaining {(x - a), (y - b) = }")
  
  # (x, y) = (21, 18) (a, b) = (3, 4) remaining (x - a), (y - b) = (18, 14)
  

  LikeLike