Sunday Times Teaser 2843 – Child’s Play

by Andrew Skidmore

Published March 19 2017 (link)

Liam has a set of cards numbered from one to twelve. He can lay some or all of these in a row to form various numbers. For example the four cards:

6, 8, 11, 2

give a five-figure number. Also, that particular number is exactly divisible by the number on each of the cards used.

In this way Liam used his set of cards to find another much larger number that was divisible by each of the numbers on the cards used — in fact he found the largest such possible number.

What was that number?

2 Comments Leave one →

Brian Gladman permalink

Quite slow but it gets the job done.


# for cards numbered 1 .. 12 when laid side by side to
# form a number,  find <lnth> cards that give a number
# that is divisible by all of the values on the cards
def compose(lnth, cards, nbr = 0, seq=[], ln=0):
  # do we have the right number of cards
  if ln == lnth:
    # is the number divisible by all the card values
    if all(nbr % d == 0 for d in seq):
      yield nbr, seq
  else:
    # add another card and continue
    for card in cards:
      m = (10 if card < 10 else 100)
      yield from compose(lnth, [x for x in cards if x != card], 
                        m * nbr + card, seq + [card], ln + 1)

# if either the 5 or the 10 card is included, the number 
# must end in 5 or 10, which would mean that the number
# could not be divisible by 4, 8 or 12 and hence have a 
# maximum of nine cards; so look for sequences of ten 
# cards without the 5 and 10 cards (order the cards to 
# improve the search speed)
cards = [9, 8, 7, 6, 4, 3, 2, 12, 11, 1]

# look for the maximum number
max_nbr = 0
for nbr, seq in compose(10, cards):
  if nbr > max_nbr:
    max_nbr = nbr
    print(nbr, tuple(seq))

# for cards numbered 1 .. 12 when laid side by side to

# form a number, find <lnth> cards that give a number

# that is divisible by all of the values on the cards

def compose(lnth, cards, nbr = 0, seq=[], ln=0):

# do we have the right number of cards

if ln == lnth:

# is the number divisible by all the card values

if all(nbr % d == 0 for d in seq):

yield nbr, seq

else:

# add another card and continue

for card in cards:

m = (10 if card < 10 else 100)

yield from compose(lnth, [x for x in cards if x != card],

m * nbr + card, seq + [card], ln + 1)

# if either the 5 or the 10 card is included, the number

# must end in 5 or 10, which would mean that the number

# could not be divisible by 4, 8 or 12 and hence have a

# maximum of nine cards; so look for sequences of ten

# cards without the 5 and 10 cards (order the cards to

# improve the search speed)

cards = [9, 8, 7, 6, 4, 3, 2, 12, 11, 1]

# look for the maximum number

max_nbr = 0

for nbr, seq in compose(10, cards):

if nbr > max_nbr:

max_nbr = nbr

print(nbr, tuple(seq))

Frits permalink

Adapting the program to leave the loop early (“cards” is already kind of sorted).


from itertools import takewhile

# for cards numbered 1 .. 12 when laid side by side to
# form a number,  find <lnth> cards that give a number
# that is divisible by all of the values on the cards
def compose(lnth, cards, nbr = 0, seq=[], ln=0):
  # do we have the right number of cards
  if ln == lnth:
    # is the number divisible by all the card values
    if all(nbr % d == 0 for d in seq):
      yield nbr, seq
  else:
    # add another card and continue
    for card in cards:
      m = (10 if card < 10 else 100)
      yield from compose(lnth, [x for x in cards if x != card],
                         m * nbr + card, seq + [card], ln + 1)

# if either the 5 or the 10 card is included, the number
# must end in 5 or 10, which would mean that the number
# could not be divisible by 4, 8 or 12 and hence have a
# maximum of nine cards; so look for sequences of ten
# cards without the 5 and 10 cards (order the cards to
# improve the search speed)
cards = [9, 8, 7, 6, 4, 3, 2, 12, 11, 1]

# look for the maximum number
max_nbr = 0
for nbr, seq in compose(10, cards):
  # leave loop if first digits become too low
  if max_nbr > 0 and str(nbr)[:fdgts] < dgts2_9:
    break

  if nbr <= max_nbr: continue

  max_nbr = nbr
  print(nbr, tuple(seq))

  # determine first digits which we can use for breaking out of the loop
  dgts2_9 = "".join([str(x) for x in takewhile(lambda x: 1 < x < 10, seq)])
  fdgts = len(dgts2_9)

from itertools import takewhile

# for cards numbered 1 .. 12 when laid side by side to

# form a number, find <lnth> cards that give a number

# that is divisible by all of the values on the cards

def compose(lnth, cards, nbr = 0, seq=[], ln=0):

# do we have the right number of cards

if ln == lnth:

# is the number divisible by all the card values

if all(nbr % d == 0 for d in seq):

yield nbr, seq

else:

# add another card and continue

for card in cards:

m = (10 if card < 10 else 100)

yield from compose(lnth, [x for x in cards if x != card],

m * nbr + card, seq + [card], ln + 1)

# if either the 5 or the 10 card is included, the number

# must end in 5 or 10, which would mean that the number

# could not be divisible by 4, 8 or 12 and hence have a

# maximum of nine cards; so look for sequences of ten

# cards without the 5 and 10 cards (order the cards to

# improve the search speed)

cards = [9, 8, 7, 6, 4, 3, 2, 12, 11, 1]

# look for the maximum number

max_nbr = 0

for nbr, seq in compose(10, cards):

# leave loop if first digits become too low

if max_nbr > 0 and str(nbr)[:fdgts] < dgts2_9:

break

if nbr <= max_nbr: continue

max_nbr = nbr

print(nbr, tuple(seq))

# determine first digits which we can use for breaking out of the loop

dgts2_9 = "".join([str(x) for x in takewhile(lambda x: 1 < x < 10, seq)])

fdgts = len(dgts2_9)

Sunday Times Teaser 2843 – Child’s Play

by Andrew Skidmore

Published March 19 2017 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta