Sunday Times Teaser 2716 – Millennial Squares

by Adrian Somerfield

The pupils in my class each created a set of cards with a digit on each side in such a way that they could use four of their cards to spell out all the years in this millennium that are perfect squares. One pupil managed this with the smallest possible number of cards.

In fact, in continuing the consecutive sequence of ‘square years’ into the next millennium, his set of cards was such that he could continue as far as is possible with this number of cards.

What was the highest square year he could create?

One Comment Leave one →

brian gladman permalink


from itertools import combinations, permutations
from collections import defaultdict

# check whether a set of cards can make a given year
def solve(y, cards):
  if not y:
    return True
  for t in cards:
    if y[0] in t and solve(y[1:], cards - set((t,))):
      return True
  return False

# the span of 'square years' to be considered
sq_years = [str(x * x) for x in range(45, 100)]

digits = '0123456789'
# how many of each digit are necessary to make years up current year
min_dgts = defaultdict(int)
# the total number of digits to be used, mapped to the maximum year
# that they can cover and the actual digits needed
dgt_lists = defaultdict(tuple)

# for each year to be considered
for year in sq_years:
  # find out how many of each digit are needed
  for d in '0123456789':
    # set this as the number needed if the maximum so far
    min_dgts[d] = max(year.count(d), min_dgts[d])
  # the total number of digits needed
  n_dgts = sum(min_dgts.values())
  # if we need an even number of digits (i.e. for both card sides)
  if n_dgts % 2 == 0:
    # compile a  list of the digits needed
    dgts = sorted(''.join(k * v for k, v in min_dgts.items()))
    # save this if (a) a maximum year for this number of digits 
    # has not been set,  or (b) the current year for this number
    # of digits is higher than that previously found
    if n_dgts not in dgt_lists or year > dgt_lists[n_dgts][0]:
      dgt_lists[n_dgts] = (year, ''.join(dgts))

# find solutions for 'n_dgt' digits for a maximum year 'max_year'
# with the list of digits in 'dgts'
def find_sol(n_dgt, max_year, dgts):
  # pick the first digit on each card
  for c in combinations(dgts, n_dgt // 2):
    # now pick the second digit on each card
    for p in permutations(x for x in dgts if x not in c):
      # create the cards
      cards = set(x + y for x, y in zip(c, p))
      # only consider cards where first digit is less than second
      if all(x < y for x, y in cards):
        # check if all years up to and including max_year can be made
        if all(solve(y, cards) for y in sq_years if y <= max_year):
          # if so, return the set of cards that gives the solution
          yield tuple(sorted(cards))

# for each number of digits
for n_dgt in sorted(dgt_lists):
  # set the maximum year possible and the digits that are needed
  max_year, dgts = dgt_lists[n_dgt]
  # find and output a solution (if any)
  for s in find_sol(n_dgt, max_year, dgts):
    print('{:2d} {:4s} {}'.format(n_dgt // 2, max_year, s))
    break

from itertools import combinations, permutations

from collections import defaultdict

# check whether a set of cards can make a given year

def solve(y, cards):

if not y:

return True

for t in cards:

if y[0] in t and solve(y[1:], cards - set((t,))):

return True

return False

# the span of 'square years' to be considered

sq_years = [str(x * x) for x in range(45, 100)]

digits = '0123456789'

# how many of each digit are necessary to make years up current year

min_dgts = defaultdict(int)

# the total number of digits to be used, mapped to the maximum year

# that they can cover and the actual digits needed

dgt_lists = defaultdict(tuple)

# for each year to be considered

for year in sq_years:

# find out how many of each digit are needed

for d in '0123456789':

# set this as the number needed if the maximum so far

min_dgts[d] = max(year.count(d), min_dgts[d])

# the total number of digits needed

n_dgts = sum(min_dgts.values())

# if we need an even number of digits (i.e. for both card sides)

if n_dgts % 2 == 0:

# compile a list of the digits needed

dgts = sorted(''.join(k * v for k, v in min_dgts.items()))

# save this if (a) a maximum year for this number of digits

# has not been set, or (b) the current year for this number

# of digits is higher than that previously found

if n_dgts not in dgt_lists or year > dgt_lists[n_dgts][0]:

dgt_lists[n_dgts] = (year, ''.join(dgts))

# find solutions for 'n_dgt' digits for a maximum year 'max_year'

# with the list of digits in 'dgts'

def find_sol(n_dgt, max_year, dgts):

# pick the first digit on each card

for c in combinations(dgts, n_dgt // 2):

# now pick the second digit on each card

for p in permutations(x for x in dgts if x not in c):

# create the cards

cards = set(x + y for x, y in zip(c, p))

# only consider cards where first digit is less than second

if all(x < y for x, y in cards):

# check if all years up to and including max_year can be made

if all(solve(y, cards) for y in sq_years if y <= max_year):

# if so, return the set of cards that gives the solution

yield tuple(sorted(cards))

# for each number of digits

for n_dgt in sorted(dgt_lists):

# set the maximum year possible and the digits that are needed

max_year, dgts = dgt_lists[n_dgt]

# find and output a solution (if any)

for s in find_sol(n_dgt, max_year, dgts):

print('{:2d} {:4s} {}'.format(n_dgt // 2, max_year, s))

break

Sunday Times Teaser 2716 – Millennial Squares

by Adrian Somerfield

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta