S2T2 | Solving Sunday Times Teasers

Recent Updates Page 45 Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 8:47 am on 4 March 2021 Permalink | Reply
Tags: by: Susan Bricket ( 17 )
Teaser 2778: Cold turkey
From The Sunday Times, 20th December 2015 [link] [link]

We are having a “cold turkey” party on Boxing Day. Fewer than 100 people have indicated that they are coming, and the percentage of them choosing the vegetarian option is (to the nearest whole number) a single-digit number. My vegetarian aunt might also come. If she does, then (to the nearest whole number) the percentage having the vegetarian option will remain the same.

If she does come, how many people will be there and how many of them will have the vegetarian option?

[teaser2778]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 8:48 am on 4 March 2021 Permalink | Reply
  This Python program runs in 47ms.
  
  Run: [ @repl.it ]
```
from enigma import divf, irange, printf

# percentage a/b to the nearest whole number
percent = lambda a, b: divf(200 * a + b, 2 * b)

# total number of people expected (including aunt)
for n in irange(2, 100):
  # consider number of vegetarians
  for v in irange(1, n):
    # percentage vegetarians (to nearest whole number)
    p = percent(v, n)
    if p > 9: break

    # and if aunt doesn't come, is percentage the same?
    if percent(v - 1, n - 1) == p:
      # output solution
      printf("{n} total; {v} veg [{p}% veg]")
```
  Solution: If the aunt comes there will be 95 people in total. 9 of them vegetarian.
  
  In this case the percentage of vegetarians is 9/95 ≈ 9.47%, which rounds down to 9%.
  
  But if the aunt doesn’t come both the number of guests and the number of vegetarians is reduced by 1, giving a percentage of 8/94 ≈ 8.51%, which rounds up to 9%.
  
  Note that Python 3’s built-in [[ round() ]] function might not do what you expect:
```
% python3.9
>>> round(11.5)
12
>>> round(12.5)
12
>>> round(1.15, 1)
1.1
>>> round(0.115, 2)
0.12
```
  The decimal module allows more control over rounding behaviour.
  
  To keep things predictable, in my program I avoided float approximations by keeping the calculations in the integer domain, and I used the common “round half up” rule.
  
  LikeLike
Reply Cancel reply
Required fields are marked *

Name *

Email *

Website

Notify me of new comments via email.
Notify me of new posts via email.
Δ

Jim Randell 8:41 am on 2 March 2021 Permalink | Reply
Tags: by: J E Kessel, by: J R Partridge

Brain-Teaser 696: The Browning version

From The Sunday Times, 17th November 1974 [link]

You see, Inspector, the combination of my safe is a six-figure number. In case anyone needed to get into it while I was away, I gave each of my clerks (Atkins, Browning and Clark) one of the two-figure numbers which make up the combination. I also told each the position in the combination of the number of another clerk, but not the number itself.

Browning must have overheard me telling a friend that it is a coincidence that two of these numbers are squares and if you put them together you get a four-figure number that equals the other clerk’s number squared. I remember I also said something about whether or not the combination is divisible by this clerk’s number.

When he was caught, Browning said, “I can’t understand why the alarm went off; I know Clark’s is the first number”. I later realised that what I’d told my friend about whether or not that other number was a factor was wrong, which was lucky for me as Browning had got his own number in the right place.

What was the combination?

This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.

[teaser696]

Jim Randell 8:43 am on 2 March 2021 Permalink | Reply
This Python program looks for candidate sets of numbers where two of the numbers are 2-digit squares, that when concatenated form a 4-digit square, that is the square of the third number. (I assumed none of the squares had leading zeros).

Once these are found we can construct a list of all possible scenarios, and then select those where B would be able to work out the combination with the information he has (even though one of the pieces of information is in fact incorrect).

Once we find B’s deduced combinations, we can look for actual scenarios that have B’s number in the correct place, but have the correct information, and this will give us the actual combination.

It runs in 49ms.

Run: [ @repl.it ]
```
from itertools import product
from enigma import irange, is_square, subsets, nsplit, nconcat, filter_unique, unpack, printf

# collect possible scenarios
ss = list()

# consider 2 digit numbers for one of the clerks numbers
for x in irange(32, 99):
  # and the square of this gives the other 2 numbers
  (y, z) = nsplit(x * x, 2, base=100)
  # both of which are 2-digit squares
  if not all(n > 9 and is_square(n) for n in (y, z)): continue
  printf("[{x} -> {y} : {z}]")
  # consider possible actual combinations (s), and assignments of (x, y, z) to (A, B, C)
  for (s, (A, B, C)) in product(subsets((x, y, z), size=len, select="P"), repeat=2):
    ss.append((s, (nconcat(s, base=100) % x == 0), A, B, C))

# B knows his own number, the value of the flag, and that C's number is first
# so we can find scenarios where B would think he knew the combination
rs = filter_unique(
  # for all possibilities with C's number first ...
  filter(unpack(lambda s, f, A, B, C: s[0] == C), ss),
  # ... knowing B's number and the value of the flag ...
  unpack(lambda s, f, A, B, C: (B, f)),
  # ... let's you work out the combination
  unpack(lambda s, f, A, B, C: s),
).unique

# consider possible scenarios
for (s, f, A, B, C) in rs:
  # find the index of B's pair
  b = s.index(B)
  # look for candidates with B's number in index b, but flag is the opposite
  actual = set(s1 for (s1, f1, A1, B1, C1) in ss if s1[b] == B == B1 and f1 != f)
  # output solution(s)
  for x in sorted(actual):
    printf("actual = {x} [B={B} f={f} -> attempt = {s}]")
```
Solution: The combination was 811641.

Fortunately there is only one candidate set of numbers, such that a 4-digit square is composed of the concatenation of two 2-digit squares.

That is: 41² = 1681 = 16:81.

So we know the safe’s combination is some ordering of the numbers (16, 41, 81).

And B overheard this construction, and also (so he thought) whether the combination is divisible by 41 or not.

There are 2 scenarios where B can think he is able to deduce the combination:

B was given number 41, and told C’s number was first.
He overheard that the combination is divisible by 41.
In this case B will attempt: (16, 81, 41).

B was given number 16, and told C’s number was first.
He overheard that the combination is divisible by 41.
In this case B will attempt: (41, 16, 81).

In both cases B got his own number in the correct position, but got the other two in the wrong positions, setting off the alarm.

So, in both cases, the actual combination is (81, 16, 41), and 181641 is not divisible by 41.

LikeLike

Frits 11:45 pm on 2 March 2021 Permalink | Reply

from collections import defaultdict
from itertools import permutations

# 2-digit squares
sqs = [x * x for x in range(4, 10)]

cands = [] 
# consider 2 digit numbers for one of the clerks numbers
for i in range(32, 100):
  # and the square of this gives the other 2 numbers
  i2 = i * i
  # view <i2> as abcd
  (ab, cd) = (i2 // 100, i2 % 100)
  # both of which are 2-digit squares
  if ab not in sqs or cd not in sqs: continue
  cands.append([i, ab, cd])

fnum = defaultdict(list)    # store info for the first 2-digit number
for cand in cands:
  # uvwxyz is a possible ordering of entries in <cand>
  for uv, wx, yz in permutations(cand):
    uvwxyz = 100 * (100 * uv + wx) + yz
    check = (uvwxyz % cand[0] == 0)
    
    # is there both a True and False combination per first 2-digit number?
    tf = check if uv not in fnum else fnum[uv][0][-1] ^ check
    fnum[uv].append([uvwxyz, check, tf])  
   
  # how many possible numbers are divisible by the first 2-digit number 
  n_divisible = sum(1 for k, vs in fnum.items() for (_, div, _) in vs if div)
  if n_divisible < 3:
    print("Browning thinks the combination is divisible by", cand[0])
  else:  
    print("Browning thinks the combination is not divisible by", cand[0])
  
  # collect first 2-digit numbers where one of the two 6-digit numbers
  # is divisible by <cand[0]> and the other isn't
  both_tf = list({k for k, vs in fnum.items() for (_, _, tf) in vs if tf})
  
  if len(both_tf) == 2:
    # suppose the two 2-digit numbers in <both_tf> are <p> and <q>
    # if B was given number <p> and C was given the first number
    # B has to look at the 6-digit numbers with first digit number <q>
    for i, p in enumerate(both_tf):
      # B will choose the other entry
      for guess, div, _ in fnum[both_tf[1-i]]:
        # B chose <guess> which didn't open the safe
        # but B had got his own number <p> in the right place
        # so we have to switch the other 2-digit numbers 
        
        if (div and n_divisible < 3) or (not div and n_divisible > 3):  
          s = str(guess)
          comb = int(s[2:4] + s[:2] + s[4:]) if guess % 100 == p \
            else int(s[4:] + s[2:4] + s[:2])
          print(f"combination = {comb}, Brown guessed {guess} "
                f"if he was given number {p}")

LikeLike

Jim Randell 8:25 am on 28 February 2021 Permalink | Reply
Tags: by: Herbert Wright

Brain-Teaser 24: [Shades of Gray]

From The Sunday Times, 3rd September 1961 [link]

Someone here in Land’s End Lane of the name of Roger Gray (or is it “Grey”? I never can remember which), seems gratified to find that by allotting distinctive digits against appropriate letters of the alphabet he can, by substituted figures for letters, make an addition sum of his name, the answer to which, converted back into letters in similar manner, spells his house number.

There seems nothing particularly surprising in this, for if it really is “Gray” and if he happened to live at No. 7, as I do, all he would have to do would be to write:

and substitute say:

However, he doesn’t live at No. 7, and moreover, I happen to know that there’s an 8 in his sum.

So where does Roger live, and what is his sum?

This puzzle was originally published with no title.

[teaser24]

Jim Randell 8:26 am on 28 February 2021 Permalink | Reply

The house number must be 5 or 6 letters, so there is only a limited number of possibilities.

We can use some handy routines from the enigma.py library to solve this puzzle. The [[ int2words() ]] function converts a number into English, and then we can use the [[ SubstitutedSum() ]] solver to find solutions to the corresponding alphametic sums.

The following Python program runs in 127ms.

from enigma import (irange, int2words, translate, SubstitutedSum, printf)

# suppose the house number is n (not 7)
for n in irange(1, 100):
  if n == 7: continue
  word = translate(int2words(n).upper(), (lambda x: x if x.isalpha() else ''))
  if not (4 < len(word) < 7): continue

  # construct the alphametic sum
  for terms in [('ROGER', 'GRAY'), ('ROGER', 'GREY')]:
    p = SubstitutedSum(terms, word)
    for s in p.solve(verbose=0):
      # one of the letters has to be 8
      if not (8 in s.values()): continue
      # output solution
      printf("{p.text} / {t}", t=p.substitute(s, p.text))

Solution: Roger Gray lives at number 12. The sum is: 94729 + 7953 = 102682.

LikeLike

Frits 10:43 pm on 1 March 2021 Permalink | Reply

Only calling SubstitutedExpression once, looking for trouble.

In order to get a decent run time (1 second with PyPy) I had to use some analysis (like skipping all the words ending on “Y”). Only 4 words (THREE, EIGHT, ELEVEN and TWELVE) remain to be checked.

from enigma import SubstitutedExpression, int2words, translate

def check(num, txt):        # txt has format (_.....)
  # first letter may not be zero
  if len(str(num)) < len(txt) - 3:
    return False
  # number of different digit must match number of letters
  return len(set(str(num))) == len(set(txt)) - 3
  
words = [] 
# suppose the house number is n
for n in range(1, 100):
  if n == 7: continue
  word = translate(int2words(n).upper(), (lambda x: x if x.isalpha() else ''))
  if not(4 < len(word) < 7): continue
  # units: R + Y can't be equal to Y (else R would have to be zero)
  if word[-1] == "Y": continue
  words.append(word)

lower = "".join([x for x in "abcdefghijklmnopqrstuvwxyz" 
                 if x not in "if else or and not sum check str"])
bits = lower[:len(words)]
exprs = ["sum([" + ','.join(bits) + "]) == 1"]

for i, word in enumerate(words):
  if len(word) == 6:
    exprs.append(bits[i] + " == 0 or R == 9")
    exprs.append(bits[i] + " == 0 or " + word[0] + " == 1")
    exprs.append(bits[i] + " == 0 or Y - 1 == " + word[-1])
  else:
    exprs.append(bits[i] + " == 0 or " + word[0] + " - 1 == R")
 
  exprs.append(bits[i] + " == 0 or " + word + " - ROGER in {GRAY, GREY}")
  exprs.append(bits[i] + " == 0 or '8' in str(" + word + ")")
  exprs.append(bits[i] + " == 0 or check(" + word + ", '" + word + "')")
  
# collect letters not used in words, they can't have value 8  
outside = "".join([x for x in "ROGEYA" if x not in "".join(words)])
symbols = "".join(set("ROGEYA" + "".join(words))) + bits
dist = ["ROGEYA" + c for c in [x for x in set(''.join(words)) 
        if x not in "ROGEYA"]]

# puzzle
p = SubstitutedExpression(
  exprs,
  symbols=symbols,
  distinct=dist,
  answer="(ROGER + GRAY if '8' in str(ROGER + GRAY) else ROGER + GREY), " + 
         " + ".join([x + ' * ' + str(i) for i, x in enumerate(bits)]),
  env=dict(check=check),
  verbose=0,
  d2i=dict([(0, "RG")] +  
           [(k, bits) for k in range(2, 8)] +
           [(8, outside + bits)] +
           [(9, bits)])
)

# print answer
sol = set()
for (_, ans) in p.solve():
  sol.add(words[ans[1]] + " = " + str(ans[0]))  

print(*sol)

LikeLike

Jim Randell 5:03 pm on 26 February 2021 Permalink | Reply
Tags: by: Andrew Skidmore ( 87 )

Teaser 3049: Plantation

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

Jed farms a large, flat, square area of land. He has planted trees at the corners of the plot and all the way round the perimeter; they are an equal whole number of yards apart.

The number of trees is in fact equal to the total number of acres (1 acre is 4840 square yards). If I told you an even digit in the number of trees you should be able to work out how far apart the trees are.

How many yards are there between adjacent trees?

It is now 60 years since the first numbered Teaser puzzle was published — Brain-Teaser 1: Tall story — on 26th February 1961.

Congratulations to The Sunday Times!

[teaser3049]

Jim Randell 5:22 pm on 26 February 2021 Permalink | Reply

Here is a constructive solution.

This Python program runs in 56ms.

Run: [ @repl.it ]

from collections import defaultdict
from enigma import irange, inf, is_square, nsplit, peek, printf

# generate (number-of-trees, total-area, size-of-square, distance-between-trees)
def generate():
  # consider total number of trees (t = 4n)
  for t in irange(4, inf, step=4):
    # this is the same as the total number of acres
    # calculate the area in square yards
    a = 4840 * t
    # but the area is a square
    # and the side is a whole number of yards
    s = is_square(a)
    if s is None: continue
    # so the distance between trees is...
    (d, r) = divmod(4 * s, t)
    if d < 1: break
    if r == 0:
      printf("[t={t} a={a} s={s} d={d}]")
      yield (t, a, s, d)

# collect candidate solutions by the even digits of the number of trees
digits = {0, 2, 4, 6, 8}
r = defaultdict(set)
for (t, a, s, d) in generate():
  for x in digits.intersection(nsplit(t)):
    r[x].add(d)

# look for digits that give a unique distance
for (x, ds) in r.items():
  if len(ds) == 1:
    printf("digit {x} -> distance {ds} yards", ds=peek(ds))

Solution: The distance between trees is 4 yards.

Manually:

If there are t = 4n trees around the perimeter, then we can calculate the distance d between them as:

d = 88 √(5 / 2n)

So:

n⋅d² = 19360 = (2^5)(5)(11^2)

Which gives the following (d, n) values:

(d=1, n=19360) → t=77440
(d=2, n=4840) → t=19360
(d=4, n=1210) → t=4840
(d=11, n=160) → t=640
(d=22, n=40) → t=160
(d=44, n=10) → t=40

Looking at the t values we see that, of the even digits, only 8 gives a unique solution.

Here is a Python program that uses the same approach:

from collections import defaultdict
from enigma import divisors_pairs, is_square, irange, nsplit, peek, printf

# generate (number-of-trees, distance-between-trees)
def generate():
  # n.d^2 = 19360
  for (n, d2) in divisors_pairs(19360, every=1):
    d = is_square(d2)
    if d is None: continue
    # return (t, d)
    t = 4 * n
    printf("[d={d} n={n} -> t={t}]")
    yield (t, d)

# group candidate solutions by the even digits of the number of trees
digits = set(irange(0, 9, step=2))
r = defaultdict(set)
for (t, d) in generate():
  for x in digits.intersection(nsplit(t)):
    r[x].add(d)

# look for digits with a single distance
for (x, ds) in r.items():
  if len(ds) == 1:
    printf("digit {x} -> distance {ds} yards", ds=peek(ds))

LikeLike

Tony Brooke-Taylor 12:57 pm on 27 February 2021 Permalink | Reply

My solution replicates my manual approach. It is an order or magnitude quicker than yours – I think because I am being much more selective about the cases I try. Ironically it took me about ten times as long to code as it took me to solve the problem manually!

#let the number of trees on a side be n, and the distance between trees be x yards, so the length of a side is n.x 

#we are told that the total number of trees is equal to the area in acres, so
#4n=((n.x)**2)/4840 

#For integer values of n, valid values of x**2 must be made up of factors of 4*4840

def factors(n):    
    j = 2
    while n > 1:
        for i in range(j, int(n**(1/2)) + 1):
            if n % i == 0:
                n /= i ; j = i
                yield i
                break
        else:
            if n > 1:
                yield int(n); break

facs=list(factors(4*4840))

#furthermore, if x is an integer, x**2 can only be made up of products of squares, meaning that we can only combine factors in multiples of two

cofac=1
mults=[]
for fac in set(facs):
  if facs.count(fac)%2==1: cofac *= fac
  if facs.count(fac)//2>0:mults.append([fac**i for i in range(facs.count(fac)//2+1)])

#mults contains the possible multiples of each valid prime factor; cofac is the product of factors that do not form part of a pair

#use mults to generate all possible values for x
x_vals=[1]
for vec in mults:
  x_vals = [(i*j) for i in x_vals for j in vec]

#each value of x generates a possible value for 4n  
n_vals=list(zip(x_vals,[4*(x**2)*cofac for x in x_vals]))

#we are now looking for the value for 4n which contains a unique instance of a given even number, so let's collect all digits in all our possible 4n's

digits=[]
for n in n_vals:
  digits=digits+([dig for dig in str(n[1])])

#then find the value of 4n which contains the even digit that appears in only one value of 4n
for ev in range(2,9,2):
  if digits.count(str(ev)) == 1:
    result_n = [n for n in n_vals if str(ev) in str(n[1])][0]

print("The distance between adjacent trees is",(result_n[0]),"yards.")

LikeLike

Jim Randell 4:40 pm on 27 February 2021 Permalink | Reply

@Tony: I also did some analysis which gives a fairly short manual solution (or a short program). I’ve put the code up on repl.it [link], and I’ll post the analysis later.

LikeLike
Frits 5:26 pm on 27 February 2021 Permalink | Reply

@Tony,

I have taken a similar approach like you (number of trees on a side is n) but I reach a different answer.

At the Notes section of the Enigmatic Code (link in the About section) site Jim has described how you can include Python code so that it is displayed with colors.

LikeLike
- Tony Brooke-Taylor 9:48 am on 28 February 2021 Permalink | Reply
  
  Brian has spotted my error. Thanks for the tip re: posting. Hopefully any posts I make in future will be more legible.
  
  LikeLike
Brian Gladman 9:31 am on 28 February 2021 Permalink | Reply
Line 38 should be:
```
n_vals = list(zip(x_vals, [16 * 4840 // (x ** 2) for x in x_vals]))
```
LikeLike
- Tony Brooke-Taylor 9:46 am on 28 February 2021 Permalink | Reply
  
  So it should, thanks.
  
  LikeLike

Frits 4:53 pm on 27 February 2021 Permalink | Reply

from enigma import divisors_pairs
from math import isqrt

#          n trees  
#     x . . . . . . . x
#  n  .               . n     T = 4 * (n - 1),  total number of trees
#     .               .             
#  t  .    Jed's      . t     A = (n - 1)^2 * D^2,  A = area, D = distance
#  r  .               . r 
#  e  .    land       . e     no acres A / 4840 = T
#  e  .               . e   
#  s  .               . s     so (n - 1) * D^2 = 4 * 4840 = 19360
#     x . . . . . . . x
#          n trees  
  
# make a list of possible <T> and <D> values
TD = [(4 * b, sa) if sa * sa == a else (4 * a, sb) 
      for (a, b) in divisors_pairs(19360) 
      if (sa := isqrt(a)) ** 2 == a or (sb := isqrt(b)) ** 2 == b]

# check if a certain even digit occurs in only one of the <T> values
for dgt in '02468':
  if len(q := [x[1] for x in TD if dgt in str(x[0])]) == 1:
    print(f"answer = {q[0]} yards")

LikeLike

Jim Randell 10:43 am on 25 February 2021 Permalink | Reply
Tags: by: Eric Emmet ( 10 )
Brain-Teaser 846: The Rajah’s jewels
From The Sunday Times, 2nd October 1977 [link]

It was a frightened, breathless, but very charming young lady who knocked on my office door late one night.

“They have gone”, she said: “The Rajah’s rubies are no longer in their ancestral home”.

I visited the scene of the crime and discovered a tattered piece of paper on which was written:

Where were the jewels hidden?

This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.

[teaser846]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 10:44 am on 25 February 2021 Permalink | Reply
  We can use the [[ SubstitutedDivision() ]] solver from the enigma.py library to solve the alphametic long division sum, and then we can create a map of digits to letters, and use that to translate to final string of digits back into letters.
  
  This Python program runs in 58ms.
  
  Run: [ @repl.it ]
```
from enigma import (SubstitutedDivision, translate, printf)

# the alphametic division puzzle
p = SubstitutedDivision(
  "?DEEF? / NU = O?SU",
  [ "?DE - NU = UR", "UR? - DTE = SH", "SH? - UT? = DF", "DFD - DT? = T" ],
)

# solve the puzzle
for s in p.solve(verbose=0):
  # map digits -> symbols
  d = dict((str(v), k) for (k, v) in s.d.items())
  # translate the string of digits
  r = translate("4936270681427669705719691270187069477266", d)
  # output solution
  printf("{r} [{s.a} / {s.b} = {s.c} (rem {s.r})]")
```
  Solution: The message reads: “UNDER THE FOURTEENTH STONE NORTH OF THE NUT TREE”.
  
  The division sum is: 136683 ÷ 94 = 1454 (remainder 7).
  
  Which gives us a mapping between digits and letters.
  
  The string of digits then translates as:
  
  UNDERTHEFOURTEENTHSTONENORTHOFTHENUTTREE
  
  which, with appropriate breaks reads:
  
  UNDER THE FOURTEENTH STONE NORTH OF THE NUT TREE
  
  LikeLike
Jim Randell 8:42 am on 23 February 2021 Permalink | Reply
Tags: by: Richard England ( 9 ), flawed ( 54 )
Teaser 2777: Summing up 2015
From The Sunday Times, 13th December 2015 [link] [link]

I asked Harry and Tom to write down three numbers that between them used nine different digits and which added to 2015. They each succeeded and one of Harry’s three numbers was the same as one of Tom’s. I noticed that Harry’s three numbers included a perfect square and Tom’s included a higher perfect square.

What were those two squares?

[teaser2777]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Frits and Jim Randell are discussing. Toggle Comments
- Jim Randell 8:44 am on 23 February 2021 Permalink | Reply
  As stated there are multiple solutions to the puzzle.
  
  Having tackled similar problems before it seems likely that the intention of the setter is:
  
  “… three numbers that between them used nine different digits, each of them [exactly] once …”
  
  or possibly:
  
  “… three 3-digit numbers that between them used nine different digits …”
  
  Any solution for the latter will appear as a solution for the former, so we will use the first one to solve the puzzle (as it turns out it does give a unique answer).
  
  The following Python code generates possible sums that use a square and 2 other numbers to produce the required total, and where each of 9 digits is used exactly once in the summands.
  
  It then choose sums that use different squares, but have one of the other numbers in common.
  
  It runs in 95ms.
  
  Run: [ @repl.it ]
```
from enigma import (
  cproduct, powers, inf, is_duplicate, irange, concat, multiset,
  group, unpack, subsets, intersect, join, arg, printf
)

# target sum
Y = arg(2015, 0, int)
printf("[Y={Y}]")

# generate (s, a, b) sums, s is square, s + a + b = Y
def generate(Y):
  # consider squares
  for s in powers(0, inf, 2):
    if s > Y: break
    if is_duplicate(s): continue

    # find sums: s + a + b = Y
    t = Y - s
    for a in irange(0, t // 2):
      b = t - a
      # check for sums with 9 different digits
      ds = concat(s, a, b)
      # check for 9 different digits
      if len(ds) == 9 and len(set(ds)) == 9:
        yield (s, a, b)

# group sums by the square
d = group(generate(Y), by=unpack(lambda s, a, b: s))

# collect the squares involved
r = multiset()

# consider squares for Harry and Tom
for (sH, sT) in subsets(sorted(d.keys()), size=2):

  # choose decompositions
  for (dH, dT) in cproduct([d[sH], d[sT]]):

    # that share a number
    if intersect([dH, dT]):
      printf("[H = {dH}; T = {dT}]", dH=join(dH, sep=" + "), dT=join(dT, sep=" + "))
      r.add((sH, sT))

# output solutions
for (k, v) in r.most_common():
  printf("squares = {k} [{v} solutions]", k=join(k, sep=", "))
```
  Solution: Harry’s square was 324. Tom’s square was 784.
  
  There are two ways to arrive at the solution:
  
  Harry: 324 + 785 + 906 = 2015
  Tom: 784 + 325 + 906 = 2015
  
  Harry: 324 + 786 + 905 = 2015
  Tom: 784 + 326 + 905 = 2015
  
  The summands in each sum use all the digits exactly once except for the digit 1.
  
  To see the multiple solutions without the restriction that each of the 9 digits is used exactly once, you can remove line 15 and the [[ len(ds) == 9 ]] clause from line 24.
  
  The same puzzle could have been set in 2019, and had the same answer.
  
  If the puzzle were set in 2022, there would only be one way to arrive at the (different) answer.
  
  LikeLike
- Frits 2:04 pm on 23 February 2021 Permalink | Reply
  I assumed Harry’s and Tom’s squares were not the number they shared (ABCD).
```
from enigma import SubstitutedExpression, is_square

# the alphametic puzzle
p = SubstitutedExpression(
  [
  # Use 4-digit numbers as sum is limited to 2015
  
  # to reduce the output assume EFGH (Harry) and MNOP (Tom) 
  # are both perfect squares
  "is_square(EFGH)",
 
  # use a variable as right hand side to reduce the number of loops
  "2015 - ABCD - EFGH = IJKL",
  
  # nine different digits
  "len(str(ABCD) + str(EFGH) + str(IJKL)) == \
   len(set(str(ABCD) + str(EFGH) + str(IJKL))) == 9",
  
  # Tom's included a higher perfect square
  "MNOP > EFGH and is_square(MNOP)",
 
  # use a variable as right hand side to reduce the number of loops
  "2015 - ABCD - MNOP = QRST",
  
  # nine different digits
  "len(str(ABCD) + str(MNOP) + str(QRST)) == \
   len(set(str(ABCD) + str(MNOP) + str(QRST))) == 9",
  ],
  answer="EFGH, MNOP",
  d2i=dict([(k, "AEIMQ") for k in range(3, 10)]),
  verbose=0,
  distinct="",
)

# Print answers
sols = set(sol for (_, sol) in p.solve())
print(f"answer = {sols}")
```
  LikeLike
Jim Randell 8:53 am on 21 February 2021 Permalink | Reply
Tags: by: F. Moore ( 2 )
Brain-Teaser 23: [Money sharing]
From The Sunday Times, 27th August 1961 [link]

A man divided 8s. 4d. among his three sons so that the difference between the shares of the eldest and youngest, expressed in halfpence, was a perfect square. The total of Alan’s and Bob’s shared was an exact multiple of 5½d.; the total of Bob’s and Clive’s shares an exact multiple of 6½d.; and the total of Alan’s and Clive’s shares an exact multiple of 9½d.

What was the name of the second son, and what was his share?

This puzzle was originally published with no title.

[teaser23]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
John Crabtree, Jim Randell, Hugh Casement, and 1 other are discussing. Toggle Comments
- Jim Randell 8:55 am on 21 February 2021 Permalink | Reply
  1s = 12d.
  
  Working in half-pennies (hp) the total amount to distribute is 100 d = 200 hp.
  
  And we are told:
  
  11 | (A + B)
  13 | (B + C)
  19 | (A + C)
  
  And the difference between two of the numbers is a square number of half pennies.
  
  The following Python program runs in 53ms.
  
  Run: [ @repl.it ]
```
from enigma import irange, is_square, div, printf

# solve the equations
def solution(middle, AB, AC, BC):
  A = div(AB + AC - BC, 2)
  B = div(AB + BC - AC, 2)
  C = div(AC + BC - AB, 2)
  if not any(x is None or x < 0 for x in (A, B, C)):
    # output solution
    printf("A={A} hp, B={B} hp, C={C} hp; middle = {middle}")

# A + C is some multiple of 19
for AC in irange(19, 200, step=19):

  # B + C is some multiple of 13
  for BC in irange(13, 200, step=13):

    # A + B is some multiple of 11
    # and (A + B) + (B + C) + (A + C) = 2(A + B + C) = 400
    AB = 400 - (AC + BC)
    if AB % 11 > 0: continue

    # one of the differences is a square
    # B - C = (A + B) - (A + C)
    if is_square(abs(AB - AC)): solution('A', AB, AC, BC)
    # A - C = (A + B) - (B + C)
    if is_square(abs(AB - BC)): solution('B', AB, AC, BC)
    # A - B = (A + C) - (B + C)
    if is_square(abs(AC - BC)): solution('C', AB, AC, BC)
```
  Solution: The middle son was Clive. His share was 45d = (3s 9d).
  
  The shares are:
  
  A: 5 hp = 2.5 d
  B: 105 hp = 52.5 d (= 4s 4.5d)
  C: 90 hp = 45 d (= 3s 9d)
  
  And we see:
  
  A + B = 110 hp = 10× 11 hp
  B + C = 195 hp = 15× 13 hp
  A + C = 95 hp = 5× 19 hp
  
  And the difference between the eldest and the youngest is: B − A = 10² hp.
  
  LikeLike
- Frits 11:53 am on 21 February 2021 Permalink | Reply
```
from enigma import SubstitutedExpression, is_square, peek

# the alphametic puzzle
p = SubstitutedExpression(
  [# A = AST, B = BVW, C = CYZ
  
  # start with the most restrictive constraint
  
  # A + C is some multiple of 19
  "(AST + CYZ) % 19 == 0",
  
  # divide 200 half-pennies over 3 sons
  "200 - AST - CYZ = BVW", 
  
  # B + C is some multiple of 13
  "(BVW + CYZ) % 13 == 0",
  
  # A + B is some multiple of 11
  "(AST + BVW) % 11 == 0",
  
  # difference between the eldest and youngest was a perfect square
  "peek(2 - i for (i, (x, y)) in \
   enumerate(zip([AST, CYZ, BVW], [BVW, AST, CYZ])) \
   if is_square(abs(x - y))) = I",
  ],
  answer="I, [AST, BVW, CYZ][I]",
  d2i=dict([(2, "ABC")] + [(k, "ABCI") for k in range(3, 10)]),
  distinct="",
  reorder=0,
  verbose=0)   

for (_, ans) in p.solve():
  print(f"{['Alan', 'Bob', 'Clive'][ans[0]]} with share {ans[1]} half-pennies")
```
  LikeLike
  - Jim Randell 12:49 pm on 21 February 2021 Permalink | Reply
    Here’s an alternative solution using the [[ SubstitutedExpression() ]] solver:
```
from enigma import (SubstitutedExpression, subsets, is_square, printf)

# find candidate (A, B, C) values
p = SubstitutedExpression(
  [ "A + B + C == 200", "(A + B) % 11 = 0", "(B + C) % 13 = 0", "(A + C) % 19 = 0" ],
  base=201,
  distinct=(),
  answer="(A, B, C)",
  template="",
)

# look at possible (A, B, C) values
for (_, vs) in p.solve(verbose=0):
  # the values for the eldest and youngest differ by a square number
  for ((i, x), (j, y)) in subsets(enumerate(vs), size=2):
    if is_square(abs(x - y)):
      # identify the middle son
      m = "ABC"[3 - i - j]
      printf("A={vs[0]} hp, B={vs[1]} hp, C={vs[2]} hp; middle={m}")
```
    LikeLike
- Hugh Casement 1:51 pm on 21 February 2021 Permalink | Reply
  
  Theoretically Alan and Clive could each have received 57 ha’pence and Bob 86.
  Zero is also a square number! However, I doubt that is the intended solution.
  
  LikeLike
  - Jim Randell 2:02 pm on 21 February 2021 Permalink | Reply
    @Hugh: Well spotted!
    
    In my programs, both 0 and None evaluate to false, so using the return value from [[ is_square() ]] as a boolean value will reject 0. (It also doesn’t consider 0 to be allowed as a multiple of 11, 13, 19).
    
    You can explicitly check [[ is_square(...) is not None ]], or just import [[ is_square_p() ]] instead which returns a boolean.
    
    And if you do that you do indeed get two solutions:
```
% python teaser23b.py
A=5 hp, B=105 hp, C=90 hp; middle = C
A=57 hp, B=86 hp, C=57 hp; middle = B
```
    The published solution is: “Clive, 3s 9d”.
    
    Perhaps the setter intended the shares to be three different values.
    
    LikeLike
- John Crabtree 6:58 pm on 22 February 2021 Permalink | Reply
  
  Working in 1/2d, then A + B + C = 200
  A + B = 11p, p ≤ 18
  B + C = 13q, q ≤ 15
  A + C = 19r, r ≤ 10
  Summing the three gives 400 = 11p + 13q + 19r
  Using r as a variable as it has the fewest possible values:
  B = 200 – 19r, p = 8 + 3r mod 13, q = 3 + 7r mod 11 which leads to
  A = 31 + 52r mod 143
  C = 112 + 110r mod 143
  It is then straightforward to manually generate a table of values for A, B and C for each r. r = 1, 2 and 4 give A+B+C = 343. r = 3 and r = 5 to 10 give A+B+C = 200 and include the two solutions noted by Jim.
  
  LikeLike
Jim Randell 4:51 pm on 19 February 2021 Permalink | Reply
Tags: by: Stephen Hogg ( 64 )
Teaser 3048: Nero Scrag from Carregnos
From The Sunday Times, 21st February 2021 [link] [link]

Our holiday rep, Nero, explained that in Carregnos an eight-digit total of car registrations results from combinations of three Greek capital letters after four numerals (e.g. 1234 ΩΘΦ), because some letters of the 24-letter alphabet and some numerals (including zero) are not permitted.

For his own “cherished” registration the number tetrad is the rank order of the letter triad within a list of all permitted letter triads ordered alphabetically. Furthermore, all permitted numeral tetrads can form such “cherished” registrations, but fewer than half of the permitted letter triads can.

Nero asked me to guess the numbers of permitted letters and numerals. He told me that I was right and wrong respectively, but then I deduced the permitted numerals.

List the permitted numerals in ascending order.

[teaser3048]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell, Tony Brooke-Taylor, Frits, and 1 other are discussing. Toggle Comments
- Jim Randell 5:29 pm on 19 February 2021 Permalink | Reply
  Nero Scrag is an anagram of Carregnos, which itself may be written as “car reg nos” = “car registration numbers”.
  
  The wording of the puzzle is a bit convoluted, but I think there is a unique solution.
  
  This Python program runs in 56ms.
  
  Run: [ @repl.it ]
```
from enigma import (irange, ndigits, group, unpack, printf)

# generate candidate solutions
# return (number-of-digits, number-of-letters, total-number-of-digit-tetrads, total-number-of-letter-triads)
def generate():
  # consider number of digits available (< 9)
  for nd in irange(1, 8):
    # number of digit tetrads
    td = nd**4

    # consider number of letters available (< 23)
    for ns in irange(1, 22):
      # number of letter triads
      ts = ns**3

      # total number of possible registrations
      t = td * ts
      # is 8 digits
      if not (ndigits(t) == 8): continue

      # all digit tetrads correspond to a letter triad
      # so remove impossible situations
      if 1111 * nd > ts: continue

      # fewer than half the letter triads correspond to number tetrads
      if not (ts > 2 * td): continue

      printf("[nd={nd} -> td={td}; ns={ns} -> ts={ts}; t={t}]")
      yield (nd, ns, td, ts)

# group candidate solutions by the number of letters (which the setter guessed right)
d = group(generate(), unpack(lambda nd, ns, td, ts: ns))

# look for a group with only two candidates
for (k, vs) in d.items():
  if len(vs) != 2: continue
  # look for candidates with only one set of digits
  for (nd, ns, td, ts) in vs:
    # are the digits forced to be 1..nd?
    if 1111 * (nd + 1) > ts:
      # output solution
      printf("digits = 1..{nd} [nd={nd} ns={ns}]")
```
  Solution: The digits are: 1, 2, 3, 4, 5, 6, 7.
  
  The setter guessed there were 20 letters and 6 digits.
  
  He was right about the number of letters, but wrong about the number of digits.
  
  The only other possibility with 20 letters is 7 digits, so that must be the correct number of digits.
  
  With 20 digits there are 20^3 = 8000 possible letter triads (which can be enumerated from 1 to 8000).
  
  The lowest valued set of 7 digits is 1..7, and the highest numeric tetrad in this case is 7777, which corresponds to an entry in the enumeration of letter triads.
  
  If not all of the digits from 1..7 are permissible, then the highest digit would be 8 or 9, and the highest numeric tetrad would be 8888 or 9999, but neither of these correspond to entries in the enumeration of letter triads. So these situations are not possible.
  
  So we know that the set of permissible digits must be 1..7.
  
  This means there are 2401 digit tetrads and 8000 letter triads.
  
  Every digit tetrad (from 1111 to 7777) corresponds to one of the letter triads, but any letter triad that has an index containing a 0, 8, or 9 does not have a corresponding digit tetrad. (Where we represent the indices with leading zeros to pad them to 4 digits, if necessary). There are 5599 of these, so less than half of the letter triads have a corresponding digit tetrad, as required.
  
  LikeLike
  - Frits 9:10 pm on 19 February 2021 Permalink | Reply
    
    Ah, I see you now have a different answer. I couldn’t understand your previous solution.
    This is a puzzle where I needed your code to understand the puzzle.
    
    LikeLike
    - Jim Randell 7:24 am on 20 February 2021 Permalink | Reply
      
      @Frits: The wording of the puzzle is a bit complicated, but I think it makes sense.
      
      In my original program I got the final check the wrong way round, but I have corrected that now.
      
      LikeLike
  - Jim Randell 8:14 am on 28 February 2021 Permalink | Reply
    
    Here is a more detailed explanation of the logic used in the program:
    
    Some digits (including 0) are not permitted, so there are fewer than 9 digits available.
    
    And some letters are not permitted, so there are fewer than 23 letters available.
    
    If there are nd digits available, then we can make nd^4 possible digit tetrads.
    
    And if there are ns letters (symbols) available, then we can make ns^3 possible letter triads.
    
    The total number of registrations that can be made is therefore: (nd^4) × (ns^3), and this must be an 8-digit number.
    
    Also the letter triads can be enumerated (in lexicographical order) from 1 to ns^3.
    
    And each digit tetrad provides a valid index into the list of enumerated letter triads.
    
    So if d is a permitted digit then the digit tetrad dddd must be an index into the list of letter triads.
    
    So: 1111 × d ≤ ns^3.
    
    And with nd possible digits, that exclude the digit 0, the maximum permitted digit must be at least nd.
    
    So we can skip situations where: 1111 × nd > ns^3, as there are no viable digit sets.
    
    We are also told that fewer than half the letter triads correspond to digit triads.
    
    So: (ns^3) > 2 × (nd^4)
    
    These restrictions limit the possible values of nd and ns.
    
    The setter makes guesses for these values, and gets ns right and nd wrong.
    
    But from this information he is able to deduce, not just the value of nd, but the actual set of permitted digits.
    
    So from his guess for ns, we know there must be 2 possibilities for nd. On being told the candidate he chose was wrong, the setter can deduce that the other candidate must be the correct one.
    
    So now he knows the values of both ns and nd. But he can go further and deduce the actual set of permitted digits.
    
    This means that there can only be one possible set of digits for the values of ns and nd.
    
    The set with the smallest valued digit tetrads will be {1..nd}, and we already know that the value (1111 × nd) indexes into the list of letter triads.
    
    And we want to exclude all other possible sets. A set that excludes just one of the digits 1..nd would have a maximum digit of (nd + 1), and in order for this to be excluded the maximum digit tetrad of (1111 × (nd + 1)) must be larger than the maximum index into the list of letter triads.
    
    i.e.: (1111 × (nd + 1)) > ns^3
    
    In that case only the set of digits {1..nd} forms a viable set, so this provides the answer.
    
    LikeLike
- Brian Gladman 10:44 pm on 19 February 2021 Permalink | Reply
  
  @Jim I have the same logic up to line 30 but I don’t see the rationale for only considering solutions with two candidates (line 36). But it does seem necessary to obtain a unique solution.
  
  LikeLike
  - Jim Randell 10:54 pm on 19 February 2021 Permalink | Reply
    
    @Brian: My reasoning was that when the setter guesses the number of permissible letters and digits, and gets the number of letters right, but the number of digits wrong, he is then able to deduce the correct number of digits. So for the number of letters guessed, there must be only two options for the number of digits. The setter went for the wrong one to begin with, but on being told he was wrong he was able to deduce the correct number, so there was only one other option remaining.
    
    LikeLike
    - Brian Gladman 11:37 pm on 19 February 2021 Permalink | Reply
      
      Thanks Jim. But it is logical for the setter to apply your line 40 logic before he is asked to guess and if he does this he only needs the first of the two answers to deduce the solution. So we have to assume he is acting illogically in order to deduce a unique solution, which seems a bit odd to me.
      
      LikeLike
      - Jim Randell 7:17 am on 20 February 2021 Permalink | Reply
        
        @Brian: But the setter doesn’t know he is going to be able to deduce the set of digits before he makes his guesses. Once he gets the answers however he knows how many letters there are (as he guessed that correctly), and as explained above there is only one candidate remaining for the number of digits, so he knows that too.
        
        He then realises that given those values for the number of digits and number of letters, there is only one possible set of digits that can work, so he can deduce what the digits are (not just how many of them there are).
        
        We aren’t told what guesses the setter made, but the fact that the scenario unrolled as described lets us work out what the setters guesses must have been, and so we can also determine what the set of digits must be, and hence answer the puzzle.
        
        LikeLike
        
        Brian Gladman 12:54 pm on 20 February 2021 Permalink | Reply
        
        Thanks Jim. My logic was originally the same as yours (up to your line 30) but I have now changed it to avoid the assumption (on your line 23) that the number of digits in use and the maximum digit in use are the same. We now arrive at the same answer in different ways.
        
        LikeLike
        
        Jim Randell 1:45 pm on 20 February 2021 Permalink | Reply
        
        @Brian: I don’t assume the maximum digit is the same as the number of digits, only it is at least this value (which it must be, as 0 is excluded).
        
        But I think in your method you also need to consider that the maximum digit could be 9.
        
        LikeLiked by 1 person
        
        Brian Gladman 5:09 pm on 20 February 2021 Permalink | Reply
        
        @Jim. Good point, changed now.
        
        LikeLike
        
        Tony Brooke-Taylor 9:39 am on 21 February 2021 Permalink | Reply
        
        Jim, doesn’t your line 40 forbid cases where the maximum digit (int(ts/1111)) is greater than the number of digits (ns)? I am sure we must apply that condition somewhere to get a unique answer, and it is the only way our subject could have inferred all the digits.
        
        I applied almost exactly the same logic as you but I did a bit of analysis first to reduce the ranges for the two main loops. We only need to explore the space defined by 10^7 <=T<10^8, where T=nd^4*ns^3. Reduces run-time by about half.
        
        LikeLike
        
        Jim Randell 9:54 am on 21 February 2021 Permalink | Reply
        
        @Tony: Yes. That line is there to ensure there is only one possible set of digits at that stage, because if there were more than one the setter would not have been able to deduce what the permissible digits are.
        
        And there is only one set of digits if the maximum digit is constrained to be the same as the number of digits (as 0 is excluded). So the set of digits is {1..nd}.
        
        LikeLike
- Frits 12:58 am on 21 February 2021 Permalink | Reply
  Under the assumption that “some letters” means “at least 2 letters”
```
from collections import defaultdict
from enigma import SubstitutedExpression, divc

# the alphametic puzzle
p = SubstitutedExpression(
  [
  #  N = number of permitted numerals
  # LE = number of permitted letters
  
  # the maximum possible car registration has at least 8 characters:
  # formula: no_numerals ** 4  *  no_letters ** 3 >= 10 ** 7 
  #
  # choose the highest number of permitted letters (twenty two)  
  # to calculate the lowest number of permitted numbers
  "N >= (divc(10 ** 7, 22 ** 3) ** 0.25)",
  "N < 9",
  
  "LE >= (divc(10 ** 7, N ** 4) ** (1 / 3))",
  "LE < 23",
  
  # consider the maximum 4-digits numbers (1111 * highest digit)
  # the smallest must not be greater than the number of letter triads
  "1111 * N <= LE ** 3",
  
  # fewer than half the letter triads correspond to number tetrads
  "LE ** 3 > 2 *( N ** 4)",
  ],
  answer="LE, N, LE ** 3",
  d2i=dict([(0, "N")] + [(k, "L") for k in range(3, 10)]),
  distinct="",
  verbose=0)   

# collect and sort solutions
sols = sorted(y for _, y in p.solve())

# group solutions by number of permitted letters
d = defaultdict(list)
for le, n, ntriads in sols:
  d[le].append([n, ntriads])
  
for k, v in d.items():
  # only with 2 options for the number of permitted numerals 
  # you can still make deductions
  if len(v) != 2: continue
  
  # "I deduced the permitted numerals"
  
  # you can only know the permitted numerals if they are 1...N
  # this must be the last entry in <v>
  
  # check that N+1 is not permitted as a numeral
  if 1111 * (v[1][0] + 1) > v[1][1]:  
    print(f"answer 1...{v[1][0]}")
```
  LikeLike
  - Tony Brooke-Taylor 9:43 am on 21 February 2021 Permalink | Reply
    
    Frits, your lines 15-19 are equivalent to the analysis I referred to in my comment to Jim. I also relaxed the assumption that ‘some’ meant ‘at least two’, and the solution still works.
    
    LikeLike
Jim Randell 9:48 am on 18 February 2021 Permalink | Reply
Tags: by: Graham Smithers ( 84 )
Teaser 2776: Winning months
From The Sunday Times, 6th December 2015 [link] [link]

I have won three Premium Bond prizes and noted the number of non-winning months between my first and second wins, and also the number between my second and third wins. Looking at the letters in the spelling of the months, I have also noted the difference between the numbers of letters in the months of my first and second wins, and also the difference between those of the months of my second and third wins. All four numbers noted were the same, and if you knew that number then it would be possible to work out the months of my wins.

What (in order of the wins) were those three months?

[teaser2776]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 9:48 am on 18 February 2021 Permalink | Reply
  The largest difference in number of letters is 6 (“May” to “September”), so we don’t need to worry about time spans longer than this.
  
  This Python program runs in 52ms.
  
  Run: [ @repl.it ]
```
from enigma import filter_unique, unpack, irange, join, printf

# month names (in English)
months = (
  'January', 'February', 'March', 'April', 'May', 'June',
  'July', 'August', 'September', 'October', 'November', 'December',
)

# month lengths
ls = set(len(x) for x in months)
M = max(ls) - min(ls)

# map (<n>, <month1>) -> <month2>
# where month1 and month2 are separated by n months
# and month2 length is different from month1 by n
d = dict()
for (m1, name) in enumerate(months):
  l1 = len(name)
  for n in irange(0, M):
    m2 = (m1 + n + 1) % 12
    if abs(l1 - len(months[m2])) == n:
      d[(n, m1)] = m2

# now look for elements (n, m1) -> m2 where (n, m2) -> m3
rs = list()
for ((n, m1), m2) in d.items():
  m3 = d.get((n, m2), None)
  if m3 is not None:
    ms = tuple(months[i] for i in (m1, m2, m3))
    rs.append((n, ms))
    printf("[n={n}: {ms}]", ms=join(ms, sep=' -> '))

# find unambiguous solutions by n
rs = filter_unique(rs, unpack(lambda n, ms: n)).unique

# output solutions
for (n, ms) in rs:
  printf("SOLUTION: n={n}, {ms}", ms=join(ms, sep=' -> '))
```
  Solution: The winning months are: February, July, December.
  
  This is the only set of months such that each adjacent pair has 4 months between them, and also differ by 4 letters.
  
  There are ambiguous solutions for values 1 and 5:
  
  1: August → October → December
  1: September → November → January
  
  5: May → November → May
  5: November → May → November
  
  LikeLike
Jim Randell 9:22 am on 16 February 2021 Permalink | Reply
Tags: by: B W M Young ( 10 )
Brain-Teaser 692: First-class post
From The Sunday Times, 20th October 1974 [link]

On Trafalgar Day each of the five Sea Lords will take over a post now occupied by one of the others. Each predicts what will happen; those whose predictions are right will get more senior posts, and those whose predictions are wrong will get more junior posts.

The most junior speaks first:

Fifth Sea Lord: “Two Sea Lords will make a direct exchange.”
Fourth Sea Lord: “The Third Sea Lord will become the Second Sea Lord.”
Third Seal Lord: “A man who makes a true prediction will take over my job.”

Of the First and Second Sea Lords each predicts the same future new post for himself.

Which post is that?

This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.

[teaser692]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
John Crabtree, Jim Randell, and Frits are discussing. Toggle Comments
- Jim Randell 9:23 am on 16 February 2021 Permalink | Reply
  If the First Sea Lord and the Second Sea Lord both predict taking on the same position, I am assuming that the position cannot be that of the First or Second Sea Lord, as then one of them would have made a prediction that was impossible to fulfil (because no-one keeps their position).
  
  This Python program runs in 53ms.
  
  Run: [ @repl.it ]
```
from enigma import subsets, peek, map2str, printf

# positions
pos = (1, 2, 3, 4, 5)

# check <n> makes statement <s> is valid in map <m>
check = lambda m, n, s: (m[n] < n) == bool(s)

# find an index that maps to x
find = lambda m, x: peek(k for (k, v) in m.items() if v == x)

# consider derangements
for s in subsets(pos, size=len, select="D"):
  m = dict(zip(pos, s))

  # check the statements:

  # 5: "two will make a direct exchange"
  if not check(m, 5, (any(m[v] == k for (k, v) in m.items()))): continue

  # 4: "3 -> 2"
  if not check(m, 4, (m[3] == 2)): continue

  # 3: "a man who makes a true prediction (so is promoted) will take
  # over my job (= 3)"
  if not check(m, 3, (find(m, 3) > 3)): continue

  # 1: "1 -> x", 2: "2 -> x"
  for x in pos:
    if x == 1 or x == 2: continue
    if not(check(m, 1, (m[1] == x)) and check(m, 2, (m[2] == x))): continue

    printf("x={x}; {m}", m=map2str(m, arr="->"))
```
  Solution: The First and Second Sea Lords both predicted they would take on the role of Third Sea Lord.
  
  There are two possible maps:
  
  1→4; 2→5; 3→2; 4→1; 5→3
  1→5; 2→4; 3→2; 4→3; 5→1
  
  In both scenarios the First and Second Sea Lords are demoted (so made false predictions), and the Third, Fourth and Fifth Sea Lords are promoted (and so made true predictions).
  
  LikeLike
- Frits 10:54 am on 19 February 2021 Permalink | Reply
```
from enigma import SubstitutedExpression

def twoswap(a, b):
  z = [tuple(sorted((x, y))) for (x, y) in zip(a, b)]
  return len(set(z)) < len(z)

# the alphametic puzzle
p = SubstitutedExpression(
  [
  # (1, 2, 3, 4, 5) --> (V, W, X, Y, Z) 
  
  "sorted([V, W, X, Y, Z]) == [1, 2, 3, 4, 5]",
  
  # 5: "two will make a direct exchange
  "twoswap([1, 2, 3, 4, 5], [V, W, X, Y, Z])",
  
  # 4: "3 -> 2"
  "(X == 2 and Y < 4) or (Y == 5 and X != 2)",
   
  # 3: "a man who makes a true prediction (so is promoted) will take
  # over my job (= 3)"
  "[V, W, X, Y, Z].index(3) > 2 if X < 3 else [V, W, X, Y, Z].index(3) < 3",
  ],
  digits=range(1, 6),
  answer="{3, 4, 5}.difference({V, W})",
  env=dict(twoswap=twoswap),
  # derangement
  # 1: "1 -> x", 2: "2 -> x",  x > 2
  # we only know both statements have to be false
  d2i={1 : "VW", 2 : "VW", 3 : "X", 4 : "Y", 5 : "Z"},
  distinct="VWXYZ",
  verbose=0)   

# print answers 
answs = set([list(y)[0] for _, y in p.solve()])

for ans in answs:
  print(f"post = {ans}")
```
  LikeLike
  - Frits 11:15 am on 19 February 2021 Permalink | Reply
    
    @Jim, do you agree with V > 2 and W > 2 for 1: “1 -> x”, 2: “2 -> x”?
    We only know both statements to be false.
    
    LikeLike
    - Jim Randell 11:39 am on 19 February 2021 Permalink | Reply
      
      @Frits: I don’t see how to determine the required answer from the output of your program.
      
      LikeLike
- John Crabtree 4:37 pm on 19 February 2021 Permalink | Reply
  
  Here are a couple of ways to tackle it manually.
  The 5th SL must be correct. There are three cases to consider:
  3rd wrong, and so the 4th is wrong: 4 -> 5, 3 -> 4, 1/2 -> 3 with no possible exchange
  3rd right, 4th wrong: 3 -> 1, 4 -> 5, 5 -> 3, with no possible exchange
  3rd right, 4th right: 3 -> 2, 4/5 -> 3, 2 -> 4/5 (to allow an exchange), 5/4 -> 1, 1 -> 5/4
  
  1st and 2nd become 4th and 5th or vice versa. Assuming that a SL could not predict his current position, the 1st and 2nd SLs predicted that they would be 3rd Sea Lord.
  
  Using Boolean algebra, where 12 means 1 moves to 2 is true,
  5th SL: the statement is true
  4th SL: (41+43).32 + 45.(31+34) = 1
  3rd SL: (31+32).(43+53) + (34+35).(13+23) = 1
  Multiplying the two and removing impossible terms gives:
  41.32.53 + 43.32 + 45.31.53 + 45.34.(13+23) = 1
  These are the same four possibilities shown in the first solution. The last two do not allow an exchange. From the 5th SL:
  14.41.32.53 + 15.51.43.32 = 1, ie
  14.41.32.53.25 + 15.51.43.32.24 = 1, with the rest as before.
  
  LikeLike

Jim Randell 9:16 am on 14 February 2021 Permalink | Reply
Tags: by: C. W. Mitford

Brain-Teaser 21: [Crossnumber]

From The Sunday Times, 13th August 1961 [link]

Across:

1a. Square of a multiple of 11.
5a. A fourth power.
8a. A multiple of 2d.
9a. A cube reversed.
11a. If added to 4d it gives a square.
12a. 3 times a prime number.
14a. A multiple of 11.
16a. A prime number.
17a. A cube, which is also the sum of three cubes.
18a. An even number.
20a. A multiple of 12.
21a. A prime number.
22a. The square of a palindromic number.

Down:

1d. The product of two consecutive numbers (neither a prime).
2d. See 8a.
3d. A cube.
4d. See 11a.
6d. The sum of the digits of 3d.
7d. The square of (6d reversed).
10d. The product of two consecutive odd numbers.
13d. The product of two consecutive even numbers.
15d. A cube.
16d. A square.
19d. An even multiple of (18a + 21a).

This puzzle was originally published with no title.

[teaser21]

Jim Randell 9:18 am on 14 February 2021 Permalink | Reply

I used the [[ SubstitutedExpression ]] solver from the enigma.py library to solve this puzzle.

The following run file executes in 333ms.

(Using the standard Python interpreter we need to provide the additional [[ --denest ]] parameter to work around the limit on statically nested blocks. This is not required if using the PyPy interpreter).

Run: [ @replit ]

#! python3 -m enigma -rr

#  A B C D E F G
#  H I J K L M N
#  P # Q R S # T
#  U V W # X Y Z
#  a b c d e f g
#  h i # # # j k
#  m n p q r s t

SubstitutedExpression

--distinct=""
--reorder=0

# 1a. = ABCD "Square of a multiple of 11"
"is_square({ABCD}) % 11 = 0"

# 11a. = QR "If added to 4d. it gives a square"
# 4d. = DKR "See 11 across"
"is_square({DKR} + {QR})"

# 8a. = HIJ "A multiple of 2d."
# 2d. = BI "See 8 across"
"{HIJ} % {BI} = 0"

# 3d. = CJQWc "A cube"
"is_cube({CJQWc})"

# 6d. = FM "The sum of the digits of 3d."
"dsum({CJQWc}) = {FM}"

# 7d. = GNTZ "The square of (6d. reversed)"
"{MF} ** 2 = {GNTZ}"

# 5a. = EFG "A fourth power"
"is_power({EFG}, 4)"

# 12a. = UVW "Three times a prime number"
"is_prime(div({UVW}, 3))"

# 1d. = AHPU "The product of two consecutive numbers (neither a prime)"
--code="
def check_1d(n):
  k = isqrt(n)
  return n == k * (k + 1) and not(is_prime(k) or is_prime(k + 1))
"
"check_1d({AHPU})"

# 13d. = Vbin "The product of 2 consecutive even numbers"
--code="
def check_13d(n):
  k = isqrt(div(n, 4))
  return n == 4 * k * (k + 1)
"
"check_13d({Vbin})"

# 16a. = ab "A prime number"
"is_prime({ab})"

# 20a. = hi "A multiple of 12"
"{hi} % 12 = 0"

# 16d. = ahm "A square"
"is_square({ahm})"

# 17a. = cde "A cube, which is also the sum of three cubes"
--code="
def check_17a(n, k=3):
  if k == 1:
    return is_cube(n)
  else:
    for x in powers(1, inf, 3):
      if k * x > n: break
      if check_17a(n - x, k - 1): return True
    return False
"
"is_cube({cde}) and check_17a({cde})"

# 10d. = LSXe "The product of 2 consecutive odd numbers"
"is_square(div({LSXe} + 1, 4))"

# 14a. = XYZ "A multiple of 11"
"{XYZ} % 11 = 0"
# 9a. = KLMN "A cube reversed"
"is_cube({NMLK})"

# 21a. = jk "A prime number"
"is_prime({jk})"

# 15d. = Yfjs "A cube"
"is_cube({Yfjs})"

# 19d. = gkt "An even multiple of (18a. + 21a.)"
"div({gkt}, {fg} + {jk}) % 2 = 0"

# 18a. = fg "An even number"
"{fg} % 2 = 0"

# 22a. = npqrs "The square of a palindrome"
"is_palindrome(nsplit(is_square({npqrs})))"

# [optional]
--template="{ABCD} {EFG} | {HIJ} {KLMN} | {P} {QR} {S} {T} | {UVW} {XYZ} | {ab} {cde} {fg} | {hi} {jk} | {m} {npqrs} {t}"
--solution=""
--header=""

Solution: The completed grid looks like this:

LikeLike

Jim Randell 4:56 pm on 12 February 2021 Permalink | Reply
Tags: by: Howard Williams ( 44 )

Teaser 3047: Some permutations

From The Sunday Times, 14th February 2021 [link] [link]

I gave Robbie three different, non-zero digits and asked him to add up all the different three-digit permutations he could make from them. As a check for him, I said that there should be three 3’s in his total. I then added two more [non-zero] digits to the [original three digits] to make [a set of] five digits, all being different, and asked Robbie’s mother to add up all the possible five-digit permutations of these digits. Again, as a check, I told her that the total should include five 6’s.

Given the above, the product of the five digits was as small as possible.

What, in ascending order, are the five digits?

I have changed the text of this puzzle slightly to make it clearer.

[teaser3047]

Jim Randell 5:10 pm on 12 February 2021 Permalink | Reply
(See also: Teaser 2863).

This Python program runs in 64ms.

Run: [ @repl.it ]
```
from enigma import irange, subsets, nconcat, nsplit, diff, multiply, group, printf

# total all permutations of a set of distinct digits
psum = lambda ds: sum(nconcat(*s) for s in subsets(ds, size=len, select="P"))

# count occurrences of digit d in number n
dcount = lambda n, d: nsplit(n).count(d)

# generate solutions
def solve():
  # permissible digits
  digits = irange(1, 9)

  # choose the initial set of 3 digits
  for ds3 in subsets(digits, size=3):
    t3 = psum(ds3)
    # there should be three 3 digits in the total
    if not(dcount(t3, 3) == 3): continue

    # now add 2 more digits to the mix
    for ds in subsets(diff(digits, ds3), size=2):
      ds5 = ds3 + ds
      t5 = psum(ds5)
      # there should be five 6 digits in the total
      if not(dcount(t5, 6) == 5): continue

      printf("[{ds3} -> {t3}; {ds5} -> {t5}]")
      yield ds5

# group solutions by product
d = group(solve(), by=multiply)

# output solutions
if d:
  k = min(d.keys())
  for ds5 in d[k]:
    printf("{ds3} + {ds2}; product = {k}", ds3=ds5[:3], ds2=ds5[3:])
```
Solution: The five digits are: 1, 2, 5, 8, 9.

There are two scenarios with a minimal product of 720:

(1) Robbie was given: 1, 5, 9; Additional digits: 2, 8.
(2) Robbie was given: 2, 5, 8; Additional digits: 1, 9.

The sum of all 3-digit permutations is 3330 (= 222 × 15).

The sum of all 5-digit permutations is 6666600 = (266664 × 25).

In total there are 16 candidate solutions, each with the same sums for the 3-digit and 5-digit permutations.

In general, if we have a set of k different digits, then they can be rearranged in factorial(k) different ways, to form different numbers.

And when these numbers are summed, each digit will appear factorial(k) / k = factorial(k − 1) times in each column.

So we can calculate the total of all permutations without having to generate them all:
```
from enigma import factorial, repdigit

def psum(ds):
  k = len(ds)
  return factorial(k - 1) * repdigit(k) * sum(ds)
```
In particular, for 3-digit numbers this simplifies to [[ 222 * sum(ds) ]] and for 5-digit numbers it simplifies to [[ 266664 * sum(ds) ]].

The program above can be adapted using this analysis to give a solution with a run time of 51ms:
```
from enigma import irange, subsets, nsplit, diff, multiply, Accumulator, inf, factorial, repdigit, printf

# return multiplier for total sum of all permutations of a set of distinct digits
psum = lambda k: factorial(k - 1) * repdigit(k)
psum3 = psum(3)
psum5 = psum(5)

# count occurrences of digit d in number n
dcount = lambda n, d: nsplit(n).count(d)

# collect minimal products
r = Accumulator(fn=min, value=inf, collect=1)

# choose the set of 5 digits
for ds5 in subsets(irange(1, 9), size=5):
  p = multiply(ds5)
  if p > r.value: continue

  # there should be five 6 digits in the total
  t5 = psum5 * sum(ds5)
  if not(dcount(t5, 6) == 5): continue

  # choose a subset of 3 digits
  for ds3 in subsets(ds5, size=3):
    t3 = psum3 * sum(ds3)
    # there should be three 3 digits in the total
    if not(dcount(t3, 3) == 3): continue

    # record the initial set of 3 digits, and the additional 2 digits
    r.accumulate_data(p, (ds3, diff(ds5, ds3)))

# output solutions
if r.count:
  for (ds3, ds2) in r.data:
    printf("{ds3} + {ds2}; product = {r.value}")
```
LikeLike
- Tony Brooke-Taylor 3:11 pm on 13 February 2021 Permalink | Reply
  
  I think it is possible to simplify the problem to a point where the solution can be found manually. I admit I only spotted the simplifications once I had written an algorithm similar to yours Jim.
  
  In the 3-digit problem we can work out manually what the total must be: there is only one multiple of 222 that has three 3’s in it. Eight sets of three digits sum to the correct cofactor, of which four are symmetrical around the value 5.
  
  In the 5-digit problem we can also work out what the total must be: there is only one multiple of 266664 that has five 6’s in it, and I believe this is more obvious if we look at multiples of 11111. Thus we have a unique cofactor in this problem too, and the sum of the extra two digits must be the difference between the two cofactors. Only four pairs of digits make up this sum.
  
  If we combine the four pairs with the eight trios and deduplicate, we get ten possible sets of 5, of which six are symmetrical around the value 5.
  
  By trigonometry, the solution with the minimum product has the greatest distances between the central number and the others. My leap of faith is that we could also have applied this at the 3-digit stage to reduce the number of trios we needed to test.
  
  LikeLike
  - Jim Randell 12:07 pm on 17 February 2021 Permalink | Reply
    @Tony: Once we’ve got the 8 pairs of triples that sum to 15, and we are extending them with a pair that sums to 10 (= (1,9) (2,8) (3, 7) (4,6)), then we only need to consider the first viable pair, as later ones will give a larger product.
    
    So we can exhaustively check the solution space by calculating only 7 products.
    
    Here’s some code that uses this analysis:
```
from enigma import irange, Accumulator, printf

# collect minimal product
r = Accumulator(fn=min, collect=1)

# look for sets of 3 digits (a, b, c) that sum to 15
for a in irange(1, 4):
  for b in irange(a + 1, 6):
    c = 15 - (a + b)
    if not(b < c < 10): continue

    # and now add (d, e) that sum to 10
    for d in irange(1, 4):
      e = 10 - d
      if len({a, b, c, d, e}) != 5: continue

      # collect minimal product
      r.accumulate_data(a * b * c * d * e, ((a, b, c), (d, e)))
      break # only need to check the first viable (d, e) pair

# output solutions
if r.count:
  for (ds3, ds2) in r.data:
    printf("{ds3} + {ds2}; product = {r.value}")
```
    LikeLike
- Frits 10:31 am on 15 February 2021 Permalink | Reply
  @Jim,
  
  If you replace line 23 “t5 = psum(ds5) ” with
```
t5 = 0
for v, w, x, y, z in permutations(ds5):
  t5 += v * 10000 + w * 1000 + x * 100 + y * 10 + z
```
  your code is approx. 4.5 times faster (with Python 3.9.0).
  
  Maybe nconcat is not efficient if called multiple times?
  Subsets only seems to have minor overhead.
  
  LikeLike
  - Jim Randell 12:40 pm on 15 February 2021 Permalink | Reply
    
    @Frits: In a program that runs pretty much instantaneously I am less concerned about coding for execution speed as I am that the program itself should be concise, clear and easy to modify (and, above all, correct).
    
    So using a general utility function like [[ nconcat() ]] makes it clear that I am turning a sequence of digits into a number, even if it is not the fastest way to achieve this.
    
    Although with a bit of analysis we find that we don’t have to construct numbers corresponding to all the permutations of the digits in order to arrive at the sum (and gives a general principle for attacking similar problems), which lets us write a program that runs even faster.
    
    But that is not to say I’m not at all interested in execution speed. I’ll have a look at improving [[ nconcat() ]], and another advantage of using utility functions is that if an improvement is made, every program that uses them gets the benefit.
    
    LikeLike

Frits 11:23 am on 13 February 2021 Permalink | Reply

Basic version, not really optimized for speed.

from itertools import permutations, combinations

sol = set()
for a, b, c in combinations(range(1, 10), 3):
  t1 = 0
  for x, y, z in permutations([a, b, c]):
    t1 += x * 100 + y * 10 + z
 
  # there should be three 3's in the total
  if str(t1).count("3") == 3:
    for d in [q for q in range(1, 9) if q not in {a, b, c}]:
      for e in [q for q in range(d + 1, 10) if q not in {a, b, c}]:
        t2 = 0
        for v, w, x, y, z in permutations([a, b, c, d, e]):
          t2 += v * 10000 + w * 1000 + x * 100 + y * 10 + z
        
        # there should be five 6's in the total
        if str(t2).count("6") == 5:
          # put product up front so we can use if for sorting
          sol.add(tuple([a * b * c * d * e] + sorted([a, b, c, d, e])))
  
if len(sol):  
  print(f"answer = {sorted(sol)[0][1:]}")

LikeLike

Frits 2:07 pm on 18 February 2021 Permalink | Reply

Partly based on Tony’s comments.

from math import prod

# Suppose a < b < c < d < e and (a + b + c + d + e) is a constant
#
# a * b * c * d * e is minimal 
# if sum of distances with respect to c is maximal.
# 
# Proof:
# 
# sum of distances = (c - a) + (c - b) + (d - c) + (e - c) = d + e - a - b
# 
# Suppose we allow d or e to decrease with one and a or b to increase with 
# one, so the sum stays the same. Say d' = d - 1 and b' = b + 1
# 
# b' * d' = (b + 1) * (d - 1) = b * d + (d - b) - 1
# as c is between b and d we can say d - b > 1, thus d' * b' > d * b
# so new product a * b' * c * d' * e  >  old product a * b * c * d * e

# decompose number <t> into <k> different numbers from sequence <ns> 
# so that  sum(<k> numbers) equals <t>
# the result is already sorted on product !!
def decompose(t, k, ns, s=[]):
  if k == 1:
    if t in ns:
      yield s + [t]
  else:
    for (i, n) in enumerate(ns):
      if not(n < t): break
      yield from decompose(t - n, k - 1, ns[i + 1:], s + [n])

digits = [1, 2, 3, 4, 5, 6, 7, 8, 9]

# sum permutations of 3 different digits is 222 * sum(digits)
# last digit of sum can never be a 3 
# so first 3 digits of sum must be all 3's
s3 = 3340 // 222                   # sum of 3 digits
if (s3 * 222) // 10 != 333: 
  exit()                           # no solution

# sum permutations of 5 different digits is 266664 * sum(digits)
sum5 = [x for x in range(s3 + 3, min(s3 + 18, 36)) 
        if str(266664 * x).count("6") == 5] 
        
sol = []        

for s5 in sum5:
  # we look for 5 digits a, b, c, d, e which sum to <s5>
  # and where three of them sum to <s3>
  # (a * b * c * d * e must be minimal)

  # choose <a> as low as possible and <e> as high as possible
  a = max(1, s5 - 30)
  e = min(9, s5 - 10)
  # d - b must be maximal
  b = max(2, s5 - 25 - a + 1)
  d = min(8, max(4, s5 - 15))
  c = s5 - (a + b + d + e)
  
  # check optimal solution 
  if len(list(decompose(s3, 3, [a, b, c, d, e]))) > 0:
    sol.append([prod([a, b, c, d, e]), (a, b, c, d, e)])
  else:
    for abcde in decompose(s5, 5, digits): 
      if len(list(decompose(s3, 3, abcde))) > 0:
        sol.append([prod(abcde), abcde])
        break  # decompose returns entries sorted on product!
  
if len(sol) > 0:  
  sol.sort()   # sort on product
  print("answer = ", sol[0][1])

LikeLike

Jim Randell 9:01 am on 11 February 2021 Permalink | Reply
Tags: by: Eric Emmet ( 10 )

Brain-Teaser 691: That’s torn it …

From The Sunday Times, 13th October 1974 [link]

It was typical of Uncle Bungle that he should have torn up the sheet of paper which gave particulars of the numbers of matches played, won, lost, drawn, etc. of four local football teams who were eventually going to play each other once. The only piece left was as shown (as usual there are 2 points for a win and 1 for a draw):

It will not surprise those who know my Uncle to hear that one of the figures was wrong, but fortunately it was only one out (i.e. one more or less than the correct figure).

Each side had played at least one game, and not more than seven goals were scored in any match.

Calling the teams A, B, C and D (in that order), find the score in each match.

This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.

[teaser691]

Jim Randell 9:02 am on 11 February 2021 Permalink | Reply

(See also: Puzzle 81).

This Python program uses the [[ Football ]] helper class from the enigma.py library. It runs in 198ms.

from enigma import (Football, subsets, cproduct, printf)

# scoring system
football = Football(points=dict(w=2, d=1))

# possible scores in the matches (no match has more than 7 goals scored)
scores = {
  'w': [
    (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (7, 0),
    (2, 1), (3, 1), (4, 1), (5, 1), (6, 1),
    (3, 2), (4, 2), (5, 2),
    (4, 3),
  ],
  'd': [(0, 0), (1, 1), (2, 2), (3, 3)],
  'x': [None],
}
scores['l'] = list((b, a) for (a, b) in scores['w'])

# choose outcomes for each of the matches
for (AB, AC, AD, BC, BD, CD) in subsets('wdlx', size=6, select="M"):
  # calculate the points
  A = football.table([AB, AC, AD], [0, 0, 0])
  B = football.table([AB, BC, BD], [1, 0, 0])
  C = football.table([AC, BC, CD], [1, 1, 0])
  D = football.table([AD, BD, CD], [1, 1, 1])

  # each team has played at least one game
  if not all(x.played > 0 for x in [A, B, C, D]): continue

  # count the discrepancies in the points
  dp = abs(A.points - 3) + abs(B.points - 5) + C.points
  if dp > 1: continue

  # choose the scores in C's games
  for (sAC, sBC, sCD) in cproduct([scores[AC], scores[BC], scores[CD]]):
    (fC, aC) = football.goals([sAC, sBC, sCD], [1, 1, 0])
    dC = aC
    if dp + dC > 1: continue

    # choose the scores in A's games
    for (sAB, sAD) in cproduct([scores[AB], scores[AD]]):
      (fA, aA) = football.goals([sAB, sAC, sAD], [0, 0, 0])
      dA = abs(aA - 5)
      if dp + dA + dC > 1: continue

      # remaining game
      for sBD in scores[BD]:
        (fB, aB) = football.goals([sAB, sBC, sBD], [1, 0, 0])
        dB = abs(aB - 6)
        if dp + dA + dB + dC > 1: continue

        (fD, aD) = football.goals([sAD, sBD, sCD], [1, 1, 1])
        dD = abs(aD - 7)
        if dp + dA + dB + dC + dD != 1: continue

        printf("A=({aA} {A.points}) B=({aB} {B.points}) C=({aC} {C.points}) D=({aD} {D.points}) / \\")
        printf("AB={AB}:{sAB} AC={AC}:{sAC} AD={AD}:{sAD} BC={BC}:{sBC} BD={BD}:{sBD} CD={CD}:{sCD}")

Solution: The scores in the played matches are: A vs B = 3-3; A vs D = 3-2; B vs C = 1-0; B vs D = 4-3.

The A vs C and C vs D matches are not yet played.

The incorrect value is C’s “goals against”. It should be 1, not 0.

It is clear that the incorrect value must be one of C’s, as if they have played at least one game they cannot have both 0 points and 0 goals against.

LikeLike

Jim Randell 8:50 am on 9 February 2021 Permalink | Reply
Tags: by: Angela Newing ( 39 )

Teaser 2775: Strictly not

From The Sunday Times, 29th November 2015 [link] [link]

Four celebrities entered a dance competition. Five judges each shared out their eight marks among the four dancers, with each getting a non-zero whole number. Each judge split the eight marks in a different way and then allocated them as follows. Amanda’s marks to Lana and Natasha added to the same total as Barry’s marks to Madge and Paula. Barry gave more marks to Madge than to any other dancer, Charles gave more to Paula than to any other, and Doris gave more to Natasha than to any other. Lana scored more from Edna than from Amanda. All dancers had the same total so the head judge’s scores were used, giving a winner and runner-up.

Who was the head judge, who was the winner and who was the runner-up?

[teaser2775]

Jim Randell 8:51 am on 9 February 2021 Permalink | Reply

Each of the 5 judges gives out 8 points, so 40 points are awarded in total. And there are 4 dancers, and they all receive the same total number of points. So each dancer receives 10 points in total.

Each judge awards a non-zero number of points to each dancer, so the points awarded are between 1 and 5.

I used the [[ SubstitutedExpression ]] solver from the enigma.py library to find possible collections of points awarded by the judges, and the scores are then examined to determine which judges scores identify a clear winner and runner up.

The following run file executes in 80ms.

Run: [ @replit ]

from enigma import (SubstitutedExpression, irange, seq_all_different, ordered, printf)

# consider the points given:
#
#             Lana
#             |  Madge
#             |  |  Natasha
#             |  |  |  Paula
#   Amanda:   A  B  C  D = 8
#   Barry:    E  F  G  H = 8
#   Charles:  I  J  K  L = 8
#   Doris:    M  N  P  Q = 8
#   Edna:     R  S  T  U = 8
#             =  =  =  =
#            10 10 10 10

# check the splits are all different
check_splits = lambda *xs: seq_all_different(ordered(*x) for x in xs)

# construct the alphametic problem
p = SubstitutedExpression([
    # each judge gave out 8 points
    "A + B + C + D = 8",
    "E + F + G + H = 8",
    "I + J + K + L = 8",
    "M + N + P + Q = 8",
    "R + S + T + U = 8",

    # points were split in a different way by each judge
    "check_splits((A, B, C, D), (E, F, G, H), (I, J, K, L), (N, M, P, Q), (R, S, T, U))",

    # "A's marks to L and N had the same sum as B's marks to M and P"
    "A + C == F + H",

    # "B gave more marks to M than to any other"
    "max(E, G, H) < F",

    # "C gave more to P than to any other"
    "max(I, J, K) < L",

    # "D gave more to N than to any other"
    "max(M, N, Q) < P",

    # "L scored more from E than from A"
    "R > A",

    # all dancers had the same total (= 10)
    "A + E + I + M + R = 10",
    "B + F + J + N + S = 10",
    "C + G + K + P + T = 10",
    "D + H + L + Q + U = 10",
  ],
  distinct=(),
  digits=irange(1, 5), # points are in the range 1-5
  env=dict(check_splits=check_splits),
  # answer is the scores from each judge
  answer="((A, B, C, D), (E, F, G, H), (I, J, K, L), (M, N, P, Q), (R, S, T, U))",
  denest=-1, # [CPython] work around statically nested block limit
)

# solve the puzzle, and output solutions
(judges, dancers) = ("ABCDE", "LMNP")
for (_, scores) in p.solve(verbose=0):
  # look for scores that differentiate 1st and 2nd place
  for (j, ss) in zip(judges, scores):
    printf("{j}: {ss}\\")
    (p1, p2, p3, p4) = sorted(ss, reverse=1)
    if p1 > p2 > p3:
      (d1, d2) = (dancers[ss.index(p)] for p in (p1, p2))
      printf(" -> head judge; 1st = {d1}, 2nd = {d2}\\")
    printf()
  printf()

Solution: Doris was the head judge. Natasha was the winner. Lana was the runner-up.

The scores were allocated as follows (L, M, N, P):

A: (2, 2, 2, 2)
B: (2, 3, 2, 1)
C: (1, 1, 1, 5)
D: (2, 1, 4, 1)
E: (3, 3, 1, 1)

There are only 5 different (unordered) ways to divide a score of 8 between 4 dancers, and only one of them (4, 2, 1, 1) gives a clear 1st and 2nd place.

LikeLike

Frits 9:26 pm on 9 February 2021 Permalink | Reply

from collections import defaultdict
 
# consider the points given:
#
#             Lana
#             |  Madge
#             |  |  Natasha
#             |  |  |  Paula
#   Amanda:   A  B  C  D = 8
#   Barry:    E  F  G  H = 8
#   Charles:  I  J  K  L = 8
#   Doris:    M  N  P  Q = 8
#   Edna:     R  S  T  U = 8
#             =  =  =  =
#            10 10 10 10

M = 5  # number of rows
N = 4  # number of columns 

# decompose number <t> into <k> positive numbers from <ns>
# so that sum(<k> numbers) equals <t>
def decompose(t, k, ns, s=[]):
  if k == 1:
    if t in ns:
      yield s + [t]
  else:
    for (i, n) in enumerate(ns):
      if not(n + k - 2 < t): break
      #yield from decompose(t - n, k - 1, ns[i:], s + [n])
      yield from decompose(t - n, k - 1, ns, s + [n])   
      
# combine rows of dictionary <d>
# so that every column total equals <t>
def combineRows(t, k, d, s=[]):
  if k == 1:
    remaining = [t - sum(x) for x in zip(*s)]
    if remaining in d[0]:
      yield s + [remaining]
  else:
    for row in d[k - 1]:
      # for each column ...
      for j in range(N):
        # .. sum already processed numbers
        already = sum([0 if len(s) == 0 else x[j] for x in s]) 
        # and check if there is room for remaining rows
        if not(row[j] + already  + k - 2 < t): 
          already = -1  # skip this row
          break
      if already > -1:
        yield from combineRows(t, k - 1, d, s + [row])         


types = []
d_rows = defaultdict(list)

# create dictionary of possible rows for each type of row
# the points awarded are between 1 and 5
for x in decompose(8, N, range(1, 6)): 
  sortx = sorted(x) 
  if sortx in types:
    type = types.index(sortx)
  else:
    type = len(types)
    types.append(x)
  # append possible row  
  d_rows[type] += [x]
  

# combine rows so that column total always equals 10  
for rows in combineRows(10, M, d_rows): 
  testB, testC, testD = -1, -1, -1
  
  # validate rows
  for i, r in enumerate(rows):
    sr = sorted(r)
    # check if maximum value is unique
    if sr[-1] > sr[-2]:
      
      if sr[-1] == r[1]:    # testB : "max(E, G, H) < F",
        testB = i  
      elif sr[-1] == r[3]:  # testC : "max(I, J, K) < L",
        testC = i
      elif sr[-1] == r[2]:  # testD : "max(M, N, Q) < P",
        testD = i
  
  if -1 in {testB, testC, testD}: continue
  
  # get the other rows
  ix_oth = [x for x in range(M) if x not in {testB, testC, testD}]
  
  # "R > A"
  if rows[ix_oth[0]][0] < rows[ix_oth[1]][0]:
    testA = ix_oth[0]; testE = ix_oth[1]
  elif rows[ix_oth[0]][0] > rows[ix_oth[1]][0]:
    testE = ix_oth[0]; testA = ix_oth[1]
  else:
    continue
  
  # "A + C == F + H"
  if rows[testA][0] + rows[testA][2] != rows[testB][1] + rows[testB][3]:
    continue
  
  # the head judge's scores were used, giving a winner and runner-up
  judges, dancers = "ABCDE", "LMNP"
  for i, r in enumerate(rows):
    sr = sorted(r)
    if sr[1] < sr[2] < sr[3]:
      print(f"head judge: {judges[i]} ")
      print(f"winner    : {dancers[r.index(sr[3])]}")
      print(f"runner up : {dancers[r.index(sr[2])]}")
      print()
     
      for r in rows:
        print(r)

LikeLike

Jim Randell 9:26 am on 7 February 2021 Permalink | Reply
Tags: by: Ptolemaeus ( 5 )
Brain-Teaser 20: The kite
From The Sunday Times, 6th August 1961 [link]

Some problems that look simple enough at first can prove to be remarkably tricky. Consider, for instance, the kite pictured above. The shaded areas are squares of equal size, the sides of each square being 15 inches. The width of the kite from A to B is exactly 42 inches.

What is the length of the kite from C to D?

[teaser20]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
John Crabtree and Jim Randell are discussing. Toggle Comments
- Jim Randell 9:29 am on 7 February 2021 Permalink | Reply
  
  The figure is a right kite [ @wikipedia ], so is composed of 2 identical right-angled triangles joined along their common hypotenuse CD (which is the length we wish to determine).
  
  Writing: AC = BC = a, and AD = BD = b, then the value we wish to determine, CD, is:
  
  CD = √(a² + b²)
  
  We are told the other diagonal, AB, has length 42, hence:
  
  42 = 2ab / √(a² + b²)
  21√(a² + b²) = ab
  
  And the sides of the squares that run from the centre to the edges of the kite are radii of the incircle, so:
  
  15 = ab / (a + b)
  
  Writing: x = ab, y = a + b, we get:
  
  15 = x / y
  x = 15y
  x² = 225y²
  
  Also:
  
  a² + b² = (a + b)² − 2ab = y² − 2x
  
  So:
  
  441(y² − 2x) = x²
  441(y² − 30y) = 225y²
  216y² = 13230y
  4y = 245
  y = 245 / 4
  x = 3675 / 4
  
  So the value of CD is:
  
  CD = √(a² + b²)
  = √(y² − 2x)
  = √(30625 / 16)
  = 175 / 4
  
  Solution: CD = 43.75 inches.
  
  And the lengths of the sides of the kite are 26.25 in and 35 in.
  
  LikeLike
- John Crabtree 10:22 pm on 8 February 2021 Permalink | Reply
  
  Let the mid-point of AB be F, and the point where the squares meet be G
  By Pythagoras, FG = √(2 * 225 – 441) = 3
  Let z be the angle formed by GAF.
  Tan(z) = t = 3 / 21 = 1 / 7
  CD = 21 [tan(45 + z) + tan(45 – z)] = 21 [(1+t)/(1-t) + (1-t)/(1+t))
  = 21 [4/3 + 3/4] = 21 * 25/12 = 43.75 inches.
  AC = 21 * 5/4 = 26.25 in. AD = 21 * 5/3 = 35 in.
  
  LikeLike

Jim Randell 4:52 pm on 5 February 2021 Permalink | Reply
Tags: by: Danny Roth ( 87 )

Teaser 3046: Square phone numbers

From The Sunday Times, 7th February 2021 [link] [link]

George and Martha run a business in which there are 22 departments. Each department has a perfect-square three-digit extension number, i.e., everything from 100 (10²) to 961 (31²), and all five of their daughters are employees in separate departments.

Andrea, Bertha, Caroline, Dorothy and Elizabeth have extensions in numerical order, with Andrea having the lowest number and Elizabeth the highest. George commented that, if you look at those of Andrea, Bertha and Dorothy, all nine positive digits appear once. Martha added that the total of the five extensions was also a perfect square.

What is Caroline’s extension?

[teaser3046]

Jim Randell 5:03 pm on 5 February 2021 Permalink | Reply

A simple Python program finds the solution in 67ms.

from enigma import (powers, subsets, concat, is_square, printf)

# possible square numbers
squares = powers(10, 31, 2)

# choose 5 of the squares (in order)
for (A, B, C, D, E) in subsets(squares, size=5):

  # the sum of the numbers is also a square
  if not is_square(A + B + C + D + E): continue

  # A, B, D use the digits 1-9
  ds = concat(A, B, D)
  if '0' in ds or len(set(ds)) != 9: continue

  # output solution
  printf("A={A} B={B} C={C} D={D} E={E}")

Solution: Caroline’s extension is 729.

Manually, you can write out the squares, and then working through the possible candidates for A, B, D, the solution is discovered quite quickly.

LikeLike

GeoffR 7:51 pm on 5 February 2021 Permalink | Reply


% A Solution in MiniZinc
include "globals.mzn";
 
% Andrea, Bertha, Caroline, Dorothy and Elizabeth's numbers
var 100..961:A; var 100..961:B; var 100..961:C;
var 100..961:D; var 100..961:E;

constraint all_different([A, B, C, D, E]);
constraint A < B /\ B < C /\ C < D /\ D < E;

% digits for squares A, B and D
var 1..9:a1; var 1..9:a2; var 1..9:a3;
var 1..9:b1; var 1..9:b2; var 1..9:b3;
var 1..9:d1; var 1..9:d2; var 1..9:d3;

% all 3-digit squares
set of int: sq3 = {n*n | n in 10..31};

predicate is_sq(var int: y) =
exists(z in 1..ceil(sqrt(int2float(ub(y)))))
(z*z = y);
        
% the total of the five extensions was also a perfect square        
constraint is_sq(A + B + C + D + E);

 % all five telephone extensions are 3-digit squares       
constraint A in sq3 /\ B in sq3 /\ C in sq3 /\ D in sq3 /\ E in sq3;

% digit components in squares A, B and D
constraint a1 == A div 100 /\ a2 == A div 10 mod 10 /\ a3 == A mod 10;
constraint b1 == B div 100 /\ b2 == B div 10 mod 10 /\ b3 == B mod 10;
constraint d1 == D div 100 /\ d2 == D div 10 mod 10 /\ d3 == D mod 10;

set of int: all_dig ={1, 2, 3 ,4, 5, 6, 7, 8, 9};
var set of int: S1 == {a1, a2, a3, b1, b2, b3, d1, d2, d3};
constraint all_dig == S1;

solve satisfy;

output ["Caroline's extension is " ++ show(C)
++"\nOther extensions are " ++ show(A) ++ ", " ++ show(B)
++ ", " ++ show(D) ++ ", " ++ show(E) ];

LikeLike

GeoffR 8:44 am on 6 February 2021 Permalink | Reply

from itertools import combinations
from enigma import nsplit, is_square

squares =[x * x for x in range(10, 32)]

for A, B, C, D, E in combinations(squares, 5):
  # five extensions are in numerical order
  if A < B < C < D < E:
    sq_total = A + B + C + D + E 
    if is_square(sq_total):
      # find individual digits of A, B and D
      a1, a2, a3 = nsplit(A)
      b1, b2, b3 = nsplit(B)
      d1, d2, d3 = nsplit(D)
      S1 = set((a1, a2, a3, b1, b2, b3, d1, d2, d3))
      # check this set contains nine positive digits
      if len(S1) == 9 and 0 not in S1:
        print(f"Five extensions are {A}, {B}, {C}, {D}, {E}")

LikeLike

Frits 7:44 pm on 6 February 2021 Permalink | Reply

squares = [x * x for x in range(15, 66)]
ABD_squares = [x * x for x in range(13, 31) 
               if len(set(str(x * x) + "0")) == 4]

for i, a in enumerate(ABD_squares[:-2]):
  for j, b in enumerate(ABD_squares[i + 1:-1]):
    if len(set(str(a) + str(b))) != 6: continue
    for d in ABD_squares[i + j + 2:]:
      if len(set(str(a) + str(b) + str(d))) != 9: continue
      p = squares.index(b)
      q = squares.index(d)
      
      for c in squares[p + 1:q]:
        for e in squares[q + 1:17]:
          if not (a + b + c + d + e) in squares: continue
          print(f"Caroline's extension is {c}.")

LikeLike

Tony Brooke-Taylor 10:21 am on 7 February 2021 Permalink | Reply

import itertools

digits = set([str(j) for j in range(1, 10)])

for M in itertools.combinations([i**2 for i in range(10, 32)], 5):
  if (sum(M)**(1/2))%1 == 0:
    if set(str(M[0])+str(M[1])+str(M[3])) == digits: print("Caroline's extension is", M[2])

LikeLike

Frits 4:21 pm on 7 February 2021 Permalink | Reply

Logic can reduce a,b and d to specific squares.
The version without reduction logic is faster.

from collections import defaultdict

squares = [x * x for x in range(15, 66)]
ABD_squares = [x * x for x in range(13, 31) 
               if len(set(str(x * x) + "0")) == 4]
    
# return first column    
col0 = lambda li: [x[0] for x in li]               

fixed = set()
str_fixed = ""
mut_excl = defaultdict(set)

# reduce candidates in list <ABD_squares>
# by looking for digits occurring once or twice in list <ABD_squares>
for loop in range(9):
  occ = defaultdict(list)
  
  for x in "123456789":
    # add entries to occurence dictionary <occ>
    for i, s in enumerate(ABD_squares):
      s1 = str(s)
      if x not in s1 or s1 in fixed: continue
      # skip if a square digit already occurs in <fixed>
      if any(y in str_fixed for y in s1): continue
      occ[x].append([i, s1])

    if len(occ[x]) == 1:  
      # a square has to occur in <ABD_squares>
      if not occ[x][0][1] in fixed:
        fixed.add(occ[x][0][1])
        str_fixed = "".join(fixed)
        # also update occurrence for other 2 related digits to same square
        for c in occ[x][0][1]:
          if c == x: continue
          occ[c] = occ[x]
    elif len(occ[x]) == 2:
      # we have a square with digits x,e,f and a square with digits x,g,h
      # so e, e, f, f may not occur in another square with resp. g, h ,g, h
      for y in occ[x][0][1]: 
        if y == x: continue
        for z in occ[x][1][1]:
          if z == x: continue
          mut_excl[y].add(z)  
          mut_excl[z].add(y) 

  # check if 2 digits always occur in different squares
  for x1, y1 in occ.items():
    for x2, y2 in occ.items():
      if x1 >= x2: continue
      if len(set(col0(y1) + col0(y2))) != \
         len(col0(y1)) + len(col0(y2)): continue
      # digit x1 and x2 occur in different squares
      # so maintain dictionary <mut_excl>
      mut_excl[x1].add(x2)
      mut_excl[x2].add(x1)

  # reduce squares if a square contains mutually exclusive digits
  ABD_squares = [s for s in ABD_squares 
                 if not any(m in str(s) for y in str(s) 
                            for m in mut_excl[y])
                ]
   
  if len(ABD_squares) == 3: break
  
  
# start with a,b,d and then check c and e
for i, a in enumerate(ABD_squares[:-2]):
  for j, b in enumerate(ABD_squares[i + 1:-1]):
    if len(set(str(a) + str(b))) != 6: continue
    for d in ABD_squares[i + j + 2:]:
      if len(set(str(a) + str(b) + str(d))) != 9: continue
      p = squares.index(b)
      q = squares.index(d)
      
      for c in squares[p + 1:q]:
        for e in squares[q + 1:17]:
          if not (a + b + c + d + e) in squares: continue
          print(f"Caroline's extension is {c}.")

LikeLike

Frits 1:25 pm on 8 February 2021 Permalink | Reply

Not very efficient.

# decompose a number into <k> increasing 3-digit squares a, b, c, d, e
# (a, b, d) has to contain all digits 1-9
def decompose(t, k, m=1, ss=[]):
  if k == 1:
    # check if last number is higher and a square
    if t > ss[-1] and int(t ** 0.5) ** 2 == t:
      yield ss + [t]
  else:
    for i in range(m, 32 - k + 1):
      s = i * i
      if s > t: break
      
      if k in {3, 1} or len(set(str(s) + "0")) == 4:
        yield from decompose(t - s, k - 1, i + 1, ss + [s])
        
# sum first five 3-digit squares is 750 and last five 3-digit squares is 4215
for r in range(28, 65):
  # get five 3-digit squares which add up to square <r * r>
  for x in decompose(r * r, 5, 10): 
    sabd = set(str(1000000 * x[0] + 1000 * x[1] + x[3]))
    if len(sabd) != 9: continue

    print(f"Caroline's extension is {x[2]}.")

LikeLike

Jim Randell 8:47 am on 4 February 2021 Permalink | Reply
Tags: by: D C Pusinelli

Brain-Teaser 688: Job allocation

From The Sunday Times, 22nd September 1974 [link]

Ashley, Bill, Charles, David, and Edward are (not necessarily in that order), a dustman, a grocer, a miner, a blacksmith, and an artist, and all live on the right hand side of Strife Lane, in even numbered houses. All five are of different ages and no man has reached the age of retirement (65). All of course are upright and honest citizens, and never tell lies. However, I had forgotten what job each man did, where he lived, and how old he was, and so, to help me, each man volunteered the following statements:

Ashley:
(1) The artist lives at No. 10, next to Charles;
(2) Nobody lives next to the grocer, although Bill is only two doors away.

Bill:
(3) I am the only man whose age is indivisible by 9;
(4) I am 4 years older than Ashley;

Charles:
(5) The blacksmith’s age is 5 times his house number;

David:
(6) The miner lives 4 houses higher up the road from me;
(7) The miner’s age is 3 times the dustman’s house number, but he is two-thirds the dustman’s age;

Edward:
(8) The dustman is twice as old as David;
(9) I am the oldest man in the street.

At what number does Ashley live?
How old is the grocer?
Who is the artist?

This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.

[teaser688]

Jim Randell 8:48 am on 4 February 2021 Permalink | Reply

I wrote a MiniZinc model to solve this puzzle, and then used the minizinc.py wrapper to format the output.

This Python program runs in 178ms.

from enigma import irange, printf
from minizinc import MiniZinc

model = """

  include "globals.mzn";

  % indices for A, B, C, D, E
  int: A = 1;
  int: B = 2;
  int: C = 3;
  int: D = 4;
  int: E = 5;

  % house numbers
  array [1..5] of var int: n;

  % even numbers
  constraint forall (i in 1..5) (n[i] > 0 /\ n[i] mod 2 = 0);
  % all different
  constraint all_different(n);

  % ages
  array [1..5] of var 16..64: a;

  % all different
  constraint all_different(a);

  % jobs
  var 1..5: Du;
  var 1..5: Gr;
  var 1..5: Mi;
  var 1..5: Bl;
  var 1..5: Ar;

  % all different
  constraint all_different([Du, Gr, Mi, Bl, Ar]);

  % (1) "the artist lives at number 10, next to C"
  constraint n[Ar] = 10;
  constraint n[C] = 8 \/ n[C] = 12;

  % (2) "nobody lives next to the grocer, although B is only 2 doors away"
  constraint forall (i in 1..5 where i != Gr) (abs(n[Gr] - n[i]) != 2);
  constraint abs(n[Gr] - n[B]) = 4;

  % (3) "B is the only one whose age is not divisible by 9"
  constraint forall (i in 1..5) (a[i] mod 9 != 0 <-> i = B);

  % (4) "B is 4 years older than A"
  constraint a[B] = a[A] + 4;

  % (5) "Bl age is 5x his house number"
  constraint a[Bl] = 5 * n[Bl];

  % (6) "Mi lives 4 houses further up the road than D"
  constraint n[Mi] = n[D] + 8;

  % (7) "Mi's age is 3x Du's house number; but Mi is 2/3 Du's age"
  constraint a[Mi] = 3 * n[Du];
  constraint 3 * a[Mi] = 2 * a[Du];

  % (8) "Du is 2x D's age"
  constraint a[Du] = 2 * a[D];

  % (9) "E is the oldest"
  constraint forall (i in 1..5 where i != E) (a[i] < a[E]);

  solve satisfy;

"""

p = MiniZinc(model)

name = [ "", "Ashley", "Bill", "Charles", "David", "Edward" ]
for (n, a, Du, Gr, Mi, Bl, Ar) in p.solve(result="n a Du Gr Mi Bl Ar"):
  j = { Du: "Dustman", Gr: "Grocer", Mi: "Miner", Bl: "Blacksmith", Ar: "Artist" }
  for i in irange(1, 5):
    printf("{name}: house = {n}; age = {a}; job = {j}", name=name[i], n=n[i], a=a[i], j=j[i])

Solution: Ashley lives at number 18. The grocer is 63. David is the artist.

The complete solution:

Ashley: house = 18; age = 36; job = Miner
Bill: house = 8; age = 40; job = Blacksmith
Charles: house = 12; age = 54; job = Dustman
David: house = 10; age = 27; job = Artist
Edward: house = 4; age = 63; job = Grocer

LikeLike

Frits 11:52 am on 11 February 2021 Permalink | Reply

@Jim, you didn’t code that B’s age may not be not divisible by 9.

LikeLike
- Jim Randell 11:59 am on 11 February 2021 Permalink | Reply
  @Frits: Oh yes.
  
  I’ll update line 48 to:
```
  % (3) "B is the only one whose age is not divisible by 9"
  constraint forall (i in 1..5) (a[i] mod 9 != 0 <-> i = B);
```
  LikeLike

Frits 9:38 pm on 11 February 2021 Permalink | Reply

“if stop: continue”

My first version started looping over house numbers (where a maximum house number had to be specified). Looping over ages first eliminates this problem.

from itertools import permutations

# indices Ashley ... Edward
(A, B, C, D, E) = (0, 1, 2, 3, 4)

#  "B is 4 years older than A (which is a multiple of 9)"
b_ages = [x for x in range(22, 65) if x % 9 != 0 and (x - 4) % 9 == 0]

acde_ages = tuple(permutations(range(18, 65, 9), 4))    

jobs_indices = list(permutations(range(5)))

# update list hn for key <k> if value <v> doesn't exist yet in hn
def update(k, v):
  if v in hn: 
    return False
  else:  
    hn[k] = v
    return True
  
# start with ages divisble by 9
for p4 in acde_ages:
  #  "Bl age is 5x his house number"
  if all(x % 5 != 0 for x in p4): 
    # at least one age must be a multiple of 5
    b_ages = [x for x in b_ages if x % 5 == 0]

  for b in b_ages:
    #  "B is 4 years older than A"
    if b != p4[0] + 4: continue
    
    # b must be placed at 2nd spot
    ag = (p4[0], b) + p4[1:]
    
    #  "E is the oldest"
    if ag[E] != max(ag): continue
    
    #  "Du is 2x D's age"
    if (2 * ag[D]) not in ag: continue
  
    # indices for Du, Gr, Mi, Bl, Ar
    for (Du, Gr, Mi, Bl, Ar) in jobs_indices:
      #  "Mi is 2/3 Du's age"
      if 3 * ag[Mi] != 2 * ag[Du]: continue
      
      #  "Bl age is 5x his house number"
      if ag[Bl] % 5 != 0: continue
      
      #  "Mi's age is 3x Du's house number"
      if ag[Mi] % 3 != 0: continue
     
      #  "Du is 2x D's age"
      if ag[Du] != 2 * ag[D]: continue
      
      # initialize house numbers
      hn = [0, 0, 0, 0, 0]
      
      #  "the artist lives at number 10, next to C"
      hn[Ar] = 10
      if not update(Du, ag[Mi] // 3): continue
      if not update(Bl, ag[Bl] // 5): continue
      
      if hn[C] and hn[C] not in {8, 12} : continue
      
      for loop in range(2):
        #  "Mi lives 4 houses further up the road than D"
        if hn[Mi] == 0 and hn[D]:
          if not update(Mi, hn[D] + 8): break
        elif hn[Mi] and hn[D] == 0:
          hn[D] = hn[Mi] - 8
          if hn[Mi] < 10 or not update(D, hn[Mi] - 8): 
            break
        elif hn[Mi] and hn[D]:  
          if hn[Mi] != hn[D] + 8: break

        # B is only 2 doors away from grocer"
        if hn[B]:
          if hn[Gr]:
            if abs(hn[B] - hn[Gr]) != 4: break
          else:
            Gr_opts = []
            if hn[B] + 4 not in hn: 
              Gr_opts.append(hn[B] + 4)
            if hn[B] > 5 and hn[B] - 4 not in hn:
              Gr_opts.append(hn[B] - 4)
            if len(Gr_opts) == 1:
              if not update(Gr, Gr_opts[0]): break
            elif len(Gr_opts) == 0: break
        else:
          if hn[Gr]:
            B_opts = []
            if hn[Gr] + 4 not in hn: 
              B_opts.append(hn[Gr] + 4)
            if hn[Gr] > 5 and hn[Gr] - 4 not in hn:
              B_opts.append(hn[Gr] - 4)
            if len(B_opts) == 1:
              if not update(B, B_opts[0]): break
            elif len(B_opts) == 0: break
        
        #  "nobody lives next to the grocer"
        if hn[Gr] and any(abs(x - hn[Gr]) == 2 and x != 0 for x in hn): break
        
        #  "the artist lives at number 10, next to C"
        if hn[C] and hn[C] not in {8, 12} :  break
        
      else: # no break
        
        # all house numbers determined? 
        if 0 in hn: continue

        jobs = {Du:  "Dustman", Gr: "Grocer", Mi: "Miner", 
                Bl: "Blacksmith", Ar: "Artist"}

        print("              Ashley", ) 
        print("              |   Bill") 
        print("              |   |   Charles") 
        print("              |   |   |   David") 
        print("              |   |   |   |   Edward") 
        print("house number", tuple(hn))
        print("age         ", ag)
        print("              |   |   |   |  ", jobs[4]) 
        print("              |   |   |  ", jobs[3]) 
        print("              |   |  ", jobs[2]) 
        print("              |  ", jobs[1]) 
        print("             ", jobs[0])

LikeLike

Frits 12:58 pm on 10 August 2021 Permalink | Reply

@Jim,

Did you choose for MiniZinc because it allows for an unrestrained house number range?

LikeLike
- Jim Randell 3:35 pm on 10 August 2021 Permalink | Reply
  
  @Frits: That was probably the main reason. Also using a declarative solver like MiniZinc meant I didn’t have to worry about what order to attack the problem in.
  
  LikeLike
Frits 2:13 pm on 10 August 2021 Permalink | Reply

@Jim,

If I add

var 2..6: q = Ar + 1;

then variable q is not in the result set.

Is this a MiniZinc issue or a wrapper issue?

LikeLike
- Jim Randell 3:29 pm on 10 August 2021 Permalink | Reply
  @Frits:
  
  The wrapper just parses the MiniZinc output and turns it into Python objects. So if MiniZinc doesn’t output a value it is not available in Python.
  
  But you should be able to use a constraint to get the value output by default:
```
var 2..6: q;
constraint q = Ar + 1;
```
  LikeLike

Jim Randell 8:33 am on 2 February 2021 Permalink | Reply
Tags: by: Ian Kay ( 5 )
Teaser 2774: Loaded dice
From The Sunday Times, 22nd November 2015 [link] [link]

I have two traditional-looking dice, but only one of them is fair. In the other there is an equal chance of getting a 1, 2, 3, 4 or 5, but the die is loaded so that a 6 is thrown more than half the time. I threw the two dice and noted the total. It turned out that with my dice the chance of getting that total was double what it would have been with two fair dice.

What (as a simple fraction) is the chance of getting a 6 with the loaded die?

[teaser2774]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
John Crabtree and Jim Randell are discussing. Toggle Comments
- Jim Randell 8:35 am on 2 February 2021 Permalink | Reply
  
  The fair die has a probability of 1/6 of showing any particular face (scores 1-6).
  
  The unfair die has a probability of p of showing 6, and (1 − p) / 5 of showing the other faces (scores 1-5).
  
  If we consider the probability of throwing a total of t (scores 2-12) using both dice:
  
  There are { n = (t − 1) if t ≤ 6; otherwise n = (13 − t) } different ways of achieving the total.
  
  And with two fair dice (which have 36 equally like outcomes) the probability of throwing t is n / 36.
  
  And we want to find when the probability of throwing t with one fair and one unfair dice is twice this value: i.e. when the probability is n / 18.
  
  If t ≤ 6, then neither die can show a 6, so the probability of throwing t is:
  
  P = n ((1 − p) / 5) (1/6)
  
  which we can solve for P = n / 18:
  
  n ((1 − p) / 5) (1/6) = n / 18
  3(1 − p) = 5
  p = −2/3 (not possible)
  
  If t > 6, then 6 can show on the unfair dice, so we have two ways to make the total:
  
  P = [(n − 1) ((1 − p) / 5) (1/6)] + [p (1/6)]
  
  and we can solve this for P = n / 18:
  
  (n − 1) ((1 − p) / 5) (1/6) + p / 6 = n / 18
  3(n − 1)(1 − p) + 15p = 5n
  18p − 3np − 3 = 2n
  p = (2n + 3) / (18 − 3n)
  
  Also for t > 6 we have: n = 13 − t, so:
  
  p = (2(13 − t) + 3) / (18 − 3(13 − t))
  p = (29 − 2t) / (3t − 21)
  
  And we are interested in cases where t = 7 .. 12 and 0.5 < p ≤ 1:
  
  t = 7 ⇒ p = undefined (not possible)
  t = 8 ⇒ p = 13/3 (not possible)
  t = 9 ⇒ p = 11/6 (not possible)
  t = 10 ⇒ p = 1
  t = 11 ⇒ p = 7/12
  t = 12 ⇒ p = 1/3 (not permitted)
  
  So we find there are 2 possible situations:
  
  (1) The loaded die always shows 6, and the setter threw 10.
  The probability of throwing 10 with two fair dice is 1/12.
  The probability of throwing 10 with one fair die and the loaded die is 1/6.
  
  (2) The loaded die has a probability 7/12 of showing 6, and the setter threw 11.
  The probability of throwing 11 with two fair dice is 1/18.
  The probability of throwing 11 with one fair die and the loaded die is 1/9.
  
  I suspect we are to ignore that case where the loaded die always shows 6, as this would be quite obvious. (Although I would have thought a die that shows 6 more than half the time would be fairly obvious anyway). The setter could have explicitly excluded this case by specifying “an equal non-zero chance of scoring 1 – 5″ for the loaded die.
  
  Solution: The probability of scoring 6 with loaded die is 7/12.
  
  LikeLike
- John Crabtree 2:16 am on 4 February 2021 Permalink | Reply
  
  I was fortunate and took the probability of the throwing 6 with the biased die as n times that of any other number ie n>5 and p = n/(n+5).
  I reached t = 10 + 9/(n+2) when Jim’s two situations are immediately apparent.
  
  LikeLike

Jim Randell 5:01 pm on 29 January 2021 Permalink | Reply
Tags: by: Stephen Hogg ( 64 )

Teaser 3045: Let Tel play BEDMAS hold ’em!

From The Sunday Times, 31st January 2021 [link] [link]

Awaiting guests on poker night, Tel placed (using only clubs, face-up, in order left-to-right) the Ace (=1) to 9 (representing numerals), then interspersed the Ten, Jack, Queen and King (representing –, +, × and ÷ respectively) in some order, but none together, among these.

This “arithmetic expression” included a value over 1000 and more even than odd numbers. Applying BEDMAS rules, as follows, gave a whole-number answer. “No Brackets or powErs, so traverse the expression, left-to-right, doing each Division or Multiplication, as encountered, then, again left-to-right, doing each Addition or Subtraction, as encountered.”

Tel’s auntie switched the King and Queen. A higher whole-number answer arose. Tel displayed the higher answer as a five-card “flush” in spades (the Jack for + followed by four numeral cards).

Give each answer.

[teaser3045]

Jim Randell 5:51 pm on 29 January 2021 Permalink | Reply

I took “whole number” to be any integer, although you get the same answer if you just use positive integers.

It was fun writing the [[ evaluate() ]] routine to perform the calculations in the described fashion (although it is just standard arithmetic precedence rules).

The following Python program runs in 59ms.

Run: [ @replit ]

from enigma import (Rational, irange, subsets, tuples, peek, as_int, catch, update, multiset, join, printf)

# implementation of rationals
Q = Rational()

# map operators to implementation
fn = {
  '+': (lambda a, b: a + b),
  '-': (lambda a, b: a - b),
  '*': (lambda a, b: a * b),
  '/': (lambda a, b: Q(a, b)),
}

# evaluate the expression <ss>
def evaluate(ss):
  ss = list(ss)
  # precedence order
  for ops in [set('*/'), set('+-')]:
    while True:
      # find the leftmost occurrence of an operator
      i = peek((i for (i, op) in enumerate(ss) if op in ops), default=-1)
      if i == -1: break
      # apply the operation
      assert 0 < i < len(ss) - 1
      n = fn[ss[i]](ss[i - 1], ss[i + 1])
      ss[i - 1:i + 2] = [n]
  assert len(ss) == 1
  return ss[0]

# interleave 2 sequences (until one runs out)
def interleave(s1, s2):
  (i1, i2) = (iter(s1), iter(s2))
  while True:
    try:
      yield next(i1)
      yield next(i2)
    except StopIteration:
      break

# the string of digits
digits = "123456789"
ds = multiset.from_seq(digits)

# slice up the string of digits
n = len(digits)
for ps in subsets(irange(1, n - 1), size=4, fn=list):
  ns = tuple(int(digits[i:j]) for (i, j) in tuples([0] + ps + [n]))
  # at least one number is greater than 1000
  if not any(n > 1000 for n in ns): continue
  # there are more even numbers than odd numbers
  if not (len(ns) > 2 * sum(n % 2 for n in ns)): continue

  # insert the operators
  for ops in subsets("+-*/", size=4, select="P"):
    # make the first expression
    ss1 = list(interleave(ns, ops))
    # evaluate it
    r1 = catch(as_int, evaluate(ss1))
    if r1 is None: continue

    # swap * and /
    ss2 = update(ss1, [(ss1.index('*'), '/'), (ss1.index('/'), '*')])
    r2 = catch(as_int, evaluate(ss2))
    if r2 is None or not(r1 < r2): continue    

    # the result is a positive 4-digit number
    if r2 < 1000 or r2 > 9999: continue
    # that can be represented using the available digits
    if not ds.issuperset(str(r2)): continue

    # output solution
    printf("{ss1} = {r1}; {ss2} = {r2}", ss1=join(ss1, sep=" "), ss2=join(ss2, sep=" "))

Solution: Tel’s answer was 1274. Auntie’s answer was 1289.

The expressions are:

Tel: 1234 + 56 × 7 ÷ 8 − 9 = 1274
Auntie: 1234 + 56 ÷ 7 × 8 − 9 = 1289

There are only 6 ways to split up the digits in the required fashion:

1 | 2 | 34 | 5678 | 9
1 | 2 | 3456 | 78 | 9
12 | 3 | 4 | 5678 | 9
12 | 3456 | 7 | 8 | 9
1234 | 5 | 6 | 78 | 9
1234 | 56 | 7 | 8 | 9

Which lead to 22 expressions that evaluate to a positive integer.

There are 2 further candidate solutions resulting in 4-digit positive numbers, but Tel would not be able to display the result as described:

Tel: 12 × 3 ÷ 4 + 5678 − 9 = 5678
Auntie: 12 ÷ 3 × 4 + 5678 − 9 = 5685

Tel: 1234 − 56 ÷ 7 × 8 + 9 = 1179
Auntie: 1234 − 56 × 7 ÷ 8 + 9 = 1194

LikeLike

Tony Brooke-Taylor 11:02 am on 31 January 2021 Permalink | Reply

I was going mad trying to find my error but when I compared my solution to yours I get the same. I guess the puzzle allows for an Ace in the flush.

LikeLike
- Jim Randell 2:05 pm on 31 January 2021 Permalink | Reply
  
  @Tony: There is only one candidate solution that is positive, and is composed of 4 distinct positive digits. And I was happy enough that this could be represented using the described cards.
  
  Fortunately I don’t know enough about poker to know if this counts as a “5 card flush” or not.
  
  LikeLike

Frits 9:23 pm on 30 January 2021 Permalink | Reply

from enigma import SubstitutedExpression
from itertools import  permutations

def check(li):
  # credit: B. Gladman
  # there must be more even than odd numbers
  if sum([x & 1 for x in li]) > 2:
    return ""
    
  li2 = [str(x) for x in li]  
  for p in permutations("*/+-", 4):
    exp = ''.join(a + b for a, b in zip(li2, p + ('',)))
    ev = eval(exp) 
    if ev % 1 == 0 and ev >= 0:
      exp2 = ''.join(chr(ord(c) ^ 5) if c in '/*' else c for c in exp)
      ev2 = eval(exp2) 
      if ev2 > ev and ev2 % 1 == 0:
        ev2 = int(ev2)
        # larger answer has distinct non-zero digits
        if "0" not in str(ev2) and len(set(str(ev2))) == len(str(ev2)):
          return exp + " ; " + exp2
      
  return ""


# the alphametic puzzle
p = SubstitutedExpression(
  [
  "T + 1 == U or T == 0",
  "S + 1 == T or S == 0",
  "R + 1 == S or R == 0",
  "[x for x in [R, S, T, U] if x > 0][0] == Q + 1",

  "P + 1 == Q or P == 0",
  "O + 1 == P or O == 0",
  "N + 1 == O or N == 0",
  "[x for x in [N, O, P, Q] if x > 0][0] == M + 1",

  "L + 1 == M or L == 0",
  "K + 1 == L or K == 0",
  "J + 1 == K or J == 0",
  "[x for x in [J, K, L, M] if x > 0][0] == H + 1",

  "G + 1 == H or G == 0",
  "F + 1 == G or F == 0",
  "E + 1 == F or E == 0",
  "[x for x in [E, F, G, H] if x > 0][0] == D + 1",

  "C + 1 == D or C == 0",
  "B + 1 == C or B == 0",
  "A + 1 == B or A == 0",
  "[x for x in [A, B, C, D] if x > 0][0] == 1",
  
  # included a value over 1000
  "sum([A > 0, E > 0, J > 0, N > 0, R > 0]) = 1",
  
  "len(check([ABCD, EFGH, JKLM, NOPQ, RSTU])) > 0",
  
  ],
  answer="check([ABCD, EFGH, JKLM, NOPQ, RSTU])", 
  distinct="",
  env=dict(check=check),
  d2i=dict([(0, "DHMQU")] + 
           [(1, "EFGHJKLMNOPQRSTU")] + 
           [(2, "JKLMNOPQRSTU")] + 
           [(3, "NOPQRSTU")] +
           [(4, "RSTU")] +
           [(5, "RSTU")] +
           [(k, "U") for k in range(6, 9)]
           ),

  #reorder=0,
  verbose=0
  )   
  
# Print answer
for (_, ans) in p.solve():
  print(f"{ans}")

LikeLike

Jim Randell 9:19 am on 28 January 2021 Permalink | Reply
Tags: by: N A Phillips ( 5 )

Brain-Teaser 685: Overseas mail

From The Sunday Times, 1st September 1974 [link]

We were visiting the island state of Kimbu and had come to the post-office to send off some parcels to friends at home. The island’s currency is the pim, and the postmaster told us that he had only stamps of five different face-values, as these had to be used up before a new issue of stamps was introduced.

These stamps were black, red, green, violet, and yellow, in descending order of values, the black being the highest denomination and the yellow the lowest.

One parcel required stamps to the value of 100 pims and we were handed 9 stamps; 5 black, one green, and 3 violet. The other two parcels required 50 pims’ worth each, and for these we were given two different sets of 9 stamps.

One consisted of 1 black and 2 of each of the other colours, and the other set contained 5 green and 1 of each of the others.

What would be been the smallest number of stamps needed for a 50-pim parcel, and of which colours?

This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.

[teaser685]

Jim Randell 9:20 am on 28 January 2021 Permalink | Reply
I assumed the denominations of the stamps were all positive integer values.

We can place lower and upper limits on the values of the stamps.

The stamps are ordered: B > R > G > V > Y, which gives minimum values of: 5, 4, 3, 2, 1.

And 5 black stamps are used in making a value of 100, so black must have a value of less than (100 − (3 + 3×2)) / 5 = 18.2.

Similarly, 5 green stamps are used in making a value of 50, so green must have a value of less than (50 − (5 + 4 + 2 + 1)) / 5 = 7.6.

So we can write down the following ranges for each denomination:

B: 5..18
R: 4..17
G: 3..7
V: 2..6
Y: 1..5

And we have three equations relating the values. So choosing values for V and Y will give us a set of 5 simultaneous equations that can be solved to find the other values.

This Python program use the [[ matrix.linear() ]] solver for systems of linear equations from the enigma.py library. It runs in 63ms.

Run: [ @repl.it ]
```
from enigma import (irange, subsets, matrix, as_int, express, group, printf)

# choose values for Y and V
for (Y, V) in subsets(irange(1, 6), size=2):

  # make the equations
  eqs = [
    # B  R  G  V  Y = ???
    ((5, 0, 1, 3, 0), 100), # 100-pim parcel
    ((1, 2, 2, 2, 2),  50), # 1st 50-pim parcel
    ((1, 1, 5, 1, 1),  50), # 2nd 50-pim parcel
    ((0, 0, 0, 0, 1),   Y), # Y value
    ((0, 0, 0, 1, 0),   V), # V value
  ]

  # solve the equations for integer values
  # (either matrix.linear() or as_int() may raise a ValueError)
  try:
    (B, R, G, V, Y) = (as_int(x) for x in matrix.linear(*zip(*eqs)))
  except ValueError:
    continue

  # check ordering
  if not (B > R > G > V > Y > 0): continue

  # find combinations that make 50, grouped by the total number of stamps
  d = group(express(50, [Y, V, G, R, B]), by=sum)
  # output minimal configurations
  k = min(d.keys())
  for (y, v, g, r, b) in d[k]:
    printf("{k} stamps; 50 = {b}x {B} (black), {r}x {R} (red), {g}x {G} (green), {v}x {V} (violet), {y}x {Y} (yellow)")
```
Solution: A 50-pim parcel can be sent using 5 stamps: 2 black, 1 red, 1 green, 1 yellow.

The values of the stamps are:

black = 18 pim
red = 9 pim
green = 4 pim
violet = 2 pim
yellow = 1 pim

So each stamp is half (rounded down) the next highest value.

There are 621 different ways to make 50 using the above denominations.

Here’s a manual derivation of the denominations:

[1] B + 2R + 2G + 2V + 2Y = 50
[2] B + R + 5G + V + Y = 50

Taking 2×[2] − [1] gives:

B + 8G = 50

And we know G is in the range 3 .. 7, and B is in the range 5 .. 18 and G < B:

G = 3 ⇒ B = 26 [not possible]
G = 4 ⇒ B = 18
G = 5 ⇒ B = 10
G = 6 ⇒ B = 2 [not possible]
G = 7 ⇒ B = −6 [not possible]

And:

5B + G + 3V = 100

Where V is in the range 2 .. 6 and V < G:

G = 4, B = 18 ⇒ V = 2
G = 5, B = 10 ⇒ V = 15 [not possible]

So we have: V = 2, G = 4, B = 18.

From which we see Y = 1, and R = 9.

LikeLike
- Jim Randell 5:55 pm on 28 January 2021 Permalink | Reply
  Here’s a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library. It runs in 122ms.
  
  It operates in base 19 as B ≤ 18.
  
  The only other restriction I used was that we already know that 50 is possible with 9 stamps, so I limit the numbers used for any single denomination to 8. (We can also do this in my Python program above, by passing [[ qs=irange(0, 8) ]] to the call to [[ express() ]] and that saves a little bit of time).
  
  We could restrict the other denominations in line with the ranges given above, but it is not necessary for a decent run time.
  
  Run: [ @repl.it ]
```
#! python -m enigma -rr

SubstitutedExpression

--base=19
--symbols="BRGVYbrgvy"
--distinct="BRGVY"

# work out the denominations
"Y > 0"
"V > Y"
"G > V"
"R > G"
"B > R"

"5 * B + G + 3 * V == 100" # 100 pim parcel
"B + 2 * (R + G + V + Y) == 50" # 1st 50 pim parcel
"5 * G + (B + R + V + Y) == 50" # 2nd 50 pim parcel

# find minimal amount to make 50
"b * B + r * R + g * G + v * V + y * Y == 50"

--answer="((b, r, g, v, y), (B, R, G, V, Y))"
--code="fmin = lambda ss: min(ss, key=unpack(lambda ns, ds: sum(ns)))"
--accumulate="fmin"

--verbose=16

# [optional] we already know 50 is possible with 9 stamps
--invalid="9-18,brgvy"
```
  LikeLike

Frits 12:24 pm on 28 January 2021 Permalink | Reply

from enigma import SubstitutedExpression

# the alphametic puzzle
p = SubstitutedExpression(
  [
  # try to avoid looping over BL and RE
  "G > V",
  "V > Y",
  # (5, 0, 1, 3, 0)  100-pim parcel
  "(100 - G - 3*V) // 5 = BL",
  
  # (1, 2, 2, 2, 2)  1st 50-pim parcel
  "(50 - BL) // 2  - (G + V + Y) = RE",
  "RE > G",
  "BL > RE",
  # (1, 1, 5, 1, 1)  2nd 50-pim parcel
  "BL + RE + 5*G + V + Y = 50",
  
  # Pick M blacks, N reds, O greens, P violets and Q yellows
  # we already know a 50-pim parcel can be formed with 9 stamps
  "M + N < 10",
  "M + N + O < 10",
  "M + N + O + P < 10",
  "M + N + O + P + Q < 10",
  
  "M*BL + N*RE + O*G + P*V + Q*Y = 50", 
  ],
  answer="M + N + O + P + Q, M, N, O, P, Q",
  distinct="",
  accumulate=min,
  # BL: 5..18  RE: 4..12  G: 3..7  V: 2..6  Y: 1..5 
  d2i=dict([(0, "GVY")] + 
           [(1, "VG")] + 
           [(2, "RBG")] + 
           [(k, "RB") for k in range(3, 6)] +
           [(6, "YRB")] +
           [(7, "YVRB")] +
           [(k, "YVGRBMNOPQ") for k in range(8, 10)]),

  reorder=0,
  verbose=0
  )   
  
  
# solve the puzzle
r = p.run()

colors = ["black", "red", "green", "violet", "yellow"]
for (x, y) in zip(list(r.accumulate)[1:], colors):
  if x > 0:
    print(x, y)

LikeLike

GeoffR 3:04 pm on 28 January 2021 Permalink | Reply

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

% black, red, green, violet, yellow stamps
% ... using Jim's analysis values for all stamp ranges
var 5..18:B; var 4..17:R; var 3..7: G;
var 2..6: V; var 1..5:Y;

% stamp values all different and in colour descending values
constraint all_different([B, R, G, V, Y]);
constraint B > R /\ R > G /\ G > V /\ V > Y;

% numbers of each colour of stamp to make 50 pim
var 0..9:NumB; var 0..9:NumG; var 0..9:NumV;
var 0..9:NumR; var 0..9:NumY;

% three stamp equations stated in teaser description
% 1. 5 black, one green, and 3 violet stamps for 100 pim
constraint 5*B + G + 3*V == 100;

% two different equations for stamps of 50 pim
% 2. one set consisted of 1 black and 2 of each of the other colours
constraint B + 2*R + 2*G + 2*V + 2*Y == 50;

% 3. other set contained 5 green and 1 of each of other colours 
constraint B + R + 5*G + V + Y == 50;

% General equation to make 50 pims value
constraint NumB*B + NumR*R +  NumG*G + NumV*V + NumY*Y == 50;

% minimise total number of coins used to make 50 units value
solve minimize(NumB + NumR + NumG + NumV + NumY);

output [ "Black stamp value = " ++ show(B) ++ " pim"
++ ", Red stamp value = " ++ show(R) ++ " pim"
++ "\n" ++ "Green stamp value = " ++ show(G) ++ " pim"
++ ", Violet stamp value = " ++ show(V) ++ " pim"
++ "\n" ++ "Yellow stamp value = " ++ show(Y) ++ " pim"
++ "\n"
++ "\n" ++ "Smallest number of stamps needed for a 50-pim parcel" 
++ "\n" ++ "[B, R, G, V, Y] =  "
++ show (NumB),", ",show(NumR),", ",show(NumG),", ",show(NumV),", ",show(NumY) ];

% Black stamp value = 18 pim, Red stamp value = 9 pim
% Green stamp value = 4 pim, Violet stamp value = 2 pim
% Yellow stamp value = 1 pim

% Smallest number of stamps needed for a 50-pim parcel
% [B, R, G, V, Y] =  2, 1, 1, 0, 1
% ----------
% ==========

LikeLike

John Crabtree 12:07 am on 29 January 2021 Permalink | Reply

Eq. 1: 5.B + 0.R + 1.G +3.V + 0.Y = 100
Eq. 2: 1.B + 2.R + 2.G +2.V + 2.Y = 50
Eq. 3 : 1.B + 1.R + 5.G +1.V + 1.Y = 50
10 * Eq. 3 – 5 * Eq. 2 – Eq. 1 gives 39.G – 3.V = 150, or 13.G – V = 50
Assuming integer solutions, G = 4, V = 2 and then B = 18, R + Y = 10 etc

LikeLike

	Jim Randell on Teaser 2443: [Phone masts…
	GeoffR on Teaser 2442: [Gaming mach…
	Jim Randell on Teaser 2442: [Gaming mach…
	Frits on Teaser 3314: Number unobt…
	Jim Randell on Teaser 3314: Number unobt…
	GeoffR on Teaser 3314: Number unobt…
	Jim Randell on Teaser 3314: Number unobt…
	Jim Randell on Teaser 3310: Building bri…

Search

Recent Posts

Recent Comments

Archives

Categories

Subscribe

RSS Links

Site Stats

Meta

Recent Updates Page 45 Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 8:47 am on 4 March 2021 Permalink | Reply Tags: by: Susan Bricket ( 17 )

Rate this:

Share:

Jim Randell 8:48 am on 4 March 2021 Permalink | Reply

Reply Cancel reply

Jim Randell 8:41 am on 2 March 2021 Permalink | Reply Tags: by: J E Kessel, by: J R Partridge

Rate this:

Share:

Jim Randell 8:43 am on 2 March 2021 Permalink | Reply

Frits 11:45 pm on 2 March 2021 Permalink | Reply

Jim Randell 8:25 am on 28 February 2021 Permalink | Reply Tags: by: Herbert Wright

Rate this:

Share:

Jim Randell 8:26 am on 28 February 2021 Permalink | Reply

Frits 10:43 pm on 1 March 2021 Permalink | Reply

Jim Randell 5:03 pm on 26 February 2021 Permalink | Reply Tags: by: Andrew Skidmore ( 87 )

Rate this:

Share:

Jim Randell 5:22 pm on 26 February 2021 Permalink | Reply

Tony Brooke-Taylor 12:57 pm on 27 February 2021 Permalink | Reply

Jim Randell 4:40 pm on 27 February 2021 Permalink | Reply

Frits 5:26 pm on 27 February 2021 Permalink | Reply

Tony Brooke-Taylor 9:48 am on 28 February 2021 Permalink | Reply

Brian Gladman 9:31 am on 28 February 2021 Permalink | Reply

Tony Brooke-Taylor 9:46 am on 28 February 2021 Permalink | Reply

Frits 4:53 pm on 27 February 2021 Permalink | Reply

Jim Randell 10:43 am on 25 February 2021 Permalink | Reply Tags: by: Eric Emmet ( 10 )

Rate this:

Share:

Jim Randell 10:44 am on 25 February 2021 Permalink | Reply

Jim Randell 8:42 am on 23 February 2021 Permalink | Reply Tags: by: Richard England ( 9 ), flawed ( 54 )

Rate this:

Share:

Jim Randell 8:44 am on 23 February 2021 Permalink | Reply

Frits 2:04 pm on 23 February 2021 Permalink | Reply

Jim Randell 8:53 am on 21 February 2021 Permalink | Reply Tags: by: F. Moore ( 2 )

Rate this:

Share:

Jim Randell 8:55 am on 21 February 2021 Permalink | Reply

Frits 11:53 am on 21 February 2021 Permalink | Reply

Jim Randell 12:49 pm on 21 February 2021 Permalink | Reply

Hugh Casement 1:51 pm on 21 February 2021 Permalink | Reply

Jim Randell 2:02 pm on 21 February 2021 Permalink | Reply

John Crabtree 6:58 pm on 22 February 2021 Permalink | Reply

Jim Randell 4:51 pm on 19 February 2021 Permalink | Reply Tags: by: Stephen Hogg ( 64 )

Rate this:

Share:

Jim Randell 5:29 pm on 19 February 2021 Permalink | Reply

Frits 9:10 pm on 19 February 2021 Permalink | Reply

Jim Randell 7:24 am on 20 February 2021 Permalink | Reply

Jim Randell 8:14 am on 28 February 2021 Permalink | Reply

Brian Gladman 10:44 pm on 19 February 2021 Permalink | Reply

Jim Randell 10:54 pm on 19 February 2021 Permalink | Reply

Brian Gladman 11:37 pm on 19 February 2021 Permalink | Reply

Jim Randell 7:17 am on 20 February 2021 Permalink | Reply

Brian Gladman 12:54 pm on 20 February 2021 Permalink | Reply

Jim Randell 1:45 pm on 20 February 2021 Permalink | Reply

Brian Gladman 5:09 pm on 20 February 2021 Permalink | Reply

Tony Brooke-Taylor 9:39 am on 21 February 2021 Permalink | Reply

Jim Randell 9:54 am on 21 February 2021 Permalink | Reply

Frits 12:58 am on 21 February 2021 Permalink | Reply

Tony Brooke-Taylor 9:43 am on 21 February 2021 Permalink | Reply

Jim Randell 9:48 am on 18 February 2021 Permalink | Reply Tags: by: Graham Smithers ( 84 )

Rate this:

Share:

Jim Randell 9:48 am on 18 February 2021 Permalink | Reply

Jim Randell 9:22 am on 16 February 2021 Permalink | Reply Tags: by: B W M Young ( 10 )

Rate this:

Share:

Jim Randell 9:23 am on 16 February 2021 Permalink | Reply

Jim Randell 8:47 am on 4 March 2021 Permalink | Reply
Tags: by: Susan Bricket ( 17 )

Jim Randell 8:41 am on 2 March 2021 Permalink | Reply
Tags: by: J E Kessel, by: J R Partridge

Jim Randell 8:25 am on 28 February 2021 Permalink | Reply
Tags: by: Herbert Wright

Jim Randell 5:03 pm on 26 February 2021 Permalink | Reply
Tags: by: Andrew Skidmore ( 87 )

Jim Randell 10:43 am on 25 February 2021 Permalink | Reply
Tags: by: Eric Emmet ( 10 )

Jim Randell 8:42 am on 23 February 2021 Permalink | Reply
Tags: by: Richard England ( 9 ), flawed ( 54 )

Jim Randell 8:53 am on 21 February 2021 Permalink | Reply
Tags: by: F. Moore ( 2 )

Jim Randell 4:51 pm on 19 February 2021 Permalink | Reply
Tags: by: Stephen Hogg ( 64 )

Jim Randell 9:48 am on 18 February 2021 Permalink | Reply
Tags: by: Graham Smithers ( 84 )

Jim Randell 9:22 am on 16 February 2021 Permalink | Reply
Tags: by: B W M Young ( 10 )

Jim Randell 9:16 am on 14 February 2021 Permalink | Reply
Tags: by: C. W. Mitford

Jim Randell 4:56 pm on 12 February 2021 Permalink | Reply
Tags: by: Howard Williams ( 44 )

Jim Randell 9:01 am on 11 February 2021 Permalink | Reply
Tags: by: Eric Emmet ( 10 )

Jim Randell 8:50 am on 9 February 2021 Permalink | Reply
Tags: by: Angela Newing ( 39 )

Jim Randell 9:26 am on 7 February 2021 Permalink | Reply
Tags: by: Ptolemaeus ( 5 )

Jim Randell 4:52 pm on 5 February 2021 Permalink | Reply
Tags: by: Danny Roth ( 87 )

Jim Randell 8:47 am on 4 February 2021 Permalink | Reply
Tags: by: D C Pusinelli