Recent Updates Page 12 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 8:07 am on 8 January 2025 Permalink | Reply
    Tags:   

    Teaser 2595: Stylish fences 

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

    Farmer Giles has a hexagonal field bounded by six straight fences. The six corners lie on a circle of diameter somewhere around 250 metres. At three alternate corners there are stiles. The angles of the hexagon at the corners without stiles are all the same. All six fences are different whole numbers of metres long. I have just walked in a straight line from one of the stiles to another and the distance walked was a whole number of metres.

    How many?

    [teaser2595]

     
    • Jim Randell's avatar

      Jim Randell 8:07 am on 8 January 2025 Permalink | Reply

      Suppose the field is:

      If the stiles are at A, C, E, then the angles at B, D, F are all equal, which means they are all 120°, and so the lines AC, AE, CE (= paths between stiles) are all equal length and so ACE is an equilateral triangle. (See: [ @wikipedia ]).

      If the diameter of the circle is d, then the length of the paths, p, is given by:

      p = d √(3/4)

      And d is around 250, let’s say in the range [245, 255], so the path is in the range [212.176, 220.836], so we can consider path lengths of 212 .. 221.

      For a given path length p (= AC) we can look for integer fence lengths (x, y) (= (AB, BC)) that complete the triangle ABC. By the cosine rule in ABC:

      p^2 = x^2 + y^2 + xy
      ⇒
      y^2 + xy + (x^2 − p^2) = 0

      which is a quadratic equation in y.

      So we can consider values for x and use the equation to find possible corresponding y values.

      And we need to find (at least) 3 different (x, y) pairs to complete the hexagon, so that all 6 fences are different lengths.

      The following Python program runs in 76ms. (Internal runtime is 7.5ms).

      from enigma import (irange, quadratic, sq, sqrt, printf)

r43 = sqrt(4, 3)

# consider possible path lengths
for p in irange(212, 221):
  # collect possible (x, y) pairs
  ss = list()
  for x in irange(1, p - 1):
    for y in quadratic(1, x, sq(x) - sq(p), domain='Z'):
      if x < y < p:
        ss.append((x, y))

  # we need (at least) 3 different pairs
  if len(ss) < 3: continue
  # output solution
  printf("p={p} d={d:.3f} -> {ss}", d=p * r43)

      Solution: The path is 217m long.

      There are actually 4 possible (x, y) pairs, and any 3 of them can be used to construct the hexagon:

      p=217 d=250.570 → [(17, 208), (77, 168), (87, 160), (93, 155)]

      If the puzzle had specified that the diameter of the circle was “around 400 m”, then we would have been able to give the lengths of the 6 fences:

      p=343 d=396.062 → [(37, 323), (112, 273), (147, 245)]

      Like

  • Unknown's avatar

    Jim Randell 6:48 am on 5 January 2025 Permalink | Reply
    Tags:   

    Teaser 3250: Very similar triangles 

    From The Sunday Times, 5th January 2025 [link] [link]

    I have a piece of A6 paper on which I draw two triangles. The triangles are very similar in two ways. First of all, they are both the same shape. Not only that, the lengths of two of the sides of one of the triangles are the same as the lengths of two of the sides of the other triangle, but one triangle is larger than the other.

    If the sides of the triangles are whole numbers of millimetres and the triangles don’t have any obtuse angles:

    What are the lengths of sides of the larger triangle?

    Note: A sheet of A6 paper measures 105 mm × 148 mm.

    [teaser3250]

     
    • Jim Randell's avatar

      Jim Randell 7:02 am on 5 January 2025 Permalink | Reply

      (See also: Enigma 1198).

      This Python program runs in 67ms. (Internal runtime is 1.5ms).

      from enigma import (irange, hypot, intf, printf)

# consider triangles with sides (a, b, c), (b, c, d)
# we have: ratio(a, b, c) = ratio(b, c, d)
M = intf(hypot(105, 148))  # max length
for a in irange(1, M - 1):
  for b in irange(a + 1, M):
    (c, r) = divmod(b * b, a)
    if c > M: break
    if r != 0: continue
    # check triangle is not obtuse
    if a + b <= c or c * c > a * a + b * b: continue
    (d, r) = divmod(c * c, b)
    if d > M: break
    if r != 0: continue
    # output solution
    printf("{t1} + {t2}", t1=(a, b, c), t2=(b, c, d))

      There is only a single candidate solution, and it is easy to demonstrate that the triangles can both fit onto a single piece of A6.

      Solution: The sides of the larger triangle are: 80 mm, 100 mm, 125 mm.

      And the smaller triangle has sides: 64 mm, 80 mm, 100 mm.

      The internal angles of the triangles are (approximately) 40°, 53°, 87°.

      Here is a diagram showing both triangles on a piece of A6 paper (dimensions in mm):

      Like

    • Tony Smith's avatar

      Tony Smith 4:29 pm on 5 January 2025 Permalink | Reply

      In fact there is nothing to stop the triangles overlapping.

      Like

      • Jim Randell's avatar

        Jim Randell 4:57 pm on 5 January 2025 Permalink | Reply

        @Tony: True enough. I was imagining we wanted to cut the triangles out, but that isn’t what the puzzle text says.

        Like

      • Ellen Napier's avatar

        Ellen Napier 12:18 am on 10 February 2026 Permalink | Reply

        In that case, the smaller size B7 would suffice.

        Like

  • Unknown's avatar

    Jim Randell 10:22 pm on 3 January 2025 Permalink | Reply
    Tags:   

    Teaser 2589: A certain age 

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

    My cousin and I share a birthday. At the moment my age, in years, is the same as hers but with the order of the two digits reversed. On one of our past birthdays I was five times as old as her but, even if I live to a world record “ripe old age”, there is only one birthday in the future on which my age will be a multiple of hers.

    How old am I?

    [teaser2589]

     
    • Jim Randell's avatar

      Jim Randell 10:22 pm on 3 January 2025 Permalink | Reply

      Suppose my age is XY and my cousin’s age is YX, then we have X > Y.

      This Python program runs in 63ms. (Internal runtime is 306µs).

      from enigma import (irange, subsets, printf)

