Enigmatic Code

Programming Enigma Puzzles

Enigma 1112: Patio zones

From New Scientist #2268, 9th December 2000 [link]

George is building a patio, which will be covered using one-foot-square concrete slabs of seven different colours. He has divided the rectangular patio into seven rectangular zones, without any gaps.

Each zone will be covered by slabs of one colour, with five different colours appearing around the perimeter of the patio, and four different colours at the corners. The seven rectangular zones are all different shapes, but all have the same perimeter, which is less than 60 feet.

What are the dimensions of the patio that George is building?

This puzzle is referenced by Enigma 1221.

[enigma1112]

Advertisements

3 responses to “Enigma 1112: Patio zones

  1. Jim Randell 5 June 2017 at 9:22 am

    See also: Enigma 17, Enigma 1251.

    At first I missed the fact that the seven zones were rectangular, and was worried that this was going to be quite a tricky problem to solve. Once I realised that the zones were rectangular it seemed like a more tractable problem, which can be solved using rectangle packing.

    This Python 3 program runs in 2.17s (or 1.06s using PyPy).

    from itertools import combinations, product
    from collections import defaultdict
    from enigma import irange, divisor_pairs, diff, join, arg, printf
    
    # -- rectangle packer --
    
    # determine if rectangle <r> overlaps with a rectangle in <rs>
    # return the index in <rs> of an overlapping rectangle, or -1
    def overlap(r, rs):
      (i1, j1, p1, q1) = r
      for (k, (i2, j2, p2, q2)) in enumerate(rs):
        if i1 < i2 + p2 and i2 < i1 + p1 and j1 < j2 + q2 and j2 < j1 + q1:
          return k
      return -1
    
    # fit the rectangles rs into a n x m grid (loose packing)
    # n, m - the dimensions of the grid
    # rs - dimensions of the rectangles (p, q)
    # ps - positions of the rectangles (x, y, p, q)
    def pack_loose(n, m, rs, ps=[]):
      # are we done?
      if not rs:
        yield ps
      else:
        # try to fit the next rectangle into the grid
        for (p, q) in set((rs[0], rs[0][::-1])):
          # consider possible locations for the rectangle
          for (i, j) in product(irange(0, n - p), irange(0, m - q)):
            # does this position overlap with any placed rectangles?
            r = (i, j, p, q)
            if overlap(r, ps) == -1:
              # try to place the remaining rectangles
              for z in pack_loose(n, m, rs[1:], ps + [r]): yield z
    
    # find the first empty square
    def empty(n, m, ps):
      for j in irange(0, m - 1):
        for i in irange(0, n - 1):
          if overlap((i, j, 1, 1), ps) == -1:
            return (i, j)
    
    # fit the rectangles rs into a n x m grid (tight packing)
    # n, m - the dimensions of the grid
    # rs - dimensions of the rectangles (p, q)
    # ps - positions of the rectangles (x, y, p, q)
    def pack_tight(n, m, rs, ps=[]):
      # are we done?
      if not rs:
        yield ps
      else:
        # find an empty square
        (i, j) = empty(n, m, ps)
        # fit one of the remaining rectangles there
        for (k, r) in enumerate(rs):
          for (p, q) in (r, r[::-1]):
            if not(i + p > n or j + q > m):
              r = (i, j, p, q)
              if overlap(r, ps) == -1:
                # and try to replace the remaining rectangles
                yield from pack_tight(n, m, rs[:k] + rs[k + 1:], ps + [r])
    
    # output a packed grid
    def output_grid(n, m, rs):
      # make an empty grid
      g = list([0] * n for _ in irange(1, m))
      # fill out the rectangles
      for (k, (x, y, p, q)) in enumerate(rs, start=1):
        for (i, j) in product(irange(x, x + p - 1), irange(y, y + q - 1)):
          g[j][i] = k
      # output the packing
      z = len(str(k))
      for r in g:
        printf("{r}", r=join((str(x or 0).zfill(z) for x in r), sep=' '))
    
    # -- end --
    
    # use the tight rectangle packer
    pack = pack_tight
    
    # fit the rectangles <rs> into an <n> x <m> grid
    # according to the required conditions
    def fit(n, m, rs):
    
      # find pairs of rectangles that have dimensions that add up to n or m
      # pairs: ((p, q), i) -> [ ((p', q'), j), ... ]
      (pairs_n, pairs_m) = (defaultdict(list), defaultdict(list))
      for (A, B) in combinations(rs, 2):
        for (a, b) in product((0, 1), repeat=2):
          x = A[a] + B[b]
          if x == n:
            pairs_n[(A, a)].append((B, b))
            pairs_n[(B, b)].append((A, a))
          if x == m:
            pairs_m[(A, a)].append((B, b))
            pairs_m[(B, b)].append((A, a))
    
      # choose a pair to go across the top (n)
      for ((A, a), vs) in pairs_n.items():
        for (B, b) in vs:
          if not(A < B): continue
    
          # look for rectangle C to fill the gap along the left edge (m)
          for (C, c) in pairs_m[(A, a ^ 1)]:
            if C == B: continue
    
            # look for rectangle D to fill the gap along the right edge (m)
            for (D, d) in pairs_m[(B, b ^ 1)]:
              if D == A or D == C: continue
    
              # measure the gap between C and D on the bottom edge (n)
              g = n - C[c ^ 1] - D[d ^ 1]
              if g > 0:
    
                # the remaining rectangles
                rs1 = diff(rs, [A, B, C, D])
    
                # find rectangle E to fit in the gap in the perimeter
                for (E, e) in product(rs1, (0, 1)):
                  if E[e] == g and not(E[e ^ 1] > m):
    
                    # place A, B, C, D
                    ps = [
                      # A is in the top left corner
                      (0, 0, A[a], A[a ^ 1]),
                      # B is in the top right corner
                      (n - B[b], 0, B[b], B[b ^ 1]),
                      # C is in the bottom left corner
                      (0, A[a ^ 1], C[c ^ 1], C[c]),
                      # D is in the bottom right corner
                      (n - D[d ^ 1], m - D[d], D[d ^ 1], D[d])
                    ]
    
                    # place E in the gap between C and D
                    r = (C[c ^ 1], m - E[e ^ 1], E[e], E[e ^ 1])
    
                    # if it packs correctly...
                    if overlap(r, ps) == -1:
                      # then pack the remaining (non-perimeter) rectangles
                      yield from pack(n, m, diff(rs1, [E]), ps + [r])
    
    # try to fit the rectangles into the grid (both ways)
    def solve(x, y, rs):
      # try the normal way
      for s in fit(x, y, rs): yield s
      # and the other way (transposing the results)
      for s in fit(y, x, rs): yield list((j, i, q, p) for (i, j, p, q) in s)
    
    # verbose output?
    verbose = arg('', 0)
    
    # consider semi-perimeters below 30
    for p in irange(2, 29):
      # possible rectangles
      rs = list((a, p - a) for a in irange(1, p // 2))
      # choose 7 of the rectangles
      for s in combinations(rs, 7):
        # max minor and major dimensions of the rectangles
        mn = max(a for (a, b) in s)
        mj = max(b for (a, b) in s)
        # calculate the total area
        A = sum(a * b for (a, b) in s)
        # consider possible dimensions of the patio (x <= y)
        for (x, y) in divisor_pairs(A):
          if x < mn or y < mj: continue
          if verbose: printf("[considering: semi-perimeter = {p}, rectangles = {s}, area = {A} = {x} * {y}]")
          # try to fit the rectangles into the grid
          for ps in solve(x, y, s):
            printf("grid = {x} x {y}, rectangles = {ps}")
            output_grid(x, y, ps)
            printf()
            break
    

    Solution: George’s patio is 26 feet by 32 feet.

    The seven rectangular areas are: 2×25, 3×24, 5×22, 6×21, 7×20, 8×19, 13×14. Each having a perimeter of 54 feet.

    Here’s a diagram of how the rectangular areas fit together:

    The program considers 15,705 different collections of rectangles and grids, which would take a long time of we passed each of them to the pack() function directly, and we would have to examine the results to check that the results are in the required configuration (i.e. with five different regions making up the perimeter, and four of these in the corners). Instead I use this information to pack five rectangles along the perimeter, and if that is possible then we only have two remaining rectangles to fit into the central hole (which I do use the rectangle packer for, although it is a bit of overkill).

  2. geoffrounce 5 June 2017 at 4:33 pm

    This Enigma proved an ideal candidate for MinZinc, consisting mainly of geometrical constraints
    to check the packing of the rectangles. It was also quite fast – 129 msec in Geocode (bundled) and relatively short code. I found the perimeter of the seven rectangles to be 54 ft.

    I used the diagram Jim included in the Enigma 1221, as it had the same requirements for colours.

    % A Solution in MiniZinc
    %
    % This solution uses Jim's diagram of seven areas in Enigma 1221: Flower Beds
    %                     M (width)
    %        ----------------------------        
    %        |      |         E         |
    %        |      |-------------------|
    %        |      |     |     D       |
    %        |   F  | G   |-------------|
    %     N  |      |     |        |    |
    %(Height)|      |     |    C   | B  |
    %        |      |     |        |    |
    %        | --------------------|    |
    %        |           A         |    |
    %        |--------------------------|
    %
    
    include "globals.mzn";
    
    % overall rectangle dimensions
    var 1..100:M;  % overall width
    var 1..100:N;  % overall height
    
    set of int: Dim = 1..100;
    
    % widths of all rectangles
    var Dim: wa; var Dim: wb; var Dim: wc; var Dim: wd; var Dim: we;
    var Dim: wf; var Dim: wg;
    
    var 4..59: perim;  % perimeter of each of 7 rectangles < 60
    
    % heights of all rectangles
    var Dim: ha; var Dim: hb; var Dim: hc; var Dim: hd; var Dim: he;  
    var Dim: hf; var Dim: hg;
    
    % all rectangle heights and widths are different for A,B,C,D,E,F
    constraint all_different ( [wa, wb, wc, wd, we, wf, wg, ha, hb,
    hc, hd, he, hf, hg]);
    
    % perimeter of all rectangles ( eg pa = perimeter of A)
    var Dim: pa; var Dim: pb; var Dim: pc; var Dim: pd; var Dim: pe;  
    var Dim: pf; var Dim: pg;
    
    % area of all rectangles (eg ab = area of B)
    var Dim: aa; var Dim: ab; var Dim: ac; var Dim: ad; var Dim: ae;  
    var Dim: af; var Dim: ag;
    
    var 100..9999 : area = M * N;   % overall area of main rectangle 
    % (inc. 7 separate rectangles)
    
    % Main Rectangle - width constraints (eg wf = width of F)
    constraint wf + we == M /\ wf + wg + wd == M /\ wa + wb == M 
    /\ wf + wg + wc + wb == M;
    
    % Main Rectangle - height constraints (eg hf = height of F)
    constraint hf + ha == N /\ he + hg + ha == N /\ 
    he + hd + hc + ha == N /\ he + hd + hb == N;
    
    % Sub rectangle area constraints ie M*N = A + B + C + D + E + F + G
    constraint area = (wa * ha) + (wb * hb) + (wc * hc) + (wd * hd)
     + (we * he) + (wf * hf) + (wg * hg);
    
    % Sub rectangle perimeter constraints
    constraint  2*(we + he) = perim /\ 2*(wf + hf) = perim /\ 2*(wa + ha) = perim
    /\ 2*(wb + hb) = perim /\ 2*(wc + hc) = perim /\ 2*(wd + hd) = perim 
    /\ 2*(wg + hg) = perim;
    
    solve satisfy;
    
    output [ "M = " ++ show(M) ++ " N = " ++ show(N) ++ 
             ", overall patio dimensions" ++ "\n" ++
             "ha = " ++ show(ha) ++ " wa = " ++ show(wa) ++ 
              ", hb = " ++ show(hb) ++ " wb = " ++ show(wb) ++ "\n" ++
             "hc = " ++ show(hc) ++ " wc = " ++ show(wc) ++ 
             ", hd = " ++ show(hd) ++ " wd = " ++ show(wd) ++ "\n" ++
             "he = " ++ show(he) ++ " we = " ++ show(we) ++ 
             ", hf = " ++ show(hf) ++ " wf = " ++ show(wf) ++ "\n" ++
             "hg = " ++ show(hg) ++ " wg = " ++ show(wg) ];
    
    % Output        
    % M = 26 N = 32, overall patio dimensions
    % ha = 7 wa = 20, hb = 21 wb = 6   (A & B)
    % hc = 14 wc = 13, hd = 8 wd = 19  (C & D)
    % he = 3 we = 24, hf = 25 wf = 2   (E & F)
    % hg = 22 wg = 5 (G)
    % ----------
    % Finished in 129msec 
    %
    
    
    • Jim Randell 7 June 2017 at 10:48 am

      Labelling the rectangles from 1 to 7 (corresponds with A to G in my program) we can get quite a compact MiniZinc model.

      include "globals.mzn";
      
      % width and height of the seven rectangles
      array[1..7] of var 1..29: w;
      array[1..7] of var 1..29: h;
      
      % the rectangles all have the same semi-perimeters less than 30
      var 1..29: sp;
      constraint forall (i in 1..7) (w[i] + h[i] = sp);
      
      % the rectangles are all different (so all dimensions are different)
      constraint all_different(w ++ h);
      
      % width of grid
      var 2..57: width;
      constraint all_equal([width, w[1] + w[2], w[3] + w[6] + w[2], w[3] + w[5] + w[7] + w[2], w[3] + w[5] + w[4]]);
      
      % height of grid
      var 2..57: height;
      constraint all_equal([height, h[1] + h[3], h[1] + h[6] + h[5], h[1] + h[6] + h[7] + h[4], h[2] + h[4]]);
      
      % the rectangles fill the grid
      constraint sum (i in 1..7) (w[i] * h[i]) = width * height;
      
      solve satisfy;
      

      On my machine this runs in 96ms with the mzn-g12fd solver (and only 98ms if the -a parameter is added).

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: