Sunday Times Teaser 2773 – King Lear III

Brian Gladman permalink


from itertools import combinations

# return true if the product of the numbers in
# the sequence s is a perfect square
def is_square_product(s):
  x = 1
  for n in s:
    x *= n
  return int(x ** 0.5 + 0.5) ** 2 == x

# return a dictionary of the other squares that
# are edge connected to each square 
adj = dict()
for x in range(4):
  for y in range(4):
    a = []
    for  xx in (x - 1, x + 1):
      if 0 <= xx < 4:
        a.append(xx + 4 * y + 1)    
    for  yy in (y - 1, y + 1):
      if 0 <= yy < 4:
        a.append(x + 4 * yy + 1)
    adj[x + 4 * y + 1] = set(a)
  
# return true if a set of squares form a connected region
def connected(p):
  # if two sets of squares in a list of such sets have 
  # any squares that are connected, combine the two sets 
  def combine(s):
    for s1, s2 in combinations(s, 2):
      if any(y in adj[x] for x in s1 for y in s2):
        s[s.index(s1)].update(s2)
        s.remove(s2)
        return True
    return False
  sets = [set([n]) for n in p]
  # combine any sets that have connected members
  while combine(sets):
    pass
  # are all squares connected?
  return len(sets) == 1

# after selecting the king's and the eldest daughter's squares
# check that the rest can be allocated connected regions
# 
#   n     the number of daughters
#   nsq   the number of squares per daughter
#   r     the so far unallocated squares

def do_rest(n, nsq, r, d=tuple()):
  # if one daughter remains
  if n == 1:
    # and the remaining squares are connected
    if connected(r):
      # we have a possible solution
      yield tuple(sorted(d + (r,)))
  else:
    # allocate squares for the next daughter
    for s in combinations(r, nsq):
      # but only if they are connected
      if connected(s):
        # continue on to the next daughter
        yield from do_rest(n - 1, nsq, 
                      tuple(x for x in r if x not in s), d + (s,))  

pieces = tuple(range(1, 17))
# a minimum of 3 daughters gives a maximum of 5 squares for each 
# making 4 the maximum number of squares for the king
for nsqr_king in range(1, 5):
  for nsqr_daughters in range(nsqr_king + 1, 6):
    daughters, rem = divmod(16 - nsqr_king, nsqr_daughters)
    if not rem:
      
      # selecct the squares for the king
      for king_sqrs in combinations(pieces, nsqr_king):
        if is_square_product(king_sqrs) and connected(king_sqrs):
          r1 = tuple(x for x in pieces if x not in king_sqrs)
          
          # selecct the squares for the eldest daughter
          for ed_sqrs in combinations(r1, nsqr_daughters):
            if is_square_product(ed_sqrs) and connected(ed_sqrs):
              r2 = tuple(x for x in r1 if x not in ed_sqrs)

              # now find solutions for the remaining daughters
              sol = None
              for r in do_rest(daughters - 1, nsqr_daughters, r2):
                # we want results for which there is only one solution for
                # the remaining daughters so exit if there is more than one
                if sol and sol != r:
                  break
                sol = r
              else:
                if sol:
                  fs = 'King {}, First Daughter {}, Other(s) {}'
                  print(fs.format(king_sqrs, ed_sqrs, sol))

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

from itertools import combinations

# return true if the product of the numbers in

# the sequence s is a perfect square

def is_square_product(s):

x = 1

for n in s:

x *= n

return int(x ** 0.5 + 0.5) ** 2 == x

# return a dictionary of the other squares that

# are edge connected to each square

adj = dict()

for x in range(4):

for y in range(4):

a = []

for xx in (x - 1, x + 1):

if 0 <= xx < 4:

a.append(xx + 4 * y + 1)

for yy in (y - 1, y + 1):

if 0 <= yy < 4:

a.append(x + 4 * yy + 1)

adj[x + 4 * y + 1] = set(a)

# return true if a set of squares form a connected region

def connected(p):

# if two sets of squares in a list of such sets have

# any squares that are connected, combine the two sets

def combine(s):

for s1, s2 in combinations(s, 2):

if any(y in adj[x] for x in s1 for y in s2):

s[s.index(s1)].update(s2)

s.remove(s2)

return True

return False

sets = [set([n]) for n in p]

# combine any sets that have connected members

while combine(sets):

pass

# are all squares connected?

return len(sets) == 1

# after selecting the king's and the eldest daughter's squares

# check that the rest can be allocated connected regions

#

# n the number of daughters

# nsq the number of squares per daughter

# r the so far unallocated squares

def do_rest(n, nsq, r, d=tuple()):

# if one daughter remains

if n == 1:

# and the remaining squares are connected

if connected(r):

# we have a possible solution

yield tuple(sorted(d + (r,)))

else:

# allocate squares for the next daughter

for s in combinations(r, nsq):

# but only if they are connected

if connected(s):

# continue on to the next daughter

yield from do_rest(n - 1, nsq,

tuple(x for x in r if x not in s), d + (s,))

pieces = tuple(range(1, 17))

# a minimum of 3 daughters gives a maximum of 5 squares for each

# making 4 the maximum number of squares for the king

for nsqr_king in range(1, 5):

for nsqr_daughters in range(nsqr_king + 1, 6):

daughters, rem = divmod(16 - nsqr_king, nsqr_daughters)

if not rem:

# selecct the squares for the king

for king_sqrs in combinations(pieces, nsqr_king):

if is_square_product(king_sqrs) and connected(king_sqrs):

r1 = tuple(x for x in pieces if x not in king_sqrs)

# selecct the squares for the eldest daughter

for ed_sqrs in combinations(r1, nsqr_daughters):

if is_square_product(ed_sqrs) and connected(ed_sqrs):

r2 = tuple(x for x in r1 if x not in ed_sqrs)

# now find solutions for the remaining daughters

sol = None

for r in do_rest(daughters - 1, nsqr_daughters, r2):

# we want results for which there is only one solution for

# the remaining daughters so exit if there is more than one

if sol and sol != r:

break

sol = r

else:

if sol:

fs = 'King {}, First Daughter {}, Other(s) {}'

print(fs.format(king_sqrs, ed_sqrs, sol))

Reply

Trevor permalink

Hi Brian,
I couldn’t get your solution to run (no module named ‘number_theory’). Here is my simplistic solution:


for a in range(1, 17):
  for b in range(a + 1, 17):
    # a, b, c etc must be contiguous
    if b == a + 1 or b == a + 4:
      for c in range(b + 1, 16):
        if (c == b + 1 or c == b + 4 or 
            c == a + 1 or c == a + 4):
          for d in range(c + 1, 17):
            if (d == c + 1 or d == c + 4 or 
                d == b + 1 or d == b + 4 or 
                d == a + 1 or d == a + 4):
              for e in range(d + 1, 17):
                if (e == d + 1 or e == d + 4 or 
                    e == c + 1 or e == c + 4 or 
                    e == b + 1 or e == b + 4 or 
                    e == a + 1 or e == a + 4):
                  x = a * b * c * d * e
                  y = x ** 0.5
                  if y == int(y):
                    print(a, b, c, d, e, x, y)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

for a in range(1, 17):

for b in range(a + 1, 17):

# a, b, c etc must be contiguous

if b == a + 1 or b == a + 4:

for c in range(b + 1, 16):

if (c == b + 1 or c == b + 4 or

c == a + 1 or c == a + 4):

for d in range(c + 1, 17):

if (d == c + 1 or d == c + 4 or

d == b + 1 or d == b + 4 or

d == a + 1 or d == a + 4):

for e in range(d + 1, 17):

if (e == d + 1 or e == d + 4 or

e == c + 1 or e == c + 4 or

e == b + 1 or e == b + 4 or

e == a + 1 or e == a + 4):

x = a * b * c * d * e

y = x ** 0.5

if y == int(y):

print(a, b, c, d, e, x, y)

By inspection the last 2 solutions are not contiguous; the second solution is the only unique division of the other 2 daughters with Lear keeping 16.

EDIT: I see your program has now changed – it runs perfectly.

Reply

Brian Gladman permalink

Hi Trevor,

I have tidied up your program a bit – I hope you don’t mind. You can format your Python code yourself by adding tags – see the ‘About’ item in the menu above.

For future reference, many of my solutions use my number theory library which is available here

Reply

Trevor permalink

I appreciate the tidying up – I couldn’t find how to wrap lines.
I see it’s in PEP8.
I don’t understand the ‘adding tags’ story – I can’t find anything in About?
Unless you meant ‘tabs’ – in which case I’ve already set my indent to 2 spaces.
Also as a matter of interest it seems like your editor has line nos. whereas the IDLE editor doesn’t. What editor do you use?

Reply

Brian Gladman permalink

Hi Trevor,

A ‘tag’ is just text you put inside square brackets (i.e. [ and ]) or inside angle brackets (i.e. < and >) to indicate that the following text is to be formatted in a specific way. If you add the text ‘pre’ inside angle brackets (without the quotes) before your Python code and then the text ‘/pre’ (again inside angle brackets without the quotes) after your code, it will then be formatted as the Python code above is. This is explained in the ‘About’ menu item above. This will also display line numbers for your code automatically (my Python IDE is Wing, which doesn’t add line numbers).

I do think that 2 space indents are good as this helps to save horizontal space when code is being displayed. And it is best to add brackets around lines when you want to put them on more than one lines (as I have done above). I also like to use PEP8 guidelines for code display as this helps people understand what it is doing.

Reply

Trevor permalink

Thanks Brian – got it.

Reply

Jim Randell permalink

I thought this was quite a good puzzle, involving several steps to arrive at the solution.

This Python program uses several useful routines from the enigma.py library. It runs in 135ms.


from itertools import combinations, product
from collections import defaultdict
from enigma import irange, multiply, is_square, filter2, diff, first, printf
 
# consider the grid:
#
#  1  2  3  4
#  5  6  7  8
#  9 10 11 12
# 13 14 15 16
 
# the plot numbers in the grid
plots = set(irange(1, 16))
 
# the adjacency matrix
adj = dict()
for i in plots:
  (y, x) = divmod(i - 1, 4)
  adj[i] = tuple(j for (g, j) in ((y > 0, i - 4), (x > 0, i - 1), (x < 3, i + 1), (y < 3, i + 4)) if g)
 
# are the pieces in ps connected to the pieces in cs?
def is_connected(ps, cs=set()):
  if not ps:
    return True
  elif not cs:
    # move one piece from ps to cs
    ps = set(ps)
    x = ps.pop()
    return is_connected(ps, set([x]))
  else:
    # partition ps into those connected to cs and those that aren't
    (pcs, pns) = filter2((lambda p: cs.intersection(adj[p])), ps)
    return bool(pcs) and is_connected(pns, cs.union(pcs))
 
# construct t connected pieces of n squares from ps
def construct(t, n, ps):
  # is there only one piece to construct?
  if t == 1:
    if is_connected(ps):
      yield [ps]
  else:
    # choose n connected pieces from ps
    ps = set(ps)
    x = ps.pop()
    for xs in combinations(ps, n - 1):
      xs = (x,) + xs
      if is_connected(xs):
        for cs in construct(t - 1, n, diff(ps, xs)):
          yield [xs] + cs
 
# find square numbers that are the product of n connected plots
# record the connected plots by the square number
squares = defaultdict(list)
for n in irange(1, 7):
  for s in combinations(plots, n):
    m = multiply(s)
    r = is_square(m)
    if r is None: continue
    if not is_connected(s): continue
    printf("[n={n}, plots={s}, product={m}, sqrt={r}]")
    squares[n].append(s)
 
# choose the number of daughters
for d in irange(2, 7):
  # number of plots per daughter
  for n in irange(2, 16 // d):
    # the remaining plots
    r = 16 - n * d
    if not(0 < r < n): continue
 
    # find regions for the king and the eldest daughter
    printf("[considering daughters={d}, plots={n}, remaining={r} ...]")
    for (K, E) in product(squares[r], squares[n]):
      # they must be disjoint
      if set(K).intersection(E): continue
      # construct connected plots for the rest of the daughters
      # and look for two different ways
      ds = first(construct(d - 1, n, plots.difference(K, E)), 2)
      printf("K={K} E={E} ds={ds}")
 
      # the solution has only one way to construct the remaining regions
      if len(ds) == 1: printf("*** SOLUTION FOUND ***")

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

from itertools import combinations, product

from collections import defaultdict

from enigma import irange, multiply, is_square, filter2, diff, first, printf

# consider the grid:

#

# 1 2 3 4

# 5 6 7 8

# 9 10 11 12

# 13 14 15 16

# the plot numbers in the grid

plots = set(irange(1, 16))

# the adjacency matrix

adj = dict()

for i in plots:

(y, x) = divmod(i - 1, 4)

adj[i] = tuple(j for (g, j) in ((y > 0, i - 4), (x > 0, i - 1), (x < 3, i + 1), (y < 3, i + 4)) if g)

# are the pieces in ps connected to the pieces in cs?

def is_connected(ps, cs=set()):

if not ps:

return True

elif not cs:

# move one piece from ps to cs

ps = set(ps)

x = ps.pop()

return is_connected(ps, set([x]))

else:

# partition ps into those connected to cs and those that aren't

(pcs, pns) = filter2((lambda p: cs.intersection(adj[p])), ps)

return bool(pcs) and is_connected(pns, cs.union(pcs))

# construct t connected pieces of n squares from ps

def construct(t, n, ps):

# is there only one piece to construct?

if t == 1:

if is_connected(ps):

yield [ps]

else:

# choose n connected pieces from ps

ps = set(ps)

x = ps.pop()

for xs in combinations(ps, n - 1):

xs = (x,) + xs

if is_connected(xs):

for cs in construct(t - 1, n, diff(ps, xs)):

yield [xs] + cs

# find square numbers that are the product of n connected plots

# record the connected plots by the square number

squares = defaultdict(list)

for n in irange(1, 7):

for s in combinations(plots, n):

m = multiply(s)

r = is_square(m)

if r is None: continue

if not is_connected(s): continue

printf("[n={n}, plots={s}, product={m}, sqrt={r}]")

squares[n].append(s)

# choose the number of daughters

for d in irange(2, 7):

# number of plots per daughter

for n in irange(2, 16 // d):

# the remaining plots

r = 16 - n * d

if not(0 < r < n): continue

# find regions for the king and the eldest daughter

printf("[considering daughters={d}, plots={n}, remaining={r} ...]")

for (K, E) in product(squares[r], squares[n]):

# they must be disjoint

if set(K).intersection(E): continue

# construct connected plots for the rest of the daughters

# and look for two different ways

ds = first(construct(d - 1, n, plots.difference(K, E)), 2)

printf("K={K} E={E} ds={ds}")

# the solution has only one way to construct the remaining regions

if len(ds) == 1: printf("*** SOLUTION FOUND ***")

Solution: The Eldest daughter gets plots 1, 2, 5, 9 and 10. The King keeps plot 16.

The division of the kingdom is shown below:

There are three daughters, who each receive a realm of 5 plots. The King keeps a realm of 1 plot for himself.

The Eldest daughter’s realm is shaded red, the other two daughter’s realms are shaded blue. The King keeps the plot shaded black.I thought it was quite an interesting puzzle, although I did alter the wording slightly so that it made more sense.

The equivalent problem considering the sum of the squares in the realm (rather than the product) has many solutions. (You can just change the call to multiply() to use sum() instead).

Reply

Trevor permalink

My program needs to be amended(all for in range(1,16) should be (1,17))!


for a in range(1,17):
  for b in range(a + 1, 17):
    # a, b, c etc must be contiguous
    if b == a + 1 or b == a + 4:
      for c in range(b + 1, 17):
        if (c == b + 1 or c == b + 4 or 
            c == a + 1 or c == a + 4):
          for d in range(c + 1, 17):
            if (d == c + 1 or d == c + 4 or 
                d == b + 1 or d == b + 4 or 
                d == a + 1 or d == a + 4):
              for e in range(d + 1, 17):
                if (e == d + 1 or e == d + 4 or 
                    e == c + 1 or e == c + 4 or 
                    e == b + 1 or e == b + 4 or 
                    e == a + 1 or e == a + 4):
                  x = a * b * c * d * e
                  y = x ** 0.5
                  if y == int(y):
                    print(a, b, c, d, e, x, y)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

for a in range(1,17):

for b in range(a + 1, 17):

# a, b, c etc must be contiguous

if b == a + 1 or b == a + 4:

for c in range(b + 1, 17):

if (c == b + 1 or c == b + 4 or

c == a + 1 or c == a + 4):

for d in range(c + 1, 17):

if (d == c + 1 or d == c + 4 or

d == b + 1 or d == b + 4 or

d == a + 1 or d == a + 4):

for e in range(d + 1, 17):

if (e == d + 1 or e == d + 4 or

e == c + 1 or e == c + 4 or

e == b + 1 or e == b + 4 or

e == a + 1 or e == a + 4):

x = a * b * c * d * e

y = x ** 0.5

if y == int(y):

print(a, b, c, d, e, x, y)

Reply

Sunday Times Teaser 2773 – King Lear III

by Nick MacKinnon

Published: 15 November 2015 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta