S2T2 | Solving Sunday Times Teasers

Recent Updates Page 11 Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 6:34 am on 15 December 2024 Permalink | Reply
Tags: by: Andrew Skidmore ( 87 )
Teaser 3247: In the bag
From The Sunday Times, 15th December 2024 [link] [link]

My set of snooker balls comprises 15 red balls, 6 “colours” (not red) and a white ball. From these, I have placed a number of balls in a bag such that if four balls are drawn at random the chance of them all being red is a two-digit whole number times the chance of them all being colours.

If I told you this whole number you would not be able to determine the numbers of reds and colours in the bag, but I can tell you that drawing four colours is a one in a whole number chance.

How many balls are in the bag and how many of them are red?

[teaser3247]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 6:52 am on 15 December 2024 Permalink | Reply
  See also: Teaser 2768 (also called “In the bag”).
  
  This Python program runs in 71ms. (Internal runtime is 1.5ms).
```
from enigma import (Rational, irange, multiset, multiply, div, filter_unique, unpack, printf)

Q = Rational()

# calculate probability of drawing <k> balls of type <X> from multiset <bs>
def prob(bs, k, X):
  (n, t) = (bs.count(X), bs.size())
  if n < k or t < k: return 0
  return multiply(Q(n - i, t - i) for i in irange(k))

# generate possible subsets of balls with the required probabilities
def generate(balls):
  bs0 = multiset(R=4, C=4)  # minimum number of reds/colours
  for bs in balls.difference(bs0).subsets():
    bs.update(bs0)
    (pR, pC) = (prob(bs, 4, 'R'), prob(bs, 4, 'C'))
    k = div(pR, pC)
    if k is None or k < 10 or k > 99: continue
    yield (bs, pR, pC, k)

# the set of snooker balls
balls = multiset(R=15, C=6, W=1)

# knowing the whole number <k> does not let us determine the number of reds and colours in <bs>
fn_k = unpack(lambda bs, pR, pC, k: k)
fn_RC = unpack(lambda bs, pR, pC, k: (bs.count('R'), bs.count('C')))
for (bs, pR, pC, k) in filter_unique(generate(balls), fn_k, fn_RC).non_unique:
  # but we want cases where pC = 1/N (for some integer N)
  if pC.numerator != 1: continue
  # output solution
  printf("{n} balls {bs} -> pR = {pR}, pC = {pC}, k = {k}", n=bs.size(), bs=bs.map2str())
```
  Solution: There are 13 balls in the bag, and 8 of them are red.
  
  And the other 5 are colours.
  
  The probability of drawing 4 red balls is:
  
  (8/13) × (7/12) × (6/11) × (5/10) = 14/143
  
  And the probability of drawing 4 coloured balls is:
  
  (5/13) × (4/12) × (3/11) × (2/10) = 1/143
  
  So the probability of drawing 4 red balls is 14 times the probability of drawing 4 coloured balls.
  
  But knowing this value is not sufficient, as there are 4 possible candidates where k = 14:
  
  13 balls (C=5, R=8) → pR = 14/143, pC = 1/143, k = 14
  14 balls (C=5, R=8, W=1) → pR = 10/143, pC = 5/1001, k = 14
  16 balls (C=6, R=10) → pR = 3/26, pC = 3/364, k = 14
  17 balls (C=6, R=10, W=1) → pR = 3/34, pC = 3/476, k = 14
  
  But only the first of these has pC = 1/N for some integer N.
  
  LikeLike
Reply Cancel reply
Required fields are marked *

Name *

Email *

Website

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

Jim Randell 10:50 am on 12 December 2024 Permalink | Reply
Tags: by: Andrew Skidmore ( 87 )

Teaser 2622: Christmas message

From The Sunday Times, 23rd December 2012 [link] [link]

In the message below the words represent numbers where the digits have consistently been replaced by letters, with different letters used for different digits:

A
MERRY
XMAS
2012
TO
YOU

In fact the largest of these six numbers is the sum of the other five.

What number is represented by MERRY?

[teaser2622]

Jim Randell 10:51 am on 12 December 2024 Permalink | Reply
We can solve this in a straightforward manner using the [[ SubstitutedExpression ]] solver from the enigma.py library.

The following run file executes in 555ms. (The internal runtime of the generated code is 506ms).
```
#! python3 -m enigma -rr

SubstitutedExpression

"A + XMAS + 2012 + TO + YOU = MERRY"

--answer="MERRY"
```
Solution: MERRY = 10552.

There are 4 possible sums, but the value of MERRY is the same in each of them:
```
A + XMAS + 2012 + TO + YOU = MERRY
6 + 8163 + 2012 + 97 + 274 = 10552
6 + 8164 + 2012 + 97 + 273 = 10552
7 + 8173 + 2012 + 96 + 264 = 10552
7 + 8174 + 2012 + 96 + 263 = 10552
```
A and O are 6 and 7 (in some order), and S and U are 3 and 4 (in some order). This gives rise to the 4 solutions above.

For a faster run time we can use the [[ SubstitutedExpression.split_sum ]] solver, which forms separate sums from the columns of the larger sum.

The following run file executes in 90ms. (And the internal runtime of the generated code is just 1.6ms).
```
#! python3 -m enigma -rr

SubstitutedExpression.split_sum

--symbols="AEMORSTUXY012"
--literal="012"
--distinct="AEMORSTUXY"

"A + XMAS + 2012 + TO + YOU = MERRY"

--answer="MERRY"
--solution="AEMORSTUXY"
```
LikeLike

GeoffR 1:28 pm on 12 December 2024 Permalink | Reply


from itertools import permutations

for p1 in permutations('0123456789', 5):
    a, m, e, r, y, = p1
    if '0' in (a, m, y): continue
    A, MERRY = int(a), int(m + e + r + r + y)
    q1 = set('0123456789').difference({a,m,e,r,y})
    for p2 in permutations(q1):
        x, s, t, o, u = p2
        if '0' in (x, t):continue
        XMAS, TO, YOU = int(x + m + a + s), int(t + o), int(y + o + u)
        if MERRY == A + XMAS + TO + YOU + 2012:
            print(f"MERRY = {MERRY}")
    
# MERRY = 10552

LikeLike

Ruud 5:18 am on 13 December 2024 Permalink | Reply

import istr

istr.repr_mode("str")
for a, m, e, r, y, x, s, t, o, u in istr.permutations(istr.digits(), 10):
    if not istr("0") in (a, m, x, t, y) and a + (x | m | a | s) + 2012 + (t | o) + (y | o | u) == (m | e | r | r | y):
        print(f"{a=} {x|m|a|s=} {2012=} {t|o=} {y|o|u=} {m|e|r|r|y=}")
print("done")

LikeLike

GeoffR 2:59 pm on 13 December 2024 Permalink | Reply

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

int: M == 1; % MERRY is the only 5-digit number
% .. and there are two 4-digit numbers

var 1..9:A; var 0..9:E; var 0..9:R; var 1..9:Y; var 1..9:X;
var 0..9:S; var 1..9:T ; var 0..9:O; var 0..9:U;

constraint all_different ([A, E, R, Y, X ,M, S, T, O, U]);

var 10000..99999:MERRY = 10000*M + 1000*E + 110*R + Y;
var 1000..9999:XMAS = 1000*X + 100*M + 10*A + S;
var 100..999:YOU = 100*Y + 10*O + U;
var 10..99:TO = 10*T + O;

constraint MERRY == A + XMAS + TO + YOU + 2012;

solve satisfy;
output ["MERRY = " ++ show(MERRY)];

% MERRY = 10552
% ----------
% ==========

LikeLike

Jim Randell 10:26 am on 10 December 2024 Permalink | Reply
Tags: by: C Higgins ( 37 ), by: H Bradley ( 37 )

Teaser 2560: Three trees

From The Sunday Times, 16th October 2011 [link] [link]

Our front garden is circular, with a diameter less than 100 metres. Three trees grow on the perimeter: an ash, a beech and a cherry, each a different whole number of metres from each of the other two. A straight trellis 84 metres long joins the ash to the beech, and a honeysuckle grows at the point on the trellis nearest to the cherry tree. The distance from the cherry to the ash plus the distance from the ash to the honeysuckle equals the distance from the cherry to the beech.

What is the diameter of the garden?

[teaser2560]

Jim Randell 10:26 am on 10 December 2024 Permalink | Reply
We represent the trees by points A, B, C on the perimeter of the circle.

If the sides of the triangle (opposite A, B, C) are a, b, c, then the diameter of the circumcircle d is given by:

d = (a . b . c) / 2T

where T is the area of the triangle.

In this case we have:

T = c . h / 2
⇒
d = a . b / h

and also:

a^2 = h^2 + c2^2
b^2 = h^2 + c1^2
a = b + c1

equating values for h^2 allows us to calculate a (and b) knowing c1 and c2:

a^2 − c2^2 = (a − c1)^2 − c1^2
c2^2 = 2a . c1
⇒
a = c2^2 / (2 . c1)

This Python program considers possible splits of c into integers c1, c2, and then checks that the resulting a, b values form a viable triangle.

It runs in 66ms. (Internal runtime is 84µs).
```
from enigma import (decompose, div, sq, rcs, fdiv, printf)

# split c into 2 integers
c = 84
for (c1, c2) in decompose(c, 2):

  # calculate a and b, and check (a, b, c) form a viable triangle
  a = div(sq(c2), 2 * c1)
  if a is None or not (a < 100): continue
  b = a - c1
  if not (b > 0 and a + b > c): continue

  # output solution
  h = rcs(a, -c2)
  d = fdiv(a * b, h)
  printf("c1={c1} c2={c2} -> a={a} b={b} c={c} -> h={h} d={d}")
```
Solution: The diameter of the garden is 85 metres.

The 84m trellis (AB) is split into 60m and 24m lengths by the honeysuckle. And the distances AC and BC are 51m and 75m.

And it turns out the height of the triangle is also an integer (h = 45), so we have two Pythagorean triples that share a non-hypotenuse length:

(24, 45, 51) = 3× (8, 15, 17)
(45, 60, 75) = 15× (3, 4, 5)

But the next smallest solution (which is eliminated by the d < 100 requirement) does not have an integer height (or diameter):

a = 121, b = 103, c1 = 18, c2 = 66
⇒
h = 11√85 ≈ 101.41, d = 1133/√85 ≈ 122.89

LikeLike

Frits 12:18 pm on 11 December 2024 Permalink | Reply

Trellis length 84 is cleverly chosen.
For D=100 we only have to investigate c1 values 22, 24 and 26.

The following program shows solutions with a integer diameter less than 1000 meters.

from math import ceil
D = 1000  #  with a diameter less than D metres

# a = c2**2 / (2 * c1) < D, (c - c1)**2 < 2 * D * c1, c1**2 - 2 * (D + c1) * c1 + c**2 < 0  
# (c1 - (D + c))**2 < (D + c)**2 - c**2
# c1 > D + c - ((D + c)**2 - c**2)**.5  
# c1 > 20.29

# a + b > 84 or c2**2 / c1 - c1 > 84 or (84 - c1)**2 / c1 - c1 > 84
# (84 - c1)**2 > c1**2 + 84 * c1 or 252 * c1 < 84**2
# c1 < 28

prt = 0

hdr = " (c1,  c2)   c2^2 2*c1 (        a,         b)     a + b          h          d   "
sols = []
for c in range(3, D):
  if prt: print(hdr) 
  min_c1 = int(D + c - ((D + c)**2 - c**2)**.5) + 1
  # c2 must be even if a is an integer
  #for c1 in range(1 + (c % 2 == 0), ceil(c / 3), 2): 
  for c1 in range(min_c1 + ((c - min_c1) % 2), ceil(c / 3), 2): 
    c2 = c - c1
    a = round(c2**2 / (2 * c1), 2)
    b = round(a - c1, 2)
    h = round((b**2 - c1**2)**.5 if b >= c1 else -1, 2)
    d = round(a * b / h if h > 0 else -1, 2)
    OK = (' OK' if a + b > c and int(a) == a and int(d) == d and 
                  all (x < D for x in [a, b, d]) else '')
    txt = (f"({c1:>3}, {c2:>3}) " + 
          f"{c2**2:>6} " + 
          f"{2 * c1:>3}  ({a:>9}, {b:>9}) " + 
          f"{round(a + b, 2):>9} " +
          f"{h:>10} " +
          f"{d:>10} " +
          f"{round(D + c - ((D + c)**2 - c**2)**.5, 2) :>8} < c1 < " + 
          f"{round(c / 3, 2):>6} " + 
          f"{OK}")
    if prt: print(txt)      
    if OK: 
      sols.append(txt)
    if h == -1: break   
    
print("solutions with a integer diameter:\n")  
print(hdr) 
for s in sols: 
  print(s)  

'''
solutions with a integer diameter:

 (c1,  c2)   c2^2 2*c1 (        a,         b)     a + b          h          d
(  1,  16)    256   2  (    128.0,     127.0)     255.0      127.0      128.0     0.14 < c1 <   5.67  OK
(  1,  18)    324   2  (    162.0,     161.0)     323.0      161.0      162.0     0.18 < c1 <   6.33  OK
(  1,  20)    400   2  (    200.0,     199.0)     399.0      199.0      200.0     0.22 < c1 <    7.0  OK
(  1,  22)    484   2  (    242.0,     241.0)     483.0      241.0      242.0     0.26 < c1 <   7.67  OK
(  1,  24)    576   2  (    288.0,     287.0)     575.0      287.0      288.0      0.3 < c1 <   8.33  OK
(  1,  26)    676   2  (    338.0,     337.0)     675.0      337.0      338.0     0.35 < c1 <    9.0  OK
(  1,  28)    784   2  (    392.0,     391.0)     783.0      391.0      392.0     0.41 < c1 <   9.67  OK
(  1,  30)    900   2  (    450.0,     449.0)     899.0      449.0      450.0     0.47 < c1 <  10.33  OK
(  1,  32)   1024   2  (    512.0,     511.0)    1023.0      511.0      512.0     0.53 < c1 <   11.0  OK
(  1,  34)   1156   2  (    578.0,     577.0)    1155.0      577.0      578.0     0.59 < c1 <  11.67  OK
(  1,  36)   1296   2  (    648.0,     647.0)    1295.0      647.0      648.0     0.66 < c1 <  12.33  OK
(  1,  38)   1444   2  (    722.0,     721.0)    1443.0      721.0      722.0     0.73 < c1 <   13.0  OK
(  1,  40)   1600   2  (    800.0,     799.0)    1599.0      799.0      800.0     0.81 < c1 <  13.67  OK
(  1,  42)   1764   2  (    882.0,     881.0)    1763.0      881.0      882.0     0.89 < c1 <  14.33  OK
(  2,  42)   1764   4  (    441.0,     439.0)     880.0      439.0      441.0     0.93 < c1 <  14.67  OK
(  1,  44)   1936   2  (    968.0,     967.0)    1935.0      967.0      968.0     0.97 < c1 <   15.0  OK
(  2,  44)   1936   4  (    484.0,     482.0)     966.0      482.0      484.0     1.01 < c1 <  15.33  OK
(  2,  46)   2116   4  (    529.0,     527.0)    1056.0      527.0      529.0      1.1 < c1 <   16.0  OK
(  2,  48)   2304   4  (    576.0,     574.0)    1150.0      574.0      576.0     1.19 < c1 <  16.67  OK
(  2,  50)   2500   4  (    625.0,     623.0)    1248.0      623.0      625.0     1.29 < c1 <  17.33  OK
(  2,  52)   2704   4  (    676.0,     674.0)    1350.0      674.0      676.0     1.38 < c1 <   18.0  OK
(  2,  54)   2916   4  (    729.0,     727.0)    1456.0      727.0      729.0     1.49 < c1 <  18.67  OK
(  2,  56)   3136   4  (    784.0,     782.0)    1566.0      782.0      784.0     1.59 < c1 <  19.33  OK
(  2,  58)   3364   4  (    841.0,     839.0)    1680.0      839.0      841.0      1.7 < c1 <   20.0  OK
(  2,  60)   3600   4  (    900.0,     898.0)    1798.0      898.0      900.0     1.81 < c1 <  20.67  OK
(  2,  62)   3844   4  (    961.0,     959.0)    1920.0      959.0      961.0     1.93 < c1 <  21.33  OK
( 24,  60)   3600  48  (     75.0,      51.0)     126.0       45.0       85.0     3.26 < c1 <   28.0  OK
( 36, 120)  14400  72  (    200.0,     164.0)     364.0      160.0      205.0    10.57 < c1 <   52.0  OK
( 48, 120)  14400  96  (    150.0,     102.0)     252.0       90.0      170.0    12.15 < c1 <   56.0  OK
( 46, 138)  19044  92  (    207.0,     161.0)     368.0     154.29      216.0    14.38 < c1 <  61.33  OK
( 32, 192)  36864  64  (    576.0,     544.0)    1120.0     543.06      577.0    20.67 < c1 <  74.67  OK
( 42, 210)  44100  84  (    525.0,     483.0)    1008.0     481.17      527.0    25.62 < c1 <   84.0  OK
( 72, 180)  32400 144  (    225.0,     153.0)     378.0      135.0      255.0    25.62 < c1 <   84.0  OK
( 81, 180)  32400 162  (    200.0,     119.0)     319.0      87.18      273.0    27.31 < c1 <   87.0  OK
( 36, 228)  51984  72  (    722.0,     686.0)    1408.0     685.05      723.0    27.88 < c1 <   88.0  OK
( 72, 240)  57600 144  (    400.0,     328.0)     728.0      320.0      410.0    37.64 < c1 <  104.0  OK
( 96, 240)  57600 192  (    300.0,     204.0)     504.0      180.0      340.0    42.94 < c1 <  112.0  OK
( 92, 276)  76176 184  (    414.0,     322.0)     736.0     308.58      432.0    50.43 < c1 < 122.67  OK
(120, 300)  90000 240  (    375.0,     255.0)     630.0      225.0      425.0    63.53 < c1 <  140.0  OK
(108, 360) 129600 216  (    600.0,     492.0)    1092.0      480.0      615.0     76.6 < c1 <  156.0  OK
(144, 360) 129600 288  (    450.0,     306.0)     756.0      270.0      510.0    86.96 < c1 <  168.0  OK
(162, 360) 129600 324  (    400.0,     238.0)     638.0     174.36      546.0    92.31 < c1 <  174.0  OK
(168, 420) 176400 336  (    525.0,     357.0)     882.0      315.0      595.0   112.87 < c1 <  196.0  OK
(144, 480) 230400 288  (    800.0,     656.0)    1456.0      640.0      820.0   124.67 < c1 <  208.0  OK
(192, 480) 230400 384  (    600.0,     408.0)    1008.0      360.0      680.0   140.99 < c1 <  224.0  OK
(198, 528) 278784 396  (    704.0,     506.0)    1210.0     465.65      765.0   160.11 < c1 <  242.0  OK
(216, 540) 291600 432  (    675.0,     459.0)    1134.0      405.0      765.0   171.07 < c1 <  252.0  OK
(240, 600) 360000 480  (    750.0,     510.0)    1260.0      450.0      850.0   202.93 < c1 <  280.0  OK
(264, 660) 435600 528  (    825.0,     561.0)    1386.0      495.0      935.0    236.4 < c1 <  308.0  OK
'''

LikeLike

Jim Randell 9:30 am on 12 December 2024 Permalink | Reply
@Frits: Your code gives solutions that are close to a whole number of metres, rather than exactly a whole number of metres.

For example, the first configuration you give:

a = 128; b = 127; c1 = 1; c2 = 16
⇒
h ≈ 126.996; d ≈ 128.004

Here is some code that looks for pairs of Pythagorean triples that share a non-hypotenuse side to find solutions where h and d are (exact) integers:
```
from enigma import (defaultdict, pythagorean_triples, subsets, div, arg, printf)

D = arg(100, 0, int)
printf("[d < {D}]")

# collect pythagorean triples by non-hypotenuse sides
d = defaultdict(list)
for (x, y, z) in pythagorean_triples(D - 1):
  d[x].append((y, z))
  d[y].append((x, z))

# look for pairs of triangles
for (h, ts) in d.items():
  if len(ts) < 2: continue

  for ((c1, b), (c2, a)) in subsets(sorted(ts), size=2):
    c = c1 + c2
    if not (a == b + c1 and c < D): continue
    d = div(a * b, h)
    if d is None: continue

    printf("a={a} b={b} c={c} -> c1={c1} c2={c2} h={h} d={d}")
```
Note that if h is an integer, then d will be rational (but not necessarily an integer).

LikeLike
- Frits 11:26 am on 12 December 2024 Permalink | Reply
  
  @Jim, you are right.
  
  I get the same output as your program if I only do rounding during printing (which I should have done).
  
  LikeLike

Brian Gladman 6:56 pm on 13 December 2024 Permalink | Reply

Finding all solutions:

# (a - b).(a + b + 2.c) =  c^2 = p.q with p < q
# 
# a - b = p        )  a = (p + q) / 2 - c
# a + b + 2.c = q  )  b = a - p

from enigma import divisor_pairs
from fractions import Fraction as RF

c = 84
print('   a    b              d^2')
for p, q in divisor_pairs(c * c):
  t, r = divmod(p + q, 2)
  a = t - c
  b = a - p
  if not r and a > 0 and 2 * b > a:
    d2 = RF(a * b * b, b + b - a)
    print(f"{a:4} {b:4} {d2:16}")

LikeLike

GeoffR 10:59 am on 14 December 2024 Permalink | Reply


% A Solution in MiniZinc - using Jim's variable notations
include "globals.mzn";

int: c == 84; % given distance between ash and beech trees

var 1..100:a; var 1..100:b; var 1..100:c1; 
var 1..100:c2; var 1..100:h; 
var 1..5000: T; % UB = 100 * 100/2
var 1..99:d; % circle diameter < 100

constraint all_different ([a, b, c]);
constraint c == c1 + c2;
constraint 2 * T * d == a * b * c;
constraint a == b + c1;
constraint c1 * c1 + h * h == b * b;
constraint c2 * c2 + h * h == a * a;
constraint 2 * T == c * h;

% Triangle formation constraints
constraint a + b > c /\ b + c > a /\ a + c > b;

solve satisfy;

output ["[a, b, c] = " ++ show([a, b, c]) ++
"\n" ++ "[c1, c2, h] = " ++ show( [c1, c2, h]) ++
"\n" ++ "Circle diameter = " ++ show(d) ++ " metres"];

% [a, b, c] = [75, 51, 84]
% [c1, c2, h] = [24, 60, 45]
% Circle diameter = 85 metres
% ----------
% ==========

LikeLike

Jim Randell 9:03 am on 8 December 2024 Permalink | Reply
Tags: by: Stephen Hogg ( 64 )
Teaser 3246: Power Rearrangers – “Morphing times”
From The Sunday Times, 8th December 2024 [link] [link]

Superhero classmates Ann, Ben and Col were Power Rearrangers with birthdays on three consecutive days in the same month. Using “morphing times” super-fast mental arithmetic, each raised that month number to the power of their own birthday number (e.g., June 2nd gives 36). Correctly calculated, the three values’ rightmost digits differed. In descending order, as a three-figure value, these digits made a multiple of the month number, but in ascending order, did not.

A new Power Rearranger recruit, Dee, joined the class. Her birthday was earlier, but the aforementioned statements also applied to Dee, Ann and Ben. Dee also raised her birthday number to the power of the month number. Curiously, this gave the same rightmost digit as when she did the former calculation.

Give Dee’s birthday as dd/mm (e.g. 31/01).

Apologies for the delay in posting this puzzle – we’ve just had a 19 hour power outage.

[teaser3246]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
ruudvanderham and Jim Randell are discussing. Toggle Comments
- Jim Randell 9:43 am on 8 December 2024 Permalink | Reply
  This Python program runs in 67ms. (Internal runtime is 378µs).
```
from enigma import (irange, tuples, seq_all_different, nconcat, rev, printf)

# check a sequence of digits
def check(m, ds):
  # they are all different
  if not seq_all_different(ds): return False
  # in descending order give a multiple of the month
  ds = sorted(ds, reverse=1)
  if nconcat(ds) % m > 0: return False
  # but not in ascending order
  if nconcat(rev(ds)) % m == 0: return False
  # looks good
  return True

# number of days in each month
mlen = dict(enumerate([31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31], start=1))

# consider possible months
for (m, n) in mlen.items():
  # (day, digit) pairs for the month
  vs = ((d, pow(m, d, 10)) for d in irange(1, n))
  # consider four consecutive (day, digit) in some month
  for ((D, dD), (A, dA), (B, dB), (C, dC)) in tuples(vs, 4):
    # check D's digit is the same as day^month
    if not (dD == pow(D, m, 10)): continue
    # check (A, B, C) and (D, A, B)
    if not (check(m, [dA, dB, dC]) and check(m, [dD, dA, dB])): continue
    # output solution
    printf("A={A} B={B} C={C} D={D} m={m} -> ds={ds}", ds=[dA, dB, dC, dD])
```
  Solution: Dee’s birthday is: 13/07.
  
  So:
  
  D = 13/07; 7^13 mod 10 = 7; 13^7 mod 10 = 7
  A = 14/07; 7^14 mod 10 = 9
  B = 15/07; 7^15 mod 10 = 3
  C = 16/07; 7^16 mod 10 = 1
  
  And:
  
  931 ÷ 7 = 133
  139 ÷ 7 = 19.86…
  
  973 ÷ 7 = 139
  379 ÷ 7 = 54.14…
  
  LikeLike
- ruudvanderham 2:54 pm on 9 December 2024 Permalink | Reply
```
from calendar import monthrange
import istr

for month in range(1, 13):
    for d in range(1, monthrange(2024, month)[1] - 3 + 1):
        for dis in (0, 1):
            last_three = {str(month ** (d + dis + i))[-1] for i in range(3)}
            ascending = "".join(sorted(last_three))
            descending = "".join(sorted(last_three, reverse=True))
            if not (len(last_three) == 3 and istr.is_divisible_by(descending, month) and not istr.is_divisible_by(ascending, month)):
                break
        else:
            if str(month**d)[-1] == str(d**month)[-1]:
                print(f"{d:02}/{month:02}")
```
  LikeLike
Jim Randell 9:25 am on 6 December 2024 Permalink | Reply
Tags: by: Andrew Skidmore ( 87 )
Teaser 2618: Antics on the block
From The Sunday Times, 25th November 2012 [link] [link]

A wooden cuboid-shaped block has a square base. All its sides are whole numbers of centimetres long, with the height being the shortest dimension. Crawling along three edges, an ant moves from a top corner of the block to the furthest-away bottom corner. In so doing it travels ten centimetres further than if it had chosen the shortest route over the surface of the block.

What are the dimensions of the block?

[teaser2618]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 9:25 am on 6 December 2024 Permalink | Reply
  If the square base has dimensions x by x, and the block has height h, where h < x.
  
  Opening up the cuboid like a cardboard box gives us the minimal distance = hypot(x, x + h).
  
  This gives a straightforward program:
```
from enigma import (irange, ihypot, printf)

# consider the size of the square
for x in irange(2, 16):
  # consider the height
  for h in irange(1, x - 1):
    # shortest distance
    d = ihypot(x, x + h)
    if not d: continue
    if h + 2 * x == d + 10:
      printf("{x} x {x} x {h}")
```
  Solution: The block is: 15 cm × 15 cm × 5 cm.
  
  With a little analysis we can get a shorter program.
  
  We have:
  
  2x + h = hypot(x, x + h) + 10
  ⇒
  (2x + h − 10)² = x² + (x + h)²
  2x² + 2(h − 20)x + 20(5 − h) = 0
  x² + (h − 20)x + 10(5 − h) = 0
  
  So, by considering possible values of h, we get a quadratic in x, which can be solved for integer values.
```
from enigma import (irange, quadratic, printf)

# consider increasing heights
for h in irange(1, 16):
  # find integer x values
  for x in quadratic(1, h - 20, 10 * (5 - h), domain='Z'):
    if x > h:
      printf("{x} x {x} x {h}")
```
  LikeLike
Jim Randell 9:57 am on 3 December 2024 Permalink | Reply
Tags: by: John Owen ( 33 )
Teaser 2600: Mileometer
From The Sunday Times, 22nd July 2012 [link] [link]

My car’s digital mileometer has five digits, displaying whole miles. It also has a trip meter with five digits, displaying tenths of a mile (which resets to zero when reaching 10,000 miles). Soon after the car was new I reset the trip meter to zero (but never did that again). Not long after, I noticed that the two five-digit displays were the same ignoring the decimal point). The next time the displays were the same I wrote down the mileage and did so on each subsequent occasion until the mileage reached 100,000. The sum of all the mileages I wrote down was 500,000.

What were the five digits when the displays were first the same?

[teaser2600]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 9:57 am on 3 December 2024 Permalink | Reply
  Suppose the readings are the same at a distance ABCDE+F miles (the +F indicates + F tenths of a mile), then the readings are:
  
  milometer = ABCDE
  trip meter = ABCD+E
  
  The trip meter is actually reading XABCD+E miles, since it was reset, for some non-visible digit X.
  
  Which means the trip meter was reset at an actual distance of:
  
  ABCDE+F − XABCD+E
  
  And we want this to be soon after the car was new, maybe in the first 10K miles.
  
  This Python program looks at distances of possible duplicated readings, and collects them by the trip reset distance. It then looks for a distance where the sum of the milometer readings (except for the first one) is 500000.
  
  It runs in 530ms (using PyPy).
```
from enigma import (defaultdict, irange, subsets, nconcat, trim, printf)

# collect readings by reset distance
rs = defaultdict(list)

# consider possible 6-digit distances (in 0.1 mile units)
for (A, B, C, D, E, F) in subsets(irange(0, 9), size=6, select='M'):
  dist = nconcat(A, B, C, D, E, F)
  for X in irange(max(0, A - 1), A):
    # consider trip distances that match the milometer (in 0.1 mile units)
    trip = nconcat(X, A, B, C, D, E)
    # calculate trip reset point
    k = dist - trip
    if not (0 < k < 100000): continue
    rs[k].append(dist)

# output the milometer/trip readings
def output(d, k):
  (m, f) = divmod(d, 10)
  (t, g) = divmod(d - k, 10)
  t %= 10000
  printf("@ {m:05d}.{f} miles -> {m:05d} + {t:04d}.{g}")

# consider possible reset distances
for (k, vs) in rs.items():
  vs = sorted(vs)
  # sum the milometer readings (except the first one)
  t = sum(v // 10 for v in trim(vs, head=1))
  if t == 500000:
    # output solution
    output(k, k)
    for v in vs: output(v, k)
    printf("t = {t}")
    printf()
```
  Solution: When the displays were first the same they were showing 01235 (or 0123.5 for the trip meter).
  
  The trip meter was reset as a distance of 1111.6 miles, and so the readings were:
  
  @ 01111.6 miles → 01111 + 0000.0 [trip reset]
  @ 01235.1 miles → 01235 + 0123.5 [1st equal display]
  @ 12346.2 miles → 12346 + 1234.6 [2nd equal display – noted down]
  @ 23457.3 miles → 23457 + 2345.7 [3rd equal display – noted down]
  @ 34568.4 miles → 34568 + 3456.8 [4th equal display – noted down]
  @ 45679.5 miles → 45679 + 4567.9 [5th equal display – noted down]
  @ 56790.6 miles → 56790 + 5679.0 [6th equal display – noted down]
  @ 67901.7 miles → 67901 + 6790.1 [7th equal display – noted down]
  @ 79012.8 miles → 79012 + 7901.2 [8th equal display – noted down]
  @ 90123.9 miles → 90123 + 9012.3 [9th equal display – noted down]
  @ 90124.0 miles → 90124 + 9012.4 [10th equal display – noted down]
  
  And the sum of the values noted down is:
  
  12346 + 23457 + 34568 + 45679 + 56790 + 67901 + 79012 + 90123 + 90124
  = 500000
  
  LikeLike
Jim Randell 7:03 am on 1 December 2024 Permalink | Reply
Tags: by: Mark Valentine ( 17 )
Teaser 3245: Gate escape
From The Sunday Times, 1st December 2024 [link] [link]

In front of you are six consecutive 200m sections, each gated at the far end, then you are free. Above your head a clock ticks. Each gate is open for four seconds, but then closed for a different single-digit number of seconds. The gates all open together every 143 minutes and are ordered by increasing closure time, with the nearest gate having the shortest closure time.

Running at your highest possible constant speed, you will reach the end precisely four minutes after entry. If you go any slower, you will be caught by the guards. You wait to enter to ensure that, going at this speed, you pass through each gate in the middle of its open time.

How many seconds after the gates open together do you enter?

[teaser3245]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 7:38 am on 1 December 2024 Permalink | Reply
  See also: Enigma 198.
  
  There are only 6 possible single-digit closed durations that allow a whole number of open/closed cycles in a 143 minute period, so we can determine the cycles of each gate.
  
  We can then try possible start times to see when we would hit each gate 2 seconds into an open period.
  
  This Python program runs in 68ms. (Internal runtime is 200µs).
```
from enigma import (irange, subsets, printf)

# look for single digit closed durations
T = 143 * 60  # cycle time (seconds)
ts = list(t for t in irange(1, 9) if T % (4 + t) == 0)
printf("[closed durations = {ts}]")

# consider possible closed durations for the 6 gates (in order)
for ss in subsets(ts, size=6, select='C'):
  # consider possible start times
  for t0 in irange(0, T - 240):
    # gates are open for 4s at the start of each (4 + t) period
    # do we hit each gate 2s after it opens?
    if all((t0 + 40 * i) % (4 + t) == 2 for (i, t) in enumerate(ss, start=1)):
      printf("{ss} -> t0 = {t0}")
      break
```
  Solution: You should enter the first section 282 seconds after the gates open together.
  
  The gate closed durations are (1, 2, 6, 7, 8, 9) seconds.
  
  It takes 40s to run through each section to the gate, and:
  
  282 + 40 = 322 = 64×(4 + 1) + 2
  322 + 40 = 362 = 60×(4 + 2) + 2
  362 + 40 = 402 = 40×(4 + 6) + 2
  402 + 40 = 442 = 40×(4 + 7) + 2
  442 + 40 = 482 = 40×(4 + 8) + 2
  482 + 40 = 552 = 40×(4 + 9) + 2
  
  LikeLike
  - Jim Randell 3:10 pm on 1 December 2024 Permalink | Reply
    Once we have determined the closed duration for each gate, we can form a set of congruence equations of the form:
    
    t0 mod m = n
    
    one for each gate, where the m and n parameters are defined by the closed duration and distance for that gate.
    
    These can then be solved using the Chinese Remainder Theorem (CRT). (The CRT implementation in enigma.py is based on the code from Teaser 3117).
    
    The internal runtime is reduced to 65µs.
```
from enigma import (irange, subsets, crt, printf)

# look for single digit closed durations
T = 143 * 60  # cycle time (seconds)
ts = list(t for t in irange(1, 9) if T % (4 + t) == 0)
printf("[closed durations = {ts}]")

# consider possible closed durations for the 6 gates (in order)
for ss in subsets(ts, size=6, select='C'):
  printf("[ss = {ss}]")
  # accumulate (residue, modulus) parameters for CRT
  vs = set()
  for (i, t) in enumerate(ss, start=1):
    (n, m) = (40 * i, 4 + t)
    r = (2 - n) % m
    printf("[(t0 + {n}) mod {m} = 2 -> t0 mod {m} = {r}]")
    vs.add((r, m))
  # solve the puzzle using CRT
  t0 = crt(vs).x
  printf("t0 = {t0}")
  printf()
```
    Manually the result is arrived at by solving the following congruences:
    
    (t0 mod 5 = 2)
    (t0 mod 6 = 0)
    t0 mod 10 = 2
    t0 mod 11 = 7
    t0 mod 12 = 6
    t0 mod 13 = 9
    
    So we can start looking for integers that are congruent to 9 mod 13, and then check that the other congruences are met, and we can just check those that are congruent to 2 mod 10, as these must end in 2:
    
    22 → fails mod 12
    152 → fails mod 12
    282 → answer!
    
    LikeLike
Jim Randell 4:55 pm on 27 November 2024 Permalink | Reply
Tags: by: Angela Newing ( 39 )
Teaser 2621: Come dancing
From The Sunday Times, 16th December 2012 [link] [link]

Angie, Bianca, Cindy and Dot were given dance partners and performed in front of four judges, Juno, Kraig, Len and Marcia. Each judge placed the performances in order and gave 4 marks to the best, then 3, 2 and 1 point to the others. The dancers’ marks were then added up and they finished in alphabetical order with no ties. Angie’s winning margin over Bianca was larger than Bianca’s over Cindy, and Bianca’s winning margin over Cindy was larger than Cindy’s over Dot.

Juno’s ordering of the four was different from the final order, and Kraig’s 4 points and Len’s 3 points went to dancers who were not in the top two.

How many points did Cindy get from Juno, Kraig, Len and Marcia respectively?

[teaser2621]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Ruud and Jim Randell are discussing. Toggle Comments
- Jim Randell 4:56 pm on 27 November 2024 Permalink | Reply
  We can use the [[ SubstitutedExpression ]] solver from the enigma.py library to solve this puzzle.
  
  The following run file executes in 90ms. (Internal runtime of the generated program is 10.5ms).
```
#! python3 -m enigma -rr

SubstitutedExpression

#     A B C D
#  J: a b c d
#  K: e f g h
#  L: i j k m
#  M: n p q r

--digits="1-4"
--distinct="abcd,efgh,ijkm,npqr"

# totals for each
--macro="@A = ({a} + {e} + {i} + {n})"
--macro="@B = ({b} + {f} + {j} + {p})"
--macro="@C = ({c} + {g} + {k} + {q})"
--macro="@D = ({d} + {h} + {m} + {r})"

# A's margin over B is larger than B's margin over C
"@A - @B > @B - @C" "@B - @C > 0"
# B's margin over C is larger than C's margin over D
"@B - @C > @C - @D" "@C - @D > 0"

# J's order was different from the final order, so not (4, 3, 2, 1)
"({a}, {b}, {c}, {d}) != (4, 3, 2, 1)"

# K's 4 did not go to A or B
--invalid="4,ef"

# L's 3 did not go to A or B
--invalid="3,ij"

--template="A=({a} {e} {i} {n}) B=({b} {f} {j} {p}) C=({c} {g} {k} {q}) D=({d} {h} {m} {r})"
--solution=""
--verbose="1-H"
```
  Solution: Cindy’s points were: Juno = 1, Kraig = 4, Len = 1, Marcia = 2.
  
  The complete scores are (J + K + L + M):
  
  A: 4 + 3 + 4 + 4 = 15
  B: 3 + 2 + 2 + 3 = 10
  C: 1 + 4 + 1 + 2 = 8
  D: 2 + 1 + 3 + 1 = 7
  
  LikeLike
- Ruud 8:25 am on 28 November 2024 Permalink | Reply
```
import itertools


def order(lst):
    return [lst.index(el) for el in sorted(lst, reverse=True)]


for juno, kraig, len, marcia in itertools.product(itertools.permutations(range(1, 5)), repeat=4):
    totals = [sum(x) for x in zip(juno, kraig, len, marcia)]
    if sorted(totals, reverse=True) == totals:
        if totals[0] - totals[1] > totals[1] - totals[2] > totals[2] - totals[3] > 0:
            if order(juno) != order(totals):
                if kraig.index(4) in (2, 3) and len.index(3) in (2, 3):
                    print(juno[2], kraig[2], len[2], marcia[2])
```
  LikeLike

Jim Randell 7:08 am on 24 November 2024 Permalink | Reply
Tags: by: Peter Good ( 28 ), flawed ( 55 )

Teaser 3244: Borderline case

From The Sunday Times, 24th November 2024 [link] [link]

Jack has a set of 28 standard dominoes: each domino has a spot pattern containing 0 to 6 spots at either end and every combination ([0-0], [0-1] and so on up to [6-6]) is represented in the set. He laid them end-to-end in several strips and arranged each strip so it formed the border of an empty square. Adjacent dominoes in each strip shared the same spot pattern where they were joined and the total number of spots on each strip was the square of the number of dominoes in that strip. More than half of the doublets were in the longest strip and there was a doublet in just one of the two shortest strips. This doublet was the largest possible in a strip of this size.

Which dominoes were in the shortest strip that doesn’t contain a doublet?

I think this puzzle is poorly worded. But I give an interpretation of the text that does give a unique answer to the puzzle in the comments below.

[teaser3244]

Jim Randell 11:25 am on 24 November 2024 Permalink | Reply

Initially I thought that the dominoes were formed into a collection of [straight linear] strips, and then these strips were used (as is) to make the border of a (single) square.

However, after working on the puzzle for some time I was not able to find a solution using this interpretation (or variations thereof).

You can see my thoughts in the chat page [ here ].

However, I think I have now found an alternative interpretation that does lead to a unique answer to the puzzle.

To me the use of the term “strip” implied that a selected set of dominoes were formed into a straight linear arrangement, whereas it seems that they need to be formed into a square loop. So in the following I just used the term “pile”.

The set of 28 dominoes is formed into a collection of piles, such that for each pile:

+ The total sum of the pips is the square of the number of the dominoes in that pile.

+ The dominoes in each pile can be arranged to form a closed loop that is the outline of a square, and where two dominoes meet the pip values on the adjoining ends are the same.

Additional requirements for the collection of piles are:

+ There is a single pile that is identifiably the largest pile, and it contains more than half of the double tiles.

+ There are (exactly) two piles that are identifiably the smallest piles. One of these piles contains a double tile, and this double is the largest possible double that can occur in a pile of that size (constructed subject to the conditions above).

+ The other smallest pile does not have a double in it, and the required answer is a list of dominoes that make up this pile.

I have verified that under this interpretation there is a unique answer to the puzzle, and have posted my code below.

Solution: [see below]

LikeLike
- Rob Bellis 8:48 am on 26 November 2024 Permalink | Reply
  
  hello Jim
  
  Is there any reason why the square cound not be bounded by 2 x 8 tiles and 2 x 6 tiles (to enclose a 6×6 square) ?
  If each side length 6 was constructed of a 2 +4 tile strings then the sum of the squares would = 168 which is the total domino spots .
  
  LikeLike
  - Jim Randell 8:56 am on 26 November 2024 Permalink | Reply
    
    In my initial interpretation of the puzzle I did look at attempting to make the outline of a single 14×14 square from a collection of straight strips, but it was not possible using 26 of the dominoes (for example: [7] + [4, 3] + [4, 2] + [4, 2]).
    
    In the (presumably) intended interpretation, enclosing a 6×6 square would require 14 dominoes, so to form an allowable loop there would have to be 14^2 = 196 pips in the selection. But there are only 168 pips in the entire set of dominoes, so the squares must be smaller than this.
    
    LikeLike
NigelR 5:38 pm on 24 November 2024 Permalink | Reply

A single domino doesn’t seem to satisfy being a border of an empty square. However, the wording would seem to allow a single strip being part of more than one square. Perhaps we are looking for a more complex shape than one or more detached squares?

LikeLike

Jim Randell 11:12 am on 25 November 2024 Permalink | Reply

This Python 3 program solves the interpretation of the puzzle given above in my first comment.

It assumes the two smallest piles are the same size.

It runs in 851ms.

from enigma import (
  defaultdict, irange, inf, first, subsets, sq, express, flatten,
  rev, remove, trim, cproduct, multiset, join, printf
)

# we represent a domino by a tuple (x, y)

# format a collection of dominoes
fmt = lambda ds: join((join(d, sep='-', enc="[]") for d in ds), sep=' ')

# number of pips on a domino
pips = sum

# a complete set of dominoes
ds = set(subsets(irange(0, 6), size=2, select='R'))

# normal form of dominoes
normalise = lambda d: tuple(sorted(d))
normal = lambda *ss: (normalise(d) for d in flatten(ss, fn=iter))

# invalid pips (sorts before all valid pips)
X = -1

