S2T2

Jim Randell 9:22 am on 15 August 2023 Permalink Reply
Tags: by: Victor Bryant ( 140 )   

• 

  Jim Randell 9:23 am on 15 August 2023 Permalink | Reply

  (See also: Enigma 611).

  There are 12 different pentominoes (if we allow rotation and reflection), and I have written polyominoes.py for dealing with them (and other polyominoes).

  This Python program starts with the 12 possible pentomino shapes, and then removes an even number of them and tries to fit them into possible rectangles.

  It runs in 2.2s.

  Run: [ @replit ]

  from enigma import (irange, subsets, divisors_pairs, seq2str, printf)
  import polyominoes
  
  # possible pentomino shapes
  tiles = polyominoes.shapes("I5 U5 T5 V5 X5 W5 L5 Y5 P5 N5 F5 Z5".split(), as_map=1)
  n = len(tiles.keys())
  
  # record grid dimensions
  rs = set()
  # an even number of tiles are unused
  for k in irange(2, n - 1, step=2):
    # choose (n - k) tiles
    for ks in subsets(tiles.keys(), size=n - k):
      ts = list(tiles[x] for x in ks)
      # consider possible rectangles for these pieces
      for (x, y) in divisors_pairs(5 * len(ts)):
        if y % x != 0: continue  # width is a multiple of height
        if (x, y) == (2, 10): continue  # exclude 2 x 10
        # can we fit the tiles into the grid?
        for g in polyominoes.fit(ts, y, x):
          rs.add((x, y))
          # output 1 example
          printf("{x} x {y} grid -> {ks} [{k} unused]", ks=seq2str(ks, sep=" "))
          polyominoes.output_grid(g)
          break
  
  # output solution
  printf("grid = {rs}", rs=seq2str(rs, sep=" ", enc=""))
  

  Solution: The rectangle was 5 in × 10 in.

  There are many possible pairs of shapes which can remain unused, and many possible ways to fit the remaining shapes into the grid. (The program prints one example packing for each set of shapes and grid size).

  Here is one:

  

  I have a wooden set of pentominoes, here is the same packing (slightly exploded, so you can see the individual pentominoes), along with the unused pieces:

  

  LikeLike