S2T2

Jim Randell 2:20 am on 20 October 2024 Permalink Reply
Tags: by: Victor Bryant ( 139 )   

• 

  Jim Randell 2:54 am on 20 October 2024 Permalink | Reply

  See also: BrainTwister #15.

  The two sizes of tiles are 10 cm × 20 cm and 20 cm × 20 cm, so we can work in units of decimetres and just consider 1×2 and 2×2 tiles.

  This Python program packs increasing numbers of tiles into a tray 2 units high, proceeding from left to right, and also constructs a representation of each packing.

  It runs in 96ms. (Internal runtime is 29ms).

  from enigma import (irange, inf, decompose, icount, is_square, printf)
  
  # find packings for <a> 2x1 and <b> 2x2 tiles
  def solve(a, b, ss=''):
    # are we done?
    if 0 == a == b:
      yield ss
    else:
      if a > 1:
        # place 2x 2x1 tiles horizontally
        yield from solve(a - 2, b, ss + '=')
      if a > 0:
        # place 1x 2x1 tile vertically
        yield from solve(a - 1, b, ss + '|')
      if b > 0:
        # place 1x 2x2 tile
        yield from solve(a, b - 1, ss + 'O')
  
  # consider total number of tiles
  for t in irange(3, inf):
    r = 0  # count results with up to 3 digits
    # split into 2x1 (more) and 2x2 tiles
    for (b, a) in decompose(t, 2, increasing=1, sep=1, min_v=1):
      # count the number of ways to place the tiles
      n = icount(solve(a, b))
      # look for cases where n is a 3-digit square
      if n < 1000:
        r += 1
        if n > 99 and is_square(n):
          printf("t={t}: a={a} b={b} -> {n} ways; length = {x}", x=a + 2 * b)
    # are we done?
    if r == 0: break
  

  If we don’t generate the representations of the packings we can write a faster program.

  The following program has an internal runtime of 227µs.

  from enigma import (irange, inf, decompose, cache, printf)
  
  # number of packings for <a> 2x1 and <b> 2x2 tiles
  @cache
  def P(a, b):
    # are we done?
    if 0 == a == b: return 1
    r = 0
    # place 2x 2x1 tiles horizontally
    if a > 1: r += P(a - 2, b)
    # place 1x 2x1 tile vertically
    if a > 0: r += P(a - 1, b)
    # place 1x 2x2 tile
    if b > 0: r += P(a, b - 1)
    return r
  
  # target values = 3-digit squares
  tgt = set(i * i for i in irange(10, 31))
  
  # consider total number of tiles
  for t in irange(3, inf):
    r = 0  # count results with up to 3 digits
    # split into 2x1 (more) and 2x2 tiles
    for (a, b) in decompose(t, 2, increasing=-1, sep=1, min_v=1):
      # count the number of ways to place the tiles
      n = P(a, b)
      # look for cases where n is a 3-digit square
      if n < 1000:
        r += 1
        if n > 99 and n in tgt:
          printf("t={t}: a={a} b={b} -> {n} ways; length = {x}", x=a + 2 * b)
    # are we done?
    if r == 0: break
  

  Solution: The box is 110 cm long. There are 3 square tiles.

  There are 8 tiles in total, 3 square and 5 rectangular. And they can fit into the box in 256 (= 16^2) different ways.

  See also: OEIS A038137.

  LikeLike

• 

  Frits 11:55 am on 20 October 2024 Permalink | Reply

  My original program performed weaving of the list of squares with the list of rectangles but as we are only interested in the number of combinations I have used the combinatorial C formula.

  from math import factorial as fact
  
  # number of possible combinations
  C = lambda n, r: fact(n) / (fact(r) * fact(n - r))
  
  # loop over number of tiles
  for t, _ in enumerate(iter(bool, 1), 3): # infinite loop
    below1000 = 0
    # choose number of square tiles
    for s in range(1, (t + 1) // 2):
      r = t - s  # number of rectangular tiles
      # fill box with <s> squares and <r> rectangles
      
      # suitable selection of rectangular pieces  
      rps = [["|"] * v + ["="] * (h // 2) for v in range(r + 1) 
             if (h := (r - v)) % 2 == 0]  
      
      c = 0
      for rp in rps:
        nv = rp.count("|")
        # C(len(rp), nv) = len(set(permutations(rp)))
        c += C(len(rp) + s, s) * C(len(rp), nv)
      
      if c < 1000:     
        below1000 = 1    
        # three-digit perfect square
        if c > 99 and (round(c**.5))**2 == c:
          print(f"answer: {10 * (2 * s + r)} cm long and with {s} square tiles")
                   
    if below1000 == 0:
      break # no need to check with more tiles
  

  LikeLike

• 

  Pete Good 5:17 pm on 20 October 2024 Permalink | Reply

  Jim, Frits’s program produces the right answer but your answer needs to be multiplied by 10.

  LikeLike

  • 

    Jim Randell 6:01 pm on 20 October 2024 Permalink | Reply

    @Pete: My programs use units of 1 decimetre.

    LikeLike