Updates from Jim Randell Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 12:43 pm on 1 July 2019 Permalink | Reply
    Tags:   

    Teaser 2902: Birthdays 2018 

    From The Sunday Times, 6th May 2018 [link] [link]

    Several friends have birthdays on different days in 2018.

    Replacing A by 1, B by 2, C by 3 … and Z by 26, each month and day can be replaced by a sequence of numbers. Every birthday is given numerically by day, date and month, as described above. For each friend, there is just one number common to each of their 3 sets of numbers. The number of friends is the largest possible.

    How many friends are there and what is the largest number of clear days between consecutive birthdays?

    [teaser2902]

     
    • Jim Randell's avatar

      Jim Randell 12:45 pm on 1 July 2019 Permalink | Reply

      The puzzle text is not completely clear, and allows several interpretations.

      I interpreted it as follows:

      A date, such as Friday 25th May 2018, is translated into a sequence of numbers as follows:

      Friday = (6, 18, 9, 4, 1, 25)
      25 = (25)
      May = (13, 1, 25)

      The “day of month” always provides a sequence with a single number in it, and this number must also appear in the “day name” sequence and the “month name” sequence (which are created by translating the letters to numbers). Furthermore it must be the only number that is shared between the translated sequences.

      In the example 25=Y occurs in FRIDAY and also in MAY, but it is not the only letter in common A=1 also occurs.

      Using this interpretation we find there are only four dates that meet the requirements. And we then look for the longest gap between consecutive dates in this set.

      This Python program runs in 83ms.

      Run: [ @repl.it ]

      import datetime
from enigma import (tuples, printf)

# days (0-indexed)
days = ( 'MONDAY', 'TUESDAY', 'WEDNESDAY', 'THURSDAY', 'FRIDAY', 'SATURDAY', 'SUNDAY' )

# months (1-indexed)
months = ( None,
  'JANUARY', 'FEBRUARY', 'MARCH', 'APRIL', 'MAY', 'JUNE', 'JULY',
  'AUGUST', 'SEPTEMBER', 'OCTOBER', 'NOVEMBER', 'DECEMBER'
)

# turn letters into numbers
letters = "?ABCDEFGHIJKLMNOPQRSTUVWXYZ"
l2n = lambda s: tuple(letters.index(x) for x in s)

year = 2018 # year
inc = datetime.timedelta(1) # 1 day increment

# consider days in the required year
d = datetime.date(year, 1, 1)
n = 0
bd = list()
while d.year == year:
  (day, date, month) = (l2n(days[d.weekday()]), d.day, l2n(months[d.month]))
  # find letters in both day and month
  s = set(day).intersection(month)
  if len(s) == 1 and date in s: # maybe just [[ date in s ]]
    n += 1
    printf("n={n}: {d} -> {wday} {date} {wmonth} -> {day} ({date}={wdate}) {month}", wday=days[d.weekday()], wdate=letters[date], wmonth=months[d.month])
    bd.append(d)
  d += inc

# number of birthdays
n = len(bd)

# find the maximum delta
deltas = list((b - a).days - 1 for (a, b) in tuples(bd, 2))
printf("{n} values, max delta = {m} days (deltas={deltas})", m=max(deltas))

      Solution: There are 4 friends. The longest gap between consecutive dates is 81 days.

      The 4 dates are:

      [1] SUNDAY 1 APRIL
      [2] THURSDAY 21 JUNE (gap = 80 days)
      [3] WEDNESDAY 25 JULY (gap = 33 days)
      [4] MONDAY 15 OCTOBER (gap = 81 days)

      The longest gap between these dates is 81 non-birthday days between [3] and [4].

      However, if we’re looking at “the maximum number of consecutive non-birthday days in 2018” there is a longer run from 1st January to 31st March, which is 90 days. (The run from 16th October to 31st December is 77 days).

      And the puzzle just asks for the longest gap between birthdays, and once we have fixed the dates we can see that the gap between birthday [4] and the next occurrence of birthday [1] (in 2019) is 167 days, and this gap would be 1 day longer if a leap year is involved. So the longest possible gap between birthdays is 168 days.

      Like

  • Unknown's avatar

    Jim Randell 9:07 am on 30 June 2019 Permalink | Reply
    Tags:   

    Brainteaser 1611: Scrambled egg 

    From The Sunday Times, 25th July 1993 [link]

    When HUMPTY fell he broke into six pieces, each comprising one letter from his name, and they landed in a row to read as a rubbish six-letter word with none of the six piece in the correct position.

    The King’s horses tried to put HUMPTY together again by arranging the pieces in the reverse order, which meant that more than one piece was in the right place.

    The King’s men then split that arrangement into two threes and placed the last three pieces before the first. This gave a higher number of letters in the correct place.

    What was the arrangement of letters just after HUMPTY fell?

    This puzzle is included in the book Brainteasers (2002). The wording above is taken from the book. It is slightly changed from the original puzzle.

    [teaser1611]

     
    • Jim Randell's avatar

      Jim Randell 9:07 am on 30 June 2019 Permalink | Reply

      This Python program tries all possible derangements of the letters, and checks to see if the conditions are satisfied. It runs in 85ms.

      Run: [ @repl.it ]

      from enigma import (subsets, join, printf)

# word with letters in their correct positions
word = "HUMPTY"

# count the number of correct letters
def correct(w):
  return sum(a == b for (a, b) in zip(w, word))

# find derangements of the word
for w in subsets(word, size=len(word), select='P'):
  if correct(w) > 0: continue

  # reversing gives more than 1 piece in the correct position
  w1 = w[::-1]
  k1 = correct(w1)
  if not (k1 > 1): continue

  # putting the last 3 before the first 3 gives even more in the correct position
  w2 = w1[3:] + w1[:3]
  k2 = correct(w2)
  if not (k2 > k1): continue

  # output solution
  printf("{w} [{w1} -> {k1}, {w2} -> {k2}]", w=join(w), w1=join(w1), w2=join(w2))

      Solution: The arrangement after HUMPTY fell was MTHYUP.

      Like

  • Unknown's avatar

    Jim Randell 5:48 pm on 28 June 2019 Permalink | Reply
    Tags:   

    Teaser 2962: Book receipts 

    From The Sunday Times, 30th June 2019 [link] [link]

    My wife recently purchased two books from her local bookshop. She showed me the receipt, which showed the cost of each book and the three-figure total cost. I noticed that all of the digits from 1 to 9 had been printed. Coincidentally, exactly the same happened to me when buying two different books, but my more expensive book cost more than hers. In fact, it would not have been possible for that book to have cost more.

    How much did I pay for the more expensive book?

    [teaser2962]

     
    • Jim Randell's avatar

      Jim Randell 5:57 pm on 28 June 2019 Permalink | Reply

      Assuming each digit from 1 to 9 is used exactly once, we can consider the following alphametic sum:

      ABC + DEF = GHI

      Which gives the prices of the books, and the total in whatever currency units we are using.

      This Python program uses a couple of useful routines from the enigma.py library to solve the puzzle.

      It runs in 163ms.

      Run: [ @replit ]

      from enigma import (SubstitutedExpression, Accumulator, irange, printf)

# the alphametic sum
p = SubstitutedExpression(
  [ "ABC + DEF = GHI", "A > D" ],  # "ABC > DEF"
  digits=irange(1, 9),
  answer="ABC",
  verbose=0
)

# find the maximum answer
r = Accumulator(fn=max, collect=1)
r.accumulate_data_from(p.solve(), value=1, data=0)

# output the solution
for s in r.data:
  t = p.substitute(s, "ABC + DEF = GHI")
  printf("max summand = {r.value} [{t}] [{n} sums]", n=r.count)

      Solution: The more expensive book cost 784 currency units.

      There are 168 possible sums, and the largest possible summand is 784, making the sum:

      784 + 152 = 936

      If the digit 0 is allowed (but we are still looking for 9 different digits) then there are 544 possible sums, and the largest possible summand is 847, in the sum:

      847 + 106 = 953

      Like

    • GeoffR's avatar

      GeoffR 12:11 pm on 3 March 2020 Permalink | Reply 

      from itertools import permutations

from collections import defaultdict
DI = defaultdict(list) 

for p in permutations('123456789'):
    A, B, C, D, E, F, G, H, I = p
    ABC = int(A + B + C)
    DEF =int(D + E + F)
    GHI = int(G + H + I)
    # ABC is most expensive book below
    if ABC > DEF and ABC + DEF == GHI:
        DI[ABC] += [(ABC, DEF, GHI)]
        
L = []  # List of most expensive books in equation

for K in DI.keys():
    L.append(K)

print(f"Most expensive book costs {max(L)} currency units")
# Most expensive book costs 784 currency units

      I also found that the summands 546 and 654 both had six solutions to the alphametic equation.

      Like

  • Unknown's avatar

    Jim Randell 11:54 am on 21 June 2019 Permalink | Reply
    Tags:   

    Teaser 2961: Alan and Cat 

    From The Sunday Times, 23rd June 2019 [link] [link]

    Alan and Cat live in a city which has a regular square grid of narrow roads. Avenues run west/east, with 1st Avenue being the furthest south, while Streets run south/north with 1st Street being the furthest west.

    Cat lives at the intersection of 1st Street and 1st Avenue, while Alan lives at an intersection due northeast from Cat. On 1 January 2018, Cat walked to Alan’s house using one of the shortest possible routes (returning home the same way), and has done the same every day since. At first, she walked a different route every day and deliberately never reached an intersection where the Street number is less then the Avenue number. However, one day earlier this year she found that she could not do the same, and repeated a route.

    What was the date then?

    [teaser2961]

     
    • Jim Randell's avatar

      Jim Randell 12:20 pm on 21 June 2019 Permalink | Reply

      We have encountered problems similar to this before, see: Enigma 1108.

      The puzzle can be solved using Catalan’s Triangle [ link ], hence the names Cat and Alan.

      This Python program counts the paths constructively. It runs in 95ms.

      Run: [ @repl.it ]

      import datetime
from enigma import (irange, inf, cached, printf)

# count paths from (0, 0) to (x, y) where x =< y
@cached
def paths(x, y):
  if x == 0: return 1
  n = paths(x - 1, y)
  if x < y: n += paths(x, y - 1)
  return n

for n in irange(1, inf):
  p = paths(n, n)
  printf("[{n} -> {p} paths]")
  if p < 365: continue
  if p > 538: break
  d = datetime.date(2018, 1, 1) + datetime.timedelta(p)
  printf("first repeat on date = {d}")

      Solution: The date of the first repeat was 6th March 2019.

      Instead of counting the paths we can use the formula for Catalan numbers:

      import datetime
from enigma import (C, irange, inf, printf)

# generalised Catalan numbers
def catalan(n, k, m=1):
  if k > n + m - 1:
    return 0
  elif 0 <= k < m:
    return C(n + k, n)
  else:
    return C(n + k, k) - C(n + k, k - m)

for n in irange(1, inf):
  p = catalan(n, n)
  printf("[{n} -> {p} paths]")
  if p < 365: continue
  if p > 538: break
  d = datetime.date(2018, 1, 1) + datetime.timedelta(p)
  printf("first repeat on date = {d}")

      Like

  • Unknown's avatar

    Jim Randell 12:37 pm on 17 June 2019 Permalink | Reply
    Tags:   

    Teaser 2903: What’s my card? 

    From The Sunday Times, 13th May 2018 [link] [link]

    Four expert logicians play a game with a pack of six cards, numbered from 1 to 6. The cards are shuffled and each draws a card, holding it in front of him so that he cannot see his own number but can see the numbers held by the others. The winner is the player who can first deduce what number he is holding.

    Each player in turn is asked to announce the sum of two numbers that he can see on the other cards. One game started with Alf announcing 6. After a long pause, no-one claimed victory, so Bert then announced 5. There was a significant pause, but before Charlie spoke, someone claimed victory.

    Which cards did Alf and Bert hold, and which cards remained on the table?

    [teaser2903]

     
    • Jim Randell's avatar

      Jim Randell 12:38 pm on 17 June 2019 Permalink | Reply

      I took the “long pause” to mean that no-one can immediately declare victory, and each player can take the fact that no-one can immediately declare victory into account. And even with this additional information no-one can declare victory, and this too can be taken into account, and so on until the process provides no further information to any of the players.

      I took the “significant pause” to mean that no-one can immediately declare victory, and each player can take this fact into account.

      This Python program starts by consider all possible P(6, 4) = 360 ways the cards can be dealt, and then reduces the possibilities as each piece of new information is taken into account.

      It runs in 84ms.

      from enigma import (unpack, subsets, filter_unique, intersect, irange, printf)

# cards for A, B, C, D
cA = unpack(lambda A, B, C, D: A)
cB = unpack(lambda A, B, C, D: B)
cC = unpack(lambda A, B, C, D: C)
cD = unpack(lambda A, B, C, D: D)

# what A, B, C, D can see
sA = unpack(lambda A, B, C, D: (B, C, D))
sB = unpack(lambda A, B, C, D: (A, C, D))
sC = unpack(lambda A, B, C, D: (A, B, D))
sD = unpack(lambda A, B, C, D: (A, B, C))

# cards
cards = set(irange(1, 6))

# start with all possible arrangements of cards for (A, B, C, D)
r = set(subsets(cards, size=4, select="P"))
printf("[{n} possibilities]", n=len(r))

# A declares 6, which the value of B+C, B+D or C+D
r = set((A, B, C, D) for (A, B, C, D) in r if 6 in (B + C, B + D, C + D))
printf("[{n} possibilities]", n=len(r))

# no-one claims immediate victory
def unclaimed(r):
  rA = filter_unique(r, sA, cA).non_unique
  rB = filter_unique(r, sB, cB).non_unique
  rC = filter_unique(r, sC, cC).non_unique
  rD = filter_unique(r, sD, cD).non_unique
  return intersect([rA, rB, rC, rD])

# apply filter until the results remain unchanged (according to ==)
def repeat(fn, x):
  while True:
    x0 = x
    x = fn(x0)
    if x == x0: return x0

# there is a long pause
# so repeat unclaimed() until there is nothing further eliminated
r = repeat(unclaimed, r)
printf("[{n} possibilities]", n=len(r))

# B declares 5, which is the value of A+C, A+D, C+D
r = set((A, B, C, D) for (A, B, C, D) in r if 5 in (A + C, A + D, C + D))
printf("[{n} possibilities]", n=len(r))

# at this point no-one claims immediate victory
r = unclaimed(r)
printf("[{n} possibilities]", n=len(r))

# so what possibilities are left?
printf("remaining = {r}")


# output possible declarations
dA = filter_unique(r, sA, cA).unique
dB = filter_unique(r, sB, cB).unique
dC = filter_unique(r, sC, cC).unique
dD = filter_unique(r, sD, cD).unique

for s in r:
  (A, B, C, D) = s
  printf("\nA={A} B={B} C={C} D={D}, table={t}:", t=cards.difference(s))
  if s in dA: printf("  A declares {A}")
  if s in dB: printf("  B declares {B}")
  if s in dC: printf("  C declares {C}")
  if s in dD: printf("  D declares {D}")

      Solution: Alf has 3. Bert has 5. The cards remaining on the table are 2 and 6.

      Starting from 360 possibilities the possible hands are reduced as follows:

      Initially, 360 possibilities.
      “A declares 6”, 144 possibilities.
      “there is a long pause”, 48 possibilities.
      “B declares 5”, 20 possibilities.
      “no-one claims immediate victory”, 2 possibilities.

      The two remaining possibilities are (A=3, B=5, C=1, D=4) and (A=3, B=5, C=4, D=1). We don’t know from the information given which order C and D are holding 1 and 4, but each player can see at least one of the cards, so they would know the exact hand dealt, and presumably all four of them would declare victory simultaneously.

      Here is my manual solution:

      A says “6”, so can see 1+5 or 2+4 (3 and 6 cannot participate in any pair that sum to 6)

      If A is holding one of these cards (1, 2, 4, 5) they must be seeing the sum that doesn’t involve their own card. B, C, D can see which card A is holding, so would know which of the sums A is seeing, and so the people who can only see one half of that sum would immediately be able to declare their number (as the other half of that sum). This doesn’t happen.

      Hence A must be holding 3 or 6. And the other card (6 or 3) must still be on the table, as if one of B, C, D were holding it the other two could deduce their cards immediately.

      So B, C, D are holding three cards from 1, 2, 4, 5.

      B says “5”, so can see 1+4 or 2+3.

      If A is holding 6, then 3 is still on the table, so B can see 1+4 from C and D. C and/or D can immediately declare their cards as soon as B says “5”. This doesn’t happen.

      So A can deduce he is holding 3 (and can declare victory, after the pause where neither C nor D declare victory).

      B must be able to see 1+4 (from C and D) or 2+3 (from A’s 3 and one of C and D holds the 2).

      If B is holding 1 or 4, then he must be able to see 2+3, so whichever of C and D cannot see the 2 must be holding it and can declare immediately. This doesn’t happen.

      Similarly if B is holding 2, then he must be able to see 1+4 from C and D, so C and D can declare their cards immediately. This doesn’t happen.

      So B can deduce he is holding 5 (and can declare, after the pause where neither C nor D declare victory).

      This leaves C and D holding two cards from 1, 2, 4, and the other is still on the table (along with 6).

      If C and D are holding 1 and 2, then when B says “5” A would immediately know his card was 3 (which goes with the 2 to make 5). This doesn’t happen.

      If C and D are holding 2 and 4, then when B says “5” A would immediately know his card was 3 (which goes with the 2 to make 5). This doesn’t happen.

      So C and D are holding 1 and 4, and can declare (after the pause where A does not declare victory). 2 and 6 remain on the table.

      Like

    • John Crabtree's avatar

      John Crabtree 3:00 pm on 21 June 2019 Permalink | Reply

      Let a declared value be D.
      If the non-declarers have cards >= D or = D/2, two players can immediately determine their cards.
      If two pairs of cards add to D, two players can immediately determine their cards.

      After A’s call, only A can have and as 1 + 5 = 2 + 4 = 6 must have, 3 or 6
      After B’s call, A must have 3 and, as 1 + 4 = 2 + 3 = 5, B must have 5.
      After B’s call, A knows immediately that he has 3 unless he can see C + D = 5 = 1 + 4.
      The cards on the table are 2 and 6.

      Like

  • Unknown's avatar

    Jim Randell 11:16 pm on 14 June 2019 Permalink | Reply
    Tags:   

    Teaser 2960: Bags of sweets! 

    From The Sunday Times, 16th June 2019 [link] [link]

    I recently bought a number of equally priced bags of sweets for a bargain price, spending more than 50p in total. If they had been priced at 9p less per bag, I could have had 2 bags more for the same sum of money. In addition, if each had cost 12p less than I paid, then I could also have had an exact number of bags for the same sum of money.

    How much did I spend in total on the sweets?

    [teaser2960]

     
    • Jim Randell's avatar

      Jim Randell 11:47 pm on 14 June 2019 Permalink | Reply

      If we buy n bags of sweets at x pence per bag, then the total outlay n.x can be expressed as:

      n.x = (n + 2)(x − 9)
      n.x = k(x − 12)
      n.x > 50

      (for some whole number k, where n > 1).

      From which we see:

      x = (18 + 9n) / 2

      This Python program finds the first value of n that satisfies the conditions and gives an integer value for k.

      Run: [ @repl.it ]

      from enigma import (Rational, irange, inf, div, printf)

Q = Rational()

# consider n the number of bags of sweets bought
for n in irange(1, inf):
  x = Q(18 + 9 * n, 2)
  t = n * x
  if not (t > 50): continue

  # find the number of bags if the prices were 12p less
  k = div(t, x - 12)
  if k is None: continue

  printf("{t}p = {n} bags @ {x}p [= {n2} bags @ {x9}p = {k} bags @ {x12}p]", n2=n+2, x9=x-9, x12=x-12)
  break

      Solution: The total spend was 216p.

      With a bit more analysis we can show this is the only solution.

      We can write an expression for k as:

      k = 9n(n + 2) / (9n − 6) = n + 8/3 + 16 / (9n − 6)

      And this only gives a whole number when 16 / (9n − 6) has a fractional part of 1/3.

      This is only possible for n = 1, 2, 6.

      n = 1 gives x = 13.5p, n.x = 13.5p, which is not more than 50p (and we want n > 1 anyway).

      n = 2 gives x = 18p, n.x = 36p, which is not more than 50p.

      n = 6 gives x = 36p, n.x = 216p, so this is the solution.

      Here is a program that uses this analysis to consider all possible solutions, by looking at the divisors of 48:

      from enigma import (Rational, divisors, div, printf)

Q = Rational()

# consider divisors of 48
for d in divisors(48):
  # we only want divisors of the form (3z + 1)
  if not (d % 3 == 1): continue
  # compute n
  n = div(48 // d + 6, 9)
  if n is None: continue
  # compute x and t
  x = Q(18 + 9 * n, 2)
  t = n * x
  if not (t > 50): continue
  # compute k
  k = div(9 * n * (n + 2), 9 * n - 6)
  # output solution
  printf("[d={d}] n={n} x={x} t={t} k={k}")

      Removing the check at line 15 will give all three solutions for the equations.

      Like

    • GeoffR's avatar

      GeoffR 6:49 pm on 16 June 2019 Permalink | Reply

      We can put Jim’s initial three equations into a MinZinc constraint for an easy solution

      % A Solution in MiniZinc
include "globals.mzn";
 
var 1..50: n;   % no of bags bought originally
var 1..50: k;   % no bags bought at 12p less
var 1..100: x;  % original cost per bag (pence)

constraint n * x > 50 /\ n * x == (n + 2) * (x - 9) 
/\ n * x = k * (x - 12);

solve satisfy;
output ["Total spent on sweets = " ++ show(n * x) ++ " pence" ];

      Like

      • Jim Randell's avatar

        Jim Randell 8:46 am on 17 June 2019 Permalink | Reply

        @GeoffR: This approach works OK for cases where the price per bag is a whole number (which is the case in the actual solution).

        I didn’t assume that and found there were 3 candidate solutions that satisfied the 2 equations, one of which has the bags priced with a fractional amount. Two of the candidates are eliminated by the inequality (including the one where the bags are priced a fractional amount), leaving a single solution.

        Like

    • GeoffR's avatar

      GeoffR 3:12 pm on 17 June 2019 Permalink | Reply

      @Jim: I can see you are making a mathematical point about prices for fractional amounts, but is this applicable for this teaser ?

      We don’t have fractional pennies these days in our monetary system, so maybe we should assume that prices per bag are in whole numbers of pennies ?

      Like

      • Jim Randell's avatar

        Jim Randell 4:56 pm on 18 June 2019 Permalink | Reply

        @GeoffR: It was just a comment to try and extract a bit more interest from a relatively straightforward puzzle.

        I try not to make additional assumptions about the puzzle if I can help it. From the formula for x we see that the price per pack is a whole number of half-pennies, so it seemed reasonable to allow this. And we do get an extra potential solution if we do. Although this solution is then removed by the “more than 50p” requirement, so it doesn’t really matter if we consider it or not.

        Like

  • Unknown's avatar

    Jim Randell 12:41 pm on 13 June 2019 Permalink | Reply
    Tags: by: Simon Porter   

    Brainteaser 1610: Word game 

    From The Sunday Times, 18th July 1993 [link]

    An unusual card game consisted of 12 cards each with a different well-known word of four letters on it. No letter appeared on more than three cards and no two cards had more than one letter in common. The winner was the first person to collect among his or her cards a set of three cards with the same letter on each.

    In one game against George I started and after two goes I had chosen:

    ZEST
    CHEW

    while George had picked up:

    DAWN
    RILE

    (the second to stop me getting a set of three with a common “E“).

    For my third I chose:

    QUAY

    and after George had selected his third card he told me that whatever card I now chose he would certainly win on this next turn.

    I picked up:

    SHIN

    for my fourth card and, as predicted, George chose:

    FLOW

    giving him a winning set.

    The unused cards were:

    CURT
    JUGS
    MOTH
    PARK

    what was George’s third card?

    This puzzle is included in the book Brainteasers (2002). The wording above is taken from the book. It is slightly changed from the original puzzle.

    [teaser1610]

     
    • Jim Randell's avatar

      Jim Randell 12:42 pm on 13 June 2019 Permalink | Reply

      This Python program extracts candidate 4-letters words from the supplied word list, selects those that are permissible according to the given rules, and then looks at each one as a possible third card for George.

      It runs in 391ms, although the run time will depend on the word list used. I used the [[ sowpods.txt ]] word list from Enigma 1195 and Enigma 288a.

      Run: [ @replit ]

      from enigma import (union, printf)

# the known cards
player1 = [ 'ZEST', 'CHEW', 'QUAY' ]
player2 = [ 'DAWN', 'RILE' ] # and a mystery card
remaining = [ 'SHIN', 'FLOW', 'CURT', 'JUGS', 'MOTH', 'PARK' ]
cards = player1 + player2 + remaining

# "no letter appears on more than three cards"
# so any letter that appears on three of the known cards cannot appear
# on the missing card
inv = set(x for x in union(cards) if sum(x in c for c in cards) > 2)

# look for 4 letter words in the word list
path = "sowpods.txt"
words = list()
for w in open(path).readlines():
  w = w.strip().upper()
  if len(w) == 4:
    # discard words containing letters already on 3 cards
    if inv.intersection(w): continue
    # discard words with more than one letter in common with a known card
    s = set(w)
    if any(len(s.intersection(c)) > 1 for c in cards): continue
    words.append(w)
printf("[{n} candidate words found]", n=len(words))

# find winning cards from rs for hand hs
def win(hs, rs):
  # pick up a card
  for w in rs:
    # have we won?
    # i.e. are there two cards in the hand containing a letter on the card?
    for x in set(w):
      if sum(x in h for h in hs) > 1:
        yield w

# consider each candidate word as a possible mystery card
for w in words:
  # George must be able to win in (at least) 2 ways, one of them using FLOW
  ss = list(win(player2 + [w], remaining))
  if len(ss) > 1 and 'FLOW' in ss:
    printf("{w} -> {ss}", ss=sorted(ss))

      Solution: George’s third card was LYNX.

      George is holding:

      DAWN
      RILE
      LYNX

      There are two cards with L and two cards with N.

      Picking FLOW will give a set of 3 cards with L, and picking SHIN will give a set of 3 cards with N.

      Like

  • Unknown's avatar

    Jim Randell 2:15 pm on 12 June 2019 Permalink | Reply
    Tags:   

    Teaser 2904: Catching another bus 

    From The Sunday Times, 20th May 2018 [link] [link]

    I want to catch a bus into town, and I arrive at the bus stop at a random time.

    The number 12 bus runs every 12 minutes, the number 15 bus runs every 15 minutes and the number 20 bus runs every 20 minutes.

    All the buses leave the bus stop at an exact number of minutes past the hour and no two buses leave at the same time. Interestingly, given the above information, the probability that I catch a number 12 bus is as small as it possibly could be.

    What is the probability that I catch a number 12 bus?

    [teaser2904]

     
    • Jim Randell's avatar

      Jim Randell 2:16 pm on 12 June 2019 Permalink | Reply

      The period between each type of bus exactly divides 60, so in any hour period the pattern of buses is the same as the previous hour.

      So if we make a timetable of the buses, as no buses arrive at the same time, the periods in between buses arriving is spent waiting for the next bus, so by examining the gaps between buses we can determine the proportions of the hour spent waiting for each type of bus.

      This Python program runs in 76ms.

      Run: [ @repl.it ]

      from enigma import (irange, update, tuples, Accumulator, unpack, fraction, printf)

# period we are interested in (60 minutes)
T = 60

# generate timetables for a bus leaving at intervals of <t>
# that doesn't coincide with the times in <d>
# yield: (<t0>, <d1>), where:
# t0 = earliest time for the bus
# d1 = updated cumulative timetable
def generate(t, d):
  for t0 in irange(0, t - 1):
    ks = list(irange(t0, T - 1, step=t))
    if any(k in d for k in ks): continue
    yield (t0, update(d, ((k, t) for k in ks)))

# find minimum wait for #12 bus
r = Accumulator(fn=min)

# suppose the #20 bus leaves at t=0
t20 = 0
ts1 = dict((t, 20) for t in irange(t20, T - 1, step=20))

# consider the time the first #15 bus leaves
for (t15, ts2) in generate(15, ts1):

  # consider the time the first #12 bus leaves
  for (t12, ts3) in generate(12, ts2):

    # make the timeline
    ts = sorted(ts3.items(), key=unpack(lambda t, n: t))
    (t, n) = ts[0]
    ts.append((t + T, n))

    # count the total waits for each type of bus
    w = { 12: 0, 15: 0, 20: 0 }
    for ((t1, _), (t2, n)) in tuples(ts, 2):
      w[n] += t2 - t1
    r.accumulate_data(w[12], (t12, t15, t20))

# output minimal solution
(a, b) = fraction(r.value, T)
printf("min P(12) = {a}/{b} [{r.data}]")

      Solution: The probability of catching a number 12 bus is 7/20.

      If we start the hour when a #20 bus is at the stop, then the #20 buses arrive at: +0, +20, +40, +60.

      The first #12 bus arrives at +5 minutes, so has a timetable of: +5, +17, +29, +41, +53.

      The first #15 bus arrives at +13 minutes, so has a timetable of: +13, +28, +43, +58.

      So the timetable looks like this:

      +00: #20 bus
      (5 minute wait for #12 bus)
      +05: #12 bus
      (8 minute wait for #15 bus)
      +13: #15 bus
      (4 minute wait for #12 bus)
      +17: #12 bus
      (3 minute wait for #20 bus)
      +20: #20 bus
      (8 minute wait for #15 bus)
      +28: #15 bus
      (1 minute wait for #12 bus)
      +29: #12 bus
      (11 minute wait for #20 bus)
      +40: #20 bus
      (1 minute wait for #12 bus)
      +41: #12 bus
      (2 minute wait for #15 bus)
      +43: #15 bus
      (10 minute wait for #12 bus)
      +53: #12 bus
      (5 minute wait for #15 bus)
      +58: #15 bus
      (2 minute wait for #20 bus)
      +60: #20 bus

      Adding the waiting times for each type of bus we get:

      21 minutes for #12 bus
      23 minutes for #15 bus
      16 minutes for #20 bus

      So if we arrive at a random time during the hour the probability the next bus is #12 is 21/60 = 7/20.

      Like

  • Unknown's avatar

    Jim Randell 9:15 am on 11 June 2019 Permalink | Reply
    Tags:   

    Brain-Teaser 483: Absentees 

    From The Sunday Times, 30th August 1970 [link]

    Only seven men still had ammunition. Aden had 1 round, Bill 2 rounds, Cuff 3, Dudd 4, Edge 5, Ford 6 and Good 7. The commander ordered there should always be five of the seven men on duty and that the duty roster should be so arranged that those on duty never had fewer than 17 rounds of ammunition.

    Next day he was told that only four men were on duty. It appeared that three of the five who should have been present were sick and that the four doing duty included two who should have been off. It so happened that the four had between them the same number of rounds as the five would have had.

    The commander had no copy of the duty roster, but he knew how many rounds each of the seven men had.

    He asked how many rounds the four men doing duty had between them. When given the figure the commander said, after some thought, that he could say with certainty who the three absentees were.

    Can you name them?

    This puzzle is included in the book Sunday Times Brain Teasers (1974).

    [teaser483]

     
    • Jim Randell's avatar

      Jim Randell 9:16 am on 11 June 2019 Permalink | Reply

      We can identify the men by the number of rounds each man has.

      Three men are sick, and two provide cover. The remaining two were scheduled to be on duty and actually were on duty.

      This Python program runs in 81ms.

      Run: [ @repl.it ]

      from enigma import (irange, subsets, diff, filter_unique, unpack, printf)

# the numbers of rounds available
rounds = list(irange(1, 7))

# generate possible (<number of rounds>, <sick>, <cover>)
def generate():
  T = sum(rounds)

  # consider the 3 sick men
  for sick in subsets(rounds, size=3):
    # the number of rounds amongst the sick men is...
    n = sum(sick)
    # and so the total number of rounds on duty is...
    t = T - n
    if (t < 17): continue
    # find 2 men to cover with the same number of rounds
    for cover in subsets(diff(rounds, sick), size=2):
      if not (sum(cover) == n): continue
      yield (t, sick, cover)

# find solutions where...
(ss, _) = filter_unique(
  generate(),
  # ... if I knew the total number of rounds ...
  unpack(lambda t, s, c: t),
  # ... I could deduce who was sick
  unpack(lambda t, s, c: s),
)

# output solutions
for (t, s, c) in ss:
  printf("{t} rounds -> sick = {s}, cover = {c}")

      Solution: The three absentees are Aden, Cuff and Dudd.

      A, C, D have 1+3+4 = 8 rounds between them, and are covered by B and F, who also have 2+6 = 8 rounds between them.

      The remaining 2 men, E and G, with 5 + 7 = 12 rounds between them were scheduled to be on duty and were not sick.

      So altogether there were 8 + 12 = 20 rounds on duty.

      Like

  • Unknown's avatar

    Jim Randell 7:08 pm on 7 June 2019 Permalink | Reply
    Tags:   

    Teaser 2959: The Magnificent Seven 

    From The Sunday Times, 9th June 2019 [link] [link]

    After a day’s filming, a group of those involved in the film’s production went for a gallop.

    They split into threes, with a samurai leading each grouping.

    The seven samurai were:

    BRONSON, BRYNNER, BUCHHOLZ, COBURN, DEXTER, MCQUEEN and VAUGHN.

    The others involved in the gallop were:

    ALANIZ, ALONZO, AVERY, BISSELL, BRAVO, DE HOYOS, HERN, LUCERO, NAVARRO, RUSKIN, RUSSELL, SUAREZ, VACIO and WALLACH.

    For each grouping, any two names from the three had exactly 2 letters in common (e.g., BRYNNER and BRAVO have B and R in common).

    If I told you who accompanied BRONSON, you should be able to tell me who accompanied (a) MCQUEEN and (b) DEXTER.

    [teaser2959]

     
    • Jim Randell's avatar

      Jim Randell 11:16 pm on 7 June 2019 Permalink | Reply

      This Python program runs in 116ms.

      Run: [ @repl.it ]

      from enigma import (grouping, subsets, diff, unpack, filter_unique, printf)

# the "others"
others = (
  'ALANIZ', 'ALONZO', 'AVERY', 'BISSELL', 'BRAVO', 'DE HOYOS', 'HERN',
  'LUCERO', 'NAVARRO', 'RUSKIN', 'RUSSELL', 'SUAREZ', 'VACIO', 'WALLACH'
)

# selection function
fn = grouping.share_letters(2)

# find a gang for leader x, with remaining members chosen from ys
def gang(x, ys):
  for (y, z) in subsets((y for y in ys if fn(x, y)), size=2):
    if fn(y, z):
      yield (y, z)

# find multiple gangs, with leaders from x, followers from ys
def gangs(xs, ys, gs=[]):
  # are we done?
  if not xs:
    yield gs
  else:
    # find a gang for the first leader
    for g in gang(xs[0], ys):
      # and solve for the rest
      yield from gangs(xs[1:], diff(ys, g), gs + [g])

# record possible values for (g1, g2, g3)
vs = list()

# find possible 2-gangs led by BRONSON, DEXTER, MCQUEEN
for gs in gangs(["BRONSON", "DEXTER", "MCQUEEN"], others):
  # check the remaining 2-gangs can be made with the remaining followers
  for _ in gangs(["BRYNNER", "BUCHHOLZ", "COBURN", "VAUGHN"], diff(others, *gs)):
    vs.append(gs)
    # we only need one example
    break

# "if I told you who accompanied BRONSON ..."
f = unpack(lambda B, D, M: B)
# "... you could tell me who accompanied MCQUEEN and DEXTER"
g = unpack(lambda B, D, M: (M, D))
(ss, _) = filter_unique(vs, f, g)

# output solutions
for (B, D, M) in ss:
  printf("BRONSON + {B} -> DEXTER + {D}, MCQUEEN + {M}")

      Solution: (a) MCQUEEN was accompanied by HERN and RUSSELL. (b) DEXTER was accompanied by AVERY and DE HOYOS.

      There are only three possible ways that complete groupings can be made:

      BRONSON = BISSELL, DE HOYOS
      DEXTER = AVERY, LUCERO
      MCQUEEN = HERN, RUSSELL
      BRYNNER = NAVARRO, RUSKIN
      BUCHHOLZ = BRAVO, SUAREZ
      COBURN = ALONZO, VACIO
      VAUGHN = ALANIZ, WALLACH

      BRONSON = BISSELL, DE HOYOS
      DEXTER = AVERY, RUSSELL
      MCQUEEN = HERN, RUSKIN
      BRYNNER = LUCERO, NAVARRO
      BUCHHOLZ = BRAVO, SUAREZ
      COBURN = ALONZO, VACIO
      VAUGHN = ALANIZ, WALLACH

      BRONSON = BISSELL, LUCERO
      DEXTER = AVERY, DE HOYOS
      MCQUEEN = HERN, RUSSELL
      BRYNNER = NAVARRO, RUSKIN
      BUCHHOLZ = BRAVO SUAREZ
      COBURN = ALONZO, VACIO
      VAUGHN = ALANIZ, WALLACH

      Telling us the parters of BRONSON uniquely identifies the solution, so it must the last of these groupings.

      Like

  • Unknown's avatar

    Jim Randell 11:04 am on 7 June 2019 Permalink | Reply
    Tags:   

    Teaser 2906: In proportion 

    From The Sunday Times, 3rd June 2018 [link] [link]

    In 2000 the Sultan of Proportion told his five sons they would inherit his fortune in amounts proportionate to their ages at his death.

    Accordingly, they each recently received a different whole number of tesares. Strangely, if he had lived a few more hours the five ages would have been consecutive and each son would again have received a whole number of tesares. Such a delay would have benefited just one son (by 1000 tesares).

    How many tesares were distributed in total?

    [teaser2906]

     
    • Jim Randell's avatar

      Jim Randell 11:06 am on 7 June 2019 Permalink | Reply

      Assuming ages are expressed as a whole number of years.

      In the actual situation the five ages are all different, and in the hypothetical situation (which is a few hours later) the ages are consecutive, lets say:

      a + 1, a + 2, a + 3, a + 4, a + 5

      The proportion going to each son would be:

      (a + 1) / (5a + 15)
      (a + 2) / (5a + 15)
      (a + 3) / (5a + 15)
      (a + 4) / (5a + 15)
      (a + 5) / (5a + 15)

      In the actual case one of the sons is one year younger, and as the ages are all different it can only be the youngest son, so that actual ages are:

      a, a + 2, a + 3, a + 4, a + 5

      and the actual proportions are:

      a / (5a + 14)
      (a + 2) / (5a + 14)
      (a + 3) / (5a + 14)
      (a + 4) / (5a + 14)
      (a + 5) / (5a + 14)

      So the youngest son is better off by 1000 tesares in the hypothetical situation, so if the total number of tesares to be distributed is T, we have:

      T (a + 1) / (5a + 15) = T a / (5a + 14) + 1000
      T = 1000 / [(a + 1) / (5a + 15) – a / (5a + 14)]
      T = 1000 (5a + 14) (5a + 15) / (4a + 14)

      As the 5 sons were around in 2000 and the puzzle was set in 2018, we can suppose that each son is older than 18 (otherwise we can find a second solution).

      This Python program runs in 68ms.

      Run: [ @repl.it ]

      from enigma import (irange, div, printf)

# splits for the specified ages (must all be integers)
def split(T, ages):
  t = sum(ages)
  return list(div(T * x, t) for x in ages)

# consider possible youngest ages (there is a further solution at a=9)
for a in irange(18, 100):

  # the youngest son is 1000 better off in the hypothetical case
  # compute the total value to be distributed
  z = 5 * a + 14
  T = div(1000 * z * (z + 1), z - a)
  if T is None: continue

  # hypothetical ages (consecutive)
  h_ages = list(irange(a + 1, a + 5))
  h_splits = split(T, h_ages)
  if None in h_splits: continue

  # actual ages (the youngest is one year younger)
  ages = [a] + h_ages[1:]
  splits = split(T, ages)
  if None in splits: continue

  # all the rest (other than the youngest) lost out
  diffs = tuple(y - x for (x, y) in zip(splits, h_splits))
    
  printf("T={T}")
  printf("actual: ages={ages}, splits={splits}")
  printf("hypoth: ages={h_ages}, splits={h_splits}, diff={diffs}")
  printf()

      Solution: In total 383,160 tesares were distributed.

      The actual ages of the sons at the time of the Sultan’s death were: 59, 61, 62, 63, 64. The youngest son turning 60 shortly after.

      If we allow ages less than 18 then there is a further solution where the actual ages of the sons are: 9, 11, 12, 13, 14, and 70,800 tesares are distributed amongst them.

      Like

  • Unknown's avatar

    Jim Randell 1:07 pm on 6 June 2019 Permalink | Reply
    Tags:   

    Brain-Teaser 482: [Alphabetical cricket] 

    From The Sunday Times, 23rd August 1970 [link]

    The Alphabet CC ended last season with a fine win against the Early Closers XI. Declaring at 155 for six they dismissed their opponents with only minutes to spare. The Early Closers’ captain, Bond, made a spirited 71 not out.

    “Nice gesture of the opposition to bat in alphabetical order”, said C. F. Arrowroot, the Alphabet president; “And did you notice that each one of the first three wickets fell when the total was the product of Bond’s score and that of the outgoing batsman?”

    “Even odder”, commented B. P. Biggin, “except when Collins was out the total at the fall of every one of their wickets was the square of the dismissed batsman’s score.”

    No one made a “duck” and there was just one “extra”. I should perhaps add that no two Early Closers had the same surname initial.

    How many did Collins score, and what was Bond’s score at the fall of the seventh wicket?

    This puzzle was originally published with no title.

    [teaser482]

     
    • Jim Randell's avatar

      Jim Randell 1:09 pm on 6 June 2019 Permalink | Reply

      Although not explicitly mentioned in the puzzle text, presumably we are talking about a cricket match.

      B is one of the first pair to go into bat, and at the 10th dismissal he is “not out”, so he is paired with every other batsman. If there is an A, he would be in the first pair (and the first to be dismissed), and C would be next (and be the second to be dismissed). If there isn’t an A, C would be in the first pair and be the first to be dismissed. So C is either the first or second batsman to be dismissed.

      I tackled this problem in 2 parts. The first part deals with the first three dismissals, where the score is always the product of B’s score and the dismissed batsman’s score (and two of the scores have to be the square of the dismissed batsman’s score – the one that isn’t identifies C).

      The second part deals with the remaining dismissals (4th – 10th) the scores have to be the square of the dismissed batsman’s score.

      When the 10th batsman is dismissed the total score must be a square less than 155, so not more than 12².

      This program runs in 80ms.

      Run: [ @repl.it ]

      from enigma import (irange, div, printf)

# solve the first three dismissals, at each the total score is the
# product of B's score and the dismissed batsman's score and all,
# except C, the total is the square of the dismissed batsman's score.
# return ([(<B's score>, <dismissed score>, <extras>), ...], <C>)
# t = total so far
# b = B's current score
# ds = scores at dismissals
# x = current extras
# c = identify C
def solve1(t=0, b=0, ds=[], x=0, c=None):
  n = len(ds)
  # are we done?
  if n == 3:
    # check C has been allocated
    if c in (0, 1):
      yield (ds, c)
  else:
    # possible extra
    for x2 in irange(x, 1):
      # possible current score for B
      for b2 in irange(b, 71):
        # calculate the score for the dismissed batsman (d)
        #   t2 = t + (b2 - b) + d + (x2 - x) = b2 * d
        # so:
        #   d = (t + b2 + x2 - b - x) / (b2 - 1)
        d = div(t + b2 + x2 - b - x, b2 - 1)
        if d is None or d < 1: continue
        t2 = b2 * d
        # is the total the square of d?
        c2 = c
        if t2 != d * d:
          # this must be C
          if c is not None: continue
          c2 = n
        yield from solve1(t2, b2, ds + [(b2, d, x2)], x2, c2)

# solve the remaining dismissals, at each the total score is the
# square of the dismissed batman's score
# t = total score so far
# b = B's current score
# ds = scores of B and dismissed batsman
# x = extra (0 or 1)
def solve2(t=0, b=0, ds=[], x=0):
  n = len(ds)
  # are we done?
  if n == 10:
    # check an extra has been scored and B's score is 71
    if x == 1 and ds[-1][0] == 71:
      yield ds
  else:
    # possible extra
    for x2 in irange(x, 1):
      # possible scores for next batsman
      for d in irange(1, 12):
        # the new total is...
        t2 = d * d
        if not (t < t2 < 155): continue
        # calculate the current score for B
        b2 = t2 + b + x - t - d - x2
        if b2 < b: continue
        yield from solve2(t2, b2, ds + [(b2, d, x2)], x2)
          
# solve for the first 3 dismissals
for (ds1, c) in solve1():
  (b, d, x) = ds1[-1]
  # solve for the remaining dismissals
  for ds in solve2(b * d, b, ds1, x):
    # output the solution
    printf("[ds={ds}]")
    printf("-> C={C} [i={c}]; B[i=6]={B}", C=ds[c][1], B=ds[6][0])

      Solution: Collins scored 5. Bond had scored 41 at the 7th dismissal.

      The scores for the batsman (in dismissal order) were:

      2, 5 (Collins), 4, 5, 6, 8, 9, 10, 11, 12, 71 (not out, Bond)

      And the total scores at each dismissal were:

      4, 10 (Collins), 16, 25, 36, 64, 81, 100, 121, 144

      So there is an A (who was dismissed first). The extra was scored between A’s dismissal and C’s dismissal.

      Bond’s scores at each dismissal were:

      2, 2, 4, 8, 13, 33, 41, 50, 60, 71

      Like

  • Unknown's avatar

    Jim Randell 2:14 pm on 3 June 2019 Permalink | Reply
    Tags:   

    Teaser 2908: Number challenge 

    From The Sunday Times, 17th June 2018 [link] [link]

    I challenged Charlotte and Oliver to find a 9-digit number, using nine different digits, so that:

    • The number given by the 1st and 2nd digits was divisible by 2.
    • The number given by the 2nd and 3rd digits was divisible by 3.
    • …

    And so on until:

    • The number given by the 8th and 9th digits was divisible by 9.

    They each produced a different, correct solution.

    Charlotte claimed hers was the better solution since in her number, the number formed by the first seven digits was also divisible by 7, Charlotte’s age.

    What was Charlotte’s number?

    [teaser2908]

     
    • Jim Randell's avatar

      Jim Randell 2:15 pm on 3 June 2019 Permalink | Reply

      We can solve this puzzle using the [[ SubstitutedExpression() ]] solver from the enigma.py library.

      This run file executes in 124ms.

      Run: [ @repl.it ]

      #! python -m enigma -rr

SubstitutedExpression

--answer="ABCDEFGHI"

"AB % 2 = 0"
"BC % 3 = 0"
"CD % 4 = 0"
"DE % 5 = 0"
"EF % 6 = 0"
"FG % 7 = 0"
"GH % 8 = 0"
"HI % 9 = 0"

# 2 solutions without this, only 1 with it
"ABCDEFG % 7 = 0"

      Solution: Charlotte’s number was 187254963.

      And Oliver’s number was 781254963.

      Allowing leading zeros gives the following additional solutions:

      081254963
      087254963

      which could also be valid numbers for Oliver.

      Like

    • GeoffR's avatar

      GeoffR 7:19 pm on 3 June 2019 Permalink | Reply 

      % A Solution in MiniZinc 
include "globals.mzn"; 

var 1..9: a; var 1..9: b; var 1..9: c;
var 1..9: d; var 1..9: e; var 1..9: f;
var 1..9: g; var 1..9: h; var 1..9: i;

constraint all_different ( [a,b,c,d,e,f,g,h,i]);

% two digit numbers
var 10..99: ab = 10*a + b;
var 10..99: bc = 10*b + c;
var 10..99: cd = 10*c + d;
var 10..99: de = 10*d + e;
var 10..99: ef = 10*e + f;
var 10..99: fg = 10*f + g;
var 10..99: gh = 10*g + h;
var 10..99: hi = 10*h + i;

% number formed by first seven digits
var 1000000..9999999: abcdefg = 1000000*a + 100000*b + 10000*c
+ 1000*d + 100*e + 10*f + g;

% divisibility constraints
constraint ab mod 2 == 0 /\ bc mod 3 == 0
/\ cd mod 4 == 0 /\ de mod 5 == 0
/\ ef mod 6 == 0 /\ fg mod 7 == 0
/\ gh mod 8 == 0 /\ hi mod 9 == 0
/\ abcdefg mod 7 == 0;   % only Charlotte

solve satisfy;

output ["Charlotte's number = " ++ show(a),show(b),show(c),
show(d),show(e),show(f),show(g),show(h),show(i) ];

% Charlotte's number = 187254963
% time elapsed: 0.03 s
% ----------
% ==========
% Finished in 217msec

      Like

  • Unknown's avatar

    Jim Randell 10:57 am on 2 June 2019 Permalink | Reply
    Tags:   

    Brainteaser 1590: Demonoes 

    From The Sunday Times, 28th February 1993 [link]

    Damien deleted a dot from one of the dominoes so that when I laid them out randomly to form a rectangle I ended up with the following arrangement:

    Fill in the outlines of the dominoes.

    This puzzle is included in the book Brainteasers (2002). The wording above is taken from the book. It is slightly changed from the original puzzle.

    [teaser1590]

     
    • Jim Randell's avatar

      Jim Randell 10:58 am on 2 June 2019 Permalink | Reply

      The puzzle uses a standard set of dominoes, so there should be 8 instances of each digit.

      In the supplied grid there 9 0’s and only 7 1’s, so one of the 0’s should be a 1.

      I adapted the code used in Enigma 179, Enigma 303 and Enigma 342 to give a generic solver for this type of problem, which also includes code to output solution grids.

      This Python code runs in 204ms.

      Run: [ @repl.it ]

      from enigma import update, printf
from domino import DominoGrid

grid = [
  6, 2, 4, 2, 4, 4, 5, 4,
  3, 0, 3, 5, 5, 3, 6, 6,
  4, 4, 3, 5, 5, 2, 2, 3,
  3, 6, 3, 0, 0, 1, 1, 6,
  1, 5, 6, 6, 0, 2, 1, 4,
  1, 4, 2, 5, 0, 2, 1, 3,
  1, 2, 0, 0, 0, 5, 0, 6,
]

# look for 0's in the grid
for (i, x) in enumerate(grid):
  if x != 0: continue
  # try to fit the dominoes with the 0 replaced by a 1
  p = DominoGrid(8, 7, update(grid, [(i, 1)]))
  for s in p.solve():
    printf("[@{i}: 0 -> 1]\n")
    p.output_solution(s)

      Solution: The dominoes are arranged thus:

      There are two 0-5 dominoes shown highlighted in yellow. One of them should be a 1-5 domino (although we don’t know which one).

      It is likely I will fold the [[ DominoGrid() ]] class into the enigma.py library in a future release.

      Like

      • John Crabtree's avatar

        John Crabtree 5:09 am on 13 August 2020 Permalink | Reply

        The 4-0 is unique, and then 3-0 is unique. With some perseverance, one gets to the grid shown by Jim.

        Like

  • Unknown's avatar

    Jim Randell 8:16 pm on 31 May 2019 Permalink | Reply
    Tags:   

    Teaser 2958: Sudoku crossword 

    From The Sunday Times, 2nd June 2019 [link] [link]

    George and Martha are doing a mathematical crossword. There is a 3×3 grid with the numbers 1 to 9 inclusive appearing once each. The clues are as follows:

    Across:
     top line: a prime number
    middle line: a prime number
    bottom line: a prime number

    Down:
    left column: a perfect square
    middle column: a perfect square
    right column: a prime number

    Although you do not need to know this, one of the diagonal three-digit numbers is also prime.

    What is the sum of the three “across” numbers?

    [teaser2958]

     
    • Jim Randell's avatar

      Jim Randell 8:18 pm on 31 May 2019 Permalink | Reply

      We can solve this using the [[ SubstitutedExpression() ]] solver from the enigma.py library.

      This run file executes in 180ms.

      Run: [ @repl.it ]

      #! python -m enigma -rr

# consider the grid:
#
#  A B C
#  D E F
#  G H I

SubstitutedExpression

--digits="1-9"

"is_prime(ABC)"
"is_prime(DEF)"
"is_prime(GHI)"

"is_square(ADG)"
"is_square(BEH)"
"is_prime(CFI)"

--answer="ABC + DEF + GHI"

      Solution: The sum of the three across numbers is 1449.

      The grid is:

      2 8 3
5 4 7
6 1 9

      The across numbers are: 283 (prime), 547 (prime), 619 (prime), and their sum is 1449.

      The down numbers are: 256 (square), 841 (square), 379 (prime), and their sum is 1476.

      The diagonals can be read (left to right) as 249 and 643, and the second of these is prime.

      There are no further solutions if the digit 0 is not excluded.

      Like

    • GeoffR's avatar

      GeoffR 8:43 am on 21 June 2019 Permalink | Reply 

      
% A Solution in MiniZinc
include "globals.mzn"; 

%  Grid
%  A B C
%  D E F
%  G H I

var 1..9:A; var 1..9:B; var 1..9:C; 
var 1..9:D; var 1..9:E; var 1..9:F; 
var 1..9:G; var 1..9:H; var 1..9:I; 

constraint all_different ( [A,B,C,D,E,F,G,H,I]);

% Rows
var 100..999: ABC = 100*A + 10*B + C;
var 100..999: DEF = 100*D + 10*E + F;
var 100..999: GHI = 100*G + 10*H + I;

% Columns
var 100..999: ADG = 100*A + 10*D + G;
var 100..999: BEH = 100*B + 10*E + H;
var 100..999: CFI = 100*C + 10*F + I;

predicate is_prime(var int: x) = 
x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
((i < x) -> (x mod i > 0));

set of int: sq3 = {n*n | n in 10..31};

% Rows
constraint is_prime(ABC) /\ is_prime(DEF) /\ is_prime(GHI);

% Columns
constraint ADG in sq3 /\ BEH in sq3 /\ is_prime(CFI);

solve satisfy;

output [ "Rows total is "++ show(ABC + DEF + GHI) ]
++ [ "\nRows are "++ show(ABC)  ++ ", " ++ show(DEF) ++ 
" and " ++ show (GHI) ];

% Rows total is 1449
% Rows are 283, 547 and 619
% time elapsed: 0.02 s
 %----------
% ==========
% Finished in 253msec

      Like

  • Unknown's avatar

    Jim Randell 9:45 am on 30 May 2019 Permalink | Reply
    Tags:   

    Brain-Teaser 481: [Long Lane] 

    From The Sunday Times, 16th August 1970 [link]

    The houses in Long Lane are conventionally numbered; odd on one side, even on the other. Six of my friends, all of different professions, live there, all except Black on the same side of the road. Each man’s house has a two-digit number, and the sum of the twelve digits, which is a perfect square, equals the number of the solicitor’s house. One house, next door to Robinson, is vacant.

    Reversing the digits of the number of Robinson’s house give the number of the doctor’s house. Both numbers are primes. The two extreme numbers of the six are occupied by Jones and the dentist.

    Reversing the digits of Green’s house gives the number of the architect’s house, and the difference between the squares of these is the square of the number of journalist’s house. Smith and the stockbroker live next door to each other.

    What is the number of the vacant house? What is White’s profession? And what is the name of the stockbroker?

    This puzzle was originally published with no title.

    [teaser481]

     
    • Jim Randell's avatar

      Jim Randell 9:46 am on 30 May 2019 Permalink | Reply

      There are quite a few conditions. I started with the two conditions that deal with reversing one of the house numbers to get another number. Together these conditions give us the house numbers for two of the names and three of the jobs, so we can work out what the majority parity of the numbers is and fill out the remaining numbers appropriately.

      This Python program runs in 96ms.

      from enigma import (irange, filter2, is_prime, nreverse, is_square, subsets, flatten, printf)

# select the first x in xs that satisfies f
def select(xs, f):
  for x in xs:
    if f(x):
      return x

# possible house numbers
numbers = set(irange(10, 99))

# split them into even and odd numbers
(even, odd) = map(set, filter2(lambda n: n % 2 == 0, numbers))

# complete a set of 6 house numbers
def complete(ns):
  # count the even and odd numbers
  r0 = len(even.intersection(ns))
  r1 = len(odd.intersection(ns))
  # find the majority parity
  m = -1
  if r0 > 1: m += 1
  if r1 > 1: m += 2
  if m not in (0, 1): return
  # do we need to choose a minority number?
  for ys in subsets([odd, even][m].difference(ns), size=1 - [r1, r0][m]):
    # choose the remaining majority numbers
    for zs in subsets([even, odd][m].difference(ns), size=6 - len(ys) - len(ns)):
      s = ns.union(ys, zs)
      # sum the digits
      t = sum(flatten(divmod(n, 10) for n in s))
      # is a perfect square, and one of the numbers itself
      if not (t in s and is_square(t)): continue
      # return the candidate set
      yield (sorted(s), m, t)

# consider Green's house number
for Gre in numbers:
  # the reverse gives the number of the Architect's house
  Arc = nreverse(Gre)
  if Arc not in numbers: continue
  # and the difference between the squares
  # is the square of the number of the Journalist's house
  Jou = is_square(abs(Gre ** 2 - Arc ** 2))
  if Jou is None or Jou not in numbers: continue

  # Robinson's house number is a prime
  for Rob in numbers:
    if not is_prime(Rob): continue
    # and is the reverse of the Doctor's number
    Doc = nreverse(Rob)
    # which is also prime
    if not is_prime(Doc): continue

    # complete the set of numbers
    for (ns, m, t) in complete(set((Gre, Rob, Arc, Jou, Doc))):
      # the sum of the digits is the number of the Solicitor's house
      Sol = t
      # Black is in the minority parity house
      Bla = select(ns, (lambda n: n % 2 != m))

      # (at least) one of the houses next to Robinson is vacant
      vacant = set([Rob - 2, Rob + 2]).difference(ns)
      if len(vacant) < 1: continue

      # the extreme numbers are occupied by Jones and the Dentist
      for (Jon, Den) in subsets([ns[0], ns[-1]], size=2, permute=1):

        # and we now have 5 of the 6 professions
        ps = set([Arc, Jou, Doc, Sol, Den])
        if len(ps) != 5: continue
        Sto = select(ns, (lambda n: n not in ps))

        # and 4 of the 6 names
        ss = set([Gre, Rob, Bla, Jon])
        if len(ss) != 4: continue
        for (Smi, Whi) in subsets(ss.symmetric_difference(ns), size=2, permute=1):

          # Smith and the Stockbroker live next door to each other
          if not (abs(Smi - Sto) == 2): continue

          # output solutions
          name = { Gre: 'Green', Rob: 'Robinson', Bla: 'Black', Jon: 'Jones', Smi: 'Smith', Whi: 'White' }
          job = { Arc: 'Architect', Jou: 'Journalist', Doc: 'Doctor', Sol: 'Solicitor', Den: 'Dentist', Sto: 'Stockbroker' }
          for n in ns:
            printf("{n}: {name} ({job})", name=name[n], job=job[n])
          printf("vacant = {vacant}", vacant=sorted(vacant))
          printf()

      Solution: The vacant house is number 29. White is the Solicitor. Robinson is the Stockbroker.

      The solution is completely determined:

      13: Jones (Doctor)
      31: Robinson (Stockbroker)
      33: Smith (Journalist)
      49: White (Solicitor)
      56: Black (Architect)
      65: Green (Dentist)

      29: vacant

      Like

  • Unknown's avatar

    Jim Randell 9:01 am on 29 May 2019 Permalink | Reply
    Tags:   

    Teaser 2909: Pensionable service 

    From The Sunday Times, 24th June 2018 [link] [link]

    A few years ago my father was lucky enough to have been able to retire and take his pension at sixty. I explained to my young son – not yet a teenager – that this was not now usual, and that neither I nor he would be so lucky in the future.

    When I am as old as my father is now, I shall be six times my son’s present age. By then, my son will be nine years older than I am now. (These statements all refer to whole years and not fractions of years).

    How old am I now?

    [teaser2909]

     
    • Jim Randell's avatar

      Jim Randell 9:02 am on 29 May 2019 Permalink | Reply

      Very straightforward.

      Run: [ @repl.it ]

      # suppose the father is currently x, the setter y and the son z

from enigma import (irange, div, printf)

# the son is not yet a teenager
for z in irange(1, 12):

  # the father's current age is 6x the sons age
  x = 6 * z

  # but this is more than 60
  if not (x > 60): continue

  # the son will be 9 years older than the setters current age in (x - y) years
  # z + (x - y) = y + 9
  y = div(x + z - 9, 2)
  if y is None: continue

  printf("father = {x}, setter = {y}, son = {z}")

      Solution: You are 34.

      Manually (these are the same steps the program carries out):

      If the father is currently x, the setter y and the son z.

      Then, the son is not yet a teenager:

      z = 1 … 12

      The father is six times the son’s present age, x = 6z, and this is more than 60. The only two possibilities are:

      z = 11, x = 66
      z = 12, x = 72

      The son will be 9 years older than the setters current age in (x − y) years, so:

      z + (x − y) = y + 9
      y = (x + z − 9) / 2

      So we get:

      z = 11, x = 66, y = 34
      z = 12, x = 72, y = 75/2

      And only the first of these is viable.

      Liked by 1 person

    • Jim Randell's avatar

      Jim Randell 9:44 am on 30 May 2019 Permalink | Reply

      Here is a simple MiniZinc model for the puzzle:

      %#! minizinc -a

var int: x; % father's age
var int: y; % setter's age
var int: z; % son's age

% all ages are non-negative
constraint x > y /\ y > z /\ z > 0;

% father is aged over 60
constraint x > 60;

% son is not yet a teenager
constraint z < 13;

% father's age is 6x son's age
constraint x = 6 * z;

% the son will be 9 years older than the setters age in (x - y) years
constraint z + (x - y) = y + 9;

solve satisfy;

      Like

  • Unknown's avatar

    Jim Randell 7:44 am on 27 May 2019 Permalink | Reply
    Tags:   

    Teaser 2911: Remembering PINs 

    From The Sunday Times, 8th July 2018 [link] [link]

    My 10-year-old grandson has several PINs of various lengths to remember. To help him in this, he has systematically replaced different digits by different letters to get corresponding words as THREE, FIVE, SIX, SEVEN, NINE, TEN and FIFTEEN. Being very clever, he has arranged it so that each PIN is divisible by the number specified by the corresponding word.

    What is his PIN for FIFTEEN?

    [teaser2911]

     
    • Jim Randell's avatar

      Jim Randell 7:45 am on 27 May 2019 Permalink | Reply

      We can solve this puzzle using the [[ SubstitutedExpression() ]] solver from the enigma.py library, by writing an alphametic expression for each PIN.

      We also need to remember to allow leading zeros (this is required as TEN is divisible by 10, so NINE must have a leading zero).

      This run file executes in 130ms.

      Run: [ @replit ]

      #! python -m enigma -rr

SubstitutedExpression

--invalid="0,"
--answer="FIFTEEN"

"THREE % 3 = 0"
"FIVE % 5 = 0"
"SIX % 6 = 0"
"SEVEN % 7 = 0"
"NINE % 9 = 0"
"TEN % 10 = 0"
"FIFTEEN % 15 = 0"

      Solution: FIFTEEN = 1412550.

      The PINs are:

      THREE = 23955 or 29355
      FIVE = 1475
      SIX = 846
      SEVEN = 85750
      NINE = 0405
      TEN = 250
      FIFTEEN = 1412550

      H and R are 3 and 9 (in some order), the other letters are fixed.

      Like

    • GeoffR's avatar

      GeoffR 8:36 pm on 27 May 2019 Permalink | Reply 

      % A Solution in MiniZinc 
include "globals.mzn"; 

var 0..9: F; var 0..9: I; var 0..9: V; var 0..9: E; 
var 0..9: S; var 0..9: X; var 0..9: T; var 0..9: N; 
var 0..9: H; var 0..9: R;

constraint all_different ([F,I,V,E,S,X,T,N,H,R]);

% N = 0, since TEN is divisible by 10
constraint N == 0;  

% Lower bound for variables allows for zero as a leading digit
var 1000..99999: THREE = 10000*T + 1000*H + + 100*R + 11*E;
var 100..9999: FIVE = 1000*F + 100*I + 10*V + E;
var 10..999: SIX = 100*S + 10*I + X;
var 1000..99999: SEVEN = 10000*S + 1000*E + 100*V + 10*E + 0;
var 100..999: NINE = 100*I + 0 + E;  % since N = 0
var 10..999: TEN = 100*T + 10*E + 0;
var 100000..9999999: FIFTEEN = 1000000*F + 100000*I + 10000*F
+ 1000*T + 100*E + 10*E + N;

constraint THREE mod 3 == 0 /\ FIVE mod 5 == 0 /\ SIX mod 6 == 0
/\ SEVEN mod 7 == 0 /\ NINE mod 9 == 0 /\ TEN mod 10 == 0
/\ FIFTEEN mod 15 == 0;

solve satisfy;

output ["FIFTEEN = " ++ show(FIFTEEN) ]
++ ["\nTHREE = "++ show(THREE) ]
++ ["\nFIVE = "++ show(FIVE) ]
++ ["\nSIX = "++ show(SIX) ]
++ ["\nSEVEN = "++ show(SEVEN) ]
++ ["\nNINE = "++ show(NINE) ]
++ ["\nTEN = "++ show(TEN) ];

% FIFTEEN = 1412550
% THREE = 29355  (or THREE = 23955)
% FIVE = 1475
% SIX = 846
% SEVEN = 85750
% NINE = 405
% TEN = 250
%----------
%==========
%Finished in 214msec

      Like

  • Unknown's avatar

    Jim Randell 8:55 am on 26 May 2019 Permalink | Reply
    Tags:   

    Brainteaser 1575: Quantum scales 

    From The Sunday Times, 15th November 1992 [link]

    The merchants of Mathematica only ever have to weigh things that weigh a whole number of “quantums”, that country’s unit of weight. They have a pair of balancing scales, and four weights. By using these weights (on either side of the balance) they can determine the weight of items weighing 1, 2, 3, 4, 5, … quantums, and they have designed the four weights so that this sequence continues as high as it possibly can with just four weights.

    With their balance and weights they can determine the weight of a Maxpack, but not of anything heavier.

    What is the weight of a Maxpack?

    This puzzle is included in the book Brainteasers (2002). The wording above is taken from the book. It is slightly changed from the original puzzle, to remove an ambiguity.

    [teaser1575]

     
    • Jim Randell's avatar

      Jim Randell 8:55 am on 26 May 2019 Permalink | Reply

      First let’s consider a problem with being able to balance exact weights of 1 … n.

      If we can weigh the numbers 1 … n using k weights, then by adding an extra weight of (2n + 1) we can weigh:

      1 … n (using the original combinations of weights)
      n + 1 … 2n (using (2n + 1) − x, for each x in the original combinations of weights)
      2n + 1 (using the extra weight)
      2n + 2 … 3n + 1 (using (2n + 1) + x, for each x in the original combinations of weight)

      So, with a weight of 1, we can weigh 1 … 1.

      With weights of (1, 3) we can weigh 1 … 4.

      With weights of (1, 3, 9) we can weigh 1 … 13.

      With weights of (1, 3, 9, 27) we can weigh 1 … 40.

      (Each weight is an increasing power of 3, 3⁰ = 1, 3¹ = 3, 3² = 9, 3³ = 27, …).

      And this would be the best we could manage if we had to balance exact weights.

      But in this puzzle we know each object we have to weigh is one of the values 1 … N.

      So there is no point in being able to balance an object with a weight of 1, as if we can make a combination with a weight of 2, and determine that our object is lighter than it, then, as weights are quantised, it can only have a weight of 1.

      In fact, there is no point in having weights of any odd value, as we determine that a weight is between (2k) and (2k + 2), then it can only have a weight of (2k + 1).

      So, by doubling the 4 weights to (2, 6, 18, 54) we can balance exact weights of 2, 4, 6, 8, …, 80.

      And we will be able to determine the weight of any object weighing 1 … 80 units:

      Any object that has an even value from 2 … 80 can be balanced exactly.

      Any object with an odd value from 3 … 79 can be isolated between two even values.

      Any object that weighs less than 2, must have a value of 1.

      The weight of any object that weighs more than 80 units cannot be determined exactly.

      Solution: The weight of a Maxpack is 80 units.

      Like

  • Unknown's avatar

    Jim Randell 10:39 pm on 24 May 2019 Permalink | Reply
    Tags:   

    Teaser 2957: Beyond the fields we know 

    From The Sunday Times, 26th May 2019 [link] [link]

    A field named “Dunsany levels” has four unequal straight sides, two of which are parallel. Anne — with her dog, Newton — walked from one corner of the field straight towards her opposite corner. Leon did the same from an adjacent corner along his diagonal. Yards apart, they each rested, halfway along their paths, where Leon, Anne and a signpost in the field were perfectly aligned. Straight fences from each corner converged at the signpost, making four unequal-area enclosures.

    Newton made a beeline for the signpost, on which the whole-number area of the field, in acres, was scratched out. Clockwise, the enclosures were named: “Plunkett’s bawn”, “Three-acre meadow”, “Drax sward” and “Elfland lea”. Anne knew that “Three-acre meadow” was literally true and that “Elfland lea” was smaller by less than an acre.

    What was the area of “Dunsany levels” in acres?

    [teaser2957]

     
    • Jim Randell's avatar

      Jim Randell 11:03 pm on 24 May 2019 Permalink | Reply

      The field is a trapezium (trapezoid in US terminology).

      By drawing a diagram of the layout we determine that there is only a limited range of possible values for the area of Elfland Lea, and only one of which gives a whole number for the total area of the field.

      Solution: The total area of the field is 11 acres.

      Here is my analysis:

      We can draw the trapezium, ABCD, with the parallel sides horizontal, and we get a diagram like this:

      I assumed that “halfway” meant exactly at the midpoint.

      The midpoints of the diagonals AC and BD are exactly half way between the parallel lines AB and CD, so the signpost lies on the line XY (and obviously within the field).

      If we suppose the trapezium has a height of 2h, then the line XY is a distance h from both AB and CD.

      Now if we suppose the signpost S lies somewhere on this line:

      If the length of AB is q and the length of CD is p, and the trapezium has a height of 2h, then the area of the trapezium is:

      area(ABCD) = (p + q)h = ph + qh

      And the area of the triangles ABS and CDS are:

      area(ABS) = qh/2
      area(CDS) = ph/2

      (and the exact position of S does not matter, as long as it is on line XY).

      So it follows that the combined area of the triangles ADS and BCS is:

      area(ADS) + area(BCS) = ph/2 + qh/2

      (the same as the combined area of triangles ABS and CDS).

      And one of these pairs consists of “Three-acre meadow” and “Elfland lea”. So one enclosure is exactly 3 acres, and the other is somewhere between 2 and 3 acres (excluding the endpoints), so the combined area of these two enclosures is between 5 and 6 acres (excluding the endpoints).

      The total area of the field is twice this value, so it is an integer between 10 and 12 (excluding the endpoints). The answer follows directly, without the need to write a program.

      Like

← Older posts

Newer posts →

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
Design a site like this with WordPress.com
Get started