S2T2 | Solving Sunday Times Teasers

Recent Updates Page 13 Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 6:51 pm on 4 September 2024 Permalink | Reply
Tags: by: Angela Newing ( 39 )

Brainteaser 1047: Youth opportunities

From The Sunday Times, 22nd August 1982 [link]

Five of the shops in our local High Street sell cakes, electrical goods, greengrocery, hardware and shoes. Each decided recently take on two young assistants, one of each sex, from the Youth Opportunities Scheme.

These ten lucky youngsters include Hazel and Stephen, who live on either side of my house, and Eric from across the road. He gave me the following information:

The initials of the assistants’ forenames are all different from the initial of the shop in which they work. Moreover no boy works with a girl whose initial is the same as his own. In addition, Emma does not work with Henry, nor does she work in the shoe shop.

Henry doesn’t work the in the cake shop, Gordon is not in the hardware shop, Gwen is not in the shoe shop, and neither Charles nor Sheila work in the greengrocer’s.

If Carol works in the hardware shop, who sells the electrical goods?

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

[teaser1047]

Jim Randell 6:51 pm on 4 September 2024 Permalink | Reply

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

Most of the conditions can be dealt with using the [[ --distinct ]] and [[ --invalid ]] parameters.

The following run file executes in 70ms. (Internal runtime of the generated code is just 27µs).

Run: [ @jdoodle ]

#! python3 -m enigma -rr

SubstitutedExpression

# shops: 0 1 2 3 4  (= Cakes, Electricals, Greengrocers, Hardware, Shoes)
# boys:  Q R S T U  (= Charles, Eric, Gordon, Henry, Steven; in some order)
# girls: V W X Y Z  (= Carol, Emma, Gwen, Hazel, Shiela; in some order)

--base=5
# boys and girls have different initials
# but no-one works with someone with the same initial
--distinct="QRSTU,VWXYZ,QV,RW,SX,TY,UZ"

# no-one shares an initial with the shop
# Emma does not work in the shoe shop
# Gwen does not work in the shoe shop
# Henry does not work in the cake shop
# Gordon does not work in the hardware shop
# neither Charles nor Shiela work in the greengrocers
--invalid="0,QVS"   # C = 0
--invalid="1,RWZ"   # E = 1
--invalid="2,SXZT"  # G = 2
--invalid="3,TYQ"   # H = 3
--invalid="4,UZX"   # S = 4

# Carol works in the hardware shop
--assign="Y,0"

# Henry and Emma do not work together
"(Q != 3) or (V != 1)" "(S != 3) or (X != 1)"

--answer="((Q, R, S, T, U), (V, W, X, Y, Z))"
--template="(Q R S T U) (V W X Y Z)"
--solution=""

We can write additional Python code to format the output nicely:

from enigma import (SubstitutedExpression, printf)

# label shops and people
shops = "Cakes Electricals Greengrocers Hardware Shoes".split()
boys  = "Charles Eric Gordon Henry Steven".split()
girls = "Carol Emma Gwen Hazel Shiela".split()

# load the puzzle
p = SubstitutedExpression.from_file("teaser1047.run")

# solve the puzzle, and format solutions
for (bs, gs) in p.answers(verbose=0):
  for (s, (b, g)) in enumerate(zip(bs, gs)):
    printf("{s} = {b} + {g}", s=shops[s], b=boys[b], g=girls[g])
  printf()

Solution: Henry and Gwen work in the electrical goods shop.

The full solution is:

Cakes = Gordon + Shiela
Electricals = Henry + Gwen
Greengrocers = Steven + Emma
Hardware = Eric + Carol
Shoes = Charles + Hazel

LikeLike

Frits 10:35 am on 5 September 2024 Permalink | Reply

This is much more intuitive to me:

#! python3 -m enigma -r
 
SubstitutedExpression
 
# shops: 0 1 2 3 4  (= Cakes, Electricals, Greengrocers, Hardware, Shoes)
# boys:  Q R S T U  (= Charles, Eric, Gordon, Henry, Steven)
# girls: V W X Y Z  (= Carol, Emma, Gwen, Hazel, Sheila)
 
--base=5
# boys and girls have different initials
# but no-one works with someone with the same initial
--distinct="QRSTU,VWXYZ,QV,RW,SX,TY,UZ"
 
# no-one shares an initial with the shop
# Emma does not work in the shoe shop
# Gwen does not work in the shoe shop
# Henry does not work in the cake shop
# Gordon does not work in the hardware shop
# neither Charles nor Sheila work in the greengrocers
--invalid="0,QVT"   # C = 0
--invalid="1,RW"    # E = 1
--invalid="2,SXQZ"  # G = 2
--invalid="3,TYS"   # H = 3
--invalid="4,UZWX"  # S = 4
 
# Carol works in the hardware shop
--assign="V,3"
 
# Henry and Emma do not work together
"T != W"
 
--answer="((Q, R, S, T, U), (V, W, X, Y, Z))"
--template="(Q R S T U) (V W X Y Z)"
--solution=""

and

from enigma import (SubstitutedExpression, printf)
 
# label shops and people
shops = "Cakes Electricals Greengrocers Hardware Shoes".split()
boys  = "Charles Eric Gordon Henry Steven".split()
girls = "Carol Emma Gwen Hazel Sheila".split()
 
# load the puzzle
p = SubstitutedExpression.from_file("teaser/teaser1047.run")
 
# solve the puzzle, and format solutions
for (bs, gs) in p.answers(verbose=0):
  for i in range(5):
    b, g = boys[bs.index(i)], girls[gs.index(i)]
    print(shops[i], "=", b, "+", g)

LikeLike

Jim Randell 6:17 am on 1 September 2024 Permalink | Reply
Tags: by: Colin Vout ( 38 )
Teaser 3232: Digital processing
From The Sunday Times, 1st September 2024 [link] [link]

I divided 1 by 5 in base 7 in the following way. I started with 1, multiplied by the base (7), recorded the result on division by 5 as a digit (1), then used the remainder (2) to repeat the process until the remainder became 0 or the pattern was about to repeat. The result was 0.1254 with those four digits then repeating.

For some base no more than 20 I also calculated the result of dividing 1 by all numbers from 2 up to the base minus 1. With one of these divisors the result had the “digit” 14 at one point followed immediately by the “digit” 13. Some “digits” never occurred in the fractional part with any of these divisors.

What “digits” (in increasing order) never occurred?

[teaser3232]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Frits, Jim Randell, and GeoffR are discussing. Toggle Comments
- Jim Randell 6:36 am on 1 September 2024 Permalink | Reply
  We can use the [[ recurring() ]] function from the enigma.py library to calculate the expansion of a fraction in different bases. (Originally written for Enigma 1247).
  
  The following Python program runs in 69ms. (Internal runtime is 949µs).
```
from enigma import (irange, recurring, int2base, base2int, format_recurring, printf)

# look for digit X followed by digit Y
(X, Y) = (14, 13)  # {14}:{13} = "ED"

# examine reciprocals in base <b>
def solve(b, verbose=0):
  # look for subsequence X:Y
  i2b = lambda n: int2base(n, base=b)
  (ss, f) = (i2b(X) + i2b(Y), 0)
  # unused digits
  ds = set(i2b(n) for n in irange(0, b - 1))
  for k in irange(2, b - 1):
    (i, nr, rr) = recurring(1, k, base=b)
    if verbose: printf("[{b}] {k} -> {x}", x=format_recurring((i, nr, rr)))
    if ss in nr + rr + rr[:1]: f += 1
    ds.difference_update(nr, rr)
  if f:
    # output solution (using integer digits)
    ds = list(base2int(d, base=b) for d in ds)
    printf("base={b} -> unused digits = {ds}", ds=sorted(ds))

# consider bases up to 20
for b in irange(max(X, Y) + 1, 20):
  solve(b)
```
  Solution: The unused digits are: 0, 12, 15, 17.
  
  In base 18 the reciprocals from 1/2 to 1/17 have the following expansions:
  
  1/2 = 0.9
  1/3 = 0.6
  1/4 = 0.49
  1/5 = 0.(3AE7)…
  1/6 = 0.3
  1/7 = 0.(2A5)…
  1/8 = 0.249
  1/9 = 0.2
  1/10 = 0.1(E73A)…
  1/11 = 0.(1B834G69ED)… [this contains E followed by D]
  1/12 = 0.19
  1/13 = 0.(16GB)…
  1/14 = 0.1(52A)…
  1/15 = 0.1(3AE7)…
  1/16 = 0.1249
  1/17 = 0.(1)…
  
  The digits (from 0123456789ABCDEFGH) that do not occur in the fractional parts of these expansions are:
  
  0
  C = 12
  F = 15
  H = 17
  
  The puzzle limits us to bases up to 20, but the next solutions don’t occur until bases 58, 86, 142.
  
  LikeLike
  - Frits 3:00 pm on 2 September 2024 Permalink | Reply
    
    @Jim, Brian’s counting of the divisors that have the special subsequence is more pure than our approach (as it doesn’t say “With at least one of these divisors”).
    
    LikeLike
    - Jim Randell 4:11 pm on 2 September 2024 Permalink | Reply
      
      @Frits: Unless the puzzle is explicit about there being exactly one case, I usually take a relaxed interpretation where the finding of one case is sufficient (a logical existential quantification). In this puzzle we don’t need to use the strict interpretation of “exactly one”.
      
      However, if you want to use the strict interpretation you can simply change the test at line 18 of my program to [[ if f == 1: ]]. But it doesn’t change the answer to the puzzle.
      
      LikeLike
- Frits 10:44 am on 1 September 2024 Permalink | Reply
```
# does list <lst2> occur in list <lst1>
inList = lambda lst1, lst2: any(lst1[i:i + len(lst2)] == lst2
                                for i in range(len(lst1) - len(lst2) + 1))

# return digits in base b in the fraction k / b (where k < b)
# (not repeating decimals) 
def divide(b, k):
  r, s, rs = 1, [], set()
  while True:
    (d, r) = divmod(r * b, k)
    s.append(d)
    # break if no remainder or repeating decimals encountered
    if not r or r in rs: break
    rs.add(r)  
  return s 

# consider bases from 15 to 20 (base must be higher than 14)
for b in range(15, 21):
  found1413, seen = 0, set()
  for k in range(2, b): 
    dgts = divide(b, k)
    # does list [14, 13] occur in <dgts>?
    if inList(dgts, [14, 13]):
      found1413 = 1
    seen |= set(dgts)
    
  if found1413:
    print(f"answer: {sorted(set(range(b)).difference(seen))}")
```
  LikeLike
  - Jim Randell 11:31 am on 2 September 2024 Permalink | Reply
    @Frits: I don’t see how you can differentiate between recurring and non-recurring expansions returned by your [[ divide() ]] routine.
```
>>> divide(10, 18)
[0, 5]
>>> divide(10, 20)
[0, 5]
```
    Would your program spot the occurrence of adjacent digits D and 6 in the expansion of 1/15 in base 20?
    
    1/15 (base 20) = 0.1(6D)… = 0.16D6D6D…
```
>>> divide(20, 15)
[1, 6, 13]
```
    LikeLike
    - Frits 2:48 pm on 2 September 2024 Permalink | Reply
      @Jim, the divide function has been made with the comment “(where k less than b)” so the first question I don’t understand. I don’t think I need to differentiate between recurring and non-recurring except for the valid 2nd point you make (divide(20, 15)).
      
      Here is the adjustment (assuming we have have to scan for only 2 “digits”):
      
      # does list <lst2> occur in list <lst1> isSubList = lambda lst1, lst2: any(lst1[i:i + len(lst2)] == lst2 for i in range(len(lst1) - len(lst2) + 1)) # return "digits" in base b in the fraction 1 / k (where k < b) # (not repeating "decimals") def divide(b, k): assert b > k r, s, dct = 1, [], dict() while True: p = r (d, r) = divmod(r * b, k) s.append(d) if not r: return s # repeating "decimals" encountered? if r in dct: # also suffix first "digit" of repetend as we have to look # for a sequence of two "digits" return s if r == p else s + [dct[r]] dct[p] = d # consider bases from 15 to 20 (base must be higher than 14) for b in range(15, 21): found1413, seen = 0, set() for k in range(2, b): dgts = divide(b, k) # does list [14, 13] occur in <dgts>? if isSubList(dgts, [14, 13]): found1413 = 1 seen |= set(dgts) if found1413: print(f"answer: {sorted(set(range(b)).difference(seen))}")
      
      LikeLike
      - Jim Randell 4:15 pm on 2 September 2024 Permalink | Reply
        
        @Frits: It was the same point really. I was trying to show a case where the return value was obviously ambiguous. But I strayed outside the acceptable parameters of your function. I should have used a different example.
        
        LikeLike
- GeoffR 11:38 am on 2 September 2024 Permalink | Reply
  
  @Jim:
  Can you please show how the first paragraph works to get an answer of 0.1245 with th same repeating digits? (as the main teaser is the second paragraph)
  
  LikeLike
  - Jim Randell 12:02 pm on 2 September 2024 Permalink | Reply
    @GeoffR:
    
    Starting with 1 we perform the following calculations:
    
    (1 × 7) / 5 = 1 (remainder 2)
    (2 × 7) / 5 = 2 (remainder 4)
    (4 × 7) / 5 = 5 (remainder 3)
    (3 × 7) / 5 = 4 (remainder 1)
    
    At the end of these 4 steps we have written down 1254 and are about to start the next step with the remainder 1. But this is the same as the value we started with at the beginning, so we will just go through the same steps again.
    
    So the result is:
    
    1/5 [base 7] = 0. 1254 1254 1254 …
```
>>> recurring(1, 5, base=7)
Recurring(i='0', nr='', rr='1254')
```
    LikeLike
- Frits 9:07 pm on 4 September 2024 Permalink | Reply
  Limiting the calls to divide().
```
# return "digits" in base b in the fraction 1 / k (where k < b)
# (not repeating "decimals") 
def divide(b, k):
  assert b > k 
  r, s, dct = 1, [], dict()
  while True:
    p = r 
    (d, r) = divmod(r * b, k)
    s.append(d)
    if not r: 
      return s
    # repeating "decimals" encountered?  
    if r in dct: 
      # also suffix first "digit" of repetend as we have to look 
      # for a sequence of two "digits"
      return s if r == p else s + [dct[r]] 
    dct[p] = d
  
seq = [14, 13]

# consider bases to 20
for b in range(max(seq) + 1, 21):
  for k in range(2, b):   
    # 14 = (r * b) // k
    r1 = (seq[0] * k) // b + 1
    (d2, r2) = divmod(r1 * b, k)  
    if d2 != seq[0]: continue
    (d3, r3) = divmod(r2 * b, k) 
    # seq[0] has to be followed by seq[1]
    if d3 != seq[1]: continue
    
    # check if first specified item is one of the "digits" in the fraction
    dgts = divide(b, k)
    if seq[0] not in dgts: continue
    seen = set(dgts)
    for k2 in range(2, b): 
      if k2 == k: continue
      seen |= set(divide(b, k2))
      
    print(f"answer: {sorted(set(range(b)).difference(seen))}")  
    break
```
  LikeLike
Jim Randell 11:11 am on 29 August 2024 Permalink | Reply
Tags: by: Simon Massarella
Teaser 2592: Inventive inventories
From The Sunday Times, 27th May 2012 [link] [link]

It is known that there is just one 10-digit number that is “self-counting” in the sense that its first digit equals the number of 1s in it, the second digit equals the number of 2s in it, and so on, with the ninth digit equalling the number of 9s in it and the tenth digit equalling the number of 0s in it.

Similarly, a 9-digit number is “self-counting” if its first digit equals the number of 1s in it, the second digit equals the number of 2s in it, and so on, with the ninth digit equalling the number of 9s in it (and with the 0s remaining uncounted).

(a) What is the 10-digit self-counting number?
(b) What is the highest 9-figure self-counting number?

[teaser2592]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 11:12 am on 29 August 2024 Permalink | Reply
  This is puzzle is a variation on autobiographical numbers (or curious numbers), see: Puzzle #16, Enigma 476.
  
  Except in autobiographical numbers the digits (in order) usually count the number 0’s, then then numbers of 1’s, 2’s, etc.
  
  The following Python program runs in 386ms. (Internal runtime is 309ms).