# generate loops with <k> dominoes and <t> pips, from dominoes <ds>
# <m> = min starting domino
def loops(k, t, ds, m=(X, X), ss=[]):
  # are we done?
  if k == 0:
    # remove duplicate loops
    if normalise(ss[1]) > normalise(ss[-1]): return
    # check all pips are used, and a loop is formed
    if t == 0 and ss[0][0] == ss[-1][-1]:
      yield (ss, ds)
  elif not (t > 12 * k):
    # choose the next domino
    for d in ds:
      nd = normalise(d)
      if nd < m or (ss and normalise(ss[0]) > nd): continue
      p = pips(d)
      if p > t: continue
      if (not ss) or (d[0] == ss[-1][-1]):
        yield from loops(k - 1, t - p, remove(ds, d, rev(d)), m, ss + [d])

# make a collection of loops with length <ks>, from dominoes <ds>
def piles(ks, ds, rs=[]):
  # are we done?
  if not ks:
    yield (rs, ds)
  else:
    k = ks[0]
    m = (normalise(rs[-1][0]) if rs and k == len(rs[-1]) else (X, X))
    for (ss, ds_) in loops(k, sq(k), ds, m):
      yield from piles(ks[1:], ds_, rs + [ss])

# find the doubles in a set of dominoes
doubles = lambda ds: sorted(x for (x, y) in ds if x == y)

# max or X
max_ = lambda xs: (max(xs) if xs else X)

# total number of pips
tpips = sum(pips(d) for d in ds)
printf("[{n} dominoes, total pips = {tpips}]", n=len(ds))

# piles have an even number of dominoes, minimum 4
ns = first(irange(4, inf, step=2), count=(lambda x: sq(x) < tpips))
printf("[pile sizes = {ns}]")

# initial set of dominoes in either orientation
dss = set(flatten({d, rev(d)} for d in ds))

# collect results
rs = multiset()

# look for possible numbers of piles (at least 3)
for qs in express(tpips, list(sq(n) for n in ns)):
  if sum(qs) < 3: continue
  # form the pile sizes (in order)
  ks = flatten([n] * q for (n, q) in zip(ns, qs) if q > 0)
  # use all the dominoes
  if sum(ks) != 28: continue
  # there should be 2 identifiable smallest piles, and 1 identifiable largest pile
  if not (ks[0] == ks[1] < ks[2] and ks[-2] < ks[-1]): continue
  # the largest pile has 4 doubles -> a loop of at least 8 dominoes
  if ks[-1] < 8: continue
  printf("[checking {ks} = {n} dominoes]", n=sum(ks))

  # start with the smallest piles (size k)
  (k, gs) = (ks[0], defaultdict(list))
  for (ss, _) in loops(k, sq(k), dss):
    gs[max_(doubles(ss))].append(ss)
  # max possible double in a smallest pile
  m = max(gs.keys())
  assert m != X

  # choose the two smallest piles
  for (ss1, ss2) in cproduct([gs[X], gs[m]]):
    # which must contain distinct dominoes
    xs = set(normal(ss1, ss2))
    if len(xs) < 2 * k: continue

    # choose the largest pile (size K)
    (K, dss_) = (ks[-1], dss.difference(xs, (rev(x) for x in xs)))
    for (ssz, dsz) in loops(K, sq(K), dss_):
      # which must have at least 4 doubles
      if len(doubles(ssz)) < 4: continue

      # fill out the remaining piles
      for (ps, _) in piles(trim(ks, head=2, tail=1), dsz):
        ans = tuple(sorted(normal(ss1)))
        # display the collection of piles
        printf("ss1 = {ss1} -> answer", ss1=fmt(ss1))
        printf("ss2 = {ss2}", ss2=fmt(ss2))
        for (i, ss) in enumerate(ps, start=3):
          printf("ss{i} = {ss}", ss=fmt(ss))
        printf("ss{z} = {ssz}", z=len(ps) + 3, ssz=fmt(ssz))
        printf()
        rs.add(ans)

# output solutions
for (ss, n) in rs.most_common():
  printf("dominoes = {ss} [{n} solutions]", ss=fmt(ss))

Solution: The required dominoes are: [0-1] [0-5] [1-2] [2-5].

Here are the 28 dominoes split into 5 piles, and each pile laid out as a square loop:

[1-0] [0-5] [5-2] [2-1]
[2-0] [0-3] [3-3] [3-2]
[0-0] [0-4] [4-3] [3-5] [5-6] [6-0]
[3-1] [1-4] [4-2] [2-2] [2-6] [6-3]
[1-1] [1-5] [5-5] [5-4] [4-4] [4-6] [6-6] [6-1]

The dominoes that make up the answer to the puzzle are those in the first (top-left) square, which has 4 dominoes and 16 pips in total.

The second (top-right) square uses the double [3-3], which is the largest possible double for a loop with 4 dominoes. It also has 16 pips in total.

Each of the middle squares consists of 6 dominoes, and has 36 pips in total.

The bottom square consists of 8 dominoes, uses 4 doubles ([1-1] [5-5] [4-4] [6-6]), and has 64 pips in total.

There is a further layout that also provides a solution:

[1-0] [0-5] [5-2] [2-1]
[2-0] [0-3] [3-3] [3-2]
[0-0] [0-4] [4-5] [5-3] [3-6] [6-0]
[3-1] [1-6] [6-2] [2-2] [2-4] [4-3]
[1-1] [1-4] [4-4] [4-6] [6-6] [6-5] [5-5] [5-1]

The first two loops are the same as the layout above.

And of course any loop in a solution can be reflected or rotated.

LikeLike

Brian Gladman 2:56 pm on 29 November 2024 Permalink | Reply

@Jim. Your optimisation in this code very is impressive. I have a structurally similar solution but it is painfully slow because it finds the same loops many thousands of times and I have not found a technique for preventing this. I can see that you have managed to do this but I am wondering what principle you have based this on?

LikeLike
- Jim Randell 3:08 pm on 29 November 2024 Permalink | Reply
  
  @Brian: Yes, this was a tricky one to program (even after determining the intended interpretation of the text).
  
  I used several “normal forms” to eliminate duplicate solutions:
  
  + for a domino (x, y) the normal form is when x ≤ y. (Otherwise we might also consider (y, x)).
  
  + for a loop, the normal form is to start with smallest domino (as above), and travel round the loop such that the second domino is less than the final domino. (There are at least 4 dominos in a loop, so these are all different). (Otherwise we could start at any domino, and go round the loop in either direction).
  
  + for a collection of loops of the same size, I require that they are ordered by the first domino. (Otherwise we might find the same loops in a different order).
  
  Together these bring the number of solutions down to two different collections of dominoes.
  
  LikeLiked by 1 person
  - Brian Gladman 5:15 pm on 29 November 2024 Permalink | Reply
    
    Thanks Jim, It looks like eliminating duplicate solutions is as much, if not more work, than finding solutions in the first place!
    
    LikeLike
Frits 11:53 am on 12 December 2024 Permalink | Reply
@Jim,

If you are only interested in the answer then you might split the cproduct for ss1 and ss2 to two separate loops and do some else/continue/break constructs. This will bring down the run time by a factor 3.

Also using a simpler normalise() is faster.
```
normalise = lambda d: d if d[0] <= d[1] else (d[1], d[0])
```
LikeLike

Frits 10:59 am on 12 December 2024 Permalink | Reply

This program runs in 35ms (not as fast as Brian’s recursive program).
A lot of work again.

from enigma import SubstitutedExpression

mx_dom = 6

# sorted tuple
stup = lambda s: tuple(sorted(s))
# generate circular pairs
circular = lambda s: set(stup([x, y]) for x, y in zip(s, s[1:] + s[:1]))

# including (x, y) and (y, x)
allcombs = lambda s: s | set((y, x) for x, y in s)
tri = lambda n: n * (n + 1) // 2

# decompose <t> into at least <mn> non-decreasing square piles
def decompose(t, mn=4, ns=[], fn=lambda x: x * x, ss = ()):
  unpack = lambda f: (lambda x: f(*x))
  if t == 0 and len(ss) >= mn:
    # also require that the two smallest values in <ss> are
    # equal and that there is only one largest value
    if ss[0] == ss[1] and ss[-1] > ss[-2]:
      yield ss
  else:
    for i, s in enumerate(ns):
      if t >= fn(s):
        yield from decompose(t - fn(s), mn, ns[i:], fn, ss + (s, ))

# run the SubstitutedExpression with specific expressions
def run(exprs, answer, d2i, syms, s2d=dict(), reorder=0, verbose=0):
  # eg for strip 'a-b-c-d-e-f-g-h-i-j' a must be different from c and i
  distinct = set(x + y if x < y else y + x for x, y in zip(syms, syms[2:] + syms[:2]))

  p = SubstitutedExpression(
      exprs,
      symbols=syms,
      answer=answer,
      d2i=d2i,
      distinct=distinct,
      env=dict(stup=stup, allcombs=allcombs),
      base=mx_dom + 1,
      s2d=s2d,
      digits=(range(mx_dom + 1)),
      reorder=reorder,
      verbose=verbose,  # use 256 to see the generated code
    )
  return tuple(p.answers())

# solve remaining strips after 3 strips are known
def solve(k, strips, pairs, ss=tuple()):
  if k == 0:
    yield ss
  else:
    s_size = strips[0]
    syms = allsyms[:s_size]
    vars = ','.join(syms)
    varlist = "[" + vars + "]"
    pairs4 = f"list(zip({varlist}, [{vars[2:]},{syms[0]}]))"
    s2d = dict()

    exprs = []

    # check if remaining strips all have the same size
    if len(set(strips)) == 1:
      # let strip begin with lowest remaining domino
      low = next(x for x in dominoes if x not in pairs)
      s2d[syms[0]], s2d[syms[1]] = low[0], low[1]
      first_domino_set = 1
    else:
      first_domino_set = 0
      # start with lowest number
      for i in range(1, s_size - 1):
        exprs.append(f"{syms[0]} <= {syms[i]}")

    # try to speed up the process
    #for i in range(2, 3):
    #  exprs.append(f"({syms[i - 1]}, {syms[i]}) not in {pairs}")

    # calculate last variable: sum(syms) * 2 = s_size^2
    exprs.append(f"{s_size**2 // 2} - sum([{vars[:-2]}]) = {syms[-1]}")

    if not first_domino_set:
      exprs.append(f"{syms[0]} <= {syms[-1]}")
    # ABCD <= ADCB
    exprs.append(f"{syms[1]} <= {syms[-1]}")

    # use different dominoes than already used
    exprs.append(f"allcombs(set(p4 := {pairs4})).isdisjoint({pairs})")

    # all dominoes must be unique
    exprs.append(f"len(set([stup([x, y]) for x, y in p4])) == {s_size}")

    # avoid rotations if list starts with a doublet
    exprs.append(f"{syms[0]} != {syms[1]} or "
                 f"{varlist} <= [{syms[1]},{syms[0]},{','.join(syms[2:][::-1])}]")

    answer = "tuple(" + varlist + ")"

    # limit variable values
    if first_domino_set:
      # other values in <syms> may not be smaller than first value
      # and for strip 'a-b-c-d-e-f-g-h-i-j' a must be different from c and i
      d2i = dict([(k, vars[2:]) for k in range(s2d[syms[0]])] +
                 [(s2d[syms[0]], syms[2] + syms[-2])])
      d2i[s2d[syms[1]]] = d2i.get(s2d[syms[1]], "") + syms[3] + syms[-1]
    else:
      # calculate highest possible starting domino
      ln = len(dominoes)
      mx = next(i for i in range(6, -1, -1)
                if ln - dominoes.index((i, i)) >= s_size)
      d2i = dict([(k, vars[0]) for k in range(mx + 1, mx_dom + 1)])

    # solve one strip
    for r in run(exprs, answer, d2i, syms, s2d, reorder=0, verbose=0):
      yield from solve(k - 1, strips[1:], pairs | circular(r), ss + (r, ))

allsyms = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

# the 28 dominoes
dominoes = tuple((i, j) for i in range(mx_dom + 1) for j in range(i, mx_dom + 1))
# the total number of spots
n_spots = sum(a + b for a, b in dominoes)
rt_spots = int(n_spots**.5)

mn_pile = 4 # at least 4 sides
# sum of spots of <n> largest dominoes must be >= n^2
mx_pile = next(i for i in range(rt_spots - rt_spots % 2 , 2, -2)
               if i * i <= sum(a + b for a, b in dominoes[-i:]))
sols = set()

# generate valid piles of strips
for pile in decompose(n_spots, mn_pile, range(mn_pile, mx_pile + 1, 2)):
  # ----------------------
  # get shortest strips
  # ----------------------
  min_strip = pile[0]
  syms = allsyms[:min_strip]
  vars = ','.join(syms)
  varlist = "[" + vars + "]"
  exprs = []
  pairs1 = f"[stup([x, y]) for x, y in zip({varlist}, [{vars[2:]},{syms[0]}])]"
  for i in range(1, min_strip - 1):
    exprs.append(f"{syms[0]} <= {syms[i]}")

  # calculate last variable: sum(syms) * 2 = min_strip^2
  exprs.append(f"{min_strip**2 // 2} - sum([{vars[:-2]}]) = {syms[-1]}")

  exprs.append(f"{syms[0]} <= {syms[-1]}")
  exprs.append(f"{syms[1]} <= {syms[-1]}")  # ABCD <= ADCB
  # strip should have 0 or 1 doublets
  exprs.append(f"len({{{vars}}}) >= {min_strip - 1}")

  # all dominoes must be unique
  exprs.append(f"len(set({pairs1})) = {min_strip}")

  answr = f"next((x for x, y in {pairs1} if x == y), -1), "
  answr += "tuple(" + varlist + ")"
  # calculate highest possible starting domino
  ln = len(dominoes)
  mx = next(i for i in range(6, -1, -1)
            if ln - dominoes.index((i, i)) >= min_strip)
  d2i = dict([(k, vars[0]) for k in range(mx + 1, 10)])
  # reverse sort on doublet
  answs = sorted(run(exprs, answr, d2i, syms, s2d=dict(),
                     reorder=0, verbose=0), reverse=True)

  mx_doublet = answs[0][0]
  # find strips with 1 doublet
  for ans1 in answs:
    if ans1[0] != mx_doublet or ans1[0] == -1: break
    pairs1 = circular(ans1[1])

    # find strips without a doublet
    for ans2 in answs:
      if ans2[0] != -1: continue
      # first 2 strips have to use different dominoes
      if len(pairs12 := pairs1 | circular(ans2[1])) != 2 * min_strip: continue

      # store potential answer
      sol = tuple((x, y) for x, y in zip(ans2[1], ans2[1][1:] + (ans2[1][0], )))
      if sol in sols: continue

      # get all possible pairs of both strips
      pairs12all = allcombs(pairs12)

      # ---------------------------------
      # find longest strip
      # ---------------------------------
      max_strip = pile[-1]
      syms = allsyms[:max_strip]
      mn_doublets = mx_dom // 2 + 1   # minimum number of doublets required

      exprs = []

      # all dominoes are doublets?
      if (all_doublets := (max_strip == 2 * mn_doublets)):
        # create <vars> like A,A,C,C,E,E,G,G
        vars = ','.join(x + "," + x for x in allsyms[:max_strip][::2])
        varlist = "[" + vars + "]"
        pairs3 = f"list(zip({varlist}, [{vars[2:]},{syms[0]}]))"
        for i in range(2, max_strip - 2, 2):
          exprs.append(f"{syms[0]} < {syms[i]}")

        # calculate last variable: sum(syms) * 2 = max_strip^2
        exprs.append(f"div({max_strip**2 // 2} - sum([{vars[:-4]}]), 2) = {syms[-2]}")
        exprs.append(f"{syms[0]} < {syms[-2]}")
      else:
        vars = ','.join(syms)
        varlist = "[" + vars + "]"
        pairs3 = f"list(zip({varlist}, [{vars[2:]},{syms[0]}]))"
        # start strip with the smallest doublet
        exprs.append(f"{syms[0]} = {syms[1]}")
        for i in range(2, max_strip - 1):
          exprs.append(f"{syms[i - 1]} != {syms[i]} or {syms[0]} < {syms[i]}")
          exprs.append(f"({syms[i - 1]}, {syms[i]}) not in {pairs12all}")

        # calculate last variable: sum(syms) * 2 = max_strip^2
        exprs.append(f"{max_strip**2 // 2} - sum([{vars[:-2]}]) = {syms[-1]}")
        exprs.append(f"{syms[0]} <= {syms[-1]}")
        exprs.append(f"{syms[1]} <= {syms[-1]}")    # ABCD <= ADCB
        exprs.append(f"({syms[-1]}, {syms[0]}) not in {pairs12all}")
        # more than half doublets
        exprs.append(f"len({{{vars}}}) <= {pile[-1] - mn_doublets}")

      # use different pairs
      exprs.append(f"allcombs(set(p3 := {pairs3})).isdisjoint({pairs12all})")
      # all dominoes must be unique
      exprs.append(f"len(set([stup([x, y]) for x, y in p3])) == {max_strip}")

      # avoid rotations if strip starts with a doublet
      if all_doublets:
        exprs.append(f"{varlist} <= [{vars[:3]},{vars[4:][::-1]}]")
      else:
        exprs.append(f"{syms[0]} != {syms[1]} or "
                     f"{varlist} <= [{syms[1]},{syms[0]},{','.join(syms[2:][::-1])}]")

      # eg. the four doublets (3, 3)...(6, 6) have too many spots
      max_smallest_doublet = next(i for i in range(max_strip - mn_doublets, -1, -1)
                                  if 4 * (i * mn_doublets + tri(mn_doublets - 1))
                                  <= max_strip**2)

      # limit first domino
      d2i = dict([(k, vars[0]) for k in range(max_smallest_doublet + 1, 10)])
      if all_doublets:
        # if (0, 0) is present then it has to be the first doublet
        d2i[0] = syms[::2][1:]
        d2i[ans1[0]] = syms # exclude the doublet used in shortest strip
      answr = f"tuple(" + varlist + ")"

      for ans3 in run(exprs, answr, d2i, syms, s2d=dict(), reorder=0, verbose=0):
        pairs123all = allcombs(pairs12 | circular(ans3))
        # solve remaining strips
        for s in solve(len(pile) - 3, pile[2:-1], pairs123all):
          sols.add(sol)
          break # as <sol> only depends on 2nd strip
        else: # no break
          continue
        break

for s in sols:
  print("answer:", s)

LikeLike

Jim Randell 8:40 am on 22 November 2024 Permalink | Reply
Tags: by: Graham Smithers ( 84 )
Teaser 2605: Simple sums
From The Sunday Times, 26th August 2012 [link] [link]

I have taken some numbers and consistently replaced the digits by letters, with different letters for different digits.

In this way:

TWO + TWO = FOUR;
FIVE is prime;
FIVE − TWO is prime;
THREE is divisible by 3.

Quelle est la valeur de HUIT?

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

SubstitutedExpression

"TWO + TWO = FOUR"
"is_prime(FIVE)"
"is_prime(FIVE - TWO)"
"THREE % 3 = 0"

--answer="HUIT"
```
  Solution: HUIT = 4539.
  
  We have:
  
  TWO = 928
  THREE = 94677
  FOUR = 1856
  FIVE = 1307
  
  LikeLike
  - Frits 4:28 am on 23 November 2024 Permalink | Reply
    
    @Jim, your first run members had option -r on line 1 but the newer ones have option -rr.
    Can you explain the difference as I have problems finding it in enigma.py.
    
    LikeLike
    - Jim Randell 10:09 am on 23 November 2024 Permalink | Reply
      
      The -r option is short for the --run option, which also allows you to specify the type of the file to run.
      
      The following additional arguments are accepted by the --run option:
      
      --run:type=.run (or -rr)
      --run:type=.py (or -rp)
      --run:timed (or -rt)
      --run:verbose (or -rv)
      
      If the type is not specified then it is set from the file extension. But specifying the type as an argument allows the code to run correctly, even if it is saved to a file that does not have a .run extension.
      
      LikeLike
- Ruud 8:06 am on 23 November 2024 Permalink | Reply
  Very brute force
```
import istr

for t, w, o, f, u, r, e, h, v, i in istr.permutations(range(10), 10):
    if (
        (t | w | o) + (t | w | o) == (f | o | u | r)
        and (f | i | v | e).is_prime()
        and ((f | i | v | e) - (t | w | o)).is_prime()
        and (t | h | r | e | e).is_divisible_by(3)
        and t * f * h
    ):
        print(f"two={t|w|o} four={f|o|u|r} five={f|i|v|e} three={t|h|r|e|e} huit={h|u|i|t}")
```
  LikeLike
  - Frits 12:49 pm on 23 November 2024 Permalink | Reply
    
    @Ruud, I thought you had forgotten about the non-zero first characters but it is there at line 9.
    
    The istr concatenation character might become aesthetically problematic when there is a letter L. In that case would you use upper case variables?
    
    LikeLike
    - Ruud 4:21 pm on 23 November 2024 Permalink | Reply
      
      In contrast to most contributors here, I try and follow PEP8 conventions, which implies lowercase variables.
      
      LikeLike
Jim Randell 11:16 am on 19 November 2024 Permalink | Reply
Tags: by: Nick MacKinnon ( 56 )
Teaser 2613: Anagrammatical
From The Sunday Times, 21st October 2012 [link] [link]

The number 258 is special in the following way. If you write down its six different anagrams (258, 285, 528, etc.), then calculate the fifteen differences between any two of those six (27, 270, 243, etc.) and then add up those fifteen differences, you get 4644, which is a multiple of the number 258 that you started with!

Which higher three-figure number has the same property?

[teaser2613]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Frits, GeoffR, Ruud, and 1 other are discussing. Toggle Comments
- Jim Randell 11:17 am on 19 November 2024 Permalink | Reply
  Here is a constructive solution.
  
  It runs in 57ms. (Internal runtime is 3.1ms).
```
from enigma import (irange, nsplit, subsets, nconcat, printf)

# check a 3 digit number
def check(n):
  # find different rearrangements of the digits
  rs = sorted(subsets(nsplit(n), size=len, select='mP', fn=nconcat))
  if len(rs) < 2: return False
  # calculate the total sum of the pairwise differences
  t = sum(y - x for (x, y) in subsets(rs, size=2))
  if t % n != 0: return False
  printf("{n} -> {t}")
  return True

# check the given value
assert check(258)

# find the next 3-digit number after 258 that works
for n in irange(259, 999):
  if check(n): break
```
  Solution: The next 3-digit number with the same property is 387.
  
  And there are no higher 3-digit numbers with the property, but there are lower ones.
  
  The complete list of 3-digit numbers (and the sum of the differences) with this property is:
  
  129 → 6192
  172 → 4644
  258 → 4644
  387 → 3870
  
  LikeLike
  - Frits 5:03 pm on 21 November 2024 Permalink | Reply
    
    The differences between any two of these four 3-digit numbers are multiples of 43.
    
    See [https://brg.me.uk/?page_id=300].
    
    LikeLike
- Ruud 7:18 pm on 19 November 2024 Permalink | Reply
  This code finds all three digit numbers that meet the conditions given:
```
import istr

for i in istr.range(100, 1000):
    if i.all_distinct() and sum(abs(x - y) for x, y in istr.combinations(istr.concat(istr.permutations(i)), 2)).is_divisible_by(i):
        print(i)
```
  LikeLike
- GeoffR 2:56 pm on 21 November 2024 Permalink | Reply
```
from enigma import nsplit

for n in range(258, 999):
    diff = 0
    a, b, c = nsplit(n)
    if 0 in (a, b, c):
        continue
    # Form the six numbers
    n1, n2 = 100*a + 10*b + c, 100*a + 10*c + b
    n3, n4 = 100*b + 10*a + c, 100*b + 10*c + a
    n5, n6 = 100*c + 10*a + b, 100*c + 10*b + a
    if not len(set((n1, n2, n3, n4, n5, n6))) == 6:
        continue
    # Find sum of fifteen differences
    diff = abs(n1-n2) + abs(n1-n3) + abs(n1-n4) + abs(n1-n5) + abs(n1-n6)\
            + abs(n2-n3) + abs(n2-n4) + abs(n2-n5) + abs(n2-n6)\
            + abs(n3-n4) + abs(n3-n5) + abs(n3-n6)\
            + abs(n4-n5) + abs(n4-n6)\
            + abs(n5-n6)
    #  Sum of fifteen differences is a multiple of the number 
    if diff % n == 0:
        print(f"Number = {n}, Differences sum = {diff}")

# Number = 258, Differences sum = 4644
# Number = 387, Differences sum = 3870
```
  Interesting that the differences sum is ten times the number.
  
  LikeLike

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

Teaser 3243: A break from tradition

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

Occasionally we used to play a very non-traditional variation of snooker. We tried to “pot” into the pockets five differently-coloured balls, which had points values of 7, 8, 9, 10, 13 in some order.

Our rules were that a red could only be followed by a blue or pink; a yellow by a red or green; a green by a yellow; a blue by a green; and a pink by a red or yellow. After a player had successfully potted a ball it was immediately returned to the table, and their turn continued, and this constituted a “break”.

One evening I scored breaks that totalled 33, 55, 24 and 57 points (none with more than five pots).

What were the values of red, yellow, green, blue and pink, in that order?

[teaser3243]

Jim Randell 7:05 am on 17 November 2024 Permalink | Reply

This Python 3 program collects possible allowable sequences of up to 5 balls, and then looks for assignments of colour values that allow all the given scores to be made.

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

from enigma import (flatten, subsets, map2str, printf)

# allowed transitions
adj = dict(R="BP", Y="RG", G="Y", B="G", P="RY")

# generate break with up to <k> more balls
def solve(k, bs):
  yield bs
  if k > 0:
    for x in adj[bs[-1]]:
      yield from solve(k - 1, bs + x)

# collect possible breaks with up to 5 balls
seqs = flatten(solve(4, k) for k in adj.keys())

# consider possible ball values
for vs in subsets([7, 8, 9, 10, 13], size=len, select='P'):
  v = dict(zip("RYGBP", vs))
  # score each of the possible sequences
  scores = set(sum(v[x] for x in bs) for bs in seqs)
  if scores.issuperset({33, 55, 24, 57}):
    # output solution
    printf("{v}", v=map2str(v, enc="", sort=0))

Solution: The values of the balls are: red = 9, yellow = 10, green = 8, blue = 7, pink = 13.

The given breaks are:

24 = RBG
33 = BGYG
55 = PYRPY
57 = PRPRP

LikeLike

ruudvanderham 3:22 pm on 17 November 2024 Permalink | Reply

import itertools

next_ball = dict(r="bp", y="rg", g="y", b="g", p="ry")

targets = (33, 55, 24, 57)


def shoot(balls, target, value):
    score = sum(value[ball] for ball in balls)
    if score <= target and len(balls) <= 5:
        if score == target:
            yield balls
        for try_ball in next_ball[balls[-1]] if balls else next_ball.keys():
            yield from shoot(balls=balls + try_ball, target=target, value=value)


for permutation in itertools.permutations((7, 8, 9, 10, 13)):
    ball_value = dict(zip(next_ball.keys(), permutation))
    if all(any(shoot(balls="", target=target, value=ball_value)) for target in targets):
        print(" ".join(f"{ball}:{value}" for ball, value in ball_value.items()))
        for target in targets:
            print(f'  {target} by playing {" or ".join(shoot(balls="",target=target,value=ball_value))}')

LikeLike

Frits 3:44 pm on 17 November 2024 Permalink | Reply

A lot of work for doing it a bit differently.

from enigma import SubstitutedExpression

# dictionary of possible next colours
d = {"b": "g", "g": "y", "p":"ry", "r": "bp", "y": "rg"}
balls = sorted(d.keys())

points = [7, 8, 9, 10, 13]
scores = [33, 55, 24, 57]

# collect all possible breaks
def solve(k, ss):
  yield ss
  if not k: return
  for x in d[ss[-1]]:
    yield from solve(k - 1, ss + x)       

breaks = set(''.join(sorted(x for x in s)) for k in d.keys() 
             for s in solve(4, k))

# colours that may occur three times in a break
balls3 = {k for k in balls if any(k in d[k1] for k1 in d[k])}
 
# invalid digit / symbol assignments
d2i = dict()
for dgt in range(0, 10):
  vs = set() 
  if dgt in {1, 2, 4, 5, 6}: vs.update('SCHQZ')
  if dgt > 1: vs.update('RBGPY')
  if dgt > 3: vs.update('ADFIJKLMNOTUVWXjqxyz')
  if dgt == 3:
    for i, k in enumerate(d.keys()):
      if k in balls3: continue
      # colours that may not occur three times in a break
      vs.update(['ADFIJKLMNOTUVWXjqxyz'[5 * j + i] for j in range(4)])
  d2i[dgt] = vs   

# check if a colour combination is allowed  
def check(*s):
  # sorted used balls
  used = ''.join(balls[i] * x for i, x in enumerate(s) if x)
  return used in breaks
   
# the alphametic puzzle
p = SubstitutedExpression(
  [ # colors: b = BC, g = GH, p = PQ, r = RS, y = YZ
    "BC in {7, 8, 9, 10, 13}",
    "H != C",
    "GH in {7, 8, 9, 10, 13}",
    "Q not in {C, H}",
    "PQ in {7, 8, 9, 10, 13}",
    "S not in {C, H, Q}",
    "RS in {7, 8, 9, 10, 13}",
    
    "{7, 8, 9, 10, 13}.difference([BC, GH, PQ, RS]).pop() = YZ",
    
    #"A * BC + D * GH + F * PQ + I * RS + J * YZ == 57",
    "div(57 - (A * BC + D * GH + F * PQ + I * RS), YZ) = J",
    "A + D + F + I + J < 6",
    "check(A, D, F, I, J)", 
    
    #"T * BC + U * GH + V * PQ + W * RS + X * YZ == 55",
    "div(55 - (T * BC + U * GH + V * PQ + W * RS), YZ) = X",
    "T + U + V + W + X < 6",
    "check(T, U, V, W, X)", 
    
    #"K * BC + L * GH + M * PQ + N * RS + O * YZ == 24",
    "div(24 - (K * BC + L * GH + M * PQ + N * RS), YZ) = O",
    "K + L + M + N + O < 6",
    "check(K, L, M, N, O)", 
    
    #"j * BC + q * GH + x * PQ + y * RS + z * YZ == 33",
    "div(33 - (j * BC + q * GH + x * PQ + y * RS), YZ) = z",
    "j + q + x + y + z < 6",
    "check(j, q, x, y, z)", 
  ] 
  ,
  answer="(RS, YZ, GH, BC, PQ)",
  symbols="ABCDEFGHIJKLMNOPQRSTUVWXYZjqxyz",
  d2i=d2i,
  distinct="",
  env=dict(check=check),
  denest=64,
  reorder=0,
  verbose=0,    # use 256 to see the generated code
) 

# print answers
for ans in p.answers():
  print(f"answer: {ans}")

LikeLike

Ruud 5:17 pm on 17 November 2024 Permalink | Reply

Certainly a lot of work …

LikeLike

Jim Randell 8:43 am on 14 November 2024 Permalink | Reply
Tags: by: C Higgins ( 37 ), by: H Bradley ( 37 )
Teaser 2545: Emblematic
From The Sunday Times, 3rd July 2011 [link] [link]

Pat’s latest art installation consists of a large triangle with a red border and, within it, a triangle with a green border. To construct the green triangle, he drew three lines from the vertices of the red triangle to points one third of the way (clockwise) along their respective opposite red sides. Parts of these lines formed the sides of the green triangle. In square centimetres, the area of the red triangle is a three-digit number and the area of the green triangle is the product of those three digits.

What is the area of the red triangle?

[teaser2545]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 8:46 am on 14 November 2024 Permalink | Reply
  See also: Teaser 3233, Teaser 2865, Enigma 1076, Enigma 320, Enigma 1313.
  
  This is another puzzle that can be solved using Routh’s Theorem [@wikipedia], which I have made notes on here [ rouths-theorem.pdf ].
  
  This Python program runs in 70ms. (Internal runtime is 3.5ms).
```
from enigma import (irange, inf, rdiv, multiply, nsplit, printf)

# ratio XYZ/ABC in Routh's theorem
def routh(x, y, z):
  a = x * y * z - 1
  b = (x * y + y + 1) * (y * z + z + 1) * (z * x + x + 1)
  return rdiv(a * a, b)

# compute the ratio r = green / red
r = routh(2, 2, 2)

# consider possible areas for the smaller (green) triangle
for G in irange(1, inf):
  # calculate the area of the larger (red) triangle
  R = rdiv(G, r)
  # R is a 3-digit number
  if R > 999: break
  if R < 100 or R % 1 > 0: continue
  # the product of R's digits is G
  if not (multiply(nsplit(R)) == G): continue

  # output solution
  printf("G={G} R={R} [r={r}]")
```
  Solution: The area of the red triangle is: 735 cm².
  
  And the area of the green triangle is: 105 cm².
  
  7 × 3 × 5 = 105
  
  From Routh’s Theorem we determine that area of the green triangle is 1/7 that of the red triangle.
  
  So we are looking for a 3-digit number ABC such that:
  
  A × B × C = ABC / 7
  
  The following run file executes in 73ms. (Internal runtime of the generated program is 144µs).
```
#! python3 -m enigma -rr

SubstitutedExpression

"7 * A * B * C = ABC"

--answer="ABC"
```
  LikeLike
Jim Randell 9:03 am on 12 November 2024 Permalink | Reply
Tags: by: Victor Bryant ( 144 )
Teaser 2543: Hit and miss
From The Sunday Times, 19th June 2011 [link] [link]

For calculations using arithmetic in a base higher than 10 I need symbols for the higher “digits”. My digits are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A (= 10), B (= 11), C (= 12), etc., using as many letters as necessary. But some numbers are ambiguous, e.g. in HIT and in MISS it is unclear whether the second digit is the number 1 or the letter I. So there are four interpretations of HIT + MISS. I’ve taken one of those four interpretations and worked out its remainder when dividing by four. If you knew the remainder you could work out which base I am using.

What is that base?

[teaser2543]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell, GeoffR, and ruudvanderham are discussing. Toggle Comments
- Jim Randell 9:03 am on 12 November 2024 Permalink | Reply
  There is a T (= 29), so the the minimum possible base is 30, and I am assuming that the maximum base is 36 (as Z = 35). (And if we consider bases larger than 36 then the puzzle has no solutions).
  
  The following Python program runs in 67ms. (Internal runtime is 199µs).
```
from enigma import (defaultdict, irange, cproduct, base2int, join, printf)

# consider possible interpretations of the sum
for terms in cproduct([["HIT", "H1T"], ["MISS", "M1SS"]]):

  # consider possible bases, and collect candidate bases by residue mod 4
  d = defaultdict(list)
  for b in irange(30, 36):
    ns = list(base2int(t, base=b) for t in terms)
    r = sum(ns) % 4
    d[r].append(b)

  # look for residues that give a unique base
  for (r, bs) in d.items():
    if len(bs) == 1:
      printf("r={r} -> base={b} [sum={terms}]", b=bs[0], terms=join(terms, sep='+'))
```
  Solution: The base is 33.
  
  The values to be summed are: H1T (= 18575) and M1SS (= 792655), i.e. both with a digit 1 (one), rather than I (capital i).
  
  The total is 811230, which has a residue of 2 (mod 4), and 33 is the only base that gives a residue of 2.
  
  Manually:
  
  We note that increasing the base by 4 will not change the residue modulo 4 of the sum.
  
  So the following pairs of bases will always give the same mod 4 residue: (30, 34), (31, 35), (32, 36).
  
  This leaves 33 as the only base for which it is possible for the residue to be unique, and this solves the puzzle. (And it also explains why the puzzle has no solutions if base 37 is included).
  
  LikeLike
- ruudvanderham 12:31 pm on 12 November 2024 Permalink | Reply
  Like Jim’s solution:
```
import istr

remainders = {i: [] for i in range(4)}
for base in range(30, 37):
    istr.base(base)
    for s in istr("HIT MISS", "H1T MISS", "HIT M1SS", "H1T M1SS"):
        s1, s2 = s.split()
        remainders[int(s1 + s2) % 4].append((base, s1, s2))
for i in range(4):
    if len(remainders[i]) == 1:
        print(remainders[i])
```
  LikeLike
- GeoffR 8:56 pm on 12 November 2024 Permalink | Reply
```
# Given letter values
H, I, M, S, T = 17, 18, 22, 28, 29

i = 1

from collections import defaultdict
rem = defaultdict(list)

# Four possible values of (HIS + MISS)
for base in range(30, 37):
    # letter I + letter I
    MISS = M*base**3 + I*base**2 + S*base + S
    HIT = H*base*base + I*base + T
    r = (HIT + MISS) % 4
    rem [r] += [base, HIT, MISS]
    
    # Letter I + digit 1
    MISS = M*base**3 + I*base**2 + S*base + S
    HiT = H*base*base + i*base + T
    r = (HiT + MISS) % 4
    rem [r] += [base, HiT, MISS]
    
    # digit 1 + letter I
    MiSS = M*base**3 + i*base**2 + S*base + S
    HIT = H*base*base + I*base + T
    r = (HIT + MiSS) % 4
    rem [r] += [base, HIT, MiSS]
    
    # digit  1 + digit 1
    M1SS = M*base**3 + 1*base**2 + S*base + S
    H1T = H*base*base + 1*base + T
    r = (H1T + M1SS) % 4
    rem [r] += [base, H1T, M1SS]

for k,v in rem.items():
    if len(v) == 3:
        print(k, v)
        print("base = ", v[0])


# 2 [33, 792655, 18575]
# base =  33
```
  LikeLike
- Jim Randell 5:44 pm on 13 November 2024 Permalink | Reply
  
  @ruud & @geoff:
  
  I don’t think it is correct to collect all the values for the different possible sums together in the same dictionary.
  
  The setter is using one of the possible sums and the residue uniquely identifies the base for that sum. But there is nothing to say that the residue is unique across all the sums (although in this case it is). But if one of the other sums had the same residue it would mean your code would not identify the solution.
  
  For example, if we used bases 31 – 37 in the puzzle (instead of 30 – 36) the solution would be that the base was 34. (The terms are still H1T and M1SS, but the residue is 3).
  
  LikeLike

Jim Randell 1:36 am on 10 November 2024 Permalink | Reply
Tags: by: Phil Jackson ( 2 )

Teaser 3242: Tynemouth Boating Lake

From The Sunday Times, 10th November 2024 [link] [link]

When Tynemouth Boating Lake was being constructed, the builder hammered in stakes at two points in the ground, tied the ends of a rope to the stakes, and with a stick keeping the rope taut, marked out an ellipse as shown (not to scale). He was surprised to find that at some points on the circumference, the rope formed two different right-angled triangles, both with sides a whole number of feet long. The free length of the rope was 289 feet.

In increasing order, what were the five lengths of the sides of the two triangles?

See: [ Google Maps ].

[teaser3242]

Jim Randell 2:00 am on 10 November 2024 Permalink | Reply
The rope is attached to the posts, so two sides of each triangle are formed by the rope, and the remaining side is formed from the straight line between the two posts (the dashed line in the diagram). An alternative method of construction would be to form the rope into a loop which is placed over the posts, and then pulled tight to form a triangle where all three sides are formed by the rope, but this will construct a smaller ellipse).

Initially I thought some of the 289 ft of rope would be used to attach it to the posts, but I think the amount of (inextensible) rope between the posts needs to be exactly 289 ft after it has been attached in order for the puzzle to have a unique solution.

This Python program runs in 69ms. (Internal runtime is 209µs).
```
from enigma import (defaultdict, pythagorean_triples, subsets, printf)

# collect pythagorean triples by perimeter
d = defaultdict(list)
for ss in pythagorean_triples(289):
  p = sum(ss)
  if any(p - s == 289 for s in ss):
    d[p].append(ss)

# consider possible perimeters
for p in sorted(d.keys()):
  # choose two triangles (x, y, z), (u, v, w)
  for ((x, y, z), (u, v, w)) in subsets(d[p], size=2, select='P'):
    # such that the hypotenuse of one is a non-hypotenuse of the other
    if w in {x, y}:
      R = u + v  # length of the rope
      printf("R={R} w={w} -> {t1}, {t2} -> {ss}", t1=(x, y, z), t2=(u, v, w), ss=sorted([x, y, z, u, v]))
```
Solution: The sides of the triangles are: 60, 85, 204, 221, 229 ft.

The triangles are: (60, 221, 229) and (85, 204, 221), and the posts were 221 ft apart.

The major and minor axes of the ellipse measure 255 and 186.23 (= 34√30) ft.

You can see the results when some of the rope is used in the attachments by changing the condition on line 7 to [[ p - s < 289 ]].

LikeLike
- Jim Randell 11:56 am on 11 November 2024 Permalink | Reply
  
  Only certain rope lengths will work for this problem.
  
  Lengths that will work are squares of the following primes, and multiples of those squares:
  
  7, 17, 23, 31, 41, 47, 71, 73, 79, 89, 97, …
  
  which are the primes that have a residue of 1 or 7 modulo 8. (See: OEIS A001132).
  
  In the given puzzle: 289 = 17^2.
  
  LikeLike
  - GeoffR 9:17 pm on 12 November 2024 Permalink | Reply
    
    I tested my code with the squares of 7, 23 and 97 which all worked OK:
    
    Five lengths = [12, 21, 28, 35, 37] – for 7 * 7 = 49
    
    Five lengths = [120, 184, 345, 391, 409] – for 23 * 23 = 529
    
    Five lengths = [1092, 1261, 8148, 8245, 8317] – for 97 * 97 = 9409
    
    LikeLike
- Jim Randell 4:51 pm on 13 November 2024 Permalink | Reply
  Here is a general solution that works by expressing the length of the rope R as:
  
  R = k.n^2
  
  (It doesn’t check that R is a multiple of p^2 for some prime p where p mod 8 = 1 or 7).
```
from enigma import (irange, ihypot, prime_factor, arg, printf)

# solve for rope R = k.n^2
def solve(n, k=1):
  # solve the reduced problem R = n^2
  R = n * n
  for i in irange(1, n - 1):
    # calculate the (u, v, w) triangle (w = hypotenuse)
    u = i * n
    v = R - u
    if u > v: break
    w = ihypot(u, v)
    if w is None: continue
    # calculate the (x, w, z) triangle (z = hypotenuse)
    x = u - i * i
    z = R - x
    # return the two triangles, scaled appropriately
    yield ((k * x, k * w, k * z), (k * u, k * v, k * w))

R = arg(289, 0, int)

# express R as k.n^2
k = n = 1
for (p, e) in prime_factor(R):
  (d, r) = divmod(e, 2)
  if r > 0: k *= p
  n *= p**d
printf("[{R} = {k} * {n}^2]")

# solve the problem
for (t1, t2) in solve(n, k):
  w = t1[1]
  ss = sorted(set(t1 + t2))
  printf("R={R} w={w} -> {t1}, {t2} -> {ss}")
```
  LikeLike

Frits 5:56 am on 10 November 2024 Permalink | Reply

from math import isqrt
is_square = lambda n: n == isqrt(n) ** 2
 
L = 289
 
# RHS triangle a^2 + b^2 = c^2 
# where c is the distance between the two focal points with a <= b
for a in range(1, L // 2 + 1):
  if not is_square(c2 := a**2 + (b := L - a)**2): continue
  # LHS triangle c^2 + d^2 = (L - d)^2
  if c2 % L: continue
  if (double_d := L - c2 // L) % 2: continue
  d = double_d // 2
  print("answer:", sorted([a, b, int(c2**.5), d, L - d]))

LikeLike

Frits 1:03 pm on 10 November 2024 Permalink | Reply

A variation with 4 iterations of k (or only 2 if we use the parity of L).

from math import ceil
 
L = 289     # 17^2

# as c2 % L = 0 then c^2 = multiplier * L
# c^2 = k^2 * L as L is a square number

# a^2 + (L - a)^2 = c^2
# a = (2.L +- sqrt(4 * L^2 - 8.L^2 + 8.c^2)) / 4
# discriminant:  -4 * L^2 + 8 * c^2 >= 0
# c^2 >= L**2 / 2 --> k^2 >= L / 2
for k in range(ceil((L / 2)**.5), ceil(L**.5)):
  c2 = L * k**2   # c2 % L = 0
  
  # as L is odd then k must be odd as well (we won't use that)
  if (double_d := L - k**2) % 2: continue
  d = double_d // 2
  
  # check valid discriminant
  if (D := -4 * L**2 + 8 * c2) < 0: continue
  # a is the bigger non-hypothenuse side (using '+' in the formula)
  a, r = divmod(2 * L + D**.5, 4)
  if r: continue
  a = int(a)
  c = int((L * k**2)**.5)
  print("answer:", sorted([a, L - a, c, d, L - d]))

LikeLike

GeoffR 10:01 am on 10 November 2024 Permalink | Reply


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

% Two triangles are abe with 'b' as  hypotenuse and cde with 'e' as hypotenuse
% 'e' also is the distance between the two stakes
var 10..289:a; var 10..289:b; var 10..289:c;
var 10..289:d; var 10..289:e;

constraint all_different ([a, b, c, d, e]);

constraint a + b == 289 /\ c + d == 289;

constraint a*a + e*e == b*b /\ c*c + d*d == e*e;

array[1..5] of var int: unsorted = [a, b, c, d, e];
array[1..5] of var int: sorted = sort(unsorted);

solve satisfy;

output [
  "Five lengths in increasing order: ", show(sorted)
];

LikeLike

GeoffR 7:02 pm on 10 November 2024 Permalink | Reply

Faster than expected with all the looping.

def is_sq(n):
  if round(n ** 0.5) ** 2 == n:
    return True
  return False

# 1st triangle is aeb with hypotenuse b
# e is distance between the two stakes
for a in range(10, 290):
  for e in range(a+1, 290):
    if is_sq(a ** 2 + e ** 2):
      b = int((a ** 2 + e ** 2) ** 0.5)
      if a + b != 289:continue
      
      # 2nd triangle is cde with hypotenuse e
      for c in range(10, 290):
        for d in range(c+1, 290):
          if c + d != 289:continue
          if c ** 2 + d ** 2 == e ** 2:
            L1 = [a, b, c, d, e]
            if len(L1) == len(set(L1)):
              sorted_list = sorted(L1)
              print(f"Five lengths = {sorted_list}")

LikeLike

Jim Randell 10:47 am on 8 November 2024 Permalink | Reply
Tags: by: C Higgins ( 37 ), by: H Bradley ( 37 )

Teaser 2616: Elevenses

From The Sunday Times, 11th November 2012 [link] [link]

On 11/11 it is perhaps appropriate to recall the following story. In the graphics class students were illustrating pairs of similar triangles. In Pat’s larger triangle the sides were all even whole numbers divisible by 11. In fact they were 22 times the corresponding sides of his smaller triangle. As well as this, in the smaller triangle the digits used overall in the lengths of the three sides were all different and did not include a zero. Miraculously, exactly the same was true of the larger triangle.

What were the sides of Pat’s smaller triangle?

[teaser2616]

Jim Randell 10:47 am on 8 November 2024 Permalink | Reply

We can place some bounds on the sides of the triangles:

The smaller triangle cannot have sides less than 6, as the corresponding side in the larger triangle would have repeated digits.

And so the smallest side in the larger triangle must have at least 3 digits, and as there are only 9 digits available, each side of the larger triangle must have 3 digits, and so the sides of the smaller triangle are between 6 and 43.

This Python program collects possible sides for the large and small triangles, and then chooses three pairs that can form viable triangles.

It runs in 66ms. (Internal runtime is 1.04ms).

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

# check for allowable digits
def check(*vs):
  s = join(vs)
  if '0' in s or is_duplicate(s): return False
  return True

# find multiples of 22 with distinct non-zero digits
d = dict()  # d maps n -> n / 22
for i in irange(6, 43):
  if not check(i): continue
  j = i * 22
  if not check(j): continue
  d[j] = i

# choose the two smaller sides
for (a, b) in subsets(d.keys(), size=2):
  if not (check(a, b) and check(d[a], d[b])): continue

  # choose the longer side
  for c in d.keys():
    # check for viable triangle
    if not (b < c): continue
    if not (c < a + b): break
    # check the digits
    if not (check(a, b, c) and check(d[a], d[b], d[c])): continue
    # output solution
    printf("{t1} -> {t2}", t2=(a, b, c), t1=(d[a], d[b], d[c]))

Solution: The sides of the smaller triangle are: 18, 26, 37.

And the corresponding sides of the larger triangle are: 396, 572, 814.

LikeLike

Frits 1:46 pm on 8 November 2024 Permalink | Reply

from enigma import SubstitutedExpression
 
# the alphametic puzzle
p = SubstitutedExpression(
  [
    "div(ABC, 22) = PQ", 
    "A < D",
    "div(DEF, 22) = RS",
    "D < G",
    "div(GHI, 22) = TU",
 
    # allow for single digit sides of smaller triangle   
    "P == 0 or P not in {Q, R, S, T, U}",
    "R == 0 or R not in {P, Q, S, T, U}",
    "T == 0 or T not in {P, Q, R, S, U}",
    
    # viable triangle
    "TU < PQ + RS",
    
    "0 not in {A, B, C, D, E, F, G, H, I, Q, S, U}",
  ],
  answer="PQ, RS, TU",
  d2i="",
  distinct=("ABCDEFGHI","QSU"),
  verbose=0,    # use 256 to see the generated code
) 

# print answers
for ans in p.answers():
  print(f"answer: {ans}")

LikeLike

GeoffR 11:16 am on 9 November 2024 Permalink | Reply


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

% Smaller triangle - assumed 2 digit sides
var 1..9:a; var 1..9:b;  var 1..9:c; var 1..9:d; var 1..9:e; var 1..9:f;

constraint all_different([a, b, c, d, e, f]);
var 12..98:ab == 10*a + b;
var 12..98:cd == 10*c + d;
var 12..98:ef == 10*e + f;
constraint ab < cd /\ cd < ef;  % order sides

% Larger triangle - assumued 3 digit sides
var 1..9:A; var 1..9:B;  var 1..9:C; 
var 1..9:D; var 1..9:E;  var 1..9:F;
var 1..9:G; var 1..9:H;  var 1..9:I;

constraint all_different([A, B, C, D, E, F, G, H, I]);  
var 123..987:ABC == 100*A + 10*B + C;
var 123..987:DEF == 100*D + 10*E + F;
var 123..987:GHI == 100*G + 10*H + I;
constraint ABC < DEF /\ DEF < GHI;  % order sides

% Larger triangle has even sides and all sides are divisible by 11
constraint sum([ABC mod 2 == 0, DEF mod 2 == 0, GHI mod 2 == 0]) == 3;
constraint sum([ABC mod 11 == 0, DEF mod 11 == 0, GHI mod 11 == 0]) == 3;

% larger triangle's sides are 22 times smaller triangle's sides
constraint ABC == 22 * ab /\ DEF == 22 * cd /\ GHI == 22 * ef;

solve satisfy;

output ["Smaller Triangle Sides = " ++ show(ab) ++ ", " ++ show(cd) ++ ", " ++ show(ef)
++ "\n" ++ "Larger Triangle Sides = " ++ show(ABC) ++ ", " ++ show(DEF) ++ ", " ++ show(GHI)
];

% Smaller Triangle Sides = 18, 26, 37
% Larger Triangle Sides = 396, 572, 814
% ----------
% ==========

LikeLike

Jim Randell 7:58 am on 5 November 2024 Permalink | Reply
Tags: by: John Owen ( 33 )

Teaser 2608: Football logic

From The Sunday Times, 16th September 2012 [link] [link]

In the logicians’ football tournament, each of three teams (captained by Alf, Bert and Charlie) plays each other once, with three points for a win and one for a draw. In working out their order at the end of the tournament, “goals scored” are used to determine the order of teams with the same points total. Each captain only knows the scores in his own team’s games. At the end I asked the captains in turn whether they knew which position they had finished in. The replies were:

Alf: “no”;
Bert: “no”;
Charlie: “no”;
Alf: “yes”.

In which position did Charlie’s team finish? And what was the result in the game between the other two teams?

[teaser2608]

Jim Randell 8:01 am on 5 November 2024 Permalink | Reply

If a captain knows that they are tied on points with another team, then they cannot know which way the tie breaking will go, as they do not know how many goals the other team scored in their remaining match, so any situation where teams are tied on points will necessarily require the captain to respond that they do not know their final position.

This Python program uses the [[ Football() ]] helper class, and the [[ filter_unique() ]] function from the enigma.py library to solve the puzzle.

It runs in 69ms. (Internal runtime is 838µs).

from enigma import (Football, filter_unique, printf)

# scoring system
football = Football(games='wdl', points=dict(w=3, d=1))

# calculate positions from points, ties are indicated with '='
def pos(pts):
  rs = [None] * len(pts)
  p = 1
  for x in sorted(set(pts), reverse=1):
    k = pts.count(x)
    v = str(p)
    if k > 1: v += '='
    for (i, y) in enumerate(pts):
      if y == x:
        rs[i] = v
    p += k
  return tuple(rs)

is_tie = lambda x: x.endswith('=')

# generate possible situations
def generate():
  # consider possible game outcomes
  for (AB, AC, BC) in football.games(repeat=3):
    # table for each team
    A = football.table([AB, AC], [0, 0])
    B = football.table([AB, BC], [1, 0])
    C = football.table([AC, BC], [1, 1])
    # return (<match-outcomes>, <positions>)
    yield ((AB, AC, BC), pos([A.points, B.points, C.points]))

# indices for the teams, and the matches
(A, B, C) = (AB, AC, BC) = (0, 1, 2)
matches = { A: (AB, AC), B: (AB, BC), C: (AC, BC) }

# can team <j> deduce their finishing position knowing the outcomes of their own matches?
# <f> = 0 if the answer is "no"; = 1 if it is "yes"
def answer(ss, j, f):
  # which matches is team <j> involved in?
  ms = matches[j]
  fnf = lambda t: tuple(t[0][i] for i in ms)
  fng = lambda t: t[1][j]
  # find results with unique/non-unique positions
  r = filter_unique(ss, fnf, fng)
  if f == 0:
    # return results that are non-unique, or end with a tie on points
    return r.non_unique + [t for t in r.unique if is_tie(fng(t))]
  else:
    # return results that are unique, but don't end with a tie on points
    return [t for t in r.unique if not is_tie(fng(t))]

# start with all possible outcomes and positions
ss = list(generate())

# A cannot deduce his finishing position
ss = answer(ss, A, 0)

# B cannot deduce his finishing position
ss = answer(ss, B, 0)

# C cannot deduce his finishing position
ss = answer(ss, C, 0)

# A can now deduce his finishing position
ss = answer(ss, A, 1)

# output solutions
for ((AB, AC, BC), (posA, posB, posC)) in ss:
  printf("posC = {posC}; AB = {AB} [AB={AB} AC={AC} BC={BC}; posA={posA} posB={posB} posC={posC}]")

Solution: Charile finished in second place. The game between Alf and Bert was a draw.

The match outcomes are either:

(A v B = draw; C beat A; B beat C)
B = 1w 1d = 4 pts (1st)
C = 1w = 3 pts (2nd)
A = 1d = 1 pt (3rd)

or:

(A v B = draw; A beat C; C beat B)
A = 1w 1d = 4 pts (1st)
C = 1w = 3pts (2nd)
B = 1d = 1pt (3rd)

LikeLike

Jim Randell 6:57 am on 3 November 2024 Permalink | Reply
Tags: by: Howard Williams ( 44 )
Teaser 3241: Users pay
From The Sunday Times, 3rd November 2024 [link] [link]

I live in a cul-de-sac which had planning permission for building on ten identical plots along the whole length of one side of the road. The developer started building, and numbered the properties, from the closed end. The plots aren’t all finished, and the cost of surfacing the whole road has to be paid by the owners of the completed properties. It was decided that the owners would only contribute to the cost of the road leading to their property, so the owner of number 1 pays for the road section in front of their property, the cost of the section outside number 2 is shared equally between numbers 1 and 2, and so on.

My contribution is £ 1,000, while that of another homeowner is £ 3,800.

What is my house number and how many houses have been built?

[teaser3241]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell and Hugo are discussing. Toggle Comments
- Hugo 7:18 am on 3 November 2024 Permalink | Reply
  
  This doesn’t appear to make sense. If the houses are numbered from the closed end, one would expect the owner of no. 1 to have to pay the highest contribution, since he is furthest from the point of access to the road.
  
  LikeLike
  - Jim Randell 8:16 am on 3 November 2024 Permalink | Reply
    
    I think the way it works is as follows:
    
    If 3 houses were built, then:
    
    road section #1 is paid for by house #1
    road section #2 is paid for by houses #1, #2 (half each)
    road sections #3..#10 are paid for by houses #1, #2, #3 (one third each)
    
    So house #1 pays the most, then #2 and then #3, and the entire cost of the road is covered.
    
    LikeLike
- Jim Randell 7:52 am on 3 November 2024 Permalink | Reply
  It took me a couple of attempts to work out how this puzzle is meant to work. I assumed the houses are built in numerical order starting at #1.
  
  This Python program runs in 70ms. (Internal runtime is 537µs).
```
from enigma import (Rational, irange, subsets, printf)

Q = Rational()

# consider total number of houses built
for n in irange(1, 10):

  # accumulate total cost (in sections) for each house
  cost = dict((i, 0) for i in irange(1, n))
  # allocate costs for each section
  for k in irange(1, 10):
    m = min(k, n)
    for i in irange(1, m):
      cost[i] += Q(1, m)

  # look for one cost which is 3.8x another
  for (a, b) in subsets(sorted(cost.keys()), size=2):
    if 10 * cost[a] == 38 * cost[b]:
      printf("n={n} -> a={a} b={b}")
```
  Solution: 8 houses have been built. The setters house is #7.
  
  The cost of the ten sections of road is distributed among the 8 houses as follows:
  
  #1: 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/8 + 1/8 = 831/280
  #2: 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/8 + 1/8 = 551/280
  #3: 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/8 + 1/8 = 411/280
  #4: 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/8 + 1/8 = 953/840
  #5: 1/5 + 1/6 + 1/7 + 1/8 + 1/8 + 1/8 = 743/840
  #6: 1/6 + 1/7 + 1/8 + 1/8 + 1/8 = 115/168
  #7: 1/7 + 1/8 + 1/8 + 1/8 = 29/56
  #8: 1/8 + 1/8 + 1/8 = 3/8
  
  The setter (at house #7) pays £1000, so the actual costs are:
  
  #1: £ 5731.03
  #2: £ 3800.00
  #3: £ 2834.48
  #4: £ 2190.80
  #5: £ 1708.05
  #6: £ 1321.84
  #7: £ 1000.00
  #8: £ 724.14
  
  So it is the occupant of house #2 who has to pay £ 3800.
  
  And the total cost of the road is £ 19310.35.
  
  LikeLike

Jim Randell 7:44 am on 31 October 2024 Permalink | Reply
Tags: by: C Higgins ( 37 ), by: H Bradley ( 37 )

Teaser 2597: Ages ago

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

Bert’s age in years is one less than one-and-a-half times the age Alf was a whole number of years ago. Cal’s age in years is one less than one-and-a-half times the age Bert was, the same number of years ago.

Dave’s age in years is one less than one-and-a-half times the age Cal was, again the same number of years ago. All four ages are different two-figure numbers, Cal’s age being Bert’s age with the order of the digits reversed.

What (in alphabetical order) are their ages?

[teaser2597]

Jim Randell 7:45 am on 31 October 2024 Permalink | Reply
Here’s a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

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

SubstitutedExpression

# ages now:
#
#   AB = Alf
#   CD = Bert
#   DC = Cal
#   EF = Dave
#
# let the number of years ago be XY

--distinct="CD"
--invalid="0,ACDE"

# "B's age is 1 less than 1.5 times A's age XY years ago"
"3 * (AB - XY) == 2 * (CD + 1)"

# "C's age is 1 less than 1.5 times B's age XY years ago"
"3 * (CD - XY) == 2 * (DC + 1)"

# "D's age is 1 less than 1.5 times C's age XY years ago"
"3 * (DC - XY) == 2 * (EF + 1)"

# ages are all different
"all_different(AB, CD, DC, EF)"

--template="(AB CD DC EF) (XY)"
--solution=""
```
Solution: The ages now are: Alf = 98; Bert = 86; Cal = 68; Dave = 41.

And Cal’s age is the reverse of Bert’s.

40 years ago, Alf was 58. And 1.5× this age is 87, and Bert’s current age is one less than this.

40 years ago, Bert was 46. And 1.5× this age is 69, and Cal’s current age is one less than this.

40 years ago, Cal was 28. And 1.5× this age is 42, and Dave’s current age is one less than this.

LikeLike

Ruud 8:38 am on 31 October 2024 Permalink | Reply

Brute force:

import itertools

for a, b, d in itertools.permutations(range(10, 100), 3):
    c = int(str(b)[::-1])
    if b != c and c >= 10:
        for n in range(1, min(a, b, c, d) + 1):
            if b == (a - n) * 1.5 - 1:
                if c == (b - n) * 1.5 - 1:
                    if d == (c - n) * 1.5 - 1:
                        print(f"Alf={a} Bert={b} Cal={c} Dave={d} Number of years ago={n}")

LikeLiked by 1 person

ruudvanderham 9:26 am on 31 October 2024 Permalink | Reply

Quite different and much more efficient than my previous one:

for a in range(10, 100):
    for n in range(a):
        b = (a - n) * 1.5 - 1
        c = (b - n) * 1.5 - 1
        d = (c - n) * 1.5 - 1
        if all(x == round(x) and n < x < 100 for x in (b, c, d)):
            if len({a, b, c, d}) == 4:
                if str(round(b)) == str(round(c))[::-1]:
                    print(a, b, c, d, n)

LikeLike

GeoffR 9:35 am on 1 November 2024 Permalink | Reply

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

% All ages are different 2-digit numbers
var 10..99:Alf; var 10..99:Bert; var 10..99:Cal; var 10..99:Dave;
constraint all_different([Alf, Bert, Cal, Dave]);

var 1..99:Y;  % the number of years ago

constraint (2 * Bert ==  (Alf - Y) * 3 - 2)
/\ (2 * Cal  ==  (Bert - Y) * 3 - 2)
/\ (2 * Dave ==  (Cal - Y) * 3 - 2);

% Cal’s age being Bert’s age with the order of the digits reversed.
constraint Cal div 10 == Bert mod 10 /\ Cal mod 10 == Bert div 10;

solve satisfy;

output ["Alf = " ++ show(Alf) ++ ", Bert = " ++ show(Bert) ++
", Cal = " ++ show(Cal) ++ ", Dave = " ++ show(Dave) ++ ", Y = " ++ show(Y)];

% Alf = 98, Bert = 86, Cal = 68, Dave = 41, Y = 40 
% ----------
% ==========

LikeLike

Jim Randell 8:10 am on 29 October 2024 Permalink | Reply
Tags: by: Danny Roth ( 87 )

Teaser 2540: Extra time

From The Sunday Times, 29th May 2011 [link] [link]

George and Martha planned a holiday on the south coast. The second-class rail fare each way was a certain whole number of pounds per person and the nightly cost of an inexpensive double room, in pounds, was the same number but with digits reversed. They originally planned to stay 30 nights, but then increased that to 33. “So the total cost will go up by 10%”, said Martha. “No”, replied George, “it will go up by some other whole number percentage”.

What is the nightly cost of a double room?

[teaser2540]

Jim Randell 8:11 am on 29 October 2024 Permalink | Reply
I assumed that the rail fare does not have a trailing zero, so that the room rate does not have a leading zero.

This Python program finds the first solution where the rail fare and room rate are less than £100.

It runs in 80ms. (Internal runtime is 188µs).
```
from enigma import (irange, nrev, div, printf)

# consider possible rail fares
for F in irange(1, 99):
  # disallow trailing zeros
  if F % 10 == 0: continue

  # the room rate is the reverse of this
  R = nrev(F)

  # cost for 30 nights and 33 nights
  t30 = 4*F + 30*R
  t33 = 4*F + 33*R

  # t33 is a k per cent increase on t30
  r = div(100 * t33, t30)
  if r is None: continue

  printf("F={F} R={R} r={r}%")
  break
```
Solution: The cost of the room was £ 54 per night.

And so the rail fares were £ 45 per person (single).

The cost for 30 days is:

4× 45 + 30× 54 = 1800

And the cost for 33 days:

4× 45 + 33× 54 = 1962

And we have:

1962 / 1800 = 1.09

So the increase is 9%.

There are larger solutions, for example:

F=45, R=54
F=495, R=594
F=4545, R=5454
F=4995, R=5994
F=45045, R=54054
F=49995, R=59994
F=450045, R=540054
F=454545, R=545454
F=495495, R=594594
F=499995, R=599994
…

But the room is described as “inexpensive”, so only the first of these is a viable solution.

However, they all involve a 9% increase.

LikeLike

GeoffR 12:34 pm on 29 October 2024 Permalink | Reply


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

var 1..9:A; var 1..9:B; 
var 1..99: per_cent;

% Assume room cost < £100
var 12..98: Room == 10*A + B; 
var 12..98: Fare == 10*B + A;

% Two people with outgoing and return trips = 4 fares
var 600..6000: Cost30 == 30 * Room + 4 * Fare;
var 660..6060: Cost33 == 33 * Room + 4 * Fare;

% Calculate percentage increased room cost
constraint (Cost33 - Cost30) * 100 ==  Cost30 * per_cent;

solve satisfy;

output ["Room cost = " ++ show(Room) ++ " pounds per night."
++ "\n" ++ "Cost percentage increase = " ++ show(per_cent) ++ " %"];

% Room cost = 54 pounds per night.
% Cost percentage increase = 9 %
% ----------
% ==========

LikeLike

Ruud 4:15 am on 30 October 2024 Permalink | Reply

from istr import istr


istr.repr_mode("int")
for train in istr(range(10, 100)):
    room = train[::-1]
    if room[0] != 0:
        total30 = int(train * 4 + room * 30)
        total33 = int(train * 4 + room * 33)
        increase = ((total33 - total30) / total30) * 100
        if increase % 1 == 0:
            print(f"{train=} {room=} {total30=} {total33=} {increase=:.0f}%")

LikeLike

Frits 5:43 am on 3 November 2024 Permalink | Reply

Objective was to use fewer iterations.

from fractions import Fraction as RF

# fare = 10 * f + g, room cost = 10 * g + f

# t30 = 4*F + 30*R = 70*f + 304*g  
# t33 = 4*F + 33*R = 73*f + 334*g

# 100 + p = 100 * (73*f + 334*g) / (70*f + 304*g)     

# integer percentages less than 10
for p in range(9, 0, -1):
  # (7300*f + 33400*g) - (100 + p) * (70*f + 304*g) = 0
  # ((300 - p*70)*f + (3000 - 304*p)*g) = 0
  
  # calculate - f / g  (g will not be zero)
  r = RF(3000 - 304*p, 300 - p*70)
  if r > 0: continue  
  f, g = abs(r.numerator), abs(r.denominator)
  if not (0 < f < 10 and g < 10): continue 
  
  # double check
  if 100 * (73*f + 334*g) / (70*f + 304*g) - 100 != p: continue
  print(f"answer: {10 * g + f} pounds per night")

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

Jim Randell 6:34 am on 15 December 2024 Permalink | Reply Tags: by: Andrew Skidmore ( 87 )

Rate this:

Share:

Jim Randell 6:52 am on 15 December 2024 Permalink | Reply

Reply Cancel reply

Jim Randell 10:50 am on 12 December 2024 Permalink | Reply Tags: by: Andrew Skidmore ( 87 )

Rate this:

Share:

Jim Randell 10:51 am on 12 December 2024 Permalink | Reply

GeoffR 1:28 pm on 12 December 2024 Permalink | Reply

Ruud 5:18 am on 13 December 2024 Permalink | Reply

GeoffR 2:59 pm on 13 December 2024 Permalink | Reply

Jim Randell 10:26 am on 10 December 2024 Permalink | Reply Tags: by: C Higgins ( 37 ), by: H Bradley ( 37 )

Rate this:

Share:

Jim Randell 10:26 am on 10 December 2024 Permalink | Reply

Frits 12:18 pm on 11 December 2024 Permalink | Reply

Jim Randell 9:30 am on 12 December 2024 Permalink | Reply

Frits 11:26 am on 12 December 2024 Permalink | Reply

Brian Gladman 6:56 pm on 13 December 2024 Permalink | Reply

GeoffR 10:59 am on 14 December 2024 Permalink | Reply

Jim Randell 9:03 am on 8 December 2024 Permalink | Reply Tags: by: Stephen Hogg ( 64 )

Rate this:

Share:

Jim Randell 9:43 am on 8 December 2024 Permalink | Reply

ruudvanderham 2:54 pm on 9 December 2024 Permalink | Reply

Jim Randell 9:25 am on 6 December 2024 Permalink | Reply Tags: by: Andrew Skidmore ( 87 )

Rate this:

Share:

Jim Randell 9:25 am on 6 December 2024 Permalink | Reply

Jim Randell 9:57 am on 3 December 2024 Permalink | Reply Tags: by: John Owen ( 33 )

Rate this:

Share:

Jim Randell 9:57 am on 3 December 2024 Permalink | Reply

Jim Randell 7:03 am on 1 December 2024 Permalink | Reply Tags: by: Mark Valentine ( 17 )

Rate this:

Share:

Jim Randell 7:38 am on 1 December 2024 Permalink | Reply

Jim Randell 3:10 pm on 1 December 2024 Permalink | Reply

Jim Randell 4:55 pm on 27 November 2024 Permalink | Reply Tags: by: Angela Newing ( 39 )

Rate this:

Share:

Jim Randell 4:56 pm on 27 November 2024 Permalink | Reply

Ruud 8:25 am on 28 November 2024 Permalink | Reply

Jim Randell 7:08 am on 24 November 2024 Permalink | Reply Tags: by: Peter Good ( 28 ), flawed ( 55 )

Rate this:

Share:

Jim Randell 11:25 am on 24 November 2024 Permalink | Reply

Rob Bellis 8:48 am on 26 November 2024 Permalink | Reply

Jim Randell 8:56 am on 26 November 2024 Permalink | Reply

NigelR 5:38 pm on 24 November 2024 Permalink | Reply

Jim Randell 11:12 am on 25 November 2024 Permalink | Reply

Brian Gladman 2:56 pm on 29 November 2024 Permalink | Reply

Jim Randell 3:08 pm on 29 November 2024 Permalink | Reply

Brian Gladman 5:15 pm on 29 November 2024 Permalink | Reply

Frits 11:53 am on 12 December 2024 Permalink | Reply

Frits 10:59 am on 12 December 2024 Permalink | Reply

Jim Randell 8:40 am on 22 November 2024 Permalink | Reply Tags: by: Graham Smithers ( 84 )

Rate this:

Share:

Jim Randell 8:41 am on 22 November 2024 Permalink | Reply

Frits 4:28 am on 23 November 2024 Permalink | Reply

Jim Randell 10:09 am on 23 November 2024 Permalink | Reply

Ruud 8:06 am on 23 November 2024 Permalink | Reply

Frits 12:49 pm on 23 November 2024 Permalink | Reply

Ruud 4:21 pm on 23 November 2024 Permalink | Reply

Jim Randell 11:16 am on 19 November 2024 Permalink | Reply Tags: by: Nick MacKinnon ( 56 )

Rate this:

Share:

Jim Randell 11:17 am on 19 November 2024 Permalink | Reply

Jim Randell 6:34 am on 15 December 2024 Permalink | Reply
Tags: by: Andrew Skidmore ( 87 )

Jim Randell 10:50 am on 12 December 2024 Permalink | Reply
Tags: by: Andrew Skidmore ( 87 )

Jim Randell 10:26 am on 10 December 2024 Permalink | Reply
Tags: by: C Higgins ( 37 ), by: H Bradley ( 37 )

Jim Randell 9:03 am on 8 December 2024 Permalink | Reply
Tags: by: Stephen Hogg ( 64 )

Jim Randell 9:25 am on 6 December 2024 Permalink | Reply
Tags: by: Andrew Skidmore ( 87 )

Jim Randell 9:57 am on 3 December 2024 Permalink | Reply
Tags: by: John Owen ( 33 )

Jim Randell 7:03 am on 1 December 2024 Permalink | Reply
Tags: by: Mark Valentine ( 17 )

Jim Randell 4:55 pm on 27 November 2024 Permalink | Reply
Tags: by: Angela Newing ( 39 )

Jim Randell 7:08 am on 24 November 2024 Permalink | Reply
Tags: by: Peter Good ( 28 ), flawed ( 55 )

Jim Randell 8:40 am on 22 November 2024 Permalink | Reply
Tags: by: Graham Smithers ( 84 )

Jim Randell 11:16 am on 19 November 2024 Permalink | Reply
Tags: by: Nick MacKinnon ( 56 )

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

Jim Randell 8:43 am on 14 November 2024 Permalink | Reply
Tags: by: C Higgins ( 37 ), by: H Bradley ( 37 )

Jim Randell 9:03 am on 12 November 2024 Permalink | Reply
Tags: by: Victor Bryant ( 144 )

Jim Randell 1:36 am on 10 November 2024 Permalink | Reply
Tags: by: Phil Jackson ( 2 )

Jim Randell 10:47 am on 8 November 2024 Permalink | Reply
Tags: by: C Higgins ( 37 ), by: H Bradley ( 37 )

Jim Randell 7:58 am on 5 November 2024 Permalink | Reply
Tags: by: John Owen ( 33 )

Jim Randell 6:57 am on 3 November 2024 Permalink | Reply
Tags: by: Howard Williams ( 44 )

Jim Randell 7:44 am on 31 October 2024 Permalink | Reply
Tags: by: C Higgins ( 37 ), by: H Bradley ( 37 )