# ages are the reverse of each other
for (Y, X) in subsets(irange(1, 9), size=2):
  (XY, YX) = (10 * X + Y, 10 * Y + X)

  # look for an age in the past where I was five times the age of the cousin
  past = ((XY - n, YX - n) for n in irange(1, YX - 1))
  x1 = list((x, y) for (x, y) in past if x == 5 * y)
  if not x1: continue

  # look for ages in the future where my age is a multiple of hers
  future = ((XY + n, YX + n) for n in irange(1, 130 - XY))
  x2 = list((x, y) for (x, y) in future if x % y == 0)
  if len(x2) != 1: continue

  # output solution
  printf("XY={XY} YX={YX} [past={x1} future={x2}]")

      Solution: Your age is 62.

      And the cousin’s age is 26.

      17 years ago the ages were 45 and 9 (and 45 = 5 × 9).

      In 10 years time the ages will be 72 and 36 (and 72 = 2 × 36).

      Like

    • Hugo's avatar

      Hugo 7:23 am on 5 January 2025 Permalink | Reply

      The difference between the ages is 9(X – Y).
      That remains the same each year, and at one time it was 4 times the cousin’s age.
      So (X – Y) is either 4 or 8.
      The current ages could be 15, 51; 26, 62; 37, 73; 48, 84; or 59, 95.
      In all cases the difference is 36.
      Ages when one age is an integer multiple of the other are 1, 37; 2, 38; 4, 40; 9, 45; 18, 54; 36, 72.
      Only one of those is allowed to be in the future.

      Alternatively, the current ages could be 19, 91, with difference 72.
      Then the ‘multiple’ ages are 1, 73; 2, 74; 4, 76; 8, 80; 9, 81; 18, 90; 36, 108; 72, 144.
      But two of those are in the future.
      The only valid solution appears to be 26, 62.

      Like

    • Hugo's avatar

      Hugo 7:32 am on 6 January 2025 Permalink | Reply

      I forgot some pairs of ages where one is an integer multiple of the other.
      With a difference 36: 3, 39; 6, 42; 12, 48.
      Similarly with a difference 72, but we’ve eliminated that as a potential solution.

      Like

  • Unknown's avatar

    Jim Randell 4:43 pm on 31 December 2024 Permalink | Reply
    Tags:   

    Teaser 2596: Unusual factors 

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

    There are no neat tests for divisibility by 7 or 13, so it’s unusual for these factors to feature in Teasers. Today we put that right.

    If you start with any three different non-zero digits, then you can make six different three-digit numbers using precisely those digits. For example, with 2, 5 and 7 you get 257, 275, 527, 572, 725 and 752. Here, one of their differences (572 − 257) is divisible by 7, and another (725
    − 257) is divisible by 13.

    Your task today is to find three different digits so that none of the six possible three-digit numbers and none of the differences between any pair of them is a multiple of either 7 or 13.

    What are the three digits?

    My review of puzzles posted in 2024 is at Enigmatic Code: 2024 in review.

    [teaser2596]

     
    • Jim Randell's avatar

      Jim Randell 4:44 pm on 31 December 2024 Permalink | Reply

      This Python program looks at possible sets of three digits, and then uses the [[ generate() ]] function to generate possible arrangements and differences. This means as soon as we find a number that fails the divisibility tests we can move on to the next set of digits.

      It runs in 65ms. (Internal runtime is 491µs).

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

# generate numbers to test from digits <ds>
def generate(ds):
  seen = list()
  # consider all arrangements of the digits
  for n in subsets(ds, size=len, select='P', fn=nconcat):
    # return the arrangement
    yield n
    # return the differences
    for x in seen:
      yield abs(n - x)
    seen.append(n)

# choose 3 digits
for ds in subsets(irange(1, 9), size=3):
  # check numbers are not divisible by 7 or 13
  if any(n % 7 == 0 or n % 13 == 0 for n in generate(ds)): continue
  # output solution
  printf("digits = {ds}")

      Solution: The three digits are: 1, 4, 9.

      See also: A video by Matt Parker on divisibility tests [@youtube].

      Like

    • GeoffR's avatar

      GeoffR 7:34 pm on 1 January 2025 Permalink | Reply 

      from itertools import permutations
from enigma import nsplit

N = []

for a, b, c in permutations(range(1, 10), 3): 
    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
    # Check three-digit numbers are not divisible by 7 or 13
    if any(x % 7 == 0 for x in (n1 ,n2, n3, n4, n5, n6)):
        continue
    if any(x % 13 == 0 for x in (n1, n2, n3, n4, n5, n6)):
        continue
    N.append(n1)