```
from enigma import (irange, decompose, join, printf)

# generate self counting sequences
def self_counting(k):
  js = (1, 2, 3, 4, 5, 6, 7, 8, 9, 0)
  assert k == 10 or k in js
  # t of the k digits are counted
  for t in (irange(0, k) if k < 10 else [10]):
    # decompose the t digits into the k counted slots
    for ns in decompose(t, k, increasing=0, sep=0, min_v=0):
      # check the counting works
      if all(ns.count(j) == n for (j, n) in zip(js, ns)):
        yield ns

# find length 10 and 9 self counting numbers
for k in [10, 9]:
  for ns in self_counting(k):
    if (ns[0] == 0 and len(ns) > 1): continue  # skip leading zeros
    printf("[{k}] {ns}", ns=join(ns))
```
  Solution: (a) 2100010006; (b) 100000000.
  
  There is an additional self-counting sequence of size 9 and that is (0, 0, 0, 0, 0, 0, 0, 0, 0), but that does not give a viable 9-digit self-counting number (and even if it did we are looking for largest 9-digit self-counting number).
  
  The full list of self-counting sequences:
  
  1: 0, 1
  2: 00, 10
  3: 000, 100
  4: 0000, 1000
  5: 00000, 10000
  6: 000000, 100000
  7: 0000000, 1000000
  8: 00000000, 10000000
  9: 000000000, 100000000
  10: 2100010006
  
  If we bring the 0 to the front of the [[ js ]] array (at line 5), then we get the more usual base 10 autobiographical numbers.
  
  4: 1210, 2020
  5: 21200
  7: 3211000
  8: 42101000
  9: 521001000
  10: 6210001000
  
  And we see for the 10-digit self-counting number (where each of the digits is counted) we can calculate the 10-digit autobiographical number and move the leading digit to the end.
  
  LikeLike

Jim Randell 12:52 am on 25 August 2024 Permalink | Reply
Tags: by: Victor Bryant ( 144 ), flawed ( 55 )

Teaser 3231: In his prime

From The Sunday Times, 25th August 2024 [link] [link]

Once, on my grandson’s birthday, I asked him the following five questions:

1. How many days are there in this month?
2. How many Mondays are there in this month?
3. How many “prime” days (i.e. 2nd, 3rd, 5th, …) are there in this month?
4. How many of those prime days are Saturdays?
5. How many letters are there when you spell the month?

The total of the five answers was a prime number.

Then I asked him the same questions the next day. No answer was the same as for the day before, but again the total of the five answers was prime.

When I first asked the questions what was the month and day of the week?

As set this puzzle has multiple solutions. However there is a unique answer for the birthday of the grandson (month and day of month).

[teaser3231]

Jim Randell 1:30 am on 25 August 2024 Permalink | Reply

Assuming the grandson answers each of the questions correctly, if the answer to each question must be different from that of the previous day, then the next day must be in a different month to the birthday.

This Python program works backwards, considering the answers for pairs of adjacent months, until it finds the most recent viable solution. (Assuming the system locale is set to find appropriate day and month names).

It runs in 68ms. (Internal runtime is 2.8ms).

from datetime import (date, timedelta)
from enigma import (Record, repeat, inc, first, icount, primes, unpack, tuples, printf)

# increment of 1 day
day1 = timedelta(days=1)
# function to check the weekday of a date
weekday_is = lambda n: (lambda d, n=n: d.isoweekday() == n)

# answer the questions
def results(y, m):
  # days in the month
  ds = first(repeat(inc(day1), date(y, m, 1)), count=(lambda d, m=m: d.month == m))
  # 1. number of days in the month
  r1 = len(ds)
  # 2. number of Mondays
  r2 = icount(ds, weekday_is(1))
  # 3. number of prime days
  pds = list(d for d in ds if d.day in primes)
  r3 = len(pds)
  # 4. number of prime Saturdays
  r4 = icount(pds, weekday_is(6))
  # 5. number of letters in the month name
  r5 = len(ds[0].strftime('%B'))
  return (r1, r2, r3, r4, r5)

# generate result values going back in time
def generate(y, m):
  prev_month = unpack(lambda y, m: (y, m - 1) if m > 1 else (y - 1, 12))
  for (y, m) in repeat(prev_month, (y, m)):
    if y < 1753: break
    rs = results(y, m)
    t = sum(rs)
    yield Record(y=y, m=m, rs=rs, t=t, tprime=(t in primes))

# consider adjacent months for (next-day, birthday)
for (d1, d2) in tuples(generate(2024, 8), 2):
  # both totals are prime and no answers are the same
  if d1.tprime and d2.tprime and not any(x == y for (x, y) in zip(d1.rs, d2.rs)):
    # output solution
    nd = date(d1.y, d1.m, 1)
    bd = nd - day1
    printf("birthday = {bd} ({dow}) {d2.rs}; next day = {nd} {d1.rs}", dow=bd.strftime('%A'))
    break  # only need the most recent solution

Solution: The first time the questions were asked was on a Monday in February.

Actually on Monday, 29th February 2016.

The answers to the questions are: (29, 5, 10, 1, 8) giving a total of 53.

The next day is Tuesday, 1st March 2016.

And the answers to the questions are: (31, 4, 11, 2, 5) also giving a total of 53.

If we go further back the dates: Friday, 29th February 2008 and Saturday, 1st March 2008 also work.

And in fact all viable dates are Monday/Friday 29th February, and Tuesday/Saturday 1st March. So there are two possible answers to the puzzle.

The published solution is: “February, Monday or Friday (apologies for the multiple answers)”.

LikeLike

Jim Randell 10:27 am on 25 August 2024 Permalink | Reply

> [Frits suggests that solutions earlier than the most recent give the same answer]

@Frits: Are you sure?

LikeLike

Jim Randell 7:26 am on 26 August 2024 Permalink | Reply

I interpreted the condition “no answer was the same as for the day before” to mean that each answer given on the second day was different from the answer given to the same question on the previous day (and I think this is the most reasonable interpretation).

However, if we take this condition to mean that there were no values given as answers on the second day that had also been given as answers on the first day, then we do find a unique solution to the puzzle.

Here is my program adapted for this interpretation. (The condition at line 38 is changed).

from datetime import (date, timedelta)
from enigma import (Record, repeat, inc, first, icount, primes, unpack, tuples, intersect, printf)

# increment of 1 day
day1 = timedelta(days=1)
# function to check the weekday of a date
weekday_is = lambda n: (lambda d, n=n: d.isoweekday() == n)

# answer the questions
def results(y, m):
  # days in the month
  ds = first(repeat(inc(day1), date(y, m, 1)), count=(lambda d, m=m: d.month == m))
  # 1. number of days in the month
  r1 = len(ds)
  # 2. number of Mondays
  r2 = icount(ds, weekday_is(1))
  # 3. number of prime days
  pds = list(d for d in ds if d.day in primes)
  r3 = len(pds)
  # 4. number of prime Saturdays
  r4 = icount(pds, weekday_is(6))
  # 5. number of letters in the month name
  r5 = len(ds[0].strftime('%B'))
  return (r1, r2, r3, r4, r5)

# generate result values going back in time
def generate(y, m):
  prev_month = unpack(lambda y, m: (y, m - 1) if m > 1 else (y - 1, 12))
  for (y, m) in repeat(prev_month, (y, m)):
    if y < 1753: break
    rs = results(y, m)
    t = sum(rs)
    yield Record(y=y, m=m, rs=rs, t=t, tprime=(t in primes))

# consider adjacent months for (next-day, birthday)
for (d1, d2) in tuples(generate(2024, 8), 2):
  # both totals are prime and no answers are the same
  if d1.tprime and d2.tprime and not intersect([d1.rs, d2.rs]):
    # output solution
    nd = date(d1.y, d1.m, 1)
    bd = nd - day1
    printf("birthday = {bd} ({dow}) {d2.rs}; next day = {nd} {d1.rs}", dow=bd.strftime('%A'))

Note: Apparently this is not the interpretation intended by the setter. They just didn’t realise that there were multiple solutions to the puzzle.

LikeLike

Ruud 5:05 pm on 26 August 2024 Permalink | Reply

That’s an interesting interpretation that indeed leads to a unique solution.
In my code just change
if all(answer1 != answer2 for answer1, answer2 in zip(counts1, counts2)):
into
if set(counts1) & set(counts2) == set():
to get the unique result.

LikeLike

Frits 12:02 pm on 28 August 2024 Permalink | Reply

@Jim, please add a comment to explain the hardcoded 1753 value

LikeLike
- Jim Randell 12:09 pm on 28 August 2024 Permalink | Reply
  
  @Frits: See [ https://enigmaticcode.wordpress.com/2021/12/10/enigma-911-unlucky-for-some/#comment-11516 ]
  
  LikeLike

Ruud 1:13 pm on 25 August 2024 Permalink | Reply

It is obvious that the birthday must be at the end of a month to make the answer to the month name different. So we can just search by year/month. As the grandchild still has a living grandfather, I assume that the grandchild must be born after 1939. So I just check for all years between 1940 and 2024 and all months.

It turns out that there are 6 possible solutions in this timeframe. And the month is unique, but the day of the week is ambiguous (there are two possibilities).

import calendar


def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if not n & 1:
        return False

    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False
    return True


def counts(year, month):
    number_of_days = calendar.monthrange(year, month)[1]
    number_of_mondays = 0
    number_of_prime_days = 0
    number_of_prime_saturdays = 0
    weekday = calendar.weekday(year, month, 1)
    for day in range(1, number_of_days + 1):
        number_of_mondays += weekday == 0
        number_of_prime_days += is_prime(day)
        number_of_prime_saturdays += weekday == 5 and is_prime(day)
        weekday = (weekday + 1) % 7
    number_of_letters = len(calendar.month_name[month])
    return [number_of_days, number_of_mondays, number_of_prime_days, number_of_prime_saturdays, number_of_letters]


for year in range(2024, 1940, -1):
    for month in range(1, 13):
        counts1 = counts(year, month)
        if is_prime(sum(counts1)):
            next_month = (month % 12) + 1
            next_year = year + (month == 12)
            counts2 = counts(next_year, next_month)
            if is_prime(sum(counts2)):
                if all(answer1 != answer2 for answer1, answer2 in zip(counts1, counts2)):
                    day = calendar.monthrange(year, month)[1]
                    print(f"{calendar.month_name[month]:10} {calendar.day_name[calendar.weekday(year,month,day)]} ({year:4}-{month:02}-{day:02})")

LikeLike

Jim Randell 10:18 am on 22 August 2024 Permalink | Reply
Tags: by: L Poulter
Brain-Teaser 777: Feeler gauges
From The Sunday Times, 6th June 1976 [link]

I have half-a-dozen feeler gauges on a ring like keys on a key ring. They are attached in a certain order and by selecting a single gauge or combinations of adjacent gauges it is possible to measure from 1 thou to 31 thous of an inch in steps of 1 thou.

If I remove two adjacent gauges, replace them with a single gauge and rearrange the five on the ring I can now measure from 1 thou to 21 thous in steps of 1 thou with these five gauges by again selecting a single gauge or combinations of adjacent gauges.

What are the thicknesses of the gauges and the order of arrangement on the ring in each case? (Start with gauge of unit thickness and then its thinner neighbour for each of the sets).

[teaser777]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell and Frits are discussing. Toggle Comments
- Jim Randell 10:20 am on 22 August 2024 Permalink | Reply
  This is another puzzle involving magic circles (see: Teaser 1986, Enigma 985, Puzzle #171, Teaser: Circular Tour).
  
  This Python program uses the routines for generating magic circles of a specified size that I’ve previously developed for the other puzzles.
  
  It runs in 72ms. (Internal runtime is 4.2ms).
```
from magic_circles import magic_circle
from enigma import (cproduct, printf)

# make magic circles of size 5 and 6
(m5s, m6s) = (list(magic_circle(n)) for n in (5, 6))

# choose the circles
for (m5, m6) in cproduct([m5s, m6s]):

  # find the difference between the circles
  ds = set(m6).difference(m5)
  # there should be 2 adjacent items
  if not (len(ds) == 2): continue
  (d1, d2) = (m6.index(d) for d in ds)
  if not ((d1 - d2) % 6 in {1, 5}): continue

  # output solution
  printf("6 set = {m6}; 5 set = {m5}")
```
  Solution: The 6-set is: (1, 3, 2, 7, 8, 10). The 5-set is: (1, 3, 10, 2, 5).
  
  There is only one magic circle of size 5:
  
  (1, 3, 10, 2, 5)
  
  There are 5 magic circles of size 6:
  
  (1, 3, 6, 2, 5, 14) [*]
  (1, 3, 2, 7, 8, 10) [*]
  (1, 2, 5, 4, 6, 13)
  (1, 7, 3, 2, 4, 14)
  (1, 2, 7, 4, 12, 5)
  
  Only the ones marked [*] have 4 values in common with the size 5 magic circle, and only the second one has the two values to be removed in adjacent positions.
  
  LikeLike
  - Frits 10:28 am on 23 August 2024 Permalink | Reply
    
    @Jim, do you assume that all the gauges are of different widths? If not then the “2 adjacent items” code doesn’t seem to be accurate.
    
    LikeLike
    - Jim Randell 10:39 am on 23 August 2024 Permalink | Reply
      
      @Frits: With k gauges we can use them all together (1 way) or we can start with any of the k gauges and use between 1 and k − 1 of the gauges (going clockwise say).
      
      This gives a total of:
      
      n(k) = 1 + k(k − 1) = k^2 − k + 1
      
      possible selections.
      
      For k = 6 we get n(6) = 31 selections.
      
      So if we can measure all values between 1 and 31 all the selections must give different total values, in particular all the single gauges must give different values, and so they must all be different.
      
      Similarly for k = 5 we get n(5) = 21 selections.
      
      LikeLike
- Frits 4:53 pm on 22 August 2024 Permalink | Reply
  
  I discovered I already had some code stored on my PC for this puzzle.
  
  Arthur Vause has made a blog entry on this Brain Teaser:
  
  [https://arthurvause.blogspot.com/2014/06/feeler-gauges-and-magic-circles.html]
  
  LikeLike

Jim Randell 11:18 am on 20 August 2024 Permalink | Reply
Tags: by: J S Rowley ( 9 )

Brain Teaser: Circular tour

From Sunday Times Brain Teasers 1974 [link]

Arley, Barley, Carley, Darley, Earley and Farley are six villages connected, in that order, by a circular bus service. A passenger is allowed to board at any village and alight at any other or complete the whole circuit. The distances from any village to any other village on the route are all different and all an exact number of miles, consisting of every possible whole number from 1 mile up to the distance for the whole circuit.

Arley to Barley is 1 mile. The distance from Farley to Arley is greater than that from Barley to Carley but less than that from Earley to Farley.

What is the distance from Earley to Farley?

This puzzle is taken from the book Sunday Times Brain Teasers (1974), but it is not a puzzle that originally appeared in The Sunday Times.

[teaser-book-1974-p95]

Jim Randell 11:20 am on 20 August 2024 Permalink | Reply

We have encountered puzzles involving magic circles before (see: Teaser 1986, Enigma 985, Puzzle #171), and developed tools for generating them

This Python program considers magic circles of size 6, and then looks for ones that meet the specified requirements.

It runs in 75ms. (Internal runtime is 4.1ms).

from magic_circles import magic_circle
from enigma import printf

# look for a size 6 magic circle (including reflections)
for ds in magic_circle(6, refl=1):
  # distance AB = 1
  assert ds[0] == 1
  # distance EF > distance FA > distance BC
  if not (ds[4] > ds[5] > ds[1]): continue
  # output solution
  printf("distance EF = {ds[4]} [ds = {ds}]")

Solution: The distance from Earley to Farley is 12 miles.

And we have the following distances around the circle:

A→B = 1
B→C = 2
C→D = 7
D→E = 4
E→F = 12
F→A = 5

LikeLike

Ruud 2:09 pm on 21 August 2024 Permalink | Reply

A bit verbose and certainly very brute force:

import itertools

ab = 1
for bc, cd, de, ef, fa in itertools.permutations(range(2, 20), 5):
    ac = ab + bc
    ad = ac + cd
    ae = ad + de
    af = ae + ef
    bd = bc + cd
    be = bd + de
    bf = be + ef
    ba = bf + fa
    ce = cd + de
    cf = ce + ef
    ca = cf + fa
    cb = ca + ab
    df = de + ef
    da = df + fa
    db = da + ab
    dc = db + bc
    ea = ef + fa
    eb = ea + ab
    ec = eb + bc
    ed = ec + cd
    fb = fa + ab
    fc = fb + bc
    fd = fc + cd
    fe = fd + de

    if ef > fa > bc and af+fa == 31:
        if {ab, ac, ad, ae, af, bc, bd, be, bf, ba, cd, ce, cf, ca, cb, de, df, da, db, dc, ef, ea, eb, ec, ed, fa, fb, fc, fd, fe} == set(range(1, 31)):
            print(ab, ac, ad, ae, af, bc, bd, be, bf, ba, cd, ce, cf, ca, cb, de, df, da, db, dc, ef, ea, eb, ec, ed, fa, fb, fc, fd, fe)
            print(ef)

LikeLike

Lise Andreasen 10:27 pm on 20 August 2024 Permalink | Reply

So… The bus travels 31 miles on 1 circuit. And there’s also 2 villages, 31 miles apart on the circuit. Is this the distance from a village to itself?

LikeLike
- Jim Randell 8:14 am on 21 August 2024 Permalink | Reply
  
  That’s right. A complete circuit is 31 miles, but we can also travel all the distances between 1 and 30 miles.
  
  A→B = 1; B→A = 30
  B→C = 2; C→B = 29
  A→C = 3; C→A = 28
  D→E = 4; E→D = 27
  F→A = 5; A→F = 26
  F→B = 6; B→F = 25
  C→D = 7; D→C = 24
  F→C = 8; C→F = 23
  B→D = 9; D→B = 22
  A→D = 10; D→A = 21
  C→E = 11; E→C = 20
  E→F = 12; F→E = 19
  B→E = 13; E→B = 18
  A→E = 14; E→A = 17
  F→D = 15; D→F = 16
  
  LikeLike
  - Lise Andreasen 6:29 pm on 21 August 2024 Permalink | Reply
    
    Just an odd way to describe the 31 miles “distance”.
    
    “The distances from any village to any other village on the route are all different and all an exact number of miles, consisting of every possible whole number from 1 mile up to the distance for the whole circuit.”
    
    LikeLike

GeoffR 9:48 am on 21 August 2024 Permalink | Reply

There are 6 single trips between villages and 6 trips for each of 2,3,4 and 5 bus stops between villages e.g. AB, BC, CD, DE, EF, FA for single stops between villages. There is only 1 circular bus trip visiting all 6 villages i.e. AB + BC + CD + DE + EF + FA.
In total, therefore, there are 5 X 6 + 1 = 31 total bus trips.
This MiniZinc solution enumerates all possible bus trips.

% A Solution in MiniZinc
include "globals.mzn";
 
% Villages are A,B,C,D,E,F

% Assumed upper bounds of six distances between villages
var 1..15:AB; var 1..15:BC; var 1..15:CD; var 1..15:DE; var 1..15:EF; var 1..15:FA;

constraint all_different ([AB, BC, CD, DE, EF, FA]);

constraint FA > BC /\ FA < EF;
constraint AB == 1; 

% There are 31 possible distances between villages, as shown below:
var set of int: soln_nums == {AB, BC, CD, DE, EF, FA,  % 1 stop
AB+BC, BC+CD, CD+DE, DE+EF, EF+FA, FA+AB,              % 2 stops
AB+BC+CD, BC+CD+DE, CD+DE+EF, DE+EF+FA, EF+FA+AB, FA+AB+BC,  % 3 stops
AB+BC+CD+DE, BC+CD+DE+EF, CD+DE+EF+FA, DE+EF+FA+AB, EF+FA+AB+BC, FA+AB+BC+CD, % 4 stops
AB+BC+CD+DE+EF, BC+CD+DE+EF+FA, CD+DE+EF+FA+AB, DE+EF+FA+AB+BC, % 5 stops
EF+FA+AB+BC+CD, FA+AB+BC+CD+DE, 
AB+BC+CD+DE+EF+FA};  % 6 stops

set of int: req_nums = 1..31;
 
constraint soln_nums == req_nums;

constraint card(soln_nums) == AB + BC + CD + DE + EF + FA;

solve satisfy;

output["[AB, BC, CD, DE, EF, FA] = " ++ show( [AB, BC, CD, DE, EF, FA] )
++"\n" ++ "Distance from Earley to Farley =  "  ++ show(EF) ++ " miles."];

% [AB, BC, CD, DE, EF, FA] = [1, 2, 7, 4, 12, 5]
% Distance from Earley to Farley =  12 miles.
% ----------
% ==========

LikeLike

Ruud 11:24 am on 22 August 2024 Permalink | Reply

A bit less verbose:

import itertools

succ = dict(zip("abcdef", "bcdefa"))

for x5 in itertools.permutations(range(2, 20), 5):
    dist = dict(zip("ab bc cd de ef fa".split(), [1, *x5]))
    for d in "abcdef":
        d1 = succ[d]
        for _ in range(4):
            dist[d + succ[d1]] = dist[d + d1] + dist[d1 + succ[d1]]
            d1 = succ[d1]
    if dist["ef"] > dist["fa"] > dist["ac"] and set(dist.values()) == set(range(1, 31)):
        print(dist["ef"])

LikeLike

Frits 4:10 pm on 22 August 2024 Permalink | Reply

Using my Puzzle #171 code but now using decomposition.

     
from itertools import permutations

# for a list with n numbers check if the set of sums of 1...n-1 adjacent items
# (also circular) is complete (with n.(n-1) different sums)
def allOccurOnce(s, ln):                                         
  sms = set(s)
  for i in range(ln):
    for j in range(2, ln):
      if (sm := sum((s * 2)[i:i + j])) in sms: 
        return False
      sms.add(sm)
  return True  

# decompose <t> into <k> increasing numbers from <ns>
def decompose(t, k, ns, s=[]):
  if k == 1:
    if t in ns:
      yield s + [t]
  else:
    for i, n in enumerate(ns):
      # make sure we don't overshoot
      if 2 * t < (2 * n + k - 1) * k: break
      yield from decompose(t - n, k - 1, ns[i + 1:], s + [n])

N = 6
T = N**2 - N + 1
H = int(T // 2)

# for a magic circle with N numbers and total sum T
# the highest possible circle number is T - N(N-1)/2 which equals H + 1

# exclude mandatory numbers 1 and 2 from the decomposition
for dc in decompose(T - 3, N - 2, range(3, H + 2)):
  # weave in the number 2
  for p in permutations([2] + dc):
    p1 = (1, ) + p
    
    # distance EF > distance FA > distance BC
    if not (p1[4] > p1[5] > p1[1]): continue
    # can we make N.(N - 1) different sums?
    if not allOccurOnce(p1, N): continue
    print(f"answer: {p1[4]} miles")

LikeLike

Jim Randell 5:35 am on 18 August 2024 Permalink | Reply
Tags: by: Howard Williams ( 44 )
Teaser 3230: Polytunnel
From The Sunday Times, 18th August 2024 [link] [link]

I have extended my market garden by the addition of a polytunnel. The polyethylene cover is supported at intervals by identical sets of three vertical pillars supporting metal arcs, of negligible thickness, resting on the level ground on both sides. In each set, the highest pillar is in the middle of the cross-section, at the highest point of the tunnel. The other two pillars are of equal height, being three quarters of the height of the central pillar. These shorter pillars are positioned on each side, 2/11 of the ground-level width of the tunnel from each edge.

Each metal arc is part of a circle (less than a semicircle), and the highest point is exactly 3m above the ground.

What is the ground-level width of the polytunnel in cm?

[teaser3230]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
GeoffR, Frits, and Jim Randell are discussing. Toggle Comments
- Jim Randell 5:36 am on 18 August 2024 Permalink | Reply
  By considering two right-angled triangles we can derive a linear equation for the depth of the centre of the arc below ground level (x), from which the width of the polytunnel (2w) can be determined.
  
  The triangles are indicated in the following diagram:
  
  This Python program (appropriately enough) uses the [[ Polynomial() ]] class from the enigma.py library to perform the calculations.
  
  It runs in 76ms. (Internal runtime is 139µs).
```
from enigma import (Rational, Polynomial, sq, sqrt, printf)

Q = Rational()

# suppose the polytunnel has ground-level semi-width w
# and the centre of the circle is a distance x below ground
# we have:
#
#  r = x + 300
#  r^2 = w^2 + x^2
#  r^2 = (7w/11)^2 + (225 + x)^2

fx = Polynomial('x')  # depth of origin
fr = fx + 300  # radius of arc

f1 = sq(fr) - sq(fx)  # = w^2
f2 = sq(fr) - sq(fx + 225)  # = (7w/11)^2

f = sq(Q(7, 11)) * f1 - f2  # equate values of w^2

# solve f(x) = 0 for positive real x
for x in f.roots(domain='F', include='0+'):
  # calculate width
  W = sqrt(f1(x)) * 2
  printf("polytunnel width = {W:g} cm [x = {x:g}]")
```
  Solution: The width of the polytunnel at ground level is 660 cm.
  
  The polynomial to determine the depth of the centre of the circular arc simplifies to:
  
  f(x) = 2x − 63
  
  From which we easily find the depth of the centre and the radius of the circle:
  
  x = 31.5
  r = 331.5
  
  And from these we calculate the semi-width of the polytunnel:
  
  w^2 = r^2 − x^2 = (r + x)(r − x)
  w^2 = 363 × 300 = 108900
  ⇒ w = 330
  
  So the total width of the polytunnel is 660 cm.
  
  LikeLike
- Frits 11:24 am on 18 August 2024 Permalink | Reply
  I made my narrowing down routine from scratch.
  Of course there are more efficient ways to do this (I don’t know them by heart).
```
from sys import float_info
eps = float_info.epsilon

# r = x + 300    # the centre of the circle is a distance x below ground
# 49.w^2 - 117600.x - 17_640_000 = 0
# 49.w^2 -  72600.x - 19_057_500 = 0

f1 = lambda x: 17_640_000 + 117_600 * x
f2 = lambda x: 19_057_500 +  72_600 * x

mode = ""
x = 100         # choose an arbitrarily starting value
delta = 5       # increment/decrement value for variable x

# find a value for "x" where both f1(x) and f2(x) are (almost) the same
while True:
  v1, v2 = f1(x), f2(x)
  # do we have an solution where both values are (almost) the same?
  if abs(v2 - v1) <= eps:
    w = (2_400 * x + 360_000)**.5
    print(f"answer:  ground-level width = {round(w, 2)} cm")
    break
  
  if v1 < v2:
    if mode == "more": 
      delta /= 2
    x += delta
    mode = "less"
  else:
    if mode == "less": 
      delta /= 2
    x -= delta
    mode = "more"     
```
  LikeLike
  - Frits 11:34 am on 18 August 2024 Permalink | Reply
    
    The program was only made if you don’t want to analyse the problem till a solution is found.
    
    LikeLike
- GeoffR 6:23 pm on 18 August 2024 Permalink | Reply
```
% A Solution in MiniZinc
include "globals.mzn";

% X = half tunnel width, Y =  depth below ground, R = circle radius
% All dustances in mm.

% Assumed UB's for variables
var 1..4500:R;  var 1..4000:X; var 1..1500:Y; 

constraint R == 3000 + Y;  

constraint X * X  + Y * Y == R * R;
 
% (2250 + Y)^2 + (7/11 * X)^2 = R * R
constraint 121 * R * R == 121 * ((2250 + Y) * (2250 + Y)) + (49 * X * X);

solve satisfy;
```
  LikeLike
Jim Randell 10:46 am on 15 August 2024 Permalink | Reply
Tags: by: Robin Nayler ( 16 )
Teaser 2623: Latecomer
From The Sunday Times, 30th December 2012 [link] [link]

Imogen is having a New Year party tomorrow night and she has invited Madeline, hoping not to have a repeat of last year’s episode which completely spoilt the celebrations. Last New Year’s Eve Madeline had been due at a certain whole number of minutes past an hour but she was late, the number of minutes late being that same aforementioned “certain number of minutes” but with the digits in the reverse order. Madeline pointed out that at least the angle between the hands of the clock at the moment of her arrival was the same as it would have been when she was due.

At what time was she due to arrive?

[teaser2623]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 10:46 am on 15 August 2024 Permalink | Reply
  Madeline was expected to arrive at a time of xy minutes past a specified hour, but she was late, and arrived yx minutes later than her expected time. So yx (and xy) cannot be 00 (as then she would not be late).
  
  This Python program finds both possible solutions to the puzzle.
  
  It runs in 74ms. (Internal runtime is 3.6ms).
```
from enigma import (Rational, irange, cproduct, nrev, printf)

Q = Rational()

# calculate angle between hands at time h:m
# angles are between 0 (coincident) and 1 (opposite)
def angle(h, m):
  (x, m) = divmod(m, 60)
  h = (h + x) % 12
  ah = Q(h + Q(m, 60), 6)
  am = Q(m, 30)
  a = abs(ah - am)
  return (2 - a if a > 1 else a)

# consider possible scheduled arrival times
for (h, m) in cproduct([irange(0, 11), irange(1, 59)]):
  a1 = angle(h, m)
  # calculate angle at actual arrival time
  a2 = angle(h, m + nrev(m, 2))
  # are angles the same?
  if a1 == a2:
    # output solution
    printf("expected arrival = {h:02d}:{m:02d} [angle = {a:.2f} min]", a=float(a1 * 30))
```
  There are two possible answers:
  
  Expected time = 11:43; Actual time = 11:43 + 34 minutes = 12:17
  Expected time = 5:43; Actual time = 5:43 + 34 minutes = 6:17
  
  Both of which are illustrated below, with the same shape indicating the identical angles between the hands:
  
  As the party in question is a New Years Eve party, presumably the setter intends us to choose the solution where Madeline was expected to arrive before midnight, but actually arrived after midnight (although this could easily have been specified in the problem text).
  
  Solution: Madeline was due to arrive at 11:43 pm.
  
  LikeLike

Jim Randell 8:21 am on 13 August 2024 Permalink | Reply
Tags: by: Danny Roth ( 87 )

Teaser 2586: Powerful dice

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

George and Martha threw a die, noted the number of spots on the uppermost face, and entered that number in one of the boxes of a 3-by-3 grid of nine squares. They repeated the exercise eight more times resulting in a digit in each box.

Then George looked at the three 3-digit numbers read across the rows and commented that each was a square or a cube. Martha looked at the three 3-digit numbers read down the columns and said the same was true for her numbers. Furthermore, their two sets of three numbers had only one in common.

What (in increasing order) were the five different 3-digit numbers?

[teaser2586]

Jim Randell 8:22 am on 13 August 2024 Permalink | Reply

We can use the [[ SubstitutedExpression ]] solver from the enigma.py library to solve this puzzle.

The following run file executes in 76ms. (Internal runtime of the generated program is 2.5ms).

#! python3 -m enigma -rr

SubstitutedExpression

#  A B C
#  D E F
#  G H I

--digits="1-6"
--distinct=""

--code="check = cached(lambda n: is_square(n) or is_cube(n))"

# check rows and columns
"check(ABC)"
"check(DEF)"
"check(GHI)"
"check(ADG)"
"check(BEH)"
"check(CFI)"

# there is exactly one number shared between the rows and columns
"len(intersect([{ABC, DEF, GHI}, {ADG, BEH, CFI}])) = 1"

# and there are five different numbers in total
"len({ABC, DEF, GHI, ADG, BEH, CFI}) = 5"

--answer="call(ordered, {ABC, DEF, GHI, ADG, BEH, CFI})"
--template="rows = [ ABC DEF GHI ]; cols = [ ADG BEH CFI ]"
--solution=""
--verbose="1-H"

Solution: The numbers entered in the box were: 121, 125, 216, 256, 512.

We have:

121 = 11^2
125 = 5^3
216 = 6^3
256 = 16^2
512 = 8^3

512 appears as both a row and a column.

The most likely scenario is:

Then George’s rows would consist of both squares and cubes, and Martha could say the same about her columns even though they are actually all cubes.

Swapping the rows and columns yields a second viable layout, but it seems unlikely George would note that his each of his rows was a square or a cube, when they are in fact all cubes.

LikeLike

ruudvanderham 11:50 am on 13 August 2024 Permalink | Reply

from istr import istr
istr.repr_mode('int')
squares=[i*i for i in range(10,32)]
cubes=[i*i*i for i in range (5,10)]
squares_cubes=istr(squares+cubes)

solutions=set()
for abc in squares_cubes:
    for def_ in squares_cubes:
        for ghi in squares_cubes:
            horizontals={abc,def_,ghi}
            verticals={abc[i]|def_[i]|ghi[i] for i in range(3)}
            if all(vertical in squares_cubes for vertical in verticals):
                horizontals_verticals= horizontals | verticals
                if len(horizontals_verticals)==5:
                    solutions.add(tuple(sorted(horizontals_verticals)))
print(solutions)

LikeLike

Ruud 7:07 pm on 13 August 2024 Permalink | Reply

I forgot to test whether all digits were between 1 and 6.
Here’s an improved version (same output):

from istr import istr

istr.repr_mode("int")
squares = [i * i for i in range(10, 32)]
cubes = [i * i * i for i in range(5, 10)]
squares_cubes = [i for i in istr(squares + cubes) if all(j in range(1, 7) for j in i)]

solutions = set()
for abc in squares_cubes:
    for def_ in squares_cubes:
        for ghi in squares_cubes:
            horizontals = {abc, def_, ghi}
            verticals = {abc[i] | def_[i] | ghi[i] for i in range(3)}
            if all(vertical in squares_cubes for vertical in verticals):
                horizontals_verticals = horizontals | verticals
                if len(horizontals_verticals) == 5:
                    solutions.add(tuple(sorted(horizontals_verticals)))
print(solutions)

LikeLike

Jim Randell 5:54 pm on 14 August 2024 Permalink | Reply

@Ruud: I think you also need to add a test for “their two sets of three numbers had only one in common”. Your code would allow a repeated row or a repeated column.

LikeLike

Ruud 7:07 pm on 14 August 2024 Permalink | Reply

@Jim
Thanks for pointing this out. You are right.
My updated code:

from istr import istr

istr.repr_mode("int")
squares = [i * i for i in range(10, 32)]
cubes = [i * i * i for i in range(5, 10)]
squares_cubes = [i for i in istr(squares + cubes) if all(j in range(1,7) for j in i)]

solutions = set()
for abc in squares_cubes:
    for def_ in squares_cubes:
        for ghi in squares_cubes:
            horizontals = {abc, def_, ghi}
            verticals = {abc[i] | def_[i] | ghi[i] for i in range(3)}
            if all(vertical in squares_cubes for vertical in verticals):
                if len(horizontals & verticals) == 1:
                    solutions.add(tuple(sorted(horizontals | verticals)))
print(solutions)

LikeLike

Jim Randell 7:04 am on 11 August 2024 Permalink | Reply
Tags: by: Stephen Hogg ( 64 )
Teaser 3229: Fishy scales
From The Sunday Times, 11th August 2024 [link] [link]

For loads under 99.5 kg, my scales have three 7-segment digits. The left and centre digits show the weight; the right digit shows “r” for rounded to whole kg or “E” for exact kg. The examples show 69 kg rounded, and 0 kg exactly. Overload displays “888”.

The scales are accurate, but one of the segments in one of the digits is faulty and is always illuminated. For example, two fish boxes were recently loaded together and “68E” appeared. A fish slid off and “62E” appeared. A third box was added and “99E” appeared. The fallen fish was then put back in its box. Curiously, the display didn’t change. Then the first two boxes were removed. A new reading appeared, with rightmost digit “E”.

Find the reading displayed for the third box alone.

[teaser3229]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 7:21 am on 11 August 2024 Permalink | Reply
  The faulty segment must be lit in all the readings given, and the first likely scenario I tried gave a viable solution, so the puzzle was solved manually in a few minutes. However the following Python program performs an exhaustive exploration of the problem space.
  
  The final digit of the display reads “E”, “r” or “8”, and it is not possible for a single incorrect segment to change one of these displays to a different viable digit. So all the readings must end in “E”, and so we are dealing with exact integer weights, less than 100 kg. This is enough to explore the problem space without requiring any additional analysis.
  
  The following Python program runs in 72ms. (Internal runtime is 4.1ms).
```
from enigma import (irange, intersect, append, join, printf)

# segments on a 7-segment display
segs = {
  0: {0, 1, 2, 4, 5, 6},
  1: {2, 5},
  2: {0, 2, 3, 4, 6},
  3: {0, 2, 3, 5, 6},
  4: {1, 2, 3, 5},
  5: {0, 1, 3, 5, 6},
  6: {0, 1, 3, 4, 5, 6},
  7: {0, 2, 5},
  8: {0, 1, 2, 3, 4, 5, 6},
  9: {0, 1, 2, 3, 5, 6},
  'E': {0, 1, 3, 4, 6},
  'r': {3, 4},
}

# segment display for integer weight <w>, with digit <d> segment <s> always lit
def display(w, d=None, s=None):
  if w > 99: return [segs[8]] * 3
  ds = list(segs[k] for k in divmod(w, 10))
  ds.append(segs['E'])
  # adjust the faulty segment
  if d is not None:
    ds[d] = append(ds[d], s)
  return ds

# output a display (? for a mangled digit)
def output(ds):
  r = dict((frozenset(v), k) for (k, v) in segs.items())  # reverse the segment map
  return join(r.get(frozenset(x), '?') for x in ds)

# the given displays
(d68E, d62E, d99E) = (display(x) for x in (68, 62, 99))

# choose the faulty segment
for (d, xs) in enumerate(zip(d68E, d62E, d99E)):
  for s in intersect(xs):
    # consider the weight of box 1 and 2 (including the fish)
    for b12 in irange(2, 98):
      # display for (box 1 + box 2) is "68E"
      if display(b12, d, s) != d68E: continue

      # consider the weight of the fish
      for f in irange(1, b12 - 1):
        # display for (box 1 + box 2 - fish) is "62E"
        if display(b12 - f, d, s) != d62E: continue

        # consider the weight of box 3
        for b3 in irange(1, 99 - b12):
          # display of (box 1 + box 2 - fish + box 3) is "99E"
          if display(b12 - f + b3, d, s) != d99E: continue
          # but display does not change if the fish is returned to its box
          if display(b12 + b3, d, s) != d99E: continue

          # final display is just b3
          fsegs = display(b3, d, s)

          # output solution
          printf("{disp} = {fsegs} [d={d} s={s}; b12={b12} f={f} b3={b3}]", disp=output(fsegs))
```
  Solution: The reading for the third box alone was: “33E”.
  
  The faulty segment is segment 2 (top right) of the second (middle) digit of the display.
  
  The first two boxes together (including the fish) weigh 66 kg. The display (incorrectly) reads “68E”.
  
  The fish weighs 4 kg, so when it is removed the total weight is 62 kg. The display (correctly) reads “62E”.
  
  The third box weighs 33 kg, so when this is added the total weight is now 95 kg. The display (incorrectly) reads “99E”.
  
  The fish is then returned to its box, so the total weight is now 99 kg. The display (correctly) reads “99E” (again).
  
  The first 2 boxes (including the fish) are now removed, leaving only the third box. The display (correctly) reads “33E”.
  
  LikeLike

Jim Randell 9:50 am on 7 August 2024 Permalink | Reply
Tags: by: Adrian Somerfield ( 13 )

Teaser 2587: Hobson’s choice

From The Sunday Times, 22nd April 2012 [link] [link]

In the diagram the letters represent the numbers 1 to 16 in some order. They form a magic square, where the sum of each row, each column and each main diagonal is the same. The letters of the word “CHOICE” and some others (including all the letters not used in the magic square) have a value equal to their position in the alphabet (C=3, H=8, etc).

What is the value of H+O+B+S+O+N?

[teaser2587]

Jim Randell 9:52 am on 7 August 2024 Permalink | Reply
See also: Enigma 1690.

The 16 numbers in the grid sum to tri(16) = 136, so each row and column must sum to 1/4 of this = 34.

We can use the [[ SubstitutedExpression ]] solver from the enigma.py library to find possible assignments.

The following run file executes in 85ms. (Internal runtime of the generated code is 145µs).
```
#! python3 -m enigma -rr

SubstitutedExpression

#  A B C D
#  E F G H
#  I J K L
#  M N O P

--base=27
--digits="1-16"

# rows
"A + B + C + D == 34"
"E + F + G + H == 34"
"I + J + K + L == 34"
"M + N + O + P == 34"
# columns
"A + E + I + M == 34"
"B + F + J + N == 34"
"C + G + K + O == 34"
"D + H + L + P == 34"
# diagonals
"A + F + K + P == 34"
"D + G + J + M == 34"

# given values
--assign="C,3"
--assign="E,5"
--assign="H,8"
--assign="I,9"
--assign="O,15"
--assign="S,19" # we only need S (from Q..Z)

# required answer
--answer="H + O + B + S + O + N"

--template=""
```
Solution: H + O + B + S + O + N = 73.

The completed grid is:

The Magic Square is a variation of the “Dürer” Magic Square seen in “Melencolia I”. [ @wikipedia ]

If you recognise that the given values (C = 3, E = 5, H = 8, I = 9, O = 15) fit into this square you don’t need to do any more working out, as the square is associative (which means any number and its symmetric opposite add to 17).

So we can calculate the required result using the given values as:

H + O + B + S + O + N
= H + O + (17 − O) + S + O + (17 − C)
= 8 + 15 + 2 + 19 + 15 + 14
= 73

LikeLike

ruudvanderham 2:10 pm on 7 August 2024 Permalink | Reply

Brute force solution:

import itertools

C = 3
E = 5
H = 8
I = 9
O = 15
S = 19
for A, B, D, F, G, J, K, L, M, N, P in itertools.permutations((1, 2, 4, 6, 7, 10, 11, 12, 13, 14, 16)):
    ABCD = A + B + C + D
    if E + F + G + H == ABCD:
        if I + J + K + L == ABCD:
            if M + N + O + P == ABCD:
                if A + E + I + M == ABCD:
                    if B + F + J + N == ABCD:
                        if C + G + K + O == ABCD:
                            if D + H + L + P == ABCD:
                                if A + F + K + P == ABCD:
                                    if D + G + J + M == ABCD:
                                        print(f"{H+O+B+S+O+N=}")
                                        print(f"{A=:2} {B=:2} {C=:2} {D=:2}")
                                        print(f"{E=:2} {F=:2} {G=:2} {H=:2}")
                                        print(f"{I=:2} {J=:2} {K=:2} {L=:2}")
                                        print(f"{M=:2} {N=:2} {O=:2} {P=:2}")

Output:

H+O+B+S+O+N=73
A=16 B= 2 C= 3 D=13
E= 5 F=11 G=10 H= 8
I= 9 J= 7 K= 6 L=12
M= 4 N=14 O=15 P= 1

LikeLike

GeoffR 5:41 pm on 7 August 2024 Permalink | Reply

A 4-stage permutation brings the run- time down to 55 msec using ABCD = 34 , or 177 msec not using ABCD = 34.


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

from itertools import permutations
#  A B C D
#  E F G H
#  I J K L
#  M N O P

# Given values
C, E, H = 3, 5, 8
I, O, S = 9, 15, 19

# Find remaining digits to permute
digits = set(range(1,17)).difference({3, 5,8,9,15})

# 1st stage permutation
for p1 in permutations (digits, 3):                       
  A, B, D = p1  # C given
  ABCD = A + B + C + D
  if ABCD != 34:continue
  
  # 2nd stage permutation
  q1 = digits.difference(p1)
  for p2 in permutations(q1, 2):
    F, G = p2  # E and H given
    EFGH = E + F + G + H
    if EFGH != ABCD:continue
    
    # 3rd stage permutation
    q2 = q1.difference(p2)
    for p3 in permutations(q2, 3):
      J, K, L = p3  # I given
      IJKL = I + J + K + L
      if IJKL != ABCD:continue
      
      # 4th stage permutation
      q3 = q2.difference(p3)
      for p4 in permutations(q3, 3):
        M, N, P = p4 # O given
        MNOP = M + N + O + P
        if MNOP != ABCD: continue
        
        # Check column and diagonal sums
        if A + E + I + M != ABCD:continue
        if B + F + J + N != ABCD:continue
        if C + G + K + O != ABCD:continue
        if D + H + L + P != ABCD:continue
        if A + F + K + P != ABCD:continue
        if D + G + J + M != ABCD:continue
          
        print(f"HOBSON = {H + O + B + S + O + N}")
        print(A,B,C,D)
        print(E,F,G,H)
        print(I,J,K,L)
        print(M,N,O,P)
        timer.stop()      
        timer.report()
        # [ST2587] total time: 0.1775740s (177.57ms) - without ABCD = 34
        # [ST2587] total time: 0.0553104s (55.31ms) - with ABCD = 34

# HOBSON = 73
# 16 2 3 13
# 5 11 10 8
# 9 7  6 12
# 4 14 15 1

LikeLike

ruudvanderham 6:48 am on 8 August 2024 Permalink | Reply

Nice solution.
I guess that if you first try the EFGH permutations, performance might slightly improve because there are only 2 choices there.

LikeLike
- ruudvanderham 6:54 am on 8 August 2024 Permalink | Reply
  
  Or even faster (maybe): go vertical vertical and first do AEIM, then CGKO (twice 2 choices only).
  
  LikeLike
- Frits 10:00 am on 8 August 2024 Permalink | Reply
  
  Brian did some analysis and discovered that L must be 12.
  
  [ https://brg.me.uk/?page_id=3378 ]
  
  LikeLike
  - Jim Randell 11:03 am on 8 August 2024 Permalink | Reply
    
    @Frits: By using the given values and simplifying the 10 equations we can get:
    
    B + N = 16
    
    And we know values for all the other letters in HOBSON, so the result follows directly.
    
    (Although it is not a constructive solution – it assumes that it is possible to make a viable Magic Square).
    
    LikeLike
    - Frits 11:56 am on 8 August 2024 Permalink | Reply
      
      That’s neat.
      
      LikeLike

GeoffR 10:07 am on 8 August 2024 Permalink | Reply

I got about a 5 ms speed increase trying the EFGH permutation first, but the second suggestion i.e. AEIM, then CGKO did not come out easily – may have another look later.

LikeLike

GeoffR 11:57 am on 9 August 2024 Permalink | Reply

This solution uses the fact that this an associative magic square to find the value of HOBSON only. The full ten constraints for summing rows, columns and diagonals were still needed to find a unique magic square.


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

%   A B C D
%   E F G H
%   I J K L
%   M N O P

var 1..16:A; var 1..16:B; var 1..16:C; var 1..16:D;
var 1..16:E; var 1..16:F; var 1..16:G; var 1..16:H;
var 1..16:I; var 1..16:J; var 1..16:K; var 1..16:L;
var 1..16:M; var 1..16:N; var 1..16:O; var 1..16:P;
int:S == 19;

constraint all_different([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P]);

% Given values
constraint C == 3 /\ E == 5 /\ H == 8 /\ I == 9 /\ O == 15;

% LB = 1+2+3+4+5+6 = 21, UB = 19 + 4*16 = 83
var 21..83: HOBSON == H + O + B + S + O + N;

% Symmetric sum = 4^2 + 1 = 17, for this associative magic square
% So symmetrically opposite numbers add to 17 
constraint A + P == 17 /\ B + O == 17 /\ C + N == 17 /\ D + M == 17;
constraint E + L == 17 /\ F + K == 17 /\ G + J == 17;  % Given H + I = 17

 solve satisfy;
 output["HOBSON = " ++ show(HOBSON) ];
%  HOBSON = 73
% ----------
% ==========

LikeLike

Jim Randell 6:16 am on 4 August 2024 Permalink | Reply
Tags: by: John Owen ( 33 )

Teaser 3228: Prime tiles

From The Sunday Times, 4th August 2024 [link] [link]

Ann, Beth and Chloe play a game with tiles. The prime numbers from 3 to 41 inclusive are written on 12 tiles, and each player receives 4 tiles. An odd starting number is chosen at random, then each player in turn tries, if possible, to increase the total to a prime number, by adding two of their tiles. For example, if the starting number is 5, Ann could play 11 and 31 to make the total 47, then Beth might be able to play 5 and 7 to make 59 and so on.

In a game where the starting number was 3, Ann was first, but couldn’t play. Beth and Chloe both took their turns, but again Ann was unable to play.

In ascending order, which four tiles did Beth and Chloe play?

[teaser3228]

Jim Randell 6:32 am on 4 August 2024 Permalink | Reply

This Python program runs in 68ms. (Internal runtime is 2.8ms).

from enigma import (primes, subsets, diff, ordered, printf)

# available tiles
tiles = list(primes.between(3, 41))

# starting total
t0 = 3

# choose 4 tiles for A
for As in subsets(tiles, size=4):
  # A is unable to play
  if any(t0 + x + y in primes for (x, y) in subsets(As, size=2)): continue

  # B plays two tiles
  for (b1, b2) in subsets(diff(tiles, As), size=2):
    t1 = t0 + b1 + b2
    if t1 not in primes: continue

    # C plays 2 tiles
    for (c1, c2) in subsets(diff(tiles, As, (b1, b2)), size=2):
      t2 = t1 + c1 + c2
      if t2 not in primes: continue

      # A is unable to play
      if any(t2 + x + y in primes for (x, y) in subsets(As, size=2)): continue

      # output solution
      played = ordered(b1, b2, c1, c2)
      printf("played = {played} [A={As}; {t0} -> ({b1}, {b2}) -> {t1} -> ({c1}, {c2}) -> {t2}]")

Solution: The tiles Beth and Chloe played were 7, 23, 31, 37.

A’s tiles were: 5, 13, 19, 41.

There are 3 possible games:

3 → (7, 31) → 41 → (23, 37) → 101
3 → (7, 37) → 47 → (23, 31) → 101
3 → (31, 37) → 71 → (7, 23) → 101

but in all cases the tiles played by B and C are: 7, 23, 31, 37.

LikeLike

Ruud 10:52 am on 5 August 2024 Permalink | Reply

Similar to @Frits:

import itertools


def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if not n & 1:
        return False
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False
    return True


primes = set(n for n in range(3, 42) if is_prime(n))

for a in itertools.combinations(primes, 4):
    bc = primes - set(a)
    total = 3
    if not any(is_prime(total + sum(a2)) for a2 in itertools.combinations(a, 2)):
        for b2 in itertools.combinations(bc, 2):
            if is_prime(total + sum(b2)):
                for c2 in itertools.combinations(bc - set(b2), 2):
                    if is_prime(total + sum(b2) + sum(c2)):
                        if not any(is_prime(total + sum(b2) + sum(c2) + sum(a2)) for a2 in itertools.combinations(a, 2)):
                            print(sorted(b2 + c2))

LikeLike

Frits 10:05 am on 4 August 2024 Permalink | Reply

from itertools import combinations

# determine valid primes up to approx 6 * 41
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, 240, 2) if all(x % p for p in P)}

sols, t = set(), 3  
tiles = {p for p in P if 3 <= p <= 41}

# pick four tiles for Ann
for a4 in combinations(tiles, 4):
  # check if any two of Ann's tiles make a prime (with 3)
  for a2 in combinations(a4, 2):
    if (sum(a2) + t) in P: break
  else: # no break, Ann couldn't play  
    # pick 2 playable tiles for Beth
    for b2 in combinations(tiles.difference(a4), 2):
      if (t_b := (sum(b2) + t)) not in P: continue
      # pick 2 playable tiles for Chloe
      for c2 in combinations(tiles.difference(a4 + b2), 2):
        if (t_c := (sum(c2) + t_b)) not in P: continue
        # check if any two of Ann's tiles can make a prime
        for a2 in combinations(a4, 2):
          if (sum(a2) + t_c) in P: break
        else: # no break, Ann couldn't play  
          sols.add(tuple(sorted(b2 + c2)))
          
# print the solution(s)          
for s in sols:
  print(f"answer: {s}")

LikeLike

Frits 12:10 pm on 4 August 2024 Permalink | Reply

Less efficient.

from itertools import combinations

# determine valid primes up to approx 6 * 41
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, 240, 2) if all(x % p for p in P)}

sols, t = set(), 3  
tiles = [p for p in P if 3 <= p <= 41]

# combinations of 4 tiles that sum to a certain total
d = {t: [c4 for c4 in combinations(tiles, 4) 
         if sum(c4) == t] for t in range(26, 139, 2)}
         
# pick four tiles for Ann
for a4 in combinations(tiles, 4):
  # starting totals where Ann cannot play
  npt = {t for t in range(3, 142, 2) 
         if all((sum(a2) + t) not in P for a2 in combinations(a4, 2))}
  if 3 not in npt: continue
  
  # check non-playing totals (besides total <t>)
  for np in npt:
    if np == t: continue
    # get 4 tiles for Beth and Chloe ...
    for t4 in d[np - t]:
      # ... that differ from Ann's tiles
      if len(set(a4 + t4)) != 8: continue
      
      # can we make a prime with 2 numbers of <t4>
      for b2 in combinations(t4, 2):
        if (t_b := sum(b2) + t) not in P: continue
        # can we make a prime with 2 numbers of <t4>
        c2 = set(t4).difference(b2)
        if (t_c := sum(c2) + t_b) not in P: continue
        sols.add(tuple(sorted(b2 + tuple(c2))))

# print the solution(s)          
for s in sols:
  print(f"answer: {s}")

LikeLike

Jim Randell 9:44 am on 1 August 2024 Permalink | Reply
Tags: by: Andrew Skidmore ( 87 )

Teaser 2584: Truncation

From The Sunday Times, 1st April 2012 [link] [link]

Callum is learning about squares and primes. He told me that he had discovered a four-figure square that becomes a three-figure prime if you delete its last digit. I could not work out his square from this information and he informed me that, if I knew the sum of its digits, then I would be able to work it out. So I then asked whether the square had a repeated digit: his answer enabled me to work out his square.

What was it?

[teaser2584]

Jim Randell 9:44 am on 1 August 2024 Permalink | Reply

This Python program runs in 81ms. (Internal runtime is 381µs).

from enigma import (
  powers, is_prime, filter_unique, dsum,
  is_duplicate, singleton, group, printf
)

# find 4-digit squares, where the first 3 digits form a prime
sqs = list(n for n in powers(32, 99, 2) if is_prime(n // 10))

# select numbers unique by digit sum
ns = filter_unique(sqs, f=dsum).unique

# group results by whether there are repeated digits
g = group(ns, by=is_duplicate)

# look for unique values
for (k, vs) in g.items():
  n = singleton(vs)
  if n is not None:
    printf("(duplicate = {k}) => n = {n}")

Solution: Callum’s number was: 5476.

There are 8 candidate squares that can be truncated to a prime, but only 3 have a unique digit sum:

dsum = 10 → 2116
dsum = 13 → 3136
dsum = 19 → 1936, 4096
dsum = 22 → 5476
dsum = 25 → 5776, 7396, 8836

Two of these 3 have repeated digits, so Callum must have answered that square did not have repeated digits, which uniquely identifies 5476 as his number.

LikeLike

GeoffR 4:17 pm on 1 August 2024 Permalink | Reply


from collections import defaultdict
from enigma import is_prime, dsum

ans = defaultdict(list)

sq4 = [ x**2 for x in range(32, 100)]

for n1 in sq4:
    flag = 0  # for repeating or non-repeating digits
    n2 = int(str(n1)[0:3])
    if is_prime(n2):
        # non rpeeating digits in squares
        if len(set(str(n1))) == len(str(n1)):
            flag = 1
            ans[(flag, dsum(n1))] += [n1]
        # repeating digits in squares
        if len(set(str(n1))) != len(str(n1)):
            flag = 2
            ans[(flag, dsum(n1))] += [n1]

for k, v in ans.items():
    print(k,v)

'''
(1, 19) [1936, 4096] <<< multiple squares for digit sum
(2, 10) [2116] <<< same number of repeating digits as square 3136
(2, 13) [3136] <<< same number of repeating digits as square 2116
(1, 22) [5476]  <<< Answer
(2, 25) [5776, 8836] <<< multiple squares for digit sum
(1, 25) [7396]  <<< same digit sum as squares 5776, 8836
'''

LikeLike

Ruud 8:50 pm on 1 August 2024 Permalink | Reply

from istr import istr
import math
import collections


def is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2  # return False
    k = 3
    while k * k <= n:
        if n % k == 0:
            return False
        k += 2
    return True


squares_per_sum_digits = collections.defaultdict(list)

for i in range(round(math.sqrt(1000)), round(math.sqrt(10000))):
    square = istr(i * i)
    if is_prime(square[:-1]):
        prime = square[:-1]
        sum_digits = sum(n for n in square)
        squares_per_sum_digits[sum_digits].append(square)

potential_squares = [squares[0] for squares in squares_per_sum_digits.values() if len(squares) == 1]
has_repeated_digits = collections.defaultdict(list)
for square in potential_squares:
    has_repeated_digits[len(set(square))!=4].append(square)

solution = [square[0] for square in has_repeated_digits.values() if len(square) == 1]
print(*solution)

LikeLike

GeoffR 7:57 pm on 3 August 2024 Permalink | Reply

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

var 1..9:A; var 0..9:B; var 1..9:C; var 0..9:D;
var 1024..9081: sq_dig4 == 1000*A + 100*B + 10*C + D;

set of int: sq4 = {n * n | n in 32..99};  

predicate is_prime(var int: x) = 
x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x)))))
 ((i < x) -> (x mod i > 0));
 
% Square with last digit deleted is a prime
constraint is_prime(100*A + 10*B + C);
constraint sq_dig4 in sq4;

solve satisfy;

output[ "Digit sum = " ++ show(A + B + C + D) ++
", Square = " ++ show(sq_dig4) ];

% Digit sum = 10, Square = 2116 - repeating digits - 2nd stage elimination
% ----------
% Digit sum = 19, Square = 1936 - not a square with a single digit sum - 1st stage elimination
% ----------
% Digit sum = 13, Square = 3136 - repeating digits - 2nd stage eliminations
% ----------
% Digit sum = 25, Square = 8836 - not a square with a single digit sum - 1st stage elimination
% ----------
% Digit sum = 22, Square = 5476 - *** ANSWER *** (unique digit sum, no repeating digits)
% ----------
% Digit sum = 25, Square = 5776 - not a square with a single digit sum - 1st stage elimination
% ----------
% Digit sum = 19, Square = 4096 - not a square with a single digit sum - 1st stage elimination
% ----------
% Digit sum = 25, Square = 7396 - not a square with a single digit sum - 1st stage elimination
% ----------
% ==========

LikeLike

Jim Randell 8:40 am on 30 July 2024 Permalink | Reply
Tags: by: R Postill ( 20 )
Brain-Teaser 542: Finger trouble
From The Sunday Times, 14th November 1971 [link]

The Wabu tribesmen, though invariably truthful, are inveterate thieves, and this despite a tribal law which requires any man convicted of theft to have one finger amputated. Few of them now have a full complement and, since they count on their fingers, their answers to numerical questions are confusing to the outsider. (For instance, an 8-fingered man gives his answers to base 8, so that, for example, our figure 100 is for him 144).

Despite these handicaps, they are keen cricketers, and I recently watched their First Eleven. The Chief told me: “Only little Dojo has 10 fingers; the worst-equipped are Abo, Bunto and Coco with 4 apiece”. (I need hardly add that the Wabu would never elect a Chief who had been convicted of theft).

Later I asked some members of the team how many fingers (thumbs are, of course, included) the Eleven totalled. Epo said “242”, and Foto agreed; Gobo said “132”, and Hingo agreed. Kinko added: “I have more fingers than Iffo”.

How many fingers each have Epo, Hingo, Iffo and Jabo (the Wicket-keeper)?

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

[teaser542]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Frits, Ruud, and Jim Randell are discussing. Toggle Comments
- Jim Randell 8:41 am on 30 July 2024 Permalink | Reply
  We can use the [[ SubstitutedExpression ]] solver from the enigma.py library to solve this puzzle.
  
  The following run file executes in 83ms. (Internal runtime of the generate code is 1.9ms).
```
#! python3 -m enigma -rr

SubstitutedExpression

--base=11  # values are between 4 and 10
--distinct=""

# we are given some values
--assign="A,4"
--assign="B,4"
--assign="C,4"
--assign="D,10"
# and the others are between 5 and 9
--digits="5-9"
# additional constraints
"E = F"
"G = H"
"K > I"

# total number of fingers
--macro="@total = (A + B + C + D + E + F + G + H + I + J + K)"

# E (and F) says "242"
"int2base(@total, base=E) == '242'"

# G (and H) says "132"
"int2base(@total, base=G) == '132'"

--answer="(E, H, I, J)"
--template=""
```
  Solution: Epo has 5 fingers; Hingo has 7 fingers; Iffo has 8 fingers; Jabo has 9 fingers.
  
  The number of fingers for each member of the team are:
  
  A = 4
  B = 4
  C = 4
  D = 10
  E = 5
  F = 5
  G = 7
  H = 7
  I = 8
  J = 9
  K = 9
  total = 72
  
  And the total given in the appropriate bases:
  
  A, B, C → 1020 [base 4]
  D → 72 [base 10]
  E, F → 242 [base 5]
  G, H → 132 [base 7]
  I → 110 [base 8]
  J, K → 80 [base 9]
  
  LikeLike
  - Ruud 4:14 pm on 30 July 2024 Permalink | Reply
    It is really simple to solve this one by hand.
    But, here’s my as brute as possible code:
```
import itertools

a = b = c = 4
d = 10
for e in range(5, 11):
    sum_e = int("242", e)

    for g in range(4, 11):
        sum_g = int("132", g)
        if sum_e == sum_g:
            f = e
            h = g
            ijk = sum_e - (a + b + c + d + e + f + g + h)
            for i, j, k in itertools.product(range(1, 10), repeat=3):
                if i + j + k == ijk and k > i:
                    print(f"Epo={e} Hingo={h} Iffo={i} Jabo={j}")
```
    LikeLike
- Ruud 7:30 pm on 30 July 2024 Permalink | Reply
  Even more brute force:
```
import itertools

a = b = c = 4
d = 10
for e, f, g, h, i, j, k in itertools.product(range(5, 10), repeat=7):
    if e == f and g == h and (total := int("242", e)) == int("132", g) and k > i and (a + b + c + d + e + f + g + h + i + j + k) == total:
        print(f"Epo={e} Hingo={h} Iffo={i} Jabo={j}")
```
  LikeLike
- Frits 1:44 pm on 31 July 2024 Permalink | Reply
```
from enigma import SubstitutedExpression

# the alphametic puzzle
p = SubstitutedExpression(
  [
    # G*G + 3*G - 2*(E*E + 2*E) = 0
    "is_square(1 + G * (G + 3) // 2) - 1 = E",
    
    "K > I",
    "(G * (G + 3) + 2) -  (A + B + C + D + E + E + G + G + I + J) = K",
  ],
  answer="(E, G, I, J)",
  distinct="",
  s2d=dict(A=4, B=4, C=4, D=10),
  digits=range(5, 10),
  verbose=0,    # use 256 to see the generated code
)

names= "Epo Hingo Iffo Jabo".split()

# print answers
for ans in p.answers():
  print(f"{', '.join(f'{x}: {str(y)}'for x, y in zip(names, ans))}")     
```
  LikeLike
Jim Randell 6:58 am on 28 July 2024 Permalink | Reply
Tags: by: Phil Jackson ( 2 )
Teaser 3227: Chess club cupboard
From The Sunday Times, 28th July 2024 [link] [link]

When installing the Chess Club cupboard in its new room, the members carelessly jammed it on the low ceiling and back wall, as shown from the side (not to scale).

Measurements were duly taken and the following were noted. The floor and ceiling were level and the back wall was vertical. The cupboard was a rectangular cuboid. The ceiling height was just 2cm greater than the cupboard height. Also, the depth of the cupboard from front to back was 148 cm less than the cupboard height. Finally the point on the ceiling where the cupboard jammed was a distance from the back wall that was 125 cm less than the cupboard height.

What is the cupboard height?

[teaser3227]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell, Frits, Ruud, and 1 other are discussing. Toggle Comments
- Jim Randell 7:11 am on 28 July 2024 Permalink | Reply
  Originally I assumed some of the dimensions were whole numbers of centimetres, which allows you to find the answer, but we do not need to make this assumption.
  
  Here is a solution using the [[ Polynomial ]] class from the enigma.py library to generate a polynomial equation, and we can then look for positive real roots of the equation to determine the necessary dimensions.
  
  (Also, today is the 15th anniversary of the start of the enigma.py library).
  
  It runs in 73ms. (Internal runtime is 4.2ms).
```
from enigma import (Polynomial, sq, printf)

# let x = cupboard depth
fx = Polynomial('x')

# y = cupboard height
fy = fx + 148

# h = room height
fh = fy + 2

# d = distance top jam to top corner
fd = fy - 125

# if:
#   a = height of upper triangle
#   b = height of lower triangle
# we have:
#   h = a + b
# and:
#   a^2 = y^2 - d^2
#   b = x.d/y
#   a = h - b = (y.h - x.d)/y
#   a^2 = (y.h - x.d)^2 / y^2 = y^2 - d^2
#   y^2(y^2 - d^2) = (y.h - x.d)^2  # for x > 0
f = (sq(fy) * (sq(fy) - sq(fd)) - sq(fy * fh - fx * fd)).scale()
printf("[f(x) = {f}]", f=f.print())

# look for positive real roots of f(x) = 0
for x in f.roots(domain='F', include='+'):
  # output solution
  printf("cupboard = {x:g} x {y:g}; room height = {h:g}", y=fy(x), h=fh(x))
```
  Solution: The cupboard was 185 cm high.
  
  So the cupboard has dimensions: 37 cm × 185 cm, and the room is 187 cm high.
  
  The polynomial to determine the depth of the cupboard x is:
  
  f(x) = x^3 + 79x^2 − 1628x − 98568
  f(x) = (x − 37)(x^2 + 116x + 2664)
  
  The linear component has a positive root at:
  
  x = 37
  
  which provides the required answer for the depth of the cupboard.
  
  The quadratic component has two negative roots at:
  
  x = 10√7 − 58 ≈ −31.542
  x = −10√7 − 58 ≈ −84.458
  
  but these do not provide viable answers to the puzzle.
  
  LikeLike
  - Jim Randell 9:09 am on 29 July 2024 Permalink | Reply
    Or the polynomial can be solved numerically, to give an approximate answer.
    
    And this is slightly faster. The following Python program has an internal runtime of 324µs).
```
from enigma import (Polynomial, sq, find_zero, printf)

# let x = cupboard depth
# y = cupboard height
# h = room height
# d = distance top jam to top corner
fx = Polynomial('x')
fy = fx + 148
fh = fy + 2
fd = fy - 125

# construct polynomial to solve
f = (sq(fy) * (sq(fy) - sq(fd)) - sq(fy * fh - fx * fd)).scale()
printf("[f(x) = {f}]", f=f.print())

# find a solution numerically
x = find_zero(f, 1, 100).v

# output solution
printf("cupboard = {x:.2f} x {y:.2f}; room height = {h:.2f}", y=fy(x), h=fh(x))
```
    LikeLike
- GeoffR 12:21 pm on 28 July 2024 Permalink | Reply
```
% A Solution in MiniZinc
include "globals.mzn";

var 1..250:h; var 1..250:y1; var 1..100:b;

% h = cupboard height
% y1 = depth below ceiling of top cupboard jam point
% b = distance of bottom jam point from vertical wall

% Two triangles to solve by Pythagorus
constraint h * h == (h - 125) * (h - 125) + (y1 * y1);

constraint (h - 148 ) * (h - 148) == (b * b) + (h + 2 - y1) * (h + 2 - y1);

solve satisfy;

output ["Cupboard height = " ++ show(h) ++ "cm."];
```
  LikeLike
