Recent Updates Page 15 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 5:28 pm on 30 April 2024 Permalink | Reply
    Tags:   

    Teaser 2612: Star signs 

    From The Sunday Times, 14th October 2012 [link] [link]

    Five friends, Abel, Bob, Jedd, Tim and Will, were investigating birthdays. Abel commented that there was just one letter of the alphabet that occurred in both his star sign and in his month of birth.

    After further investigation he found that for any pair of his star sign, his month of birth, his name, and the day of the week on which he was born, just one letter of the alphabet occurred in both. Remarkably, the same turned out to be true for each of the friends.

    Their names are listed alphabetically. What, respectively, are their star signs?

    [teaser2612]

     
    • Jim Randell's avatar

      Jim Randell 5:29 pm on 30 April 2024 Permalink | Reply

      This is a “grouping” style problem (for which there is a solver in enigma.py), but in this case the non-primary values (i.e. signs, month, day) can be re-used, and the signs and months are not independent (i.e. a particular sign spans two consecutive months).

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

      from enigma import grouping

# names
names = "Abel Bob Jedd Tim Will".split()

# map months -> month number
months = "January February March April May June July August September October November December".split()
months = dict((x, i) for (i, x) in enumerate(months, start=1))

# map signs -> valid month numbers
signs = {
  "Aries": {3, 4},
  "Taurus": {4, 5},
  "Gemini": {5, 6},
  "Cancer": {6, 7},
  "Leo": {7, 8},
  "Virgo": {8, 9},
  "Libra": {9, 10},
  "Scorpio": {10, 11},
  "Sagittarius": {11, 12},
  "Capricorn": {12, 1},
  "Aquarius": {1, 2},
  "Pisces": {2, 3},
}

# days
days = "Monday Tuesday Wednesday Thursday Friday Saturday Sunday".split()

# check a (<name>, <sign>, <month>, <day>) group
def check(n, s, m, d, fn=grouping.share_letters(1)):
  # sign/month should match, as well as the shared letters
  return (months[m] in signs[s]) and fn(n, s, m, d)

# find candidate groups (allowing repeated values)
grouping.solve([names, signs.keys(), months.keys(), days], check, distinct=0)

      Solution: The star signs are: Pisces, Virgo, Leo, Virgo, Leo.

      The full solution is:

      Abel: Pisces, March, Sunday
      Bob: Virgo, September, Monday
      Jedd: Leo, July, Monday
      Tim: Virgo, August, Monday
      Will: Leo, July, Wednesday

      Like

    • Ruud's avatar

      Ruud 4:14 am on 2 May 2024 Permalink | Reply

      Here’s my solution:

      import itertools


def day_month_to_zodiac(day, month):
    signs = [
        ("capricorn", 19),
        ("aquarius", 18),
        ("pisces", 20),
        ("aries", 19),
        ("taurus", 20),
        ("gemini", 20),
        ("cancer", 22),
        ("leo", 22),
        ("virgo", 22),
        ("libra", 22),
        ("scorpio", 21),
        ("sagittarius", 21),
        ("capricorn",),
    ]
    return signs[month - (day <= signs[month - 1][1])][0]


month_names = "x january febuary march april may june july august september october november december".split()

weekday_names = "monday tuesday wednesday thursday friday saturday sunday".split()

for first_name in "abel bob jedd tim will".split():
    for month, weekday_name in itertools.product(range(1, 13), weekday_names):
        month_name = month_names[month]
        for zodiac_name in (day_month_to_zodiac(1, month), day_month_to_zodiac(31, month)):
            if all(len(set(c0) & set(c1)) == 1 for c0, c1 in itertools.combinations((first_name, month_name, zodiac_name, weekday_name), 2)):
                print(first_name, zodiac_name, month_name, weekday_name)

      Like

    • Frits's avatar

      Frits 11:24 am on 2 May 2024 Permalink | Reply 

       
first_names = "abel bob jedd tim will".split()

zodiac_names = "capricorn aquarius pisces aries taurus gemini cancer " \
               "leo virgo libra scorpio sagittarius".split()

month_names = "january febuary march april may june july august " \
              "september october november december".split()

weekday_names = "monday tuesday wednesday thursday " \
                "friday saturday sunday".split()

# does sequence <x> share exactly one item with all sequences in <g>
share1 = lambda x, g: all(len(set(x).intersection(z)) == 1 for z in g)

sols = []
for m, mo in enumerate(month_names, start=1):
  for zo in (zodiac_names[m - 1], zodiac_names[m % 12]):
    if not share1(zo, [mo]): continue
    for wd in weekday_names:
      if not share1(wd, [mo, zo]): continue
      for nm in first_names:
        if not share1(nm, [mo, zo, wd]): continue
        sols.append((nm, zo))

print(', '.join(x[1] for x in sorted(sols)))

      Like

  • Unknown's avatar

    Jim Randell 4:37 pm on 26 April 2024 Permalink | Reply
    Tags:   

    Teaser 3214: Squaring the square 

    From The Sunday Times, 28th April 2024 [link] [link]

    Clark took a sheet of A4 paper (8.27 × 11.69 inches) and cut out a large square with dimensions a whole number of inches. He cut this into an odd number of smaller squares, each with dimensions a whole number of inches. These were of several different sizes and there was a different number of squares of each size; in fact, the number of different sizes was the largest possible, given the above.

    It turns out that there is more than one way that the above dissection can be made, but Clark chose the method that gave the smallest number of smaller squares.

    How many smaller squares were there?

    [teaser3214]

     
    • Jim Randell's avatar

      Jim Randell 5:55 pm on 26 April 2024 Permalink | Reply

      The largest (integral sized) square that can cut from a sheet of A4 is 8 inches × 8 inches. And in order to get multiple different sizes of smaller square we need at least a 3 × 3 square.

      I am assuming that when the puzzle refers to “more than one way that the dissection can be made”, it means there are multiple different possible sets of smaller squares. (Not the same set just assembled in a different way to form the larger square).

      By using the [[ express() ]] function from the enigma.py library to find candidate dissections, and the rectpack.py library to fit the smaller squares into the larger square, I was able to quickly write a program that runs in a reasonable time.

      However, the rectpack.py library wasn’t designed to handle multiple rectangles of the same shape, and was not as efficient as it could be in this case. So I have updated it to cope better with this situation, and the program now runs even faster.

      The following Python program runs in 95ms. (Internal runtime is 28ms).

      Run: [ @replit ]

      from enigma import (Accumulator, irange, express, multiset, seq_all_different, group, item, printf)
import rectpack

# can we pack the squares?
def pack(n, ms):
  rs = list((x, x) for x in ms.elements())
  for ps in rectpack.pack(n, n, rs):
    return ps  # a single packing will do

# find the largest number of different sizes of smaller square [at least 3]
acc = Accumulator(fn=max, value=3, collect=1)

# consider the size of the larger square
for n in irange(8, 3, step=-1):

  # consider the areas of smaller squares
  ss = list(irange(1, n - 1))

  # decompose n^2 into smaller squares
  for qs in express(n * n, (i * i for i in ss)):
    # there was an odd number of smaller squares
    if sum(qs) % 2 != 1: continue
    # and there were "several" sizes
    k = len(qs) - qs.count(0)
    if k < acc.value: continue
    ms = multiset.from_pairs(zip(ss, qs))
    # and a different number of each size
    if not seq_all_different(ms.values()): continue
    # attempt to pack the squares
    ps = pack(n, ms)
    if ps:
      # record (<size of large square>, <number of smaller squares>, <packing>)
      acc.accumulate_data(k, (n, ms.size(), ps))

if acc.data:
  printf("{acc.value} different sizes of smaller squares")

  # consider possible sizes of larger square
  g = group(acc.data, by=item(0))
  for (k, vs) in g.items():
    # we need multiple ways to dissect the square
    if len(vs) < 2: continue
    printf("{k} x {k} square -> {n} dissections", n=len(vs))
    # find the minimal number of smaller squares
    sm = min(s for (n, s, ps) in vs)
    printf("min {sm} smaller squares")
    for (n, s, ps) in vs:
      if s == sm:
        rectpack.output_grid(n, n, ps, end="--")

      Solution: There were 13 smaller squares.

      The maximum number of different sizes of smaller squares is 4. It is possible to dissect 5×5, 6×6, 7×7, 8×8 using 3 different sizes of smaller squares, but only 8×8 can be dissected into 4 different sizes. So this must be the size of square chosen by Clark.

      An 8×8 square can be dissected into 5 different sets of smaller squares of 4 different sizes, and the smallest of these uses 13 smaller squares.

      A minimal dissection is shown below:

      1 @ 4×4 square [red]
      3 @ 3×3 squares [orange]
      4 @ 2×2 squares [green]
      5 @ 1×1 squares [blue]
      = 13 smaller squares

      Had the puzzle allowed Clark to start with a 9×9 square this can also be dissected into 4 different sizes of smaller squares (but not 5), and so this would give a further answer to the puzzle:

      A 9×9 square can be dissected into 23 different sets of smaller squares of 4 different size, and the smallest of these uses 15 smaller squares.

      The program can be used to investigate extensions to the puzzle for squares up to 12 × 12, after which it gets a bit bogged down.

      Like

    • Frits's avatar

      Frits 5:40 pm on 27 April 2024 Permalink | Reply

      Using SubstitutedExpression to fit pieces into a grid.
      The programs runs in 1.25 seconds (8 or 9 times longer than my similar Python-only program on Brian’s site).

      from enigma import SubstitutedExpression

symbols = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
symbols += "ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖØÙÚÛÜÝÞßàáâãäåæçèéêëìíîïð"

# "these were of several different sizes" (let's say more than three)
min_sizes = 4

# decompose <t> into <k> numbers from <ns> so that sum(<k> numbers) equals <t>
def decompose(t, k=1, ns=[], s=[], mn=min_sizes):
  if k == 1:
    if t in ns and t >= s[-1]:
      s_ = s + [t]
      cnts = [s_.count(x) for x in set(s_)]
      # there was a different number of squares of each size
      if len(cnts) >= mn and len(cnts) == len(set(cnts)):
        yield (s_, cnts)
  else:
    for n in ns:
      if k * n > t: break
      if s and n < s[-1]: continue   # sequence is non-decreasing
      yield from decompose(t - n,  k - 1, ns, s + [n])
 
sqs = [i * i for i in range(1, 9)]

# determine sum of <min_sizes> lowest squares
mand = sum(x * x for x in range(1, min_sizes + 1))

max_diff_sizes = 0
sols = []
# process sizes of the large square (at least 5x5)
for sq in sqs[::-1][:-4]:
  X = int(sq**.5)            # width and height of the large square
  sqs_ = [x for x in sqs if x < sq]
  max_pieces = sq - mand
  # start with a high number of pieces
  for np in range(max_pieces - (max_pieces % 2 == 0), 3, -2):
    # break if triangular root of <np> get's too low
    if int(0.5 * ((8 * np + 1)**.5 - 1.0)) < max_diff_sizes: break
    
    # make total <sq> from small squares
    for p, cnts in decompose(sq, np, sqs_):
      # ignore entries with too few different sizes
      if (ln := len(cnts)) >= max_diff_sizes:
        pieces = [int(x**.5) for x in p[::-1]]
        topleft = [symbols[2 * i:2 * i + 2] for i in range(np)]
        sizes = [symbols[2 * np + i] for i in range(np)]
        s2d = dict(zip(sizes, pieces))
       
        answer = ', '.join(str('(({' + x[0] + '}, {' + x[1] + '}), \
                 {' + sizes[i] + '})') \
                 for i, x in enumerate(topleft) if s2d[sizes[i]] > 1)
        answer = f"{answer}"

        # invalid digit / symbol assignments
        d2i = {i: set() for i in range(len(pieces))}
        for i, p in enumerate(pieces):
          # make sure we don't cross the boundaries
          for d in range(X - p + 1, 10):
            vs = set()
            vs.update(topleft[i][0])
            vs.update(topleft[i][1])
            d2i[d] |= vs

        placed = [(topleft[0], sizes[0])]
        # build expressions
        exprs = []
        for i in range(1, np):
          piece = symbols[2 * i:2 * i + 2]
          sz = sizes[i]
          if s2d[sz] == 1: break  # pieces of dimensions 1 always fit
          for tl, s in placed:
            # squares may not overlap
            exprs.append(f"({{{tl[0]}}} + {{{s}}} <= {{{piece[0]}}} or "
                         f"{{{piece[0]}}} <= {{{tl[0]}}} - {{{sz}}}) or "
                         f"({{{tl[1]}}} + {{{s}}} <= {{{piece[1]}}} or "
                         f"{{{piece[1]}}} <= {{{tl[1]}}} - {{{sz}}})")             
          placed.append((piece, sz))  
      
        #for e in exprs: print(e); 
        #print()

        # the alphametic puzzle
        p = SubstitutedExpression(
          exprs,
          base=X,
          answer=answer,
          d2i=d2i,
          s2d=s2d,
          distinct="",
          verbose=0,    # use 256 to see the generated code
        )

        # print answers
        for ans in p.answers():
          if ln > max_diff_sizes:
            sols = []
          # store data, count of smallest piece first
          sols.append((pieces.count(min(pieces)), np, pieces))
          break # we need only one solution
          
        max_diff_sizes = len(cnts)          

if len(sols) < 2:
  print("no multiple dissections have been found")
