S2T2

Jim Randell 9:08 am on 29 July 2021 Permalink Reply
Tags: by: Des MacHale ( 11 )   

• 

  Jim Randell 9:09 am on 29 July 2021 Permalink | Reply

  The original rectangle is cut from an A4 sheet of card (dimensions = 21.0cm × 29.7cm).

  The maximum square that we can make would be 21cm × 21cm, which puts an upper limit on Jack’s age. However the area of an A4 sheet places a smaller upper limit on Jack’s age, as the sum of the area of the pieces for age 10 would be 715cm² – larger than the area of a single A4 sheet.

  This Python program considers possible ages, and calculates the total area of the rectangular pieces. It then looks for possible dimensions and perimeters for packed rectangles. And looks for two of these that could be the setters and Jack’s rectangles. It then uses the rectpack.py library (see: Enigma 1491, Teaser 2650, Teaser 3069) to attempt to pack the pieces into the required rectangle.

  It runs in 1.94s.

  Run: [ @replit ]

  from enigma import irange, divisors_pairs, cached, printf
  from rectpack import pack_tight, output_grid, by_area
  
  # how to pack a set of rectangles
  pack = lambda x, y, rs: pack_tight(x, y, by_area(rs))
  
  # look for a packing
  @cached
  def check(n, x, y):
    # collect the pieces
    ps = list((k, k) for k in irange(1, n))
    ps += list((k - 1, k) for k in irange(2, n))
  
    # attempt a packing
    printf("[n = {n} -> pack {x} x {y} ...]")
    for s in pack(x, y, ps):
      output_grid(x, y, s)
      return True
    printf("[-> no packing]")
    return False
  
  # total area
  t = 0
  for n in irange(1, 21):
    t += n * (2 * n - 1)
    if t > 624: break
  
    printf("[n={n}; t={t}]")
  
    # find possible dimensions and perimeter for the packed rectangles
    rs = dict(((a, b), 2 * (a + b)) for (a, b) in divisors_pairs(t) if not(n > a))
  
    # consider the setter's rectangle
    for ((a1, b1), p1) in rs.items():
      # it must fit on an A4 sheet
      if a1 > 21 or b1 > 29: continue
  
      # and look for another rectangle, with a smaller perimeter
      for ((a2, b2), p2) in rs.items():
        if not(p2 < p1): continue
  
        # check packing is possible
        if check(n, a1, b1) and check(n, a2, b2):
          # output solution
          printf("n={n}: {a1}x{b1} (p={p1}) -> {a2}x{b2} (p={p2}) [*** SOLUTION ***]")
  

  Solution: The original rectangle measured 12cm × 21cm.

  Here is a diagram of the two packings (12×21 → 14×18):

  

  There will be many more different packings, as any sub-rectangle consisting of two (or more) pieces can be flipped round. (In fact there are 5156 different packings for the 12×21 rectangle, and 1307 for the 14×18 rectangle).

  ---

  The program assumes that the original rectangle was cut parallel to the sides of the A4 sheet, so the smaller side must be no more than 21cm and the longer side no more than 29cm. But rectangles with a dimension larger than these could potentially be made by cutting a rectangle not aligned with the sides. (e.g. We could cut a 7×30 rectangle obliquely from a sheet of A4).

  So there are potentially two possible ages, listed here along with possible rectangles (and perimeters):

  n=7: 7×36 (86), 9×28 (74), 12×21 (66), 14×18 (64)
  n=9: 15×35 (100), 21×25 (92)

  It is not possible to pack the 7×36 or 9×28 rectangles, so there are only 2 viable solutions:

  n=7: 12×21 (66) → 14×18 (64)
  n=9: 15×35 (100) → 21×25 (92)

  In the n=7 case the 12×21 rectangle can easily be cut from an A4 sheet (with a single cut), so this is a viable solution. (Note that as it is possible to cut the 9×28 rectangle from an A4 sheet, we need to show that it cannot be packed in order to rule out multiple solutions).

  In the n=9 case the 15×35 rectangle cannot be cut from an A4 sheet (even obliquely), so this is not a viable solution. (Although the 21×25 rectangle could be cut from an A4 sheet (again with a single cut), the puzzle requires that the rectangle with the larger perimeter be cut out from the A4 sheet).

  LikeLike

  • 

    Frits 2:48 pm on 30 July 2021 Permalink | Reply

    @Jim,

    Checking combination 9 x 28 takes a long time.

    Running time will be under half a second (with CPython) if you add the following to function check (or incorporate it in rectpack.py):

     
    # skip if stacked wide pieces exceed height
    if sum(min(a, b) for a, b in ps if 2 * min(a, b) > x) > y: 
      return False
    

    LikeLike

    • 

      Jim Randell 11:42 am on 31 July 2021 Permalink | Reply

      @Frits: Thanks for the suggestion.

      I’ve added a [[ pack() ]] function to rectpack.py that does a couple of quick checks before starting the packing.

      (And I also added [[ pack_uniq() ]] which generates solutions that are symmetrically distinct, see: Teaser 3069).

      LikeLike