- GeoffR 12:52 pm on 28 July 2024 Permalink | Reply
  
  I don’t suppose the setter intended it, but I found a second solution with a cupboard height of more than 400 cm higher than the presumed solution!
  
  LikeLike
  - Jim Randell 2:32 pm on 28 July 2024 Permalink | Reply
    
    @GeoffR: Originally I thought there were further solutions involving cupboards with non-integer dimensions, or very large cupboards (and rooms). But now I have done the analysis I found that the depth of the cupboard is defined by a cubic equation that has one positive real root (which gives the required answer) and two negative real roots, so I don’t think there are any further solutions, even if the size of the cupboard/room are not restricted.
    
    LikeLike
    - Frits 2:54 pm on 28 July 2024 Permalink | Reply
      
      @Jim,
      
      The equations I noted down for this puzzle also had a solution 10 * (9 + sqrt(7)) but that was less than 148 cm.
      
      LikeLike
      - Jim Randell 3:23 pm on 28 July 2024 Permalink | Reply
        
        @Frits: Presumably you were working in terms of the height of the cupboard. I was working in terms of the depth, so there was only one positive root.
        
        LikeLike
    - GeoffR 4:11 pm on 28 July 2024 Permalink | Reply
      @Jim: My original program gave the same outputs as your original solution.
      I increased the upper bounds of the variables to show the second solution I obtained with the second program below. Seems reasonable to use integers . Program is slow with the extra solution, but does it look OK?
      
      % A Solution in MiniZinc include "globals.mzn"; var 1..1250:h; var 1..1250:y1; var 1..1000:b; % h = cupboard height, rht = room height (for output) % y1 = depth below ceiling of top cupboard jam point % b = distance of bottom jam point from vertical wall % Two triangles to solve by Pythagorus constraint h * h == (h - 125) * (h - 125) + (y1 * y1); constraint (h - 148 ) * (h - 148) == (b * b) + (h + 2 - y1) * (h + 2 - y1); solve satisfy; output ["Cupboard height = " ++ show(h) ++ "cm." ++ "\n" ++ "[h, w, rht, y1, b ] = " ++ show( [h, h-148, h+2, y1, b ] )];
      
      LikeLike
      - Jim Randell 6:03 pm on 28 July 2024 Permalink | Reply
        
        @GeoffR: My very first program did not include a check that the upper and lower triangles were similar, which lead me to believe that there potentially multiple solutions without further constraints. But this allows cupboards that have a non-rectangular cross-section.
        
        However my subsequent analysis gives a single solution without further constraints. So we don’t need to limit the size of cupboard/room, and we don’t require measurements to have integer values.
        
        LikeLiked by 1 person
- Ruud 6:16 pm on 28 July 2024 Permalink | Reply
  
  I worked out by hand that the problem can be defined as finding the roots of the expression
  math.sqrt(250 *c -125*125)+((c-148)*(c-125)/c) – (c+2)
  I just put that in Wolfram Alpha as
  find roots of sqrt(250 *c -125*125)+((c-148)*(c-125)/c) – (c+2)
  to find the real solution (not revealed) and 10 (9 + sqrt(7)). The latter does not work here.
  
  LikeLike
  - Frits 6:55 pm on 28 July 2024 Permalink | Reply
    I did something similar with the same results.
    
    Adding the following to your code prevent multiple solutions:
```
  
% same angles
constraint h * b = (h - 148) * y1;
```
    LikeLike
Jim Randell 10:49 am on 25 July 2024 Permalink | Reply
Tags: by: J S Rowley ( 9 )
Brain-Teaser 416: Sharing sweets
From The Sunday Times, 27th April 1969 [link]

The Binks family had a birthday party recently for Ann, the youngest child. A tin of toffees was shared among the seven youngest members of the family, whose ages were all different and less than 20.

It was decided that the younger children should have more than the older; so Mr Binks suggested that each should receive the number obtained by dividing the total number of toffees by his or her age. This was done and it so happened that all the divisions worked out exactly and no toffees were left over.

Mary received 18 sweets.

How much older was she than Ann?

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

[teaser416]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Frits, Ruud, Jim Randell, and 1 other are discussing. Toggle Comments
- Jim Randell 10:51 am on 25 July 2024 Permalink | Reply
  Labelling the children in age order A, …, G, so A is Ann, and the total number of toffees is T, we have:
  
  T = T/A + T/B + T/C + T/D + T/E + T/F + T/G
  ⇒
  1 = 1/A + 1/B + 1/C + 1/D + 1/E + 1/F + 1/G
  
  So we need to find 7 different reciprocals (with denominators less than 20) that sum to 1. And we can use the [[ reciprocals() ]] function from the enigma.py library to do that (originally written for Enigma 348).
  
  We can then assign one of the values T/B, …, T/G to 18 (for Mary), and check that all the remaining T/X values give a whole number.
  
  The following Python program runs in 66ms. (Internal runtime is 753µs).
```
from enigma import (reciprocals, printf)

# find 7 different reciprocals that sum to 1
for rs in reciprocals(7, 1, 1, M=19, g=1):
  # Ann is the youngest
  A = rs.pop(0)
  # Mary received 18 sweets
  for M in rs:
    T = M * 18
    if not all(T % r == 0 for r in rs): continue
    # output solution
    printf("A={A} M={M} [T={T} rs={rs}]", rs=[A] + rs)
```
  Solution: Mary (10) is 7 years older than Ann (3).
  
  There is only one set of 7 reciprocals that works:
  
  1 = 1/3 + 1/4 + 1/9 + 1/10 + 1/12 + 1/15 + 1/18
  
  There are 180 toffees, and the ages are:
  
  3 → 60 toffees (Ann)
  4 → 45 toffees
  9 → 20 toffees
  10 → 18 toffees (Mary)
  12 → 15 toffees
  15 → 12 toffees
  18 → 10 toffees
  total = 180 toffees
  
  LikeLike
- GeoffR 1:32 pm on 25 July 2024 Permalink | Reply
```
% A Solution in MiniZinc
include "globals.mzn";

var 1..19:A; var 1..19:B; var 1..19:C; var 1..19:D;
var 1..19:E; var 1..19:F; var 1..19:G;

constraint all_different ([A, B, C, D, E, F, G]);
% Order childrens ages
constraint A < B /\ B < C /\ C < D /\ D < E /\ E < F /\ F < G;

var 28..200:T;  % total number of toffees

% Distribute toffees to seven children, with none left over
constraint T  mod A == 0 /\ T  mod B == 0 /\ T  mod C == 0 /\ T  mod D == 0 
/\ T  mod E == 0 /\ T  mod F == 0 /\ T  mod G == 0;

constraint T == T div A  + T div B + T div C + T div D 
+ T div E + T div F + T div G;

solve satisfy;

output ["Childrens ages = " ++ show ( [A,B,C,D,E,F,G] )
++ "\n" ++ "Number of toffees = " ++ show(T) ];

% Childrens ages = [3, 4, 9, 10, 12, 15, 18]
% Number of toffees = 180
% ----------
% ==========
```
  As Mary received 18 sweets, she was 10 years old, as 10 * 18 = 180.
  As the youngest was Ann, she was 3 years old, 7 years younger than Mary.
  
  LikeLike
- Ruud 6:40 am on 26 July 2024 Permalink | Reply
  
  [removed]
  
  LikeLike
  - Jim Randell 9:21 am on 26 July 2024 Permalink | Reply
    
    @Ruud: Can you explain the reasoning behind your code? I tried changing the 18 to 24 to solve a variation of the puzzle, but it did not give a correct answer. (I also added the missing imports to your program).
    
    LikeLike
    - ruudvanderham 12:02 pm on 26 July 2024 Permalink | Reply
      @Jim
      My solution was incorrect. Could you remove it?
      Here’s my revised one, which is not much different from yours:
      
      import itertools import math number_of_toffee_mary = 18 for ages in itertools.combinations(range(1, 20), 7): if math.isclose(sum(1 / age for age in ages), 1): for age in ages: if all(divmod(age * number_of_toffee_mary, try_age)[1] == 0 for try_age in ages): print(f"{ages=}. Number of toffees={number_of_toffee_mary*age}. Mary is {age-ages[0]} years older than Ann")
      
      LikeLike
- Frits 4:59 pm on 27 July 2024 Permalink | Reply
```
from itertools import combinations

M = 19
N = 7

# return divisors of <n> between 2 and <m>
def divs(n, m=M):
  lst = [d for d in range(2, int(n**.5) + 1) if n % d == 0 and d <= m]
  return lst + [d for x in lst[::-1] if x * x != n and (d := n // x) <= m]

# reciprocal sum
def rs(s): 
  i, t = 0, 0.0
  ln = len(s)
  while t < 1 and i < ln:
    t += 1 / s[i]
    i += 1
  return i == ln and round(t, 5) == 1

# Mary received 18 sweets
for m in range(2, M + 1):
  # pick <N> divisors
  for c in combinations(divs(18 * m), N):
    # reciprocal sum must be 1
    if rs(c) == 1: 
      print(f"answer: {c}")
```
  LikeLike
Jim Randell 9:44 am on 23 July 2024 Permalink | Reply
Tags: by: Adrian Somerfield ( 13 )
Teaser 2576: Latin cube
From The Sunday Times, 5th February 2012 [link] [link]

I have a cube and on each face of it there is a capital letter. I look at one face from the front, hold the top and bottom faces horizontal, and rotate the cube. In this way I can correctly read a four-letter Roman numeral. Secondly, I hold the cube with the original front face underneath and the original top face at the front, and I rotate the cube keeping the new top and bottom faces horizontal. In this way I correctly see another four-letter Roman numeral. Thirdly, I return the cube to its original position and rotate it with the two sides vertical to give another correct four-letter Roman numeral. The sum of the second and third numbers is less than a hundred.

What was the third four-letter Roman numeral seen?

[teaser2576]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Lise Andreasen and Jim Randell are discussing. Toggle Comments
- Jim Randell 9:45 am on 23 July 2024 Permalink | Reply
  Some clarification of the puzzle text is required to find a single answer (and I assume the puzzle is meant to have a unique answer):
  
  (1) Although the letters used in Roman numerals (I, V, X, L, C, D, M) are all distinguishable whatever the orientation, the puzzle requires that when letters are read they are in a “sensible” orientation. So, I and X can be read correctly upside down. However this is not sufficient to solve the puzzle, we also require that X can be read correctly in any orientation (which may not be the case if a serif font is used, as is often the case with Roman numerals).
  
  (2) The mechanism to read the numbers is that the front face is read, the cube is then rotated through 90° about a major axis to change the front face, which is then read, and the same move is repeated until the four faces in a band around the cube have been read in order (and a final move would bring the cube back to the starting position).
  
  (3) The numbers read should be valid Roman numerals in the “usual” form. (I used the [[ int2roman() ]] and [[ is_roman() ]] functions in the enigma.py library to ensure this). I didn’t allow “IIII” to represent 4 (although if you do it doesn’t change anything).
  
  (4) Each of the three numbers read is different. (Possibly this is meant to be indicated by the use of “another”).
  
  We are not told what direction the cube is rotated, so this Python program considers rotations in each direction for the 3 numbers. Although note that for some numbers (e.g. VIII (= 8), where the second and fourth letters are the same), the direction of the rotation doesn’t matter.
  
  I used the [[ Cube() ]] class (originally from Teaser 2835) to keep track of the rotation of the cube (and orientation of the faces).
  
  This Python program considers possible values for the second and third numbers (which cover bands of the cube that include all faces, so leave the cube fully specified), and then reads the first number and looks for cases where this gives a valid Roman numeral.
  
  It runs in 78ms. (Internal runtime is 11ms).
```
from enigma import (irange, int2roman, is_roman, join, seq2str, printf)
from cube import (Cube, U, D, L, R, F, B, face_label as f2l)

# valid orientations for roman digits
valid = dict((k, {0}) for k in "IVXLCDM")
valid['I'] = {0, 2}  # I can be upside down
valid['X'] = {0, 1, 2, 3}  # X can be in any orientation

# collect 4-letter roman numerals less than 100
n2r = dict()
for n in irange(1, 99):
  r = int2roman(n)
  if len(r) == 4:
    n2r[n] = r

# read values from the front of cube <c>, and apply each of the specified moves <ms>
# while match the values in <vs> (can be '?')
# return (<updated cube>, <values read>)
def read(c, ms, vs):
  rs = list()
  while True:
    # read the front face
    (v, vs0) = (c.faces[F], vs[0])
    # blank face?
    if v is None:
      v = vs0
      if v != '?':
        # fill out the new value
        c = c.update(faces=[(F, v)], orientations=[(F, 0)])
    else:
      # check it is in a valid orientation and a valid value
      if (c.orientations[F] not in valid[v]) or (vs0 != '?' and vs0 != v):
        return (None, None)
    rs.append(v)
    # any more moves?
    if not ms: break
    c = c.rotate(ms[0:1])
    ms = ms[1:]
    vs = vs[1:]
  return (c, join(rs))

# start with an empty cube
c0 = Cube(faces=[None] * 6)

# choose a 4-letter roman for the second number
for (n2, r2) in n2r.items():
  # choose the direction of rotation
  for d2 in [U, D]:
    # read the second number
    (c1, _) = read(c0.rotate([L]), [d2] * 3, r2)
    if c1 is None: continue
    # reset to original position
    c1 = c1.rotate([d2, R])

    # choose a 4-letter roman for the third number
    for (n3, r3) in n2r.items():
      # the first and second numbers sum to less than 100
      if n2 + n3 > 99: continue
      # choose a direction of rotation
      for d3 in [L, R]:
        # read the third number
        (c2, _) = read(c1, [d3] * 3, r3)
        if c2 is None: continue
        # all faces should now be filled out
        assert None not in c2.faces
        # reset to original position
        c2 = c2.rotate([d3])

        # choose a direction for the first number
        for d1 in [U, D]:
          # read the first number
          (_, r1) = read(c2, [d1] * 3, '????')
          if r1 is None: continue
          # is it a valid roman?
          n1 = is_roman(r1)
          if not n1: continue
          # check numbers are all different
          if len({n1, n2, n3}) != 3: continue

          # output solution
          printf("{r1} ({n1}) [{d1}]; {r2} ({n2}) [{d2}]; {r3} ({n3}) [{d3}]; {cube}",
                 d1=f2l[d1], d2=f2l[d2], d3=f2l[d3], cube=seq2str(c2.faces))
```
  Solution: The third Roman numeral seen was: LXII (= 62).
  
  The first two numbers were: LXIX (= 69) and XXIX (= 29), and the second and third sum to 91.
  
  Note that both of the first two numbers can be read using either direction of rotation (which is why my code finds 4 different ways to the answer), but the final number only works in one direction.
  
  The cube has faces (U, D, L, R, F, B) = (X, I, X, X, L, I).
  
  If we allow repeated numbers there is also a solution with the cube (U, D, L, R, F, B) = (X, I, X, X, X, I), which gives the numbers XXIX (= 29), XXIX (= 29), XXII (= 22).
  
  LikeLike
- Lise Andreasen 12:07 am on 24 July 2024 Permalink | Reply
  
  Especially (1) the orientation of X is interesting.
  
  LikeLike

Jim Randell 12:59 pm on 21 July 2024 Permalink | Reply
Tags: by: B W M Young ( 10 )

Brain-Teaser 420: [The Island of Squares]

From The Sunday Times, 25th May 1969 [link]

Here is the Island of Squares with its 22 provinces, and its capital in the middle of the central province.

The Geographer Royal has been instructed to colour the provinces red, blue and yellow, in such a way that no two provinces with the same colouring have a common boundary-line.

There is one further complication. Four main roads are planned each of which will go straight from the capital to one corner of the island crossing the corners of provinces on the way; one of these roads must never be in a blue province, and another must at no corner move from a yellow to a blue province or vice versa.

What colours Geographer Royal will the use for provinces 1 and 2?

This puzzle was originally published with no title.

[teaser420]

Jim Randell 1:00 pm on 21 July 2024 Permalink | Reply

This Python program colours the provinces so that no two adjacent regions share a colour, and then checks to see if there are two roads that meet the requirements.

It runs in 68ms. (Internal runtime is 4.5ms).

from enigma import (peek, update, join, union, map2str, printf)

# adjacency matrix for provinces
adj = {
  1: {2, 3, 4, 5},
  2: {1, 6, 7},
  3: {1, 4, 14},
  4: {1, 3, 5, 8, 15},
  5: {1, 4, 6, 9, 10},
  6: {2, 5, 7, 10, 13},
  7: {2, 6, 13, 18, 21, 22},
  8: {4, 9, 11, 16},
  9: {5, 8, 10, 11},
  10: {5, 6, 9, 12},
  11: {8, 9, 12, 17},
  12: {10, 11, 13, 17},
  13: {6, 7, 12, 18},
  14: {3, 15, 19},
  15: {4, 14, 16, 20},
  16: {8, 15, 17, 20},
  17: {11, 12, 16, 18, 21},
  18: {7, 13, 17, 21},
  19: {14, 20, 22},
  20: {15, 16, 19, 21, 22},
  21: {7, 17, 18, 20, 22},
  22: {7, 19, 20, 21},
}

# colour regions <rs> with colours <cs>
def colour(rs, cs, m=dict()):
  # are we done?
  if not rs:
    yield m
  else:
    # choose an uncoloured region
    r = peek(rs)
    # choose a colour
    xs = cs.difference(m[x] for x in adj[r] if x in m)
    for x in xs:
      yield from colour(rs.difference([r]), cs, update(m, [(r, x)]))

# regions for each road
roads = dict(
  NW=[11, 16, 20, 19],
  NE=[11, 17, 21, 7],
  SE=[11, 10, 6, 2],
  SW=[11, 8, 4, 1],
)

# check roads
def check(m):
  # map roads to colours
  r = dict((k, join(m[x] for x in v)) for (k, v) in roads.items())
  # find roads the do not pass through a blue province
  R1 = set(k for (k, v) in r.items() if not ('B' in v))
  if not R1: return
  # find roads that do not pass directly from blue to yellow (or vice versa)
  R2 = set(k for (k, v) in r.items() if not ('BY' in v or 'YB' in v))
  if not R2: return
  # check we can find one of each
  if len(union([R1, R2])) < 2: return
  return r

# colour the regions
for m in colour(set(adj.keys()), set("RBY")):
  # and check the roads
  r = check(m)
  if r:
    # output solution
    printf("{m}", m=map2str(m))
    printf("-> {r}", r=map2str(r))
    printf()

Solution: Province 1 is red. Province 2 is yellow.

The complete map is shown below:

There is one province that can be either red or blue (On the extreme left of the diagram. I numbered it 14, and gave it both colours).

The NE road passes through no blue, and the SW road does not pass directly from a blue to a yellow (or vice versa).

We can see that there is no point trying to colour the central province blue (as that would make blue appear in every road), but I think the code is fast enough without this.

LikeLike

Ruud 9:27 am on 22 July 2024 Permalink | Reply

Here’s my code:

neighbours = {
    1: {2, 3, 4, 5},
    2: {1, 6, 7},
    3: {1, 4, 14},
    4: {1, 3, 5, 8, 15},
    5: {1, 4, 6, 9, 10},
    6: {2, 5, 7, 10, 13},
    7: {2, 6, 13, 18, 21, 22},
    8: {4, 9, 11, 16},
    9: {5, 8, 10, 11},
    10: {5, 9, 6, 12},
    11: {8, 9, 12, 17},
    12: {10, 11, 13, 17},
    13: {6, 12, 7, 18},
    14: {3, 15, 19},
    15: {4, 14, 16, 20},
    16: {8, 15, 17, 20},
    17: {11, 12, 16, 18, 21},
    18: {13, 17, 7, 21},
    19: {14, 20, 22},
    20: {15, 16, 19, 21, 22},
    21: {17, 18, 20, 7, 22},
    22: {19, 20, 21, 7},
}
roads = [(1, 4, 8, 11), (2, 6, 10, 11), (19, 20, 16, 11), (7, 21, 17, 11)]


def solve(province, colors):
    for color in colors[province]:
        new_colors = colors.copy()
        new_colors[province] = color
        for neighbour in neighbours[province]:
            new_colors[neighbour] = new_colors[neighbour].replace(color, "")
        if province == 22:
            not_blue = set()
            not_blue_yellow = set()
            for road in roads:
                road_colors = "".join(colors[province] for province in road)
                if "b" not in road_colors:
                    not_blue.add(road)
                if not ("yb" in road_colors or "by" in road_colors):
                    not_blue_yellow.add(road)

            if len(not_blue) > 0 and len(not_blue_yellow) > 0 and len(not_blue | not_blue_yellow) >= 2:
                print(new_colors[1], new_colors[2])
        else:
            solve(province + 1, colors=new_colors)


solve(province=1, colors={province: "ryb" for province in range(1, 23)})

LikeLike

Jim Randell 3:48 pm on 19 July 2024 Permalink | Reply
Tags: by: Andrew Skidmore ( 87 )

Teaser 3226: Prime choice

From The Sunday Times, 21st July 2024 [link] [link]

I have written down three numbers, which together use each of the digits from 0 to 9 once.

All the numbers are greater than one hundred and the two smaller numbers are prime. I have also written down the product of the three numbers. If I told you how many digits the product contains you wouldn’t be able to tell me the value of the product. However, if I also told you whether the product is odd or even then you would be able to work out all the three numbers.

What, in increasing order, are my three numbers?

[teaser3226]

Jim Randell 4:09 pm on 19 July 2024 Permalink | Reply

The smaller two numbers must be 3-digit numbers, and so the remaining number must have 4 digits.

I used the [[ SubstitutedExpression() ]] solver, from the enigma.py library, to generate the possible sets of 3 numbers.

The sets are then grouped by (<length of product>, <parity of product>), and we look for keys that give a unique set of numbers, such that there is also at least one set grouped under the opposite parity (which means that there are multiple products with the same digit length).

The following Python program runs in 194ms. (Internal runtime is 125ms).

from enigma import (SubstitutedExpression, multiply, ndigits, group, unpack, printf)

# find possible sets of 3 numbers, their product and number of digits
# return (<numbers>, <product>)
def generate():
  # find two 3-digit primes, using different digits
  p = SubstitutedExpression(
    ["is_prime(ABC)", "is_prime(DEF)", "A < D"],
    answer="(ABC, DEF, GHIJ)",
  )
  for ns in p.answers(verbose=0):
    p = multiply(ns)
    yield (ns, p)

# group candidates by (<digit length>, <parity>) of the product
g = group(generate(), by=unpack(lambda ns, p: (ndigits(p), p % 2)))

# look for candidate sets that are unique by (<digit length>, <parity>) of the product
for ((k, m), vs) in g.items():
  if len(vs) != 1: continue
  # check there are solutions of the other parity
  if not g.get((k, 1 - m)): continue
  # output solution
  (ns, p) = vs[0]
  printf("{k} digits -> parity {m} -> {ns} = {p}")

Solution: The three numbers are: 109, 367, 2485.

The product is 99407455, which is 8-digits long. But there are 15 different products that are 8 digits long, so we cannot tell which set of numbers we started with, knowing only the number of digits in the product.

However there is only one 8-digit product that is odd, and only one set of numbers that gives this product, and so provides the answer to the puzzle.

LikeLike

Jim Randell 9:37 am on 20 July 2024 Permalink | Reply

In fact it enough to know the solution is unique by (<digit length>, <parity>) of the product. There is only a single candidate, so the additional check that the digit length alone is not sufficient to determine the product is not required (although a complete solution should verify it).

But this leads to a shorter program:

from enigma import (
  SubstitutedExpression, multiply, ndigits,
  filter_unique, unpack, printf
)

# find possible sets of 3 numbers, their product and number of digits
# return (<numbers>, <product>)
def generate():
  # find two 3-digit primes, using different digits
  p = SubstitutedExpression(
    ["is_prime(ABC)", "is_prime(DEF)", "A < D"],
    answer="(ABC, DEF, GHIJ)",
  )
  for ns in p.answers(verbose=0):
    p = multiply(ns)
    yield (ns, p)

# answer is unique by (<digit length>, <parity>) of product
f = unpack(lambda ns, p: (ndigits(p), p % 2))
for (ns, p) in filter_unique(generate(), f).unique:
  # output solution
  printf("{k} digits -> parity {m} -> {ns} = {p}", k=ndigits(p), m=p % 2)

LikeLike

Frits 5:52 pm on 19 July 2024 Permalink | Reply

from itertools import permutations

# prime numbers between 101 and 1000 with different digits
P = [3, 5, 7]
P += [x for x in range(11, 100, 2) if all(x % p for p in P)]
P = [str(x) for x in range(101, 1000, 2) if all(x % p for p in P) and 
                                            len(set(str(x))) == 3]                                           

# product of two 3-digit numbers and a 4-digit number has length 8, 9 or 10
impossible = {8: 0, 9: 0, 10: 0}
d, dgts = dict(), set("0123456789")

# choose two prime numbers
for i, p1 in enumerate(P[:-1]):
  for p2 in P[i + 1:]:
    # different digits
    if len(s12 := set(p1 + p2)) != 6: continue
    p1_x_p2 = int(p1) * int(p2)
    
    # break if for high products we can never work out all the three numbers
    if impossible[9] and impossible[10] and p1_x_p2 > 99999: break

    # consider all variants of the third number
    for p in permutations(dgts - s12):
      if (n3 := int(''.join(p)) ) < 1000: continue
      # check if we already have enough entries for this (length, parity)
      if impossible[ln := len(str(prod := p1_x_p2 * n3))]: continue
      # store length/parity
      d[(ln, par)] = d.get((ln, par := prod % 2), []) + [(p1, p2, str(n3))]
      # if a length for both parities already has 2 entries or more
      # then remember this for subsequent processing
      if all((ln, par) in d and len(d[(ln, par)]) > 1 for par in [0, 1]):
        impossible[ln] = 1

# check all possible solutions    
for (ln, par), vs in d.items():
  # no uniqueness?
  if impossible[ln]: continue
  # can we work out all the three numbers?
  if len(vs) == 1 and (ln, 1 - par) in d:
    print("answer:", ', '.join(vs[0]))

LikeLike

GeoffR 12:16 pm on 20 July 2024 Permalink | Reply

Trial testing showed that there were 8, 9 or 10 digits in the product of the three numbers.


from itertools import permutations
from enigma import is_prime

from collections import defaultdict
dlen = defaultdict(list)
key = 0

for p1 in permutations('1234567890'):
    A, B, C, D, E, F, G, H, I, J = p1
    if '0' in (A, D, G):continue
    ABC = int(A + B + C)
    if not is_prime(ABC):continue
    DEF = int(D + E + F )
    if D < A:continue
    if not is_prime(DEF):continue
    GHIJ = int(G + H + I + J)
    # product of two  primes and a 4-digit number
    prod = ABC * DEF * GHIJ

    # Classify products for length and parity
    # Assume the products are 8, 9 or 10 digit in length
    if len(str(prod)) == 8 and prod % 2 == 0: key = 1
    if len(str(prod)) == 8 and prod % 2 == 1: key = 2
    if len(str(prod)) == 9 and prod % 2 == 0: key = 3
    if len(str(prod)) == 9 and prod % 2 == 1: key = 4
    if len(str(prod)) == 10 and prod % 2 == 0: key = 5
    if len(str(prod)) == 10 and prod % 2 == 1: key = 6

    # update dictionary
    dlen[key] += [ (prod, (ABC, DEF, GHIJ))]

for k, v in dlen.items():
    # Answer is a single entry in dictionary
    if len(v) == 1:
        print('Ans = ', k, v)
    # find number of products in each group
    if k == 1: print(k, len(v))
    if k == 2: print(k, len(v))
    if k == 3: print(k, len(v))
    if k == 4: print(k, len(v))
    if k == 5: print(k, len(v))
    if k == 6: print(k, len(v))

LikeLike

Ruud 2:23 pm on 20 July 2024 Permalink | Reply

Quite similar to @Frits, just a it more brute force.

from istr import istr
from collections import defaultdict


def is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    k = 3
    while k * k <= n:
        if n % k == 0:
            return False
        k += 2
    return True


collect = defaultdict(list)

for n1 in istr(range(100, 988)):
    if not is_prime(int(n1)):
        continue
    if not n1.all_distinct():
        continue
    for n2 in istr.range(n1 + 1, 988):
        if not is_prime(n2):
            continue
        if not (n1 | n2).all_distinct():
            continue
        for n3 in istr.concat(istr.permutations((c for c in istr.digits() if c not in n1 | n2))):
            if n3 < 1000:
                continue
            product = n1 * n2 * n3
            collect[len(product), product.is_odd()].append((n1, n2, n3))

for v in collect.values():
    if len(v) == 1:
        print(*map(int, v[0]))

LikeLike

Jim Randell 6:28 pm on 14 July 2024 Permalink | Reply
Tags: by: E. R. J. Benson ( 2 )

Brainteaser 1081: Trifling troubles

From The Sunday Times, 24th April 1983 [link]

Fred and I usually do the washing and drying up in our commune. Fred always washes the largest saucepan first, then the second largest, and so on down to the smallest. In this way I can dry them and store them away in the order they were washed, by putting one saucepan inside the previously washed saucepan, ending up with a single pile.

Yesterday, the cook misread the quantities for the sherry trifle recipe, with the result that Fred got the washing up order completely wrong. For example, he washed the second smallest saucepan immediately after the second largest; and the smallest saucepan immediately before the middle-sized saucepan (i.e. the saucepan with as many saucepans larger than it as there are smaller).

I realised something was wrong when, having started to put the saucepans away in the usual manner, one of the saucepans did not fit the previously washed saucepan; so I started a second pile. Thereafter each saucepan either fitted in to one, but only one pile, or did not fit into any pile, in which case I started another pile.

We ended up with a number of piles, each containing more than one saucepan. The first pile to be completed contained more saucepans than the second, which contained more than the third etc.

In what order were the saucepans washed up? (Answers in the form a, b, c, …, numbering the saucepans from 1 upwards, 1 being the smallest).

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

[teaser1081]

Jim Randell 6:29 pm on 14 July 2024 Permalink | Reply

There must be an odd number of pans (in order for there to be a middle sized one), and there must be at more than 3 pans (so that the second largest is different from the second smallest).

This Python program considers possible orderings of pans that fit the conditions, and then attempts to organise them into piles that meet the requirements.

It runs in 169ms. (Internal runtime is 96ms).

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

# organise the sequence of pans into piles
def organise(ss):
  (ps, i) = ([], 0)
  for n in ss:
    # find placement for n
    js = list(j for (j, p) in enumerate(ps) if n < p[-1])
    if len(js) > 1: return None
    if len(js) == 1:
      ps[js[0]].append(n)
    else:
      ps.append([n])
  return ps

# solve for n pans
def solve(n):
  assert n % 2 == 1
  # allocate numbers to the pans
  ns = list(irange(1, n))
  k = 0
  # choose an ordering for the pans
  for ss in subsets(ns, size=len, select='P'):
    # check ordering conditions:
    # the 2nd smallest (2) is washed immediately after the 2nd largest (n - 1)
    # the smallest (1) is washed immediately before the middle ((n + 1) // 2)
    if not (ss.index(2) == ss.index(n - 1) + 1): continue
    if not (ss.index(1) + 1 == ss.index((n + 1) // 2)): continue
    # organise the pans into piles
    ps = organise(ss)
    if ps and len(ps) > 1 and is_decreasing([len(p) for p in ps] + [1], strict=1):
      # output solution
      printf("{n} pans; {ss} -> {ps}")
      k += 1
  return k

# solve for an odd number of pans > 3
for n in irange(5, inf, step=2):
  k = solve(n)
  if k:
    printf("[{n} pans -> {k} solutions]")
    break

Solution: The order of the pans was: 9, 8, 2, 1, 5, 4, 3, 7, 6.

Which gives 3 piles:

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

To explore larger number of pans it would probably be better to use a custom routine that generates orders with the necessary conditions, rather than just generate all orders and reject those that are not appropriate.

LikeLike

Ruud 5:52 pm on 15 July 2024 Permalink | Reply

I am working on a fast recursive algorithm and find four solutions for n=9
9 7 6 1 , 5 4 3 , 8 2
9 7 6 3 , 8 2 1 , 5 4
9 7 6 4 , 8 2 1 , 5 3
9 8 2 1 , 5 4 3 , 7 6
The last one matches yours. But aren’t the others valid? Did I miss a condition?

LikeLike
- Jim Randell 6:22 pm on 15 July 2024 Permalink | Reply
  
  @Ruud: In your first three sequences when you get the 2 pan you could put it into either of two available piles, so they are not viable sequences.
  
  LikeLike

Ruud 6:54 am on 16 July 2024 Permalink | Reply

I have solved this with a recursive algorithm, which is significantly faster than Jim’s but still very slow when the number of pans becomes >= 15.
Here’s the code:

from itertools import count

def wash(remaining_pans, last_pan, piles, washed_pans):
    if not remaining_pans:
        if all(len(piles1) > len(piles2) > 1 for piles1, piles2 in zip(piles, piles[1:])):
            print(piles, washed_pans)
        return
    if len(piles) > max_number_of_piles:
        return

    for pan in remaining_pans:
        if pan != 2 and last_pan == (n - 1):
            continue
        if pan != (n + 1) // 2 and last_pan == 1:
            continue
        if pan == 2 and last_pan != (n - 1):
            continue
        if pan == (n + 1) // 2 and last_pan != 1:
            continue
        selected_pile = None
        for pile in piles:
            if pile[-1] > pan:
                if selected_pile is None:
                    selected_pile = pile
                else:
                    selected_pile = None
                    break
        if selected_pile is None:
            wash(
                last_pan=pan,
                remaining_pans=[ipan for ipan in remaining_pans if ipan != pan],
                piles=[pile[:] for pile in piles] + [[pan]],
                washed_pans=washed_pans + [pan],
            )
        else:
            wash(
                last_pan=pan,
                remaining_pans=[ipan for ipan in remaining_pans if ipan != pan],
                piles=[pile + [pan] if pile == selected_pile else pile[:] for pile in piles],
                washed_pans=washed_pans + [pan],
            )


for n in count(5,2):
    print(f'number of pans = {n}')
    max_number_of_piles=0
    cum_pile_height=0
    for pile_height in count(2):
        cum_pile_height+=pile_height
        max_number_of_piles+=1
        if cum_pile_height>=n: 
            break
    wash(last_pan=0, remaining_pans=range(1, n + 1), piles=[], washed_pans=[])

LikeLike

Frits 4:52 pm on 18 July 2024 Permalink | Reply

@Ruud,

“cum_pile_height” probably must be initialized to 1 to get the correct pile_height for n = 15.

With some more checks (like “if len(piles) > 1 and len(piles[-1]) >= len(piles[-2]): return”) your program runs faster:

 
pypy TriflingTroubles1.py
2024-07-18 17:47:39.184252 number of pans = 5
2024-07-18 17:47:39.186248 n = 5 pile_height = 2 max_number_of_piles = 1 cum_pile_height = 3
2024-07-18 17:47:39.188241 n = 5 pile_height = 3 max_number_of_piles = 2 cum_pile_height = 6
2024-07-18 17:47:39.191231 number of pans = 7
2024-07-18 17:47:39.191231 n = 7 pile_height = 2 max_number_of_piles = 1 cum_pile_height = 3
2024-07-18 17:47:39.192234 n = 7 pile_height = 3 max_number_of_piles = 2 cum_pile_height = 6
2024-07-18 17:47:39.192234 n = 7 pile_height = 4 max_number_of_piles = 3 cum_pile_height = 10
2024-07-18 17:47:39.194224 number of pans = 9
2024-07-18 17:47:39.194224 n = 9 pile_height = 2 max_number_of_piles = 1 cum_pile_height = 3
2024-07-18 17:47:39.194224 n = 9 pile_height = 3 max_number_of_piles = 2 cum_pile_height = 6
2024-07-18 17:47:39.195221 n = 9 pile_height = 4 max_number_of_piles = 3 cum_pile_height = 10
[[9, 8, 2, 1], [5, 4, 3], [7, 6]] [9, 8, 2, 1, 5, 4, 3, 7, 6]
2024-07-18 17:47:39.202204 number of pans = 11
2024-07-18 17:47:39.204206 n = 11 pile_height = 2 max_number_of_piles = 1 cum_pile_height = 3
2024-07-18 17:47:39.205194 n = 11 pile_height = 3 max_number_of_piles = 2 cum_pile_height = 6
2024-07-18 17:47:39.206192 n = 11 pile_height = 4 max_number_of_piles = 3 cum_pile_height = 10
2024-07-18 17:47:39.206192 n = 11 pile_height = 5 max_number_of_piles = 4 cum_pile_height = 15
2024-07-18 17:47:39.267028 number of pans = 13
2024-07-18 17:47:39.267460 n = 13 pile_height = 2 max_number_of_piles = 1 cum_pile_height = 3
2024-07-18 17:47:39.268462 n = 13 pile_height = 3 max_number_of_piles = 2 cum_pile_height = 6
2024-07-18 17:47:39.271365 n = 13 pile_height = 4 max_number_of_piles = 3 cum_pile_height = 10
2024-07-18 17:47:39.271365 n = 13 pile_height = 5 max_number_of_piles = 4 cum_pile_height = 15
2024-07-18 17:47:39.467843 number of pans = 15
2024-07-18 17:47:39.468983 n = 15 pile_height = 2 max_number_of_piles = 1 cum_pile_height = 3
2024-07-18 17:47:39.469985 n = 15 pile_height = 3 max_number_of_piles = 2 cum_pile_height = 6
2024-07-18 17:47:39.472540 n = 15 pile_height = 4 max_number_of_piles = 3 cum_pile_height = 10
2024-07-18 17:47:39.472540 n = 15 pile_height = 5 max_number_of_piles = 4 cum_pile_height = 15
2024-07-18 17:47:40.190655 number of pans = 17
2024-07-18 17:47:40.191653 n = 17 pile_height = 2 max_number_of_piles = 1 cum_pile_height = 3
2024-07-18 17:47:40.192626 n = 17 pile_height = 3 max_number_of_piles = 2 cum_pile_height = 6
2024-07-18 17:47:40.195803 n = 17 pile_height = 4 max_number_of_piles = 3 cum_pile_height = 10
2024-07-18 17:47:40.195803 n = 17 pile_height = 5 max_number_of_piles = 4 cum_pile_height = 15
2024-07-18 17:47:40.196803 n = 17 pile_height = 6 max_number_of_piles = 5 cum_pile_height = 21
2024-07-18 17:47:51.650183 number of pans = 19
2024-07-18 17:47:51.651412 n = 19 pile_height = 2 max_number_of_piles = 1 cum_pile_height = 3
2024-07-18 17:47:51.652742 n = 19 pile_height = 3 max_number_of_piles = 2 cum_pile_height = 6
2024-07-18 17:47:51.655439 n = 19 pile_height = 4 max_number_of_piles = 3 cum_pile_height = 10
2024-07-18 17:47:51.656182 n = 19 pile_height = 5 max_number_of_piles = 4 cum_pile_height = 15
2024-07-18 17:47:51.656182 n = 19 pile_height = 6 max_number_of_piles = 5 cum_pile_height = 21

LikeLike

Frits 4:58 pm on 18 July 2024 Permalink | Reply

@Ruud, Sorry, my first statement is incorrect (I forgot that each pile has to have more than one saucepan)

LikeLike

Frits 4:43 pm on 18 July 2024 Permalink | Reply

Runs within a second for up to 21 saucepans.

from itertools import combinations
from math import ceil

# triangular root
trirt = lambda x: 0.5 * ((8 * x + 1)**.5 - 1.0)

# check validity of sequence <s>
def check(n, p, s):
  if not s: return False
  # check second smallest and second largest
  if (n28 := (2 in s) + ((n - 1) in s)) == 0: return True
  if n28 == 1: return False
  return not((p2 := s.index(2)) <= 0 or s[p2 - 1] != n - 1)
  
def solve(n, h, ns, p, m, ss=[]):
  if not ns:
    yield ss
    return # prevent indentation
 
  # determine which numbers we have to select (besides smallest number)
  base = [x for x in ns[:-1] if x != h] if p == 1 else ns[:-1]
  if p == 2: # second pile starts with <h>
    base = [x for x in base if x < h]

  mn = max(0, ceil(trirt(len(ns))) - 1 - (p == 2))
  mx = min(len(base), n if not ss else len(ss[-1]) - 1)  
  for i in range(mn, mx + 1):
    for c in combinations(base, i):
      c += (ns[-1], )              # suffix lowest remaining number
      if p == 2 and h not in c: 
        c = (h, ) + c              # second pile starts with <h>
      if (m_ := m - len(c)) == 1:  # each containing more than one saucepan
        continue
      if check(n, p, c):           # check second smallest and second largest
        yield from solve(n, h, [x for x in ns if x not in c], p + 1, m_,
                         ss + [c])
      
M = 21                             # maximum number of saucepans
for n in range(5, M + 1, 2):
  print(f"number of saucepans: {n}")
  for c in solve(n, (n + 1) // 2, range(n, 0, -1), 1, n):
    print("-----------------", c)

LikeLike

Ruud 5:49 am on 19 July 2024 Permalink | Reply

@Frits
Can you explain this code/algortithm. The one letter varibiables don’t really help …

LikeLike

Frits 2:37 pm on 19 July 2024 Permalink | Reply

@Jim, please replace my code with this version with more comments and using header:

I noticed that each pile can be regarded as the result of a combinations() call with descending saucepan numbers.

from itertools import combinations
from math import ceil

# triangular root
trirt = lambda x: 0.5 * ((8 * x + 1)**.5 - 1.0)

# check validity of sequence <s> (2nd smallest 2nd largest logic)
def check(n, s):
  if not s: return False
  # check second smallest and second largest
  if (totSecSmallSecLarge := (2 in s) + ((n - 1) in s)) == 0: return True
  if totSecSmallSecLarge == 1: return False        # we need none or both
  # the 2nd smallest must be washed immediately after the 2nd largest 
  return not((p2 := s.index(2)) == 0 or s[p2 - 1] != n - 1)

# add a new pile of saucepans
# <n> = original nr of saucepans (middle one <h>), <ns> = saucepan nrs left,
# <p> = pile nr, <r> = nr of saucepans left (rest), <ss> = piles
def solve(n, h, ns, p, r, ss=[]):
  if not ns: # no more saucepans left
    yield ss
    return # prevent indentation
 
  # determine which numbers we have to use below in combinations() 
  # (besides smallest number)
  base = [x for x in ns[:-1] if x != h] if p == 1 else ns[:-1]
  if p == 2: # second pile starts with <h>
    base = [x for x in base if x < h] # only saucepan nrs below <h>

  # if triangular sum 1 + 2 + ... + y reaches nr of saucepans left <r> then we
  # need at least y + 1 saucepans (if r = tri(y) - 1 we only need y saucepans)
  mn = max(0, int(trirt(r)) - (p == 2))    
  # use less saucepans than in previous pile
  mx = min(len(base), n if not ss else len(ss[-1]) - 1)  
  
  # loop over number of saucepans to use for the next/this pile
  for i in range(mn, mx + 1):      # nr of saucepans needed besides smallest
    # pick <i> descending saucepan numbers for next/this pile
    for c in combinations(base, i):
      c += (ns[-1], )              # suffix lowest remaining saucepan number
      if p == 2 and h not in c:    # second pile starts with <h>
        c = (h, ) + c              
      if (r_ := r - len(c)) == 1:  # each containing more than one saucepan
        continue
      if check(n, c):              # check second smallest and second largest
        yield from solve(n, h, [x for x in ns if x not in c], p + 1, r_,
                         ss + [c])
      
M = 21                             # maximum number of saucepans (adjustable)
for n in range(5, M + 1, 2):       
  print(f"number of saucepans: {n}")
  # use a descending sequence of numbers n...1 so that combinations() will
  # also return a descending sequence of saucepan numbers
  for c in solve(n, (n + 1) // 2, range(n, 0, -1), 1, n):
    print("-----------------", c)

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 13 Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 6:51 pm on 4 September 2024 Permalink | Reply Tags: by: Angela Newing ( 39 )

Rate this:

Share:

Jim Randell 6:51 pm on 4 September 2024 Permalink | Reply

Frits 10:35 am on 5 September 2024 Permalink | Reply

Reply Cancel reply

Jim Randell 6:17 am on 1 September 2024 Permalink | Reply Tags: by: Colin Vout ( 38 )

Rate this:

Share:

Jim Randell 6:36 am on 1 September 2024 Permalink | Reply

Frits 3:00 pm on 2 September 2024 Permalink | Reply

Jim Randell 4:11 pm on 2 September 2024 Permalink | Reply

Frits 10:44 am on 1 September 2024 Permalink | Reply

Jim Randell 11:31 am on 2 September 2024 Permalink | Reply

Frits 2:48 pm on 2 September 2024 Permalink | Reply

Jim Randell 4:15 pm on 2 September 2024 Permalink | Reply

GeoffR 11:38 am on 2 September 2024 Permalink | Reply

Jim Randell 12:02 pm on 2 September 2024 Permalink | Reply

Frits 9:07 pm on 4 September 2024 Permalink | Reply

Jim Randell 11:11 am on 29 August 2024 Permalink | Reply Tags: by: Simon Massarella

Rate this:

Share:

Jim Randell 11:12 am on 29 August 2024 Permalink | Reply

Jim Randell 12:52 am on 25 August 2024 Permalink | Reply Tags: by: Victor Bryant ( 144 ), flawed ( 55 )

Rate this:

Share:

Jim Randell 1:30 am on 25 August 2024 Permalink | Reply

Jim Randell 10:27 am on 25 August 2024 Permalink | Reply

Jim Randell 7:26 am on 26 August 2024 Permalink | Reply

Ruud 5:05 pm on 26 August 2024 Permalink | Reply

Frits 12:02 pm on 28 August 2024 Permalink | Reply

Jim Randell 12:09 pm on 28 August 2024 Permalink | Reply

Ruud 1:13 pm on 25 August 2024 Permalink | Reply

Jim Randell 10:18 am on 22 August 2024 Permalink | Reply Tags: by: L Poulter

Rate this:

Share:

Jim Randell 10:20 am on 22 August 2024 Permalink | Reply

Frits 10:28 am on 23 August 2024 Permalink | Reply

Jim Randell 10:39 am on 23 August 2024 Permalink | Reply

Frits 4:53 pm on 22 August 2024 Permalink | Reply

Jim Randell 11:18 am on 20 August 2024 Permalink | Reply Tags: by: J S Rowley ( 9 )

Rate this:

Share:

Jim Randell 11:20 am on 20 August 2024 Permalink | Reply

Ruud 2:09 pm on 21 August 2024 Permalink | Reply

Lise Andreasen 10:27 pm on 20 August 2024 Permalink | Reply

Jim Randell 8:14 am on 21 August 2024 Permalink | Reply

Lise Andreasen 6:29 pm on 21 August 2024 Permalink | Reply

GeoffR 9:48 am on 21 August 2024 Permalink | Reply

Ruud 11:24 am on 22 August 2024 Permalink | Reply

Frits 4:10 pm on 22 August 2024 Permalink | Reply

Jim Randell 5:35 am on 18 August 2024 Permalink | Reply Tags: by: Howard Williams ( 44 )

Rate this:

Share:

Jim Randell 5:36 am on 18 August 2024 Permalink | Reply

Frits 11:24 am on 18 August 2024 Permalink | Reply

Frits 11:34 am on 18 August 2024 Permalink | Reply

GeoffR 6:23 pm on 18 August 2024 Permalink | Reply

Jim Randell 10:46 am on 15 August 2024 Permalink | Reply Tags: by: Robin Nayler ( 16 )

Rate this:

Share:

Jim Randell 10:46 am on 15 August 2024 Permalink | Reply

Jim Randell 8:21 am on 13 August 2024 Permalink | Reply Tags: by: Danny Roth ( 87 )

Rate this:

Share:

Jim Randell 8:22 am on 13 August 2024 Permalink | Reply

ruudvanderham 11:50 am on 13 August 2024 Permalink | Reply

Ruud 7:07 pm on 13 August 2024 Permalink | Reply

Jim Randell 5:54 pm on 14 August 2024 Permalink | Reply

Ruud 7:07 pm on 14 August 2024 Permalink | Reply

Jim Randell 6:51 pm on 4 September 2024 Permalink | Reply
Tags: by: Angela Newing ( 39 )

Jim Randell 6:17 am on 1 September 2024 Permalink | Reply
Tags: by: Colin Vout ( 38 )

Jim Randell 11:11 am on 29 August 2024 Permalink | Reply
Tags: by: Simon Massarella

Jim Randell 12:52 am on 25 August 2024 Permalink | Reply
Tags: by: Victor Bryant ( 144 ), flawed ( 55 )

Jim Randell 10:18 am on 22 August 2024 Permalink | Reply
Tags: by: L Poulter

Jim Randell 11:18 am on 20 August 2024 Permalink | Reply
Tags: by: J S Rowley ( 9 )

Jim Randell 5:35 am on 18 August 2024 Permalink | Reply
Tags: by: Howard Williams ( 44 )

Jim Randell 10:46 am on 15 August 2024 Permalink | Reply
Tags: by: Robin Nayler ( 16 )

Jim Randell 8:21 am on 13 August 2024 Permalink | Reply
Tags: by: Danny Roth ( 87 )

Jim Randell 7:04 am on 11 August 2024 Permalink | Reply
Tags: by: Stephen Hogg ( 64 )

Jim Randell 9:50 am on 7 August 2024 Permalink | Reply
Tags: by: Adrian Somerfield ( 13 )

Jim Randell 6:16 am on 4 August 2024 Permalink | Reply
Tags: by: John Owen ( 33 )

Jim Randell 9:44 am on 1 August 2024 Permalink | Reply
Tags: by: Andrew Skidmore ( 87 )

Jim Randell 8:40 am on 30 July 2024 Permalink | Reply
Tags: by: R Postill ( 20 )

Jim Randell 6:58 am on 28 July 2024 Permalink | Reply
Tags: by: Phil Jackson ( 2 )

Jim Randell 10:49 am on 25 July 2024 Permalink | Reply
Tags: by: J S Rowley ( 9 )