# check differences for each number in the list
# of potential candidates
for m in N:
    x, y, z = nsplit(m)
    m1, m2 = m, 100*x + 10*z + y
    m3, m4 = 100*y + 10*x + z, 100*y + 10*z + x
    m5, m6 = 100*z + 10*x + y, 100*z + 10*y + x
    # a manual check of the 15 differences of each 6-digit number
    if abs(m1-m2) % 7 == 0 or abs(m1-m2) % 13 == 0: continue
    if abs(m1-m3) % 7 == 0 or abs(m1-m3) % 13 == 0: continue
    if abs(m1-m4) % 7 == 0 or abs(m1-m4) % 13 == 0: continue
    if abs(m1-m6) % 7 == 0 or abs(m1-m5) % 13 == 0: continue
    if abs(m1-m6) % 7 == 0 or abs(m1-m6) % 13 == 0: continue
    #
    if abs(m2-m3) % 7 == 0 or abs(m2-m3) % 13 == 0: continue
    if abs(m2-m4) % 7 == 0 or abs(m2-m4) % 13 == 0: continue
    if abs(m2-m5) % 7 == 0 or abs(m2-m5) % 13 == 0: continue
    if abs(m2-m6) % 7 == 0 or abs(m2-m6) % 13 == 0: continue
    #
    if abs(m3-m4) % 7 == 0 or abs(m3-m4) % 13 == 0: continue
    if abs(m3-m5) % 7 == 0 or abs(m3-m5) % 13 == 0: continue
    if abs(m3-m6) % 7 == 0 or abs(m3-m6) % 13 == 0: continue
    #
    if abs(m4-m5) % 7 == 0 or abs(m4-m5) % 13 == 0: continue
    if abs(m4-m6) % 7 == 0 or abs(m4-m6) % 13 == 0: continue
    if abs(m5-m6) % 7 == 0 or abs(m5-m6) % 13 == 0: continue
    if x < y < z:
        print(f"The three digit numbers are {x}, {y} and {z}.")

# The three digit numbers are 1, 4 and 9.

      I resorted to a manual check of the differences of the 6 numbers arising from each 3 digit candidate, as it was not coming out easily in code.

      Like

  • Unknown's avatar

    Jim Randell 1:37 am on 29 December 2024 Permalink | Reply
    Tags:   

    Teaser 3249: Test to twelve 

    From The Sunday Times, 29th December 2024 [link] [link]

    I have been testing for divisibility by numbers up to twelve. I wrote down three numbers and then consistently replaced digits by letters (with different letters used for different digits) to give:

    TEST
    TO
    TWELVE

    Then I tested each of these numbers to see if they were divisible by any of 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 or 12. It turned out that each of these eleven divisors was a factor of exactly one of the three numbers.

    What are the three numbers?

    This completes the archive of puzzles from 2024. There is now a complete archive of puzzles (and solutions!) from July 2012 onwards (plus a lot of earlier puzzles). Enjoy!

    [teaser3249]

     
    • Jim Randell's avatar

      Jim Randell 1:55 am on 29 December 2024 Permalink | Reply

      Here is a short, but not particularly quick, solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      It runs in 446ms (using PyPy, internal runtime of the generated program is 272ms).

      #! python3 -m enigma -rr

SubstitutedExpression

--code="check = lambda ns, ds, k: all(sum(n % d == 0 for n in ns) == k for d in ds)"

"check([TEST, TO, TWELVE], [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], 1)"

      Solution: The numbers are: 3073, 31, 340560.

      So:

      TEST = 3073, is divisible by 7
      TO = 31, is prime
      TWELVE = 340560, is divisible by 2, 3, 4, 5, 6, 8, 9, 10, 11, 12

      Manually:

      Analysis shows that TWELVE must be divisible by 2, 3, 4, 5, 6, 8, 9, 10, 11, 12 (and TO and TEST are not).

      Hence TWELVE is a 6-digit multiple of 3960. The only appropriate candidates are:

      130560
      150480
      170280
      320760
      340560
      380160
      740520
      760320
      780120

      None of of which are divisible by 7. So either TO or TEST is divisible by 7.

      If it is TO the only option is 35, but this is also divisible by 5, so TEST must be divisible by 7, and TO must have none of the divisors.

      Possible values for TEST (divisible by only 7) are:

      TWELVE = 340560 → TEST = 3073, TO = 31
      TWELVE = 380160 → TEST = 3073, TO = [none]

      And so we have found the required solution.

      Like

      • Jim Randell's avatar

        Jim Randell 8:11 am on 29 December 2024 Permalink | Reply

        A bit of analysis provides extra constraints that reduces the internal runtime down to a more acceptable 24ms:

        There can only be one even number (i.e. only one of T, O, E is even), and whichever of the words is even must be the one divisible by 2, 4, 6, 8, 10, 12 (and hence 3, 5, 9). These have a LCM of 360, so O cannot be the even digit, it must be one of T or E, and the digit must be 0. Hence it must be E. And T and O must be odd digits (but not 5).

        #! python3 -m enigma -rr

SubstitutedExpression

--code="check = lambda ns, ds, k: all(sum(n % d == 0 for n in ns) == k for d in ds)"

"check([TEST, TO, TWELVE], [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], 1)"

# [optional] additional constraints to speed things up:
# E is 0
--assign="E,0"
# T and O are odd digits (but not 5)
--invalid="0|2|4|5|6|8,TO"

        And further constraints can be used to get the runtime down to 0.9ms:

        #! python3 -m enigma -rr

SubstitutedExpression

--code="check = lambda ns, ds, k: all(sum(n % d == 0 for n in ns) == k for d in ds)"

"check([TEST, TO, TWELVE], [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], 1)"

# [optional] additional constraints to speed things up:
# E is 0
--assign="E,0"
# T and O are odd digits (but not 5)
--invalid="0|2|4|5|6|8,TO"

# TWELVE is divisible by: 2, 3, 4, 5, 6, 8, 9, 10, 12; LCM = 360
"TWELVE % 360 = 0"

# and TEST and TO are not
"check([TO, TEST], [2, 3, 4, 5, 6, 8, 9, 10, 12], 0)"

# which leaves 7, 11
"check([TEST, TO, TWELVE], [7, 11], 1)"

--template="(TEST TO TWELVE)"
--reorder="[2,4,3]"

        And Frits’ observation that 11 must also be a divisor of TWELVE further reduces the runtime to 0.5ms.

        Like

        • Frits's avatar

          Frits 6:06 pm on 29 December 2024 Permalink | Reply 

          from math import ceil
from itertools import product

# check if number <n> is not divisible by any of <ds>
check = lambda n, ds: all(n % d for d in ds)        

# a given number can only be completely divided by 11 if the difference of
# the sum of digits at odd position and sum of digits at even position in a 
# number is 0 or 11

# So TEST is not divisible by 11 as (S + T) - T = S and S not in {0, 11} 
# TO is not divisible by 11 as otherwise T would be equal to O
# So TWELVE must be divisible by 11

# TWELVE must be divisible by 2, 4, 6, 8, 10, 11, 12 (and hence 3, 5 and 9)
# these have a LCM of 3960 = 11 * 360

# E = 0 and both T and O are odd (see S2T2 page)

lcm = 3960
for t in range(1, 10, 2):
  # loop over divisor of TWELVE
  for k in range(ceil((t1 := 100000 * t) / lcm), (t1 + 90999) // lcm + 1):
    if ((twelve := k * lcm) // 1000) % 10 != 0: continue # check E being zero
    if len(set12 := set(str(twelve))) != 5: continue     # 4 different digits
    
    # choose 2-12 divisors  or  2-6 and 8-12 divisors
    divs = (set(range(2, 13)) - {7} if (need7 := twelve % 7 > 0) else 
             range(2, 13))
    
    # candidates for TEST 
    TESTs = [n for s in range(1, 10) if str(s) not in set12 and 
               check(n := 1001 * t + 10 * s, divs)]
    if not TESTs: continue
    
    T0 = 10 * t
    # candidates for TO 
    TOs = [n for o in range(1, 10, 2) if str(o) not in set12 and 
           check(n := T0 + o, divs)]
    
    # check combinations of TEST and TO
    for test, to in product(TESTs, TOs): 
      if (test % 100) // 10 == to % 10: continue  # S must be unequal to O
      # we need the right amount of entries divisible by 7
      if sum(z % 7 == 0 for z in [test, to]) == need7:
        print(f"answer: {test}, {to} and {twelve}")

          Like

          • Frits's avatar

            Frits 3:38 pm on 31 December 2024 Permalink | Reply

            If we know one of the values in pair (W, L) then the other value can be calculated. The same is true for the pair (T, V).
            It also reduces the domain of some of the variables T, V, W and L.

            Like

        • Frits's avatar

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

          @Jim, nice to see the improvement to the reorder parameter.

          Surprisingly using even values for V doesn’t speed things up a lot.

          Like

    • bencooperjamin's avatar

      bencooperjamin 8:09 pm on 30 December 2024 Permalink | Reply

      Jim, after selecting all the even divisors you need to add in turn the divisors of the even numbers (3/6,5/10, and then in turn 9 because 3 is a divisor of that number, giving LCM 360) so you are only left with primes 7 and 11 . We need different prime multiples above 12 to leverage these three groups into the 3 compliant numerals given.

      Like

    • GeoffR's avatar

      GeoffR 11:03 am on 31 December 2024 Permalink | Reply 

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

% Using Jim's / Frits' analysis
% E is 0 
% T and O are both odd
% Either TEST or TWELVE is divisible by 7.
% Only TWELVE is divisible by 11.
% TWELVE is divisible by 2,3,4,5,6,8,9,10,11, 12.
% TWELVE cannot be divisible by 7 as it ends in zero.
% so either TEST or TO must be divisible by 7.
% Since T an O are odd the only value for TO would be 35.
% ... but divisor 5 is catered for elsewhere.
% TEST is not divisible by 11 by the divisibility rule for 11
% as (T - E + S - T ) is not zero or divisible by 11.
% TO is not divisible by 11 as T and O are different odd digits.


var 1..9:T; var 0..9:E; var 0..9:S; var 0..9:O;
var 0..9:W; var 0..9:L; var 0..9:V;

constraint all_different([T, E, S, O, W, L, V]);

constraint E == 0 /\ T mod 2 == 1 /\ O mod 2 == 1;

% Using the rule for divisibility by 11 for TWELVE.
constraint (T - W + E - L + V - E) mod 11 == 0 
\/ (T - W + E - L + V - E) == 0;   

var 1000..9999:TEST == 1001*T + 100*E + 10*S;
var 10..99: TO == 10*T + O;
var 100000..999999: TWELVE == 100000*T + 10000*W + 1001*E + 100*L + 10*V;

% There are 9 divisors for TWELVE here
% ... the divisors 7 and 11 are tested separately
constraint sum ([TWELVE mod 2 == 0, TWELVE mod 3 == 0, TWELVE mod 4 == 0, 
TWELVE mod 5 == 0, TWELVE mod 6 == 0, TWELVE mod 8 == 0, TWELVE mod 9 == 0, 
TWELVE mod 10 == 0, TWELVE mod 12 == 0]) == 9;

% TEST cannot use the same divisors necessary for TWELVE
constraint sum ([TEST mod 2 == 0, TEST mod 3 == 0, TEST mod 4 == 0, 
TEST mod 5 == 0, TEST mod 6 == 0, TEST mod 8 == 0, TEST mod 9 == 0, 
TEST mod 10 == 0, TEST mod 11 == 0, TEST mod 12 == 0]) == 0;

% Minimun check for lower odd divisors needed as both T and O are odd digits
% and divisor 5 is used for TWELVE
constraint TO mod 3 != 0 /\ TO mod 5 != 0;

% Only TWELVE or TEST is divisible by 7.
constraint TWELVE mod 7 == 0 \/ TEST mod 7 == 0;   

solve satisfy;

output ["TEST, TO, TWELVE = " ++ show(TEST) ++ ", " ++ show(TO) ++ ", " ++ show(TWELVE) 
++ "\n" ++ "[T,E,S,O,W,L,V] = " ++ show ([T,E,S,O,W,L,V]) ];

      Like

  • Unknown's avatar

    Jim Randell 1:31 pm on 25 December 2024 Permalink | Reply
    Tags:   

    Teaser 2569: Christmas gift 

    From The Sunday Times, 18th December 2011 [link] [link]

    I sent Hank, an American friend, a Times subscription for a Christmas present. He is pleased and has responded with this numerical addition sum with a prime total in which he has consistently replaced digits by letters, with different letters for different digits.

    What is TIMES?

    [teaser2569]

     
    • Jim Randell's avatar

      Jim Randell 1:31 pm on 25 December 2024 Permalink | Reply

      A quick one for Christmas Day.

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

      It runs in 87ms. (Internal runtime of the generated code is 12.5ms).

      #! python3 -m enigma -rr

SubstitutedExpression.split_sum

"GEE + A + XMAS + TREE + GIFT = TIMES"

--extra="is_prime(TIMES)"
--answer="TIMES"

      Solution: TIMES = 12589.

      Like

    • GeoffR's avatar

      GeoffR 9:00 pm on 25 December 2024 Permalink | Reply 

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

var 1..9:G; var 1..9:A; var 1..9:X; var 1..9:T;
var 0..9:E; var 0..9:M; var 0..9:S; var 0..9:R;
var 0..9:I; var 0..9:F;

constraint all_different([G, E, A, X, T, M, S, R, I, F]);
  
predicate is_prime(var int: x) = 
x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) ((i < x) -> (x mod i > 0));
  
var 100..999:GEE == 100*G + 11*E;
var 1000..9999 : XMAS == 1000*X + 100*M + 10*A + S;
var 1000..9999 : TREE == 1000*T + 100*R + 11*E;
var 1000..9999 : GIFT == 1000*G + 100*I + 10*F + T;
var 10000..99999: TIMES == 10000*T + 1000*I + 100*M + 10*E + S;

constraint GEE + A + XMAS + TREE  + GIFT == TIMES;

constraint is_prime(TIMES);

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

% TIMES = 12589
% ----------
% ==========

      Like

    • GeoffR's avatar

      GeoffR 7:25 pm on 26 December 2024 Permalink | Reply 

      from itertools import permutations
from enigma import is_prime

# Adding columns from the right hand end being column col1
# with a carry of c1 to col2
for p1 in permutations(range(10), 4):
    E, A, S, T = p1
    if 0 in (A, T): continue
    c1, col1 = divmod((2*E + A + S + T), 10)
    if col1 != S: continue

    # Column 2
    q1 = set(range(10)).difference({E, A, S, T})
    for p2 in permutations(q1, 1):
        F = p2[0]
        c2, col2 = divmod((2*E + A + F + c1), 10)
        if col2 != E: continue

        # Column 3
        q2 = q1.difference({F})
        for p3 in permutations(q2, 4):
            G, M, R, I = p3
            if G == 0: continue
            c3, col3 = divmod((G + M + R + I + c2), 10)
            if col3 != M: continue

            # Column 4
            q3 = q1.difference({F, G, M, R, I})
            X = next(iter(q3))
            c4, col4 = divmod((X + T + G + c3), 10)
            if col4 != I: continue
            if c4 != T: continue
            
            TIMES = 10000*T + 1000*I + 100*M + 10*E + S
            if not is_prime(TIMES): continue
            print(f"TIMES = ", TIMES)

      Like

  • Unknown's avatar

    Jim Randell 7:55 am on 22 December 2024 Permalink | Reply
    Tags:   

    Teaser 3248: Miss Scarlet in the study 

    From The Sunday Times, 22nd December 2024 [link] [link]

    In Cluedo, one “room” card (from nine possible ones), one “person” card (from six) and one “weapon” card (from six) are placed in a murder bag. The remaining 18 cards are shared out (four or five per player). Players take turns to suggest the contents of the murder bag. If wrong, another player shows the suggester a card, eliminating one possibility. The first person to know the contents of the murder bag will immediately [reveal their solution and] claim victory.

    My brothers and I are playing, in the order Michael-John-Mark-Simon. After several completed rounds, we all know the murder was committed in the Study. Michael and I know the murderer was Miss Scarlet with one of four weapons. Mark and Simon know the weapon and have narrowed it down to four people. Being new to Cluedo, we don’t learn from others’ suggestions.

    From this point on, what are Michael’s chances of winning (as a fraction in its lowest terms)?

    To clarify the wording, the intention is that once a player has deduced the contents of the murder bag, they reveal their solution, and do not have to wait for their next turn.

    [teaser3248]

     
    • Jim Randell's avatar

      Jim Randell 8:12 am on 22 December 2024 Permalink | Reply

      Not learning from another players accusation means that a player may repeat an accusation that has previously been suggested (and shown to be false), but it does make working out the probabilities easier.

      Each of the players has narrowed down the scenario to one of four possibilities.

      Initially Mike has a 1/4 chance of choosing the right weapon (assuming he suggests one of his four possibilities).

      And a 3/4 chance of choosing the wrong weapon. The card shown to him must be the weapon he suggested, so he is reduced to 3 possibilities.

      And the other players proceed similarly.

      If none of them make a correct accusation, then in the next round each player is down to 3 possibilities.

      And in the following round (if any), each player is down to 2 possibilities.

      Then in the next round (if any), each player is down to 1 possibility, and so Mike (who goes first) will make a correct accusation.

      So we can calculate the probability of Mike winning each round:

      from enigma import (Rational, printf)

Q = Rational()

# each of <n> players has a <k> remaining scenarios
(n, k, r, q) = (4, 4, 0, 1)
while True:
  # p = probability of Mike winning this round
  p = Q(1, k)
  # accumulate probability of Mike winning some round
  r += q * p
  if p == 1: break
  k -= 1
  # q = probability of there being a next round
  q *= (1 - p)**n

# output solution
printf("r = {r}")

      Solution: Michael’s chances of winning are 25/64.

      Which is about 39%.

      Note: This applies if the players have to wait for their turn before making a certain accusation, which was my original interpretation of the puzzle. The intended interpretation is that players can declare a solution as soon they are certain of it, so Michael does not have to wait for his fourth turn.

      Like

      • Jim Randell's avatar

        Jim Randell 10:20 am on 23 December 2024 Permalink | Reply

        Originally I took the text “players take turns to suggest the contents of the murder bag” at face value, but the intention of the puzzle is that once a solution has been deduced with certainty it is declared without waiting for the next turn.

        In this case Michael can declare a solution after making his third round suggestion (where he has only two scenarios remaining). If his suggestion is wrong, he knows the remaining scenario is the correct one.

        We can adjust the code given above for this interpretation of the puzzle text:

          p = (Q(1, k) if k > 2 else 1)

        Solution: Michael’s chances of winning are 107/256.

        Which is about 42%.

        If he has to wait for his turn before making his certain accusation, his chances of winning are 25/64 (about 39%).

        Like

      • Frits's avatar

        Frits 12:06 pm on 23 December 2024 Permalink | Reply

        “The card shown to him must be the weapon he suggested”.

        “eliminating one possibility”. What is a possibility (one of the 9x6x6 possibilities?).

        I have never played Cluedo.

        I am considering not trying to solve recent Teasers anymore as I have felt for a couple of weeks that solving Teasers has 2 layers. The first layer being to interpret a puzzle text that seems to have been constructed to use as few words as possible instead of explaining the rules in a way that leaves no interpretation.

        Like

    • Pete Good's avatar

      Pete Good 7:21 pm on 22 December 2024 Permalink | Reply

      Jim, I followed the same thought process as you did but there is another interpretation which enables Michael to win in the third round.

      In this round, he has an equal chance of suggesting the right weapon or the wrong weapon. If he suggests the right one then nobody will show him its card so he knows that it is in the murder pack. If he suggest the wrong one then somebody will show him its card so he knows that the other weapon card is in the murder pack. Either way, he knows the contents of the murder bag and can immediately claim victory!

      I can’t see anything in the teaser wording that avoids this except that the fraction you obtain cannot be reduced to lower terms. I’d be interested to know what you think.

      Like

      • Jim Randell's avatar

        Jim Randell 11:11 pm on 22 December 2024 Permalink | Reply

        @Pete: I see what you mean.

        It depends on the exact mechanics of the gameplay. I was assuming that you can only make one accusation on your turn (“players take turns to suggest the contents of the murder bag”), and then your turn ends, so you have to wait until your next turn to make another accusation.

        But it does also say “the first person to know the contents of the murder bag will immediately claim victory”. Does that mean you can make an accusation out of turn? If so, then Mike can jump in with a correct accusation immediately after his third go without waiting for the fourth round. And his chance of winning will be a different fraction to the value I calculated.

        Looks like it is another puzzle where the wording could be clearer.

        Also, although it has been a while since I played Cluedo, I don’t think this is how play proceeds in the actual game. I recall there is an “interrogation” phase of moving around between rooms, “I suspect X in room Y with weapon Z”, and then (if possible) another player shows you a card that can disprove the suspicion (i.e. one of X, Y, Z). But later in the game you can make an accusation (during your turn), and if it is correct you win, but if it is wrong you are out of the game.

        But this doesn’t seem to be the same as the gameplay given in this puzzle.

        Like

        • Brian Gladman's avatar

          Brian Gladman 9:22 am on 23 December 2024 Permalink | Reply

          @Jim : John Owen (the teaser coordinator for the Sunday Times Teaser) has posted on this page to say that players can announce their win as soon as they know it without waiting f or their turn. This rather suggests that the third round win for Michael is the intended solution.

          Like

  • Unknown's avatar

    Jim Randell 12:08 pm on 19 December 2024 Permalink | Reply
    Tags:   

    Teaser 2601: Olympic economics 

    From The Sunday Times, 29th July 2012 [link] [link]

    George and Martha are organising a large sports meeting. Usually a gold medal (costing £36) is given to each winner, silver (£17) to each runner-up, and bronze (£11) to each third. In a minority of events, such as tennis and boxing, both losing semi-finalists get a bronze medal. However, George and Martha are going to economise by having third place play-offs in such events, thus reducing the medals needed by an odd number. George noticed that the total cost of the medals is now a four-figure palindrome, and Martha commented that the same would have been true under the previous system.

    How many events are there?

    [teaser2601]

     
    • Jim Randell's avatar

      Jim Randell 12:09 pm on 19 December 2024 Permalink | Reply

      If there are n events, under the new system each has a 1 gold, 1 silver and 1 bronze medal (assuming each event is for individual competitors). The cost of medals for each event is £36 + £17 + £11 = £64. So the total cost of medals is 64n, and we are told this is a 4-digit palindrome.

      This Python program looks for possible multiples of 64 that give a 4-digit palindrome, and then looks at adding an odd number of extra bronze medals (for less than half of the events), that also gives a 4-digit palindrome for the total cost.

      It runs in 67ms. (Internal runtime is 156µs).

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

# consider the number of events
for n in irange(1, inf):
  # total cost of medals is a 4-digit palindrome
  t = 64 * n  #  (gold + silver + bronze) per event
  if t < 1000: continue
  if t > 9999: break
  if not is_npalindrome(t): continue

  # consider an odd number of extra bronze medals
  for x in irange(1, (n - 1) // 2, step=2):
    tx = t + 11 * x
    if tx > 9999: break
    if not is_npalindrome(tx): continue

    # output solution
    printf("{n} events -> cost = {t}; +{x} bronze -> cost = {tx}")

      Solution: There are 132 events.

      So the total cost of medals under the new system is £64×132 = £8448.

      There are two situations where the cost of additional bronze medals also gives a 4-digit palindromic total cost:

      If there are 51 extra bronze medals required under the old system, then the additional cost is £11×51 = £561, and the total cost would have been £9009.

      If there are 61 extra bronze medals required, then the additional cost is £11×61 = £671, and the total cost would have been £9119.

      Like

  • Unknown's avatar

    Jim Randell 10:02 am on 17 December 2024 Permalink | Reply
    Tags:   

    Teaser 2598: Die hard 

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

    I have placed three identical standard dice in a row on a table-top, leaving just eleven faces and an odd number of spots visible. Regarding each face as a digit (with, naturally enough, the five-spotted face being the digit 5, etc.) from the front I can read a three-digit number along the vertical faces and another three-digit number along the top. Similarly, if I go behind the row I can read a three-digit number along the vertical faces and another three-digit number along the top. Of these four three-digit numbers, two are primes and two are different perfect squares.

    What are the two squares?

    [teaser2598]

     
    • Jim Randell's avatar

      Jim Randell 10:02 am on 17 December 2024 Permalink | Reply

      See also: Teaser 3130.

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

      It runs in 80ms. (Internal runtime of the generated code is 2.3ms).

      #! python3 -m enigma -rr

SubstitutedExpression

# layout (viewed from above):
#
#       I H G
#     +-------+
#   X | A B C | Y
#     +-------+
#       D E F

--digits="1-6"
--distinct="ADIX,BEH,CFGY"

# check for valid numbers
--code="check = lambda x: is_prime(x) or is_square_p(x)"

# the top can be read both ways
"check(ABC)"
"check(CBA)"

# the front and back
"D + I = 7" "E + H = 7" "F + G = 7"
"check(DEF)"
"check(GHI)"

# total number of spots is odd
"sum([A, B, C, D, E, F, G, H, I, X, Y]) % 2 = 1"

# two of the 3-digit numbers are primes, and two are (different) squares
--macro="@numbers = (ABC, CBA, DEF, GHI)"
"len(list(filter(is_prime, @numbers))) = 2"
"len(set(filter(is_square_p, @numbers))) = 2"

# possible corner configurations (right-handed dice)
--code="all_corners = lambda x, y, z, k=7: union([(x, y, z), (k - x, k - z, k - y)] for (y, z) in tuples([y, z, k - y, k - z, y], 2))"
--code="corners = union(repeat(rotate, v, 2) for v in all_corners(3, 2, 1))"  # or [[ (1, 2, 3) ]] for LH
"(A, D, X) in corners"
"(A, X, I) in corners"
"(C, Y, F) in corners"
"(C, G, Y) in corners"

--code="ans = lambda ns: call(ordered, filter(is_square_p, ns))"
--answer="ans(@numbers)"
--template="@numbers (X, Y)"
--solution=""

      Solution: The squares are 361 and 625.

      (Or this arrangement can be viewed from the back).

      From the front the top reads 361 (= 19^2) and the front reads 625 (= 25^2).

      From the back the top reads 163 (= prime) and the back reads 251 (= prime).

      With standard (right-handed) dice the left and right sides are 2 and 4, giving a total visible spot count of 37.

      The same numbers work for mirrored (left-handed) dice, but the left and right sides are 5 and 3, giving a total visible spot count of 39.

      Like

    • Frits's avatar

      Frits 2:12 pm on 17 December 2024 Permalink | Reply 

      # as we have 2 primes and 2 squares and primes and squares are mutually
# exclusive every 3-digit number must either be square or prime

# layout is:
#
#       I H G
#     +-------+
#   X | A B C | Y
#     +-------+
#       D E F

# given two dice faces anti-clockwise at a vertex, find the third
# face at this vertex (using a western die if 'same' is True)
def die_third_face(f, s, same=True):
  if s in {f, 7 - f}:
    raise ValueError
  oth = [i for i in range(1, 7) if i not in {f, s, 7 - f, 7 - s}]
  return oth[((f < s) == ((s - f) % 2)) == (same == (s + f > 7))]

dgts = "123456" 
# opposite side
opp = {str(i): str(7 - i) for i in range(1, 7)}  

# 3-digit squares
sqs = {str(i * i) for i in range(10, 32) if all(x in dgts for x in str(i * i))}
   
# determine valid 3-digit primes
prms = {3, 5, 7}
prms |= {x for x in range(11, 100, 2) if all(x % p for p in prms)}
prms = {str(i) for i in range(101, 700, 2) if all(i % p for p in prms) and
        all(x in dgts for x in str(i))}

# candidates for numbers along the top
top = sqs | prms

# front and back: DEF and IHG
fb = [(DEF, GHI[::-1]) for DEF in top if 
      (GHI := (''.join(opp[x] for x in DEF))[::-1]) in top]
        
# combine 3-digit squares which reverse are square or prime with
#         3-digit primes which reverse are square or prime
top = ({s for s in sqs if s[::-1] in top} |
       {p for p in prms if p[::-1] in top})

sols = set()
for f, b in fb:
  # mix front and back with possible top 
  for t in [t for t in top if all(t[i] not in f[i] + b[i] for i in range(3))]:
    # two are different perfect squares
    used_sqs = tuple(x for x in (f, b[::-1], t, t[::-1]) if x in sqs)
    if len(used_sqs) != 2 or len(set(used_sqs)) == 1: continue
    
    # assume a western die (counterclockwise)
    left  = str(die_third_face(int(f[0]), int(t[0])))
    right = str(die_third_face(int(t[2]), int(f[2])))
    # an odd number of spots visible
    if sum(int(x) for x in f + b + t + left + right) % 2 == 0: continue
    sols.add(used_sqs)
    
for sq1, sq2 in sols:
  print(f"answer: {sq1} and {sq2}")

      Like

  • Unknown's avatar

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

    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]

     
    • Jim Randell's avatar

      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.

      Like

  • Unknown's avatar

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

    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's avatar

      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"

      Like

    • GeoffR's avatar

      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

      Like

    • Ruud's avatar

      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")

      Like

    • GeoffR's avatar

      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
% ----------
% ==========

      Like

  • Unknown's avatar

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

    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's avatar

      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² = h² + c2²
      b² = h² + c1²
      a = b + c1

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

      a² − c2² = (a − c1)² − c1²
      c2² = 2a . c1
      ⇒
      a = c2² / (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

      Like

    • Frits's avatar

      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
'''

      Like

      • Jim Randell's avatar

        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).

        Like

        • Frits's avatar

          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).

          Like

    • Brian Gladman's avatar

      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}")

      Like

    • GeoffR's avatar

      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
% ----------
% ==========

      Like

  • Unknown's avatar

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

    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]

     
    • Jim Randell's avatar

      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…

      Like

    • ruudvanderham's avatar

      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}")

      Like

  • Unknown's avatar

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

    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]

     
    • Jim Randell's avatar

      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}")

      Like

  • Unknown's avatar

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

    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]

     
    • Jim Randell's avatar

      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

      Like

  • Unknown's avatar

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

    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]

     
    • Jim Randell's avatar

      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

      Like

      • Jim Randell's avatar

        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!

        Like

  • Unknown's avatar

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

    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]

     
    • Jim Randell's avatar

      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

      Like

    • Ruud's avatar

      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])

      Like

  • Unknown's avatar

    Jim Randell 7:08 am on 24 November 2024 Permalink | Reply
    Tags: ,   

    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's avatar

      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]

      Like

      • Rob Bellis's avatar

        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 .

        Like

        • Jim Randell's avatar

          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.

          Like

    • NigelR's avatar

      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?

      Like

    • Jim Randell's avatar

      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.

      Like

      • Brian Gladman's avatar

        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?

        Like

        • Jim Randell's avatar

          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.

          Liked by 1 person

          • Brian Gladman's avatar

            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!

            Like

      • Frits's avatar

        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])

        Like

    • Frits's avatar

      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)

      Like

  • Unknown's avatar

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

    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]

     
    • Jim Randell's avatar

      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

      Like

      • Frits's avatar

        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.

        Like

        • Jim Randell's avatar

          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.

          Like

    • Ruud's avatar

      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}")

      Like

      • Frits's avatar

        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?

        Like

        • Ruud's avatar

          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.

          Like

  • Unknown's avatar

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

    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]

     
    • Jim Randell's avatar

      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

      Like

      • Frits's avatar

        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].

        Like

    • Ruud's avatar

      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)

      Like

    • GeoffR's avatar

      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.

      Like

← Older posts

Newer posts →

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