S2T2 | Solving Sunday Times Teasers

Recent Updates Page 14 Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 4:36 pm on 12 July 2024 Permalink | Reply
Tags: by: Bernardo Recaman ( 6 )
Teaser 3225: My extended family
From The Sunday Times, 14th July 2024 [link] [link]

When Daniela, the youngest of my nieces, was born not so long ago, her brother John remarked that Daniela’s year of birth was very special: no number added to the sum of that number’s digits was equal to her year of birth. The same was true for John’s year of birth.

“Well,” intervened Lorena, the eldest of my nieces, “if you want to know, my own year of birth — earlier than yours — also shares that very same property, and so does the year of birth of our father Diego. The same is even true for our grandmother Anna, who, as you know, was born in the 1950s”.

When were Daniela, John, Lorena, Diego and Anna born?

[teaser3225]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Tony Smith, Ruud, Brian Gladman, and 1 other are discussing. Toggle Comments
- Jim Randell 4:43 pm on 12 July 2024 Permalink | Reply
  It is straightforward to find candidate years, and we can then fit them to the family circumstances.
  
  I imposed a reasonable gap between generations, and although I’m not sure this is strictly necessary it does give a unique solution to the puzzle.
  
  The following Python program runs in 73ms. (Internal runtime is 245µs).
```
from enigma import (irange, dsum, diff, subsets, printf)

# find numbers added to their digit sum
xs = set(n + dsum(n) for n in irange(1922, 2024))

# look for recent years not in xs
years = diff(irange(1950, 2024), xs)
printf("years = {years}")

# enforce generation gaps
gap = lambda x, y: 15 < abs(y - x) < 50
# assign birth years in order
for (A, D, L, J, D2) in subsets(years, size=5):
  if not (A // 10 == 195): continue
  if not (gap(A, D) and gap(D, L) and gap(D, J) and gap(D, D2)): continue
  # output solution
  printf("A={A} D={D} L={L} J={J} D2={D2}")
```
  Solution: The years of birth were: Daniela = 2022; John = 2007; Lorena = 1996; Diego = 1974; Anna = 1952.
  
  There are only 7 recent candidate years (shown below), and only one reasonable assignment of birth years (also shown below):
  
  1952 = Anna
  1963
  1974 = Diego
  1985
  1996 = Lorena
  2007 = John
  2022 = Daniela
  
  Anna was born in the 1950’s (i.e. 1952), and was (presumably) more than 11 when Diego was born, so he could be born in 1974 (when Anna was 22).
  
  And Diego was (presumably) more than 11 when Lorena was born, so the nephews/nieces were born in 1996, 2007, 2022 (when Diego was 22, 33, 48).
  
  And this is the only situation where there is more than 11 years between generations.
  
  LikeLike
  - Tony Smith 12:01 pm on 13 July 2024 Permalink | Reply
    
    Biologically generation gap could be eg 11, and Diego could have been born before Anna.
    These possibilities give multiple answers.
    
    LikeLike
- Ruud 7:47 am on 13 July 2024 Permalink | Reply
  We can simply with
```
from istr import istr

print(sorted(set(range(1950, 2024)) - {int(sum(n) + n) for n in istr(range(2025))}))
```
  find that the only possible years of birth are
  1952, 1963, 1974, 1985, 1996, 2007, 2022
  But, given the fact that there are three generations, this leads to
  Anna 1952
  Diego 1974
  Loreena 1996
  John 2007
  Daniella 2022
  
  LikeLike
  - Brian Gladman 9:13 am on 13 July 2024 Permalink | Reply
    
    Hi Ruud,
    
    These teasers are published on Sundays each week as a competition for prizes in the print edition of the Sunday Times. They are designed with the intention that they are solved without computer assistance. I would hence ask you not to encourage cheating by revealing solutions before the competition ends two weeks after its publication.
    
    LikeLike
    - Ruud 9:31 am on 13 July 2024 Permalink | Reply
      
      Ok.
      
      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 9:46 am on 11 July 2024 Permalink | Reply
Tags: by: R. Buchanan-Dunlop ( 2 )

I recoded this teaser in a 3-stage permutation for 4, 2 and 3 digits – my previous posting was a brute-force 9-digit permutation. It was much faster, albeit that this 2nd posting was on an I9 CPU as opposed to an I7 CPU for the original posting

from enigma import Timer
timer = Timer('ST2579', timer='E')
timer.start()

from itertools import permutations

# a b c
# d e f
# g h i

digits = set(range(1, 10))

for p1 in permutations (digits, 4):
  a, b, d, e = p1
 
  # check four square totals
  tot = a + b + d + e
  q1 = digits.difference( p1)
  for p2 in permutations(q1, 2):
    c, f = p2
    if b + c + e + f == tot:
       q3 = q1.difference(p2)
       for p3 in permutations(q3):
         g, h, i = p3
         if d + e + g + h == tot:
           if e + f + h + i == tot:
       
             # check corner digits sum for a reverse total
             x, y = tot // 10, tot % 10
             rev_tot = 10 * y + x
             if a + c + g + i == rev_tot:
               if a < c and a < g and c < g:
           
                 # digits whose boxes have a common side with 6’s box
                 if a == 6:print(f"Adjacent digits = {b} and {d}.")
                 if b == 6:print(f"Adjacent digits = {a},{e} and {c}.")
                 if c == 6:print(f"Adjacent digits = {b} and {f}.")
                 if d == 6:print(f"Adjacent digits = {a},{e} and {g}.")
                 if e == 6:print(f"Adjacent digits = {b},{d},{f} and {h}.")
                 if f == 6:print(f"Adjacent digits = {c},{e} and {i}.")
                 if g == 6:print(f"Adjacent digits = {d} and {h}.")
                 if h == 6:print(f"Adjacent digits = {g},{e} and {i}.")
                 if i == 6:print(f"Adjacent digits = {h} and {f}.")
                 # Adjacent digits = 4,3 and 5.
                 timer.stop()      
                 timer.report()
                 # [ST2579] total time: 0.0055232s (5.52ms)

LikeLike

Frits 9:08 pm on 10 July 2024 Permalink | Reply

Looping over 4 variables.

     
from itertools import permutations

row, col = lambda i: i // 3, lambda i: i % 3

# adjacent fields to field <i>
adj = {i: tuple(j for j in range(9)
          if sum(abs(tp(j) - tp(i)) for tp in (row, col)) == 1)
          for i in range(9)}
          
#  A B C
#  D E F
#  G H I

'''
# each box of 4 digits sums to XY
"A + B + D + E = XY"
"B + C + E + F = XY"
"D + E + G + H = XY"
"E + F + H + I = XY"
 
# the four corners sum to YX
"A + C + G + I = YX"
'''

sols, set9 = set(), set(range(1, 10))
# Y is 1 or 2 as YX < 30 and X = 2 (H formula) so XY = 21
XY, YX = 21, 12
# get first three numbers
for B, D, E in permutations(range(1, 10), 3):
  # remaining numbers after permutation
  r = sorted(set9 - {B, D, E})
  A = XY - (B + D + E)
  if A in {B, D, E} or not (0 < A <= 12 - sum(r[:2])): continue
 
  for F in set(r).difference([A]):
    C = XY - B - E - F
    H = (4 * XY - YX) // 2 - (B + D + 2 * E + F)
    G = XY - D - E - H
    I =  YX - A - C - G
    if E + F + H + I != XY: continue
    
    vars = [A, B, C, D, E, F, G, H, I]
    if set(vars) != set9: continue
    # store digits adjacent to the 6
    sols.add(tuple(sorted(vars[j] for j in adj[vars.index(6)])))

print("answer:", ' or '.join(str(s) for s in sols))

LikeLike

Jim Randell 4:27 pm on 5 July 2024 Permalink | Reply
Tags: by: Colin Vout ( 38 )

Teaser 3224: Put your finger on it

From The Sunday Times, 7th July 2024 [link] [link]

On a particular stringed instrument, a fingering pattern of 2, 2, 3, 1 means that the pitches of strings 1 to 4 are raised by that many steps respectively from the “open strings” (i.e. their pitches when not fingered); this gives a “chord” of pitches C, E, G, A♯ in some order. The fingering pattern 4, 1, 0, x (for some whole number x from 0 to 11 inclusive) would give pitches F, A, C, D in some order, if these were all shifted by some fixed amount.

[Pitches range through C, C♯, D, D♯, E, F, F♯, G, G♯, A, A♯, B, which then repeat].

What are the pitches of “open strings” 1 to 4, and what is the value of x？

[teaser3224]

Jim Randell 4:46 pm on 5 July 2024 Permalink | Reply

A simple exhaustive search of the problem space finds the answer fairly quickly. So it will do for now – I might refine it a bit later.

This Python program runs in 99ms. (Internal runtime is 8.3ms).

from enigma import (irange, subsets, join, printf)

# format a set of notes
fmt = lambda ns: join(ns, sep=" ", enc="()")

# the order of notes
notes = "C C# D D# E F F# G G# A A# B".split()
n = len(notes)

# finger strings <ss> at frets <fs>
def finger(ss, fs):
  return list(notes[(notes.index(x) + y) % n] for (x, y) in zip(ss, fs))

# target chords
tgt1 = sorted("C E G A#".split())
tgt2 = sorted("F A C D".split())

# choose an ordering for the first target chord
for ns1 in subsets(tgt1, size=4, select='P'):
  # and fret it down to open strings
  ss = finger(ns1, [-2, -2, -3, -1])

  # choose a value for x and a transposition
  for (x, t) in subsets(irange(0, 11), size=2, select='M'):
    ns2 = finger(ss, [4 + t, 1 + t, 0 + t, x + t])
    # check for the target chord
    if sorted(ns2) == tgt2:
      printf("{ss} @[2, 2, 3, 1] = {ns1}; @[4, 1, 0, {x}] + {t} = {ns2}", ss=fmt(ss), ns1=fmt(ns1), ns2=fmt(ns2))

Solution: The open strings are [D, G♯, E, B]. And the value of x is 2.

Fretting @[2, 2, 3, 1] gives [E, A♯, G, C].

And, shifting up by 8 frets (e.g. using a capo) gives [A♯, E, C, G].

Then fretting @[4, 1, 0, 2] (above the capo) gives [D, F, C, A].

LikeLike

Ruud 7:31 am on 6 July 2024 Permalink | Reply

Here’s my brute force solution using sets:

from itertools import product

pitches = "C C# D D# E F F# G G# A A# B".split()

def index_set(s):
    return {pitches.index(n) for n in s}

def iadd(i, n):
    return (i + n) % 12

for istrings in product(range(12), repeat=4):
    if {iadd(istrings[0], 2), iadd(istrings[1], 2), iadd(istrings[2], 3), iadd(istrings[3], 1)} == index_set({"C", "E", "G", "A#"}):
        for shift in range(12):
            for x in range(12):
                if {iadd(istrings[0], 4 + shift), iadd(istrings[1], 1 + shift), iadd(istrings[2], 0 + shift), iadd(istrings[3], x + shift)} == index_set(
                    {"F", "A", "C", "D"}
                ):
                    print(f"open strings are {' '.join(pitches[i] for i in istrings)}")
                    print(f"x = {x}")

LikeLike

Jim Randell 4:32 pm on 28 June 2024 Permalink | Reply
Tags: by: Peter Good ( 28 )
Teaser 3223: Shaping up
From The Sunday Times, 30th June 2024 [link] [link]

Clark wondered how many different shapes he could draw with identical squares joined edge to edge and each shape containing the same number of squares. He only drew five different shapes containing four squares, for example, because he ignored rotations and reflections:

He drew all of the different shapes containing 1, 2, 3, 4, 5 and 6 squares and wrote down the total number of different shapes in each case. He took the six totals in some order, without reordering the digits within any total, and placed them end to end to form a sequence of digits which could also be formed by placing six prime numbers end to end.

In ascending order, what were the six prime numbers?

[teaser3223]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 4:53 pm on 28 June 2024 Permalink | Reply
  This is fairly straightforward, if you know how many free n-polyominoes there are of the required sizes. [@wikipedia]
  
  This Python program runs in 70ms. (Internal runtime is 4.1ms).
```
from enigma import (irange, primes, subsets, concat, uniq, ordered, printf)

# number of n-polyominoes (n = 1..6) [see: OEIS A000105]
ns = [1, 1, 2, 5, 12, 35]

# can we split a string into k primes?
def solve(s, k, ps=list()):
  if k == 1:
    p = int(s)
    if p in primes:
      yield ps + [p]
  elif k > 0:
    for n in irange(1, len(s) + 1 - k):
      p = int(s[:n])
      if p in primes:
        yield from solve(s[n:], k - 1, ps + [p])

# collect answers (ordered sequence of primes)
ans = set()
# consider possible concatenated sequences
for s in uniq(subsets(ns, size=len, select='P', fn=concat)):
  # can we split it into 6 primes?
  for ps in solve(s, 6):
    ss = ordered(*ps)
    printf("[{s} -> {ps} -> {ss}]")
    ans.add(ss)

# output solution(s)
for ss in sorted(ans):
  printf("answer = {ss}")
```
  Solution: The 6 prime numbers are: 2, 2, 5, 5, 11, 13.
  
  (Although note that they are not 6 different prime numbers).
  
  The number of free n-polyominoes for n = 1..6 is:
  
  1, 1, 2, 5, 12, 35
  
  (i.e. there is only 1 free monomino, going up to 35 free hexominoes).
  
  And we don’t have to worry about polyominoes with holes, as they don’t appear until we reach septominoes (7-ominoes).
  
  We can order these numbers as follows:
  
  1, 12, 1, 35, 2, 5 → “11213525”
  
  and this string of digits can be split into 6 prime numbers as follows:
  
  “11213525” → 11, 2, 13, 5, 2, 5
  
  In fact, we can order the numbers into 24 different strings of digits that can be split into primes, but they all yield the same collection of primes.
  
  LikeLike

Jim Randell 3:59 pm on 25 June 2024 Permalink | Reply
Tags: by: Robin Nayler ( 16 )

Teaser 2578: The right money

From The Sunday Times, 19th February 2012 [link] [link]

In order to conserve his change, Andrew, our local shopkeeper, likes to be given the exact money. So today I went to Andrew’s shop with a collection of coins totalling a whole number of pounds in value. I could use these coins to pay exactly any amount from one penny up to the total value of the coins. Furthermore, the number of coins equalled the number of pounds that all the coins were worth; I had chosen the minimum number of coins to have this property.

(a) How many coins did I have?
(b) For which denominations did I have more than one coin of that value?

[teaser2578]

Jim Randell 3:59 pm on 25 June 2024 Permalink | Reply

I am assuming we are using “standard” UK coinage which was in circulation at the time of the publication of the puzzle. These are: 1p, 2p, 5p, 10p, 20p, 50p, £1 (= 100p), £2 (= 200p).

There are special commemorative 25p and £5 coins, but these are not commonly used in making purchases.

We can get a nice compact program without doing any particular analysis (like determining there must be at least one 1p coin), and it runs in just under 1s, so it not too bad. (I also tried a custom express() routine which makes an amount using an exact number of coins, but it was only a little bit faster).

We are going to need at least 10 coins to be able to make the required different amounts (with a set of 10 different coins there are 2^10 − 1 = 1023 subsets, which could potentially allow all values from 1p – 1000p to be made, but with fewer coins there will be insufficiently many subsets).

This Python program runs in 860ms (using PyPy).

from enigma import (irange, inf, subsets, multiset, printf)

# coin denominations (in pence)
coins = (1, 2, 5, 10, 20, 50, 100, 200)

# consider number coins (= total value in pounds)
for n in irange(10, inf):
  done = 0
  # choose n coins ...
  for vs in subsets(coins, size=n, select='R', fn=multiset.from_seq):
    # ... with a total value of n pounds
    if vs.sum() != 100 * n: continue
    # can we make all values between 1 and 100n using these coins?
    if not all(any(vs.express(x)) for x in irange(1, 100 * n)): continue
    # output solution
    printf("{n} coins -> {vs}", vs=vs.map2str(arr='p x', sep='; '))
    done = 1
  if done: break

Solution: (a) There are 16 coins; (b) There is more than one of the 2p, 10p, £2 coins.

The collection is:

1× 1p
2× 2p
1× 5p
2× 10p
1× 20p
1× 50p
1× £1
7× £2
total = £16 in 16 coins

If we additionally allow 25p and £5 coins we can achieve the answer using only 13 coins:

1× 1p
2× 2p
2× 5p
1× 10p
1× 25p
1× 50p
1× £1
3× £2
1× £5
total = £13 in 13 coins

1x 1p
2× 2p
1× 5p
2× 10p
1× 20p
1× 50p
1× £1
3× £2
1× £5
total = £13 in 13 coins

LikeLike

Frits 1:30 pm on 1 July 2024 Permalink | Reply
Lucky for you the coin denominations weren’t something like [1, 2, 5, 10, 20, 50, 101, 104].
```
 
-------- number of coins: 182 [1, 2, 1, 1, 2, 1, 2, 172]
```
LikeLike

Jim Randell 2:21 pm on 3 July 2024 Permalink | Reply

I’ve just realised that [[ multiset.express() ]] already supports making an amount with a specific number of coins, so my code can be a bit more compact (and faster).

from enigma import (irange, inf, multiset, printf)

# coin denominations
coins = (1, 2, 5, 10, 20, 50, 100, 200)

# consider total value in pounds
for n in irange(10, inf):
  done = 0
  # make a total of n pounds using exactly n coins
  tot = 100 * n
  for vs in multiset.from_seq(coins, count=n).express(tot, n):
    # can we make all other values between 1 and tot using these coins?
    if not vs.expressible(irange(1, tot - 1)): continue
    # output solution
    printf("{n} coins -> {vs}", vs=vs.map2str(arr='p x', sep='; '))
    done = 1
  if done: break

LikeLike

Frits 2:55 pm on 3 July 2024 Permalink | Reply
I know you said you were not doing any particular analysis but with this update the program is faster especially for more difficult cases.
```
if not all(any(vs.express(x)) for x in irange(1, max(vs) - 1)): continue     
```
LikeLike
- Jim Randell 4:24 pm on 3 July 2024 Permalink | Reply
  
  @Frits: Good idea!
  
  LikeLike

Jim Randell 8:43 am on 5 July 2024 Permalink | Reply

The following approach builds up increasing sets of coins that can make change for all values from 1..n, by adding a coin to the previous sets. We can expand a set by adding another instance of the largest denomination in the set, or we can add a larger denomination coin only if we can already make all values lower than it.

This program runs (under PyPy) in 125ms (internal runtime is 37ms).

from enigma import (multiset, printf)

# coin denominations (in pence)
coins = (1, 2, 5, 10, 20, 50, 100, 200)

# build up increasing sets of coins that cover range 1..n
assert 1 in coins
(ss, tgt, done) = ([(0, [])], 0, 0)
while not done:
  tgt += 100
  ss_ = list()
  # consider current sets
  for (n, vs) in ss:
    m = (vs[-1] if vs else 0)
    # and try to add in another coin
    for d in coins:
      if d < m: continue
      if d - 1 > n: break
      (n_, vs_) = (n + d, vs + [d])
      if n_ == tgt:
        printf("{k} coins -> {vs}", k=len(vs_), vs=multiset.from_seq(vs_).map2str(arr="p x", sep="; "))
        done += 1
      ss_.append((n_, vs_))
  ss = ss_

printf("[{done} solutions]")

Note that with the following 16 coins we can make change for all values up to 1610p:

1× 1p
2× 2p
1× 5p
1× 10p
2× 20p
1× 50p
1× 100p
7× 200p
total = £16.10 in 16 coins

LikeLike

Frits 2:20 pm on 5 July 2024 Permalink | Reply

Jim’s clever latest program can use a lot of memory and become quite slow for some denominations (like “pypy3 teaser2578.py 1 2 5 10 39 71 103 131”).
His program suggested to me there might be a minimal number of pounds to have a solution. This minimal number of pounds can be used with his earlier program (unfortunately not with my program (of which I made a similar recursive version)).

from enigma import (irange, inf, multiset, map2str, printf)
from sys import argv

# coin denominations (in pence)
coins = ([1, 2, 5, 10, 20, 50, 100, 200] if len(argv) == 1 else
         list(int(x) for x in argv[1:]))

# build up increasing sets of coins that cover range 1..n
assert 1 in coins
coins.sort()

print(f"{coins = }") 

# determine the minimal number of pounds for which a solution is feasible
(tgt, ss, done, strt) = (0, [(0, [])], 0, 10)
while not done and tgt < 1000000:
  tgt += 100
  if tgt - ss[-1][0] <= coins[-1]:   # within reach
    if tgt > coins[-1]:  
      strt = tgt // 100
      print("minimal number of pounds:", strt)
      done = 1
      continue 
  
  ss_ = list()
  # consider current sets
  for (n, vs) in ss:
    m = (vs[-1] if vs else 0)
    # and try to add in another high coin
    for d in coins[::-1]:
      if d < m: continue     # not below minimum 
      # don't choose a coin higher than <n + 1>
      # otherwise number <n + 1> can never me made
      if d - 1 > n: continue
      ss_.append((n + d, vs + [d]))
      break # we have found the highest coin
  ss = ss_
  

if strt > 26:  # this can be changed to a better value
  print("Jim 1")
  # consider total value in pounds
  for n in irange(strt, inf):
    done = 0
    # make a total of n pounds using exactly n coins
    tot = 100 * n
    for vs in multiset.from_seq(coins, count=n).express(tot, n):
      # can we make all other values between 1 and tot using these coins?
      #if not vs.expressible(irange(1, tot - 1)): continue
      if not vs.expressible(irange(1, max(vs) - 1)): continue
      # output solution
      printf("{n} coins -> {vs}", vs=vs.map2str(arr='p x', sep='; '))
      done = 1
    if done: break  
else:
  print("Jim 2")
  (tgt, ss, done) = (0, [(0, [])], 0)
  while not done:
    tgt += 100
    ss_ = list()
    # consider current sets
    for (n, vs) in ss:
      m = (vs[-1] if vs else 0)
      # and try to add in another coin
      for d in coins:
        if d < m: continue
        if d - 1 > n: break
        (n_, vs_) = (n + d, vs + [d])
        if n_ == tgt:
          printf("{k} coins -> {vs}", k=len(vs_), vs=multiset.from_seq(vs_).map2str(arr="p x", sep="; "))
          done += 1
        ss_.append((n_, vs_))
    ss = ss_
   
  printf("[{done} solutions]")

LikeLike

Frits 1:25 pm on 1 July 2024 Permalink | Reply

For this program I didn’t try to keep every line within 80 bytes (it is already a bit messy).
I used a performance enhancement I don’t understand myself and I used break statements that I theoretically are not supposed to make. So far I have not encountered a case that differs from Jim’s program. The programs supports different coin denominations and also more than 8.

With the performance enhancement the program runs in 21ms.

from math import ceil
from sys import argv

# coin denominations
coins = (1, 2, 5, 10, 20, 50, 100, 200) if len(argv) == 1 else list(int(x) for x in argv[1:])
N = len(coins)
M = 20      # maximum quantity
vars = "abcdefghijklmnopqrstuxwxyz"
print(f"{coins = }, {N = }")
mn = 1e8    # minimum number of coins

# make number <n> for specific deniminations and quantities
def make(n, t, k, denoms, qs, ns=set(), ss=[]):
  if t == 0:
    yield ns | {n}
  if k :
    v, q = denoms[0], qs[0]
    ns.add(n - t)
    for i in range(min(q, t // v) + 1):
      yield from make(n, t - i * v, k - 1, denoms[1:], qs[1:], ns, ss + [i])
   
# make all numbers from <strt> to <n>      
def make_all(n, denoms, qs, strt=1):
  todo = set(i for i in range(strt, n + 1))  
  ln = len(denoms)
  while todo:
    n = max(todo)
    # make number <n>
    for made in make(n, n, ln, denoms, qs): 
      break
    else: return False  
    
    todo -= made
  return True

# enhance performance (don't know why this is the case)
if N < 9:
  _ = make_all(sum(qs := [2] * N) * 100, coins, qs)
  
exprs = ""

exprs += "mn, cnt = 1e8, 0\n\n"  
exprs += "def check(lev, qs, tv, mn, make=1):\n"
exprs += "  global cnt\n"  
exprs += f"  if mn < 1e8:\n"
exprs += "    # calculate minimum last quantity\n"  
exprs += "    h_ = ceil((100 * mn - tv) / coins[-1])\n"  
exprs += "    if sum(qs) + h_ > mn:\n"  
exprs += "      return 'break'\n"  

exprs += "  if make:\n"  
exprs += "    n = coins[lev] - 1\n"  
exprs += "    if tv < n: return False \n"  
exprs += "    strt = 1 + coins[lev - 1] if lev > 1 else 1\n"  
exprs += "    cnt += 1\n"  
exprs += "    # can we make numbers <strt>...<n> with these denominations?\n"  
exprs += "    if not make_all(n, coins[:lev], qs, strt):\n"  
exprs += "      return False\n"
exprs += "  return True\n\n"  

exprs += f"make_{vars[0]} = 1\n"
exprs += f"# can we make numbers 1..<total pence> with denominations {coins}?\n"

last_odd = [i for i, x in enumerate(coins) if x % 2][-1]
sols = dict()

for i in range(1, N + 1):
  if i < N: 
    # our worst case scenario is if we have only one odd denomination and we check
    # all combinations with only one coin of 1 with no chance of achieving an 
    # even number of pence
    if last_odd == 0 and i == 1:
      exprs += f"{'  '* (i - 1)}for {vars[i - 1]} in range({coins[1] - (coins[1] % 2)}, {max(coins[1] - (coins[1] % 2) + 15, M) if i != N - 1 else 2 * M}, 2):\n"
    elif last_odd == i - 1 and i != N:
      exprs += f"{'  '* (i - 1)}for {vars[i - 1]} in range(prod_{vars[i - 2]} % 2, max(prod_{vars[i - 2]} % 2 + 15, M) if i != N - 1 else {2 * M}, 2):\n"  
    else:  
      exprs += f"{'  '* (i - 1)}for {vars[i - 1]} in range({coins[1] - 1 if i == 1 else 0}, {max(coins[1] + 14 if i == 1 else 0, M) if i != N - 1 else 2 * M}):\n"
      
    if i == N - 1: 
      exprs += f"{'  '* i}tot = sum(lst_{vars[i - 2]}) + {vars[i - 1]}\n"
      if coins[-2] != 100:
        exprs += f"{'  '* i}# calculate last quantity so that the total is a multiple of 100\n"
        exprs += f"{'  '* i}{(last := vars[i])}, rest = divmod(prod_{vars[i - 2]} + {vars[i - 1]} * {coins[i - 1]} - "
        exprs += f"100 * tot, 100 - coins[-1])\n"
        exprs += f"{'  '* i}if rest or {last} < 0: continue\n"  
    
    exprs += f"{'  '* i}# can we make numbers 1..{coins[i] - 1} with denominations {coins[:i]}\n"
    exprs += f"{'  '* i}if not (chk := check({i}, lst_{vars[i - 1]} := [{', '.join(vars[:i])}],\n"
    if i > 1:
      exprs += f"{'  '* i}                        prod_{vars[i - 1]} := prod_{vars[i - 2]} + {vars[i - 1]} * {coins[i - 1]},\n"
    else:
      exprs += f"{'  '* i}                        prod_{vars[i - 1]} := {vars[i - 1]} * {coins[i - 1]},\n"  
    exprs += f"{'  '* i}                        mn, make_{vars[i - 1]})): continue\n"
    exprs += f"{'  '* i}if chk == 'break': break\n"
    exprs += f"{'  '* i}make_{vars[i - 1]}, make_{vars[i]} = 0, 1   # don't try to make 1..x anymore in this loop\n"
  
  if i == N - 2 and coins[-2] == 100: 
    exprs += f"{'  '* i}# we can already calculate last quantity\n"
    exprs += f"{'  '* i}{(last := vars[N - 1])}, rest = divmod(prod_{vars[i - 1]} - 100 * sum(lst_{vars[i - 1]}), 100 - coins[-1])\n"
    exprs += f"{'  '* i}if rest or {last} < 0: continue\n"
    
  if i == N: 
    exprs += f"{'  '* (i - 1)}if tot + {last} > mn: break\n"
    exprs += f"{'  '* (i - 1)}mn = tot + {last}\n"
    exprs += f"{'  '* (i - 1)}sols[mn] = sols.get(mn, []) + [lst_{vars[i - 2]} + [{last}]]\n"

exprs += "if mn not in sols:\n"   
exprs += "  print('ERROR: no solutions, mn =', mn)\n"   
exprs += "else:\n"   
exprs += "  print(f'solutions: {len(sols[mn])}            {cnt} calls to make_all')\n"    
exprs += "  for s in sols[mn]: print('-------- number of coins:', mn, s)\n"   

#print(exprs)  
exec(exprs)

The following code is generated:

mn, cnt = 1e8, 0

def check(lev, qs, tv, mn, make=1):
  global cnt
  if mn < 1e8:
    # calculate minimum last quantity
    h_ = ceil((100 * mn - tv) / coins[-1])
    if sum(qs) + h_ > mn:
      return 'break'
  if make:
    n = coins[lev] - 1
    if tv < n: return False
    strt = 1 + coins[lev - 1] if lev > 1 else 1
    cnt += 1
    # can we make numbers <strt>...<n> with these denominations?
    if not make_all(n, coins[:lev], qs, strt):
      return False
  return True

make_a = 1
# can we make numbers 1..<total pence> with denominations (1, 2, 5, 10, 20, 50, 100, 200)?
for a in range(1, 20):
  # can we make numbers 1..1 with denominations (1,)
  if not (chk := check(1, lst_a := [a],
                          prod_a := a * 1,
                          mn, make_a)): continue
  if chk == 'break': break
  make_a, make_b = 0, 1   # don't try to make 1..x anymore in this loop
  for b in range(0, 20):
    # can we make numbers 1..4 with denominations (1, 2)
    if not (chk := check(2, lst_b := [a, b],
                            prod_b := prod_a + b * 2,
                            mn, make_b)): continue
    if chk == 'break': break
    make_b, make_c = 0, 1   # don't try to make 1..x anymore in this loop
    for c in range(prod_b % 2, max(prod_b % 2 + 15, M) if i != N - 1 else 40, 2):
      # can we make numbers 1..9 with denominations (1, 2, 5)
      if not (chk := check(3, lst_c := [a, b, c],
                              prod_c := prod_b + c * 5,
                              mn, make_c)): continue
      if chk == 'break': break
      make_c, make_d = 0, 1   # don't try to make 1..x anymore in this loop
      for d in range(0, 20):
        # can we make numbers 1..19 with denominations (1, 2, 5, 10)
        if not (chk := check(4, lst_d := [a, b, c, d],
                                prod_d := prod_c + d * 10,
                                mn, make_d)): continue
        if chk == 'break': break
        make_d, make_e = 0, 1   # don't try to make 1..x anymore in this loop
        for e in range(0, 20):
          # can we make numbers 1..49 with denominations (1, 2, 5, 10, 20)
          if not (chk := check(5, lst_e := [a, b, c, d, e],
                                  prod_e := prod_d + e * 20,
                                  mn, make_e)): continue
          if chk == 'break': break
          make_e, make_f = 0, 1   # don't try to make 1..x anymore in this loop
          for f in range(0, 20):
            # can we make numbers 1..99 with denominations (1, 2, 5, 10, 20, 50)
            if not (chk := check(6, lst_f := [a, b, c, d, e, f],
                                    prod_f := prod_e + f * 50,
                                    mn, make_f)): continue
            if chk == 'break': break
            make_f, make_g = 0, 1   # don't try to make 1..x anymore in this loop
            # we can already calculate last quantity
            h, rest = divmod(prod_f - 100 * sum(lst_f), 100 - coins[-1])
            if rest or h < 0: continue
            for g in range(0, 40):
              tot = sum(lst_f) + g
              # can we make numbers 1..199 with denominations (1, 2, 5, 10, 20, 50, 100)
              if not (chk := check(7, lst_g := [a, b, c, d, e, f, g],
                                      prod_g := prod_f + g * 100,
                                      mn, make_g)): continue
              if chk == 'break': break
              make_g, make_h = 0, 1   # don't try to make 1..x anymore in this loop
              if tot + h > mn: break
              mn = tot + h
              sols[mn] = sols.get(mn, []) + [lst_g + [h]]
if mn not in sols:
  print('ERROR: no solutions, mn =', mn)
else:
  print(f'solutions: {len(sols[mn])}            {cnt} calls to make_all')
  for s in sols[mn]: print('-------- number of coins:', mn, s)

LikeLike

Ruud 3:12 pm on 1 July 2024 Permalink | Reply

You could generate exprs with:

exprs = f"""\
mn, cnt = 1e8, 0

def check(lev, qs, tv, mn, make=1):
  global cnt
  if mn < 1e8:
    # calculate minimum last quantity
    h_ = ceil((100 * mn - tv) / coins[-1])
    if sum(qs) + h_ > mn:
      return 'break'
  if make:
    n = coins[lev] - 1
    if tv < n: return False
    strt = 1 + coins[lev - 1] if lev > 1 else 1
    cnt += 1
    # can we make numbers <strt>...<n> with these denominations?
    if not make_all(n, coins[:lev], qs, strt):
      return False
  return True

make_{vars[0]} = 1
# can we make numbers 1..<total pence> with denominations {coins}?
"""

No change in functionality, just easier to understand and maintain.

LikeLike

Frits 5:27 pm on 1 July 2024 Permalink | Reply

Thanks, I had seen it before but had forgotten it.

I also tried to use make() and make_all() in this way but had to use
yield ns | {{n}}
for my original line 15. I hoped in making these 2 functions local as well I wouldn’t need the performance enhancement but it is still lowers the run time.

LikeLike

Frits 5:44 pm on 1 July 2024 Permalink | Reply

Does anybody have an explanation why line 38 (in the first program) lowers the run time? Is it a memory thing and does it also occur on a linux system?

LikeLike

Frits 9:26 pm on 18 July 2024 Permalink | Reply

from sys import argv
from math import ceil
from time import perf_counter

# coin denominations
coins = [1, 2, 5, 10, 20, 50, 100, 200] if len(argv) == 1 else \
         list(int(x.replace(",", "", 1)) for x in argv[1:])
coins.sort()
N = len(coins)
assert 1 in coins and coins[-1] > 100 and len(set(coins)) == N
last_odd = [i for i, x in enumerate(coins) if x % 2][-1]
mx_factor = max(divs := [ceil(coins[i + 1] / coins[i]) for i in range(N - 1)])
print(f"{coins = }")

# solve problem by adding coins of <N> different denominations  
def solve(ds, k=0, tv=0, nc=0, qs=[]):
  global mn
  if k == N - 1:
    # we can calculate the quantity of the highest denomination
    last, r = divmod(tv - 100 * nc, 100 - ds[-1])
    if r or last < 0 or (nc_ := nc + last) > mn: return
    mn = nc_
    yield qs + [last]
  else:
    min_i = max(0, ceil((ds[k + 1] - tv - 1) / ds[k]))
    if k == last_odd:
      min_i += (tv + min_i) % 2
    
    remaining = 100 * mn - tv
    # minimum elements to follow = ceil((remaining - (i * ds[k])) / ds[-1])
    # nc + i + minimum elements to follow <= mn 
    max_i = min((ds[-1] * (mn - nc) - remaining) // (ds[-1] - ds[k]),
            mn - nc,
            # do not make a total which is higher than the minimum
            remaining // ds[k])
    
    if max_i < min_i: 
      return
      
    if k < N - 2:
      # with <j - 1> quantities can we still make numbers up to ds[j] - 1
      # if we choose <i> of ds[k]    (for j >= k + 2)
      # tv + i * ds[k] + (mn - nc - i) * ds[j - 1] >= ds[j] - 1
      mx1 = min(((mn - nc) * ds[j - 1] + tv - c + 1) // (ds[j - 1] - ds[k])
              for j, c in enumerate(ds[k + 2:], k + 2))
      max_i = min(max_i, mx1)
    
    for i in range(min_i, max_i + 1, 1 if k != last_odd else 2):
      yield from solve(ds, k + 1, tv + i * ds[k], nc + i, qs + [i])
    
sols = dict()
mn = mx_factor + 27 # solving approx 80% of all cases in one pass 
inc = 15
cnt = 0
while not sols:
  print(f"try {mn = }")
  M = mn
  for s in solve(coins):
    cnt += 1
    # limit the number of printed solutions (causing slowness due to memory)
    if cnt > 999 and mn in sols: continue    
    if mn not in sols: 
      sols = dict()
      cnt = 1
    sols[mn] = sols.get(mn, []) + [s]
     
  if not sols:
    mn += inc  

for s in sols[mn]: print('-------- number of coins:', mn, s)  
print(f'[{cnt:>5} solutions]')

solving 1000 random testcases in approximately 200 seconds.

from random import sample
from os import system
from sys import argv, stdout, stderr

N = 8

c = 0
for _, _ in enumerate(iter(bool, 1), 1): # infinite loop     
  c += 1
  if c == 1001: break
  lst = [1] + sorted(sample(range(2, 2001), N - 1))
  if lst[-1] < 101: continue
  
  lst = ' '.join(str(x) for x in lst)
  print(f"{c = } {lst = }", file=stderr)
  system("python TheRightMoney.py " + lst)

LikeLike

Jim Randell 4:28 pm on 21 June 2024 Permalink | Reply
Tags: by: Mark Valentine ( 17 )

Teaser 3222: Squarism

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

There are 84 marbles, numbered sequentially from 1, in a bag. Oliver (going first) and Pam take turns, each removing two marbles from the bag. The player finds the “most square” integer factorisation of each number. The difference between the two factors for each number is then added to the player’s score (e.g. removing marbles 1 and 84 scores 5 points since 1 = 1 × 1 and 84 = 7 × 12), and the game ends when all marbles are removed.

After each of the first four turns (two each), both players’ expected final score was a whole number. For example, if there were 90 points remaining, with 4 turns left for Oliver and 5 for Pam, Oliver would expect to score another 40 points. In addition, each player’s score for their second turn was the same as their first. Also, Pamela scored the lowest possible game total.

What was Oliver’s expected final score after Pamela’s second turn?

[teaser3222]

Jim Randell 5:27 pm on 21 June 2024 Permalink | Reply

This Python program looks for possible repeated scores for O and P that could happen in the first 4 turns, that give the required whole number expectations, to give candidate solutions.

Once candidates are found (there are only two) it then attempts to choose marble values for the turns that give the required score, and any non-viable candidates (one of them) are eliminated.

It runs in 71ms. (Internal runtime is 656µs).

from enigma import (irange, isqrt, div, ediv, group, subsets, disjoint_cproduct, disjoint_union, printf)

# calculate the score for a marble
def score(n):
  for a in irange(isqrt(n), 1, step=-1):
    b = div(n, a)
    if b is not None: return abs(a - b)

# group the marbles by score
g = group(irange(1, 84), by=score)

# calculate total number of points
tot = sum(k * len(vs) for (k, vs) in g.items())

# find possible scores available to O and P
(keysO, keysP) = (list(), list())
t = 0
for k in sorted(g.keys()):
  n = len(g[k])
  t += n
  if not (t < 42):
    keysO.append(k)
  if not (t > n + 42):
    keysP.append(k)

# construct example scores for O and P
def choose(OPs, i=0, ss=list(), used=set()):
  # are we done?
  if not OPs:
    yield ss
  else:
    # choose values for the next score
    s = OPs[0]
    for vs in subsets([keysO, keysP][i], size=2, select='R'):
      if not (sum(vs) == s): continue
      # choose marbles
      for xs in disjoint_cproduct(g[v] for v in vs):
        used_ = disjoint_union([used, xs])
        if used_ is not None:
          yield from choose(OPs[1:], 1 - i, ss + [xs], used_)

# possible scores for O and P
scoresO = set(sum(ks) for ks in subsets(keysO, size=2, select='R'))
scoresP = set(sum(ks) for ks in subsets(keysP, size=2, select='R'))

# check expected remaining points
def check_exp(r, *fs):
  try:
    return list(ediv(r * a, b) for (a, b) in fs)
  except ValueError:
    return None

# consider scores for O's first 2 turns
for sO in scoresO:
  # expected remaining points after turn 1 (41 remaining turns)
  if not check_exp(tot - sO, (20, 41), (21, 41)): continue

  # consider scores for P's first 2 turns
  for sP in scoresP:
    # expected remaining points after turn 2 (40 remaining turns)
    if not check_exp(tot - (sO + sP), (20, 40)): continue
    # expected remaining points after turn 3 (39 remaining turns)
    if not check_exp(tot - (sO + sP + sO), (19, 39), (20, 39)): continue
    # expected remaining points after turn 4 (38 remaining turns)
    es = check_exp(tot - (sO + sP + sO + sP), (19, 38))
    if not es: continue

    # check scores can be made twice
    if not any(choose([sO, sP] * 2)): continue

    # output solution candidate
    printf("expected total scores: O={tO} P={tP} [sO={sO} sP={sP}]", tO=sO + sO + es[0], tP=sP + sP + es[0])

Solution: Oliver’s expected final score after Pam takes her second turn is 685.

There are only two candidate turn scores that give the required whole number expectations:

O scores 52 on turns 1 and 3
P scores 8 on turns 2 and 4

and:

O scores 134 on turns 1 and 3
P scores 0 on turns 2 and 4

However a score of 134 can only be made by choosing marbles 53 (score = 52) and 83 (score = 82), so this cannot be repeated in the third turn. Hence the second candidate solution is eliminated.

But there are many ways to make the scores for the first candidate solution, for example:

O picks (7, 47); score = 6 + 46 = 52
→ 1230 points remaining; O’s expected total = 652; P’s expected total = 630.

P picks (3, 27); score = 2 + 6 = 8
→ 1222 points remaining; O’s expected total = 663; P’s expected total = 619.

O picks (11, 43); score = 10 + 42 = 52
→ 1170 points remaining; O’s expected total = 674; P’s expected total = 608.

P picks (8, 55); score = 2 + 6 = 8
→ 1162 points remaining; O’s expected total = 685; P’s expected total = 597.

In fact, when the game ends, P has scored the lowest possible total, which is 92 points, and so O has scored the remaining 1190 points.

LikeLike

Jim Randell 12:59 pm on 22 June 2024 Permalink | Reply

We can simplify this approach by just keeping a multiset (or bag(!)) of the possible scores, and then we don’t need to worry about the actual marbles chosen at all.

from enigma import (irange, isqrt, div, ediv, group, multiset, first, subsets, cproduct, call, printf)

# calculate the score for a marble
def score(n):
  for a in irange(isqrt(n), 1, step=-1):
    b = div(n, a)
    if b is not None: return abs(a - b)

# make a multiset of scores
scores = multiset.from_seq(score(x) for x in irange(1, 84))

# calculate total number of points
tot = scores.sum()

# scores for P and O (P has the lowest 42)
scoresP = multiset.from_seq(first(scores.sorted(), 42))
scoresO = scores.difference(scoresP)

# possible total scores for O and P in a turn
turnsO = group(scoresO.subsets(size=2), by=sum)
turnsP = group(scoresP.subsets(size=2), by=sum)

# check expected remaining points
def check_exp(r, *fs):
  try:
    return list(ediv(r * a, b) for (a, b) in fs)
  except ValueError:
    return None

# check scores can be made twice
def check_scores(sO, sP):
  for (ssO, ssP) in cproduct(subsets(xs, size=2, select='R') for xs in [turnsO[sO], turnsP[sP]]):
    if call(multiset.from_dict, ssO + ssP).issubset(scores):
      return True

# consider scores for O's first 2 turns
for sO in turnsO:
  # expected remaining points after turn 1 (41 remaining turns)
  if not check_exp(tot - sO, (20, 41), (21, 41)): continue

  # consider scores for P's first 2 turns
  for sP in turnsP:
    # expected remaining points after turn 2 (40 remaining turns)
    if not check_exp(tot - (sO + sP), (20, 40)): continue
    # expected remaining points after turn 3 (39 remaining turns)
    if not check_exp(tot - (sO + sP + sO), (19, 39), (20, 39)): continue
    # expected remaining points after turn 4 (38 remaining turns)
    es = check_exp(tot - (sO + sP + sO + sP), (19, 38))
    if not es: continue

    # check the turn scores can be made twice
    if not check_scores(sO, sP): continue

    # output solution candidate
    printf("expected total scores: O={tO} P={tP} [sO={sO} sP={sP}]", tO=sO + sO + es[0], tP=sP + sP + es[0])

LikeLike

Frits 11:35 am on 23 June 2024 Permalink | Reply

Just for fun:

g = {i: set() for i in range(84)}
for a in range(1, 85):
  for b in range(a, 0, -1):
    if a * b > 84 or any(a * b in g[i] for i in range(a - b)): continue
    g[a - b].add(a * b)
g = {k: vs for k, vs in g.items() if vs}    # remove empty items

@Jim, you don’t use the “ss” list so you could just yield True “if not OPs”.

LikeLike

Frits 8:40 pm on 21 June 2024 Permalink | Reply

There must be a smarter way of getting this solution.
The program runs in 350ms (PyPy).

 
from enigma import divisor_pairs
from itertools import combinations

# determine differences for "most square" integer factorisation
seq = [sorted(b - a for a, b in divisor_pairs(i))[0] for i in range(1, 85)]
# total of all scores
T = sum(seq)

P, O = [], []
# determine the lowest scores for Pam
for i, s, in enumerate(sorted(seq), 1):
  if i <= 42:
    P.append(s)
  else:  
    O.append(s)

sols = set()
# first turn for Oliver
for o12 in combinations(O, 2):
  # 20/41 * remaining is a whole number
  if (T - (sum_o12 := o12[0] + o12[1])) % 41: continue
  # first turn for Pam
  for p12 in combinations(P, 2):
    # 20/40 * remaining is a whole number
    if (T - (sum_p12 := p12[0] + p12[1]) - sum_o12) % 2: continue
    O_ = O.copy()
    for o in o12:
      O_.remove(o)
    # second turn for Oliver  
    for o34 in combinations(O_, 2):
      # 19/39 * remaining is a whole number
      if (T - (sum_o34 := o34[0] + o34[1]) - sum_o12 - sum_p12) % 39: continue
      # score for their second turn was the same as their first
      if sum_o34 != sum_o12: continue
      
      P_ = P.copy()
      for p in p12:
        P_.remove(p)
      for p34 in combinations(P_, 2):
        remaining = (T - (sum_p34 := p34[0] + p34[1]) - 
                     sum_o12 - sum_p12 - sum_o34)
        # 19/38 * remaining is a whole number
        # score for their second turn was the same as their first
        if remaining % 2 or sum_p34 != sum_p12: continue
        # Oliver's expected final score after Pamela’s second turn
        sols.add(str(sum_o12 + sum_o34 + remaining // 2))

print("answer:", ' or '.join(sols))

LikeLike

Frits 2:16 pm on 22 June 2024 Permalink | Reply

An easy performance improvement is to use keep2() in the combinations() lines.

# keep only a maximum of 2 occurences of a sequence item
keep2 = lambda seq: [b for a in [[x] * min(2, seq.count(x)) 
                     for x in sorted(set(seq))] for b in a]

LikeLike

Frits 7:19 am on 24 June 2024 Permalink | Reply

from itertools import combinations
 
seq = []
for n in range(1, 85):
  # find the two factors nearest to a square
  for a in range(int(n**.5), 0, -1):
    b, r = divmod(n, a)
    if r: continue
    seq.append(b - a) 
    break            
 
seq.sort()
T = sum(seq)                 # total of all scores
assert T % 2 == 0            # whole number expected score after 4th turn
P, O = seq[:42], seq[42:]    # points for Pam and Oliver
 
# sum of points of 2 marbles for Oliver that guarantees divisibility by 41
o_sums = [sm for i in range(5) 
          if sum(O[:2]) <= (sm := (T % 41) + 41 * i) <= sum(O[-2:])]
 
# indices of 2 marbles for Oliver that guarantees divisibility by 41
o_pairs = {sm: [(i1, i1 + i2 + 1) for i1, m1 in enumerate(O[:-1]) 
           for i2, m2 in enumerate(O[i1 + 1:]) if m1 + m2 == sm] 
           for sm in o_sums}
           
# reduce items if possible           
o_pairs = {k: vs for k, vs in o_pairs.items() if len(vs) > 1}      
o_sums = [sm for sm in o_sums if sm in o_pairs]    
 
# valid Oliver/Pam points that also guarantees divisibility by 39
# after the third turn and divisibility by 2 after the second turn
op_pts = [(o_pts, p_pts) for o_pts in o_sums 
          if (T - o_pts - (p_pts := (T - 2 * o_pts) % 39)) % 2 == 0]
 
sols = set()
# can solutions be formed by picking 4 different marbles per person
for o, p in op_pts:
  # pick 4 marbles for Oliver
  if not any(len(set(a + b)) == 4 for a, b in combinations(o_pairs[o], 2)):
    continue
   
  # indices of 2 marbles for Pam
  p_pairs = [(i1, i1 + i2 + 1) for i1, m1 in enumerate(P[:-1]) 
              for i2, m2 in enumerate(P[i1 + 1:]) if m1 + m2 == p]
  
  # pick 4 marbles for Pam
  if not any(len(set(a + b)) == 4 for a, b in combinations(p_pairs, 2)):
    continue
  
  # store Oliver's expected final score after Pamela's second turn
  sols.add(str(T // 2 + o - p))
 
print("answer:", ' or '.join(sols))

LikeLike

Jim Randell 8:19 am on 18 June 2024 Permalink | Reply
Tags: by: J S Rowley ( 9 )
Brain-Teaser 339: Cross country
From The Sunday Times, 5th November 1967 [link]

Tom, Dick and Harry had come up the school together and in three successive years had competed in the Junior, Colts and Senior, cross-country races.

Every year they finished in the same positions but interchanged so that no boy came in the same position twice. The same applied to the numbers on their vests, all six numbers being different, odd, and greater than 1.

When each boy multiplied his position number by the number he was wearing at the time, the nine results were all different and together totalled 841.

Dick beat the other two in the Junior race, but the number he was wearing was smaller than his position number; but he was wearing the highest card number in the Senior race, and this was [also] smaller than his position number.

Harry’s three products had a sum smaller than that of either of the other two.

What were the three boys’ positions in the Colts race and what numbers were they wearing?

This puzzle is included in the book Sunday Times Brain Teasers (1974). The puzzle text is taken from the book.

[teaser339]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 8:20 am on 18 June 2024 Permalink | Reply
  Let the finishing positions be (best to worst) (a, b, c), and the runner numbers be (smallest to largest) (x, y, z).
  
  These six numbers are all different, odd, and greater than 1.
  
  Taking the cartesian product of these sets we get:
  
  {a, b, c} × {x, y, z} = {ax, ay, az, bx, by, bz, cx, cy, cz}
  
  And for each boy in each race the product of his runner number and his finishing position gives a unique value, so they correspond directly with the 9 values produced by this cartesian product.
  
  The following Python program considers divisor pairs of 841, and then splits each divisor into 3 odd numbers meeting the requirements. We then use the [[ SubstitutedExpression() ]] solver from the enigma.py library to assign runner numbers and finishing positions in each race.
  
  The program runs in 116ms. (Internal runtime is 38ms).
```
from enigma import (SubstitutedExpression, divisors_pairs, decompose, div, cproduct, sprintf as f, join, printf)

# find 3 odd numbers that give the required total
def numbers(t):
  r = div(t - 3, 2)
  if r:
    for (a, b, c) in decompose(r, 3, min_v=1, sep=1):
      yield (2 * a + 1, 2 * b + 1, 2 * c + 1)

# solve for positions <pos>, numbers <num>
def solve(pos, num):
  # let the positions and numbers in the races be:
  #           pos   | num
  #           T D H | T D H
  #  junior:  A B C | D E F
  #  colt:    G H I | J K L
  #  senior:  M N P | Q R S

  # an expression to calculate the sum of products
  def fn(ps, ns):
    ps = join((f("pos[{x}]") for x in ps), sep=", ", enc="[]")
    ns = join((f("num[{x}]") for x in ns), sep=", ", enc="[]")
    return f("dot({ps}, {ns})")
  # construct an alphametic puzzle
  exprs = [
    # "D beat T and H in the junior race ..."
    "pos[B] < pos[A]",
    "pos[B] < pos[C]",
    # "... but his runner number was less than his position number"
    "num[E] < pos[B]",
    # "D has the largest runner number in the senior race ..."
    "num[R] > num[Q]",
    "num[R] > num[S]",
    # "... but his runner number was less than his position number"
    "num[R] < pos[N]",
    # "the sum of H's products were smaller than T's or D's"
    f("{H} < min({T}, {D})", T=fn("AGM", "DJQ"), D=fn("BHN", "EKR"), H=fn("CIP", "FLS")),
  ]
  p = SubstitutedExpression(
    exprs,
    base=3, # values are (0, 1, 2)
    distinct="ABC DEF GHI JKL MNP QRS AGM BHN CIP DJQ EKR FLS".split(),
    env=dict(pos=pos, num=num),
  )
  # solve the alphametic
  for s in p.solve(verbose=""):
    # output solution
    for (t, ps, ns) in zip(["junior", "colt  ", "senior"], ["ABC", "GHI", "MNP"], ["DEF", "JKL", "QRS"]):
      ((pT, pD, pH), (nT, nD, nH)) = ((pos[s[k]] for k in ps), (num[s[k]] for k in ns))
      printf("{t}: T (#{nT}) = {pT}; D (#{nD}) = {pD}; H (#{nH}) = {pH}")

# consider the values of (a + b + c) * (x + y + z)
for (p, q) in divisors_pairs(841, every=1):
  if p < 15 or q < 15: continue
  for (abc, xyz) in cproduct([numbers(p), numbers(q)]):
    # all numbers and products are different
    if len(set(abc + xyz)) != 6: continue
    if len(set(i * j for (i, j) in cproduct([abc, xyz]))) != 9: continue
    # solve the puzzle
    solve(abc, xyz)
```
  Solution: In the Colts race Tom (#15) finished 5th; Dick (#11) finished 7th; Harry (#3) finished 17th.
  
  The full results are:
  
  Junior: Tom (#11) = 17th; Dick (#3) = 5th; Harry (#15) = 7th
  Colts: Tom (#15) = 5th; Dick (#11) = 7th; Harry (#3) = 17th
  Senior: Tom (#3) = 7th; Dick (#15) = 17th; Harry (#11) = 5th
  
  In each race the runner numbers are #3, #11, #15 and the positions are 5th, 7th, 17th.
  
  And the sum of the nine different products of these numbers is:
  
  (3 + 11 + 15) × (5 + 7 + 17) = 29 × 29 = 841
  
  In fact the only viable factorisation of 841 is 29 × 29.
  
  LikeLike
Jim Randell 8:59 am on 16 June 2024 Permalink | Reply
Tags: by: J R Wowk
Brain-Teaser 959: A question of age
From The Sunday Times, 7th December 1980 [link]

The remarkable Jones family has a living male member, each directly descended, in five generations. At a recent reunion Ben, the genius of the family, made the following observations. After much deliberation, the rest of the Joneses agreed that these facts were indeed true.

Ben began: “If Cy’s great grandfather’s age is divided by Cy’s own age, it gives an even whole number, which, if doubled, gives Dan’s grandson’s age”.

“Eddy’s father’s age and his own have the same last digit. My great grandfather’s age is an exact multiple of my own, and if one year is taken away from that multiple it gives the age of my son”.

“Adam’s age, divided by that of his grandson, gives an even whole number which, when doubled, is his son’s age reversed. Furthermore, this figure is less than his grandfather’s age”.

All fathers were 18 or above when their children were born. Nobody has yet reached the age of 100.

Give the ages of the five named people in ascending order.

This puzzle is included in the book The Sunday Times Book of Brainteasers (1994).

[teaser959]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Frits, Lise Andreasen, and Jim Randell are discussing. Toggle Comments
- Jim Randell 9:01 am on 16 June 2024 Permalink | Reply
  The following Python program constructs a collection of alphametic expressions that give a viable puzzle, and then uses the [[ SubstitutedExpression() ]] solver from the enigma.py library to solve them.
  
  It runs in 156ms.
```
from enigma import (SubstitutedExpression, subsets, peek, sprintf as f, rev, seq2str, printf)

# choose ordering 0 = youngest to 4 = eldest
for (A, B, C, D, E) in subsets((0, 1, 2, 3, 4), size=len, select='P'):

  # construct a SubstitutedExpression recipe
  # symbols used for the ages:
  sym = lambda k, vs=['AB', 'CD', 'EF', 'GH', 'IJ']: peek(vs, k)
  try:
    exprs = [
      # "C's great-grandfather's age (C + 3) divided by C's age is an even whole number ..."
      f("div({x}, 2 * {y})", x=sym(C + 3), y=sym(C)),
      # "... which, if doubled, gives D's grandson's age (D - 2)"
      f("div(2 * {x}, {y}) = {z}", x=sym(C + 3), y=sym(C), z=sym(D - 2)),
      # "E's fathers age (E + 1) and E's age have the same last digit"
      f("{x} = {y}", x=sym(E + 1)[-1], y=sym(E)[-1]),
      # "B's great-grandfather's age (B + 3) is an exact multiple of B's ..."
      # "... and this multiple less 1 gives the age of B's son (B - 1)"
      f("div({x}, {y}) - 1 = {z}", x=sym(B + 3), y=sym(B), z=sym(B - 1)),
      # "A's age divided by the age of A's grandson (A - 2) is an even whole number ..."
      f("div({x}, 2 * {y})", x=sym(A), y=sym(A - 2)),
      # "... which, when doubled, is A's son's age (A - 1) reversed"
      f("div(2 * {x}, {y}) = {z}", x=sym(A), y=sym(A - 2), z=rev(sym(A - 1))),
      # "... and this value is less than A's grandfather's age (A + 2)"
      f("{z} < {x}", z=rev(sym(A - 1)), x=sym(A + 2)),
    ]
  except IndexError:
    continue
  # generation gap is at least 18
  exprs.extend(f("{y} - {x} >= 18", x=sym(i), y=sym(i + 1)) for i in (0, 1, 2, 3))

  # solve the puzzle
  p = SubstitutedExpression(exprs, distinct="", d2i={})
  for s in p.solve(verbose=""):
    # output ages
    ss = list(p.substitute(s, sym(i)) for i in (0, 1, 2, 3, 4))
    printf("ages = {ss} [A={A} B={B} C={C} D={D} E={E}]", ss=seq2str(ss), A=ss[A], B=ss[B], C=ss[C], D=ss[D], E=ss[E])
```
  Solution: The ages are: 3, 23, 48, 72, 92.
  
  Corresponding to:
  
  Cy = 3
  Ben = 23
  Adam = 48
  Eddy = 72
  Dan = 92
  
  And the given facts are:
  
  Cy’s great-grandfather = Eddy = 72
  divided by Cy = 3
  gives 72/3 = 24, an even whole number
  when doubled = 48 = Adam = Dan’s grandson.
  
  Eddy’s father = Dan = 92
  Eddy = 72, they have the same final digit.
  Ben’s great-grandfather = Dan = 92
  is 4 times Ben = 23
  and 4 − 1 = 3 = Cy = Ben’s son.
  
  Adam = 48
  divided by Adam’s grandson = Cy = 3
  gives 48/3 = 16, an even whole number
  when doubled = 32,
  reverse of Adam’s son = Ben = 23 is also 32.
  Furthermore 32 is less than Adam’s grandfather = Dan = 92.
  
  It turns out that the facts lead to a single possible ordering (youngest to eldest), which is: (C, B, A, E, D), so we only evaluate a single alphametic puzzle.
  
  LikeLike
- Lise Andreasen 4:00 pm on 16 June 2024 Permalink | Reply
  
  h - i denotes h is the father of i.
  (1) x - ? - ? - c (2) x/c = 2k, k integer. (3) d - ? - y (4) y = 4k (5) z - e (6) z and e have the same last digit. (7) u - ? - ? - b - v (8) u = bl, l integer. (9) v = l minus 1 (10) s - ? - a - r - w (11) a/w = 2m, m integer. (12) 4m is r reversed (13) 4m < s (14) d < 100 (15) h minus i >= 18 (16) Youngest >= 1 - assumption (7) and (10): ? - ? - a - b - ? Combine with (1): ? - ? - a - b - c Combine with (5): ? - e - a - b - c Only d is left: d - e - a - b - c As d and b are 3 generations apart: (17) d minus b >= 3 * 18 = 54 (15) and (16): (18) b >= 19 (8), (18) and (14): d = b * l 76 = 19 * 4 95 = 19 * 5 80 = 20 * 4 84 = 21 * 4 88 = 22 * 4 92 = 23 * 4 96 = 24 * 4 As (15) and (9), we can throw away solutions, where b minus l plus 1 < 18. That's 76, 95 and 80. 4m is b reversed. b reversed is 12, 22, 23 and 42. As 4 should divide this, throw away 22 and 42. That is, throw away 88 and 96. d = b * l, 4m, m 84 = 21 * 4, 12, 3 92 = 23 * 4, 32, 8 As (11), a/c= 2m. Further, (9), c = 3 So a is 6m, either 18 or 48. 18 < 21, won't work. As (4): k = 12 As (2): e/3 = 2 * 12 e = 72 So it has to be:
  d - e - a - b - c 92 - 72 - 48 - 23 - 3
  
  LikeLike
- Frits 2:23 pm on 18 June 2024 Permalink | Reply
  Python program to describe a manual solution.
```
'''
GGF(C) / C = even   (Ia), 2 * even = GS(D)           (Ib)
F(E) and E have the same last digit                  (II)
GGF(B) = k * B    (IIIa), S(B) = k - 1               (IIIb)
A / GS(A) = even   (IVa), 2 * even = reversed(S(A))  (IVb)
reversed(S(A)) < GF(A)                               (IVc) 
generation gap is at least 18                        (V) 
'''

# hierarchy [S, F, GF, GGF, GGGF]
hier = [set("ABCDE") for _ in range(5)]

# determine order
for i in range(2, 5): hier[i].remove('C')                 # (Ia)
for i in range(5): hier[i].discard('A'); hier[2] = {"A"}  # (IVa and IVc)
for i in range(5): hier[i].discard('B'); hier[1] = {"B"}  # (IIIa and IIIb)
hier[0] = {"C"}   # (Ia and hier[1] = B)
for i in [0, 1, 2, 4]: hier[i].discard('E');              # (II --> no 4)
hier[3] = {"E"}   # only place left for E
hier[4] = {"D"}   # what remains 

# D = k * B  (as GGF(B) = D), D >= 72, k = D / B > 2 as D - B >= 54
range_k = {i for i in range(3, 99 // 18 + 1)}

# as rev(B) is even (IVb) B must be 2. or 4. so k can't be 5
range_k -= {5} 
# E / C = A / 2  (Ia and Ib), so C can't be 2 and thus k can't be 3 (IIIb)
range_k -= {3} 
k = next(iter(range_k))                   # only one value remains
C = k - 1                                 # IIIb

# A is a multiple of 3 (IVa) and of 4 (Ib) thus also a multiple of 12
range_A = [a for a in range(C + 2 * 18, 100 - 38) if a % 12 == 0]
for A in range_A:
  E = C * A // 2                          # (Ia and Ib)
  for D in range(E + 20, 100, 10):
    B, r = divmod(D, k)                   # (IIIa)
    if r or not(C + 18 <= B <= A - 18): continue
    revB = int(str(B)[::-1])
    if revB != (2 * A) // C: continue     # (IVa and IVb)
    print("answer:", sorted([A, B, C, D, E]))     
```
  LikeLike
Jim Randell 4:40 pm on 14 June 2024 Permalink | Reply
Tags: by: Victor Bryant ( 144 )
Teaser 3221: Faulty towers
From The Sunday Times, 16th June 2024 [link] [link]

The famous “Tower of Hanoi” puzzle consists of a number of different-sized rings in a stack on a pole with no ring above a smaller one. There are two other poles on which they can be stacked and the puzzle is to move one ring at a time to another pole (with no ring ever above a smaller one) and to end up with the entire stack moved to another pole.

Unfortunately I have a faulty version of this puzzle in which two of the rings are of equal size. The minimum number of moves required to complete my puzzle (the two equal rings may end up in either order) consists of four different digits in increasing order.

What is the minimum number of moves required?

[teaser3221]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 4:52 pm on 14 June 2024 Permalink | Reply
  See also: Teaser 1858 and Enigma 14.
  
  I re-used the [[ H() ]] function from Teaser 1858 to calculate the number of moves required for a configuration of discs.
  
  This Python program runs in 65ms. (Internal runtime is 421us).
```
from enigma import (Accumulator, irange, inf, nsplit, is_increasing, printf)

# number of moves for sequence of discs (largest to smallest)
def H(ns):
  t = 0
  m = 1
  for n in ns:
    t += m * n
    m *= 2
  return t

# consider numbers of different size discs
for n in irange(1, inf):
  r = Accumulator(fn=min)
  # duplicate one of the discs
  for i in irange(n):
    ns = [1] * n
    ns[i] += 1
    # calculate the number of moves
    t = H(ns)
    # answer is a 4 digit number consisting of strictly increasing digits
    if 999 < t < 10000 and is_increasing(nsplit(t), strict=1):
      printf("{ns} -> {t}")
    r.accumulate(t)
  if r.value >= 6789: break
```
  Solution: The minimum number of moves required is 1279.
  
  The arrangement of discs is:
  
  There are 11 discs (of 10 different sizes) and discs 9 and 10 (counting from the bottom) are the same size.
  
  So the number of moves is:
  
  1×1 + 1×2 + 1×4 + 1×8 + 1×16 + 1×32 + 1×64 + 1×128 + 2×256 + 1×512 = 1279
  
  With analysis:
  
  The number of moves for a standard “Tower of Hanoi”, is the sum of the powers of 2 corresponding to each disc.
  
  So for a tower of 4 discs we would have:
  
  1 + 2 + 4 + 8 = 15 moves
  
  When one of the discs is duplicated we also duplicate one of the powers of 2, and this gives us a 4-digit increasing number (the smallest is 1234, and the largest 6789).
  
  So our starting tower must have between 10 and 12 different sizes.
  
  Summing the first n powers of 2:
  
  n=10: sum(1..512) = 1023
  n=11: sum(1..1024) = 2047
  n=12: sum(1..2048) = 4095
  
  And we need to duplicate one of the powers of 2 to give a number with (strictly) increasing digits:
  
  1023 + 256 = 1279
  2047 + 512 = 2559 (increasing, but not strictly increasing)
  
  LikeLike

Jim Randell 5:08 pm on 13 June 2024 Permalink | Reply
Tags: by: Graham Smithers ( 84 )

Teaser 2577: Number waves

From The Sunday Times, 12th February 2012 [link] [link]

I challenged Sam to find a 9-digit number using all of the digits 1 to 9, such that each digit occupying an even position was equal to the sum of its adjacent digits. (For example, the digit occupying position four would be equal to the sum of the digits occupying positions three and five). Sam produced a solution that was exactly divisible by its first digit, by its last digit, and by 11.

What was his number?

[teaser2577]

Jim Randell 5:08 pm on 13 June 2024 Permalink | Reply

Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

It runs in 77ms. (Internal runtime of the generated program is 230µs).

#! python3 -m enigma -rr

# suppose the number is: ABCDEFGHI
#                  pos = 123456789

SubstitutedExpression

--digits="1-9"

# even positions are the sum of the adjacent digits
"A + C = B"
"C + E = D"
"E + G = F"
"G + I = H"

# solution is divisible by A, I and 11
"ABCDEFGHI % A = 0"
"ABCDEFGHI % I = 0"
"ABCDEFGHI % 11 = 0"

--answer="ABCDEFGHI"

Solution: Sam’s number was: 143968275.

LikeLike

Ruud 7:49 pm on 15 June 2024 Permalink | Reply

No a priori knowledge, just brute force:

from istr import istr

for i in istr.concat(istr.permutations(istr.digits("1-"), 9)):
    if (
        i[1] == i[0] + i[2]
        and i[3] == i[2] + i[4]
        and i[5] == i[4] + i[6]
        and i[7] == i[6] + i[8]
        and i.divisible_by(11)
        and i.divisible_by(i[0])
        and i.divisible_by(i[8])
    ):
        print(i)

Note that this requires the latest-soon to be published- version of istr.

LikeLike

GeoffR 6:56 pm on 13 June 2024 Permalink | Reply


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

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

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

var 123456789..987654321:N == a*pow(10,8) + b*pow(10,7) + c*pow(10,6) 
+ d*pow(10,5) + e*pow(10,4) + f*pow(10,3) + g*pow(10,2) + h*pow(10,1) + i;
 
constraint N mod a == 0;
constraint N mod i == 0;
constraint N mod 11 == 0;

constraint a + c == b /\ c + e == d /\ e + g == f /\ g + i ==h;

solve satisfy;
 
output [ "His number was " ++ show(N)];

% His number was 143968275
% ----------
% ==========
% Finished in 461 msec - Chuffed Solver

LikeLike

Frits 7:01 pm on 13 June 2024 Permalink | Reply

     
#! python3 -m enigma -r
 
# suppose the number is: ABCDEFGHI
#                  pos = 123456789
 
SubstitutedExpression
 
--digits="1-9"

# divisibility of 11 rule, abs(sum odd digits - sum even digits) is 0 or a 
# multiple of 11, sum odd: A + C + E + G + I, sum even: A + 2.(C + G + E) + I
 
"(11 if C + E < 11 else 22) - (C + E) = G"
 
# even positions are the sum of the adjacent digits
"A + C = B"
"C + E = D"
"E + G = F"
"G + I = H"
 
# solution is divisible by A and I
"ABCDEFGHI % A = 0"
"ABCDEFGHI % I = 0"
 
--answer="ABCDEFGHI"

LikeLike

Frits 9:23 pm on 13 June 2024 Permalink | Reply

You only need to know three digits (like the 1st, 3rd and 5th digits).

from functools import reduce

# convert digit sequences to number
d2n = lambda s: reduce(lambda x,  y: 10 * x + y, s)

dgts8 = set(range(1, 9))
dgts9 = dgts8 | {9}

for C in dgts8:
  for E in dgts8 - {C}:
    # 11 divisibility rule
    G = (11 if C + E < 11 else 22) - (C + E)
    D, F = C + E, E + G
    # different digits
    if len(r1 := dgts9 - {C, E, G, D, F}) != 4: continue
    for A in r1:
      B = A + C
      if len(r2 := sorted(r1 - {A, B})) != 2: continue
      H, I = r2[1], r2[0]
      if H != G + I: continue
      
      ABCDEFGHI = d2n([A, B, C, D, E, F, G, H, I])
      if ABCDEFGHI % A: continue
      if ABCDEFGHI % I: continue
      print("answer:", ABCDEFGHI)

LikeLike

Ruud 6:44 am on 16 June 2024 Permalink | Reply

This version does not require the divisible_by method:

from istr import istr

for i in istr.concat(istr.permutations(istr.digits("1-"), 9)):
    if i[1] == i[0] + i[2] and i[3] == i[2] + i[4] and i[5] == i[4] + i[6] and i[7] == i[6] + i[8] and i % 11 == 0 and i % i[0] == 0 and i % i[8] == 0:
        print(i)

LikeLike

Jim Randell 4:42 pm on 7 June 2024 Permalink | Reply
Tags: by: Angela Newing ( 39 )

Teaser 3220: Graffiti

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

Six pupils were in detention having been caught painting graffiti on the school wall. The teacher decided to show them some examples of abstract art and produced seven different pictures in order ABCDEFG for them to study for a few minutes. Teacher took them back, showed them again upside down and in random order, and asked them to write down which of ABCDEFG each one was.

The answers were:
Helen: A B C D E F G
Ian:   A B C F E D G
Jean:  A D F G C E B
Kevin: A D B F C E G
Lee:   A F C G E D B
Mike:  C A F B E D G
It transpired that each picture had been correctly identified by at least one pupil, and everyone had a different number of correct answers.

What was the correct order for the upside down ones?

[teaser3220]

Jim Randell 4:54 pm on 7 June 2024 Permalink | Reply

This Python program runs in 55ms. (Internal runtime is 786µs).

from enigma import (cproduct, seq_all_different, join, printf)

# guesses
guesses = "ABCDEFG ABCFEDG ADFGCEB ADBFCEG AFCGEDB CAFBEDG".split()

# count number of correct answers
correct = lambda xs, ys: sum(x == y for (x, y) in zip(xs, ys))

# consider possible correct orderings (each is correctly placed by someone)
for order in cproduct(set(xs) for xs in zip(*guesses)):
  if not seq_all_different(order): continue
  # each pupil got a different number of correct answers
  if not seq_all_different(correct(order, guess) for guess in guesses): continue
  # output solution
  printf("order = {order}", order=join(order))

Solution: The correct order was: C A F G E D B.

So the number of correct identifications for each pupil were:

H = 1 (E)
I = 2 (D E)
J = 3 (B F G)
K = 0
L = 4 (B D E G)
M = 5 (A C D E F)

There are factorial(7) = 5040 possible orders that the paintings could be presented in, but as we know that each must appear in the correct position for one of the pupils we only need to look for positions that have received a guess, and using the disjoint cartestian product of the possible positions brings the number of candidate orderings down to 15.

LikeLike

Jim Randell 10:21 am on 8 June 2024 Permalink | Reply

I had a look at a more efficient way to generate the disjoint cartesian product of a sequence of sets (where no value can appear in more than one position).

It is possible to implement this fairly directly using the [[ exact_cover() ]] function from the enigma.py library, but it was slightly faster to implement a specific algorithm.

The following Python program has an internal runtime of 331µs.

from enigma import (peek, seq_all_different, join, printf)

# guesses
guesses = "ABCDEFG ABCFEDG ADFGCEB ADBFCEG AFCGEDB CAFBEDG".split()

# count number of correct answers
correct = lambda xs, ys: sum(x == y for (x, y) in zip(xs, ys))

# disjoint cartestian product of a bunch of sets, any value may only appear in one position
def disjoint_cproduct(ss):
  ss = dict(enumerate(set(xs) for xs in ss))
  return _disjoint_cproduct(ss, [None] * len(ss))

# ss = remaining sets to process
# vs = selected values
def _disjoint_cproduct(ss, vs):
  # final slot?
  if len(ss) == 1:
    j = peek(ss.keys())
    for x in ss[j]:
      vs[j] = x
      yield tuple(vs)
  else:
    # choose a slot with the fewest options
    j = min(ss.keys(), key=(lambda j: len(ss[j])))
    for x in ss[j]:
      ss_ = dict((k, v.difference([x])) for (k, v) in ss.items() if k != j)
      vs[j] = x
      yield from _disjoint_cproduct(ss_, vs)

# consider possible correct orderings (each is correctly placed by someone)
for order in disjoint_cproduct(zip(*guesses)):
  # each pupil got a different number of correct answers
  if not seq_all_different(correct(order, guess) for guess in guesses): continue
  # output solution
  printf("order = {order}", order=join(order))

Expect to see [[ disjoint_cproduct() ]] appearing in the next update to enigma.py. (Note: It is available from version 2024-06-07).

LikeLike

Frits 6:41 pm on 7 June 2024 Permalink | Reply

guesses = "ABCDEFG ABCFEDG ADFGCEB ADBFCEG AFCGEDB CAFBEDG".split()
M, N = len(guesses), len(guesses[0])
 
# count number of correct answers
correct = lambda xs, ys: sum(x == y for (x, y) in zip(xs, ys))

# candidate correct pictures per slot
sols = sorted([(set(g[i] for g in guesses), i) for i in range(N)], 
               key=lambda x: len(x[0]))
# save the original order
order = [x[1] for x in sols]

# get a sequence of different pictures
def solve(ps, k, ss=[]):
  if k == 0:
    yield ss
  else:
    for n in ps[0][0]:
      if n in ss: continue
      yield from solve(ps[1:], k - 1, ss + [n])

# get a sequence of <N> different pictures     
for s in solve(sols, N):
  # put solution in the right order
  sol = ''.join(x for x, y in sorted(zip(s, order), key=lambda z: z[1]))
  # check for different numbers of correct answers
  if len(set(correct(sol, g) for g in guesses)) != M: continue
  print("answer", sol)

LikeLike

Frits 1:36 pm on 8 June 2024 Permalink | Reply

I assumed choosing slots with the fewest options was more efficient but without it the program is slightly faster. Jim’s disjoint_cproduct program is definitely faster compared to the version with “j = min(ss.keys())”.

LikeLike
- Ruud 7:24 pm on 8 June 2024 Permalink | Reply
  
  It’s because the number of combinations of 4 out of 15 is the same as the number of combinations of 11 out of 15. Both are 1365.
  
  LikeLike

Ruud 7:27 pm on 7 June 2024 Permalink | Reply

Here’s my version:

from itertools import permutations

guesses = ["A B C D E F G".split(), "A B C F E D G".split(), "A D F G C E B".split(), "A D B F C E G".split(), "A F C G E D B".split(), "C A F B E D G".split()]
for correct in permutations("A B C D E F G".split()):
    counts = set()
    for guess in guesses:
        count = sum(1 for c0, c1 in zip(correct, guess) if c0 == c1 and c0 != " ")
        counts.add(count)
    if len(counts) == 6:
        print(" ".join(correct))

LikeLike

Rob 5:39 pm on 16 June 2024 Permalink | Reply

Jim’s solution shows CAFGEBD provides Jean (ADFGCEB) with 3 correct matches (BFG). It seems there are only 2 correct matches (BF) in which case the solution does not meet the criterion of “everyone having a different number of correct answers”
The correct solution is CAFGEDB

LikeLike

Jim Randell 5:20 pm on 6 June 2024 Permalink | Reply
Tags: by: Danny Roth ( 87 )

Teaser 2573: Prime cricketers

From The Sunday Times, 15th January 2012 [link] [link]

George and Martha support their local cricket team and keep records of all the results. At the end of last season, they calculated the total number of runs scored by each of the 11 players. George commented that the totals were all different three-digit palindromic primes. Martha added that the average of the 11 totals was also a palindromic prime.

What were the two highest individual totals?

[teaser2573]

Jim Randell 5:21 pm on 6 June 2024 Permalink | Reply

Very straightforward constructive solution.

This Python program runs in 57ms. (Internal runtime is 877µs).

from enigma import (primes, is_npalindrome, subsets, div, printf)

# 3-digit palindromic primes
scores = list(n for n in primes.between(100, 999) if is_npalindrome(n))

# choose 11 different scores
for ss in subsets(scores, size=11):
  # calculate the mean
  avg = div(sum(ss), 11)
  # which is also in scores
  if avg and avg in scores:
    # output solution
    printf("{avg} -> {ss}")

Solution: The two highest individual totals are 787 and 919.

The full list of totals is:

101, 131, 151, 181, 191, 313, 353, 373, 383, 787, 919
mean = 353

LikeLike

Ruud 6:41 pm on 6 June 2024 Permalink | Reply

Very similar to @Jim Randell’s solution, but without enigma:

import sympy
from itertools import combinations

palindromic_primes_with_length_3 = []
for i in range(1, 1000):
    prime = sympy.prime(i)
    prime_as_str = str(prime)
    if len(prime_as_str) > 3:
        break
    if len(prime_as_str) == 3 and str(prime_as_str) == str(prime_as_str)[::-1]:
        palindromic_primes_with_length_3.append(prime)

solutions = set()
for scores in combinations(palindromic_primes_with_length_3, 11):
    average_score = sum(scores) / 11
    if average_score in palindromic_primes_with_length_3:
        solutions.add((scores, int(average_score)))
print(solutions)

LikeLike

Frits 11:28 am on 7 June 2024 Permalink | Reply

Sympy also has a primerange() method.

LikeLike

GeoffR 8:16 pm on 6 June 2024 Permalink | Reply


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

var 100..999:A; var 100..999:B; var 100..999:C; var 100..999:D;
var 100..999:E; var 100..999:F; var 100..999:G; var 100..999:H;
var 100..999:I; var 100..999:J; var 100..999:K; 

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

predicate is_prime(var int: x) = 
 x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) ((i < x) -> (x mod i > 0));
 
constraint A div 100 == A mod 10 /\ is_prime(A);
constraint B div 100 == B mod 10 /\ is_prime(B);
constraint C div 100 == C mod 10 /\ is_prime(C);
constraint D div 100 == D mod 10 /\ is_prime(D);
constraint E div 100 == E mod 10 /\ is_prime(E);
constraint F div 100 == F mod 10 /\ is_prime(F);
constraint G div 100 == G mod 10 /\ is_prime(G);
constraint H div 100 == H mod 10 /\ is_prime(H);
constraint I div 100 == I mod 10 /\ is_prime(I);
constraint J div 100 == J mod 10 /\ is_prime(J);
constraint K div 100 == K mod 10 /\ is_prime(K);

var 1000..9999:asum;
var 100..999:average;

constraint asum  == A+B+C+D+E+F+G+H+I+J+K;
constraint average == asum div 11 /\ asum mod 11 == 0;

constraint is_prime(average);

constraint card( {average} intersect {A,B,C,D,E,F,G,H,I,J,K}) == 1;

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

solve satisfy;

output["Scores are " ++ show([A,B,C,D,E,F,G,H,I,J,K])
++ "\n" ++ "Average = " ++ show(average) ];

% Scores are [101, 131, 151, 181, 191, 313, 353, 373, 383, 787, 919]
% Average = 353
% ----------
% ==========

LikeLike

GeoffR 9:39 am on 7 June 2024 Permalink | Reply

Shorter code, but still slow.

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

% Eleven cricket scores
var 100..999:A; var 100..999:B; var 100..999:C; var 100..999:D;
var 100..999:E; var 100..999:F; var 100..999:G; var 100..999:H;
var 100..999:I; var 100..999:J; var 100..999:K; 
 
constraint all_different([A,B,C,D,E,F,G,H,I,J,K]);

var 100..999:average;
 
predicate is_pr_pal(var int: x) = 
 x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
 ((i < x) -> (x mod i > 0)) /\ x div 100 == x mod 10;
 
constraint sum([is_pr_pal(A), is_pr_pal(B),is_pr_pal(C), is_pr_pal(D),
 is_pr_pal(E), is_pr_pal(F), is_pr_pal(G), is_pr_pal(H),
 is_pr_pal(I), is_pr_pal(J), is_pr_pal(K)]) == 11;
   
constraint average == (A+B+C+D+E+F+G+H+I+J+K) div 11
/\ (A+B+C+D+E+F+G+H+I+J+K) mod 11 == 0;
 
constraint is_pr_pal(average);
 
constraint card( {average} intersect {A,B,C,D,E,F,G,H,I,J,K}) == 1;
 
constraint increasing( [A,B,C,D,E,F,G,H,I,J,K]);
 
solve satisfy;
 
output["Scores are " ++ show([A,B,C,D,E,F,G,H,I,J,K])
++ "\n" ++ "Average = " ++ show(average) ];

LikeLike

GeoffR 9:57 pm on 6 June 2024 Permalink | Reply


from enigma import is_prime
from itertools import combinations

scores = [x for x in range(100,999) if is_prime(x) \
          if x // 100 == x % 10 ]

for s in combinations(scores, 11):
    av, r = divmod(sum(s), 11)
    if r != 0: continue
    if av in scores and av //100 == av % 10:
        print(f"Average = {av}")
        print(f"Scores = {s}")

LikeLike

Ruud 10:20 am on 7 June 2024 Permalink | Reply

You can leave out the av // 100 == av % 10 test in the final if condition, as that’d guaranteed by the membership of scores.

LikeLike

Frits 10:17 am on 7 June 2024 Permalink | Reply

Same number of iteratons. It also works if scores would have had exactly 11 items.

from itertools import combinations

# prime numbers from 101-999
P = [3, 5, 7]
P += [x for x in range(11, 100, 2) if all(x % p for p in P)]
P = [x for x in range(101, 1000, 2) if all(x % p for p in P)]
# 3-digit palindromic primes
scores = {p for p in P if p // 100 == p % 10}
assert (ln := len(scores)) >= 11

t = sum(scores)

# choose scores outside the 11
for ss in combinations(scores, ln - 11):
  # calculate the average
  avg, r = divmod(t - sum(ss), 11)
  # which is also in scores
  if r or avg not in scores: continue
  print("answer", sorted(scores.difference(ss))[-2:])

LikeLike

Jim Randell 4:48 pm on 2 June 2024 Permalink | Reply
Tags: by: W A Thatcher ( 13 )
Brain-Teaser 443: Space ship
From The Sunday Times, 2nd November 1969 [link]

Says Bell at the pub:

I’ve been reading about a space ship. They fly the thing round playing the usual Cops and Robbers stuff, but the way they name the crew is interesting. Using A, B, C and so on right up to I, no gaps, they make, once only, every possible pair of different letters; so there’s no AA, BB and so on, and they take no notice of the order in a pair; s0 BC is the same as CB.

Four, including AD and BC, are on a list of officers and on that list no letter appears more than once. All the rest are just proles but do they have an A initial they call themselves A proles.

All proles work in shifts with the same number on each shift — not just two shifts; more than that — and at the end of a shift every prole hands over to another whose initials are each one farther on in the alphabet than his own, so AB would hand over to BC. Of course I is followed by A.

The shifts are picked so that when all shifts have been worked, every prole has been on duty once only.

Now you tell me who’s on the first shift. I want the biggest possible list. Easier than it looks. Usual prize. One pint.

Which A proles, if any, are on the first shift?

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

[teaser443]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 4:48 pm on 2 June 2024 Permalink | Reply
  A manual solution follows from a bit of analysis:
  
  There are C(9, 2) = 36 names, and 4 officers, so there are 32 proles, which we must form into shifts, and we want the shifts to be as large as possible (and more than 2 of them).
  
  So we are looking at:
  
  4 shifts, each of 8 proles; or:
  8 shifts, each of 4 proles
  
  If we start with a name we can consider the successor names until we get back to where we started, which forms the names into 4 groups:
  
  AB → BC → CD → DE → EF → FG → GH → HI → AI (→ AB) [adjacent letters]
  AC → BD → CE → DF → EG → FH → GI → AH → BI (→ AC) [separated by 1 letter (or 6)]
  AD → BE → CF → DG → EH → FI → AG → BH → CI (→ AD) [separated by 2 letters (or 5)]
  AE → BF → CG → DH → EI → AF → BG → CH → DI (→ AE) [separated by 3 letters (or 4)]
  
  Any officer (in bold) must be preceded by a member of the final shift and working backwards gives us members of previous shifts, giving a chain that is 8 long, which consists of 1 member for each of 8 shifts, or 2 members for each of 4 shifts.
  
  Each officer must appear in a different group, and as we have used ABCD, we must choose 2 officers from EFGHI.
  
  In the final group only EI is available to be an officer, so the remaining officer must be FH in the second group.
  
  And so we can construct 4 shifts, each of 8 proles:
  
  shift 4: (AB, EG, CI, DH) + (FG, AC, EH, DI)
  shift 3: (AI, DF, BH, CG) + (EF, BI, DG, CH)
  shift 2: (HI, CE, AG, BF) + (DE, AH, CF, BG)
  shift 1: (GH, BD, FI, AE) + (CD, GI, BE, AF)
  
  (And the two halves could be split to make 8 shifts, each of 4 proles = (1b, 2b, 3b, 4b, 1a, 2a, 3a, 4a)).
  
  Solution: AE and AF are on the first shift.
  
  Here is a program that performs the same steps:
  
  It runs in 64ms. (Internal runtime is 351µs).
```
from enigma import (
  irange, subsets, diff, tuples, repeat, join,
  intersect, disjoint_union, cache, printf
)

# letters
letters = "ABCDEFGHI"

# construct possible crew names
names = list(x + y for (x, y) in subsets(letters, size=2))

# constrict successor names
adj = dict(tuples(letters, 2, circular=1))
succ = cache(lambda xs: join((adj[x] for x in xs), sort=1))

# group names into successor chains
def group(names):
  while names:
    # make the chain for the next name
    g = list(repeat(succ, names[0], 8))
    yield g
    names = diff(names, g)

# collect groups
gs = list(group(names))

# choose an officer from each group
def officers(gs, offs=[]):
  # are we done?
  if not gs:
    yield offs
  else:
    g = gs[0]
    # AD and BC are officers
    xs = intersect([{'AD', 'BC'}, g])
    if not xs:
      # choose officers that don't include ABCD
      xs = list(x for x in g if not intersect(['ABCD', x]))
    # process the candidates
    for x in xs:
      offs_ = offs + [x]
      if disjoint_union(offs_):
        yield from officers(gs[1:], offs_)

# choose the officers
for offs in officers(gs):
  # find the first shift
  shift = set()
  for (g, off) in zip(gs, offs):
    j = g.index(off)
    shift.update(g[(j + i) % 9] for i in [-4, -8])
  shift = sorted(shift)
  # output shifts 1-4
  for k in irange(1, 4):
    printf("shift {k} = {shift}", shift=join(shift, sep=" "))
    if k == 4: break
    # hand on to the next shift
    shift = list(succ(x) for x in shift)
```
  LikeLike
Jim Randell 4:36 pm on 31 May 2024 Permalink | Reply
Tags: by: Howard Williams ( 44 )
Teaser 3219: Number funnel
From The Sunday Times, 2nd June 2024 [link] [link]

Betty, being a keen mathematician, has devised a game to improve her children’s maths additions. She constructed an inverted triangular tiling of hexagonal shapes, with nine hexagons in the top row, eight in the second row etc., reducing to one at the bottom. Then, completing the top row with 0s and 1s, she asks them to complete each row below by adding in each hexagon shape the numbers in the two hexagons immediately above it.

In the last game she noticed that if the top row is considered as a base-2 [binary] number, then this is exactly four and a half times the bottom total.

What is the bottom total?

[teaser3219]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
GeoffR, Hugo, Jim Randell, and 3 others are discussing. Toggle Comments
- Jim Randell 4:50 pm on 31 May 2024 Permalink | Reply
  If we suppose that the top row must have at least one of each binary digit present, then a single answer is found.
  
  This Python program runs in 64ms. (Internal runtime is 986µs).
```
from enigma import (irange, tuples, repeat, nsplit, ediv, peek, printf)

# process a row
process = lambda ns: list(x + y for (x, y) in tuples(ns, 2))

# consider possible start row values (must be a multiple of 9)
for n in irange(0, 511, step=9):
  # this is 4.5 times the target
  t = ediv(n * 2, 9)
  # perform the process
  top = nsplit(n, 9, base=2)
  bot = peek(repeat(process, top, 8), 8)
  if bot == [t]:
    # output solution
    printf("{n} -> {t}; {top} -> {bot}")
```
  Solution: The final total is 102.
  
  The initial row is the binary representation of 4.5 × 102 = 459, which gives the following rows:
  
  (1, 1, 1, 0, 0, 1, 0, 1, 1)
  (2, 2, 1, 0, 1, 1, 1, 2)
  (4, 3, 1, 1, 2, 2, 3)
  (7, 4, 2, 3, 4, 5)
  (11, 6, 5, 7, 9)
  (17, 11, 12, 16)
  (28, 23, 28)
  (51, 51)
  (102)
  
  LikeLike
  - Ruud 7:56 pm on 31 May 2024 Permalink | Reply
    This my version
```
from istr import istr

for s9 in istr.concat(istr.product((0, 1), repeat=9)):
    as_binary = int(s9, 2)
    if as_binary % 4.5 == 0:
        target = int(as_binary / 4.5)
        s = s9[:]
        while len(s) > 1:
            s = [i + j for i, j in zip(s, s[1:])]
        if s[0] == target:
            print(f'from {s9} to {target}')
```
    LikeLike
  - NigelR 11:11 am on 1 June 2024 Permalink | Reply
    No external dependencies and a recursive approach for the shapes. I started at the high end for the top row and worked down as it might have been faster if I’d stopped once a valid solution was found. As it is, it makes no difference but it confirms a unique solution.
```
#return bottom row from top row r
def blox(r):
  #are we at the bottom row?
  if len(r)==1: return r
  #find the next row down
  else: return blox(nxt(r))

#return next row down from list of current row
nxt = lambda r: [(r[i]+r[i+1]) for i in range(0,len(r)-1)]

#top row must be less than 512 and divisible by 9
for top in range (504,0,-9):
  r1 = [int(y) for y in format(top,'09b')]
  #have we found a solution?
  if (bot:=blox(r1)[0])*9/2 == top:
      print(f"top row was {top}, bottom row was {bot}")
```
    LikeLike
- Jim Randell 4:51 pm on 1 June 2024 Permalink | Reply
  Here is a solution based on a bit of analysis:
  
  We have:
  
  9 × (final value) = 2 × (binary interpretation of top row)
  
  And we can write each of these in terms of the 0,1 values in the top row.
  
  So we can extract the coefficients of these top row values in the equation:
  
  (9 × (final value)) − (2 × (binary interpretation of top row)) = 0
  
  Some of them are positive, and some of them are negative. (And it turns out there are 2 negative values and 7 positive values).
  
  So we assign 0,1 values to the variables in the top row with negative coefficients (there are only 3 interesting cases), and then try to express the resulting value using the 0,1 quantities of the positive values.
  
  We can address this manually, or programatically.
  
  The following program has an internal runtime of 250µs, so it is slightly faster (although more complicated) than just applying the procedure to each of the possible top row values:
```
from enigma import (irange, nCr, subsets, dot, express, nconcat, printf)

# we have: 9 * (final value) = 2 * (binary representation)

# calculate coefficients in the final value (= pascal_row(8))
pascal_row = lambda n: tuple(nCr(n, r) for r in irange(0, n))
pr8 = pascal_row(8)
lhs = tuple(9 * x for x in pr8)

# calculate coefficients in the binary representation
rhs = tuple(2**n for n in irange(9, 1, step=-1))

# calculate coefficients in <lhs> - <rhs> = 0
cs = tuple(a - b for (a, b) in zip(lhs, rhs))

# collect indices for positive and negative values
jps = sorted((j for (j, x) in enumerate(cs) if x > 0), key=cs.__getitem__)
jns = list(j for (j, x) in enumerate(cs) if x < 0)

# things we could work around, but don't need to
assert not (len(jns) > len(jps))
assert len(jps) + len(jns) == len(cs)
assert len(set(cs[j] for j in jps)) == len(jps)

# the positive and negative values
ps = list(cs[j] for j in jps)
ns = list(cs[j] for j in jns)

# choose 0,1 values for the negative values
for vs in subsets((0, 1), size=len(jns), select='M'):
  # calculate total for the negative values
  t = -dot(vs, ns)
  # express the same total using the positive values
  for qs in express(t, ps, qs=[0, 1]):
    # construct top row
    top = [None] * 9
    for (j, v) in zip(jns, vs): top[j] = v
    for (j, v) in zip(jps, qs): top[j] = v
    # output solution
    n = nconcat(top, base=2)
    bot = dot(top, pr8)
    printf("{top} {n} -> {bot}")
```
  Manually:
  
  We are looking to solve:
  
  −503a + −184b + 124c + 440d + 598e + 488f + 244g + 68h + 7i = 0
  
  The coefficients are all different, so we can uniquely identify a 0,1 valued variable with the corresponding coefficient.
  
  This boils down to choosing two subsets such that:
  
  sum(choose({503, 184})) = sum(choose({598, 488, 440, 244, 124, 68, 7}))
  
  There is a trivial solution where an empty set is chosen on both sides.
  
  Otherwise we have:
  
  LHS = 184 → not possible.
  LHS = 503 → not possible
  LHS = 184 + 503 = 687 → RHS = 488 + 124 + 68 + 7 = 687
  
  The final case corresponds to: a = 1, b = 1, c = 1, d = 0, e = 0, f = 1, g = 0, h = 1, i = 1.
  
  And so the top row is (1, 1, 1, 0, 0, 1, 0, 1, 1) and the bottom row is (102).
  
  LikeLike
  - Frits 5:42 pm on 2 June 2024 Permalink | Reply
    
    I needed to print the variables to see understand the method.
    I had forgotten that “dot” stands for “vector product”.
    
    Thanks for the “key=cs.__getitem__” construct. I didn’t know that.
    
    LikeLike
    - Jim Randell 10:27 am on 3 June 2024 Permalink | Reply
      @Frits: dict has the get() function which makes the equivalent look neater for dictionaries:
      
      # sort keys by value ks = sorted(d.keys(), key=d.get)
      
      Or I suppose you could use [[ key=(lambda i: seq[i]) ]] for sequences.
      
      LikeLike
  - Frits 11:19 pm on 2 June 2024 Permalink | Reply
    
    @Jim, is there a reason why express() doesn’t support negative quantities? The code would have been more compact.
    
    LikeLike
    - Jim Randell 8:02 am on 3 June 2024 Permalink | Reply
      
      @Frits: Allowing negative quantities should be possible, but in general there is no guarantee of termination if non-positive denominations are used in [[ express() ]].
      
      It feels like solving an integer equation where the variables take on (0, 1) values could have a specialised solver (I think an ILP solver would work). But I used [[ express() ]] in this instance to save having to write one.
      
      LikeLike
    - Frits 12:38 pm on 3 June 2024 Permalink | Reply
      A minimal modification to Enigma’s express_quantities() is sufficient to make this program work (assuming the denominations are ordered). I don’t see how this subroutine can keep running without terminating.
      
      from enigma import (irange, nCr, dot, nconcat, printf) # express total <t> using denominations <ds>, quantities chosen from <qs> def express_quantities(t, ds, qs, ss=[]): if any(x for x in ss) and t == 0: if not ds: yield ss elif 0 in qs: yield ss + [0] * len(ds) elif ds: d = ds[0] for q in qs: if d * q > t: break for r in express_quantities(t - d * q, ds[1:], qs, ss + [q]): yield r # we have: 9 * (final value) = 2 * (binary representation) # calculate coefficients in the final value (= pascal_row(8)) pascal_row = lambda n: tuple(nCr(n, r) for r in irange(0, n)) pr8 = pascal_row(8) lhs = tuple(9 * x for x in pr8) # calculate coefficients in the binary representation rhs = tuple(2**n for n in irange(9, 1, step=-1)) # calculate coefficients in <lhs> - <rhs> = 0 cs = tuple(a - b for (a, b) in zip(lhs, rhs)) # express the same total using the positive values for top in express_quantities(0, cs, qs=[0, 1]): # construct top row # output solution n = nconcat(top, base=2) bot = dot(top, pr8) printf("{top} {n} -> {bot}")
      
      LikeLike
      - Jim Randell 11:20 am on 4 June 2024 Permalink | Reply
        
        @Frits: But you asked about express() not express_quantities().
        
        Think about expressing a value using denominations of (-1, 0, +1) where you can use as many of each as you like.
        
        Of course with finite sets of denominations and quantities there is only a finite number of possible arrangements.
        
        LikeLike
  - Jim Randell 3:27 pm on 4 June 2024 Permalink | Reply
    Or, using a single call to express():
```
from enigma import (irange, nCr, express, nconcat, dot, printf)

# solve the binary equation: sum(n[i] * x[i]) = 0, for x[i] in [0, 1]
# return the sequences of binary x[] values
def solve(ns):
  # collect the coefficients (all different absolute values)
  m = dict()  # value -> index
  ts = set()  # set of negative values
  for (i, n) in enumerate(ns):
    assert n != 0  # coefficients must be non-zero
    k = abs(n)
    if n < 0: ts.add(k)
    m[k] = i
  ds = sorted(m.keys())
  assert len(ds) == len(ns)  # coefficients must all be different
  # express the sum of the negative values using 0,1 quantities
  for qs in express(sum(ts), ds, qs=[0, 1]):
    # return the values in the required order
    xs = [None] * len(ns)
    for (d, q) in zip(ds, qs):
      xs[m[d]] = (1 - q if d in ts else q)
    yield xs

# calculate coefficients for the final value (= pascal_row(8))
pascal_row = lambda n: tuple(nCr(n, r) for r in irange(0, n))
pr8 = pascal_row(8)
lhs = tuple(9 * x for x in pr8)

# calculate coefficients in the binary representation
rhs = tuple(2**n for n in irange(9, 1, step=-1))

# calculate coefficients in <lhs> - <rhs> = 0
ns = tuple(a - b for (a, b) in zip(lhs, rhs))

# solve the 0,1-equation with coefficients <ns> to give the top row
for top in solve(ns):
  # output solution
  n = nconcat(top, base=2)
  bot = dot(pr8, top)
  printf("{top} {n} -> {bot}")
```
    LikeLike
- Hugo 2:12 pm on 9 June 2024 Permalink | Reply
  
  If the numbers in the top row are a, b, c, d, e, f, g, h, i,
  then the value at the bottom has coefficients as given by the appropriate row of Pascal’s triangle: a + 8b + 28c + 56d + 70e + 56f + 28g + 8h + i.
  An exhaustive search is still needed, but my program (in Basic) found a solution immediately.
  
  This puzzle opens up the possibility of a whole family of puzzles, with factors other than 4.5. There could also be a different number of digits in the top row.
  
  Where do Jim’s negative values come from? The top row contains only 0s and 1s; each subsequent row is formed by addition, never subtraction.
  
  A further puzzle for me is Frits’ mention of dot for a vector product.
  I don’t speak Python, but normally dot is for a scalar product and cross for a vector product.
  
  LikeLike
- Hugo 8:48 am on 10 June 2024 Permalink | Reply
  
  I see now what Jim was doing: equating nine times the value of the bottom number and twice the value of the binary number, 256a + 128b + 64c + 32d + 16e + 8f + 4g + 2h + i.
  The mental leap was too much for me! I had evaluated them separately.
  
  LikeLike
- GeoffR 3:16 pm on 12 June 2024 Permalink | Reply
```
% A Solution in MiniZinc
include "globals.mzn";

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

var 1..512:top;
var 1..512:btm;

% top is abcdefghi in binary
constraint top == a*pow(2,8) + b*pow(2,7) + c*pow(2,6)
+ d*pow(2,5) + e*pow(2,4) + f*pow(2,3) + g*pow(2,2) + h*2 + i;

% 9th row Pascal Triangle coefficients
constraint btm == a + 8*b + 28*c + 56*d + 70*e + 56*f + 28*g + 8*h + i;

constraint 9 * btm == 2 * top;

solve satisfy;

output[ "Top row = " ++ show(top) ++
"\n" ++ "Bottom row = " ++ show(btm)];

% Top row = 459
% Bottom row = 102
% ----------
% ==========
```
  LikeLike
- GeoffR 4:15 pm on 14 June 2024 Permalink | Reply
  
  I tried this teaser with ChatGPT trying to find a solution. Despite several hints, it failed, as we have experienced previously.
  
  I have been experimenting using AI to write poetry in recent months, so I tried a poem for this teaser by feeding the teaser description as a prompt for the poem for ChatGPT. to generate a poem.
  
  It worked well – poem below:
  
  The Hexagon Puzzle – ST 3219
  =====================
  A Poem by ChatGPT
  
  In Betty’s realm, where numbers dance,
  A game of wit and math’s advance,
  Hexagons align in rows so neat,
  A challenge for young minds to meet.
  
  From nine at the top, they descend,
  Each row a puzzle to comprehend,
  Zeros and ones adorn the crest,
  A binary code, a numeric test.
  
  With eager eyes, her children trace,
  The patterns woven in this maze,
  Adding the pairs above with care,
  Unveiling sums, a secret to share.
  
  And as they reach the final row,
  A revelation starts to glow,
  The top row’s binary, a key so bright,
  Unlocks the bottom’s total, a wondrous sight.
  
  Four and a half times, the answer lies,
  A mathematical truth that never dies,
  In Betty’s game, where numbers reign,
  Hexagons persist, and minds retain.
  
  LikeLike

Jim Randell 11:05 am on 30 May 2024 Permalink | Reply
Tags: by: Victor Bryant ( 144 )

Brainteaser 1318: May I repeat?

From The Sunday Times, 6th December 1987 [link]

In this letters-for-digits puzzle, as usual, different letters consistently replace different digits. I have thought of a two-digit number and worked out a fraction (in its lowest form) involving my number. The recurring decimal which I get consists of infinite repeats, i.e.:

? / MY = 0. REPEAT REPEAT …

What is the value of PART?

[teaser1318]

Jim Randell 11:06 am on 30 May 2024 Permalink | Reply

This solution uses the [[ farey() ]] function from the enigma.py library, which generates co-prime pairs (i.e. the numerator and denominator of a fraction in its lowest terms), and then uses the [[ recurring() ]] function to determine the representation of the fraction as a recurring decimal.

It runs in 131ms. (Internal runtime is 55ms).

from enigma import (farey as coprime_pairs, recurring, format_recurring as fmt, printf)

# consider fractions a/b
for (a, b) in coprime_pairs(98):
  # b is 2 different digits
  if b < 10 or b % 11 == 0: continue
  # check repetend
  (i, nr, rr) = recurring(a, b)
  if nr or len(rr) != 6 or rr[1] != rr[3]: continue
  rs = set(rr)
  if len(rs) != 5 or rs.intersection(str(b)): continue
  # output solution
  PART = rr[2] + rr[4] + rr[0] + rr[5]
  printf("PART = {PART} [{a}/{b} = {f}]", f=fmt((i, nr, rr)))

Solution: PART = 8015.

The required fraction is:

5/39 = 0.(128205)…

LikeLike

Jim Randell 8:56 pm on 30 May 2024 Permalink | Reply

Here’s my solution based on the observation:

(MY / k) × REPEAT = 999999

(Although I don’t assume k is a single digit number).

It runs in 66ms. (Internal runtime is 502µs).

from enigma import (irange, divisor_pairs, gcd, nsplit, join, printf)

# (MY / k) * REPEAT = 999999

# MY is a 2-digit divisor of 999999
for (MY, r) in divisor_pairs(999999):
  if MY < 10 or MY % 11 == 0: continue
  if MY > 99: break
  # REPEAT is some multiple of r
  for k in irange(1, MY - 1):
    if gcd(k, MY) > 1: continue
    REPEAT = k * r
    ds = nsplit(REPEAT, 6)
    if ds[1] != ds[3]: continue
    ss = set(ds)
    if len(ss) != 5 or ss.intersection(nsplit(MY)): continue
    # output solution
    PART = join(ds[i] for i in (2, 4, 0, 5))
    printf("PART = {PART} [{k}/{MY} = 0.({REPEAT:06d})...]")

LikeLike

Frits 11:27 am on 31 May 2024 Permalink | Reply

Nice. Indeed, MY must be a divisor of 999999.

LikeLike

GeoffR 2:09 pm on 30 May 2024 Permalink | Reply


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

var 1..9:R; var 0..9:E; var 0..9:P; var 0..9:A;
var 0..9:T; var 1..9:X; var 1..9:M; var 0..9:Y;

constraint all_different([R,E,P,A,T,M,Y]);

var 10..99:MY == 10*M + Y;
var 100000..999999:REPEAT == 100000*R + 10100*E + 1000*P + 10*A + T;
var 1000..9999:PART == 1000*P + 100*A + 10*R + T;

% function ex Hakan Kjellerstrand 
function var int: gcd(var int: x, var int: y) =
  let {
    int: p = min(ub(x),ub(y));
    var 1..p: g;
    constraint
       exists(i in 1..p) (
          x mod i = 0 /\ y mod i = 0
          /\
          forall(j in i+1..p) (
             not(x mod j = 0 /\ y mod j = 0)
          ) /\ g = i);
  } in g;
  
constraint gcd(X, MY) == 1;

% As X/MY = 0.REPEATREPEAT..
% Multiplying both sides by 1,000,000 gives..
constraint 999999 * X == MY * REPEAT;

solve satisfy;

output ["PART = " ++ show(PART) ++ "\n"
++ "REPEAT = " ++ show(REPEAT) ++ "\n"
++ "X, MY =" ++ show([X, MY])];

% PART = 8015
% REPEAT = 128205
% X, MY =[5, 39]
% ----------
% ==========

LikeLike

Frits 6:41 pm on 30 May 2024 Permalink | Reply

Following GeoffR’s method.

 
from enigma import divisor_pairs

# 999999 * X == MY * REPEAT 
for X in range(1, 10):
  LHS = 999999 * X
 
  #  fraction X / MY is in its lowest form
  for MY, REPEAT in [(str(x), str(y)) for x, y in divisor_pairs(LHS)
                     if 9 < x < 100 and (x % X or X == 1)]:
    # letter E                 
    if REPEAT[1] != REPEAT[3]: continue
    # different letters
    if len(set(MY + REPEAT)) != 7: continue
   
    print(f"answer: {REPEAT[2]}{REPEAT[4]}{REPEAT[0]}{REPEAT[5]}")

LikeLike

Frits 11:15 am on 31 May 2024 Permalink | Reply

I did assume a 1-digit question mark. Line 9 should have been:
if 9 < x < 100 and gcd(x, X) == 1]:

LikeLike

Ruud 6:33 am on 31 May 2024 Permalink | Reply

Brute force with istr:

from istr import istr

for r, e, p, a, t, m, y in istr.permutations(istr.digits(), 7):
    if (m | y) * (r | e | p | e | a | t) % 999999 == 0:
        print(f"{m|y} / {r|e|p|e|a|t}")

LikeLike

Ruud 6:50 am on 31 May 2024 Permalink | Reply

Improved prints:

from istr import istr

for r, e, p, a, t, m, y in istr.permutations(istr.digits(), 7):
    if (m | y) * (r | e | p | e | a | t) % 999999 == 0:
        print(f"{(m | y) * (r | e | p | e | a | t) // 999999} / {m | y} =  0.{r | e | p | e | a | t}...")
        print(f"part = {p | a | r | t}")

LikeLike

Jim Randell 8:40 am on 31 May 2024 Permalink | Reply

@Ruud: How does this program ensure the fraction (?/MY) is in lowest terms?

LikeLiked by 1 person
- Ruud van der Ham 10:26 am on 31 May 2024 Permalink | Reply
  Ok, no guarantee.
  Better would be to do
```
for m, y, r, e, p, a, tin istr.permutations(istr.digits(), 7):
    if (m | y) * (r | e | p | e | a | t) % 999999 == 0:
        print(f"{(m | y) * (r | e | p | e | a | t) // 999999} / {m | y} =  0.{r | e | p | e | a | t}...")
        print(f"part = {p | a | r | t}")
        break
```
  Although my original code also just result in one solution.
  Alth
  
  LikeLike

Jim Randell 11:11 am on 28 May 2024 Permalink | Reply
Tags: by: Keith Austin ( 6 )

Brainteaser 1351: Letters find the largest

From The Sunday Times, 24th July 1988 [link]

Each letter stands for one of the two digits 1 and 2.

TEN is larger than SIX, which is larger than TWO, which is larger than ONE.

NINE is larger than FIVE, which is larger than FOUR, which is larger than ZERO.

EIGHT is larger than SEVEN, which is larger than THREE.

Which is the larger in each of the following pairs?

(a) ELEVEN and NINETY;
(b) TWENTY and EIGHTY;
(c) FIFTY and SIXTY;
(d) SEVENTY and HUNDRED;
(e) EIGHTY and NINETY?

[teaser1351]

Jim Randell 11:11 am on 28 May 2024 Permalink | Reply
Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

It runs in 80ms. (Internal runtime of the generated program is 122µs).
```
#! python3 -m enigma -rr

SubstitutedExpression

--digits="1,2"
--distinct=""

"TEN > SIX"
"SIX > TWO"
"TWO > ONE"

"NINE > FIVE"
"FIVE > FOUR"
"FOUR > ZERO"

"EIGHT > SEVEN"
"SEVEN > THREE"

--answer="(ELEVEN < NINETY, TWENTY < EIGHTY, FIFTY < SIXTY, SEVENTY < HUNDRED, EIGHTY < NINETY)"
--template=""
```
Solution: We have:

NINETY > ELEVEN
EIGHTY > TWENTY
FIFTY > SIXTY
SEVENTY > HUNDRED
NINETY > EIGHTY

The following letters have fixed values:

E=2, F=2, G=2, H=1, I=2, N=2, O=1, S=2, T=2, V=1, W=1, X=1, Z=1

And the letters D, L, R, U, Y can take on either value, and give rise to the 32 possible assignments.

So:

NINETY = 22222? > 2?2122 = ELEVEN
EIGHTY = 22212? > 21222? = TWENTY
FIFTY = 2222? > 2212? = SIXTY
SEVENTY = 221222? > 1?2??2? = HUNDRED
NINETY = 22222? > 22212? = EIGHTY

LikeLike

Ruud 3:51 pm on 28 May 2024 Permalink | Reply

Brute force solution:

from collections import defaultdict
from istr import istr

answers = defaultdict(set)
for t, e, n, s, i, x, w, o, f, v, r, z, g, h, u, l, y, d in istr.product((1, 2), repeat=18):
    if t | e | n > s | i | x > t | w | o > o | n | e:
        if n | i | n | e > f | i | v | e > f | o | u | r > z | e | r | o:
            if e | i | g | h | t > s | e | v | e | n > t | h | r | e | e:
                answers["a"].add(("ninety", "eleven")[e | l | e | v | e | n > n | i | n | e | t | y])
                answers["b"].add(("eighty", "twenty")[t | w | e | n | t | y > e | i | g | h | t | y])
                answers["c"].add(("sixty", "fifty")[f | i | f | t | y > s | i | x | t | y])
                answers["d"].add(("hundred", "seventy")[s | e | v | e | n | t | y > h | u | n | d | r | e | d])
                answers["e"].add(("ninety", "eighty")[e | i | g | h | t | y > n | i | n | e | t | y])

for letter, answer in answers.items():
    print(f"{letter}) {answer}")

LikeLike

Jim Randell 4:49 pm on 28 May 2024 Permalink | Reply
I get:
```
TypeError: tuple indices must be integers or slices, not istr
```
LikeLike
- Ruud 5:05 pm on 28 May 2024 Permalink | Reply
  
  @Jim Randell
  Sorry, I forgot to tell that you need istr 1.0.7 to run this code.
  
  LikeLike
  - Jim Randell 10:17 pm on 28 May 2024 Permalink | Reply
    
    @Ruud: Thanks. It works with the new version of istr.
    
    LikeLike

Ruud 8:19 am on 29 May 2024 Permalink | Reply

As some ‘Spielerei’, I did refactor my original istr-version.
It uses n2w module to convert ints to ‘spoken’ strings. With that and a helper function, I can formulate all the comparison statements as ints, which make more compact code.

A bit (?) overengineered, maybe …

from collections import defaultdict
from istr import istr
import n2w  # this module can convert an integer to a 'spoken' string
from functools import reduce, lru_cache


@lru_cache
def convert(number):
    """just as n2w.convert, but 100 is treated differenr]t as n2w.convert(100) is 'one hundred'"""
    return "hundred" if number == 100 else n2w.convert(number)


def a(number):
    """translates an int into an istr, using the global variables that define the letter value"""
    return reduce(lambda x, y: x | globals()[y], convert(number), istr(""))


def largest(number0, number1):
    return (convert(number1), convert(number0))[a(number0) > a(number1)]


answers = defaultdict(set)
for t, e, n, s, i, x, w, o, f, v, r, z, g, h, u, l, y, d in istr.product((1, 2), repeat=18):
    if a(10) > a(6) > a(2) > a(1):
        if a(9) > a(5) > a(4) > a(0):
            if a(8) > a(7) > a(3):
                answers["a"].add(largest(11, 90))
                answers["b"].add(largest(80, 20))
                answers["c"].add(largest(60, 50))
                answers["d"].add(largest(100, 70))
                answers["e"].add(largest(90, 80))

for letter, answer in answers.items():
    print(f"{letter}) {answer}")

LikeLike

Jim Randell 10:09 am on 29 May 2024 Permalink | Reply

All comparisons are between values of the same length, so we don’t need to convert the values into numbers, we can just use lexicographic ordering.

This Python program uses integer keys to refer to the words, but considers the values of the words with all 2^18 possible assignments of symbols, so is much slower than my solution using the [[ SubstitutedExpression ]] solver.

from enigma import (union, subsets, join, printf)

# words we are interested in (use numbers as short keys)
words = {
  10: 'TEN', 6: 'SIX', 2: 'TWO', 1: 'ONE',
  9: 'NINE', 5: 'FIVE', 4: 'FOUR', 0: 'ZERO',
  8: 'EIGHT', 7: 'SEVEN', 3: 'THREE', 50: 'FIFTY', 60: 'SIXTY',
  11: 'ELEVEN', 90: 'NINETY', 20: 'TWENTY', 80: 'EIGHTY',
  70: 'SEVENTY', 100: 'HUNDRED',
}

# answers we need to find (which is larger?)
qs = [(11, 90), (20, 80), (50, 60), (70, 100), (80, 90)]

# collect symbols used
syms = sorted(union(words.values()))

# collect answers
ans = set()
# assign the symbols to values
for vs in subsets('12', size=len(syms), select='M'):
  m = dict(zip(syms, vs))
  # map the words to values
  w = dict((k, join(m[x] for x in v)) for (k, v) in words.items())
  # check the conditions
  if (w[10] > w[6] > w[2] > w[1] and w[9] > w[5] > w[4] > w[0] and w[8] > w[7] > w[3]):
    # accumulate answers
    ans.add(tuple(max(a, b, key=w.get) for (a, b) in qs))

# output solution
for ks in ans:
  for (q, k) in zip("abcde", ks):
    printf("({q}) {k}", k=words[k])
  printf()

LikeLike

Jim Randell 4:31 pm on 24 May 2024 Permalink | Reply
Tags: by: Stephen Hogg ( 64 )
Teaser 3218: Algorithm Al
From The Sunday Times, 26th May 2024 [link] [link]

On his 35th birthday, maths teacher Al’s three younger half-sisters bought him “The Book of Numbers for Nerds” as a tease. It showed how to find right-angle triangles with whole-number sides using any two unequal odd square numbers. You take half their sum; half their difference; and the square root of their product to get the three sides. Any multiple of such a triplet would also work. He told his sisters this and that their ages were the sides of such a triangle. “Algorithm Al!” they yelled.

Knowing the age of any one sister would not allow you to work out the other ages with certainty, but in one case you could be sure of her place chronologically (youngest, middle or oldest).

Give the three sisters’ ages (youngest to oldest).

[teaser3218]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Frits and Jim Randell are discussing. Toggle Comments
- Jim Randell 5:33 pm on 24 May 2024 Permalink | Reply
  (See also: Teaser 3017).
  
  The construction of primitive Pythagorean triples in this way is known as Euclid’s formula [@wikipedia].
  
  This program collects Pythagorean triples with sides less than 35, and looks for triangles where all sides appear in more than one candidate triangle.
  
  Of the selected triangles we look for a side that can only appear in one specific position in the ordering (again, considering all candidate triangles). And this identifies the required answer.
  
  It runs in 63ms. (Internal runtime is 193µs).
```
from enigma import (
  defaultdict, pythagorean_triples, multiset, singleton, icount, printf
)

# collect possible triangles
tris = list(pythagorean_triples(34))

# record positions of each side
d = defaultdict(multiset)
for tri in tris:
  for (i, x) in enumerate(tri):
    d[x].add(i)

# check a candidate triangle
def check_tri(tri):
  # each side must appear in multiple triangles
  if not all(d[x].size() > 1 for x in tri): return
  printf("tri = {tri}; all sides occur in multiple triangles")
  # look for sides that can only appear in a single position
  for x in tri:
    k = singleton(d[x].distinct_elements())
    if k is not None:
      printf("-> {x} only appears in pos {k}")
      yield (x, k)

# check triangles, exactly one side appears in a single position
for tri in tris:
  if icount(check_tri(tri)) == 1:
    printf("=> SOLUTION: ages = {tri}")
```
  Solution: The three ages are: 15, 20, 25.
  
  There are just five primitive triangles we are interested in:
  
  euclid(1, 3) = (3, 4, 5)
  euclid(1, 5) = (5, 12, 13)
  euclid(1, 7) = (7, 24, 25)
  euclid(3, 5) = (8, 15, 17)
  euclid(3, 7) = (20, 21, 29)
  
  Candidate triangles are formed from these, along with multiples such that the largest side does not exceed 34.
  
  And the only candidate triangles where every side length occurs in another triangle are:
  
  (12, 16, 20) = (3, 4, 5) × 4
  (15, 20, 25) = (3, 4, 5) × 5
  
  And of these sides only 25 always appears as the largest side length:
  
  (7, 24, 25)
  (15, 20, 25)
  
  LikeLike
- Frits 5:55 pm on 24 May 2024 Permalink | Reply
  Following the instructions.
```
 
sols = set()
# odd squares
osqs = [i * i for i in range(1, 68, 2)]
for i, a in enumerate(osqs):
  if a > 33: break
  for b in osqs[i + 1:]:
    # calculate sister's ages
    p = (a + b) // 2
    if p > 34: break
    q = abs(a - b) // 2
    r = int((a * b) ** .5)
    # allow for multiples
    for k in range(1, 35):
      if any(x > 34 for x in [k * p, k * q, k * r]): break
      sols.add(tuple(sorted([k * p, k * q, k * r])))

sides = set(y for x in sols for y in x)
# dictionary of age appearing as y/m/o
d = {s: [sol.index(s) for sol in sols if s in sol] for s in sides}

# group of sisters that qualify
gs = [sol for sol in sols if all(len(d[s]) > 1 for s in sol)]
for sisters in gs:
  if sum([len(set(d[s])) == 1 for s in sisters]) == 1:  # in one case ...
    print("answer:", sisters)   
```
  LikeLike
Jim Randell 8:59 am on 21 May 2024 Permalink | Reply
Tags: by: R Postill ( 20 )
Brain-Teaser 350: Catering crisis
From The Sunday Times, 21st January 1968 [link]

The caterer at our Village Hall is in a quandary, as the Hall has been double-booked for next Saturday — by the Cricket Club and the Darts Club.

Unfortunately the matter cannot be resolved until the return of the Vicar on Saturday morning. He is quite unpredictable in such decisions, and the caterer must order the food by Friday.

The Cricketers want 100 sausage rolls and 60 meat pies; the Darts Club wants 50 sausage rolls and 90 meat pies.

The caterer is empowered to spend exactly £6.00. He buys sausage rolls at 3p and sells at 4p; meat pies cost him 5p and sell at 8p. Any left-overs are disposed of at a loss to a local prep school, which pays 2p per sausage roll and 3p a pie.

What should the caterer order so that he makes the best safe profit no matter which club gets the booking? And what will that profit be?

This puzzle is included in the book Sunday Times Brain Teasers (1974). The puzzle text is taken from the book.

[teaser350]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell, Frits, and Lise Andreasen are discussing. Toggle Comments
- Jim Randell 8:59 am on 21 May 2024 Permalink | Reply
  This Python program looks at possible orders of sausage rolls and pies that cost the caterer exactly 600p, and then the amount made if these supplies are available for each club, and records the minimum profit made in each case. We then look for the largest of these profits to find the answer to the puzzle.
  
  It runs in 58ms. (Internal runtime is 240µs).
```
from enigma import (Accumulator, express, printf)

# amount earned for supply <s>, demand <d>, price <p>, disposal price <x>
def amount(s, d, p, x):
  return (d * p + (s - d) * x if s > d else s * p)

# calculate amount earned for a supply (s, p) and a demand (S, P)
# of sausage rolls and pies
def earned(s, p, S, P):
  return amount(s, S, 4, 2) + amount(p, P, 8, 3)

# find the maximum profit
r = Accumulator(fn=max, collect=1)

# the caterer spends 600p
for (s, p) in express(600, [3, 5]):
  # calculate amount earned from each club
  C = earned(s, p, 100, 60)
  D = earned(s, p, 50, 90)
  # record profit
  r.accumulate_data(min(C, D), (s, p, C - 600, D - 600))

# output solution
for (s, p, C, D) in r.data:
  printf("{s} sausages rolls + {p} pies -> cricket = {C} / darts = {D}")
```
  Solution: The caterer should order 80 sausage rolls and 72 pies. Whichever club arrives he will make a profit of 236p.
  
  In the originally published puzzle pre-decimal currency was used and the numbers were different:
  
  The Cricketers want 200 sausage rolls and 120 meat pies; the Darts Club wants 100 sausage rolls and 180 meat pies.
  
  The caterer is empowered to spend exactly £5 [= 1200 pence].
  
  And the answer is: 160 sausage rolls, 144 pies. The profit is 472 pence = £1, 19s, 4d.
  
  LikeLike
  - Frits 10:35 am on 21 May 2024 Permalink | Reply
    This program doesn’t assume that the caterer will spend exactly 600p.
```
   
from enigma import SubstitutedExpression, Accumulator

# invalid digit / symbol assignments
d2i = dict()
# try to spend close to 600p in order to maximize the profit
for dgt in range(0, 101):
  vs = set()
  if dgt < 50: vs.update('S')
  if dgt < 60: vs.update('P')
  if dgt > 90: vs.update('P')
  d2i[dgt] = vs

# the alphametic puzzle
p = SubstitutedExpression(
  [
    # expenditure close to the maximum
    "595 < S * 3 + P * 5 <= 600",
    # calculate profits for cricketers and darters
    "(pc := S + min(P, 60) * 3 - (P - 60) * 2 * (P > 60))",
    "(pd := min(S, 50) + P * 3 - (S - 50) * 1 * (S > 50))",
  ],
  answer="min(pc, pd), S, P",
  base=101,
  d2i=d2i,
  distinct="",
  reorder=0,
  verbose=0,    # use 256 to see the generated code
)

# find the maximum profit
r = Accumulator(fn=max).accumulate_from(ans for (_, ans) in p.solve())

# output solution
w, s, p = r.value
print(f"he should order {s} sausages and {p} pies for a profit of {w}p")
```
    LikeLike
    - Frits 10:32 am on 22 May 2024 Permalink | Reply
      
      Assuming that the caterer will spend exactly 600p and that the caterer will order a sensible amount of sausages S (50, 55, 60, …, 95, 100) the profit (if the cricketers get the booking) can be expressed as: 2.2 * S + 60 and 460 – 2.8 * S if the darters get the booking.
      
      As the first function is increasing and the latter is decreasing for S the safe profit will be maximized if 2.2 * S + 60 = 460 – 2.8 * S or S = 80.
      
      LikeLiked by 1 person
- Lise Andreasen 2:17 am on 22 May 2024 Permalink | Reply
  
  Interesting.
  
  I approached it differently and arrived at 100 sausage rolls and a profit of 280.
  
  https://onlinephp.io/c/47cce
  
  LikeLike
  - Lise Andreasen 2:23 am on 22 May 2024 Permalink | Reply
    
    Oh, hang on. Read the puzzle incorrectly.
    
    LikeLike
    - Lise Andreasen 2:25 am on 22 May 2024 Permalink | Reply
      
      Yeah. I get the correct result now.
      
      https://onlinephp.io/c/37baa
      
      LikeLike
    - Lise Andreasen 2:27 am on 22 May 2024 Permalink | Reply
      
      Read the numbers in an early version of this page?
      
      LikeLike
  - Jim Randell 12:44 pm on 24 May 2024 Permalink | Reply
    
    Sorry. For a short while the numbers were mixed up between the original puzzle and the version published in the book. The puzzle text now reflects the version from the book, rather than the originally published version.
    
    LikeLike
Jim Randell 8:04 am on 19 May 2024 Permalink | Reply
Tags: by: Oliver Anderson ( 3 )
Brainteaser 1315: The nineteenth hole
From The Sunday Times, 15th November 1987 [link]

A famous English mathematician, J.E. Littlewood, once posed the following puzzle:

Find a number N (sensibly the smallest) such that, if you shift the first digit to the end, the result is exactly one-and-a-half times N.

The solution to this being:

N = 1,176,470,588,235,294.

Professor Egghead has discovered a similar intriguing fact (not in his bath, nor sitting under a fruit-tree; but while relaxing in the club-house, after a round of golf). It is:

A smallest positive integer, M, such that, if one again shifts the leading digit to the end, the result is, this time, exactly just one half of M.

How many digits has M?

[teaser1315]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Frits and Jim Randell are discussing. Toggle Comments
- Jim Randell 8:11 am on 19 May 2024 Permalink | Reply
  See: Puzzle #180, Enigma 653, Enigma 924, Teaser 2565, Enigma 1036, Enigma 455, Enigma 1161 (but note these may reveal the answer to this puzzle).
  
  Normally a parasitic number [ @wikipedia ] involves multiplying the number by a(n integer) value by moving the final digit to the front.
  
  This puzzle moves the front digit to the end, so we are looking at the inverse of the process involved in parasitic numbers. So if we find a 2-parasitic number, we can start with it, move the front digit (back) to the end, and it is divided by 2.
  
  For this Python program I adapted my [[ parasitic() ]] function from Enigma 924 to deal with fractional multipliers, and this allows us to solve both problems mentioned in the puzzle text.
  
  This program runs in 59ms. (Internal runtime is 167µs).
```
from enigma import (irange, inf, div, ndigits, first, printf)

# find numbers such that moving the final digit to the front
# result in a multiplication of the original number by k/q
def parasitic(k, q=1, M=inf, base=10):
  assert k < q * base and q < k * base
  b = base * k - q

  # consider n digit numbers
  for n in irange(1, M):
    a = base**n * q - k
    m = base**(n - 1)
    # consider non-zero digits d
    for d in irange(1, base - 1):
      x = div(d * a, b)
      if x is not None and m * base > x >= m:
        yield base * x + d

# find numbers such that moving the first digit to the end
# result in a multiplication of the original number by p/q
# this is the same as finding a (q/p)-parasitic number
for (p, q) in [(3, 2), (1, 2)]:
  # find the lowest number
  for x in first(parasitic(q, p), 1):
    n = div(x * q, p)
    # output solution
    printf("[{p}/{q}] {n} * {p}/{q} = {x} [{k} digits]", k=ndigits(n))
```
  Solution: M has 18 digits.
  
  The smallest number is 210526315789473684.
  
  210526315789473684 × 1/2 = 105263157894736842
  
  Note that this is the repetend of 4/19 = 0.(210526315789473684)…
  
  If you don’t mind leading zeros we can apply the same procedure to the result (which also has 18 digits), to get:
  
  105263157894736842 × 1/2 = 052631578947368421
  
  See also: OEIS A337922, OEIS A146088.
  
  LikeLike
- Frits 3:24 pm on 19 May 2024 Permalink | Reply
```
  
# k-digit number n = fp = 2(10p + f) with 19p = (10^(k - 1) - 2)f
# 19p = a999...999b with a = f - 1 and b = 10 - 2f

for k in range(2, 99):
  for f in range(2, 6):
    # check for a multiple of 19
    if (p19 := f * 10**(k - 1) - 2 * f) % 19: continue
    s19 = str(p19)
    a = str(f - 1)
    b = str(10 - 2 * f)
    
    if s19[1:-1] == "9" * (k - 2) and (s19[0], s19[-1]) == (a, b):
      print("answer:", k)
      break
  else:
    continue
  break   
```
  LikeLike

	Jim Randell on Teaser 2438: [Nested quad…
	Jim Randell on Teaser 2438: [Nested quad…
	Jim Randell on Teaser 3315: Primal screa…
	Ruud on Teaser 3315: Primal screa…
	Frits on Teaser 3315: Primal screa…
	Ruud on Teaser 3315: Primal screa…
	Jim Randell on Teaser 3315: Primal screa…
	Jim Randell on Teaser 2443: [Phone masts…

Search

Recent Posts

Recent Comments

Archives

Categories

Subscribe

RSS Links

Site Stats

Meta

Recent Updates Page 14 Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 4:36 pm on 12 July 2024 Permalink | Reply Tags: by: Bernardo Recaman ( 6 )

Rate this:

Share:

Jim Randell 4:43 pm on 12 July 2024 Permalink | Reply

Tony Smith 12:01 pm on 13 July 2024 Permalink | Reply

Ruud 7:47 am on 13 July 2024 Permalink | Reply

Brian Gladman 9:13 am on 13 July 2024 Permalink | Reply

Ruud 9:31 am on 13 July 2024 Permalink | Reply

Reply Cancel reply

Jim Randell 9:46 am on 11 July 2024 Permalink | Reply Tags: by: R. Buchanan-Dunlop ( 2 )

Rate this:

Share:

Jim Randell 9:47 am on 11 July 2024 Permalink | Reply

GeoffR 1:22 pm on 11 July 2024 Permalink | Reply

ruudvanderham 1:26 pm on 11 July 2024 Permalink | Reply

Jim Randell 5:24 pm on 9 July 2024 Permalink | Reply Tags: by: Victor Bryant ( 144 )

Rate this:

Share:

Jim Randell 5:25 pm on 9 July 2024 Permalink | Reply

Ruud 12:40 pm on 10 July 2024 Permalink | Reply

Frits 9:19 pm on 10 July 2024 Permalink | Reply

Jim Randell 7:17 am on 11 July 2024 Permalink | Reply

Frits 8:09 am on 11 July 2024 Permalink | Reply

Jim Randell 3:06 pm on 11 July 2024 Permalink | Reply

GeoffR 7:31 pm on 9 July 2024 Permalink | Reply

GeoffR 3:34 pm on 10 July 2024 Permalink | Reply

GeoffR 11:51 am on 11 July 2024 Permalink | Reply

Frits 9:08 pm on 10 July 2024 Permalink | Reply

Jim Randell 4:27 pm on 5 July 2024 Permalink | Reply Tags: by: Colin Vout ( 38 )

Rate this:

Share:

Jim Randell 4:46 pm on 5 July 2024 Permalink | Reply

Ruud 7:31 am on 6 July 2024 Permalink | Reply

Jim Randell 4:32 pm on 28 June 2024 Permalink | Reply Tags: by: Peter Good ( 28 )

Rate this:

Share:

Jim Randell 4:53 pm on 28 June 2024 Permalink | Reply

Jim Randell 3:59 pm on 25 June 2024 Permalink | Reply Tags: by: Robin Nayler ( 16 )

Rate this:

Share:

Jim Randell 3:59 pm on 25 June 2024 Permalink | Reply

Frits 1:30 pm on 1 July 2024 Permalink | Reply

Jim Randell 2:21 pm on 3 July 2024 Permalink | Reply

Frits 2:55 pm on 3 July 2024 Permalink | Reply

Jim Randell 4:24 pm on 3 July 2024 Permalink | Reply

Jim Randell 8:43 am on 5 July 2024 Permalink | Reply

Frits 2:20 pm on 5 July 2024 Permalink | Reply

Frits 1:25 pm on 1 July 2024 Permalink | Reply

Ruud 3:12 pm on 1 July 2024 Permalink | Reply

Frits 5:27 pm on 1 July 2024 Permalink | Reply

Frits 5:44 pm on 1 July 2024 Permalink | Reply

Frits 9:26 pm on 18 July 2024 Permalink | Reply

Jim Randell 4:28 pm on 21 June 2024 Permalink | Reply Tags: by: Mark Valentine ( 17 )

Rate this:

Share:

Jim Randell 5:27 pm on 21 June 2024 Permalink | Reply

Jim Randell 12:59 pm on 22 June 2024 Permalink | Reply

Frits 11:35 am on 23 June 2024 Permalink | Reply

Frits 8:40 pm on 21 June 2024 Permalink | Reply

Frits 2:16 pm on 22 June 2024 Permalink | Reply

Frits 7:19 am on 24 June 2024 Permalink | Reply

Jim Randell 8:19 am on 18 June 2024 Permalink | Reply Tags: by: J S Rowley ( 9 )

Rate this:

Share:

Jim Randell 8:20 am on 18 June 2024 Permalink | Reply

Jim Randell 8:59 am on 16 June 2024 Permalink | Reply Tags: by: J R Wowk

Rate this:

Share:

Jim Randell 9:01 am on 16 June 2024 Permalink | Reply

Lise Andreasen 4:00 pm on 16 June 2024 Permalink | Reply

Jim Randell 4:36 pm on 12 July 2024 Permalink | Reply
Tags: by: Bernardo Recaman ( 6 )

Jim Randell 9:46 am on 11 July 2024 Permalink | Reply
Tags: by: R. Buchanan-Dunlop ( 2 )

Jim Randell 5:24 pm on 9 July 2024 Permalink | Reply
Tags: by: Victor Bryant ( 144 )

Jim Randell 4:27 pm on 5 July 2024 Permalink | Reply
Tags: by: Colin Vout ( 38 )

Jim Randell 4:32 pm on 28 June 2024 Permalink | Reply
Tags: by: Peter Good ( 28 )

Jim Randell 3:59 pm on 25 June 2024 Permalink | Reply
Tags: by: Robin Nayler ( 16 )

Jim Randell 4:28 pm on 21 June 2024 Permalink | Reply
Tags: by: Mark Valentine ( 17 )

Jim Randell 8:19 am on 18 June 2024 Permalink | Reply
Tags: by: J S Rowley ( 9 )

Jim Randell 8:59 am on 16 June 2024 Permalink | Reply
Tags: by: J R Wowk

Jim Randell 4:40 pm on 14 June 2024 Permalink | Reply
Tags: by: Victor Bryant ( 144 )

Jim Randell 5:08 pm on 13 June 2024 Permalink | Reply
Tags: by: Graham Smithers ( 84 )

Jim Randell 4:42 pm on 7 June 2024 Permalink | Reply
Tags: by: Angela Newing ( 39 )

Jim Randell 5:20 pm on 6 June 2024 Permalink | Reply
Tags: by: Danny Roth ( 87 )

Jim Randell 4:48 pm on 2 June 2024 Permalink | Reply
Tags: by: W A Thatcher ( 13 )

Jim Randell 4:36 pm on 31 May 2024 Permalink | Reply
Tags: by: Howard Williams ( 44 )