else: 
  # print the solution with the the smallest number of smaller squares
  for n_smallest, m, pieces in sorted(sols):
    print("answer:", m, "\n")
    print("pieces:", *[(x, x) for x in pieces], "\n")
    break

      Like

      • Jim Randell's avatar

        Jim Randell 10:45 am on 3 May 2024 Permalink | Reply

        @Frits: An inventive use of the [[ SubstitutedExpression ]] solver.

        But I think the puzzle is asking for a dissection that uses the minimum number of pieces in total, rather than a dissection that has the minimum number of smallest pieces. (Although it turns out these are the same for the given constraints).

        Like

        • Frits's avatar

          Frits 8:24 pm on 3 May 2024 Permalink | Reply

          Yes, I got confused with the phrase “smallest number of smaller squares”.

          I also have a Python only version that first performs the express calls for all “n” using the Boecker-Liptak Money Changing [https://enigmaticcode.wordpress.com/2020/09/21/enigma-946-patterns-of-fruit/#comment-9773] and then reorders this list on the number of different pieces and number of pieces before packing.

          The A1 format (n=23) can be done in 165 seconds:

          29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 28 28 28 28 28 28 27 27
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 28 28 28 28 28 28 27 27
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 28 28 28 28 28 28 26 26
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 28 28 28 28 28 28 26 26
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 28 28 28 28 28 28 25 25
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 28 28 28 28 28 28 25 25
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 24 24 24 24 24 23 23 23
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 24 24 24 24 24 23 23 23
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 24 24 24 24 24 23 23 23
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 24 24 24 24 24 22 22 22
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 24 24 24 24 24 22 22 22
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 21 21 21 20 19 22 22 22
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 21 21 21 18 18 18 18 18
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 21 21 21 18 18 18 18 18
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 17 17 17 18 18 18 18 18
16 16 16 16 16 16 15 15 15 15 14 14 14 14 13 17 17 17 18 18 18 18 18
16 16 16 16 16 16 15 15 15 15 14 14 14 14 12 17 17 17 18 18 18 18 18
16 16 16 16 16 16 15 15 15 15 14 14 14 14 11 11 11 11 11 11 10 10 10
16 16 16 16 16 16 15 15 15 15 14 14 14 14 11 11 11 11 11 11 10 10 10
16 16 16 16 16 16  9  9  9  9  8  8  8  8 11 11 11 11 11 11 10 10 10
16 16 16 16 16 16  9  9  9  9  8  8  8  8 11 11 11 11 11 11  7  7  7
 6  6  5  5  4  3  9  9  9  9  8  8  8  8 11 11 11 11 11 11  7  7  7
 6  6  5  5  2  1  9  9  9  9  8  8  8  8 11 11 11 11 11 11  7  7  7

          There are combinations of pieces that are hard to for the pack routine.

          Like

  • Unknown's avatar

    Jim Randell 10:01 pm on 24 April 2024 Permalink | Reply
    Tags:   

    Teaser 1849: Losing a daughter 

    From The Sunday Times, 22nd February 1998 [link]

    “I’ll be pleased to get rid of her!”, exclaimed George, as he and Martha worked out the seating plan for the wedding of their youngest daughter. The 50 guests were to be seated at seven tables (numbered 1 to 7), each table seating at least six but not more than eight. Alter long arguments as to who should be avoiding whom, they came up with a plan. “That’s strange”, commented Martha. “If you take the number at each table and multiply it by the table number and then add the seven products, you get a perfect square — highly inappropriate when all the tables are round!”. George rang the caterer, who was familiar with the details, and told him about this “square” property as well as the number of people to be seated on table 7. “Then the same number of people will be at table 1″, said the caterer”. “Yes”, confirmed George.

    How many were to be seated on table 6?

    [teaser1849]

     
    • Jim Randell's avatar

      Jim Randell 10:02 pm on 24 April 2024 Permalink | Reply

      This Python program generates all possible arrangements with the “square” property.

      And then looks for those which would allow the caterer to deduce the number of guests at table 1, having been told the number of guests at table 7. We then examine the cases where these numbers are equal.

      The program runs in 53ms. (Internal runtime is 1.5ms).

      Run: [ @replit ]

      from enigma import (decompose, is_square, filter_unique, item, map2str, printf)

# generate possible configurations with the "square" property
def generate():
  # distribute the 50 guests among the 7 tables
  for ns in decompose(50, 7, increasing=0, sep=0, min_v=6, max_v=8):
    # map table numbers to the number of guests seated
    m = dict(enumerate(ns, start=1))
    # check the "square" property
    if is_square(sum(i * n for (i, n) in m.items())):
      yield m

# knowing the number at table 7 the caterer deduces the number at table 1
for m in filter_unique(generate(), item(7), item(1)).unique:
  # is it the same number?
  if m[1] == m[7]:
    # output solution
    printf("m[6]={m[6]} [m={s}]", s=map2str(m))

      Solution: 6 guests were to be seated at table 6.

      There are three possible arrangements (table number = number of guests):

      (T1=8, T2=8, T3=6, T4=8, T5=6, T6=6, T7=8)
      (T1=8, T2=7, T3=8, T4=7, T5=6, T6=6, T7=8)
      (T1=8, T2=8, T3=7, T4=6, T5=7, T6=6, T7=8)

      In each case the “square” property gives a value of 196 (= 14²).

      Like

      • ruudvanderham's avatar

        ruudvanderham 11:25 am on 25 April 2024 Permalink | Reply

        Here’s my (brute force) solution:

        import itertools
import math
import collections

number_at_table1_per_number_at_table7 = collections.defaultdict(set)
number_at_table6_per_number_at_table7 = collections.defaultdict(set)

for number_at_table in itertools.product((6, 7, 8), repeat=7):
    if sum(number_at_table) == 50:
        total = sum(i * n for i, n in enumerate(number_at_table, 1))
        if math.sqrt(total) % 1 == 0:
            number_at_table1_per_number_at_table7[number_at_table[6]].add(number_at_table[0])
            number_at_table6_per_number_at_table7[number_at_table[6]].add(number_at_table[5])

for i in number_at_table1_per_number_at_table7:
    if len(number_at_table1_per_number_at_table7[i]) == 1:  # unique!
        print(number_at_table6_per_number_at_table7[i])

        Like

    • Frits's avatar

      Frits 2:18 pm on 25 April 2024 Permalink | Reply

      Allowing for more than one solution.

      sign = lambda x: -1 if x < 0 else x > 0
# return a list of items grouped by element <by>
grpby = lambda s, by: [[x for x in s if x[by] == v] 
                       for v in set(x[by] for x in s)]    

# decompose number <t> into <k> numbers from <ns> times -1, 0 or 1 so that 
# sum(<k> numbers) equals <t> and with the count of positive numbers 
# one higher than the count of negative numbers
def decompose2(t, k, ns, s=[], delta=0):
  if k == 1:
    if abs(t) in ns or t == 0:
      if delta + sign(t) == 1:
        yield s + [t]
  else:
    for m in [-1, 0, 1]:
      n_ = m * ns[0] 
      # can we get to delta = 1 in k - 1 moves
      if abs(delta + m - 1) <= k - 1:
        yield from decompose2(t - n_, k - 1, ns[1:], s + [n_], delta + m)

# 7 * tri(7) = 14^2 and 14^2 is the only feasible square.
# if we substract 7 from the number of guests per table we have a list of
# -1, 0 and 1. Making sure all these -1/0/1 items sum to zero we end up with
# square 14^2 and having one more postive than negative number guarantees
# 50 people at 7 tables.

# group by table 7
for g in grpby(list(decompose2(0, 7, range(1, 8))), -1):
  # group by table 1
  if len(g2 := grpby(g, 0)) != 1: continue
  print("answer:", ' or '.join(set(str(7 + sign(x[-2])) for x in g2[0])))

      Like

    • GeoffR's avatar

      GeoffR 6:15 pm on 25 April 2024 Permalink | Reply 

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

% Guests seated at each of the seven tables
var 6..8:T1; var 6..8:T2; var 6..8:T3; var 6..8:T4;
var 6..8:T5; var 6..8:T6; var 6..8:T7; 

% Same number of guests on Tables 1 and 7
constraint T1 == T7;

% There are 50 guests seated at the seven tables
constraint T1 + T2 + T3 + T4 + T5 + T6 + T7 == 50;
constraint T1 + 2*T2 + 3*T3 + 4*T4 + 5*T5 + 6*T6 + 7*T7 == tables_total;

% LB and UB of tables total 
% LB of  tables total = 6 * (1+2+3+4+5+6+7) = 6 * 28 = 168
% UB of  tables total = 8 * (1+2+3+4+5+6+7) = 8 * 28 = 224
var 168..224:tables_total;

% Only squares between 168 and 224 are 13^2 (169) and 14^2 (196)
constraint tables_total == 13 * 13 \/ tables_total == 14*14;

solve satisfy;
output["[T1, T2, T3, T4, T5, T6, T7] = " ++ show( [T1, T2, T3, T4, T5, T6, T7] )
++ ", Tables total = " ++ show (tables_total )];  

% [T1, T2, T3, T4, T5, T6, T7] = [8, 8, 7, 6, 7, 6, 8], Tables total = 196 - Soln 1
% ----------
% [T1, T2, T3, T4, T5, T6, T7] = [7, 8, 8, 6, 8, 6, 7], Tables total = 196 - Soln 2
% ----------
% [T1, T2, T3, T4, T5, T6, T7] = [6, 8, 8, 8, 8, 6, 6], Tables total = 196 - Soln 3
% ----------
% [T1, T2, T3, T4, T5, T6, T7] = [7, 8, 8, 7, 6, 7, 7], Tables total = 196 - Soln 4
% ----------
% ==========

      As shown, this program gave four potential solutions, which need some manual filtering, as this facilty does not seem available in MiniZinc.
      Of the four solutions output, the 2nd and 4th solutions can be discounted, as they have different values for Table No. 6.
      The 1st and 3rd solutions have equal numbers of guests on Tables 1 and 7, albeit different, but the same number of 6 guests on Table 6.
      Therefore, number of guests on Table 6 = 6.

      Like

  • Unknown's avatar

    Jim Randell 4:41 pm on 19 April 2024 Permalink | Reply
    Tags:   

    Teaser 3213: A streetcar named divisor 

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

    In retrospect it was inadvisable to ask an overenthusiastic mathematician to overhaul our local tram routes. They allocated a positive whole number less than 50 to each district’s tram stop. To find the number of the tram going from one district to another you would “simply” (their word, not mine) find the largest prime divisor of the difference between the two districts’ numbers; if this was at least 5 it was the unique route number, and if not there was no direct route.

    The routes, each in increasing order of the stop numbers, were:

    Atworth, Bratton, Codford;
    Atworth, Downlands, Enford;
    Bratton, Figheldean, Enford;
    Downlands, Figheldean, Codford;
    Codford, Enford.

    What were the route numbers, in the order quoted above?

    [teaser3213]

     
    • Jim Randell's avatar

      Jim Randell 5:35 pm on 19 April 2024 Permalink | Reply

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

      This run file executes in 228ms. (Internal runtime of the generated program is 147ms).

      Run: [ @replit ]

      #! python3 -m enigma -rr

SubstitutedExpression

--code="""
# largest prime factor (n > 0)
primes.expand(50)
@cache
def lpf(n):
  fs = list(primes.prime_factor(n))
  if not fs: return 0
  r = fs[-1][0]
  return (0 if r < 5 else r)

# route number between 2 districts
route = lambda x, y: lpf(abs(x - y))
"""

--base=50
--digits="1-49"
--distinct="ABCDEF,VWXYZ"

# route V: A < B < C
"A < B" "B < C"
"route(A, B) = V"
"route(B, C) = V"
"route(C, A) = V"

# route W: A < D < E
"A < D" "D < E"
"route(A, D) = W"
"route(D, E) = W"
"route(E, A) = W"

# route X: B < F < E
"B < F" "F < E"
"route(B, F) = X"
"route(F, E) = X"
"route(E, B) = X"

# route Y: D < F < C
"D < F" "F < C"
"route(D, F) = Y"
"route(F, C) = Y"
"route(C, D) = Y"

# route Z: C < E
"C < E"
"route(C, E) = Z"

# no routes between A - F, B - D
"not route(A, F)"
"not route(B, D)"

--answer="(V, W, X, Y, Z)"
--template=""

      Solution: The route numbers are: 5, 11, 13, 7, 19.

      And the numbers of the tram stops are:

      A = x + 1
      B = x + 6
      C = x + 26
      D = x + 12
      E = x + 45
      F = x + 19
      x = 0 .. 4

      Adding a constant value to each of the stop numbers does not change the differences between them, but x must be between 0 and 4 for all stop numbers to lie in the range 1 .. 49.

      In the program above, if we fix the value A=1 (with: [[ --assign="A,1" ]], we bring the runtime down to 93ms. (11.3ms internal).

      Like

      • Frits's avatar

        Frits 6:31 pm on 19 April 2024 Permalink | Reply

        @Jim, “They allocated a positive whole number less than 50 to each district’s tram stop.”. For some reason you seem to disregard tram stops 1-4 (that’s why I have five solutions). Could you explain why?

        Like

        • Jim Randell's avatar

          Jim Randell 6:40 pm on 19 April 2024 Permalink | Reply

          @Frits: In an earlier version of my code I disallowed stops 1-4, then I realised that we are looking for prime factors of the difference that are 5 or more.

          But there is only one answer to the puzzle (although there are multiple numberings of the stops).

          Like

      • Frits's avatar

        Frits 11:16 pm on 19 April 2024 Permalink | Reply

        I also started with SubstitutedExpression to get a quick solution but decided to publish something with a little analysis.

        # primes in range 1 - 48
P = [3, 5]
P = [x for x in range(47, 10, -2) if all(x % p for p in P)] + [7, 5]

# largest prime divisor of the difference between the two numbers
def check(a, b):
  diff = b - a
  for p in P:
    if diff % p == 0:
      return p

sols = set()
# order: A, (B|D), F, C, E
#          5  1  7  11 13

# E is the stop with the highest number with minimum 5+1+7+11+13  
for E in range(38, 50):
  for C in range(25, E):
    if not (r5 := check(C, E)): continue
    for F in range(14, C): 
      if not (r4 := check(F, C)) or r4 == r5: continue
      if not (r3 := check(F, E)): continue
      if r3 in {r4, r5}: continue
      for D in range(6, F): 
        if check(D, F) != r4: continue
        if not (r2 := check(D, E)): continue
        if r2 in {r3, r4, r5}: continue
        for B in range(6, F): 
          if check(B, F) != r3 or B == D: continue
          if not (r1 := check(B, C)): continue
          if r1 in {r2, r3, r4, r5}: continue
          for A in range(1, min(B, D)): 
            if check(A, D) != r2: continue
            if check(A, B) != r1: continue
            sols.add((r1, r2, r3, r4, r5))

print("answer", *sols)

        Like

      • Frits's avatar

        Frits 11:40 pm on 19 April 2024 Permalink | Reply

        “and if not there was no direct route”. This probably suggests to check the routes A – F and B – D for primary divisors. I didn’t use it as it is not explicitly specified that a tram route must exist if a direct route is possible.

        Like

        • Jim Randell's avatar

          Jim Randell 10:20 am on 20 April 2024 Permalink | Reply

          @Frits: I interpreted this as an “if any only if” condition.

          For every pair of stop numbers, if the calculation give an LPF ≥ 5, then this is the route number that the stops are both on. If it does not, then that pair are not on the same route.

          It would be simple to add the check to your program.

          Like

      • Frits's avatar

        Frits 11:13 am on 20 April 2024 Permalink | Reply

        With the implicit “if any only if” condition.

        # primes in range 1 - 48
P = [3, 5]
P = [x for x in range(47, 10, -2) if all(x % p for p in P)] + [7, 5]

# largest prime divisor of a difference
def check(diff):
  for p in P:
    if diff % p == 0:
      return p
  return 0   # faster then implicitly returning None

# build dictionary of largest prime divisors for differences
d = {diff: check(diff) for diff in range(1, 49)}

# order: A, (B|D), F, C, E
#          5  1  7  11 13

sols = set()
# E is the stop with the highest number with minimum 1+5+1+7+11+13  
for E in range(minE := 2 + sum(P[-4:]), 50):
  for C in range(minE - P[-4], E - 4):
    if not (r5 := d[E - C]): continue
    for F in range(minE - P[-4] - P[-3], C - 4): 
      if not (r4 := d[C - F]) or r4 == r5: continue
      if not (r3 := d[E - F]): continue
      if r3 in {r4, r5}: continue
      for D in range(1 + P[-1], F - 4): 
        if d[F - D] != r4: continue
        if not (r2 := d[E - D]): continue
        if r2 in {r3, r4, r5}: continue
        for B in range(1 + P[-1], F - 4): 
          if d[F - B] != r3 or B == D: continue
          if not (r1 := d[C - B]): continue
          if r1 in {r2, r3, r4, r5}: continue
          for A in range(1, min(B, D) - 4): 
            if d[D - A] != r2: continue
            if d[B - A] != r1: continue
            # no route Atworth - Figheldean nor Bratton - Downlands
            if d[F - A] == d[D - B] == 0:       
              sols.add((r1, r2, r3, r4, r5))
             
print("answer:", *sols)

        Like

    • Jim Randell's avatar

      Jim Randell 1:00 pm on 20 April 2024 Permalink | Reply

      Here is a Python solution with an internal runtime of <1ms.

      A is the smallest stop number, so we can assume A=1, as adding the same constant value to each stop number will not change the differences. We can generate further solutions that give the same answer by incrementing the stop numbers until the largest stop number (E) reaches 49.

      Run: [ @replit ]

      from enigma import (irange, primes, cache, printf)

# largest prime factor (n > 0)
primes.expand(50)
@cache
def lpf(n):
  fs = list(primes.prime_factor(n))
  if not fs: return 0
  r = fs[-1][0]
  return (0 if r < 5 else r)
# route number between 2 districts
route = lambda x, y: lpf(abs(x - y))

# A is the smallest stop number, so assume A=1
A = 1
for B in irange(A + 5, 34):
  r1 = route(A, B)
  if not r1: continue
  for C in irange(B + 5, 44):
    if route(B, C) != r1 or route(A, C) != r1: continue
    for E in irange(C + 5, 49):
      (r2, r3, r5) = (route(A, E), route(B, E), route(C, E))
      if not (r2 and r3 and r5): continue
      rs = {r1, r2, r3, r5}
      if len(rs) != 4: continue
      for F in irange(B + 5, C - 5):
        if route(B, F) != r3 or route(E, F) != r3 or route(A, F): continue
        r4 = route(C, F)
        if (not r4) or r4 in rs: continue
        for D in irange(A + 5, F - 5):
          if route(A, D) != r2 or route(D, E) != r2 or route(D, F) != r4 or route(C, D) != r4 or route(B, D): continue
          # output solution
          printf("routes = {r1} {r2} {r3} {r4} {r5} [A={A} B={B} C={C} D={D} E={E} F={F}]")

      Like

      • Frits's avatar

        Frits 2:45 pm on 20 April 2024 Permalink | Reply

        @Jim, a smart idea. I wonder if assuming E=49 is more optimal.
        You can also start C from B + 12 (as F is between B and C).

        Like

    • Frits's avatar

      Frits 1:03 pm on 20 April 2024 Permalink | Reply

      My first program in the Julia language.

      # primes in range 1 - 48
P = [3, 5]
P = [x for x in 47:-2:10 if all(x % p > 0 for p in P)] 
push!(P, 7, 5)

# largest prime divisor of a difference
function check(diff)
  for p in P
    if diff % p == 0
      return p
    end  
  end    
  return 0   
end

# build dictionary of largest prime divisors for differences
d = Dict(diff => check(diff) for diff in 1:49)

sols = Set()
# E is the stop with the highest number with minimum 1+5+1+7+11+13  

minE = 2 + sum(P[end - 3:end])
for E in minE:49
  for C in minE - P[end - 3]:E - 5
    r5 = d[E - C]
    if r5 == 0
      continue
    end
    
    for F in minE - P[end-3] - P[end-2]:C - 5 
      r4 = d[C - F]
      if r4 == 0 || r4 == r5 
        continue
      end  
      r3 = d[E - F]
      if r3 == 0 || r3 in Set([r4, r5])
        continue
      end  

     for D in 1 + P[end]:F - 5 
        if d[F - D] != r4 
          continue
        end  
        r2 = d[E - D]
        if r2 == 0 || r2 in Set([r3, r4, r5])
	  continue
        end  

        for B in 1 + P[end]:F - 5
          if d[F - B] != r3 || B == D
            continue
          end  
          r1 = d[C - B]
          if r1 == 0 || r1 in Set([r2, r3, r4, r5])
            continue
          end  
          
          for A in 1: min(B, D) - 5 
            if d[D - A] != r2 || d[B - A] != r1
              continue
            end  
            # no route Atworth - Figheldean nor Bratton - Downlands
            if d[F - A] == d[D - B] == 0   
              #println("E = ", E, " C = ", C, " F = ", F, " D = ",  D,
              #        " B = ", B, " A = ", A)
              push!(sols, (r1, r2, r3, r4, r5))
            end  
          end
        end
      end
    end          
  end
end

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

      Like

      • Jim Randell's avatar

        Jim Randell 11:01 am on 30 April 2024 Permalink | Reply

        What did you think of Julia? I briefly dabbled with it 10 years ago. (I think the only remnant of that is here [ link ]). But I decided to stick with Python.

        Like

        • Frits's avatar

          Frits 8:21 pm on 30 April 2024 Permalink | Reply

          I prefer the syntax of Python (without the “if end”). Not using the word “range” doesn’t make the code easy to read for me (I have to scan for a “:”). I don’t know all the features in Julia (like if assignment statements are possible). Comprehensions and dictionaries seem to work fine.

          I am mainly disappointed in the external run time of Julia programs. I would only use it again if we have a tough problem where a Python program runs longer than 30 minutes. Even then it is doubtful if it will be quicker than CPython or PyPy.

          Like

    • Frits's avatar

      Frits 1:23 pm on 22 April 2024 Permalink | Reply

      Adding E = 49 and negative step loops.

      Internal run time is approx 100 microseconds.

      # primes in range 1 - 48
P = [3, 5]
P = [x for x in range(47, 10, -2) if all(x % p for p in P)] + [7, 5]

# largest prime divisor of a difference
def check(diff):
  for p in P:
    if diff % p == 0:
      return p

# build dictionary of largest prime divisors for differences
d = {diff: check(diff) for diff in range(1, 49)}

# order: A, (B|D), F, C, E
#          5  1  7  11 13

# since all route numbers depend on differences between
# stop numbers, we can set E equal to 49
E = 49
sols = set()
for F in range(2 + sum(P[-2:]), E - sum(P[-2:]) + 1): 
  if not (r3 := d[E - F]): continue
  for B in range(F - r3, 1 + P[-1], -r3): 
    if not (d[F - B] == r3): continue
    for C in range(F + P[-1], E - P[-1] + 1): 
      if not (r4 := d[C - F]) or r4 == r3: continue
      if not (r1 := d[C - B]) or r1 in {r3, r4}: continue
      if not (r5 := d[E - C]) or r5 in {r1, r3, r4}: continue
      for D in range(F - r4, 1 + P[-1], -r4): 
        if not (d[F - D] == r4): continue
        if not (r2 := d[E - D]) or r2 in {r1, r3, r4, r5}: continue

        mx, step = B - r1 if B < D else D - r2, -r1 if B < D else -r2
        for A in range(mx, 0, step): 
          if not (d[B - A] == r1): continue
          if not (d[D - A] == r2): continue
          # infeasible routes
          if d[abs(B - D)]: continue
          if d[F - A]: continue
          sols.add((r1, r2, r3, r4, r5))
              
print("answer:", *sols)

      Like

    • Frits's avatar

      Frits 8:53 pm on 25 April 2024 Permalink | Reply

      Another program but now based on differences/multiples.

      # multiples diagram
#
# +----------mA_C---------+           r1, prime p1 <= (48 - 5) / 2
# +-mA_B-+                |           r1
#        B                |
#        +-mB_F---+-----mF_E------+   r3, prime p3 <= (48 - 5) / 2
# +--mA_D--+---------mD_E---------+   r2, prime p2 <= 48 / 2
# A   -    D  -   F   -   C   -   E  
#                 +-mF_C--+       |   r4, prime p4 <= (48 - 5 - 7) / 2 
#          +----mD_C------+       |   r4           
#                         +-mC_E--+   r5, prime p5 <= 48 - 2*5 - 7 - 1

for mD_E, p2 in [(m, p) for p in [5, 7, 11, 13, 17, 19, 23] 
                 for m in range(1, 7) if 17 <= m * p <= 42 and
                                         (m + 1) * p <= 48]:
  for p4 in [5, 7, 11, 13, 17]:
    if p4 == p2: continue
    for mC_E in range(1, 6 if 5 not in {p2, p4} else 5):
      # p5 >= 5
      for mD_C in range(2, (mD_E * p2 - 5 * mC_E) // p4 + 1):
        p5, r = divmod(mD_E * p2 - mD_C * p4, mC_E)
        if r or p5 not in {5, 7, 11, 13, 17, 19, 23, 29} or p5 in {p2, p4}:
          continue
        # (mA_D + mD_E) * p2 <= 48  
        for mA_D in range(1, (48 // p2) - mD_E + 1):
          # p1 >= 5
          for mA_C in range(2, (mA_D * p2 + mD_C * p4) // 5 + 1):
            p1, r = divmod(mD_C * p4 + mA_D * p2, mA_C)
            if r or p1 not in {5, 7, 11, 13, 17, 19} or p1 in {p2, p4, p5}:
              continue
            for mF_C in range(1, mD_C):
              # p3 >= 5
              for mF_E in range(1, (mF_C * p4 + mC_E * p5) // 5 + 1):
                p3, r = divmod(mF_C * p4 + mC_E * p5, mF_E)
                if r or p3 not in {5, 7, 11, 13, 17, 19} or \
                  p3 in {p1, p2, p4, p5}: continue
                for mB_F in range(1, 4):
                  mA_B, r = divmod((mD_E + mA_D) * p2 - (mB_F + mF_E) * p3, p1)
                  if r or mA_B not in {1, 2, 3}: continue
                  if not (mA_B < mA_C): continue
                  print("answer:", (p1, p2, p3, p4, p5))

      Like

  • Unknown's avatar

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

    Teaser 2607: Tribonacci 

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

    In the Fibonacci sequence 1, 2, 3, 5, 8, 13, … each number after the second is the sum of the previous two. Pat has experimented with some “Tribonacci” sequences of positive whole numbers where each number after the third is the sum of the previous three.

    He chooses the first three numbers to be different and in increasing order and then generates the sequence. He has shown us one where just the first five numbers are less than a hundred and where a later number is ten thousand.

    What are the first three numbers in this sequence?

    [teaser2607]

     
    • Jim Randell's avatar

      Jim Randell 10:10 am on 17 April 2024 Permalink | Reply

      If the first 3 terms are a, b, c (where a < b < c) then the first 5 terms are:

      a, b, c, a+b+c, a+2b+2c, …

      And so the fifth term of the sequence must be at least:

      a + 2(a + 1) + 2(a + 2) = 5a + 6
      a + 2b + 2(b + 1) = a + 4b + 2

      We can use these to reduce the search space for the (a, b, c) values.

      This Python program runs in 78ms. (Internal runtime is 12ms).

      Run: [ @replit ]

      from enigma import (irange, fib, first, le, printf)

# suppose the sequence starts (a, b, c, a+b+c, a+2b+2c, ...)
# and these terms are all < 100
for a in irange(1, 97):
  if not (5*a + 6 < 100): break
  for b in irange(a + 1, 98):
    if not (a + 4*b + 2 < 100): break
    for c in irange(b + 1, 99):
      if not (a + 2*b + 2*c) < 100: break
      if 2*a + 3*b + 4*c < 100: continue

      # calculate terms up to 10_000
      ss = first(fib(a, b, c), le(10000))

      # is the final term 10_000?
      if ss[-1] == 10000:
        # output solution sequence
        printf("{ss}")

      Solution: The first three numbers in the sequence are: 6, 11, 24.

      The terms of the sequence up to 10,000 are:

      [6, 11, 24, 41, 76, 141, 258, 475, 874, 1607, 2956, 5437, 10000]

      Like

      • Frits's avatar

        Frits 3:17 pm on 17 April 2024 Permalink | Reply

        “just the first five numbers are less than a hundred” :

        sixth term: 2a + 3b + 4c > 99

        Like

        • Jim Randell's avatar

          Jim Randell 3:29 pm on 17 April 2024 Permalink | Reply

          Good point. I’ve added a check in my program to ensure the 6th term is at least 100.

          Like

      • Frits's avatar

        Frits 8:30 pm on 17 April 2024 Permalink | Reply

        I wanted to start from the back of the sequence. It has been a lot of work.
        This might be automated with the sympy or z3 packages (or with Enigma’s Matrix.linear_solve).

        from math import ceil

# round
r = lambda n, k=0: int(round(n, k)) if k == 0 else round(n, k)
 
# suppose the sequence ends like the following list
s = [
  "18*y+27*z-200000", "-20*y-2*z+70000", "7*y-13*z+50000", "5*y+12*z-80000",
  "-8*y-3*z+40000",   "4*y-4*z+10000",   "y+5*z-30000",    "-3*y-2*z+20000",   
  "2*y-z",            "2*z-10000",       "-y-z+10000",     "y", "z", "10000"]

# the sequence must be increasing:

# 7*y-13*z+50K < 5*y+12*z-80K,   2*y < 25*z-130K,     y < 12.5*z - 65K
# 5*y+12*z-80K < -8*y-3*z+40K,   13y < -15*z + 120K,  y < -15/13*z + 120K/13
# -8*y-3*z+40K <  4*y-4*z+10K,   12y > z + 30K        y > z/12 + 2500
#  4*y-4*z+10K < y+5*z-30K   ,   3*y < 9*z - 40K      y < 3*z - 40K/3 
#  y+5*z-30K   < -3*y-2*z+20K,   4*y < -7*z + 50K     y < -7/4*z + 12500
# -3*y-2*z+20K < 2*y-z       ,   5*y > -z + 20K       y > -z/5 + 4K
# 2*y-z        < 2*z-10K     ,                        y < 1.5*z - 5K 


# determine minimum for <z>
# y < 12.5*z - 65K, z > y / 12.5 + 5200 and y > -z/5 + 4K 
# z > -z / 62.5 + 5520,  63.5/62.5*z > 5520, z > 5433.07 

# determine maximum for <z>
# 15/13*z < -y + 120K/13 and y > -z/5 + 4K 
# 15*z < 13*(z/5 - 4K) + 120K, z < 68K / 12.4 = 5483.87

# maximum looks too high (knowing the answer) so:

# 15/13*z < -y + 120K/13 and y > z/12 + 2500
# 15*z < -13*(z/12 + 2500) + 120K, z < 12 * 87500 / 193 = 5440.41

for z in range(5434, 5441):
  # determine boundaries for <y>
  mx = min(1.5*z - 5000, 12.5*z - 65000, -15/13*z + 120000/13, 
           3*z - 40000/3, -7/4*z + 12500)
  mn = max(z / 12 + 2500, -z/5 + 4000)
  for y in range(int(mn) + 1, ceil(mx)):
    # calculate the sequence numbers
    ns = [eval(x) for x in s]  
    # determine the 5 numbers below 100
    b100 = [n for n in ns if n < 100]  
    if len(b100) < 5: continue
    f5 = b100[-5:]
    
    # five numbers must be increasing and without a valid previous number
    if sorted(f5) == f5 and f5[0] > 0 and \
       not (0 < f5[2] - f5[1] - f5[0] < f5[0]):
      print("answer:", f5[:3], "\n")
      # print the sequence
      for i, x in enumerate(s):
        print(f"{i + 1:>2}  {x:<20} {ns[i]:<10}")

        Like

      • ruudvanderham's avatar

        ruudvanderham 8:18 am on 18 April 2024 Permalink | Reply

        Instead of a very clever, fast algorithm, here’s a super simple -brute force- solution without any reasoning beforehand.

        import itertools

for i1, i2, i3 in itertools.combinations(range(1, 100), 3):
    n_min2 = i1 + i2 + i3
    n_min1 = i2 + i3 + n_min2
    if n_min2 < 100 and n_min1 < 100:
        n = i3 + n_min2 + n_min1
        while n < 10000:
            n_min2, n_min1, n = n_min1, n, n_min2 + n_min1 + n
        if n == 10000:
            print(i1, i2, i3)

        Like

      • Jim Randell's avatar

        Jim Randell 11:39 am on 18 April 2024 Permalink | Reply

        Here is a different approach, that I didn’t think would be very fast, but it turns out it has an internal runtime of 11ms. (Although it does stop when it finds the first solution).

        It works by generating the coefficients of (a, b, c) in each term, i.e.

        term 1 = 1a + 0b + 0c → (1, 0, 0)
        term 2 = 0a + 1b + 0c → (0, 1, 0)
        term 3 = 0a + 0b + 1c → (0, 0, 1)
        term 4 = 1a + 1b + 1c → (1, 1, 1)
        term 5 = 1a + 2b + 2c → (1, 2, 2)
        term 6 = 2a + 3b + 4c → (2, 3, 4)
        …

        And then, when we reach sufficiently large terms, it looks for (a, b, c) values between 1 and 99 that would give the term a value of 10000. If an acceptable set of values is found we construct the sequence of terms up to 10000 and check the remaining conditions.

        Run: [ @replit ]

        from enigma import (unzip, express, fib, first, dot, printf)

# solve the puzzle, by looking for a term = N
def solve(N=10000):
  # a, b, c coefficients for terms 1, 2, 3
  ts = [(1, 0, 0), (0, 1, 0), (0, 0, 1)]
  k = 3
  # find the coefficients in the k'th term
  while True:
    k += 1
    cs = tuple(sum(ss) for ss in unzip(ts))
    if k > 5 and not (dot(cs, [97, 98, 99]) < N):
      # is the k'th term is N
      for (a, b, c) in express(N, cs, min_q=1, max_q=99):
        if not (a < b < c): continue
        # calculate the first k terms
        ss = first(fib(a, b, c), k)
        # check 5th term < 100 and 6th term >= 100
        if ss[4] < 100 and not (ss[5] < 100):
          yield ss
    # move on to the next term
    ts.pop(0)
    ts.append(cs)

for ss in solve():
  printf("{ss}")
  break

        A custom version of express() that only generates quantities in ascending order would probably make this code even faster.

        Like

      • Frits's avatar

        Frits 5:58 pm on 18 April 2024 Permalink | Reply

        Mix of Jim’s and Ruud’s code.

        # 5a + 6 < 100
for a in range(1, 19):
  # a + 4 * b + 2 < 100
  for b in range(a + 1, (101 - a) // 4):
    # a + 2b + 2c < 100 and not all odd
    # sixth term 2 * a + 3 * b + 4 * c > 99
    mn = max(b + 1, (103 - 2 * a - 3 * b) // 4)
    mxplus1 = (101 - a - 2 * b) // 2
    for c in range(mn, mxplus1, 1 + (a % 2 and b % 2)):
      n_min2 = a + b + c
      n_min1 = a + 2 * b + 2 * c
      n = c + n_min2 + n_min1
      while n < 10000:
        n_min2, n_min1, n = n_min1, n, n_min2 + n_min1 + n
      if n == 10000:
        print("answer:", a, b, c)

        Like

    • Hugo's avatar

      Hugo 11:03 am on 17 April 2024 Permalink | Reply

      I solved this rather differently.
      In a Fibonacci sequence, the ratio of successive terms tends to the positive root of the equation
      x^2 = x + 1. Here it tends to the real root of x^3 = x^2 + x + 1: x = 1.839 287 approx.

      I divided 10000 by that number twice, taking the nearest integer each time.
      The method may lead to incorrect values when they become small,
      but I continued with the relationship T(n) = T(n + 3) – T(n + 2) – T(n + 1)
      for successively smaller n and got the required answer.

      Like

    • GeoffR's avatar

      GeoffR 10:54 am on 18 April 2024 Permalink | Reply

      Not a rigorous solution – I had to use the fact that the answer is the 13th term, in order to get a solution in MiniZinc. 

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

% First three terms of the series
var 1..100: a; var 1..100: b; var 1..100: c;

% Knowing the answer is the 13th term of the Tribonacci series...
int:T13 == 10000;

constraint a < b /\ b < c;

% The algebraic value of the 13th term of the series
constraint 149 * a + 230 * b + 274 * c == T13;

solve satisfy;

output ["First three numbers are " ++ show([a, b, c]) ];

% First three numbers are [6, 11, 24]
% ----------
% ==========

      Like

    • Frits's avatar

      Frits 2:06 pm on 18 April 2024 Permalink | Reply

      An implementation with the z3 solver (of my previous program).

      Downside is that I had to fix the sequence length to 13. I tried to loop over sequence lengths but for some reason the program got really slow after one or 2 runs.

        
from z3 import Solver, Int, simplify, sat

s = Solver()

M = 13 # length of final sequence

# variables
y, z = Int('y'), Int('z')

# start from the back of the sequence
a, b, c = "y", "z", "10000"

seq = [a, b, c]
eqs = ["y < z", "z < 10000"]
# add <M - 3> previous numbers
for _ in range(M - 3):
  a, b, c = c + " - (" + a + ") - (" + b + ")", a, b, 
  # simplify and prettify the new equation
  a_ = str(eval(f"simplify({a})"))
  seq = [a_.replace("+ -", "-").replace("-", "- ").replace(" 1*", " ")] + seq
  eval(f"s.add({a} < {b})")

# first sequence number must be positive (otherwise y = 2957 is a solution)
eval(f"s.add({seq[0]} > 0)")

# run z3 solver
if(s.check() == sat):
  m = s.model()
  # convert y and z to integers
  y = int(str(m[y]))
  z = int(str(m[z]))
  
  # calculate the sequence numbers
  ns = [eval(x) for x in seq]
  
  # determine the 5 numbers below 100
  b100 = [n for n in ns if n < 100]  
  if len(b100) >= 5: 
    f5 = b100[-5:]

    # five numbers must be increasing
    if sorted(f5) == f5 and f5[0] > 0:
      print("answer:", f5[:3], "\n")
      # print the sequence
      for i, x in enumerate(seq):
        print(f"{i + 1:>2}  {x:<22} {ns[i]:<10}")

      Like

  • Unknown's avatar

    Jim Randell 4:40 pm on 12 April 2024 Permalink | Reply
    Tags:   

    Teaser 3212: Changes at Chequers 

    From The Sunday Times, 14th April 2024 [link] [link]

    I started with a six-by-six grid with a 0 or 1 in each of its 36 squares: they were placed in chequerboard style with odd rows 101010 and even rows 010101. Then I swapped over two of the digits that were vertically adjacent. Then in three places I swapped a pair of horizontally adjacent digits.

    In the resulting grid I read each of the six rows as a binary number (sometimes with leading zeros) and I found that three of them were primes and the other three were the product of two different primes.

    The six numbers were all different and were in decreasing order from the top row to the bottom.

    What (in decimal form) were the six decreasing numbers?

    [teaser3212]

     
    • Jim Randell's avatar

      Jim Randell 5:23 pm on 12 April 2024 Permalink | Reply

      This Python program considers all possible sequences of swaps. It is not very quick (it runs in 4.1s, although if we disallow overlapping horizontal swaps things are quicker), but I’ll have another look later:

      from enigma import (
  irange, subsets, update, chunk, nconcat, is_decreasing,
  factor, intersect, printf
)

# primes and products of 2 different primes
(primes, factor2) = (set(), set())
for n in irange(1, 63):
  fs = factor(n)
  if len(fs) == 1:
    primes.add(n)
  elif len(fs) == 2 and len(set(fs)) == 2:
    factor2.add(n)

# initial grid
parity = lambda i: sum(divmod(i, 6)) % 2
grid = list(parity(i) ^ 1 for i in irange(0, 35))

# vertical swap (i, i + 6)
vert = list(irange(0, 29))

# horizontal swap (i, i + 1)
hori = list(i for i in irange(0, 35) if i % 6 != 5)

# check for solutions with swaps <vs> + <hs>
def check(vs, hs, g=grid):
  # perform vertical swaps, then horizontal swaps
  for (js, dj) in [(vs, 6), (hs, 1)]:
    for j in js:
      k = j + dj
      g = update(g, [j, k], [g[k], g[j]])

  # extract the numbers
  ns = list(nconcat(row, base=2) for row in chunk(g, 6))

  # check they are decreasing
  if not is_decreasing(ns, strict=1): return

  # check for primes and products of different primes
  ps = sorted(intersect([ns, primes]))
  fs = sorted(intersect([ns, factor2]))
  if len(ps) != 3 or len(fs) != 3: return

  # output solution
  printf("V{vs} + H{hs} -> {ns} [primes={ps} factor2={fs}]", hs=list(hs))

# choose 1 vertical and 3 horizontal (all different)
for hs in subsets(hori, size=3, select='P'):
  for v in vert:
    check([v], hs)

      Solution: The six decimal rows are: 41, 37, 34, 29, 26, 21.

      Manually we can use the same steps that my final program uses:

      We see there are only the following options for vertical, horizontal and unchanged rows:

      vertical (odd, even) = (58, 5) (46, 17) (34, 29)
      vertical (even, odd) = (53, 10)

      horizontal (odd) = (41) (38) (26)
      horizontal (even) = (37) (22) (19) (13)

      unchanged (odd) = <none>
      unchanged (even) = (21)

      The only possible unchanged row is 21, and the only vertical swap this can partner with is (34, 29).

      So we have: (34 (odd), 29 (even)) + (21 (even)), and have to fit 3 horizontal swaps in.

      The only odd horizontal swap that can fit between these two swaps is (26), giving us: (34, 29) + (26) + (21).

      And we then need to fit an odd and an even horizontal swap before this sequence.

      The only options are:

      (41) + (37) + (34, 29) + (26) + (21)
      (38) + (37) + (34, 29) + (26) + (21)

      and only the first of these consists of 3 primes and 3 semi-primes.

      (This is also the 3000th comment on the site).

      Like

      • Jim Randell's avatar

        Jim Randell 9:58 pm on 12 April 2024 Permalink | Reply

        We can get a faster program with a bit of analysis:

        Each row starts with 3 bits set.

        The vertical swap changes the two rows it modifies from (3, 3) bits set to (2, 4) bits set.

        And the remaining 4 unchanged rows are 2 copies each of:

        “101010” = 42 = 2×3×7
        “010101” = 21 = 3×7

        42 is neither a prime, nor a product of 2 primes, so both of those remaining rows must be changed, hence 2 of the horizontal swaps must change the remaining 42 rows. And these swaps are independent of each other.

        Together these swaps account for 4 of the rows in the grid, and the remaining 2 rows are both initially 21, so one of them must have the third horizontal swap in it, hence all horizontal swaps are independent, and the vertical swap must change 2 rows that are not changed by horizontal swaps, so that exactly 5 of the 6 rows are changed.

        Here is my program restructured to take this analysis into account. (Although I think it might be even faster to calculate the values of the rows with each swap and ensure the appropriate distribution is maintained).

        The following Python program runs in 173ms.

        from enigma import (
  irange, floor, diff, cproduct, factor, update, chunk,
  nconcat, is_decreasing, intersect, printf
)

# primes and products of 2 different primes
(primes, factor2) = (set(), set())
for n in irange(1, 63):
  fs = factor(n)
  if len(fs) == 1:
    primes.add(n)
  elif len(fs) == 2 and len(set(fs)) == 2:
    factor2.add(n)

# initial grid
parity = lambda i: sum(divmod(i, 6)) % 2
grid = list(parity(i) ^ 1 for i in irange(0, 35))

# check for solutions with swaps <vs> + <hs>
def check(vs, hs, g=grid):
  # perform vertical swaps, then horizontal swaps
  for (js, dj) in [(vs, 6), (hs, 1)]:
    for j in js:
      k = j + dj
      g = update(g, [j, k], [g[k], g[j]])

  # extract the numbers
  ns = list(nconcat(row, base=2) for row in chunk(g, 6))

  # check they are decreasing
  if not is_decreasing(ns, strict=1): return

  # check for primes and products of different primes
  ps = sorted(intersect([ns, primes]))
  fs = sorted(intersect([ns, factor2]))
  if len(ps) != 3 or len(fs) != 3: return

  # output solution
  printf("V{vs} + H{hs} -> {ns} [primes={ps} factor2={fs}]", hs=sorted(hs))

# the initial 42 and 21 rows
r42 = [0, 12, 24]
r21 = [6, 18, 30]

# choose the vertical swap (v, v + 6)
for v in irange(0, 29):
  # choose 2 horizontal swaps from the remaining 42 rows
  rv = floor(v, 6)
  rs = diff(r42, {rv, rv + 6})
  for (h1, h2) in cproduct(irange(x, x + 5) for x in rs):
    # and the remaining horizontal swap
    for rh in diff(r21, {rv, rv + 6}):
      for h3 in irange(rh, rh + 4):
        check([v], [h1, h2, h3])

        Like

        • Frits's avatar

          Frits 11:08 am on 13 April 2024 Permalink | Reply

          @Jim, a technical thing. Performing direct updates on a grid copy is in this case more efficient (shaving 20% off the runtime). I had a similar result when I reduced the number of deep copies in my program (waiting to be updated on Brian’s site).

          Like

      • Jim Randell's avatar

        Jim Randell 11:39 am on 13 April 2024 Permalink | Reply

        And here is a much faster version, that keeps track of the conditions as we go along.

        It has an internal runtime of 781µs.

        from enigma import (primes, irange, append, nconcat, printf)

# primes and products of 2 different primes
ps = set(primes.between(2, 63))
f2s = set()
for p in primes.between(2, 7):
  f2s.update(p * q for q in primes.between(p + 1, 63 // p))

# initial grid
parity = lambda i: sum(divmod(i, 6)) % 2
grid = list(parity(i) ^ 1 for i in irange(0, 35))

# value of a row
row = lambda g, i: nconcat(g[i:i + 6], base=2)

# return a new grid with values at <i> and <j> swapped
def swap(g, i, j):
  g = list(g)
  (g[i], g[j]) = (g[j], g[i])
  return g

# solve the puzzle on grid g, row i
# vs = values to incorporate
# v, h, u = remaining vertical swaps, horizontal swaps, unaltered rows
# ns = list of numbers so far
# np, nf = count of (prime, factor2) so far
def solve(g, vs=list(), i=0, v=1, h=3, u=1, ns=list(), np=0, nf=0):

  # incorporate any given values
  for n in vs:
    # check increasing
    if ns and not (ns[-1] > n): return
    ns = append(ns, n)
    # check factors
    if n in ps:
      if np > 2: return
      np += 1
    elif n in f2s:
      if nf > 2: return
      nf += 1
    else:
      return

  # are we done?
  if v == h == u == 0:
    if np == 3 and nf == 3:
      yield ns
  else:
    # can we leave this row unaltered?
    if u > 0:
      n = row(g, i)
      yield from solve(g, [n], i + 6, v, h, u - 1, ns, np, nf)
    # can we do a horizontal swap? (j, j + 1)
    if h > 0:
      for j in irange(i, i + 4):
        # update the grid, and calculate the row value
        g_ = swap(g, j, j + 1)
        n = row(g_, i)
        yield from solve(g_, [n], i + 6, v, h - 1, u, ns, np, nf)
    # can we do a vertical swap? (j, j + 6)
    if v > 0 and i < 30:
      for j in irange(i, i + 5):
        # update the grid, and calculate the row values
        g_ = swap(g, j, j + 6)
        (n1, n2) = (row(g_, i), row(g_, i + 6))
        yield from solve(g_, [n1, n2], i + 12, v - 1, h, u, ns, np, nf)

# solve the puzzle
for ns in solve(grid):
  printf("{ns}")

        Like

      • Jim Randell's avatar

        Jim Randell 6:34 pm on 14 April 2024 Permalink | Reply

        And this version is even faster. As there are only two different starting rows, this program builds up possible values for vertical, horizontal and unchanged rows, and then combines them into an appropriate order.

        It has an internal run time of 581µs.

        from enigma import (primes, irange, nconcat, update, subsets, join, printf)

# primes and products of 2 different primes
ps = set(primes.between(2, 63))
f2s = set()
for p in primes.between(2, 7):
  f2s.update(p * q for q in primes.between(p + 1, 63 // p))

# value of a row
row = lambda bs: nconcat(bs, base=2)

# check a sequence, return (num prime, num factor2)
def check(ns):
  np = nf = 0
  for (i, n) in enumerate(ns):
    # check decreasing
    if i > 0 and not (ns[i - 1] > n): return
    # check factors
    if n in ps:
      if np > 2: return
      np += 1
    elif n in f2s:
      if nf > 2: return
      nf += 1
    else:
      return
  return (np, nf)

# odd rows and even rows
(odd, even) = ([1, 0, 1, 0, 1, 0], [0, 1, 0, 1, 0, 1])

# perform a vertical swap
def vertical(r1, r2):
  for i in irange(6):
    ns = [row(update(r1, [i], [r2[i]])), row(update(r2, [i], [r1[i]]))]
    # check conditions
    if check(ns):
      yield ns

# perform a horizontal swap
def horizontal(r):
  for i in irange(5):
    ns = [row(update(r, [i, i + 1], [r[i + 1], r[i]]))]
    if check(ns):
      yield ns

# unchanged rows
def unchanged(r):
  ns = [row(r)]
  if check(ns):
    yield ns

swaps = {
  # vertical swaps on an odd/even and even/odd row
  'v': [list(vertical(odd, even)), list(vertical(even, odd))],
  # horizontal swaps on an odd and even row
  'h': [sorted(horizontal(odd), reverse=1), sorted(horizontal(even), reverse=1)],
  # unchanged values for odd and even rows
  'u': [list(unchanged(odd)), list(unchanged(even))],
}

# find possible values from the specified swap pattern
def assemble(ss, ns=[]):
  for xs in swaps[ss[0]][len(ns) % 2]:
    ns_ = ns + xs
    cs = check(ns_)
    if cs:
      # are we done?
      if len(ss) == 1:
        if cs == (3, 3):
          yield ns_
      else:
        # fill out the remaining rows
        yield from assemble(ss[1:], ns_)

# now assemble the swaps (1 vertical, 3 horizontal, 1 unchanged)
for ss in subsets('vhhhu', size=len, select='mP'):
  for ns in assemble(ss):
    printf("{ss} -> {ns}", ss=join(ss))

        Like

  • Unknown's avatar

    Jim Randell 10:09 pm on 9 April 2024 Permalink | Reply
    Tags:   

    Brainteaser 1341: Hexadecipal 

    From The Sunday Times, 15th May 1988 [link]

    Vicky Naylor gets up my nose! One day she was required to convert a hex number (i.e. one in base 16) to its decimal equivalent. But she can’t tell her hex from her decs and she thought the whole number had to be reversed. So, doing it her way, she merely reversed the hex number’s digits.

    But, lo and behold, Vicky’s method gave the correct decimal equivalent in this particular instance. Apart from the single digit numbers there are only a handful of numbers with this property, and Vicky had found the largest of them all.

    What was the decimal form of the number?

    [teaser1341]

     
    • Jim Randell's avatar

      Jim Randell 10:10 pm on 9 April 2024 Permalink | Reply

      We could just consider k-digit sequences of digits 0-9 such that the value of the sequence interpreted as a number in hexadecimal is the same as the value of the reversed sequence interpreted as a number in decimal.

      And this gives us a straightforward program (using Python’s builtin conversions to base 10 and base 16), that runs in 261ms. (And an internal runtime of 198ms).

      Run: [ @replit ]

      from enigma import (irange, rev, printf)

for n in irange(10, 99999):
  h = hex(n)[2:]
  if rev(h) == str(n):
    printf("{h} [hex] = {n} [dec]")

      But if we consider a sequence of digits abc…z, where abc… is a k-digit sequence, then we have:

      as_hex(abc…z) = as_dec(z…cba)
      ⇒
      16 as_hex(abc…) + z = z 10^k + as_dec(…cba)
      ⇒
      z = [16 as_hex(abc…) − as_dec(…cba)] / (10^k − 1)

      So we can consider k-digit prefix sequences to see if we get a viable z value, and construct a (k + 1)-digit sequence. This allows us to reduce the number of candidate values tested to 1/10 of the previous approach.

      This Python program runs in 116ms. (Internal runtime is 50ms).

      Run: [ @replit ]

      from enigma import (irange, inf, ndigits, nsplit, nconcat, rev, div, printf)

# consider (k + 1) digit numbers
for k in irange(1, inf):
  # number of dec digits in smallest k-digit hex
  if ndigits(16**k) > k + 1: break

  # consider k leading digits 0-9
  for n in irange(10**(k - 1), 10**k - 1):
    ds = nsplit(n, k)
    # calculate the final digit
    r = nconcat(rev(ds), base=10)
    z = div(nconcat(ds, base=16) * 16 - r, 10**k - 1)
    if z is None or not (0 < z < 10): continue
    # output solution
    printf("{n}{z} [hex] = {z}{r} [dec]")

      Solution: The largest such number is 99481 (decimal).

      Excluding single digit sequences, we have:

      35 [hex] = 53 [dec]
      173 [hex] = 371 [dec]
      1415 [hex] = 5141 [dec]
      18499 [hex] = 99481 [dec]

      Like

    • GeoffR's avatar

      GeoffR 2:46 pm on 10 April 2024 Permalink | Reply 

      from itertools import product

# 2-digit reversible Hex/Dec numbers
for A in range(1, 10):
  for B in range(1, 10):
    if 16*A + B == 10*B + A:
      print(f"Decimal format is {10*B + A}")  

# 3-digit reversible Hex/Dec numbers
for C, D, E in product(range(1, 10),repeat=3):
  if 16**2*C + 16*D + E == 100*E + 10*D + C:
    print(f"Decimal format is {100*E  + 10*D + C}") 
                
# 4-digit reversible Hex/Dec numbers
for F, G, H, J in product(range(1, 10),repeat=4):
  if 16**3*F + 16**2*G + 16*H + J == 1000*J + 100*H + 10*G + F:
     print(f"Decimal format is {1000*J + 100*H  + 10*G + F}") 

# 5-digit reversible Hex/Dec numbers
for K, M, N, P, Q in product(range(1, 10),repeat=5):
  if 16**4*K + 16**3*M + 16**2*N + 16*P + Q == \
    10000*Q + 1000*P + 100*N + 10*M + K:
    print(f"Decimal format is {10000*Q + 1000*P + 100*N  + 10*M + K}")
    
# Decimal format is 53
# Decimal format is 371
# Decimal format is 5141
# Decimal format is 99481

      Like

      • Jim Randell's avatar

        Jim Randell 11:11 am on 12 April 2024 Permalink | Reply

        @GeoffR: Your program finds solutions providing they don’t include the digit 0.

        Like

    • Frits's avatar

      Frits 12:48 pm on 12 April 2024 Permalink | Reply

      Designed to be efficient for listing all solutions instead of the largest.
      I am not sure if this program also would have worked if higher powers than k=5 would have qualified.

      from itertools import product

# suitable powers of 16
pw = {k + 1: k16 for k in range(1, 10) if len(str(k16 := 16**k)) == k + 1}

# from large to small
for k in sorted(pw.keys(), reverse=True):  
  m = k // 2
  # divide a k-digit number in a left part and a right part 
  for L in range(10**m - 1, 10**(m - 1) - 1, -1):
    p = L * 10**(k - m)      # make it a k-digit number  (e.g. xx000)              
    if p < pw[k]: break      # don't allow for a trailing zero
   
    t, lst = 0, []
    # calculate valid trailing digits 
    for x in range(m):
      # divide <p> by the highest appropriate power of 16
      L1 = p // pw[k - x]
      # maintain hexadecimal total
      t += L1 * pw[k - x]
      
      # allow for one (L1) or two digits (L1, L1 + 1)
      lst.append((L1, (L1 + 1) % 16) if (t + pw[k - x]) // 10**(k - m) == L
                  else (L1, ))
      # remainder            
      p -= L1 * pw[k]
      
    
    # check whether L.R is a solution 
    for p in product(*lst):
      R = ''.join(str(x) for x in p[::-1])
      # combine left and right (with a potential center digit)
      chk = [int(str(L) + R)] if k % 2 == 0 else \
            [int(str(L) + str(c) + R) for c in range(10)] 
      
      # reversed hexadecimal number equals the decimal form of the number?
      for n in chk: 
        if hex(n)[2:][::-1] == str(n):
          print("answer:", n)
          # break   # Vicky had found the largest of them all

      Like

    • GeoffR's avatar

      GeoffR 1:50 pm on 12 April 2024 Permalink | Reply 

      # Version 2
from itertools import product

# Decimal numbers cannot have hex digits A,B,C,D,E or F
# Also, decimal numbers cannot start with zero
# 2-digit reversible Hex/Dec numbers
for A in range(10):
  for B in range(10):
    if B == 0:continue
    if 16*A + B == 10*B + A:
      print(f"Decimal format is {10*B + A}")  
 
# 3-digit reversible Hex/Dec numbers
for C, D, E in product(range(10),repeat=3):
  if E == 0:continue
  if 16**2*C + 16*D + E == 100*E + 10*D + C:
    print(f"Decimal format is {100*E  + 10*D + C}") 
                 
# 4-digit reversible Hex/Dec numbers
for F, G, H, J in product(range(10),repeat=4):
  if J == 0:continue
  if 16**3*F + 16**2*G + 16*H + J == 1000*J + 100*H + 10*G + F:
    print(f"Decimal format is {1000*J + 100*H  + 10*G + F}") 
 
# 5-digit reversible Hex/Dec numbers
for K, M, N, P, Q in product(range(10),repeat=5):
  if Q == 0:continue
  if 16**4*K + 16**3*M + 16**2*N + 16*P + Q == \
     10000*Q + 1000*P + 100*N + 10*M + M:
    print(f"Decimal format is {10000*Q + 1000*P + 100*N  + 10*M + K}")
    # includes largest number found

      Like

  • Unknown's avatar

    Jim Randell 10:04 am on 7 April 2024 Permalink | Reply
    Tags:   

    Brain-Teaser 157: Veres and Ficts 

    From The Sunday Times, 12th April 1964 [link]

    Since 1945, when the Veres (who always tell the truth) entered the country of the Ficts (who always lie), there has been a certain amount of intermarriage. So the country now contains four races: The Verifics (children of a Vere father and Fict mother), who first tell the truth and then lie; the Fivers (children of a Fict father and a Vere mother), who first lie and then tell the truth; the Veres (born of two Vere parents) who are always truthful; and the Ficts (born of two Fict parents), who are always untruthful.

    I met four children, one of each race, who told me some interesting things about their sixteen-year-old prince:

    Alan: “The prince is a Fict. My mother is a sister of the Prince’s cook”.
    Bruce: “The Prince’s father is of the same race as Orsino. The Prince’s tutor is Carl’s grandfather”.
    Carl: The Prince is of the same race as I am. I am a Verific”.
    David: “Orsino is the Prince’s tutor. The Prince’s cook is not of the same race as the Prince’s father”.

    What is the race of each child? And what is the race of the Prince?

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

    [teaser157]

     
    • Jim Randell's avatar

      Jim Randell 10:05 am on 7 April 2024 Permalink | Reply

      We are only told about offspring of V and F parents, so I assume there is only one generation that may have mixed parentage. (And this makes the father() and mother() functions idempotent).

      This Python program assigned the four tribes to A, B, C, D and then looks for possible tribes for the Prince, Orsino, the cook and the tutor, and the values of the three free propositions in the children’s statements, and then checks that the truth values of the statements match the assigned tribes.

      (The program assumes VF and FV’s alternate truths and falsehoods, although each statement we are given consists of exactly two clauses, so we don’t need to worry about the extended case).

      It runs in 94ms. (Internal runtime is 29ms).

      Run: [ @replit ]

      from enigma import (subsets, printf)

# V - always tells the truth
def V(ss): return all(ss)

# F - always tells untruths
def F(ss): return not any(ss)

alternate= lambda X, Y, ss: X(ss[0::2]) and Y(ss[1::2])

# VF - alternate true then false
def VF(ss): return alternate(V, F, ss)

# FV - alternate false then true
def FV(ss): return alternate(F, V, ss)

tribes = [V, F, VF, FV]

# father of tribe X (idempotent)
def father(X):
  if X is V or X is VF: return V
  if X is F or X is FV: return F

# mother of tribe X (idempotent)
def mother(X):
  if X is V or X is FV: return V
  if X is F or X is VF: return F

# choose tribes for A, B, C, D
for (A, B, C, D) in subsets(tribes, size=4, select="P"):

  # choose tribe for Orsino (O), Prince (P), Cook (Q), Tutor (T)
  for (O, P, Q, T) in subsets(tribes, size=4, select="M"):

    # and choose values for the following propositions:
    # p1 = "A's mother is sister of the cook"
    # p2 = "the tutor is C's grandfather"
    # p3 = "Orsino is the tutor"
    for (p1, p2, p3) in subsets([False, True], size=3, select="M"):
      # check tribes match statements
      if p1 and not (mother(A) is Q): continue
      if p2 and not (father(C) is T): continue
      if p3 and not (O is T): continue

      # check the statements:
      # A: "P is F; A's mother is sister of the cook
      if not A([P is F, p1]): continue
      # B: "father(P) = O; T is C's grandfather
      if not B([father(P) is O, p2]): continue
      # C: "P is C; C is VF"
      if not C([P is C, C is VF]): continue
      # D: "O is T; Q != father(P)"
      if not D([p3, father(P) is not Q]): continue

      # output solution
      printf(
        "A={A} B={B} C={C} D={D}; O={O} P={P} Q={Q} T={T}; p1={p1} p2={p2} p3={p3}",
        A=A.__name__, B=B.__name__, C=C.__name__, D=D.__name__,
        O=O.__name__, P=P.__name__, Q=Q.__name__, T=T.__name__,
      )

      Solution: Alan is a Fiver. Bruce is a Verific. Carl is a Fict. David is a Vere. The Prince is a Fiver.

      We have:

      A is FV
      B is VF
      C is F
      D is V

      Prince is FV
      Orsino is F
      the cook is V
      the tutor is F

      A’s mother is the sister of the cook.
      The tutor is not C’s grandfather.
      Orsino is the tutor.

      And so the statements are:

      A: “Prince (FV) is F” → false; “A’s mother (V) is sister of the cook (V)” → true; (false, true) → FV
      B: “Prince’s father (F) is same as Orsino (F) → true; “tutor is C’s grandfather” → false; (true, false) → VF
      C: “Prince (FV) is same as C (F)” → false; “C (F) is VF” → false; (false, false) → F
      D: “Orsino (F) is tutor” → true; “the cook (V) is not the same as Prince’s father (F)” → true; (true, true) → V

      Like

    • Frits's avatar

      Frits 11:06 am on 8 April 2024 Permalink | Reply

      SubstitutedExpression version of Jim’s program.

      from enigma import SubstitutedExpression
 
# V - always tells the truth
def V(ss): return all(ss)
 
# F - always tells untruths
def F(ss): return not any(ss)
 
alternate = lambda X, Y, ss: X(ss[0::2]) and Y(ss[1::2])
 
# VF - alternate true then false
def VF(ss): return alternate(V, F, ss)
 
# FV - alternate false then true
def FV(ss): return alternate(F, V, ss)
 
tribes = [V, F, VF, FV]
race = ["Vere", "Fict", "Verific", "Fiver"]
d = dict(zip(tribes, race))
 
# father of tribe X (idempotent)
def father(X):
  if X is V or X is VF: return V
  if X is F or X is FV: return F
 
# mother of tribe X (idempotent)
def mother(X):
  if X is V or X is FV: return V
  if X is F or X is VF: return F

# invalid digit / symbol assignments
d2i = dict()
for dgt in range(4):
  vs = set() 
  if dgt > 1: vs.update('XYZ')
  d2i[dgt] = vs   

# return corresponding function for values 0-3
fn = lambda a: V if not a else F if a == 1 else VF if a == 2 else FV

# the alphametic puzzle
p = SubstitutedExpression(
  [
    # V, F, VF, FV = 0, 1, 2, 3
    
    # choose tribes for A, B, C, D
    # choose tribe for Orsino (O), Prince (P), Cook (Q), Tutor (T)
    # and choose values for the following propositions:
    # X = "A's mother is sister of the cook"
    # Y = "the tutor is C's grandfather"
    # Z = "Orsino is the tutor"
    
    # check tribes match statements
    "not X or (mother(fn(A)) is fn(Q))",
    "not Y or (father(fn(C)) is fn(T))",
    "not Z or (O is T)",

    # check the statements:
    # A: "P is F; A's mother is sister of the cook
    "fn(A)([P == 1, X])",
    # B: "father(P) = O; T is C's grandfather
    "fn(B)([father(fn(P)) is fn(O), Y])",
    # C: "P is C; C is VF"
    "fn(C)([P == C, C == 2])",
    # D: "O is T; Q != father(P)"
    "fn(D)([Z, father(fn(P)) is not fn(Q)])",
  ],
  answer="(fn(A), fn(B), fn(C), fn(D)), fn(P)",
  base=4,
  d2i=d2i,
  distinct=("ABCD"),
  env=dict(mother=mother, father=father, fn=fn),
  verbose=0,    # use 256 to see the generated code
) 

# print answers
for ans in p.answers():
  print(f"Children: {', '.join(d[a] for a in ans[0])}   Prince: {d[ans[1]]}")

      Like

  • Unknown's avatar

    Jim Randell 4:35 pm on 5 April 2024 Permalink | Reply
    Tags:   

    Teaser 3211: Descendants’ ages 

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

    I have three daughters and a grandson. They are all of different ages, with the eldest being younger than 35 years old, and my grandson being the youngest.

    Three years ago the square of the age of my eldest daughter was equal to the sum of the squares of the ages of the other three. In another three years’ time the sum of the square of the age of my eldest daughter plus the square of the age of my grandson will be equal to the sum of the squares of the ages of my other two daughters.

    In ascending order, what are their ages?

    [teaser3211]

     
    • Jim Randell's avatar

      Jim Randell 4:43 pm on 5 April 2024 Permalink | Reply

      A straightforward solution using the [[ SubstitutedExpression ]] solver from the enigma.py library:

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

      Run: [ @replit ]

      #! python3 -m enigma -rr

# suppose daughters are aged D, E, F, and the grandson G

SubstitutedExpression

# allow for ages from 0-34
--base=35

# ages in descending order
"D > E" "E > F" "F > G"

# 3 years ago ...
"sq(D - 3) == sq(E - 3) + sq(F - 3) + sq(G - 3)"

# 3 years time ...
"sq(D + 3) + sq(G + 3) == sq(E + 3) + sq(F + 3)"

# answer is ages in ascending order
--answer="(G, F, E, D)"
--template=""

      Solution: The ages are: 9, 24, 25, 34.

      Three years ago we have:

      31² = 961
      6² + 21² + 22² = 961

      and in three years time we have:

      37² + 12² = 1513
      27² + 28² = 1513

      The next smallest solution is with ages: 9, 21, 30, 36. Which explains why the age of the eldest daughter was limited to 34 (although the puzzle could have said “less than 36”, and still had a unique solution).

      Like

      • Jim Randell's avatar

        Jim Randell 6:14 pm on 5 April 2024 Permalink | Reply

        Or using less brute force:

        This Python program has an internal runtime of 1.4ms.

        Run: [ @replit ]

        from enigma import (irange, sum_of_squares, sq, printf)

# consider possible ages for the eldest daughter
for D in irange(34, 18, step=-1):
  # 3 years ago ...
  for (G, F, E) in sum_of_squares(sq(D - 3), 3, sep=1):
    (G, F, E) = (G + 3, F + 3, E + 3)
    # 3 years time ...
    if sq(D + 3) + sq(G + 3) == sq(E + 3) + sq(F + 3) and not (D - G < 15):
      # output solution
      printf("{G}, {F}, {E}, {D}")

        Liked by 1 person

        • Frits's avatar

          Frits 10:48 am on 6 April 2024 Permalink | Reply

          @Jim, please elaborate on the lower bound of variable D.

          NB Your first program seems to consider negative ages as well (3 years ago).

          Like

          • Jim Randell's avatar

            Jim Randell 11:57 am on 6 April 2024 Permalink | Reply

            My first program allows the full range of ages (including negative ages for the “3 years ago” case), as I wondered if the puzzle had an “unexpected” configuration. But this didn’t give any answers in the “unexpected” range, so for my second program I used a more normal interpretation, that the grandson has a non-negative age 3 years ago, and that at least the eldest daughter is old enough to be his mother. (I’ve now added a check to ensure this). Both programs find the same answer.

            Like

    • Frits's avatar

      Frits 5:03 pm on 5 April 2024 Permalink | Reply 

        
from itertools import combinations
  
# pick 4 different squares for the situation of 3 years ago
for sqG, sqD1, sqD2, sqE in combinations([i**2 for i in range(32)], 4):
  if sqE != sqG + sqD1 + sqD2: continue
  G, D1, D2, E = [int(x**.5) for x in [sqG, sqD1, sqD2, sqE]]

  # check the situation in 3 years time
  if (E + 6)**2 + (G + 6)**2 != (D1 + 6)**2 + (D2 + 6)**2: continue
  print("answer: ages", [G + 3, D1 + 3, D2 + 3, E + 3])

      Like

    • GeoffR's avatar

      GeoffR 10:36 am on 6 April 2024 Permalink | Reply 

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

% Three daughters and one grandson
var 1..34:D1; var 1..34:D2; var 1..34:D3; var 1..34:GS;

constraint all_different([D1, D2, D3, GS]);

% Make D1 the eldest daughter
constraint D1 > D2 /\ D1 > D3 /\ D1 > GS;

% My grandson is the youngest person
% D2 can be less than D3, as on same side of the two equations
constraint GS < D2 /\ GS < D3 /\ D2 < D3;

% Three years ago the square of the age of my eldest daughter was equal to
% the sum of the squares of the ages of the other three

constraint (D1-3) * (D1-3) == (D2-3) * (D2-3) + (D3-3) * (D3-3) + (GS-3) * (GS-3);

% However, in three years time..
constraint (D1+3) * (D1+3) + (GS+3) * (GS+3) == (D2+3) * (D2+3) + (D3+3) * (D3+3);

solve satisfy;

output ["[GS, D2, D3, D1] = " ++ show([GS, D2, D3, D1])];

      Like

    • GeoffR's avatar

      GeoffR 4:16 pm on 6 April 2024 Permalink | Reply

      This teaser only gives a unique answer with an upper age limit of less than 35. If this upper age limit is increased. there are other values which satisfy the two equations e.g.

      [GS, D2, D3, D1] = [9, 21, 30, 36]
      ———-
      [GS, D2, D3, D1] = [9, 20, 33, 38]
      ———-
      [GS, D2, D3, D1] = [9, 18, 45, 48]
      ———-
      [GS, D2, D3, D1] = [9, 17, 60, 62]

      There are further values, but the eldest daughter’s age starts getting unrealistic. For clarity, the answer is not included in the above extra possibilities.

      Like

    • GeoffR's avatar

      GeoffR 6:10 pm on 9 April 2024 Permalink | Reply

      Initially I assumed D2 could be the mother of the setter’s grandson(GS).
      The code below works OK if any of the daughters is the mother, with a lower bound of GS+13.

      # Mother of GS is one of the daughters
# Assume the mother had a minimum age of 13 when GS was born.
for GS in range(3, 20):
  for D2 in range(GS+13, 33):
    for D3 in range(1, 34):
      for D1 in range(1, 35):
        if not(GS < D2 < D3 < D1):continue
        # Conditions 3 years ago and 3 years hence
        if (D1-3)**2 == (D2-3)**2 + (D3-3)**2 + (GS-3)**2 \
            and (D1+3)**2 + (GS+3)**2 == (D2+3)**2 + (D3+3)**2:
              print(f"Grandson = {GS}, Daughters = {D2}, {D3} and {D1}.")

      Like

  • Unknown's avatar

    Jim Randell 9:01 am on 2 April 2024 Permalink | Reply
    Tags:   

    Teaser 2614: The end of time 

    From The Sunday Times, 28th October 2012 [link] [link]

    In the table the letters represent the numbers 1 to 25 in some order. In each row, each column and each main diagonal the sum of the five numbers is the same. If you list all the letters in increasing numerical order then somewhere in the list you will get …, S, U, N, D, A, Y, T, I, M,.. with E coming later.

    Which letters are equal to 11, 9, 7, 3, 23 and 22?

    [teaser2614]

     
    • Jim Randell's avatar

      Jim Randell 9:02 am on 2 April 2024 Permalink | Reply

      The total of the numbers from 1 to 25 is 325. So the magic constant is 325/5 = 65.

      We can solve the puzzle using the [[ SubstitutedExpression ]] solver from the enigma.py library.

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

      Run: [ @replit ]

      #! python3 -m enigma -rr

SubstitutedExpression

--base=26
--digits="1-25"

# rows are magic
"A + B + C + D + E == 65"
"F + G + H + I + J == 65"
"K + L + M + N + O == 65"
"P + Q + R + S + T == 65"
"U + V + W + X + Y == 65"

# columns are magic
"A + F + K + P + U == 65"
"B + G + L + Q + V == 65"
"C + H + M + R + W == 65"
"D + I + N + S + X == 65"
"E + J + O + T + Y == 65"

# diagonals are magic
"A + G + M + S + Y == 65"
"E + I + M + Q + U == 65"

# look for required subsequence
"S + 1 = U"
"U + 1 = N"
"N + 1 = D"
"D + 1 = A"
"A + 1 = Y"
"Y + 1 = T"
"T + 1 = I"
"I + 1 = M"
"M < E"

--template=""

      And here is a wrapper that assembles the required answer(!).

      from enigma import (SubstitutedExpression, rev, join, printf)

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

# solve it
for s in p.solve(verbose=0):
  r = rev(s)
  # output solution
  vs = [11, 9, 7, 3, 23, 22]
  printf("{vs} -> {ks}", ks=join(r[v] for v in vs))

      Solution: The given values spell: ANSWER.

      The grid looks like this:

      And the letters ordered by value are:

      J B W K Q H S U N D A Y T I M O V P C G L R E F X

      Like

      • Frits's avatar

        Frits 10:59 am on 2 April 2024 Permalink | Reply

        @Jim, 5th column equation is same as 5th row equation.

        Like

        • Jim Randell's avatar

          Jim Randell 11:13 am on 2 April 2024 Permalink | Reply

          Thanks. Fixed now.

          I did make a version of the code that derives the expressions from the rows of the square [@replit] (which eliminates mistakes like this), but I posted the literal version as it is more readable.

          Like

    • GeoffR's avatar

      GeoffR 2:22 pm on 2 April 2024 Permalink | Reply 

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

var 1..25:A;   var 1..25:B;   var 1..25:C;   var 1..25:D;
var 1..25:E;   var 1..25:F;   var 1..25:G;   var 1..25:H;
var 1..25:I;   var 1..25:J;   var 1..25:K;   var 1..25:L;
var 1..25:M;   var 1..25:N;   var 1..25:O;   var 1..25:P;
var 1..25:Q;   var 1..25:R;   var 1..25:S;   var 1..25:T;
var 1..25:U;   var 1..25:V;   var 1..25:W;   var 1..25:X;
var 1..25:Y;

constraint all_different([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y]);

% ROWS
constraint A+B+C+D+E == 65 /\ F+G+H+I+J == 65 /\ K+L+M+N+O == 65
/\ P+Q+R+S+T == 65 /\ U+V+W+X+Y == 65;  % Jim's analysis

% COLUMNS
constraint  A+F+K+P+U == 65 /\ B+G+L+Q+V == 65 /\ C+H+M+R+W == 65
/\ D+I+N+S+X == 65 /\ E+J+O+T+Y == 65;

% DIAGONALS
constraint A+G+M+S+Y == 65 /\ U+Q+M+I+E == 65;

%  S, U, N, D, A, Y, T, I, M are in increasing sequence
 constraint S+1 == U /\ U+1 == N /\ N+1 == D /\ D+1 == A /\ A+1 == Y
/\ Y+1 == T /\ T+1 ==I /\ I + 1 == M;

constraint M < E; %... with E coming later

solve satisfy;

output[" [A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y] = " ++
"\n" ++ show(  [A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y] ) ++
"\n" ++ "Grid : " ++ "\n" ++ show ([A,B,C,D,E] )
++"\n" ++ show([F,G,H,I,J]) ++ "\n" ++ show( [K,L,M,N,O] )
++"\n" ++ show( [P,Q,R,S,T]) ++ "\n" ++ show ( [U,V,W,X,Y]) ];

% [A,  B, C,  D,  E,  F,  G,  H, I,  J, K, L,  M,  N, O,  P,  Q, R,  S, T,  U, V,  W, X,  Y] =
% [11, 2, 19, 10, 23, 24, 20, 6, 14, 1, 4, 21, 15, 9, 16, 18, 5, 22, 7, 13, 8, 17, 3, 25, 12]
% Grid :
% [11, 2, 19, 10, 23]
% [24, 20, 6, 14, 1]
% [4, 21, 15, 9, 16]
% [18, 5, 22, 7, 13]
% [8, 17, 3, 25, 12]
%----------
%==========
% By interpolation 11, 9, 7, 3 , 23, 22 = A, N, S, W, E, R

      Like

    • Frits's avatar

      Frits 6:09 pm on 3 April 2024 Permalink | Reply 

      # make sure loop variable value is not equal to previous ones
def domain(v, r=range(1, 26)):
  # find already used loop values  ...
  vals = set()
  # ... by accessing previously set loop variable names
  i = 0  # initially <i> (otherwise compiler error)
  for i, s in enumerate(lvd[v], 1):
    val = globals()[s]
    # general domain check
    if not (0 < val < 26): return []
    vals.add(val)
  
  # don't except duplicates in previous variables
  if len(vals) != i:
    return []
 
  return [x for x in r if x not in vals]

# set up dictionary of for-loop variables
lv = list("NXSUDAYTIMGEQVWBCLOKJFHPR")
lvd = {v: lv[:i] for i, v in enumerate(lv)}

# D + I + N + S = (N + 1) + (N + 5) + N + (N - 2) = 4N + 4 --> X = 61 - 4N
for N in domain('N', range(9, 16)):
  X = 61 - 4 * N
  S, U, N, D, A, Y, T, I, M = [N + x for x in range(-2, 7)]
  G = 65 - (A + M + S + Y)
  # E + I + M + Q + U = 65, E = 65 - Q - (I + M + U) and E > M
  # assume E = M + x, x > 0 --> x = 65 - Q - (I + 2M + U) > 0 
  if (I + 2 * M + U) > 63: continue
  # check rest of numbers
  for E in domain('E', range(M + 1, 26)):
    Q = 65 - (E + I + M + U)
    for V in domain('V'):
      W = 65 - (U + V + X + Y)
      for B in domain('B'):
        C = 65 - (A + B + D + E) 
        L = 65 - (B + G + Q + V)
        for O in domain('O'):
          K = 65 - (L + M + N + O)
          J = 65 - (E + O + T + Y)
          for F in domain('F'):
            H = 65 - (F + G + I + J)
            P = 65 - (A + F + K + U)
            for R in domain('R'):
              if R != 65 - (P + Q + S + T): continue
              
              # check remaining equations to be sure we give a correct answer
              if P + Q + R + S + T != 65: continue
              if C + H + M + R + W != 65: continue

              vs = [11, 9, 7, 3, 23, 22]
              nums = [A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y]
              chars = "ABCDEFGHIJKLMNOPQRSTUVWXY"

              print(f"answer: {[chars[nums.index(v)] for v in vs]}")

      Like

      • Frits's avatar

        Frits 8:39 pm on 3 April 2024 Permalink | Reply

        line 30 also implies that N is less than 12.

        Like

  • Unknown's avatar

    Jim Randell 6:04 pm on 31 March 2024 Permalink | Reply
    Tags: by: Sir John Cowley   

    Brainteaser 1092: If a man and a half… 

    From The Sunday Times, 10th July 1983 [link]

    I wanted some small alterations done, to my house, so I asked Tom Smith, the local builder, to come and see me.

    I told Tom exactly what the job was and he said he could do it alone, but if he brought his brother Dick (also a trained builder), and his son Harry (an apprentice), the three of them could do the job in half the time that he; Tom, would take if he worked alone.

    Dick could also do the job by himself, but it would take him a day (eight hours) longer than the three of them working together. Young Harry working alone would take six days more than the three of them.

    I wanted the job done quickly, but as there was no room for all three of them to work together, and it was not necessary to employ two trained builders, I decided to employ either Tom and Harry working together, or Dick and Harry working together.

    Exactly how much longer would the second pair take to finish the job than the first pair?

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

    [teaser1092]

     
    • Jim Randell's avatar

      Jim Randell 6:05 pm on 31 March 2024 Permalink | Reply

      Suppose Tom, Dick, Harry can do T, D, H amounts of work per day.

      If we suppose the job consists of 1 unit of work, which all 3 can complete in d days:

      1 = (T + D + H) d

      Tom would take twice as long to do it alone:

      1 = T 2d
      ⇒
      T = 1/(2d)

      Dick would take 1 day longer than all three:

      1 = D (d + 1)
      ⇒
      D = 1/(d + 1)

      And Harry alone would take 6 days longer than all three:

      1 = H (d + 6)
      ⇒
      H = 1/(d + 6)

      And so:

      1/d = T + D + H
      = 1/(2d) + 1/(d + 1) + 1/(d + 6)
      = [(d + 1)(d + 6) + 2d(d + 6) + 2d(d + 1)] / 2d(d + 1)(d + 6)
      ⇒
      2(d + 1)(d + 6) = (d + 1)(d + 6) + (2d² + 12d) + (2d² + 2d)
      d² + 7d + 6 = 4d² + 14d
      3d² + 7d − 6 = 0
      (3d − 2)(d + 3) = 0
      d = 2/3 (= 5h 20m)

      and:

      T = 3/4
      D = 3/5
      H = 3/20

      So the time taken for Tom and Harry (= t1) is:

      t1 = 1 / (T + H)
      T + H = 3/4 + 3/20 = 9/10
      t1 = 10/9

      And the time taken for Dick and Harry (= t2) is:

      t2 = 1 / (D + H)
      D + H = 3/5 + 3/20 = 3/4
      t2 = 4/3

      And the difference:

      t2 − t1 = 4/3 − 10/9 = 2/9 (days)

      Solution: It would take exactly 1 hour, 46 minutes, 40 seconds longer.

      Liked by 1 person

  • Unknown's avatar

    Jim Randell 4:16 pm on 29 March 2024 Permalink | Reply
    Tags:   

    Teaser 3210: Random rabbit 

    From The Sunday Times, 31st March 2024 [link] [link]

    Every year Easter Bunnies must pass a series of demanding tests, the most important being the double jump. Rabbits perform a single jump comprising two hops, with the total distance scoring. For both hops, Max knows he has an equal chance of jumping any distance between two limits. For the first hop, the limits are 80 and 100cm. For his weaker second hop, these limits decrease but keep the same proportion.

    However, the instructors have increased the required standard from 152 to 163cm. Max is worried; he can still pass, but his chance is half what it was before.

    What, as a percentage, is his chance of passing this year?

    This brings the total number of Teaser puzzles posted on the site to 1024 (= 2^10), which is roughly 1/3 of all published Teaser puzzles.

    [teaser3210]

     
    • Jim Randell's avatar

      Jim Randell 5:47 pm on 29 March 2024 Permalink | Reply

      We can consider the possible jumps to be a region of the cartesian plane between x = [80, 100] (= hop 1) and y = [80f, 100f] (= hop 2), where f ∈ (0, 1) gives the reduction for the second hop.

      The probabilities are then calculated from the proportion of this rectangular region that is above the lines x + y = 152 (last year) and x + y = 163 (this year). (Assuming that hops are uniformly distributed).

      This Python program finds the value of f numerically, such that the second area (dark blue) is half the first area (both blues), and then calculates the corresponding probabilities.

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

      Run: [ @replit ]

      from enigma import (find_value, fdiv, sq, inf, printf)

# find area where x + y > t
def A(t, f):
  # where does x + y = t hit y = 80f and 100f
  (x1, x2) = (t - 80 * f, t - 100 * f)
  if x1 < 80:
    # entire area = 20 * 20f
    return 400 * f
  if x2 < 80:
    # remove bottom left corner
    return 400 * f - 0.5 * sq(x1 - 80)
  if x1 < 100:
    # trapezium
    return 20 * f * (10 * f + 100 - x1)
  if x2 < 100:
    # top left corner
    return 0.5 * sq(100 - x2)
  # otherwise, zero area
  return 0

# find ratio of areas for the two scenarios
def fn(f):
  # area for t = 152
  A1 = A(152, f)
  if A1 == 0: return inf
  # area for t = 163
  A2 = A(163, f)
  # return the ratio A2/A1
  return fdiv(A2, A1)

# find when fn(f) = 0.5, for f in the interval (0, 1)
r = find_value(fn, 0.5, 0.0, 1.0)
f = r.v

# calculate probabilities
T = 400 * f  # total area
P1 = fdiv(A(152, f), T)
P2 = fdiv(A(163, f), T)

# output solution
printf("{P1:.1%} -> {P2:.1%} [f={f:.2f}]")

      Solution: Max’s chance of passing this year is 45%.

      The value of f is 0.8, so the range for the second hop is 64 – 80 cm.

      This gives a total area of the rectangle as: 20 × 16 = 320.

      For last year we want the area of the rectangle above the line (80, 72) – (88, 64) which gives: 288.

      For this year we want the area above the line (83, 80) – (99, 64) which gives: 144.

      And so the probability this year (144/320 = 45%) is exactly half of the probability last year (288/320 = 90%).

      Like

    • Frits's avatar

      Frits 7:38 pm on 29 March 2024 Permalink | Reply

      For the time being an approximation, less than half a second with PyPy.
      Starts to slow down quickly when increasing the precision.

      from itertools import product

lmts = [80, 100]
stds = {2023: 152, 2024: 163}
fr, to = 52, 79 
done = 0

m = 1 # multiplication factor
while not done:
  lmts = [10 * x if m > 1 else x for x in lmts]
  rng1 = range(lmts[0], lmts[1] + 1)
  
  # a = lower limit for 2nd jump
  for a in range(to, fr - 1, -1):
    rng2 = [a * x / lmts[0] for x in rng1]
    # chance of passing per year
    P2023 = sum(x + y >= m * stds[2023] for x, y in product(rng1, rng2)) / (len(rng1) * len(rng2))
    P2024 = sum(x + y >= m * stds[2024] for x, y in product(rng1, rng2)) / (len(rng1) * len(rng2))
    # check if we are close to 50% 
    if abs(P2024 / P2023 - 0.500) <= 1e-3:
      print(f"answer: approximately {round(100 * P2024, 1)}%")
      done = 1
      break

    if P2024 / P2023 < 0.5: break  
  
  # try to get closer to 50,00% by increasing the ranges by 10 
  m *= 10
  (fr, to) = (10 * a, 10 * (a + 1))

      Like

      • Frits's avatar

        Frits 2:50 pm on 30 March 2024 Permalink | Reply

        More efficient.

        from math import ceil
 
lmts = [80, 100]
stds = {2023: 152, 2024: 163}
# if 2nd hop is below 52 we can never reach 152
fr, to = 52, 79
done = 0

# calculate the chance if we pick one element from r1 and r2 that
# their sum is greater or equal <std> 
def calcP(r1, r2, std):
  miss, strt = 0, 0
  ln1, ln2 = len(rng1), len(rng2)
  df1, df2 = rng1[1] - rng1[0], rng2[1] - rng2[0]
  # factor f: f * df2 >= df1 --> f >= df1 / df2
  f = ceil(df1 / df2)
  r2rev = rng2[::-1]

  # if x1 + x2 is lower than <std> for this x2 then x1 + (x2 + df2) >= std
  # --> (x1 - df1) + (x2 + df2 + f * df2) >= std  (as f * df2 >= df1)
  # meaning: for the next x1 iteration we can select a subset of rng2
  
  # loop from the high value to low value
  for x1 in rng1[::-1]:
    for j, x2 in enumerate(r2rev[strt:], start=strt):
      if x1 + x2 < std:
        strt = j - f if j - f >= 0 else j - 1 
        # increment number of combinations below the standard
        miss += (ln2 - j)
        # for the next x1 we can start checking x2 as of (x2 + k * df2)
        break
    else:
      continue
      
    # a break has occurred  
    if j == 0:
      # for lower x1's add maximum missing number (ln2)
      miss += (ln2 * (x1 - rng1[0]))
      break
 
  return ((ln1 * ln2) - miss) / (ln1 * ln2)       
  
 
m = 1 # multiplication factor
while not done:
  lmts = [10 * x if m > 1 else x for x in lmts]
  rng1 = range(lmts[0], lmts[1] + 1)
   
  # a = lower limit for 2nd jump
  for a in range(to, fr - 1, -1):
    rng2 = [a * x / lmts[0] for x in rng1]
    # chance of passing per year
    P2023 = calcP(rng1, rng2, m * stds[2023]) 
    P2024 = calcP(rng1, rng2, m * stds[2024])
    
    # check if we are close to 50% 
    if abs(P2024 / P2023 - 0.5) <= 1e-4:
      print(f"answer: approximately {round(100 * P2024, 2)}%")
      done = 1
      break
 
    if P2024 / P2023 < 0.5: break 
    
  # try to get closer to 50,00% by increasing the elements by 10
  m *= 10
  (fr, to) = (10 * a, 10 * (a + 1))

        PyPy is a lot faster than CPython. I don’t recall a program where PyPy was more than 17 times quicker.

        D:\Python>pypy RandomRabbit1D.py
answer: approximately 45.0%
[temp.py] total time: 1.4625589s (1.46s)
D:\Python>pyth RandomRabbit1D.py
answer: approximately 45.0%
[temp.py] total time: 25.6650562s (25.67s)

        Like

        • Frits's avatar

          Frits 12:11 pm on 1 April 2024 Permalink | Reply

          line 24 can be done more efficiently.

               
for x1 in [x for x in rng1 if x < std - r2[-0]][::-1]:

          The program runs now in 200ms/500ms for PyPy/CPython.

          Like

  • Unknown's avatar

    Jim Randell 10:35 am on 28 March 2024 Permalink | Reply
    Tags:   

    Teaser 2636: Simple Easter Teaser 

    From The Sunday Times, 31st March 2013 [link] [link]

    I have written down three numbers, at least one of which is odd. Furthermore, one of the three is the sum of the other two. Then I have consistently replaced digits by letters, using different letters for different digits, and the numbers have become:

    SIMPLE
    EASTER
    TEASER

    What number is EASTER?

    [Incidentally, Easter Sunday 2013 has a palindromic date, 31/3/13. Interestingly, this happens next in 2031].

    This puzzle completes the archive of puzzles originally published in 2013.

    [teaser2636]

     
    • Jim Randell's avatar

      Jim Randell 10:36 am on 28 March 2024 Permalink | Reply

      At least one of the numbers is odd, so at least one of E or R must be odd.

      We can check that one of the numbers is the sum of the other two by adding all of them together, and then this total must be twice one of the original numbers:

      SIMPLE + EASTER + TEASER ∈ { 2×SIMPLE, 2×EASTER, 2×TEASER }

      So the LHS must be an even number, and if both E and R were odd, the LHS would be an odd number, so only one of them can be odd. And if E is odd then the LHS is also odd, hence E must be even and R must be odd.

      We can solve the puzzle using this expression directly with the [[ SubstitutedExpression ]] solver from the enigma.py library.

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

      Run: [ @replit ]

      #! python3 -m enigma -rr

SubstitutedExpression

"SIMPLE + EASTER + TEASER in { 2 * SIMPLE, 2 * EASTER, 2 * TEASER }"

# E is even, R is odd
"E % 2 = 0"
"R % 2 = 1"

--answer="EASTER"

      Solution: EASTER = 278521.

      And the sum is:

      EASTER + TEASER = SIMPLE → 278521 + 527821 = 806342

      There is a further solution to this alphametic sum where all the terms are even:

      EASTER + TEASER = SIMPLE → 417342 + 341742 = 759084

      For a faster program we can consider the three possible sums (which can be solved using the [[ SubstitutedExpression.split_sum() ]] solver.

      The following Python program runs in 58ms. (Internal runtime is 8.6ms).

      Run: [ @replit ]

      from enigma import (SubstitutedExpression, delete, sprintf, join, printf)

# words involved in the alphametic
words = ['SIMPLE', 'EASTER', 'TEASER']

# try each word as the result
for (i, result) in enumerate(words):
  expr = sprintf("{terms} = {result}", terms=join(delete(words, [i]), sep=" + "))
  # construct the alphametic puzzle
  p = SubstitutedExpression.split_sum(
    expr,
    extra=["(E % 2 != 0) or (R % 2 != 0)"],  # at least one is odd
  ).solver()
  # solve the puzzle
  for s in p.solve(verbose=0):
    # output solution
    printf("{expr} / {s}", s=p.substitute(s, expr))

      Like

    • GeoffR's avatar

      GeoffR 1:47 pm on 28 March 2024 Permalink | Reply 

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

var 1..9:S; var 0..9:I; var 0..9:M; var 0..9:P; var 0..9:L;
var 1..9:E; var 0..9:A; var 1..9:T; var 1..9:R;

constraint all_different ([S, I, M, P, L, E, A, T, R]);

% At least one of three numbers is odd.
constraint sum([E mod 2 == 1, R mod 2 == 1]) > 0;

var 100000..999999:SIMPLE == 100000*S + 10000*I + 1000*M + 100*P + 10*L + E;
var 100000..999999:EASTER == 100000*E + 10000*A + 1000*S + 100*T + 10*E + R;
var 100000..999999:TEASER == 100000*T + 10000*E + 1000*A + 100*S + 10*E + R;

%  One of the three numbers is the sum of the other two
constraint SIMPLE == EASTER + TEASER
\/ EASTER == SIMPLE + TEASER
\/ TEASER == SIMPLE + EASTER;

solve satisfy;

output[ "EASTER = " ++ show(EASTER) 
++ "\n" ++ "SIMPLE = " ++ show(SIMPLE) 
++ "\n" ++ "TEASER = " ++ show(TEASER) ];

% EASTER = 278521
% SIMPLE = 806342
% TEASER = 527821
% ----------
% ==========
% So SIMPLE = EASTER + TEASER

      Like

    • Frits's avatar

      Frits 9:13 pm on 28 March 2024 Permalink | Reply 

        
from itertools import permutations

# EASTER
# TEASER     only valid sum ot the three sums (otherwise E = 0)
# ------ +
# SIMPLE

# A can't be zero as it would also lead to M = 0
for R, E, S, T in permutations(range(1, 10), 4):
  # basic checks (R must be odd)
  if not ((2 * R) % 10 == E and R % 2 and E + T in {S - 1, S}): continue

  if (L := (2 * E + (R > 5)) % 10) in {R, E, S, T}: continue
  if (P := (S + T + (E > 4)) % 10) in {R, E, S, T, L}: continue
  
  for A in set(range(1, 10)).difference({R, E, S, T, L, P}):
    EASTER = int(''.join(str(x) for x in [E, A, S, T, E, R]))
    TEASER = int(''.join(str(x) for x in [T, E, A, S, E, R]))
    
    if (SIMPLE := EASTER + TEASER) // 100000 != S: continue
    IM = (SIMPLE // 1000) % 100
    if any(int(x) in {R, E, S, T, L, P, A} for x in str(IM)): continue
    print("answer:", EASTER)

      Like

  • Unknown's avatar

    Jim Randell 10:09 am on 26 March 2024 Permalink | Reply
    Tags:   

    Teaser 2674: Roll model 

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

    My new board game has squares numbered from 1 to 100 and has two unusual dice. The first die is 10-sided with numbers from 1 to 10, and the second is 4-sided with a prime number on each side. A move consists of throwing the two dice and then choosing either one of the numbers or their sum and moving that number of squares in either direction. I found myself on one square and realised that there were just two squares which it would be impossible for me to reach with my next move. Both of those squares had prime numbers that did not appear on the dice.

    (a) Which particular square was I on?
    (b) What are the four numbers on the second die?

    [teaser2674]

     
    • Jim Randell's avatar

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

      There are (10 + 4 + 10×4) = 54 possible scores, and we can move in either direction.

      So, when we start on a square the reachable squares spread out from it in both directions. If we have 56 consecutive numbers, and we can make 54 of them using the dice, this would be the maximum possible. And so the largest possible square we can be on is 57 and the smallest possible is 44. And we can’t afford more than 6 non-usable scores.

      We cannot afford more than 1 gap in the scores from 1 to 43 (as any gaps will be mirrored on the other side), or more than 2 gaps overall (if they are close to the end, the gaps could be on the same side – although this seems improbable if they are both primes).

      This Python program considers possible sets of primes on the second die, and let looks for an appropriate starting square. (We could just consider all possible combinations of primes, but it is a bit faster check we don’t introduce too many gaps or overlaps as we build up the sets).

      It runs in 58ms. (Internal runtime is 1.3ms).

      Run: [ @replit ]

      from enigma import (irange, primes, printf)

# squares on the board
squares = set(irange(1, 100))

# die 1
d1 = list(irange(1, 10))

# fill out die 2
def die2(ns, d1, ds, d2=list()):
  k = len(d2)
  if k == 4:
    yield (d2, ds)
  else:
    # choose the next number on die 2
    for (i, n) in enumerate(ns):
      # update the set of deltas
      ds_ = ds.union([n], (n + x for x in d1))
      m = 11 * k + 10
      # check for overlaps and gaps
      if len(ds_) < m + 5: continue
      if len(set(irange(1, m)).difference(ds_)) > (1 if k < 3 else 2): continue
      # fill out the remaining faces
      yield from die2(ns[i:], d1, ds_, d2 + [n])

# die 2 has 4 [different] primes
ps = list(primes.between(5, 50))

# consider possible die 2 and deltas
for (d2, ds) in die2(ps, d1, set(d1)):
  n = len(ds)
  # consider starting on square i
  for i in irange(98 - n, 5 + n):
    # find unreachable squares
    missing = squares.difference((i - x for x in ds), (i + x for x in ds), [i])
    # there are exactly 2 primes missing, that are not on d2
    if len(missing) != 2: continue
    if any(x in d2 or x not in primes for x in missing): continue
    # output solution
    printf("die2={d2}; square={i}; missing={missing}", missing=sorted(missing))

      Solution: (a) You were on square 51; (b) The numbers on the second die are: 11, 23, 31, 41.

      And the squares that cannot be reached are 29 and 73.

      Manually we can adopt a “greedy” strategy to maximise the reach of the dice while minimising the gaps:

      Die 10 will cover deltas 1..10 on either side, and if 11 is not on die 2, then both deltas of 11 and 12 are unreachable, which would make at least 4 unreachable squares (2 on each site). So 11 must be on die 2 and we can cover deltas 1..21.

      The next missing delta is now 22 (which is not prime), so we either leave 22 as unreachable, or we put a prime less than 22 on die 2.

      If we leave 22 as unreachable, and put 23 on die 2 then we can cover deltas 1..33, our unreachable values are at ±22, and we can’t have any more gaps.

      The next missing delta is 34, which is not a prime, so the largest prime we can add to die 2 is 31, which means we can cover deltas 1..41 (except 22).

      The next missing delta is 42, so the largest prime we can add is 41, and so with die 2 = (11, 23, 31, 41) we can cover deltas 1..51 (except 22).

      Starting on squares 49..52 we have the following unreachable squares:

      49 → 27, 71 [not both prime]
      50 → 28, 72 [not both prime]
      51 → 29, 73 [both prime, not on die 2 ⇒ solution]
      52 → 30, 74 [not both prime]

      So we have found a single candidate solution, but we can continue and confirm this is the only candidate:

      If we choose to cover 22, by placing the largest possible prime (i.e. 19) on die 2, then we can cover deltas 1..29.

      The next missing delta is now 30, we could choose to leave ±30 unreachable, and place 31 on die 2, so we can cover 1..41 (except 30).

      And then we place 41 on die 2, and we can cover 1..51 (except 30).

      This gives the following unreachable squares with die 2 = (11, 19, 31, 41):

      49 → 19, 79 [both prime, but 19 on die 2]
      50 → 20, 80 [not both prime]
      51 → 21, 81 [not both prime]
      52 → 22, 82 [not both prime]

      This gives no solutions.

      So we need to cover 30, so we place 29 on die 2, we can then cover deltas 1..39.

      We can leave 40 as unreachable and place 41 on die 2, and we cover 1..51 (except 40).

      This gives the following unreachable squares with die 2 = (11, 19, 29, 41):

      49 → 9, 89 [not both prime]
      50 → 10, 90 [not both prime]
      51 → 11, 91 [not both prime]
      52 → 12, 92 [not both prime]

      This gives no solutions.

      So we need to cover 40, so we place 37 on die 2, and we cover 1..47, and this is not enough to leave just 2 unreachable squares.

      And we have found no further candidate solutions.

      Like

      • Hugo's avatar

        Hugo 11:39 am on 26 March 2024 Permalink | Reply

        A ten-sided die is not very practical, and a tetrahedron doesn’t roll.
        I suggest using an icosahedron and an octahedron, with each number occurring twice
        (for example, on opposite faces).

        Like

        • Jim Randell's avatar

          Jim Randell 12:23 pm on 26 March 2024 Permalink | Reply

          @Hugh: I think I have seen 10 sided dice based on a pentagonal trapezohedron [@wikipedia]. You could also roll a long dodecahedral prism. A square prism might not be so good though.

          Like

          • Lise Andreasen's avatar

            Lise Andreasen 4:34 pm on 4 April 2024 Permalink | Reply

            There are standard 4 and 10 sided easily available, among other things for paper RPG.

            Like

    • Frits's avatar

      Frits 10:47 pm on 26 March 2024 Permalink | Reply 

       
# primes up to 100
P = [3, 5, 7]
P = [2] + P + [x for x in range(11, 100, 2) if all(x % p for p in P)]

# this program tries to follow Jim's manual solution.

# for delta's 1 - 43 we can afford to miss one delta

# add a new prime allowing only 1 gap for the first 43 delta's
def solve(d, ds=[], skip=0):
  if len(ds) == 4:
    # check number of possible reachable squares
    if 2 *(ds[-1] + 10 - (skip > 0)) > 96:
      yield (ds, skip)
  else:
    # try to make delta <d> or ...
    if d in P:
      yield from solve(d + 11, ds + [d], skip)    
    else:
      # largest prime we can add to die 2
      lp = [p for p in P if p < d and p != skip][-1]
      yield from solve(lp + 11, ds + [lp], skip)    
    # ... leave delta <d> as unreachable
    if not skip:
      yield from solve(d + 1, ds, d)  

# deltas 1-10 will be covered by the first die
for d2, skip in solve(11):
  # we can cover deltas 1..r except possible <skip>
  r = d2[-1] + 10
  
  # one delta must have been skipped, otherwise the number of possible
  # reachable squares is too low
  
  # consider starting on square <pos>
  for pos in range(100 - r, r + 2) :
    # non-reachables
    nr = [pos - skip, pos + skip] 
    if any(x for x in nr if x not in P or x in d2): continue
    print(f"answer: Peter was on square {pos}, "
          f"the four numbers on the second die are: {d2}")

      Like

  • Unknown's avatar

    Jim Randell 10:03 am on 24 March 2024 Permalink | Reply
    Tags:   

    Brain-Teaser 351: Birthday party 

    From The Sunday Times, 28th January 1968 [link]

    Some years ago the Bell family were holding their usual annual special birthday party. Four members of the family, of four different generations, had birthdays on the same day of the year. They were old Adam, his son Enoch, Enoch’s son Joseph and Joseph’s son David. On this occasion David remarked that the sum of any three of their four ages was a perfect square.

    Some years later old Adam died on his birthday, but it so happened that on the very same day David’s son Samuel was born, and the annual party was continued in subsequent years.

    In 1967 at the usual party Samuel made exactly the same remark that David had made, on the previous occasion.

    In what year did Adam die and how old was he then?

    (Perhaps I should mention that no one survived to be 100!).

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

    [teaser351]

     
    • Jim Randell's avatar

      Jim Randell 10:03 am on 24 March 2024 Permalink | Reply

      This Python program considers possible potential gaps between generations, and then looks for ages that makes any subset of size 3 sum to a square. Once we have found potential candidates we look for a pair with suitable overlapping gaps.

      It runs in 221ms. (Internal runtime is 144ms).

      Run: [ @replit ]

      # generate possible (<gaps>, <ages>)
def generate():
  # suppose the gaps between generations are in the range [15, 40]
  # which means the sum of the 3 gaps lies between 45 and 97
  for g in irange(45, 97):
    for (p, q, r) in decompose(g, 3, increasing=0, sep=0, min_v=15, max_v=40):
      # consider lowest age
      for a in irange(1, 98 - g):
        b = a + p
        c = b + q
        d = c + r
        t = a + b + c + d
        if not all(is_square(t - x) for x in (a, b, c, d)): continue
        printf("[({r}, {q}, {p}) -> ({d}, {c}, {b}, {a})]")
        yield ((r, q, p), (d, c, b, a))

# look for gaps (p, q, r) -> (q, r, s)
for (((p, q, r), (A1, E1, J1, D1)), ((q_, r_, s), (E2, J2, D2, S2))) in subsets(generate(), size=2, select='P'):
  if not (q_ == q and r_ == r and E2 > E1): continue
  # event 2 is in 1967
  y2 = 1967
  y1 = y2 - (E2 - E1)
  printf("{y1} (A={A1} E={E1} J={J1} D={D1}) -> {y2} (E={E2} J={J2} D={D2} S={S2})")
  b = y1 - A1  # A's birth year
  d = y2 - S2  # A's death year = S's birth year
  a = d - b # A's age at death
  printf("-> A born {b}; died {d}, aged {a}")

      Solution: Adam died in 1953, on his 96th birthday.

      There are only three viable candidate lists:

      (58, 41, 22, 1) with gaps of (17, 19, 21)
      (78, 57, 34, 9) with gaps of (21, 23, 25)
      (89, 66, 41, 14) with gaps of (23, 25, 27)

      An age of 1 might be a little young to be making observations, but in any case only the final two candidates have suitable overlapping gaps.

      So, at the first event we have:

      Adam = 78; Enoch = 57; Joseph = 34; David = 9

      And at the second event:

      Enoch = 89; Joseph = 66; David = 41; Samuel = 14

      This is 32 years later than the first event, and as it happened in 1967 the first event was in 1935.

      So Adam was born in 1857, and Samuel was born in 1953, the same year Adam died. So Adam died on his 96th birthday.

      Like

    • Frits's avatar

      Frits 12:40 pm on 24 March 2024 Permalink | Reply

      Faster and probably easier to understand.
      I have also not put in an age restriction for the youngest family member to make observations.

       
from enigma import SubstitutedExpression, subsets

# invalid digit / symbol assignments
d2i = dict()
for d in range(0, 100):
  vs = set() 
  if d > 69: vs.update('A')
  # not excluding young fathers (with such names)
  for i in range(4):
    if not (10 * i <= d < 10 * (i + 7)): vs.update('ABCD'[i])
  d2i[d] = vs  

# the alphametic puzzle
p = SubstitutedExpression(
  [ # increasing ages A, B, C and D
    "B > (A + 10)",
    "C > (B + 10)", 
    "is_square(A + B + C)",
    "D > (C + 10)", 
    # the sum of any three of their four ages was a perfect square
    "all(is_square(x + y + z) for x, y, z in subsets(@ages, 3))"
  ],
  base=100,
  macro=dict([("ages", "[D, C, B, A]")]),
  answer="@ages",
  d2i=d2i,
  distinct="",
  verbose=0,    # use 256 to see the generated code
)

# a,     e,     j,     d
# e + n, j + n, d + n, s 
for (a, e, j, d), (e2, j2, d2, s)  in subsets(p.answers(), 2, select="P"):
  # same age increase for Enoch, Joseph and David
  if len(set([e2 - e, j2 - j, d2 - d])) != 1: continue
  n = e2 - e
  # some years later old Adam died on his birthday
  if s >= n - 2: continue
  print(f"answer: Adam died in {1967 - s} at the age of {a + n - s}")

      Like

      • Jim Randell's avatar

        Jim Randell 1:34 pm on 24 March 2024 Permalink | Reply

        @Frits: Yes, it a good idea to check three of the values sum to a square before moving on to the fourth.

        This Python program runs in 70ms. (Internal runtime is 11ms).

        Run: [ @replit ]

        from enigma import (irange, powers, decompose, subsets, is_square, singleton, printf)

# generate possible (<gaps>, <ages>)
def generate():
  # choose possible squares for b + c + d
  for ta in powers(10, 15):
    for (b, c, d) in decompose(ta, 3, increasing=1, sep=15, min_v=16, max_v=99):
      # find values for a
      for a in irange(1, b - 15):
        t = ta + a
        if not all(is_square(t - x) for x in (b, c, d)): continue
        printf("[ages = ({d}, {c}, {b}, {a})]")
        yield (d, c, b, a)

# look for gaps (p, q, r) -> (q, r, s)
for ((A1, E1, J1, D1), (E2, J2, D2, S2)) in subsets(generate(), size=2, select='P'):
  g = singleton({E2 - E1, J2 - J1, D2 - D1})
  if g is None or not (g > 0): continue
  # event 2 is in 1967
  y2 = 1967
  y1 = y2 - g
  printf("{y1} (A={A1} E={E1} J={J1} D={D1}) -> {y2} (E={E2} J={J2} D={D2} S={S2})")
  b = y1 - A1  # A's birth year
  d = y2 - S2  # A's death year = S's birth year
  a = d - b # A's age at death
  if not (d > y1 and a < 100): continue
  printf("-> A born {b}; died {d}, aged {a}")

        Like

      • Frits's avatar

        Frits 2:21 pm on 24 March 2024 Permalink | Reply

        It is getting more and more annoying to have to do an import or specify a function for a normal operation like ceil.

        This program performs the same as Jim’s 2nd program and seems to have more requirements checks than Jim.

        @Jim, it is not immediately clear to me from your code that Adam didn’t die as a centenarian or that Samuels’ age isn’t too high.

        from itertools import permutations
from math import ceil

# minimal difference between generations
diff = 15
mxA = 98   # if Adam dies one year after the party he still is only 99

d6 = 6 * diff
sqs = set(i * i for i in range(ceil(d6**.5), int((4 * mxA - d6)**.5) + 1))

sols = []
for A in range(1, mxA - 3 * diff + 1):
  for B in range(A + diff, mxA - 2 * diff + 1):
    for C in range(B + diff, mxA - diff + 1):
      if (A + B + C) not in sqs: continue
      for D in range(C + diff, mxA + 1):
        # borrowed from Jim
        if any((A + B + C + D - x) not in sqs for x in [D, C, B, A]): 
          continue
        sols.append([D, C, B, A])

# a,     e,     j,     d
# e + n, j + n, d + n, s 
for (a, e, j, d), (e2, j2, d2, s) in permutations(sols, 2):
  # same age increase for Enoch, Joseph and David
  if len(set([e2 - e, j2 - j, d2 - d])) != 1: continue
  n = e2 - e
  # some (1 or more) years later Adam died on his birthday and 
  # no one (read Adam) survived to be 100
  if s >= n or a + n - s > 99: continue
  print(f"answer: Adam died in {1967 - s} at the age of {a + n - s}")

        Like

        • Jim Randell's avatar

          Jim Randell 2:59 pm on 24 March 2024 Permalink | Reply

          @Frits: Yes, for completeness we can add a check to ensure a < 100 and d > y1.

          Fortunately it doesn’t remove the single candidate solution.

          Like

      • Frits's avatar

        Frits 8:29 pm on 24 March 2024 Permalink | Reply

        Inspired by Brian. Fastest approach sofar (5ms with PyPy).

             
from itertools import combinations

# minimal difference between generations
diff = 15

sqs = [sq for n in range(1, 20) 
       if 3 * (diff + 1) < (sq := n * n) <= 3 * (99 - diff)]

# find sets of four different values, all less
# than 100, for which any three add to a square
quads = []
# pick four squares (a + b + c, a + b + d, a + c + d, b + c + d)
for sq1, sq2, sq3, sq4 in combinations(sqs, 4):
  a, r = divmod(sq1 + sq2 + sq3 - 2 * sq4, 3)
  if r or a < 1: continue
  
  if (d := sq4 - sq1 + a) > 99: continue
  b, c = sq2 - a - d, sq3 - a - d

  # check difference between generations
  if any(y - x < diff for x, y in zip((a, b, c), (b, c, d))): continue
   
  quads.append((a, b, c, d))

# consider the two events mentioned
for p in quads:
  for q in quads:
    if p == q:
      continue
    #               ages in 1967 
    (d, j, e, a), (s, d_, j_, e_) = p, q
    # the age gap between the two events must 
    # be the same for David, Joseph and Enoch
    if len({d_ - d, j_ - j, e_ - e}) == 1:
      gap = e_ - e
      if s < gap and (ad := a + gap - s) < 100:
        print(f"Adam died in {1967 - s} at age {ad}.")

        Like

        • Jim Randell's avatar

          Jim Randell 10:01 pm on 24 March 2024 Permalink | Reply

          Starting from the squares is an even better idea.

          If we have four ages (a, b, c, d) (in ascending order), and each 3-subset sums to a square number, we have:

          a + b + c = u²
          a + b + d = v²
          a + c + d = w²
          b + c + d = x²

          The squares also appear in ascending order, and the difference between consecutive squares is the difference between consecutive ages.

          Then by summing the equations we get:

          t = a + b + c + d = (u² + v² + w² + x²) / 3

          And given the squares we can recover the ages:

          a = t − x²
          b = t − w²
          c = t − v²
          d = t − u²

          Here’s my version. It has an internal runtime of 349µs.

          Run: [ @replit ]

          from enigma import (powers, sqrtc, sqrtf, subsets, div, singleton, printf)

# generate possible ages
def generate():
  g = 15  # min generation gap
  # find possible sets of 4 squares
  m = 3 + 3*g
  for (u2, v2, w2, x2) in subsets(powers(sqrtc(m), sqrtf(300 - m)), size=4):
    # check generation gaps
    if v2 - u2 < g or w2 - v2 < g or x2 - w2 < g: continue
    # 3(a + b + c + d) = u^2 + v^2 + w^2 + x^2
    t = div(u2 + v2 + w2 + x2, 3)
    if t is None: continue
    # calculate (a, b, c, d)
    (a, b, c, d) = (t - x2, t - w2, t - v2, t - u2)
    if not (0 < a < b < c < d < 100): continue
    printf("[ages = ({d}, {c}, {b}, {a})]")
    yield (d, c, b, a)

# look for ages at the 2 events
for ((A1, E1, J1, D1), (E2, J2, D2, S2)) in subsets(generate(), size=2, select='P'):
  # gap between events
  g = singleton({E2 - E1, J2 - J1, D2 - D1})
  if g is None or not (g > 0): continue
  # event 2 is in 1967
  y2 = 1967
  y1 = y2 - g
  printf("{y1} (A={A1} E={E1} J={J1} D={D1}) -> {y2} (E={E2} J={J2} D={D2} S={S2})")
  b = y1 - A1  # A's birth year
  d = y2 - S2  # A's death year = S's birth year
  # check timeline
  if not (y1 + 1 < d < 100 + b): continue
  # output solution
  printf("-> A born {b}; died {d}, aged {a}", a=d - b)

          Like

  • Unknown's avatar

    Jim Randell 4:39 pm on 22 March 2024 Permalink | Reply
    Tags:   

    Teaser 3209: All in order 

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

    Audley’s age is a two-figure number. He has that number of cards and on them he has spelt out the consecutive numbers from one up to and including his age, (“one”, “two”, etc) with one number on each card.

    Then he has arranged the cards in a row in alphabetical order. It turns out that two of the numbers are in the “correct” place (i.e. in the same place as if he had arranged the cards in numerical order).

    If he had done all this a year ago, or if he repeated this whole exercise in a year’s time, there would be no card in the correct place.

    How old is he?

    [teaser3209]

     
    • Jim Randell's avatar

      Jim Randell 4:51 pm on 22 March 2024 Permalink | Reply

      This Python program generates (age, correct) pairs for increasing ages, and then looks for a sequence of (0, 2, 0) occurring in the correct values, to find the required age.

      It runs in 58ms. (Internal runtime is 585µs).

      Run: [ @replit ]

      from bisect import insort
from enigma import (irange, inf, int2words, tuples, unzip, printf)

# generate (<age>, <correct>) values for increasing ages
def generate(m=inf):
  # numbers in order (numerically and alphabetically)
  (num, lex) = (list(), list())
  for n in irange(1, m):
    # insert the next number
    w = int2words(n)
    num.append(w)
    insort(lex, w)
    # how many are in the correct position?
    p = sum(x == y for (x, y) in zip(lex, num))
    yield (n, p)

# find triples of (<age>, <correct>) with <correct> = 0, 2, 0
for ts in tuples(generate(100), 3):
  (ages, ps) = unzip(ts)
  if ps == (0, 2, 0) and 9 < ages[1] < 100:
    printf("{ages} -> {ps}")

      Solution: Audley is 87.

      The two numbers in the correct position are “eleven” and “sixty two”.

      The next time it would happen is when Audley is 172.

      Like

      • Jim Randell's avatar

        Jim Randell 8:39 am on 24 March 2024 Permalink | Reply

        Or a version that considers ages in decreasing order:

        It runs in 63ms. (Internal runtime is 517µs).

        Run: [ @replit ]

        from enigma import (irange, int2words, tuples, unzip, printf)

# generate (<age>, <correct>) values for decreasing ages
def generate(n):
  # numbers in alphabetical order
  lex = sorted(irange(1, n), key=int2words)
  # consider decreasing ages
  while lex:
    # how many in the correct position
    k = sum(x == i for (i, x) in enumerate(lex, start=1))
    yield (n, k)
    lex.remove(n)
    n -= 1

# find triples of (<age>, <correct>) with <correct> = 0, 2, 0
for ts in tuples(generate(100), 3):
  (ages, ps) = unzip(ts)
  if ages[1] < 10: break
  if ps == (0, 2, 0):
    printf("{ages} -> {ps}")

        Like

    • Frits's avatar

      Frits 5:25 pm on 22 March 2024 Permalink | Reply

      Used some code from [ https://s2t2.home.blog/2021/04/15/teaser-2786-out-of-order/ ]

       
from bisect import insort

upto19 = ['', 'one', 'two', 'three', 'four', 'five', 'six', 'seven',
          'eight', 'nine', 'ten', 'eleven', 'twelve', 'thirteen',
          'fourteen', 'fifteen', 'sixteen', 'seventeen', 'eighteen',
          'nineteen']
asof20 = ['twenty', 'thirty', 'forty', 'fifty', 'sixty', 'seventy',
          'eighty', 'ninety']

# convert integer to word
i2w = lambda i: "one hundred" if i == 100 else upto19[i] if i < 20 else \
                asof20[(i - 20) // 10] + " " + upto19[(i - 20) % 10]
               
n_order = [i2w(n) for n in range(1, 9)]
a_order = sorted(n_order)
last3 =[-1, -1, -1]

# also consider two ages outside Audley's age boundaries
for a in range(9, 101):
  # age as a word
  w = i2w(a)
  # cards in numerical order
  n_order.append(w)
  # insert into a list in alphabetical order
  insort(a_order, w)

  # numbers in the "correct" place
  n_correct = sum(x == y for x, y in zip(n_order, a_order))
  if (last3 := last3[1:] + [n_correct]) == [0, 2, 0]:
    print(f"answer: {a - 1}")

      Like

      • Frits's avatar

        Frits 11:59 am on 23 March 2024 Permalink | Reply

        First item of ‘upto19’ can also be set to ‘\b’ (backspace) to remove the trailing blank for numbers 20, 30, 40, …

        Like

  • Unknown's avatar

    Jim Randell 10:26 am on 21 March 2024 Permalink | Reply
    Tags:   

    Brainteaser 1647: Happy Easter 

    From The Sunday Times, 3rd April 1994 [link]

    Here is a sum with an odd total in which digits have been consistently replaced by letters, different letters being used for different digits:

    Find the value of EGGS.

    [teaser1647]

     
    • Jim Randell's avatar

      Jim Randell 10:27 am on 21 March 2024 Permalink | Reply

      Using the [[ SubstitutedExpression ]] solver from the enigma.py library.

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

      Run: [ @replit ]

      #! python3 -m enigma -rr

SubstitutedExpression.split_sum

# the alphametic sum
"DEAR + READER + HAPPY = EASTER"

# the total is odd
--extra="R % 2 = 1"

--answer="EGGS"

      Solution: EGGS = 4882.

      The sum is: 1403 + 340143 + 60997 = 402543.

      Which assigns 9 of the ten digits, leaving G = 8.

      Like

    • GeoffR's avatar

      GeoffR 7:03 pm on 21 March 2024 Permalink | Reply 

      from itertools import permutations
digits = set('0123456789')

for R in (1,3,5,7,9):
    r = str(R)
    q1 = digits - {r}
    for p1 in permutations(q1, 3):
        d, e, a = p1
        dear = int(d + e + a + r)
        reader = int(r + e + a + d + e + r)
        q2 = q1 - set(p1)
        for p2 in permutations(q2, 3):
            h, p, y = p2
            happy = int(h + a+ p + p + y)
            EASTER = dear + reader + happy
            easter = str(EASTER)
            if easter[0] == e and easter[4] == e:
                if easter[1] == a and easter[-1] == r:
                   s, t = easter[2], easter[3]
                   used = set((e, a, s, t, r, d, h, p, y))
                   if len(used) == 9:
                       g = digits - used
                       G = int(g.pop())
                       E, S = int(e), int(s)
                       EGGS = 1000*E + 110*G +  S
                       print(f"EGGS = {EGGS}")
                       print(f"Sum: {dear} + {reader} + {happy} = {EASTER}")
# EGGS = 4882           
# Sum: 1403 + 340143 + 60997 = 402543

      Like

    • Frits's avatar

      Frits 11:11 am on 22 March 2024 Permalink | Reply 

      from functools import reduce

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

dgts = set(range(10))

# R is odd as total is odd but not 5 (Y becomes 5) or 9 (E becomes 10)
for R in [1, 3, 7]:
  if len(q1 := dgts - {R, E := R + 1, Y := 10 - R}) != 7: continue
  for A in q1:
    # carry + E + H = 10 + A --> A < carry + E
    if not (A < 2 + E): continue
   
    if len(q2 := q1 - {A, P := 9 - A}) != 5: continue
    APPY = d2n([A, P, P, Y])
    for D in q2:
      if D == 0: continue
      DEAR = d2n([D, E, A, R])
      READER = d2n([R, E, A, D, E, R])
   
      # sum last 4 columns
      carry, tot = divmod(DEAR + READER % 10000 + APPY, 10000)
      # carry + E + H = 10 + A
      H = 10 + A - carry - E
      if H in {0, D} or H not in q2: continue
     
      # tot must be equal to STER
      S, T = divmod(tot // 100, 10)
   
      if len(q3 := q2 - {D, H, S, T}) != 1: continue
     
      HAPPY = 10000 * H + APPY
      EASTER = d2n([E, A, S, T, E, R])
      if DEAR + READER + HAPPY != EASTER: continue

      print(f"answer: EGGS = {d2n([E, (G := q3.pop()), G, S])}")
      '''
      print()
      print(f"{DEAR:>6}")
      print(f"{READER:>6}")
      print(f"{HAPPY:>6}")
      print("------")
      print(f"{EASTER:>6}")
      '''

      Like

    • Ruud's avatar

      Ruud 6:42 am on 21 April 2024 Permalink | Reply

      Brute force, extremely simple, solution. Runs within 30 seconds …

      import itertools
from istr import istr

for d, e, a, r, h, p, y, s, t,g in istr(itertools.permutations("0123456789", 10)):
    if r.is_odd() and (d | e | a | r) + (r | e | a | d | e | r) + (h | a | p | p | y) == (e | a | s | t | e | r):
        print('eggs = ', e|g|g|s)

      Like

      • Frits's avatar

        Frits 10:55 am on 22 April 2024 Permalink | Reply

        Hi Ruud, with CPython your version runs for 140seconds on my PC. A similar program without the istr package runs for 3 seconds with CPython (PyPy is faster).

        from itertools import permutations
 
for d, e, a, r, h, p, y, s, t, g in permutations("0123456789"):
  if (r in "13579" and "0" not in (d + r + h + e) and
      int(d+e+a+r) + int(r+e+a+d+e+r) + int(h+a+p+p+y) == int(e+a+s+t+e+r)):
    print('eggs = ', e+g+g+s)

        Like

    • GeoffR's avatar

      GeoffR 11:10 am on 21 April 2024 Permalink | Reply

      Using primary school addition method of columns and carry digits.

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

var 1..9:D; var 1..9:E; var 0..9:A; var 1..9:R;
var 0..9:S; var 0..9:T; var 0..9:G; var 1..9:H;
var 0..9:P; var 0..9:Y;
var 1000..9999:EGGS = 1000*E + 110*G + S;

constraint R in {1,3,5,7,9};

% Column carry digits from right hand end
var 0..2:c1; var 0..2:c2; var 0..2:c3; var 0..2:c4; var 0..2:c5; 

constraint all_different ([D, E, A, R, S, T, G, H, P, Y]);

% Adding columns from the right hand end
constraint (R + R + Y) mod 10 == R /\ c1 == (R + R + Y) div 10;
constraint (c1 + A + E + P) mod 10 == E /\ c2 == (c1 + A + E + P) div 10;
constraint (c2 + E + D + P) mod 10 == T /\ c3 ==  (c2 + E + D + P) div 10;
constraint (c3 + D + A + A) mod 10 == S /\ c4 ==  (c3 + D + A + A) div 10;
constraint (c4 + E + H) mod 10 == A /\ c5 == (c4 + E + H) div 10;
constraint E == R + c5;

solve satisfy;
output ["EGGS = " ++ show(EGGS) ++ "\n" 
++ "([D, E, A, R, S, T, G, H, P, Y] = "  ++ show([D, E, A, R, S, T, G, H, P, Y]  )];
 
% EGGS = 4882
% ([D, E, A, R, S, T, G, H, P, Y] = 
%  [1, 4, 0, 3, 2, 5, 8, 6, 9, 7]
% ----------
% ==========

      Like

  • Unknown's avatar

    Jim Randell 8:54 am on 19 March 2024 Permalink | Reply
    Tags:   

    Teaser 2673: Footprints 

    From The Sunday Times, 15th December 2013 [link] [link]

    A cubical dice, with faces labelled as usual, is placed in one of the nine squares of a three-by-three grid, where it fits exactly. It is then rotated about one of its edges into an adjacent square and this is done a total of eight times so that the dice visits each square once. The “footprint” of the route is the total of the nine faces that are in contact with the grid.

    (a) What is the lowest footprint possible?
    (b) What is the highest footprint possible?
    (c) Which whole numbers between those two values cannot be footprints?

    [teaser2673]

     
    • Jim Randell's avatar

      Jim Randell 8:55 am on 19 March 2024 Permalink | Reply

      I used the [[ Cube() ]] class to deal with rotations of the standard die (see: Teaser 2835).

      This Python program considers possible representative starting squares on the grid (a corner, an edge, the centre square) using a standard right-handed die, and then positioning it in all possible orientations it looks for possible footprint values as it moves around the grid. (We get the same results with the remaining squares on the grid, and also if we were to use a left-handed die).

      It runs in 82ms. (Internal runtime is 17ms).

      Run: [ @replit ]

      from enigma import (irange, append, diff, printf)
from cube import (Cube, U, D, L, R, F, B)

# possible moves:
#
#  1 2 3
#  4 5 6
#  7 8 9
#
move = {
  1: { F: 2, L: 4 },
  2: { B: 1, F: 3, L: 5 },
  3: { B: 2, L: 6 },
  4: { R: 1, F: 5, L: 7 },
  5: { R: 2, B: 4, F: 6, L: 8 },
  6: { R: 3, B: 5, L: 9 },
  7: { R: 4, F: 8 },
  8: { R: 5, B: 7, F: 9 },
  9: { R: 6, B: 8 },
}

# calculate footprint totals
# d = current die orientation
# i = current die position
# t = accumulated footprint total
# vs = visited positions
def footprints(d, i, t=0, vs=set()):
  # add in the value on the D face
  t += d.faces[D]
  vs = append(vs, i)
  # have we visited each square in the grid?
  if len(vs) == 9:
    yield t
  else:
    # make a move
    for (r, j) in move[i].items():
      if j not in vs:
        yield from footprints(d.rotate([r]), j, t, vs)

# a standard die (U, D, L, R, F, B)
die = (1, 6, 2, 5, 3, 4)

# accumulate footprint totals
ts = set()
# consider possible starting squares: corner = 1, edge = 2, centre = 5
for i in [1, 2, 5]:
  # consider possible initial orientations for the die
  for d in Cube(faces=die).rotations():
    # calculate footprint totals
    ts.update(footprints(d, i))

# calculate min/max footprints
(a, b) = (min(ts), max(ts))
# output solution
printf("min = {a}; max = {b}; missing = {ms}", ms=diff(irange(a, b), ts))

      Solution: (a) The minimum possible footprint is 21; (b) The maximum possible footprint is 42; (c) 29 and 34 cannot be footprints.

      The following paths starting in the centre square (5) and visiting (5, 6, 3, 2, 1, 4, 7, 8, 9) (i.e. spiralling out from the centre) give the minimum and maximum:

      (1); F → (2); R → (4); B → (1); B → (3); L → (2); L → (4); F → (1); F → (3) = footprint 21
      (6); F → (5); R → (4); B → (6); B → (3); L → (5); L → (4); F → (6); F → (3) = footprint 42

      With a bit of analysis we can get a faster program:

      There are only 3 essentially different paths (every other path is a reflection/rotation/reversal of one of these):

      If we start at the beginning of one of these paths with a die showing (x, y, z) around one corner, and opposite faces (X, Y, Z) (so x + X = y + Y = z + Z = 7), then we get the following footprints:

      X + z + x + y + z + Y + X + z + x = 21 + 3z
      X + z + x + y + X + z + x + y + z = 14 + 2y + 3z
      X + z + y + X + Z + y + z + X + Z = 14 + 2y + 3X

      (y, z) = (2, 1) gives a minimum of 21 in second equation, and (y, z) = (5, 6) gives a maximum of 42.

      We can examine the full range of footprints by considering the value of 1 face in the first equation, and 2 adjacent faces in the second (or third) equation.

      This Python program examines all possible footprints, and has an internal runtime of 63µs.

      Run: [ @replit ]

      from enigma import (irange, diff, printf)

# calculate footprint totals
scores = [1, 2, 3, 4, 5, 6]
ts = set()
for x in scores:
  ts.add(21 + 3*x)
  for y in scores:
    if x == y or x + y == 7: continue
    ts.add(14 + 2*x + 3*y)

# calculate min/max footprints
(a, b) = (min(ts), max(ts))
# output solution
printf("min = {a}; max = {b}; missing = {ms}", ms=diff(irange(a, b), ts))

      Like

  • Unknown's avatar

    Jim Randell 8:28 am on 17 March 2024 Permalink | Reply
    Tags:   

    Brain-Teaser 948: Journey north-east 

    From The Sunday Times, 21st September 1980 [link]

    For the purpose of my problem I have to choose two towns 26 miles apart. I might have chosen Oxford and Newbury, but it would be more appropriate for me as a Scotsman to go much farther north and choose Kingussie and Grantown-on-Spey, where the roads are somewhat less busy.

    Alf, Bert and Charles start off at the same time from Kingussie to make their way north-eastwards to Grantown-on-Spey, 26 miles distant.

    Alf walks at a constant speed of four miles per hour. Bert and Charles drive together in a car. After a certain time, Bert leaves the car, and walks forward at the same rate as Alf, while Charles drives back to meet Alf.

    Alf gets Into the car with Charles, and they continue to drive to Grantown-on-Spey, arriving there just as Bert does.

    On each stretch Charles averages 40 miles per hour.

    What is the time (in minutes) taken for them all to travel from Kingussie to Grantown-on-Spey?

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

    [teaser948]

     
    • Jim Randell's avatar

      Jim Randell 8:29 am on 17 March 2024 Permalink | Reply

      See: Teaser 3140, where we determined:

      If there are k pedestrians to be transported a distance d, and each walks a distance x at velocity w and is transported a distance (d − x) at velocity v, and the total time taken is t, then we have:

      n = 2k − 1
      x = dw(n − 1) / (v + wn)
      t = d(w + vn) / v(v + wn)

      We can plug the numbers for this puzzle in and calculate the result:

      Run: [ @replit ]

      from enigma import (fdiv, printf)

# initial conditions
k = 2   # number of walkers
d = 26  # distance
w = 4   # walking speed
v = 40  # driving speed

# calculate walking distance per person
n = 2 * k - 1
x = fdiv(d * w * (n - 1), v + w * n)

# calculate time taken
t = fdiv(x, w) + fdiv(d - x, v)

# output solution
printf("t = {t:g} hours (= {m:g} min) [x={x:g} miles]", m=t * 60)

      Solution: The total time taken is 93 minutes.

      Alf walks the first 4 miles (in 60 minutes), and is driven the remaining 22 miles (in 33 minutes).

      Bert is driven 22 miles first, and walks the last 4 miles.

      Charles drives 22 miles to drop off Bert, returns 18 miles to collect Alf, and then 22 miles to the destination, a total of 62 miles (in 93 minutes).

      So each arrives at the destination after 93 minutes.

      Like

    • Lise Andreasen's avatar

      Lise Andreasen 4:22 pm on 4 April 2024 Permalink | Reply

      Alf walks x miles. For symmetry reasons, Bert also walks x miles. In the middle we have y miles. 26 = x + y + x.
      They all spend the same amount of time.
      x/4 + (x+y)/40 = (2x+3y)/40.
      Solve.

      Like

  • Unknown's avatar

    Jim Randell 4:45 pm on 15 March 2024 Permalink | Reply
    Tags:   

    Teaser 3208: The scores are all square 

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

    For Skaredahora’s quartet four players read the same musical score, but from different compass directions. There are symbols of three types, indicating different whole number beat durations, on a square 17×17 grid. Each player reads the beat position in their left-to-right direction, and pitch in their bottom-to-top.

    Each player plays four notes; South reads a plus at (beat,pitch) position (3,12), a circle at (14,1), a cross at (16,3), and a plus at beat 9. For example, if a cross indicates three beats, South plays a note of pitch 3 at beat 16, which is still sounding at beats 17 and 18, while East plays a note of pitch 2 sounding at beats 3, 4 and 5.

    No player sounds more than one note at the same time. All possible pitch differences between notes sounding simultaneously from different players occur, except zero and exactly one other value.

    Which non-zero pitch difference never occurs? What pitch does South play at beat 9?

    [teaser3208]

     
    • Jim Randell's avatar

      Jim Randell 6:10 pm on 15 March 2024 Permalink | Reply

      This program considers possible positions for the unspecified “+” note, and then constructs the notes heard at each beat for each player and checks the remaining constraints.

      It runs in 59ms. (Internal runtime is 1.8ms).

      Run: [ @replit ]

      from enigma import (irange, inf, tuples, cproduct, subsets, diff, singleton, printf)

# fill out beats for notes in <X>, durations <dd>
def beats(X, dd):
  bs = [0] * 22
  for (b, p, d) in X:
    for i in irange(dd[d]):
      i += b
      if bs[i] != 0: return
      bs[i] = p
  return bs

# check a set of beats
def check(bs):
  if None in bs: return
  # find differences between non-zero pitches
  ds = set()
  for ps in zip(*bs):
    ds.update(abs(x - y) for (x, y) in subsets(filter(None, ps), size=2))
  # differences exclude 0 and exactly one other value
  if 0 in ds: return
  return singleton(diff(irange(1, 16), ds))

# duration symbols
ks = "ox+"

# suppose the unspecified '+' is at pitch <x> for S
for x in irange(1, 17):
  # construct the notes (<beat>, <pitch>, <duration>) for each player
  S = [(3, 12, '+'), (9, x, '+'), (14, 1, 'o'), (16, 3, 'x')]
  N = list((18 - b, 18 - p, d) for (b, p, d) in S)
  W = list((18 - p, b, d) for (b, p, d) in S)
  E = list((p, 18 - b, d) for (b, p, d) in S)

  # determine maximum possible note duration
  dm = dict((k, inf) for k in ks)
  for X in [S, N, W, E]:
    for ((a, _, k), (b, _, _)) in tuples(sorted(X), 2):
      dm[k] = min(dm[k], b - a)
  if 0 in dm.values(): continue

  # choose durations
  for ds in cproduct(irange(1, dm[k]) for k in ks):
    if len(set(ds)) != 3: continue
    dd = dict(zip(ks, ds))

    # record pitches on each beat
    (bS, bN, bW, bE) = (beats(X, dd) for X in [S, N, W, E])
    k = check((bS, bN, bW, bE))
    if not k: continue

    # output solution
    printf("S={bS}", bS=bS[1:])
    printf("N={bN}", bN=bN[1:])
    printf("W={bW}", bW=bW[1:])
    printf("E={bE}", bE=bE[1:])
    printf("x={x} dd={dd} -> k={k} S[9]={S9}", S9=bS[9])
    printf()

      Solution: A pitch difference of 4 does not occur. South plays pitch 17 at beat 9.

      The note durations are:

      o = 1 beat
      x = 2 beats
      + = 5 beats

      Here is a diagram of the notes played:

      Like

      • Frits's avatar

        Frits 3:08 pm on 22 March 2024 Permalink | Reply

        @Jim, only thing to improve for a general solution is getting rid of the hardcoded 22 in line 5.

        Like

    • Frits's avatar

      Frits 5:23 pm on 16 March 2024 Permalink | Reply

      Based on part of Jim’s first published program. 

       
from enigma import SubstitutedExpression, subsets

# invalid digit / symbol assignments
d2i = dict()
for d in range(0, 10):
  vs = set()
  if d == 0: vs.update('KLM')
  if d > 1: vs.update('U')
  if d > 2: vs.update('KL') # by manual inspection of S resp. N
  if d > 5: vs.update('M')  # by manual inspection of S
  d2i[d] = vs  

# check for 15 different pitch differences (without zero)
def check(K, L, M, UV):
  S = sorted([(3,      12, M), (9,  UV, M), (14,      1, K), (16,  3, L)])
  E = sorted([(UV,      9, M), (1,   4, K), (3,       2, L), (12, 15, M)])
  N = sorted([(2,      15, L), (4,  17, K), (9, 18 - UV, M), (15,  6, M)])
  W = sorted([(18 - UV, 9, M), (6,   3, M), (15,     16, L), (17, 14, K)])
  d = dict()
  for pl in [S, E, N, W]:
    done = set()  
    for (b, p, s) in pl:
      for j in range(s):
        # no simultaneous notes by the same player
        if (k := b + j - 1) in done: return False
        d[k] = d.get(k, []) + [p]
        done.add(k)
        
  # pitch differences
  diffs = set(abs(p2 - p1) for vs in d.values() for p1, p2 in subsets(vs, 2))
  if 0 in diffs or len(diffs) != 15: return False
  
  return set(range(1, 17)).difference(diffs).pop()


# the alphametic puzzle
p = SubstitutedExpression(
  [ # duration 'o': K, duration 'x': L, duration '+': M
    # the unspecified pitch
    "0 < UV < 18",
    # main checks
    "(missing := check(K, L, M, UV)) != 0",
  ],
  answer="(K, L, M, UV, missing)",
  d2i=d2i,
  # different whole number beat durations
  distinct=("KLM"),
  env=dict(check=check),
  verbose=0,    # use 256 to see the generated code
) 

# print answers
for ans in p.answers():
  print(f"{ans}")
  print("answer: pitch difference that never occurs:", ans[4])
  print("        South plays pitch", ans[3], "at beat 9")

      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