Enigmatic Code

Programming Enigma Puzzles

Enigma 1475: Lines of thought

notableFrom New Scientist #2637, 5th January 2008

Joe cut out a number of small square cards. On some of them he drew a thin red line joining the centres of two opposite sides and on the others he drew a thin red line joining the centres of two adjacent sides.

Penny’s challenge was to select 24 cards and arrange them in a 6-card by 4-card rectangle so as to produce a number of small areas, each with a complete single boundary of thin red lines, with a total area equal to five-sixteenths of the total card area.

Penny could choose any combination of cards – for example, 10 of the first and 14 of the second – but only some of the combinations would lead to her meeting the challenge.

How many of the combinations?

[enigma1475]

Advertisements

2 responses to “Enigma 1475: Lines of thought

  1. Jim Randell 9 December 2012 at 10:47 am

    I thought this sounded like a tricky one to code up, but when I set about it it was actually surprisingly simple, but still fun. The following recursive Python approach runs in 150ms.

    from collections import namedtuple, defaultdict
    from itertools import product
    from enigma import printf
    
    # each edge is split into two segments, whichare on the
    # exterior (0) or interior (1) of the shape
    # u - top edge (up)
    # d - lower edge (down)
    # l - left edge
    # r - right edge
    # measure the area of the tile in eighths of a tile
    # i - interior area of the tile
    # tiles are of type A (half split) or type B (corner split)
    # t - type of the tile
    Tile = namedtuple('Tile', 'u d l r i t') 
    
    # types of tile
    (A, B) = ('A', 'B')
    
    tiles = [
      #     u  u    d  d    l  l    r  r   i  t
      Tile((0, 1), (0, 1), (0, 0), (1, 1), 4, A),
      Tile((1, 0), (1, 0), (1, 1), (0, 0), 4, A),
      Tile((1, 1), (0, 0), (1, 0), (1, 0), 4, A),
      Tile((0, 0), (1, 1), (0, 1), (0, 1), 4, A),
      Tile((0, 0), (0, 1), (0, 0), (0, 1), 1, B),
      Tile((1, 1), (1, 0), (1, 1), (1, 0), 7, B),
      Tile((0, 0), (1, 0), (0, 1), (0, 0), 1, B),
      Tile((1, 1), (0, 1), (1, 0), (1, 1), 7, B),
      Tile((1, 0), (0, 0), (1, 0), (0, 0), 1, B),
      Tile((0, 1), (1, 1), (0, 1), (1, 1), 7, B),
      Tile((0, 1), (0, 0), (0, 0), (1, 0), 1, B),
      Tile((1, 0), (1, 1), (1, 1), (0, 1), 7, B),
    ]
    
    # x, y - dimensions of the grid
    # g - the grid
    # n - number of tiles to place
    # r - accumulate results
    def solve(x, y, g, n, r):
      # are we done?
      if n == 0:
        # count the interior area and types of tiles
        (a, c) = (0, { A: 0, B: 0 })
        for (i, j) in product(range(x), range(y)):
          t = g[i][j]
          a += t.i
          if t.t in c: c[t.t] += 1
        if a == 60:
          r[(c[A], c[B])] += 1
        return
      # find an empty space
      for (i, j) in product(range(x), range(y)):
        if g[i][j] is None: break
      # find a tile to fit there
      for t in tiles:
        # check adjacent tiles
        if not all((g[i-1][j] is None or g[i-1][j].d == t.u,
                    g[i+1][j] is None or g[i+1][j].u == t.d,
                    g[i][j-1] is None or g[i][j-1].r == t.l,
                    g[i][j+1] is None or g[i][j+1].l == t.r)): continue
        g[i][j] = t
        # and try to fill the remaining squares
        solve(x, y, g, n - 1, r)
        g[i][j] = None
    
    # a blank tile
    E = Tile((0, 0), (0, 0), (0, 0), (0, 0), 0, 0)
    
    # make a 6x4 grid, surrounded by blank tiles (so an 8x6 grid)
    (x, y) = (6, 8)
    g = list([None] * y for i in range(x))
    for (i, j) in product(range(x), range(y)):
      if not(0 < i < x - 1 and 0 < j < y - 1): g[i][j] = E
    
    r = defaultdict(int)
    solve(x, y, g, (x - 2) * (y - 2), r)
    
    # output the results
    for k in sorted(r.keys()):
      printf("{k[0]}A + {k[1]}B: {n} solutions", n=r[k])
    printf("SOLUTION: {n} combinations", n=len(r))
    

    Solution: There are 5 different combinations.

    Instead of considering two different types of card and worrying about their rotations and determining the interior and exterior of shapes I instead considered 12 possible tiles which take all possible arrangements into account.

    Enigma 1475 - 12 Tiles

    The edges of the tiles are split into two segments and labelled either 0 or 1 (for “0utside” and “1nside” to distinguish the exterior and interior segments). I then consider a 6 x 8 grid where the perimeter is filled with empty tiles that consist entirely of exterior edges. The problem is then simply to fit tiles into the grid so that the edges match up. And find solutions where the interior (coloured in) area is 60 (measuring in eighths of squares, so the entire 4 x 6 grid has an area of 192).

    It turns out the are 59 different grids (although fewer if you eliminate duplicates grids by symmetry, and fewer still if you eliminate duplicate grids that use the same shapes, but rearranged).

    It turns out that each of these grids is composed of the following 15 different enclosed shapes.

    Enigma 1475 - Shapes 1

    Enigma 1475 - Shapes 2

    Enigma 1475 - Shapes 3

    Enigma 1475 - Shapes 4

    and here are example solutions using, 4 type A and 20 type B cards (there are 4 such grids):

    Enigma 1475 - 4A + 20B

    6 type A and 18 type B cards (there are 4 such grids):

    Enigma 1475 - 6A + 18B

    8 type A and 16 type B cards (there are 22 such grids):

    Enigma 1475 - 8A + 16B

    10 type A and 14 type B cards (there are 20 such grids):

    Enigma 1475 - 10A + 14B

    12 type A and 12 type B cards (there are 9 such grids):

    Enigma 1475 - 12A + 12B

    The following code is augmented to produce all grid patterns (regardless of area), and attempt an ASCII art representation of the layout:

    from collections import namedtuple, defaultdict
    from itertools import product
    from enigma import printf
    
    # each edge is split into two segments, whichare on the
    # exterior (0) or interior (1) of the shape
    # u - top edge (up)
    # d - lower edge (down)
    # l - left edge
    # r - right edge
    # measure the area of the tile in eighths of a tile
    # i - interior area of the tile
    # tiles are of type A (half split) or type B (corner split)
    # t - type of the tile
    # s - string representation
    Tile = namedtuple('Tile', 'u d l r i t s') 
    
    # types of tile
    (A, B) = ('A', 'B')
    
    tiles = [
      #     u  u    d  d    l  l    r  r   i  t   s
      Tile((0, 1), (0, 1), (0, 0), (1, 1), 4, A, ' o o'),
      Tile((1, 0), (1, 0), (1, 1), (0, 0), 4, A, 'o o '),
      Tile((1, 1), (0, 0), (1, 0), (1, 0), 4, A, 'oo  '),
      Tile((0, 0), (1, 1), (0, 1), (0, 1), 4, A, '  oo'),
      Tile((0, 0), (0, 1), (0, 0), (0, 1), 1, B, '   /'),
      Tile((1, 1), (1, 0), (1, 1), (1, 0), 7, B, 'ooo/'),
      Tile((0, 0), (1, 0), (0, 1), (0, 0), 1, B, '  \\ '),
      Tile((1, 1), (0, 1), (1, 0), (1, 1), 7, B, 'oo\\o'),
      Tile((1, 0), (0, 0), (1, 0), (0, 0), 1, B, '/   '),
      Tile((0, 1), (1, 1), (0, 1), (1, 1), 7, B, '/ooo'),
      Tile((0, 1), (0, 0), (0, 0), (1, 0), 1, B, ' \\  '),
      Tile((1, 0), (1, 1), (1, 1), (0, 1), 7, B, 'o\\oo'),
    ]
    
    # x, y - dimensions of the grid
    # g - the grid
    # n - number of tiles to place
    # r - accumulate results
    def solve(x, y, g, n, r):
      # are we done?
      if n == 0:
        # count the interior area and types of tiles
        (a, c) = (0, { A: 0, B: 0 })
        for (i, j) in product(range(x), range(y)):
          t = g[i][j]
          a += t.i
          if t.t in c: c[t.t] += 1
        printf("area={a} count={c}")
        # output the gird
        for x in g:
          print(''.join(t.s[0:2] for t in x))
          print(''.join(t.s[2:4] for t in x))
        r[a][(c[A], c[B])] += 1
        return
      # find an empty space
      for (i, j) in product(range(x), range(y)):
        if g[i][j] is None: break
      # find a tile to fit there
      for t in tiles:
        # check adjacent tiles
        if not all((g[i-1][j] is None or g[i-1][j].d == t.u,
                    g[i+1][j] is None or g[i+1][j].u == t.d,
                    g[i][j-1] is None or g[i][j-1].r == t.l,
                    g[i][j+1] is None or g[i][j+1].l == t.r)): continue
        g[i][j] = t
        # and try to fill the remaining squares
        solve(x, y, g, n - 1, r)
        g[i][j] = None
    
    # a blank tile
    E = Tile((0, 0), (0, 0), (0, 0), (0, 0), 0, 0, '    ')
    
    # make a 6x4 grid, surrounded by blank tiles (so an 8x6 grid)
    (x, y) = (6, 8)
    g = list([None] * y for i in range(x))
    for i, j in product(range(x), range(y)):
      if not(0 < i < x - 1 and 0 < j < y - 1): g[i][j] = E
    
    r = defaultdict(lambda: defaultdict(int))
    solve(x, y, g, (x - 2) * (y - 2), r)
    
    # output the results
    for k in sorted(r.keys()):
      printf("area={k}: {n} solutions {a}", n=len(r[k]), a='*** ANSWER ***' if k == 60 else '')
      print(dict(r[k]))
    

    The maximum enclosed area you can make is 13.5 tiles, using a grid that uses 12 type A and 12 type B cards. It looks like this:

    Enigma 1475 - Max

    • Hugh Casement 4 October 2014 at 2:57 pm

      Brilliant, Jim. Just the sort of detailed analysis we appreciate, as opposed to the one-line answers published in the magazine.

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: