Sunday Times Teaser 2828 – Return to Zenda

by Nick MacKinnon

Published: 4 December 2016 (link)

Each postcode in Ruritania consists of ten digits, the first three showing the area, the next three showing the town, and the final four showing the house. Just twelve houses have “lucky” postcodes that have no repeated digit and which consist of two three-figure squares followed by a four-figure square. Rudolph lives in such a house and he recently met a girl called Flavia. She only told him that hers was the only house in her area with a lucky postcode, and that her area/town/house numbers were all bigger than his. He has found a postcode satisfying these conditions and sent her a Christmas card, but it has been returned as it was not her postcode.

What is Rudolph’s postcode?

2 Comments Leave one →

Brian Gladman permalink


from collections import defaultdict
from itertools import product

# for three and four digit squares with no repeated digits
# map their digit sets to lists of squares with these digits
sq3, sq4 = defaultdict(list), defaultdict(list)
for s in (x ** 2 for x in range(10, 100)):
  dgts = [int(x) for x in str(s)]
  key = frozenset(dgts)
  if len(dgts) == len(key):
    (sq3 if len(key) == 3 else sq4)[key].append(s)

# map area codes to postcodes in the area
pc = defaultdict(list)
# the three digit area and town codes
for a, t in product(sq3.keys(), repeat=2):
  # ... cannot share digits
  if not a & t:
    # and the house code
    for h in sq4.keys():
      # ... cannot share digits with the area or town code
      if not (a | t) & h:
        for p in product(sq3[a], sq3[t], sq4[h]):
          pc[p[0]].append(p)

# map Rudolph's postcodes to Flavia's possible postcodes 
r2f = defaultdict(list)
# consider possible area codes for Flavia
for af in pc.keys(): 
  # Flavia's postcode is unique within her area
  if len(pc[af]) == 1:
    fc = pc[af][0]
    # consider possible postcodes for Rudolph
    for r in pc.keys():
      for rc in pc[r]:
        # Flavia's values are all greater than Rudolph's
        if all(r < f for r, f in zip(rc, fc)):
          r2f[rc].append(fc)

# find Rudolph's postcodes that do not uniquely identify Flavia
for r in r2f:
  if len(r2f[r]) > 1:
    print("Rudolph's postcode is {}".format(r))

from collections import defaultdict

from itertools import product

# for three and four digit squares with no repeated digits

# map their digit sets to lists of squares with these digits

sq3, sq4 = defaultdict(list), defaultdict(list)

for s in (x ** 2 for x in range(10, 100)):

dgts = [int(x) for x in str(s)]

key = frozenset(dgts)

if len(dgts) == len(key):

(sq3 if len(key) == 3 else sq4)[key].append(s)

# map area codes to postcodes in the area

pc = defaultdict(list)

# the three digit area and town codes

for a, t in product(sq3.keys(), repeat=2):

# ... cannot share digits

if not a & t:

# and the house code

for h in sq4.keys():

# ... cannot share digits with the area or town code

if not (a | t) & h:

for p in product(sq3[a], sq3[t], sq4[h]):

pc[p[0]].append(p)

# map Rudolph's postcodes to Flavia's possible postcodes

r2f = defaultdict(list)

# consider possible area codes for Flavia

for af in pc.keys():

# Flavia's postcode is unique within her area

if len(pc[af]) == 1:

fc = pc[af][0]

# consider possible postcodes for Rudolph

for r in pc.keys():

for rc in pc[r]:

# Flavia's values are all greater than Rudolph's

if all(r < f for r, f in zip(rc, fc)):

r2f[rc].append(fc)

# find Rudolph's postcodes that do not uniquely identify Flavia

for r in r2f:

if len(r2f[r]) > 1:

print("Rudolph's postcode is {}".format(r))

Jim Randell permalink

I felt that the wording on this Teaser could have been a bit clearer.

The code below uses squares that do not use leading zeros, and it turns out there exactly 12 “lucky” postcodes that can be constructed using this interpretation, so it is probably what the puzzle setter had in mind.


from itertools import product, combinations
from enigma import irange, is_duplicate, filter_unique, unpack, join, printf

# find n-digit squares from a^2 to b^2 with no repeated digits (as
# strings) leading zeros are allowed
def squares(n, a, b):
  r = list()
  for i in irange(a, b):
    s = str(i * i).zfill(n)
    if not is_duplicate(s):
      r.append(s)
  return r

# 3 and 4 digit squares
s3s = squares(3, 10, 31)
s4s = squares(4, 31, 99)

# collect "lucky" (pandigital) postcodes
lucky = list()
for (area, town, house) in product(s3s, s3s, s4s):
  if len(set(area + town + house)) != 10: continue
  lucky.append((area, town, house))

printf("[{n} lucky postcodes]", n=len(lucky))

# choose the 12 lucky postcodes
for postcodes in combinations(lucky, 12):

  # flavias postcode is the only (possible) lucky postcode in the area
  (fs, _) = filter_unique(postcodes, unpack(lambda a, t, h: a))

  # consider rudolph's postcode
  for (ra, rt, rh) in postcodes:
    # find possible postcodes for flavia
    f = list((a, t, h) for (a, t, h) in fs if a > ra and t > rt and h > rh)
    # and there must be more than one possibility
    if len(f) > 1:
      printf("r = {ra}:{rt}:{rh}, f = [{f}]", 
                           f=join((join(x, sep=':') for x in f), sep=', '))

from itertools import product, combinations

from enigma import irange, is_duplicate, filter_unique, unpack, join, printf

# find n-digit squares from a^2 to b^2 with no repeated digits (as

# strings) leading zeros are allowed

def squares(n, a, b):

r = list()

for i in irange(a, b):

s = str(i * i).zfill(n)

if not is_duplicate(s):

r.append(s)

return r

# 3 and 4 digit squares

s3s = squares(3, 10, 31)

s4s = squares(4, 31, 99)

# collect "lucky" (pandigital) postcodes

lucky = list()

for (area, town, house) in product(s3s, s3s, s4s):

if len(set(area + town + house)) != 10: continue

lucky.append((area, town, house))

printf("[{n} lucky postcodes]", n=len(lucky))

# choose the 12 lucky postcodes

for postcodes in combinations(lucky, 12):

# flavias postcode is the only (possible) lucky postcode in the area

(fs, _) = filter_unique(postcodes, unpack(lambda a, t, h: a))

# consider rudolph's postcode

for (ra, rt, rh) in postcodes:

# find possible postcodes for flavia

f = list((a, t, h) for (a, t, h) in fs if a > ra and t > rt and h > rh)

# and there must be more than one possibility

if len(f) > 1:

printf("r = {ra}:{rt}:{rh}, f = [{f}]",

f=join((join(x, sep=':') for x in f), sep=', '))

The code uses some utility functions from the enigma.py library [ https://www.magwag.plus.com/jim/enigma.html ], and runs in 50ms.

An alternative interpretation would be allow squares with leading zeros, which gives 34 possible “lucky” postcodes, but we are told only 12 of them are in use, which gives C(34, 12) = 131,128,140 different sets of “lucky” postcodes that may be in use. In this interpretation there is also the problem of how Flavia “knows” that hers is the only lucky postcode in her area. Is it the only possible lucky postcode in her area? Or just the only one (currently) in use? In my program I have implemented the latter.

It is trivial to modify the program to consider this scenario (just change the a parameters in the calls to squares() to 0), and if you do it will find many hundreds of thousands of possible situations, and as there would be multiple answers for Rudolph’s postcode I think it’s probably not what the setter had in mind.

Sunday Times Teaser 2828 – Return to Zenda

by Nick MacKinnon

Published: 4 December 2016 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta