Sunday Times Teaser 2838 – King Lear IV

by Nick MacKinnon

Published: 12 February 2017 (link)

King Lear IV’s realm consisted of a regular hexagon divided into 24 counties that were equal-sized equilateral triangles. In his will he wanted to share the counties among his six daughters, each daughter’s portion having the property that, if you walked in a straight line between any two points in it, then you remained in her portion. If two daughters’ portions had the same area then they had to be of different shapes (and not the mirror image of each other). He wanted Cordelia to have a single county (his favourite county on the edge of the kingdom), he wanted Goneril to have a hexagonal-shaped portion, and he knew the number of counties he wanted to allocate to each of the other daughters, with Reagan’s portion being the largest of all. It turned out that his requirements uniquely determined Goneril’s and Reagan’s counties.

What, in increasing order, were the numbers of counties allocated to the six daughters?

3 Comments Leave one →

Brian Gladman permalink

This solution used Donald Knuth’s ‘Dancing Links’ algorithm for the exact cover problem.


from itertools import product
from collections import defaultdict

# import an implementation of Donald Knuth's Danncing Links algorithm
# by David Goodger and Ali Assaf  (licensed under GPL v2)
from exact_cover_x2 import ExactCover

# The positions of triangles are specified by three numbers (u, v, w).
# The u axis is horizontal while the v axis is at an angle 60 degrees
# as shown below. Triangles have w = 1 and are located by the position
# of their lower-left corner; inverted triangles (w = -1) are located
# by the position of their upper-right corner. 
#                                                   __________ (u,v)
#              3  __  __                 /\        \          /
#               /\  /\  /               /  \        \ w = -1 /
#            2 /__\/__\/               /    \        \      /
#             /\  /\  /\              /      \        \    /
#      /   1 /__\/__\/__\            / w = 1  \        \  /
#     /     /\  /\  /\  /\    (u,v) /__________\        \/
#    v   0 /__\/__\/__\/__\     
#    u ->  0  1   2   3   4
#

# rotate the coordinate system by 60 degrees
def rot(x):
  return [(u + v + w, -u, -w) for u, v, w in x]

# normalise a set of triangles by shifting the whole set left/right
# and up/down so that the minimum u and v values in the set are zero
def norm(x):
  min_u = min(u if w > 0 else u - 1 for u, v, w in x)
  min_v = min(v for u, v, w in x)
  return frozenset((u - min_u, v - min_v, w) for u, v, w in x)

# rotate a set of triangles by six 60 degree intervals, accumulating
# triangle data for each of the different orientations that occur
def poly_data(x):
  dat = set()
  x = norm(x)
  dat.add(x)
  for r in range(6):
    x = norm(rot(x))
    dat.add(x)
  return dat

# a dictionary holding triangle data for each of the convex 'polyiamond'
# shapes that can fit in a hexagon of side two (the first letter is the
# area, the second distinguishes different shapes with the same area)
p_data = {
  '1T': ((0,0,1),),
  '2D': ((0,0,1), (1,1,-1)),
  '3I': ((0,0,1), (1,1,-1), (1,0,1)),
  '4I': ((0,0,1), (1,1,-1), (1,0,1), (2,1,-1)),
  '4T': ((0,0,1), (1,1,-1), (1,0,1), (0,1,1)),
  '5I': ((0,0,1), (1,1,-1), (1,0,1), (2,1,-1), (2,0,1)),
  '6I': ((0,0,1), (1,1,-1), (1,0,1), (2,1,-1), (2,0,1), (3,1,-1)),
  '6H': ((0,0,1), (1,1,-1), (1,0,1), (1,0,-1), (1,-1,1), (2,0,-1)),
  '7I': ((0,0,1), (1,1,-1), (1,0,1), (2,1,-1), (2,0,1), (3,1,-1), (3,0,1)),
  '7D': ((0,0,1), (1,1,-1), (1,0,1), (0,1,1), (1,0,-1), (1,-1,1), (2,0,-1)),
  '8R': ((0,0,1), (1,1,-1), (1,0,1), (2,1,-1), (0,1,1), (1,2,-1), (1,1,1), (2,2,-1)),
  '8D': ((0,0,1), (1,1,-1), (1,0,1), (2,1,-1), (2,0,1), (0,1,1), (1,2,-1), (1,1,1))
  }

# compose shape and orientation data for the above pieces
piece_data = {p:poly_data(p_data[p]) for p in p_data}

# triangle data for a hexagon of side two
region = [
  (0,1,1), (1,2,-1), (1,1,1), (2,2,-1), (2,1,1),
  (0,0,1), (1,1,-1), (1,0,1), (2,1,-1), (2,0,1), (3,1,-1), (3,0,1),
  (1,0,-1), (1,-1,1), (2,0,-1), (2,-1,1), (3,0,-1), (3,-1,1), (4,0,-1),
  (2,-1,-1), (2,-2,1), (3,-1,-1), (3,-2,1), (4,-1,-1) ]

# fit a set of pieces into a region using Donald Knuth's 'Dancing Links'
# exact cover algorithm
def solve_region(pieces, piece_data, region):
  n_pieces, area = len(pieces), len(region)
  # a two dimensional matrix
  mat = []
  # the first row holds strings of the names of the pieces followed
  # by names for each point in the space being covered
  lp = pieces + list(str(x) for x in region) 
  mat.append(lp)
  
  # for each piece
  for i, piece in enumerate(pieces):
    # in each of its orientations
    for sdat in piece_data[piece]:
      # fix the position of the single triangle on the edge of the hexagon
      rr = ((0, 0),) if piece == '1T' else product(range(4), range(-2, 2))
      # generate cover data for each position/orientation of the piece
      for uu, vv in rr:
        sd = set((u + uu, v + vv, c) for u, v, c in sdat)
        # if the shape is wholly within the region 
        if sd.intersection(region) == sd:
          l = [0] * (n_pieces + len(region)) 
          l[i] = 1
          for p in sd:
            l[n_pieces + region.index(p)] = 1
          # append it to the matrix
          mat.append(l)
          
  # return the ways in which the pieces cover the region
  ec = ExactCover(mat)
  for s in ec.solve():
    yield tuple(tuple(x) for x in s)

# find combinations of pieces that always include T1 and O6
# and have a combined area of 24
def compose(pieces, area=17, sp=['1T', '6H']):
  if not area:
    if len(sp) == 6:
      yield sp
  else:
    # add a piece       
    for i, p in enumerate(pieces):
      ap = int(p[0])
      # ... if it is not already present and its area is less
      # than that which remains
      if p not in sp and area >= ap:
        # avoid duplicated solutions
        if len(sp) > 2:
          if ap < int(sp[-1][0]):
            continue
          if ap == int(sp[-1][0]) and sp[-1][1] < p[1]:
            continue
        # add further pieces
        yield from compose(pieces, area - int(p[0]), sp + [p])

# list solutions according to the sizes of the pieces
sols = defaultdict(list)
for pc in compose(piece_data):
  # check that these pieces can be packed into the region
  n_sols = len(tuple(solve_region(pc, piece_data, region)))
  if n_sols:
    areas = tuple(sorted(int(p[0]) for p in pc))
    sols[areas].append((pc, n_sols))

# look for sets of pieces with a unique set of areas, one
# which is larger than six
for p, ls in sols.items():
  if max(p) > 6:
    print(f'Areas: {p}:')
    for x, ns in ls:
      print(f'  {sorted(x)} ({ns})')

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

from itertools import product

from collections import defaultdict

# import an implementation of Donald Knuth's Danncing Links algorithm

# by David Goodger and Ali Assaf (licensed under GPL v2)

from exact_cover_x2 import ExactCover

# The positions of triangles are specified by three numbers (u, v, w).

# The u axis is horizontal while the v axis is at an angle 60 degrees

# as shown below. Triangles have w = 1 and are located by the position

# of their lower-left corner; inverted triangles (w = -1) are located

# by the position of their upper-right corner.

# __________ (u,v)

# 3 __ __ /\ \ /

# /\ /\ / / \ \ w = -1 /

# 2 /__\/__\/ / \ \ /

# /\ /\ /\ / \ \ /

# / 1 /__\/__\/__\ / w = 1 \ \ /

# / /\ /\ /\ /\ (u,v) /__________\ \/

# v 0 /__\/__\/__\/__\

# u -> 0 1 2 3 4

# rotate the coordinate system by 60 degrees

def rot(x):

return [(u + v + w, -u, -w) for u, v, w in x]

# normalise a set of triangles by shifting the whole set left/right

# and up/down so that the minimum u and v values in the set are zero

def norm(x):

min_u = min(u if w > 0 else u - 1 for u, v, w in x)

min_v = min(v for u, v, w in x)

return frozenset((u - min_u, v - min_v, w) for u, v, w in x)

# rotate a set of triangles by six 60 degree intervals, accumulating

# triangle data for each of the different orientations that occur

def poly_data(x):

dat = set()

x = norm(x)

dat.add(x)

for r in range(6):

x = norm(rot(x))

dat.add(x)

return dat

# a dictionary holding triangle data for each of the convex 'polyiamond'

# shapes that can fit in a hexagon of side two (the first letter is the

# area, the second distinguishes different shapes with the same area)

p_data = {

'1T': ((0,0,1),),

'2D': ((0,0,1), (1,1,-1)),

'3I': ((0,0,1), (1,1,-1), (1,0,1)),

'4I': ((0,0,1), (1,1,-1), (1,0,1), (2,1,-1)),

'4T': ((0,0,1), (1,1,-1), (1,0,1), (0,1,1)),

'5I': ((0,0,1), (1,1,-1), (1,0,1), (2,1,-1), (2,0,1)),

'6I': ((0,0,1), (1,1,-1), (1,0,1), (2,1,-1), (2,0,1), (3,1,-1)),

'6H': ((0,0,1), (1,1,-1), (1,0,1), (1,0,-1), (1,-1,1), (2,0,-1)),

'7I': ((0,0,1), (1,1,-1), (1,0,1), (2,1,-1), (2,0,1), (3,1,-1), (3,0,1)),

'7D': ((0,0,1), (1,1,-1), (1,0,1), (0,1,1), (1,0,-1), (1,-1,1), (2,0,-1)),

'8R': ((0,0,1), (1,1,-1), (1,0,1), (2,1,-1), (0,1,1), (1,2,-1), (1,1,1), (2,2,-1)),

'8D': ((0,0,1), (1,1,-1), (1,0,1), (2,1,-1), (2,0,1), (0,1,1), (1,2,-1), (1,1,1))

}

# compose shape and orientation data for the above pieces

piece_data = {p:poly_data(p_data[p]) for p in p_data}

# triangle data for a hexagon of side two

region = [

(0,1,1), (1,2,-1), (1,1,1), (2,2,-1), (2,1,1),

(0,0,1), (1,1,-1), (1,0,1), (2,1,-1), (2,0,1), (3,1,-1), (3,0,1),

(1,0,-1), (1,-1,1), (2,0,-1), (2,-1,1), (3,0,-1), (3,-1,1), (4,0,-1),

(2,-1,-1), (2,-2,1), (3,-1,-1), (3,-2,1), (4,-1,-1) ]

# fit a set of pieces into a region using Donald Knuth's 'Dancing Links'

# exact cover algorithm

def solve_region(pieces, piece_data, region):

n_pieces, area = len(pieces), len(region)

# a two dimensional matrix

mat = []

# the first row holds strings of the names of the pieces followed

# by names for each point in the space being covered

lp = pieces + list(str(x) for x in region)

mat.append(lp)

# for each piece

for i, piece in enumerate(pieces):

# in each of its orientations

for sdat in piece_data[piece]:

# fix the position of the single triangle on the edge of the hexagon

rr = ((0, 0),) if piece == '1T' else product(range(4), range(-2, 2))

# generate cover data for each position/orientation of the piece

for uu, vv in rr:

sd = set((u + uu, v + vv, c) for u, v, c in sdat)

# if the shape is wholly within the region

if sd.intersection(region) == sd:

l = [0] * (n_pieces + len(region))

l[i] = 1

for p in sd:

l[n_pieces + region.index(p)] = 1

# append it to the matrix

mat.append(l)

# return the ways in which the pieces cover the region

ec = ExactCover(mat)

for s in ec.solve():

yield tuple(tuple(x) for x in s)

# find combinations of pieces that always include T1 and O6

# and have a combined area of 24

def compose(pieces, area=17, sp=['1T', '6H']):

if not area:

if len(sp) == 6:

yield sp

else:

# add a piece

for i, p in enumerate(pieces):

ap = int(p[0])

# ... if it is not already present and its area is less

# than that which remains

if p not in sp and area >= ap:

# avoid duplicated solutions

if len(sp) > 2:

if ap < int(sp[-1][0]):

continue

if ap == int(sp[-1][0]) and sp[-1][1] < p[1]:

continue

# add further pieces

yield from compose(pieces, area - int(p[0]), sp + [p])

# list solutions according to the sizes of the pieces

sols = defaultdict(list)

for pc in compose(piece_data):

# check that these pieces can be packed into the region

n_sols = len(tuple(solve_region(pc, piece_data, region)))

if n_sols:

areas = tuple(sorted(int(p[0]) for p in pc))

sols[areas].append((pc, n_sols))

# look for sets of pieces with a unique set of areas, one

# which is larger than six

for p, ls in sols.items():

if max(p) > 6:

print(f'Areas: {p}:')

for x, ns in ls:

print(f' {sorted(x)} ({ns})')

Jim Randell permalink

I used the Polyform Puzzler framework [ https://puzzler.sourceforge.net/ ] to write a Python program to solve this one.

I copied the convex polyiamonds up to size 7 from the framework, and added the two convex polyiaminds of size 8. We then fit 6 of them with a total size of 24 into the hexagon (with additional constraints that T1 is already placed, O6 must be present, and the largest polyiamond has a size greater than 6).

We then accumulate solutions according to the sizes of the pieces used, and output sizes that lead to a unique packing.

The program runs in 458ms.


import puzzler.coordsys
from puzzler.puzzles.polyiamonds import Polyiamonds1234567
from StringIO import StringIO
import re

# a wrapper to capture output from the polyform puzzler
def solve(puzzle, verbose=0):

  # collect the output
  output = StringIO()
  puzzler.run(puzzle, output_stream=output)

  # count the solutions
  r = output.getvalue()
  if verbose: printf("\n--- polyform puzzler --\n\n{r}\n--- end ---\n")
  m = re.search("^(\d+)\ssolutions?,", r, re.MULTILINE)
  if m is None: return
  return int(m.group(1))


from itertools import combinations
from collections import defaultdict
from enigma import diff, printf

pieces = {
  "T1": 1,
  "D2": 2,
  "I3": 3,
  "T4": 4,
  "I4": 4,
  "I5": 5,
  "O6": 6,
  "I6": 6,
  "I7": 7,
  "D7": 7,
  "d8": 8, # extra size 8 piece ("diamond")
  "t8": 8, # extra size 8 piece ("trapeziod")
}

# define the pieces (we can copy the pieces of size 7 or less)
piece_data = {
  'd8': (((0, 0, 1), (1, 0, 0), (0, -1, 1), (1, -1, 0), (1, -1, 1), (0, 1, 0), (1, -2, 1)), {}),
  't8': (((0, 0, 1), (1, 0, 0), (0, -1, 1), (1, -1, 0), (1, -1, 1), (0, 1, 0), (0, -1, 0)), {}),
}
for k in pieces.keys():
  if k not in piece_data:
    piece_data[k] = Polyiamonds1234567.piece_data[k]

# accumulate results by the size of the pieces
r = defaultdict(int)

# choose 4 pieces to go with T1 and O6
for ps in combinations(diff(pieces.keys(), ("T1", "O6")), 4):
  ns = list(pieces[k] for k in ps)
  if not(sum(ns) == 17 and max(ns) > 6): continue

  # pieces used in this puzzle
  ps = sorted(ps + ("T1", "O6"), key=lambda k: pieces[k])
  ks = tuple(pieces[k] for k in ps)

  # create a solver for this collection of pieces
  class Teaser2838(Polyiamonds1234567):

    height = 4
    width = 4

    # place T1 in an edge position, and solve for the remaining pieces
    def coordinates(self):
      holes = [(1, 0, 1)]
      return sorted(set(self.coordinates_hexagon(2)).difference(holes))

    piece_data = dict((k, piece_data[k]) for k in ps[1:])


  # solve the puzzle
  n = solve(Teaser2838, verbose=0)
  r[ks] += n
  printf("{ks} = {n} solutions")

# look for a unique solution
for (k, v) in r.items():
  if v == 1:
    printf("solution = {k}")

import puzzler.coordsys

from puzzler.puzzles.polyiamonds import Polyiamonds1234567

from StringIO import StringIO

import re

# a wrapper to capture output from the polyform puzzler

def solve(puzzle, verbose=0):

# collect the output

output = StringIO()

puzzler.run(puzzle, output_stream=output)

# count the solutions

r = output.getvalue()

if verbose: printf("\n--- polyform puzzler --\n\n{r}\n--- end ---\n")

m = re.search("^(\d+)\ssolutions?,", r, re.MULTILINE)

if m is None: return

return int(m.group(1))

from itertools import combinations

from collections import defaultdict

from enigma import diff, printf

pieces = {

"T1": 1,

"D2": 2,

"I3": 3,

"T4": 4,

"I4": 4,

"I5": 5,

"O6": 6,

"I6": 6,

"I7": 7,

"D7": 7,

"d8": 8, # extra size 8 piece ("diamond")

"t8": 8, # extra size 8 piece ("trapeziod")

}

# define the pieces (we can copy the pieces of size 7 or less)

piece_data = {

'd8': (((0, 0, 1), (1, 0, 0), (0, -1, 1), (1, -1, 0), (1, -1, 1), (0, 1, 0), (1, -2, 1)), {}),

't8': (((0, 0, 1), (1, 0, 0), (0, -1, 1), (1, -1, 0), (1, -1, 1), (0, 1, 0), (0, -1, 0)), {}),

}

for k in pieces.keys():

if k not in piece_data:

piece_data[k] = Polyiamonds1234567.piece_data[k]

# accumulate results by the size of the pieces

r = defaultdict(int)

# choose 4 pieces to go with T1 and O6

for ps in combinations(diff(pieces.keys(), ("T1", "O6")), 4):

ns = list(pieces[k] for k in ps)

if not(sum(ns) == 17 and max(ns) > 6): continue

# pieces used in this puzzle

ps = sorted(ps + ("T1", "O6"), key=lambda k: pieces[k])

ks = tuple(pieces[k] for k in ps)

# create a solver for this collection of pieces

class Teaser2838(Polyiamonds1234567):

height = 4

width = 4

# place T1 in an edge position, and solve for the remaining pieces

def coordinates(self):

holes = [(1, 0, 1)]

return sorted(set(self.coordinates_hexagon(2)).difference(holes))

piece_data = dict((k, piece_data[k]) for k in ps[1:])

# solve the puzzle

n = solve(Teaser2838, verbose=0)

r[ks] += n

printf("{ks} = {n} solutions")

# look for a unique solution

for (k, v) in r.items():

if v == 1:

printf("solution = {k}")

Note that the Polyform Puzzler framework works with Python 2, but not Python 3.

I’ve used a variant of the wrapper code I wrote for Enigma 321 [ https://enigmaticcode.wordpress.com/2015/11/27/enigma-321-going-to-pieces/ ] to find the number of solutions using the Polyform Puzzler framework, and also a couple of useful routines from the enigma.py library [ https://www.magwag.plus.com/jim/enigma.html ].

Jim Randell permalink

Note that really I should be recording the solutions by the numbers of counties (= size of the pieces) and the positions of Goneril’s and Regan’s pieces.

We can achieve this by modifying the solve() routine to return the positions of the pieces (instead of just the number of solutions), and then accumulate the positions of O6 and the largest piece against the size of the pieces.

This doesn’t affect the run time, and the overall answer is the same.

Reply

Sunday Times Teaser 2838 – King Lear IV

by Nick MacKinnon

Published: 12 February 2017 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta