Sunday Times Teaser 2788 – Red-Letter Days

by Nick MacKinnon

Published: 28 February 2016 (link)

The months of my 2016 calendar are headed M, T, W, Th, F, Sa, Su, with the dates 1, 2, 3 … in a grid of squares underneath. I have shaded all the days on which I have meetings planned — all of them being on weekdays. For example, in February the days 1, 2, 3, 4, 8 and 9 are shaded: these shaded squares form a connected piece and the product of the numbers is a perfect cube. The same is true of the shaded squares in another month — and in fact it’s the largest possible such cube in the calendar. My last meeting in that month is on my aunt’s birthday.

What is her birthday?

3 Comments Leave one →

Brian Gladman permalink

I liked this teaser but it is one that is a great deal less effort when done manually rather than by computer. Fortunately, however, I had various pieces already (finding connected areas in a grid of cells was needed in Teaser 2773) so it was not too hard to put a program together.


from itertools import combinations, product
from calendar import month_name as name
from number_theory import Primes, factors

# month lengths in 2016
month_len = (0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)

# if the product of days in a month give perfect cubes, the days
# won't include primes above 7 since there will be too few of them
ex_pr = set(Primes().list(11, 32))

# output a calendar month in grid form
def grid_out(grid):
  for row in grid:
    if len(set(row)) != 1:
      for day in row:
        print(' {:02d}'.format(day) if day else '   ', end='')
      print()
  print()

# return a dictionary of the days in a calendar grid that
# are adjacent (horizontally or vertically) to other days
def adjacency_matrix(g, nr, nc):
  adj = dict()
  for r, c in product(range(nr), range(nc)):
    if g[r][c]:
      a = ([(i, c) for i in (r - 1, r + 1) if 0 <= i < nr and g[i][c]] +
           [(r, i) for i in (c - 1, c + 1) if 0 <= i < nc and g[r][i]])
      adj[(r, c)] = set(a)
  return adj

# return true if a set of days in a calendar grid form a connected region
def connected(grid):
  nr, nc = len(grid), len(grid[0])
  # if two sets of cells in a list of such sets have
  # any cells 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
  adj = adjacency_matrix(grid, nr, nc)
  sets = [set([n]) for n in adj]
  # combine any sets that have connected members
  while combine(sets):
    pass
  # return sets of sorted lists of connected cell contents
  return set(tuple(sorted(grid[x][y] for x, y in s))
                   for s in sets)

# form a calendar grid for a month, keeping columns from Monday
# to Friday and only days that can contribute to cubic products
def create_grid(month):
  grid = []
  # day of the week (0 = Sunday) for the first day
  pos = (3 + sum(month_len[:month])) % 7
  # set grid cells to zero if they don't have days in them
  row = [0] * (pos + 1) if pos < 5 else []
  # for days in this month
  for day in range(1, month_len[month] + 1):
    # find its position on a row
    pos = (pos + 1) % 7
    # if it is not in a weekend
    if pos < 5:
      # add this day to the current row if it can contribute to products
      row += [0 if any(day % p == 0 for p in ex_pr) else day]
    elif pos == 6:
      # if it is a Saturday add the row to the grid
      grid += [row]
      row = []
  # add last row if it is not empty
  if row:
    grid += [row + [0] * 5][:5]
  # return days left in the grid and the grid
  return [y for x in grid for y in x if y], grid

# find the maximum product for each month
def max_prod(month):
  # list the days remaining in the grid
  days, grid = create_grid(month)
  # map days to the exponents of their factors of 2, 3, 5 and 7
  f = {d:tuple(tuple(list(factors(d)).count(p)
                     for p in (2, 3, 5, 7))) for d in days}
  # consider sets of connected days
  ss = []
  for s in connected(grid):
    # consider all combinations of days
    for p in product((0, 1), repeat=len(s)):
      dd = [d for d, m in zip(s, p) if m]
      # add the exponents of 2, 3, 5 and 7 in these days
      sm = [sum(x) for x in zip(*(f[d] for d in dd))]
      # select sums where all exponents are multiples of three
      if sm and all(x % 3 == 0 for x in sm):
        pr = 1
        for p, e in zip((2, 3, 5, 7), sm):
          pr *= p ** (e // 3)
        ss += [(pr, month, dd)]

  # now look for cubic products with connected cells
  max_cube = 0
  for c, m, d in sorted(ss, reverse=True):
    # form the grid for the days, check if they are connected
    # and return lists of days for the maximum cubic product
    g = [[x if x in d else 0 for x in r] for r in grid]
    if len(connected(g)) == 1:
      if c >= max_cube:
        max_cube = c
        yield c, d
    if c < max_cube:
      return

max_cube, mth, last_day = 0, 0, 0
for month in range(1, 13):
  for c, d in max_prod(month):
    if c > max_cube:
      max_cube, mth, last_day = c, month, d[-1]
    print('{:2d} {:5d} {}'.format(month, c, d))
fs = "nThe Aunt's birthday is {} {} (cube = {}^3)."
print(fs.format(name[mth], last_day, max_cube))

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

from itertools import combinations, product

from calendar import month_name as name

from number_theory import Primes, factors

# month lengths in 2016

month_len = (0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)

# if the product of days in a month give perfect cubes, the days

# won't include primes above 7 since there will be too few of them

ex_pr = set(Primes().list(11, 32))

# output a calendar month in grid form

def grid_out(grid):

for row in grid:

if len(set(row)) != 1:

for day in row:

print(' {:02d}'.format(day) if day else ' ', end='')

print()

# return a dictionary of the days in a calendar grid that

# are adjacent (horizontally or vertically) to other days

def adjacency_matrix(g, nr, nc):

adj = dict()

for r, c in product(range(nr), range(nc)):

if g[r][c]:

a = ([(i, c) for i in (r - 1, r + 1) if 0 <= i < nr and g[i][c]] +

[(r, i) for i in (c - 1, c + 1) if 0 <= i < nc and g[r][i]])

adj[(r, c)] = set(a)

return adj

# return true if a set of days in a calendar grid form a connected region

def connected(grid):

nr, nc = len(grid), len(grid[0])

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

# any cells 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

adj = adjacency_matrix(grid, nr, nc)

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

# combine any sets that have connected members

while combine(sets):

pass

# return sets of sorted lists of connected cell contents

return set(tuple(sorted(grid[x][y] for x, y in s))

for s in sets)

# form a calendar grid for a month, keeping columns from Monday

# to Friday and only days that can contribute to cubic products

def create_grid(month):

grid = []

# day of the week (0 = Sunday) for the first day

pos = (3 + sum(month_len[:month])) % 7

# set grid cells to zero if they don't have days in them

row = [0] * (pos + 1) if pos < 5 else []

# for days in this month

for day in range(1, month_len[month] + 1):

# find its position on a row

pos = (pos + 1) % 7

# if it is not in a weekend

if pos < 5:

# add this day to the current row if it can contribute to products

row += [0 if any(day % p == 0 for p in ex_pr) else day]

elif pos == 6:

# if it is a Saturday add the row to the grid

grid += [row]

row = []

# add last row if it is not empty

if row:

grid += [row + [0] * 5][:5]

# return days left in the grid and the grid

return [y for x in grid for y in x if y], grid

# find the maximum product for each month

def max_prod(month):

# list the days remaining in the grid

days, grid = create_grid(month)

# map days to the exponents of their factors of 2, 3, 5 and 7

f = {d:tuple(tuple(list(factors(d)).count(p)

for p in (2, 3, 5, 7))) for d in days}

# consider sets of connected days

ss = []

for s in connected(grid):

# consider all combinations of days

for p in product((0, 1), repeat=len(s)):

dd = [d for d, m in zip(s, p) if m]

# add the exponents of 2, 3, 5 and 7 in these days

sm = [sum(x) for x in zip(*(f[d] for d in dd))]

# select sums where all exponents are multiples of three

if sm and all(x % 3 == 0 for x in sm):

pr = 1

for p, e in zip((2, 3, 5, 7), sm):

pr *= p ** (e // 3)

ss += [(pr, month, dd)]

# now look for cubic products with connected cells

max_cube = 0

for c, m, d in sorted(ss, reverse=True):

# form the grid for the days, check if they are connected

# and return lists of days for the maximum cubic product

g = [[x if x in d else 0 for x in r] for r in grid]

if len(connected(g)) == 1:

if c >= max_cube:

max_cube = c

yield c, d

if c < max_cube:

return

max_cube, mth, last_day = 0, 0, 0

for month in range(1, 13):

for c, d in max_prod(month):

if c > max_cube:

max_cube, mth, last_day = c, month, d[-1]

print('{:2d} {:5d} {}'.format(month, c, d))

fs = "nThe Aunt's birthday is {} {} (cube = {}^3)."

print(fs.format(name[mth], last_day, max_cube))

Jim Randell permalink

Brian, would I be right in thinking your program finds a maximum connected region of 12^3 for August?

Because I think you can get to 120^3 using [1, 2, 3, 4, 5, 8, 10, 12, 15].

It also works for February. Other than that the maximum values my program finds agree with yours.

Reply
Brian Gladman permalink

Hi Jim,

Yes, it misses the 120^3 because I wrongly excluded day 1 from the grid. I have changed it now because that is not the only issue with my original version, which might have missed a maximum cube because I didn’t check all combinations of days, only the most likely ones.

Reply

Sunday Times Teaser 2788 – Red-Letter Days

by Nick MacKinnon

Published: 28 February 2016 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta