S2T2

Jim Randell 4:56 pm on 16 July 2021 Permalink Reply
Tags: by: Peter Good ( 27 )   

• 

  Jim Randell 5:19 pm on 16 July 2021 Permalink | Reply

  I reused the code from rectpack.py, originally written for Enigma 1491, and also used in Teaser 2650.

  Each solution also appears rotated, reflected, and rotated and reflected, so the total number of solutions found is 4× the answer.

  The following Python program runs in 199ms.

  Run: [ @replit ]

  from enigma import (irange, ediv, printf)
  from rectpack import (pack, output_grid)
  
  # width/height of the tray
  (X, Y) = (15, 16)
  
  # rectangles
  rs = list((x, x + 1) for x in irange(1, 8))
  
  # count the solutions
  n = 0
  for (i, s) in enumerate(pack(X, Y, rs), start=1):
    printf("{i}: {s}")
    output_grid(X, Y, s, end="")
    n += 1
  
  printf("age = {x}", x=ediv(n, 4))
  

  Solution: Clark was 10.

  The 10 solutions arise due to the following 2 packings:

  

  The first has 3 (coloured) sub-rectangles that can be flipped over, giving 2×2×2 = 8 packings.

  The second has only 1 sub-rectangle, so gives 2 packings.

  LikeLike

  • 

    Jim Randell 6:32 pm on 16 July 2021 Permalink | Reply

    And here is an alternate version that calculates a canonical form for each solution, and counts the number of different canonical forms.

    Run: [ @replit ]

    from enigma import (irange, printf)
    from rectpack import (pack, output_grid)
    
    # width/height of the tray
    (X, Y) = (15, 16)
    
    # rectangles
    rs = list((x, x + 1) for x in irange(1, 8))
    
    # rotation / reflection
    rotate = lambda s: tuple(sorted((X - x - w, Y - y - h, w, h) for (x, y, w, h) in s))
    reflect = lambda s: tuple(sorted((X - x - w, y, w, h) for (x, y, w, h) in s))
    
    # canonical form of s
    def canonical(s):
      s = tuple(sorted(s))
      r = rotate(s)
      return min(s, r, reflect(s), reflect(r))
    
    # count the canonical forms
    ss = list()
    for (i, s) in enumerate(pack(X, Y, rs), start=1):
      r = canonical(s)
      if r not in ss:
        ss.append(r)    
        printf("{i} -> {x}", x=len(ss))
        output_grid(X, Y, s)
      else:
        printf("{i} -> {x}", x=ss.index(r) + 1)
      printf()
    
    printf("age = {x}", x=len(ss))
    

    LikeLike

• 

  Frits 12:31 pm on 19 July 2021 Permalink | Reply

  With analysis to place the biggest piece in top left corner.

  This program ran in 181ms.

   
  from itertools import product
  
  (X, Y) = (15, 16)        # width/height of the tray
  M = 9                    # longest side of rectangle
  
  # return grid coordinates (top left, bottom right) where piece w x h will fit
  def grid_coords(grid, w, h):
    res = []
    for i in range(M, X + M):
      for j in range(M, Y + M):
        if grid[i][j] == 0:
          # horizontal and vertical
          for k in range(2):
            if all(grid[x][y] == 0 for x in range(i, i + h)
                                   for y in range(j, j + w)):
             res.append([(i - M, j - M), (i - M + h - 1, j - M + w - 1)])
  
            (w, h) = (h, w)   # mirror
    return res       
  
  # print grid without borders   
  def grid_print(grid):
    for i, g in enumerate(grid):
      if M <= i < Y + M - 1:
        print(f"{g[M:-M]}")   
    print()   
  
  # fit k pieces into empty spots in the grid   
  def fit(r, k, s):
    if k == 1:
      # check if last piece fits
      coords = grid_coords(s, r[0][0], r[0][1])
      if coords:
        (tl, rb) = (coords[0][0], coords[0][1])
        for (i, j) in product(range(tl[0], rb[0] + 1), range(tl[1], rb[1] + 1)):
          s[i + M][j + M] = k   
        yield [r.copy() for r in s]       # return copy !!
        # backtrack
        for (i, j) in product(range(tl[0], rb[0] + 1), range(tl[1], rb[1] + 1)):
          s[i + M][j + M] = 0
    else:
      (w, h) = r[0]   # pick first remaining piece from list
      for tl, rb in grid_coords(s, w, h):
        if k == N:
          # only allow the biggest piece 9x8 mostly in the top left quadrant
          # in order to prevent rotated or reflected versions
          #
          # if biggest piece is not in the top left corner (not touching (0, 0)):
          # - if biggest piece lies vertical then placing the 8x7 piece
          #   results in a 9x1 stroke --> impossible
          # - if biggest piece lies horizontal there is a stroke 8xa to the left
          #   and a stroke 8xb to the left (where a + b = 7)
          #   strokes of 8x1, 8x2 or 8x3 are impossible to fill --> impossible
        
          if tl != (0, 0): continue
       
        # update piece in the grid s
        for (i, j) in product(range(tl[0], rb[0] + 1), range(tl[1], rb[1] + 1)):
          s[i + M][j + M] = k   
      
        yield from fit(r[1:], k - 1, s)  
        # backtrack
        for (i, j) in product(range(tl[0], rb[0] + 1), range(tl[1], rb[1] + 1)):
          s[i + M][j + M] = 0
         
       
  # rectangles (biggest first)
  rs = list((x, x + 1) for x in range(8, 0, -1))
  N = len(rs)
  
  # initialize grid with borders of size M
  grid = [[9 for i in range(Y + 2 * M)] for j in range(X + 2 * M)]
  # initialize inner grid to 0
  for i in range(X):
    for j in range(Y):
      grid[i + M][j + M] = 0
         
  # generate solutions
  sols = list(fit(rs, N, grid))   
  
  print("Clark was", len(sols), "years old. \n\nexample:\n")
  grid_print(sols[0])
  

  LikeLike