Recent Updates Page 25 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 10:46 am on 11 May 2023 Permalink | Reply
    Tags:   

    Teaser 1978: Sunday study 

    From The Sunday Times, 13th August 2000 [link]

    This TEASER is odd and it needs careful STUDY. Throughout, different letters consistently stand for different non-zero digits. Each letter on the lower line is the sum of the two letters above it (so that, for example, U = A + S).

    What is SUNDAY‘s number?

    [teaser1978]

     
    • Jim Randell's avatar

      Jim Randell 10:47 am on 11 May 2023 Permalink | Reply

      See also: Teaser 1688, Teaser 2533.

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

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

      Run: [ @replit ]

      #! python3 -m enigma -rr

SubstitutedExpression

--digits="1-9"

"T + E = S"
"E + A = T"
"A + S = U"
"S + E = D"
"E + R = Y"

# TEASER is odd
"R % 2 = 1"

--answer="SUNDAY"

      Solution: SUNDAY = 469528.

      Like

    • GeoffR's avatar

      GeoffR 12:09 pm on 11 May 2023 Permalink | Reply 

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

set of int: INT = 1..9;
var INT: T; var INT: E; var INT: A;
var INT: S; var INT: R; var INT: U;
var INT: D; var INT: Y; var INT: N;

constraint all_different([T, E, A, S, R, U, D, Y, N]);

constraint S == T + E /\ T == E + A /\ U == A + S /\ D == S + E
 /\ Y == E + R /\ R mod 2 == 1;

solve satisfy;
output ["SUNDAY = " ++  "\(S)\(U)\(N)\(D)\(A)\(Y)" ];

% SUNDAY = 469528
% ----------
% ==========

      Like

    • GeoffR's avatar

      GeoffR 1:47 pm on 11 May 2023 Permalink | Reply 

      from itertools import permutations

digits = {1, 2, 3, 4, 5, 6, 7, 8, 9}

for p1 in permutations(range(1, 10), 4):
    T, E, A, S = p1
    if S != T + E:continue
    if T != E + A:continue
    
    # find 5 remaining digits
    q1 = digits.difference(p1)
    for p2 in permutations(q1):
       U, D, R, Y, N = p2
       if U != A + S:continue
       if D != S + E:continue
       if R % 2 != 1:continue  # TEASER is odd
       if Y != E + R:continue
       SUNDAY = 100000*S + 10000*U + 1000*N + 100*D + 10*A + Y
       print('SUNDAY = ', SUNDAY)

      Like

  • Unknown's avatar

    Jim Randell 9:11 am on 9 May 2023 Permalink | Reply
    Tags:   

    Teaser 2628: Unnaturally quiet 

    From The Sunday Times, 3rd February 2013 [link] [link]

    I have given each letter of the alphabet a different value from 0 to 25, so some letters represent a single digit and some represent two digits. Therefore, for example, a three-letter word could represent a number of three, four, five or six digits. With my values it turns out that:

    NATURAL = NUMBER.

    What is the sum of the digits in the number MUTE?

    [teaser2628]

     
    • Jim Randell's avatar

      Jim Randell 9:15 am on 9 May 2023 Permalink | Reply

      Presumably the value of a word is the number formed by the concatenation of the digits in the values for each letter.

      So we are looking for assignments that make ATURAL = UMBER (as the value of N is immaterial).

      This Python program looks for assignments of letters to numeric values that make the translated versions of the strings equal. It does this by assigning values to the leading letters that allow the corresponding digits to match.

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

      from enigma import (irange, subsets, filter2, group, item, update, remove, translate, join, catch, printf)

# replace letters in <X>, <Y> with numeric values from <ns>, so the numeric strings formed are equal
# <ns> groups values by their first digit
# return the map: letter -> value
def _solve(X, Y, ns, d):
  # are we done?
  if X == Y:
    yield d
  elif X and Y:
    # remove any common prefix
    while X and Y and X[0] == Y[0]: (X, Y) = (X[1:], Y[1:])
    if not (X and Y): return
    # split the leading characters into numeric / non-numeric
    (nums, nons) = filter2((lambda x: x.isdigit()), [X[0], Y[0]])
    # different leading numerics = failure
    if len(nums) > 1: return
    # choose values with the same leading digit
    # if there is a numeric value use that, otherwise use the groups
    for k in (nums or ns.keys()):
      ss = ns.get(k, [])
      for vs in subsets(ss, size=len(nons), select='P'):
        # update the strings
        d_ = update(d, nons, vs)
        (X_, Y_) = (translate(x, d_, embed=0) for x in (X, Y))
        ns_ = update(ns, [(k, remove(ss, *vs))])
        # and solve for the translated strings
        yield from _solve(X_, Y_, ns_, d_)

# replace letters in <X>, <Y>
def solve(X, Y, ns):
  # group numeric values (as strings) by their leading digit
  ns = group(map(str, ns), by=item(0), fn=set)
  # and call the solver
  return _solve(X, Y, ns, dict())

# possible values
ns = irange(0, 25)

# word values we are interested in
(w1, w2, w3) = ("NATURAL", "NUMBER", "MUTE")

# turn a word into a string
fmt = lambda w, sep=':': join((d.get(x, x) for x in w), sep=sep)
# calculate digit sum
dsum = lambda w: sum(map(int, fmt(w, sep='')))

# solve the puzzle
for d in solve(w1, w2, ns):
  # sum the digits in w3
  s = catch(dsum, w3)
  if s is not None:
    # output solution
    printf("dsum({w3}) = {s} [{w1}={f1} {w2}={f2} {w3}={f3}]", f1=fmt(w1), f2=fmt(w2), f3=fmt(w3))

      Solution: The sum of the digits in MUTE is 12.

      M and U are 12 and 21, in some order. And T and E are 11 and 22, in some order.

      So MUTE is either “12:21:11:22” or “21:12:22:11”. Either way there are four copies of each of the digits “1” and “2”.

      There are 8 ways to assign the letters in ATURAL and UMBER (and N can be any of the remaining values).

      The assignments are of the form:

      NATURAL = N:x:yy:xy:z:x:xz
      NUMBER = N:xy:yx:yz:xx:z

      where: (x, y) are (1, 2), in some order; and z ∈ {0, 3, 4, 5}.

      As noted by Brian Gladman [link], it is more efficient if the words are considered starting at the end, rather than the beginning.

      I think this is because there are many values with leading characters of “1” and “2”, but when values are grouped by their final character they form into much smaller sets (max size = 3).

      The internal runtime of my code is about twice as fast if the words and values are simply reversed (and the answer is the same). But it is straightforward to adapt the program to process the strings from the end.

      This program runs in 90ms. (Internal runtime is 33ms).

      from enigma import (irange, subsets, filter2, group, item, update, remove, translate, join, catch, printf)

# replace letters in <X>, <Y> with numeric values from <ns>, so the numeric strings formed are equal
# <ns> groups values by their final digit
# return the map: letter -> value
def _solve(X, Y, ns, d=dict()):
  # are we done?
  if X == Y:
    yield d
  elif X and Y:
    # remove any common suffix
    while X and Y and X[-1] == Y[-1]: (X, Y) = (X[:-1], Y[:-1])
    if not (X and Y): return
    # split the final characters into numeric / non-numeric
    (nums, nons) = filter2((lambda x: x.isdigit()), [X[-1], Y[-1]])
    # different final numerics = failure
    if len(nums) > 1: return
    # choose values with the same final digit
    # if there is a numeric value use that, otherwise use the groups
    for k in (nums or ns.keys()):
      ss = ns.get(k, [])
      for vs in subsets(ss, size=len(nons), select='P'):
        # update the strings
        d_ = update(d, nons, vs)
        (X_, Y_) = (translate(x, d_, embed=0) for x in (X, Y))
        ns_ = update(ns, [(k, remove(ss, *vs))])
        # and solve for the translated strings
        yield from _solve(X_, Y_, ns_, d_)

# replace letters in <X>, <Y>
def solve(X, Y, ns):
  # group numeric values (as strings) by their final digit
  ns = group(map(str, ns), by=item(-1), fn=set)
  # and call the solver
  return _solve(X, Y, ns, dict())

# possible numeric values
ns = irange(0, 25)

# word values we are interested in
(w1, w2, w3) = ("NATURAL", "NUMBER", "MUTE")

# turn a word into a string
fmt = lambda w, sep=':': join((d.get(x, x) for x in w), sep=sep)
# calculate digit sum
dsum = lambda w: sum(map(int, fmt(w, sep='')))

# solve the puzzle
for d in solve(w1, w2, ns):
  # sum the digits in w3
  s = catch(dsum, w3)
  if s is not None:
    # output solution
    printf("dsum({w3}) = {s} [{w1}={f1} {w2}={f2} {w3}={f3}]", f1=fmt(w1), f2=fmt(w2), f3=fmt(w3))

      Like

  • Unknown's avatar

    Jim Randell 4:40 pm on 5 May 2023 Permalink | Reply
    Tags:   

    Teaser 3163: Letterboxes 

    From The Sunday Times, 7th May 2023 [link] [link]

    To enable me to spell out ONE, TWO, up to NINE one or more times, I bought large quantities of the letters E, F, G, H, I, N etc. Then in a box labelled “ONE” I put equal numbers of Os, Ns and Es; in a second box labelled “TWO” I put equal numbers of Ts, Ws and Os; in box “THREE” I put equal numbers of Ts, Hs and Rs, together with double that number of Es; etc.

    In this way I made nine boxes from which my grandson could take out complete sets to spell out the relevant digit. In total there was a prime number of each of the letters, with equal numbers of Ns and Vs, but more Ts. Furthermore, the grand total number of letters in the boxes was a two-figure prime.

    In the order ONE to NINE, how many sets were in each box?

    [teaser3163]

     
    • Jim Randell's avatar

      Jim Randell 5:04 pm on 5 May 2023 Permalink | Reply

      This Python program chooses a word at each stage that has a letter not involved in any of the remaining words. So we can then start adding copies of the word to the total collection of letters, and when the uninvolved letters all have a prime number of copies, we can look to solve for the remaining words. And we do this while there are less than 100 letters in the total collection. In this way we exhaustively explore the solution space.

      The collection of words we are given is such that there is always at least one word at each stage that has letters not involved in the remaining words.

      This Python program runs in 166ms. (Internal runtime is 108ms).

      from enigma import (defaultdict, irange, inf, is_prime, multiset, peek, remove, update, map2str, printf)

# map letters to the words they appear in
def group(ns):
  g = defaultdict(set)
  for n in ns:
    for k in set(n):
      g[k].add(n)
  return g

# solve for remaining words <ws>, such that the count of each letter is prime
# m = current allocation of letters
# d = map of words used to number of repetitions
# return (m, d)
def solve(ns, m=multiset(), d=dict()):
  # are we done?
  if not ns:
    yield (m, d)
  else:
    g = group(ns)
    # choose a letter with the minimum number of words
    k = min(g.keys(), key=(lambda k: len(g[k])))
    # choose a word
    w = peek(g[k])
    ns_ = remove(ns, w)
    # letters that no longer appear
    xs = set(w).difference(*ns_)
    # add in sets of letters for this word
    m_ = m.copy()
    for i in irange(1, inf):
      m_.update_from_seq(w)
      if m_.size() > 99: break
      # any letters that no longer appear must be prime
      if not all(is_prime(m_.count(x)) for x in xs): continue
      # attempt to solve for the remaining words
      yield from solve(ns_, m_, update(d, [(w, i)]))

# solve the puzzle for the given labels
words = "ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE".split()
for (m, d) in solve(words):
  # total number of letters is prime
  if not is_prime(m.size()): continue
  # total number of N's and V's is the same and there are more T's
  if not (m.count('T') > m.count('N') == m.count('V')): continue
  # valid solution found, output the counts for the labels
  for w in words:
    printf("{k}x {w}", k=d[w])
  printf("total letters = {n} {m}", n=m.size(), m=map2str(m))
  printf()

      Solution: The numbers of sets are:

      1× ONE
      2× TWO
      3× THREE
      2× FOUR
      3× FIVE
      5× SIX
      2× SEVEN
      2× EIGHT
      1× NINE

      This gives a (prime) total of 83 letters.

      The individual letter counts are:

      E=17
      F=5
      G=2
      H=5
      I=11
      N=5
      O=5
      R=5
      S=7
      T=7
      U=2
      V=5
      W=2
      X=5

      Like

      • Jim Randell's avatar

        Jim Randell 6:28 pm on 5 May 2023 Permalink | Reply

        Or using the [[ SubstitutedExpression() ]] solver from the enigma.py library, we can construct an alphametic equivalent of the puzzle and solve that (although it assumes there are no more than 9 sets of letters in any box (but you can use a higher base parameter to allow more, allowing up to 16 sets is sufficient to provide an exhaustive search)).

        The following Python program runs in 64ms. (Internal runtime of the generated program is 2.3ms).

        from enigma import (SubstitutedExpression, irange, is_prime, union, join, sprintf, multiset, str_upper, map2str, printf)

# the labels for the boxes
words = "ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE".split()

# make symbols for each word
symbols = dict(zip(words, str_upper))

# make an expression from a multiset of symbols
def expr(m):
  ts = list()
  for (s, n) in m.items():
    if n == 1:
      ts.append(s)
    elif n > 0:
      ts.append(sprintf("{n}*{s}"))
  return join(ts, sep=" + ")

# make a symbol count for each letter
xs = dict((k, multiset()) for k in union(words))
for (w, s) in symbols.items():
  for k in w:
    xs[k].add(s)

# construct the expressions:

# each letter count is prime
exprs = list(sprintf("is_prime({x})", x=expr(m)) for (k, m) in xs.items())

# the total letter count is prime
m = multiset.from_pairs((s, len(w)) for (w, s) in symbols.items())
exprs.append(sprintf("is_prime_2d({x})", x=expr(m)))

# N count = V count
(m1, m2) = xs['N'].differences(xs['V'])
exprs.append(sprintf("{x1} == {x2}", x1=expr(m1), x2=expr(m2)))

# T count > V count
(m1, m2) = xs['T'].differences(xs['V'])
exprs.append(sprintf("{x1} > {x2}", x1=expr(m1), x2=expr(m2)))

# construct the alphametic problem
p = SubstitutedExpression(
  exprs,
  digits=irange(1, 9),
  distinct=[],
  env=dict(is_prime_2d=lambda n: 9 < n < 100 and is_prime(n)),
  verbose=0
)

# solve it
for r in p.solve():
  # output solution
  m = multiset()
  for w in words:
    n = r[symbols[w]]
    printf("{n}x {w}")
    m.update_from_seq(w, count=n)
  printf("total letters = {n} {m}", n=m.size(), m=map2str(m))
  printf()

        Like

    • Frits's avatar

      Frits 10:41 pm on 5 May 2023 Permalink | Reply

      Just a basic program with hard coded logic.

      A following step could be to remove this logic and generate a solution like with SubstitutedExpression().

       
from enigma import int2words

lenwords = [len(int2words(i)) for i in range(1, 10)]

# primes up to 99
P = {3, 5, 7}
P |= {2} | {x for x in range(11, 100, 2) if all(x % p for p in P)}
smallP = sorted(P)[:4]

# (n1, n2, n3, n4, n5, n6, n7, n8, n9): the number of sets in each box
# assumption: there are no more than 9 sets of letters in any box

for n8 in smallP:                    
  for n3 in range(1, 10):                 
    if (n3 + n8) not in P: continue  # number of Hs  
    for n2 in smallP:               
      if (n2 + n3 + n8) not in P: continue # number of Ts 
      for n4 in smallP:             
        if (n3 + n4) not in P: continue # number of Rs 
        for n5 in range(1, 10):     
          if (n4 + n5) not in P: continue # number of Fs
          for n7 in range(1, 10):   
            if (n5 + n7) not in P: continue # number of Vs
            if not (n2 + n3 + n8 > n5 + n7): continue # more Ts than Vs
            for n9 in range(1, 10): 
              n1 = n5 - 2 * n9           # equal numbers of Ns and Vs
              if not (0 < n1 < 10): continue 
              if (n1 + n2 + n4) not in P: continue     # number of Os
              
              if (n1 + 2*n3 + n5 + 2*n7 + n8 + n9) not in P: # number of Es
                continue 
              for n6 in smallP:     
                if (n5 + n6 + n8 + n9) not in P: continue # number of Is
                if (n6 + n7) not in P: continue # number of Ss
                
                # total is also prime
                answer = (n1, n2, n3, n4, n5, n6, n7, n8, n9)
                T = sum(x * y for x, y in zip(answer, lenwords))
                if T not in P: continue 
                print(answer)

      Like

    • Frits's avatar

      Frits 12:50 pm on 6 May 2023 Permalink | Reply

      The following program emulates SubstitutedExpression() from the enigma library.
      The programs runs fast (6 ms) although the order of rows in list lst doesn’t seem to be optimal.

         
from enigma import int2words

# return calculation string number of occurrences of character <c>
def N(c):
  seq = [x[1] for x in lst if x[0] == c][0]
  # check if enough variables available
  if any(not sofar[i] for i, x in enumerate(seq) if x): return ""
  
  return ' + '.join(("n" if x == 1 else str(x) + "*n") + str(i) 
         for i, x in enumerate(seq, 1) if x)

# primes up to 99
P = {3, 5, 7}
P |= {2} | {x for x in range(11, 100, 2) if all(x % p for p in P)}
smallP = sorted(P)[:4]

words = [int2words(i).upper() for i in range(1, 10)]
lenwords = [len(w) for w in words]

letters = "".join(set("".join(words)))

# list of characters and usage within words
lst = [(c, [w.count(c) for w in words]) for c in letters] 
# sort characters  (least usage first)
lst.sort(key=lambda x: sum(x[1]))

# (n1, n2, n3, n4, n5, n6, n7, n8, n9): the number of sets in each box
# assumption: there are no more than 9 sets of letters in any box

# list of variable names which may only be a prime number     
primes = {"n" + str([i for i, y in enumerate(x[1], 1) if y][0]) 
          for x in lst if sum(x[1]) == 1}    
          
sofar = [1 for _ in range(10)]      

# additional conditions
extra = [("# equal numbers of Ns and Vs\n",
          "if not(" + N('N') + " == " + N('V') + "): continue\n"),
         ("# more Ts than Vs\n",
          "if not(" + N('T') + " > " + N('V') + "): continue\n")]          

ex = ind = done = ""
sofar = [0 for _ in range(10)]
for c, seq in lst:
  # check which variables in <seq> have not been used sofar
  new = [i for i, (x, y) in enumerate(zip(seq, sofar), 1) if not y and x != y]
  
  for nv in new:
    var = "n" + str(nv)
    r = "smallP" if var in primes else "range(1, 10)"
  
    # add for loop for new variable
    ex += ind + "for " + var + " in " + r + ":\n"
    sofar[nv - 1] = 1
    ind += "  "
  
    # add prime checks 
    for c2 in [ch for ch, sq in lst if ch not in done and sum(sq) > 1]:
      # function N checks if enough variables are available
      n = N(c2)   # number of occurrences of character <c2>
      if n:       
        ex += ind + "if (" + n + ") not in P: continue # number of "
        ex += c2 + "s \n"
        done += c2
    
    # add extra conditions if enough variables are available
    sofar_vars = set("n" + str(i) for i, x in enumerate(sofar, 1) if x)
    for comm, cond in extra.copy():
      nvars = cond.count('+') + 2
      # do we have enough variable in <sofar_vars>?
      if nvars == sum(sv in cond for sv in sofar_vars):
        ex += ind + comm
        ex += ind + cond
        extra.remove((comm, cond)) # no need to process condition again

# remaining conditions        
for comm, cond in extra:  
  ex += ind + comm
  ex += ind + cond
  
# add additional conditions to most inner loop
ex += ind + "\n"
ex += ind + "# total is also prime\n"
ex += ind + "answer = (n1, n2, n3, n4, n5, n6, n7, n8, n9)\n"
ex += ind + "T = sum(x * y for x, y in zip(answer, lenwords))\n"
ex += ind + "if T not in P: continue\n" 

ex += ind + "print('answer:', answer)\n"

#print(ex)  
exec(ex)

      with the following generated code:

         
for n2 in smallP:
  for n8 in smallP:
    for n6 in smallP:
      for n4 in smallP:
        for n5 in range(1, 10):
          if (n4 + n5) not in P: continue # number of Fs
          for n7 in range(1, 10):
            if (n5 + n7) not in P: continue # number of Vs
            if (n6 + n7) not in P: continue # number of Ss
            for n3 in range(1, 10):
              if (n3 + n4) not in P: continue # number of Rs
              if (n3 + n8) not in P: continue # number of Hs
              if (n2 + n3 + n8) not in P: continue # number of Ts
              # more Ts than Vs
              if not(n2 + n3 + n8 > n5 + n7): continue
              for n1 in range(1, 10):
                if (n1 + n2 + n4) not in P: continue # number of Os
                for n9 in range(1, 10):
                  if (n5 + n6 + n8 + n9) not in P: continue # number of Is
                  if (n1 + n7 + 2*n9) not in P: continue # number of Ns
                  if (n1 + 2*n3 + n5 + 2*n7 + n8 + n9) not in P: continue # number of Es
                  # equal numbers of Ns and Vs
                  if not(n1 + n7 + 2*n9 == n5 + n7): continue

                  # total is also prime
                  answer = (n1, n2, n3, n4, n5, n6, n7, n8, n9)
                  T = sum(x * y for x, y in zip(answer, lenwords))
                  if T not in P: continue
                  print('answer:', answer)

      Like

    • GeoffR's avatar

      GeoffR 9:38 am on 10 May 2023 Permalink | Reply 

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

% Assumed ranges of primes for vowels and consonants
set of int:vowels = {2, 3, 5, 7, 11, 13, 17, 19};
set of int:cons = {2, 3, 5, 7, 11};

var vowels:E; var vowels:I; var vowels:O; var vowels:U;
var cons:F; var cons:G; var cons:H; var cons:N;  var cons:R;
var cons:S; var cons:T; var cons:V; var cons:W;  var cons:X;

% 2-digit primes for total sum of all letters
set of int:primes2d = {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 
                      53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
                 
% Numbers of groups of  spelt numbers - assumed range 1..9
var 1..9:ONE; var 1..9:TWO; var 1..9:THREE; 
var 1..9:FOUR; var 1..9:FIVE; var 1..9:SIX;
var 1..9:SEVEN; var 1..9:EIGHT; var 1..9: NINE;

% Given:  N == V  and  T > N;
constraint (ONE + SEVEN + NINE * 2) == (FIVE + SEVEN)
/\ (TWO + THREE + EIGHT) > (ONE + SEVEN + NINE * 2);

% sum of total letters
var 11..97: total_letters;

% Find sums of individual letters
constraint E == (ONE + THREE * 2 + FIVE + SEVEN * 2  + EIGHT + NINE );
constraint F == (FOUR + FIVE ) /\ G == EIGHT ;
constraint H == (THREE + EIGHT) /\ I == (FIVE + SIX + EIGHT + NINE);
constraint N == (ONE + SEVEN + NINE * 2) /\ O == (ONE + TWO + FOUR) ;
constraint R == (THREE + FOUR) /\ S == (SIX + SEVEN) /\ T == (TWO + THREE + EIGHT);
constraint U == FOUR /\ V == (FIVE + SEVEN) /\ W == TWO /\ X == SIX;

constraint total_letters == E + F + G + H + I + N + O + R + S + T + U + V + W + X;
constraint total_letters in primes2d;

solve satisfy;

output["Sets:[ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE] = " ++ "\n"
++ show([ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE])   ++ "\n" 
++ "Letters:[E, F, G, H, I, N, O, R, S, T, U, V, W, X] = " ++  "\n" ++ 
"       " ++ show( [E,F,G,H,I,N,O,R,S,T,U,V,W,X]) ];

      Like

  • Unknown's avatar

    Jim Randell 10:25 am on 4 May 2023 Permalink | Reply
    Tags:   

    Teaser 1977: Reverse and add 

    From The Sunday Times, 6th August 2000 [link]

    In the above sums, digits have consistently been replaced by letters, with different letters used for different digits.

    Find the number for this SUNDAY.

    [teaser1977]

     
    • Jim Randell's avatar

      Jim Randell 10:26 am on 4 May 2023 Permalink | Reply

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

      The following run file (or command line) executes in 65ms. (Internal runtime of the generated program is 312µs).

      Run: [ @replit ]

      #! python3 -m enigma -rr

SubstitutedExpression

"AND + DNA = BUT"
"BUT + TUB = ALSO"

--answer="SUNDAY"

      % python3 -m enigma -r SubstitutedExpression "AND + DNA = BUT" "BUT + TUB = ALSO" --answer="SUNDAY"
(AND + DNA = BUT) (BUT + TUB = ALSO) (SUNDAY)
(183 + 381 = 564) (564 + 465 = 1029) (268317) / A=1 B=5 D=3 L=0 N=8 O=9 S=2 T=4 U=6 Y=7
SUNDAY = 268317 [1 solution]

      Solution: SUNDAY = 268317.

      The sums are:

      AND + DNA = BUT → 183 + 381 = 564
      BUT + TUB = ALSO → 564 + 465 = 1029

      Like

    • GeoffR's avatar

      GeoffR 2:55 pm on 4 May 2023 Permalink | Reply 

      from itertools import permutations

digits = set(range(10))

# 1st stage permutation (3 digits)
for p1 in permutations (digits, 3):
  A, N, D = p1
  if 0 in (A, D):continue
  AND, DNA = 100*A + 10*N + D, 100*D + 10*N + A
  
  # 2nd stage permutation (3 digits)
  qs = digits.difference(p1)
  for p2 in permutations(qs, 3):
    B, U, T = p2
    if 0 in (B, T):continue 
    BUT, TUB = 100*B + 10*U + T, 100*T + 10*U + B
    if AND + DNA != BUT:continue

    # 3rd stage permutation (4 digits)
    qs2 = qs.difference(p2)
    for p3 in permutations(qs2):
      L, S, O, Y = p3
      ALSO = 1000*A + 100*L + 10*S + O
      if BUT + TUB == ALSO:
        SUNDAY = 100000*S + 10000*U + 1000*N + 100*D + 10*A + Y
        print('SUNDAY = ', SUNDAY)
        
# SUNDAY =  268317

      Like

    • Frits's avatar

      Frits 7:28 pm on 4 May 2023 Permalink | Reply 

         
'''
"AND + DNA = BUT"
"BUT + TUB = ALSO"
'''
 
A = 1  # thousands digit
# D, T, B are consecutive digits T = D + 1, B = T + 1
# D >= 3 as T >= 4 (as B + T >= 9 and B = T + 1) 
# D != 4 as T != 5 (B = T + 1, if T = 5 then O would become 1 (A))
# D != 5 otherwise (N, U) becomes (9, 8) and O would become 7 (B))
# D != 6 otherwise N becomes 5 and U becomes 0 and S becomes 0 (U) or 1 (A)
#               or N becomes 9 and U becomes 8 (B)
# D != 7 otherwise O becomes 7 as well
(D, T, B, O) = (3, 4, 5, 9)

# N != 5 otherwise U would be 0 forcing S to be 0 (U) or 1 (A)
# N != 6 as U >= 5 as T + B = 9
# N != 7 otherwise U would be 4 (T)
# N != 9 as O is 9 
(N, U) = (8, 6)

# S = 2 ((2 * U) % 10)
# L = 0 (B + T + 1 = 10)
# Y = 7 (remaining digit)
(S, L, Y) = (2, 0, 7)

print("SUNDAY = ", ''.join(str(x) for x in (S, U, N, D, A, Y)))

      Like

  • Unknown's avatar

    Jim Randell 9:10 am on 2 May 2023 Permalink | Reply
    Tags:   

    Teaser 2624: Is it 2013? 

    From The Sunday Times, 6th January 2013 [link] [link]

    I have in mind a four-digit number. Here are three clues about it:

    (1) Like 2013, it uses 4 consecutive digits in some order;
    (2) It is not divisible by any number from 2 to 11;
    (3) If I were to tell you the _____ digit, then you could work out my number.

    Those clues would have enabled you to work out my number, but unfortunately the printer has left a gap: it should have been the word “units” or “tens” or “hundreds” or “thousands”.

    What is my number?

    [teaser2624]

     
    • Jim Randell's avatar

      Jim Randell 9:13 am on 2 May 2023 Permalink | Reply

      The puzzle works equally well if the missing word is chosen from: “first”, “second”, “third”, “fourth”.

      It is straightforward to consider all possible 4-digit numbers. But we can be a bit cleverer, and there are a few sets of digits we can use, some of which can be discarded immediately, and we can then produce viable permutations from the remaining digits.

      This Python program runs in 52ms. (Internal runtime is 201µs).

      Run: [ @replit ]

      from enigma import (irange, tuples, subsets, nconcat, filter_unique, item, join, printf)

# generate candidate numbers
def generate():
  # consider possible sets of digits
  for ds in tuples(irange(0, 9), 4):
    # discard any sets where all numbers will be divisible by 3
    if sum(ds) % 3 == 0: continue
    # consider possible permutations
    for (A, B, C, D) in subsets(ds, size=4, select='P'):
      # discard final digit = 0, 2, 4, 6, 8 (divisible by 2) or 5 (divisible by 5)
      if D not in {1, 3, 7, 9}: continue
      # discard if divisible by 7 or 11
      n = nconcat(A, B, C, D)
      if n % 7 == 0 or n % 11 == 0: continue
      # return viable (<candidate>, <digits>)
      yield (A, B, C, D)

# collect candidate numbers
rs = list(generate())

# consider possible missing digit positions
for i in irange(0, 3):
  # there must be only one solution
  ss = filter_unique(rs, item(i)).unique
  if len(ss) == 1:
    printf("digit {i} => {n}", i=i + 1, n=join(ss[0]))

      Solution: The number is 2143.

      There are 5 candidate numbers where if we were told the digit in a certain position we would be able to work out the number:

      1st digit = 1 ⇒ 1423
      1st digit = 8 ⇒ 8567
      2nd digit = 1 ⇒ 2143
      3rd digit = 1 ⇒ 2413
      3rd digit = 3 ⇒ 4231

      But the puzzle text tells us that if we knew which of the words the printer had left out, we would be able to work out the number. (Without being told the value of the digit in that position).

      The only possibility that lets us work out the number, is if the position the printer omitted is the 2nd digit (“hundreds”) (as either of 1st (“thousands”) or 3rd (“tens”) would not allow us to work out the number).

      So the missing word must be “hundreds”, and the number is 2143.

      Like

    • Frits's avatar

      Frits 1:43 pm on 3 May 2023 Permalink | Reply 

         
from itertools import permutations as perm

# sum(x, x+1, x+2, x+3) = 4.x + 6 is divisible by 3 if x is divisible by 3 
# dgts = 1-8    (as x cannot be 0 and x+3 cannot be 9)
mind, maxd = 1, 8
dgts = ''.join(str(x) for x in range(mind, maxd + 1))

cands = [''.join(p) for s in [x - mind for x in range(mind, maxd - 2) if x % 3]
         for p in perm(dgts[s: s + 4])
         if p[-1] in "137" and all(int(''.join(p)) % i for i in [7, 11])]
         
# consider possible missing digit positions
for pos in range(4):
  # check if there is a unique digit that occurs only once in this position
  occ1 = [s[0] for d in dgts if len(s := [c for c in cands if c[pos] == d]) == 1]
  if len(occ1) == 1:
    print("answer:", occ1[0])

      If we know there is exactly one solution:

         
from itertools import permutations as perm

# reverse non-empty 2-dimensional matrix (from  MxN to NxM)
R = lambda mat: [[m[pos] for m in mat] for pos in range(len(mat[0]))]

# sum(x, x+1, x+2, x+3) = 4.x + 6 is divisible by 3 if x is divisible by 3 
# dgts = 1-8    (as x cannot be 0 and x+3 cannot be 9)
mind, maxd = 1, 8
dgts = ''.join(str(x) for x in range(mind, maxd + 1))

cands = [''.join(p) for s in [x - mind for x in range(mind, maxd - 2) if x % 3]
         for p in perm(dgts[s: s + 4])
         if p[-1] in "137" and all(int(''.join(p)) % i for i in [7, 11])]
         
# check reversed candidates (from  MxN to NxM)
ind = [s[0] for r in R(cands) 
       if len(s := [r.index(d) for d in dgts if r.count(d) == 1]) == 1][0] 
print("answer:", cands[ind])

      Like

  • Unknown's avatar

    Jim Randell 3:43 pm on 30 April 2023 Permalink | Reply
    Tags:   

    Teaser 2406: [Powers of three] 

    From The Sunday Times, 2nd November 2008 [link]

    For a school project, Penny was investigating the powers of 3. She wrote some down and explained to Joe that the first power was 3, the second power was 9, the third power was 27, and so on. Soon the numbers were in the millions and Joe asked how close to a whole number of millions one of the high powers could be.

    Simply by some clever logic and algebra Penny was soon able to answer the question. She also found the lowest power of 3 that actually came that close.

    Which power (e.g. 248th) was it?

    This puzzle was originally published with no title.

    [teaser2406]

     
    • Jim Randell's avatar

      Jim Randell 3:44 pm on 30 April 2023 Permalink | Reply

      For positive integers k we have 3^k is an odd number, so we are never going to land on an exact number of millions.

      But if we consider the sequence:

      a[k] = (3^k) mod 1000000

      Then it will form a repeating sequence of values, all less than a million. So we can calculate a[k] for increasing k, until we see a repeated value, and that will tell us where 3^k is closest to an exact million.

      This Python program runs in 96ms. (Internal runtime is 41ms).

      from enigma import (Accumulator, divr, number, arg, printf)

M = number(arg("1_000_000", 0))  # M is the modulus
n = arg(3, 1, int)  # n is the base

# find the closest value (= smallest delta)
r = Accumulator(fn=min, collect=1)

# consider increasing powers of n mod M
(p, k, a) = (1, 0, dict())
while True:
  p *= n
  p %= M
  k += 1
  # have we already seen this residue?
  if p in a:
    # calculate the period
    printf("[period = {d}]", d=k - a[p])
    break
  # otherwise, record the value
  a[p] = k
  if r.count > 0 or divr(pow(n, k), M) > 0:
    r.accumulate_data(min(p, M - p), k)

# output solution
for k in r.data:
  printf("{n}^{k} mod {M} = {x} [delta = {r.value}]", x=pow(n, k, M))

      Solution: The lowest power of 3 that comes closest to an exact million is the 50,000th.

      We have:

      >>> pow(3, 50_000, 1_000_000)
1

      In fact 3^50000 is a 23,857 digit number: 1155409630…2761000001.

      And we see that the sequence has a period of 50,000, so:

      >>> pow(3, 50_000 * 2, 1_000_000)
1
>>> pow(3, 50_000 * 3, 1_000_000)
1
>>> pow(3, 50_000 * 117, 1_000_000)
1

      And of course, we have a[0] = 1.

      It is not possible for a power of 3 to be −1 (mod 10^6), which we can see by calculating values of 3^k mod 100. There are only 20 possible values, and 99 never occurs.

      But we can use Euler’s Theorem [@wikipedia] to determine that there is some value k such that:

      3^k (mod 10^6) = 1

      (as 10^6 and 3 are co-prime).

      And we can calculate one possible value of k using Euler’s totient function [@wikipedia] as φ(10^6).

      However this is not necessarily the smallest value of k (although Lagrange’s theorem [@wikipedia] tells that the smallest value of k must divide φ(10^6)).

      But we can calculate the required value with a relatively modest amount of calculation.

      If we consider the powers of 3^k mod 10^n, we find that when n = 1 we have:

      mod 10:
      3^1 = 3
      3^2 = 3×3 = 9
      3^3 = 9×3 = 7
      3^4 = 7×3 = 1

      So every a[4k] = 1 (mod 10).

      For n = 2 we can just look at 3^(4k) mod 100:

      mod 100:
      3^4 = 81
      3^8 = 81×81= 61
      3^12 = 61×81 = 41
      3^16 = 41×81 = 21
      3^20 = 21×81 = 1

      So every a[20k] = 1 (mod 100).

      For n = 3:

      mod 1000:
      3^20 = 401
      3^40 = 401×401 = 801
      3^60 = 801×401 = 201
      3^80 = 201×401 = 601
      3^100 = 601×401 = 1

      So every a[100k] = 1 (mod 1000).

      For n = 4:

      mod 10000:
      3^100 = 2001
      3^200 = 2001×2001 = 4001
      3^300 = 4001×2001 = 6001
      3^400 = 6001×2001 = 8001
      3^500 = 8001×2001 = 1

      So every a[500k] = 1 (mod 10000).

      For n = 5:

      mod 100000:
      3^500 = 10001
      3^1000 = 10001×10001 = 20001
      3^1500 = 20001×10001 = 30001
      3^2000 = 30001×10001 = 40001
      3^2500 = 40001×10001 = 50001
      3^3000 = 50001×10001 = 60001
      3^3500 = 60001×10001 = 70001
      3^4000 = 70001×10001 = 80001
      3^4500 = 80001×10001 = 90001
      3^5000 = 90001×10001 = 1

      So every a[5000k] = 1 (mod 100000).

      For n = 6:

      mod 1000000:
      3^5000 = 100001
      3^10000 = 100001×100001 = 200001
      3^15000 = 200001×100001 = 300001
      3^20000 = 300001×100001 = 400001
      3^25000 = 400001×100001 = 500001
      3^30000 = 500001×100001 = 600001
      3^35000 = 600001×100001 = 700001
      3^40000 = 700001×100001 = 800001
      3^45000 = 800001×100001 = 900001
      3^50000 = 900001×100001 = 1

      So every a[50000k] = 1 (mod 1000000).

      And this provides our answer.

      Or using Euler’s totient function (as mentioned above).

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

      from enigma import (prime_factor, divisors, number, arg, printf)

# Euler's totient function
def phi(n):
  t = n
  for (p, _) in prime_factor(n):
    t -= t // p
  return t

M = number(arg("1_000_000", 0))  # M is the modulus
n = arg(3, 1, int)  # n is the base

# the order of the multiplicative group of integers modulo M is ...
m = phi(M)
printf("[phi({M}) = {m}]")

# Lagrange's Theorem = "The smallest k such that a^k = 1 (mod M) divides m"
# look for the smallest value ...
for k in divisors(m):
  if pow(n, k, M) == 1:
    printf("{n}^{k} mod {M} = 1")
    break

      Like

      • Jim Randell's avatar

        Jim Randell 2:16 pm on 1 May 2023 Permalink | Reply

        In fact we can be a bit cleverer by solving the equivalent problem for the prime factors of the modulus, and then the required result is the lowest common multiple of these exponents.

        from enigma import (prime_factor, divisors, mlcm, gcd, number, arg, printf)

# calculate the totient of p^k, for prime p
phi_pk = lambda p, k: pow(p, k - 1) * (p - 1)

def solve(n, M):
  assert gcd(n, M) == 1
  # collect exponents for prime factors of the modulus
  ks = list()
  for (p, e) in prime_factor(M):
    f = pow(p, e)
    for k in divisors(phi_pk(p, e)):
      if pow(n, k, f) == 1:
        ks.append(k)
        break
  return mlcm(*ks)

M= number(arg("1_000_000", 0))  # M is the modulus
n = arg(3, 1, int)  # n is the base

k = solve(n, M)
r = pow(n, k, M)
printf("{n}^{k} mod {M} = {r}")
assert r == 1

        Like

  • Unknown's avatar

    Jim Randell 4:27 pm on 28 April 2023 Permalink | Reply
    Tags:   

    Teaser 3162: Flash Cordon and Ming 

    From The Sunday Times, 30th April 2023 [link] [link]

    Housing its priceless Ming collection, the museum’s main hall had eight flashing, motion-sensor alarms. Each alarm’s flash ON and OFF times were settable from 1s to 4s in 0.1s steps. This allowed the flash “duty cycle” (the percentage of one ON+OFF period spent ON) to be altered. To conserve power, all duty cycles were set under 50%. All eight duty cycles were whole numbers, not necessarily all different.

    Four alarms were set with consecutive incremental ON times (e.g. 2.0, 2.1, 2.2, 2.3). One pair of these had equal OFF times, as did the other pair (but a different OFF time from the first pair). Curiously, these two statements also apply to the other four alarms if the words ON and OFF are exchanged.

    Give the lowest and highest duty cycles for each set of four alarms.

    [teaser3162]

     
    • Jim Randell's avatar

      Jim Randell 5:27 pm on 28 April 2023 Permalink | Reply

      At first I misunderstand how this puzzle worked. But each sensor has an ON duration, and an OFF duration, each chosen from values between 1.0s and 4.0s (inclusive). The “duty cycle” is then calculated as the fraction ON / (ON + OFF), when expressed as a percentage.

      This Python program runs in 56ms. (Internal runtime is 1.4ms).

      Run: [ @replit ]

      from enigma import (irange, subsets, div, group, item, tuples, cproduct, multiset, printf)
 
# collect possible duty cycles (ON, OFF) -> duty%
ds = dict()
# consider possible ON/OFF pairs (deci-seconds)
for (ON, OFF) in subsets(irange(10, 40), size=2):
  # calculate the duty cycle
  d = div(100 * ON, ON + OFF)
  if not d: continue
  ds[(ON, OFF)] = d

# does a collection of values form pairs?
pairs = lambda vs: multiset.from_seq(vs).all_same(2)

# choose consecutive item <i> times, and corresponding pairs of <j> times
def choose(ds, i, j):
  # group item j by item i
  g = group(ds.keys(), by=item(i), f=item(j))
 
  # choose 4 consecutive keys
  for ks in tuples(sorted(g.keys()), 4):
    if ks[-1] - ks[0] != 3: continue
    # choose possible values ...
    for vs in cproduct(g[k] for k in ks):
      # ... that form pairs
      if not pairs(vs): continue
      # return (keys, values)
      yield (ks, vs)
 
# the first set of alarms (consecutive ON times)
for (ks, vs) in choose(ds, 0, 1):
  duty = list(ds[k] for k in zip(ks, vs))
  printf("[1] ON = {ks} -> OFF = {vs}; duty% = {duty} => min={min} max={max}", min=min(duty), max=max(duty))
 
# the second set of alarms (consecutive OFF times)
for (ks, vs) in choose(ds, 1, 0):
  duty = list(ds[k] for k in zip(vs, ks))
  printf("[2] ON = {vs} -> OFF = {ks}; duty% = {duty} => min={min} max={max}", min=min(duty), max=max(duty))

      Solution: The minimum and maximum duty cycles for the first set of alarms are: 22% and 28%. For the second set of alarms they are: 24% and 26%.

      The first set is:

      ON = 1.1s, OFF = 3.9s; duty cycle = 22% (min)
      ON = 1.2s, OFF = 3.6s; duty cycle = 25%
      ON = 1.3s, OFF = 3.9s; duty cycle = 25%
      ON = 1.4s, OFF = 3.6s; duty cycle = 28% (max)

      And the second set:

      ON = 1.2s, OFF = 3.6s; duty cycle = 25%
      ON = 1.3s, OFF = 3.7s; duty cycle = 26% (max)
      ON = 1.2s, OFF = 3.8s; duty cycle = 24% (min)
      ON = 1.3s, OFF = 3.9s; duty cycle = 25%

      Like

    • Frits's avatar

      Frits 7:53 pm on 28 April 2023 Permalink | Reply

      Basically trying to get the same output as Jim’s program.
      Performance could have been improved by initially collecting possible duty cycles.
      This program runs in 210ms.

       
from enigma import SubstitutedExpression

# invalid digit / symbol assignments
d2i = dict()
for d in range(0, 10):
  vs = set()
  tens = 'ACEGIKMOQS'
  if d == 0: vs.update(tens)
  if d > 4:  vs.update(tens)

  d2i[d] = vs

# all duty cycles are whole numbers  
check = lambda s, t: all((100 * x) % (x + y) == 0 for x, y in zip(s, t))    

# [1] ON = (AB, AB+1, AB+2, AB+3) -> OFF = {CD, EF, GH, IJ} 
# [2] ON = {KL, MN, OP, QR}       -> OFF = (ST, ST+1, ST+2, ST+3)

# the alphametic puzzle
p = SubstitutedExpression(
  [
    # consecutive ON times: CD, EF, GH, IJ contain two pairs
    "len({CD, EF, GH}) == 2",
    "all(x < 41 for x in [CD, EF, GH])",
    "[x for x in [CD, EF, GH] if [CD, EF, GH].count(x) == 1][0] = IJ",
    
    # all duty cycles are set under 50% ...
    "AB < min(CD, EF - 1, GH - 2, IJ - 3)",
    # ... and are whole numbers
    "check((AB, AB+1, AB+2, AB+3), (CD, EF, GH, IJ))",
    
    # consecutive OFF times: KL, MN, OP, QR contain two pairs
    "len({KL, MN, OP}) == 2",
    "all(x < 41 for x in [KL, MN, OP])",
    "[x for x in [KL, MN, OP] if [KL, MN, OP].count(x) == 1][0] = QR",
    
    # all duty cycles are set under 50% ...
    "max(KL, MN - 1, OP - 2, QR - 3) < ST < 38",
    # ... and are whole numbers
    "check((KL, MN, OP, QR), (ST, ST+1, ST+2, ST+3))",
  ],
  answer="(AB, AB+1, AB+2, AB+3), (CD, EF, GH, IJ), \
          (KL, MN, OP, QR), (ST, ST+1, ST+2, ST+3)",
  d2i=d2i,
  distinct="",
  env=dict(check=check),
  reorder=0,
  verbose=0,    # use 256 to see the generated code
)

# print answers
for (_, (n1, f1, n2, f2)) in p.solve():
  print("1st set:", min(dt := [(100 * x) // (x + y) for x, y in zip(n1, f1)]),
        "and", max(dt))
  print("2nd set:", min(dt := [(100 * x) // (x + y) for x, y in zip(n2, f2)]),
        "and", max(dt))

      Like

      • Jim Randell's avatar

        Jim Randell 9:37 am on 29 April 2023 Permalink | Reply

        @Frits: You can use a [[ SubstitutedExpression ]] recipe like this to find the first set of values, and a similar recipe will find the second set:

        #! python3 -m enigma -rr

SubstitutedExpression

# suppose the on/off durations are:
#  X + 0 -> P
#  X + 1 -> Q
#  X + 2 -> R
#  X + 3 -> S
# where each is a number between 10 and 40
# so we use base 41
--base=41
--digits="10-40"
--distinct=""

# check values come in pairs
--code="check = lambda vs: multiset.from_seq(vs).all_same(2)"
"check([P, Q, R, S])"

# check duty cycles
--code="duty = lambda ON, OFF: (div(100 * ON, ON + OFF) if ON < OFF else None)"
"duty(X, P)"
"duty(X + 1, Q)"
"duty(X + 2, R)"
"duty(X + 3, S)"

--template=""
--answer="((X, P), (X + 1, Q), (X + 2, R), (X + 3, S))"

        Internal runtimes are 16.8ms and 7.0ms.

        I’ve put a complete solution to the puzzle using this technique up on [@replit].

        Like

        • Frits's avatar

          Frits 11:58 am on 30 April 2023 Permalink | Reply

          Thanks, I didn’t think of the combination of base and digits.

          The following MiniZinc problem runs fastest with the Chuffed solver (330ms).

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

%  ------- first 4 alarms ----------

% suppose the on/off durations are:
%  X1 + 0 -> Y1[1]
%  X1 + 1 -> Y1[2]
%  X1 + 2 -> Y1[3]
%  X1 + 3 -> Y1[4]
  
var 10..36:X1;  
array [1..4] of var 11..40: Y1;
array [1..4] of var 20..49: D1;  % duty cycles

% Y1 contains 2 pairs 
constraint forall (y in Y1) (count(Y1, y) == 2);

% check duty cycles
constraint forall (i in 1..4) ( X1 + i - 1 < Y1[i] /\ 
                  (100 * (X1 + i - 1)) mod (X1 + i - 1 + Y1[i]) == 0);
                  
constraint forall (i in 1..4) ((100 * (X1 + i - 1)) div (X1 + i - 1 + Y1[i]) == D1[i]);

output ["X1 = " ++ show (X1) ++ ", Y1 = " ++ show(Y1) ++ 
        ", min = " ++ show(min(D1)) ++ ", max = " ++ show(max(D1)) ++ "\n" ];

%  ------- other 4 alarms ----------

% suppose the on/off durations are:
%  Y2[1] -> X2 + 0
%  Y2[2] -> X2 + 1
%  Y2[3] -> X2 + 2
%  Y2[4] -> X2 + 3
 
var 11..37:X2;  
array [1..4] of var 10..39: Y2;
array [1..4] of var 20..49: D2;  % duty cycles

% Y2 contains 2 pairs 
constraint forall (y in Y2) (count(Y2, y) == 2);

% check duty cycles
constraint forall (i in 1..4) ( Y2[i] < X2 + i - 1 /\ 
                  (100 * Y2[i]) mod (X2 + i - 1 + Y2[i]) == 0);
                  
constraint forall (i in 1..4) ((100 * (Y2[i])) div (X2 + i - 1 + Y2[i]) == D2[i]);
 
output ["X2 = " ++ show (X2) ++ ", Y2 = " ++ show(Y2) ++ 
        ", min = " ++ show(min(D2)) ++ ", max = " ++ show(max(D2)) ];

solve satisfy;

          Like

  • Unknown's avatar

    Jim Randell 9:36 am on 27 April 2023 Permalink | Reply
    Tags:   

    Teaser 2626: Homophones 

    From The Sunday Times, 20th January 2013 [link] [link]

    Wo, who lives in Woe, has been studying homophones (i.e. sets of words that sound the same, but have different meanings). He has now extended his studies to sets of numbers that have a common property.

    He wrote down three numbers which were prime, and a further two numbers whose different digits formed a consecutive set. Having consistently replaced different digits by different letters, this made his primes into:

    TWO
    TOO
    TO

    and his numbers using consecutive digits into:

    STRAIGHT
    STRAIT

    What is the three-figure number WOE?

    This puzzle appears in the book The Sunday Times Brain Teasers Book 2 (2020) under the title “Our secret”.

    [teaser2626]

     
    • Jim Randell's avatar

      Jim Randell 9:36 am on 27 April 2023 Permalink | Reply

      I used the [[ SubstitutedExpression ]] solver from the enigma.py library to solve this puzzle.

      The following run file executes in 79ms. (Internal runtime is 10.4ms).

      Run: [ @replit ]

      #! python3 -m enigma -rr

SubstitutedExpression

# primes
"is_prime(TWO)"
"is_prime(TOO)"
"is_prime(TO)"

# check for a consecutive set of digits
--code="check = lambda ds: max(ds) - min(ds) == len(ds) - 1"
"check({S, T, R, A, I, G, H, T})"
"check({S, T, R, A, I, T})"

# no leading zeros
--invalid="0,TSW"

--answer="WOE"
--template="(TWO TOO TO) (STRAIGHT STRAIT) (WOE)"
--solution=""

      Solution: WOE = 798.

      There are 84 possible solutions, although the following words have the same value in all of them:

      TO = 19
      TOO = 199
      TWO = 179
      WOE = 798

      Note that STRAIGHT and STRAIT are not required to be prime, but there are only 7 solutions where they are:

      STRAIGHT = 41203651, STRAIT = 412031
      STRAIGHT = 31402561, STRAIT = 314021
      STRAIGHT = 41325601, STRAIT = 413251
      STRAIGHT = 21435061, STRAIT = 214351
      STRAIGHT = 31245601, STRAIT = 312451
      STRAIGHT = 31245061, STRAIT = 312451
      STRAIGHT = 41352061, STRAIT = 413521

      Like

    • Frits's avatar

      Frits 1:57 pm on 27 April 2023 Permalink | Reply 

         
#! python3 -m enigma -r
 
SubstitutedExpression
 
# primes
"is_prime(TWO)"
"is_prime(TOO)"
"is_prime(TO)"

#  credit: Brian Gladman [ https://brg.me.uk/?page_id=485 ]

# since the digits for letters other than WOE are consecutive,
# we must have one of the following four situations:
#
# digit sequence  (W, O, E) values (in some order with W <> 0)
#      0..6       (7, 8, 9)
#      1..7       (0, 8, 9)
#      2..8       (0, 1, 9)
#      3..9       (0, 1, 2)
 
# check for a consecutive set of digits in remaining digits
"''.join(sorted(str(WOE))) in {'012', '019', '089', '789'}", 

# no leading zeros
--invalid="0,OTW"
--invalid="3-6,WOE"
--invalid="2|8,O"
 
--answer="WOE"
--template="(TWO TOO TO) (WOE)"
--solution=""

      Like

  • Unknown's avatar

    Jim Randell 10:25 am on 25 April 2023 Permalink | Reply
    Tags: ,   

    Teaser 2627: Inversion 

    From The Sunday Times, 27th January 2013 [link] [link]

    In the woodwork class Pat cut a triangle from a sheet of plywood, leaving a hole in the sheet. The sides of the triangle were consecutive whole numbers of centimetres long. He then wanted to turn the triangle over and fit it back into the hole. To achieve this he had to cut the triangle into three pieces. He did this with two straight cuts, each cut starting at a midpoint of a side. Then each of the three pieces (two of which had the same perimeter) could be turned over and placed back in exactly its starting position in the hole.

    What are the lengths of the sides of the original triangle?

    [teaser2627]

     
    • Jim Randell's avatar

      Jim Randell 10:26 am on 25 April 2023 Permalink | Reply

      I imagined the wood was painted black on one side, and the goal is then to cut the triangle into 3 shapes, such that each shape will fit back into its original hole when turned over, to produce a completely black triangle of the same shape as the original.

      My first thought, when looking for a triangle with sides that are consecutive whole numbers, was to look at a (3, 4, 5) triangle, as these often crop up in these puzzles.

      Making two cuts between midpoints of sides divides the triangle into 3 shapes as shown:

      The quadrilateral Q, can be turned over to fit back into its vacated hole, but the triangles P and R do not, as they are not isosceles (but they are identical, and so have the same perimeter).

      But we can make these triangles isosceles, but in doing this the quadrilateral shrinks to zero size (and our two cuts become one):

      But what if we make the initial triangle such that it can be divided into two smaller isosceles triangles and a quadrilateral that can be turned over?

      We end up with something like this:

      And we can make Q and R have the same perimeter by making the base of R have length 2a.

      Now, the lengths {2a, 2b, 2(a + c)} must be consecutive integers in some order.

      So either:

      b = a + 1; c = 1/2
      b = a + 1/2; c = 1

      We can calculate the height h of triangles P and R to get:

      h² = a² − c² = b² − a²
      ⇒ 2a² − b² − c² = 0

      Substituting the possible values for b and c in terms of a, gives us quadratic equations (in a), which we can solve for viable solutions.

      This Python program runs in 59ms. (Internal runtime is 241µs).

      Run: [ @replit ]

      from enigma import (enigma, Polynomial, sq, printf)

Q = enigma.Rational()
as_int = lambda x: enigma.as_int(x, include="+", default=None)

# consider values for c
for c in (Q(1, 2), 1):
  # form the polynomial
  b = Polynomial([Q(3, 2) - c, 1])
  p = Polynomial([-sq(c), 0, 2]) - sq(b)
  # find positive rational roots for a
  for a in p.quadratic_roots(domain='Q', include="+", F=Q):
    # find integer sides
    sides = list(map(as_int, [2 * a, 2 * b(a), 2 * (a + c)]))
    if all(sides):
      # output solution
      printf("sides = {sides} [c={c} p={p} -> a={a}]", sides=sorted(sides))

      Solution: The sides of the original triangle were 5cm, 6cm, 7cm.

      The polynomials we form are:

      a² − 2a − 5/4 = 0
      ⇒ (2a + 1)(2a − 5) = 0
      ⇒ a = 5/2, b = 7/2, c = 1/2

      a² − a − 5/4 = 0
      ⇒ no rational roots

      The second polynomial does have a real root at: a = (1 + √6) / 2.

      Which gives a triangle with sides of (3.449…, 4.449…, 5.449…).

      So although the puzzle does not work with a (3, 4, 5) triangle, it does work with a (3, 4, 5) + (√6 − 2) triangle.

      Like

  • Unknown's avatar

    Jim Randell 11:57 am on 23 April 2023 Permalink | Reply
    Tags:   

    Brain teaser 1005: Words and numbers 

    From The Sunday Times, 1st November 1981 [link]

    A familiar letters-for-digits problem is to take a correct addition sum such as:

    1 + 1 = 2

    and write it in words so:

    ONE + ONE = TWO

    The problem is to assign numbers from 0 to 9 to the letters so that we get a correct addition sum, e.g. E = 6, N = 3, O = 2, T = 4, W = 7 gives:

    236 + 236 = 472

    Two rules to be kept are that the left hand digit of any number is not zero, and different letters are assigned different numbers.

    Some addition sums clearly have no solution. e.g.:

    ONE + THREE = FOUR

    In the Kudali Language the words for 1, 2, 3, 4 are AA, BA, EB, DE, although not necessarily in that order. Now all the addition sums:

    1 + 1 = 2
    1 + 2 = 3
    1 + 3 = 4
    2 + 2 = 4
    1 + 4 = 2 + 3

    when written in Kudali, give letters-for-digits problems each of which has at least one solution.

    What are the Kudali words for 1, 2, 3, 4, in that order?

    This puzzle is included in the books Microteasers (1986) and The Sunday Times Book of Brainteasers (1994).

    [teaser1005]

     
    • Jim Randell's avatar

      Jim Randell 11:57 am on 23 April 2023 Permalink | Reply

      This Python program uses the [[ SubstitutedExpression() ]] solver from the enigma.py library to see if there are solutions to the alphametic expressions.

      It runs in 85ms.

      Run: [ @replit ]

      from enigma import (SubstitutedExpression, subsets, sprintf, printf)

# does an alphametic sum have answers?
solve = lambda expr: any(SubstitutedExpression([expr]).solve(verbose=0))

# expressions involving words for 1, 2, 3, 4
exprs = [
  "{w1} + {w1} = {w2}",
  "{w1} + {w2} = {w3}",
  "{w1} + {w3} = {w4}",
  "{w2} + {w2} = {w4}",
  "{w1} + {w4} == {w2} + {w3}",
]

# allocate the words
for (w1, w2, w3, w4) in subsets(["AA", "BA", "EB", "DE"], size=4, select='P'):
  # are all the expressions solvable?
  if all(solve(sprintf(x)) for x in exprs):
    # output solution
    printf("1 = {w1}; 2 = {w2}; 3 = {w3}; 4 = {w4}")

      Solution: 1 = DE; 2 = BA; 3 = AA; 4 = EB.

      So we have:

      DE + DE = BA → 13 + 13 = 26, …
      DE + BA = AA → 10 + 23 = 33, …
      DE + AA = EB → 13 + 22 = 35, …
      BA + BA = EB → 21 + 21 = 42, …
      DE + EB = BA + AA → 14 + 42 = 23 + 33, …

      Like

    • Frits's avatar

      Frits 5:10 pm on 23 April 2023 Permalink | Reply 

       
from enigma import subsets

'''
0: ab + ab = ef       reject if: b in {a, f}, e = f,
1: ab + cd = ef       reject if: b = f and d in {a, e}, d = f and b in {c, e}
                                 e = f and (b = c or a = d)
2: ab + cd = ef + gh  reject if not: b = d or f = h 
'''

# reject words depending on the type of equation
def rej(t, w, x, y, z=0):
  (a, b) = (w[0], w[1])
  (c, d) = (x[0], x[1])
  (e, f) = (y[0], y[1])
  if t == 0 and (e == f or b in {a, f}): return True
  if t == 1 and any([b == f and d in {a, e}, d == f and b in {c, e},
                     e == f and (b == c or a == d)]): return True
  if t == 2 and not (b == d or f == z[1]): return True                   
  
  return False

# allocate the words
for (w1, w2, w3, w4) in subsets(["AA", "BA", "EB", "DE"], size=4, select='P'):
  if rej(0, w1, w1, w2): continue
  if rej(1, w1, w2, w3): continue
  if rej(1, w1, w3, w4): continue
  if rej(0, w2, w2, w4): continue
  if rej(2, w1, w4, w2, w3): continue
  print(*zip(range(1, 5), (w1, w2, w3, w4)))

      Like

      • Frits's avatar

        Frits 5:23 pm on 23 April 2023 Permalink | Reply

        This is more of a program saying: “if there is a solution it must be one of these: ….”

        Like

  • Unknown's avatar

    Jim Randell 4:14 pm on 21 April 2023 Permalink | Reply
    Tags:   

    Teaser 3161: Going through the hoops 

    From The Sunday Times, 23rd April 2023 [link] [link]

    I arrived very late to watch the croquet game. Someone had listed the times when the four balls (blue, black, red and yellow) had run through hoops 1 to 12; none had yet hit the central peg to finish. Blue had run each hoop earlier than black, and every hoop had been run by colours in a different order. The only change in running order from one hoop to the next-numbered hoop was that two colours swapped positions. These swapping pairs (to obtain the order for the next-numbered hoop) were in non-adjacent positions for hoops 5 and 10, but no others. For one particular colour, all the hoops where it passed through earlier than the yellow were before all those where it passed through later than the yellow.

    In what order had the balls run the twelfth hoop?

    [teaser3161]

     
    • Jim Randell's avatar

      Jim Randell 4:44 pm on 21 April 2023 Permalink | Reply

      This Python program runs in 60ms. (Internal runtime is 4.9ms).

      Run: [ @replit ]

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

# the colours (K = black)
colours = "BKRY"

# x before y
before = lambda s, x, y: s.index(x) < s.index(y)

# is there a colour where all "before yellow" < all "after yellow"
def check(ss, n):
  for k in colours:
    if k == "Y": continue
    (bY, aY) = filter2((lambda i: before(ss[i], k, 'Y')), irange(n))
    if bY[-1] < aY[0]: return True
  return False

# solve the puzzle
def solve(ss):
  n = len(ss)
  # are we done?
  if n == 12:
    if check(ss, n):
      yield ss
  else:
    # choose 2 indices to swap
    s = ss[-1]
    for ((i, x), (j, y)) in subsets(enumerate(s), size=2):
      if (j == i + 1) == (n in {5, 10}): continue
      s_ = update(s, [(i, y), (j, x)])
      # blue before black, and no repeats
      if before(s_, 'B', 'K') and s_ not in ss:
        # move on to the next hoop
        yield from solve(ss + [s_])

# choose an order for the first hoop, with blue before black
for s in subsets(colours, size=len, select='P', fn=join):
  if not before(s, 'B', 'K'): continue
  # solve for the remaining hoops
  for ss in solve([s]):
    # output solution
    printf("hoop 12 = {s12} [{ss}]", s12=ss[-1], ss=join(ss, sep=" "))

      Or [here] is a (longer) version that verifies the “yellow” condition as it goes along (instead of just checking it at the end).

      Solution: The order for the 12th hoop was: Red, Yellow, Blue, Black.

      The full list of orders is (B = Blue, K = Black, R = Red, Y = Yellow):

       1: B K Y R (K before Y)
       2: B K R Y (3/4 swapped; K before Y)
       3: B R K Y (2/3 swapped; K before Y)
       4: R B K Y (1/2 swapped; K before Y)
       5: R B Y K (3/4 swapped; Y before K)
       6: Y B R K (1/3 swapped; Y before K)
       7: Y B K R (3/4 swapped; Y before K)
       8: B Y K R (1/2 swapped; Y before K)
       9: B Y R K (3/4 swapped; Y before K)
      10: B R Y K (2/3 swapped; Y before K)
      11: Y R B K (1/3 swapped; Y before K)
      12: R Y B K (1/2 swapped; Y before K)

      And we see the non-adjacent swaps are between hoops 5 & 6 and 10 & 11.

      Like

    • Frits's avatar

      Frits 11:44 pm on 21 April 2023 Permalink | Reply

      Without recursion.

         
from itertools import permutations, product
from collections import defaultdict

# the colours (K = black)
colours = "BKRY"

# possible running orders (blue before black)
ps = list(p for p in permutations(range(4)) if p.index(0) < p.index(1))

adj_moves = defaultdict(list)
nonadj_moves = defaultdict(list)

# determine all possible next running orders for a specific running order
for (x, y) in product(ps, repeat=2):
  if x == y: continue
  swaps = [i for i, (a, b) in enumerate(zip(x, y)) if a != b]
  # only one swap took place ...
  if len(swaps) != 2: continue
  # .. and store for adjacent fields and non-adjacent fields
  (adj_moves if abs(swaps[0] - swaps[1]) == 1 else nonadj_moves)[x].append(y)
 

# first hoop
ss = [(x, ) for x in ps]
# process remaining hoops after first hoop
for n in range(1, 12):
  ss_ = []
  for s in ss:
    # determine next running order
    for ro in (adj_moves if n not in {5, 10} else nonadj_moves)[s[-1]]:
      if ro not in s:
        ss_.append(s + (ro, ))
  ss = ss_
 
# is there a colour where all "before yellow" < all "after yellow"
for s in ss:  
  for k in range(3):
    # make string with only digits 3 and k 
    # (like k3-k3-3k-3k-3k-3k-k3-k3-3k-3k-3k-3k)
    s_3k = '-'.join([''.join(str(x) for x in y if x in {k, 3}) for y in s])
    f_3k = s_3k.index('3' + str(k))   # first 3k string
    
    if f_3k == 0: continue
    # all k3 strings must occur before first 3k string
    if s_3k[f_3k + 3:].find(str(k) + '3') >= 0: continue
    
    print("answer:", ''.join(colours[x] for x in s[-1]))
    break

      Like

    • Frits's avatar

      Frits 4:21 pm on 25 April 2023 Permalink | Reply

      John Crabtree said that it was not hard to determine the “particular colour”.
      The following code will reject two out of three colours. 

       
from itertools import permutations

# the colours (K = black)
colours = "BKRY"

# possible running orders (blue before black)
ps = list(p for p in permutations(range(4)) if p.index(0) < p.index(1))

# return possible outcomes after a non-adjacent swap
def n_adj(s):
  return set(((s[2], s[1], s[0], s[3]), 
              (s[3], s[1], s[2], s[0]), 
              (s[0], s[3], s[2], s[1])))

particular_colours = []
for k in range(3):
  a, b = [], []       # after/before
  for p in ps:
    (b if p.index(k) < p.index(3) else a).append(p)
  
  # the "after" group has at least 3 elements
  # with at least one non-adjacent move 
  if all(n_adj(e).isdisjoint(a) for e in a): continue
  particular_colours.append(colours[k])

print("possible particular colours:", particular_colours)

      Like

  • Unknown's avatar

    Jim Randell 10:07 am on 20 April 2023 Permalink | Reply
    Tags:   

    Teaser 2696: Digital display 

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

    George and Martha have a seven-figure telephone number consisting of seven different digits in decreasing order. Martha commented that the seven digits added together gave a total number that did not use any of the digits from the telephone number.

    George agreed and added that their telephone number was in fact a multiple of that total number.

    What is their telephone number?

    This completes the archive of Teaser puzzles originally published in The Sunday Times in 2014.

    There are now 856 Teaser puzzles available on the site, including a complete archive of puzzles from December 2013 to the most recent puzzle (April 2023).

    [teaser2696]

     
    • Jim Randell's avatar

      Jim Randell 10:07 am on 20 April 2023 Permalink | Reply

      This Python program runs in 52ms. (Internal runtime is 320µs).

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

# choose 7 digits in decreasing order
for ds in subsets(irange(9, 0, step=-1), size=7):
  # the sum of the digits does not use any of the digits
  dsum = sum(ds)
  if any(d in ds for d in nsplit(dsum)): continue

  # compute the telephone number
  n = nconcat(ds)
  if n % dsum != 0: continue

  # output solution(s)
  printf("number = {n} [dsum = {dsum}]")

      Solution: Their telephone number is: 8654310.

      The digit sum is 27 and:

      8654310 = 320530 × 27

      Like

      • Jim Randell's avatar

        Jim Randell 1:39 pm on 10 May 2023 Permalink | Reply

        Here is a version that uses the [[ SubstitutedExpression ]] solver from the enigma.py library, using the newly implemented macro functionality to tidy things up a bit.

        #! python3 -m enigma -rr

SubstitutedExpression

# suppose the 3 unused digits are X, Y, Z
"X < Y" "Y < Z"

# digit sum of the remaining digits is: 45 - (X + Y + Z)
--macro="@ds = (45 - X - Y - Z)"
# and must be composed entirely of digits in {X, Y, Z}
--macro="@xs = {X, Y, Z}"
"@xs.issuperset(nsplit(@ds))"

# phone number is a multiple of ds
--code="number = lambda xs: nconcat(diff(irange(9, 0, step=-1), xs))"
"number(@xs) % @ds == 0"

--answer="number(@xs)"
--template=""

        Like

    • Frits's avatar

      Frits 11:11 am on 20 April 2023 Permalink | Reply 

         
from enigma import SubstitutedExpression

vars = "ABCDEFG"
d2i = {d: (vars[:6 - d] if d < 6 else "") + (vars[3 - d:] if d > 3 else "")
          for d in range(0, 10)} 

# the alphametic puzzle
p = SubstitutedExpression(
  [
    "A > B",
    "B > C",
    "C > D",
    "D > E",
    "E > F",
    "F > G",
    "A + B + C + D + E + F + G = HI",
    "div(ABCDEFG, HI)",
    
  ],
  answer="ABCDEFG",
  d2i=d2i,
  reorder=0,
  verbose=0,    # use 256 to see the generated code
)

# print answers
for (_, ans) in p.solve():
  print(f"{ans}")

      Like

      • Jim Randell's avatar

        Jim Randell 2:54 pm on 20 April 2023 Permalink | Reply

        @Frits: I think I would allow H and I to have the same value.

        You can allow this with the following parameter to [[ SubstitutedExpression ]]:

        distinct=["ABCDEFGH", "ABCDEFGI"]

        Like

        • Frits's avatar

          Frits 5:12 pm on 20 April 2023 Permalink | Reply

          @Jim, I erronuously thought that the total number also had to have different digits

          Like

        • Frits's avatar

          Frits 5:15 pm on 20 April 2023 Permalink | Reply 

             
dgts = "0123456789"

# decompose <t> into <k> numbers from <ns>
# return number with decreasing digits
def decompose(t, k, ns, s=[]):
  if k == 1:
    if t in ns:
      yield int("".join(str(x) for x in (s + [t])[::-1]))
  else:
    for (i, n) in enumerate(ns):
      if t - n < 0: continue
      yield from decompose(t - n, k - 1, ns[i + 1:], s + [n])

# try each possible total number
for tot_nr in range(sum(range(7)), sum(range(3, 10)) + 1):
  # remaining digits
  rd = [int(x) for x in dgts if x not in str(tot_nr)]
 
  # total number must lie between sum 7 smallest and sum 7 highest digits 
  if not (sum(x for x in rd[:7]) <= tot_nr <= sum(x for x in rd[-7:])):
    continue
  
  pr(tot_nr, rd, sum(x for x in rd[-7:]))
  
  # pick 7 digits with sum to <tot_nr>
  for y in decompose(tot_nr, 7, rd):
    if y % tot_nr == 0:
      print("answer:", y)

          Like

    • GeoffR's avatar

      GeoffR 9:14 pm on 20 April 2023 Permalink | Reply 

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

var 1..9:A; var 0..9:B; var 0..9:C; var 0..9:D;
var 0..9:E; var 0..9:F; var 0..9:G;
var 1..9:H; var 0..9:I;

% 7 digits of the telephone number are in descending order
constraint A > B /\ B > C /\ C > D /\ D > E /\ E > F /\ F > G;

% Telephone number is ABCDEFG
var 6543210..9876543: ABCDEFG == A * pow(10,6) + B * pow(10,5) + C * pow(10,4)
+ D * pow(10,3) + E *  pow(10,2) + F * pow(10,1) + G;

% Sum of digits in Telephone Number
var 21..42: digsum = A + B + C + D + E + F + G;

constraint H == digsum div 10;  
constraint I == digsum mod 10;

% Divisor of telephone number uses digits H and I
constraint ABCDEFG div digsum > 0 /\  ABCDEFG mod digsum == 0;

% Digits H and I could be the same or different
constraint card({A, B, C, D, E, F, G, H}) == 8 
/\ card({A, B, C, D, E, F, G, I}) == 8;  

solve satisfy;

output["Tel. Num. = " ++ show(ABCDEFG) ++ ", Digit sum = " ++ show(digsum)];

% Tel. Num. = 8654310, Digit sum = 27
% ----------
% ==========

      Like

  • Unknown's avatar

    Jim Randell 9:15 am on 18 April 2023 Permalink | Reply
    Tags:   

    Teaser 2675: Should old acquaintance … 

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

    I have given each letter of the alphabet a different whole number value from 1 to 26 (for instance, A has the value 5 and B has the value 24). In this way I can work out the value of any word by adding up the values of its letters. Looking at the values of the words:

    SHOULD
    OLD
    ACQUAINTANCE

    I find that the value of OLD is the average of the other two values.

    I also find that NEW and YEAR have the same value as each other – and it is like the value of OLD but with its two digits in the reverse order. It is possible from all this information to work out the values of N, E and W, but all we want to know is…

    … what is the value of NEW?

    I replaced “for example” in the original puzzle text by “for instance” to make it clear these are the actual values that are being given. In the book The Sunday Times Brain Teasers 2 (2020), the values are simply given as “(eg, A=5 and B=24)”, which I think is more ambiguous than the original text.

    [teaser2675]

     
    • Jim Randell's avatar

      Jim Randell 9:16 am on 18 April 2023 Permalink | Reply

      From:

      (SHOULD + ACQUAINTANCE) / 2 = OLD

      we determine:

      SHU + ACQUAINTANCE = OLD
      ⇒ 3A + 2CNU + CEHIQST = OLD

      And A = 5, so the smallest possible value for OLD is: 3×5 + 2×(1 + 2 + 3) + (4 + 6 + 7 + 8 + 9 + 10) = 71.

      And this is enough to give us a way to attack the problem programatically.

      This Python program runs in 81ms. (Internal runtime is 23.5ms).

      Run: [ @replit ]

      from enigma import (irange, subsets, group, diff, nreverse, cproduct, intersect, singleton, printf)

# given values
A = 5
B = 24

# collect sums of 3 digit values for OLD, NEW, YER
g = group(subsets(diff(irange(1, 26), {A, B}), size=3), by=sum)

# find 2-digit keys with whose reverse is also a key
for OLD in g.keys():
  if OLD < 71: continue
  NEW = nreverse(OLD)
  if NEW < 10 or NEW == OLD or NEW not in g: continue
  YER = NEW - A
  if YER not in g: continue

  # NEW and YER must have E in common (but nothing else)
  for (vNEW, vYER) in cproduct([g[NEW], g[YER]]):
    E = singleton(intersect([vNEW, vYER]))
    if E is None: continue
    # OLD has no letters in common with them
    vs = vNEW + vYER
    for vOLD in g[OLD]:
      if intersect([vOLD, vs]): continue

      # find a value for N (which also gives W)
      for N in diff(vNEW, {E}):
        # calculate remaining amount for 2CU + HIQST
        r = OLD - (3*A + E + 2*N)
        ns = diff(irange(1, 26), {A, B}, vs, vOLD)
        # can we make this from the remaining values?
        if r < sum(ns[0:2]) + sum(ns[0:7]): continue

        # output solution
        printf("OLD={OLD} NEW={NEW} YER={YER} -> E={E} NEW={vNEW} YER={vYER} OLD={vOLD} -> N={N} {ns}", ns=ns[0:7])

      Solution: NEW has a value of 37.

      And we can determine: N = 3, E = 11, W = 23

      OLD has a value of 73, so the individual letters have values 22, 25, 26 (in some order).

      And Y and R are 9 and 12 (in some order).

      To complete the given letters, U and C can be 1 and 2 (in some order).

      And H, I, Q, S, T can be 4, 6, 7, 8, 10 (in some order).

      Like

    • GeoffR's avatar

      GeoffR 1:56 pm on 18 April 2023 Permalink | Reply

      The Chuffed Solver took about 1 sec to run, but the Geocode Solver took about 40 sec.

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

var 1..26:A; var 1..26:C; var 1..26:E; var 1..26:D; var 1..26:H; 
var 1..26:I; var 1..26:L; var 1..26:N; var 1..26:O; var 1..26:Q;
var 1..26:S; var 1..26:T; var 1..26:U; var 1..26:Y; var 1..26:R;
var 1..26:W; var 1..26:B;

constraint A == 5 /\ B == 24; % given in teaser

constraint all_different ([A,C,E,D,H,I,L,N,O,Q,S,T,U,Y,R,W,B]);

% OLD is the average of SHOULD and ACQUAINTANCE
constraint 2 * (O + L + D) == (S + H + O + U + L + D) 
+ (A + C + Q + U + A + I + N + T + A + N + C + E);

% NEW and YEAR have the same value
constraint (N + E + W) == (Y + E + A + R);

% NEW is similar OLD, but with its two digits in the reverse order
var 10..99:NEW == N + E + W;
var 10..99:OLD == O + L + D;
var 1..9:a; var 1..9:b;
var 1..9:c; var 1..9:d;

constraint a == NEW mod 10 /\ b == NEW div 10;
constraint c == OLD mod 10 /\ d == OLD div 10;
constraint a == d /\ b == c;

solve satisfy;

output ["[N, E, W] = " ++ show([N, E, W]) 
++ "\n" ++ "NEW = " ++ show(NEW)
++ "\n" ++ "OLD = " ++ show(OLD)
];

% [N, E, W] = [3, 11, 23]
% NEW = 37
% OLD = 73

      Like

    • Frits's avatar

      Frits 1:05 pm on 19 April 2023 Permalink | Reply

      Not as fast as my version of Brian’s program.

      [https://brg.me.uk/?page_id=1756#comment-3740]

       
from enigma import SubstitutedExpression

# invalid digit / symbol assignments
d2i = dict()
for d in range(0, 27):
  vs = set()
  if d == 0: vs.update('ABCDEHILNOQRSTUWY')
  # 71 <= OLD <= 74
  # 3A + 2CNU + EHIQST = OLD
  # 3×5 + 2×(1 + 2 + 3) + (4 + 6 + 7 + 8 + 9 + x) <= 74 
  # so x <= 13
  if d > 13: vs.update('NECUHIQST')
  
  if d < 20: vs.update('OLD')
  if d < 21: vs.update('LD')
  if d < 22: vs.update('D')
  if d > 24: vs.update('O')
  if d > 25: vs.update('OL')

  d2i[d] = vs

# the alphametic puzzle
p = SubstitutedExpression(
  [
    # order not important
    "O < L < D",      # order not important
    # NEW is like the value of OLD with digits in the reverse order
    "(10 * ((old := O + L + D) % 10) + old // 10) - N - E = W",
    
    "C < U",          # order not important
    
    # 3×5 + 2×(C + N + U) + (1 + 2 + 3 + 4 + 6 + 7) <= 74 
    # thus the maximum of C + N + U is 18 
    "(cnu := C + N + U) <= 18",
    
    # 3A + 2CNU + EHIQST = OLD, determine value of HIQST 
    # check if remaining numbers are too high for making target HIQST
    "(hiqst := old - 3 * A - 2 * cnu - E) >= 16",
    
    "hiqst >= sum(sorted(set(range(1, 14)) - {A, C, E, N, U})[:5])",
    
    "H < I < Q < T",  # order not important
    
    # OLD is the average of the values SHOULD and ACQUAINTANCE 
    "old - (H+U + A+C+Q+U+A+I+N+T+A+N+C+E) = S",
    "Q < S < T",     # order not important
    
    #  NEW and YEAR have the same value
    "N + W - Y - A = R",
    "R < Y",         # order not important
    
  ],
  answer="N + E + W",
  base=27,
  d2i=d2i,
  s2d=dict(A=5, B=24),
  reorder=0,
  verbose=0,    # use 256 to see the generated code
)

# print answers
for (_, ans) in p.solve():
  print(f"{ans}")

      Like

  • Unknown's avatar

    Jim Randell 9:09 am on 16 April 2023 Permalink | Reply
    Tags: by: R J Webster   

    Brain teaser 977: Little boy blue 

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

    The baby department of our local store has just organised a raffle. The tickets were numbered consecutively from one upwards and were made into large books, each containing the same number of consecutive tickets.

    Numbers having at least one repeated digit were printed on blue paper and those having all their digits different were printed on pink paper. It turned out that there was an equal number of blue and pink tickets. The prize was a generously equipped layette in the colour of the winning ticket.

    Being the first person to buy a ticket, I had the opportunity to see that among the large collection of books only one of them consisted of tickets all of the same colour, and it was the colour I wanted too.

    Spoilt for choice, I bought the ticket in the middle of this book. My choice was fully justified: I won the prize!

    What was my winning number?

    The version of the puzzle published in the book Microteasers (1986), also includes the additional question:

    How many tickets were there?

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

    [teaser977]

     
    • Jim Randell's avatar

      Jim Randell 9:09 am on 16 April 2023 Permalink | Reply

      This Python program runs in 72ms. (Internal runtime is 13.0ms).

      Run: [ @replit ]

      from enigma import (
  irange, inf, is_duplicate, divisors_pairs,
  seq_all_same, singleton, printf
)

blue = pink = 0
ts = [None] # there is no ticket 0

# look for books with tickets the same colour
def same_colour(ts, n, k):
  for i in irange(1, n, step=k):
    if seq_all_same(ts[i] for i in irange(i, i + k - 1)):
      yield i

# consider number of tickets
for n in irange(1, inf):
  f = is_duplicate(n)
  ts.append(f)
  if f:
    blue += 1
  else:
    pink += 1

  if blue == pink:
    printf("total={n} [blue={blue} pink={pink}]")

    # consider j books, each with k tickets
    done = 0
    for (j, k) in divisors_pairs(n, every=1):
      # k is odd (and  > 1)
      if not (k > 1 and k % 2 == 1): continue
      # find books with tickets all the same colour
      b = singleton(same_colour(ts, n, k))
      if b is None: continue
      printf("-> {j} books, each with {k} tickets -> {b} .. {x}", x=b + k - 1)
      if k % 2 == 1:
        # find the middle ticket
        t = b + (k // 2)
        printf("-> middle ticket = {t}")
        done += 1

    if done: break

      Solution: The winning number was: 10073.

      There were 44 books, each with 255 tickets, making 11220 tickets in total. 5610 of them are blue, and 5610 of them are pink.

      The book of tickets from 9946 – 10200 consists of 255 tickets, all of which have repeated digits, so are coloured blue.

      The ticket in the middle of this book is 10073 (there are 127 tickets before it and 127 tickets after it).

      Like

    • Hugo's avatar

      Hugo 10:48 am on 16 April 2023 Permalink | Reply

      Is it possible that there were 187 tickets per book? In that case there would be a book 9912 – 10098,
      with middle number 10005. If it had been fewer than 187, there would be two all-blue books.

      I think the longest possible run with repeated digits is 357, from 9877 to 10233.

      Like

      • Frits's avatar

        Frits 11:28 am on 16 April 2023 Permalink | Reply

        @Hugo, as 187 is less than 220 (there are 11220 tickets in total) the last book must be all-blue as well (all tickets of the form 11xxx).

        Like

  • Unknown's avatar

    Jim Randell 4:34 pm on 14 April 2023 Permalink | Reply
    Tags: ,   

    Teaser 3160: Hymn number anagrams 

    From The Sunday Times, 16th April 2023 [link] [link]

    At Church on Sunday, the hymn board showed just four different hymn numbers, each having the same three, different, non-zero digits, but in a different order. I noticed that the first hymn number was a perfect square, and that there was at least one other perfect square, formed from the same three digits, which did not appear on the board. The sum of the four hymn numbers was a prime number. If I told you the first digit of that prime number, you would be able to tell me the first hymn number on the board.

    What was the first hymn number on the board?

    [teaser3160]

     
    • Jim Randell's avatar

      Jim Randell 5:02 pm on 14 April 2023 Permalink | Reply

      As worded there are multiple answers to this puzzle.

      However we can get a unique answer if we are told the last digit of the prime sum (not the first digit).

      This Python program runs in 64ms. (Internal runtime is 503µs).

      Run: [ @replit ]

      from enigma import (
  irange, sq, nsplit, ordered, group, item, subsets,
  nconcat, is_prime, filter_unique, unpack, printf
)

# generate possible 3-digit squares, and their digits (ordered)
def squares():
  # consider 3-digit squares
  for i in irange(10, 31):
    n = sq(i)
    # there should be 3 different non-zero digits
    ds = nsplit(n, fn=set)
    if len(ds) != 3 or 0 in ds: continue
    # return (<square>, <digits>)
    yield (n, ordered(*ds))

# generate candidate solutions
def generate():
  # group possible squares by their digits
  g = group(squares(), by=item(1), f=item(0), fn=set)

  # choose a set of digits with (at least) 2 squares
  for (ds, sqs) in g.items():
    if len(sqs) < 2: continue
    # construct all rearrangements of the digits
    rs = list(nconcat(ss) for ss in subsets(ds, size=len, select='P'))
    # choose 4 of the candidates
    for ns in subsets(rs, size=4):
      # at least one square must be unused
      if sqs.issubset(ns): continue
      # at least one square must be present
      fs = sqs.intersection(ns)
      if not fs: continue
      # the sum should be a prime
      t = sum(ns)
      if not is_prime(t): continue
      # yield solutions (<first>, <sum>, <all>)
      for n in fs:
        printf("[first={n} hymns={ns} sum={t}; unused={xs}]", xs=sorted(sqs.difference(ns)))
        yield (n, t, ns)

# if we knew the first digit of the total, we could deduce the number of the first hymn
f = unpack(lambda n, t, ns: nsplit(t)[0])  # first digit of total
g = unpack(lambda n, t, ns: n)  # first hymn number
ss = filter_unique(generate(), f, g).unique

# output solution
for (n, t, ns) in ss:
  printf("prime = {t} -> hymns = {ns}, first = {n}")

      Solution: There are two possibilities: 256 and 961.

      There are only two sets of 3 distinct digits that can form multiple squares:

      {1, 6, 9} → 169 (=13²), 196 (= 14²), 961 (= 31²)
      {2, 5, 6} → 256 (=16²), 625 (= 25²)

      And these lead to the 5 possible arrangements of hymns that fit the requirements:

      first = 256; rest = 265, 526, 562; sum = 1609; unused square = 625
      first = 256; rest = 265, 526, 652; sum = 1699; unused square = 625
      first = 961; rest = 196, 619, 691; sum = 2467; unused square = 169
      first = 196; rest = 619, 691, 961; sum = 2467; unused square = 169
      first = 961; rest = 619, 691, 916; sum = 3187; unused square = 169, 196

      If we are told the first digit of the sum is 1, then we see the first hymn must be 256. (We can also determine that two of the three other hymns are 265 and 526, but without more information we can’t determine if the remaining hymn is 562 or 652).

      And if we are told the first digit of the sum is 3, then we see the first hymn must be 961. (In this case we can determine that the other three hymn are 619, 691 and 916).

      These are the two possible answers.

      It is possible we are meant to read “if I told you the first digit [of the sum], you would be able to tell me the first hymn number on the board” to mean that although we can deduce the first hymn number on the board, we cannot deduce with certainty all of the other three numbers. And this removes one of the viable answers, leaving a unique solution to the puzzle.

      But I think if this was the intended interpretation, the puzzle text should have been worded more clearly.

      Like

    • Frits's avatar

      Frits 7:19 pm on 14 April 2023 Permalink | Reply 

      from enigma import SubstitutedExpression, is_square_p, is_prime
from itertools import combinations as comb

# return number of perfect squares in a sequence of numbers
def n_squares(seq):
  return sum(is_square_p(x) for x in seq)

# the alphametic puzzle
p = SubstitutedExpression(
  [
    # first item ABC must be a perfect square
    "n_squares([ABC])",
    # there was at least one other perfect square
    "n_squares(r5 := [ACB, BAC, BCA, CAB, CBA])",
    
    # the sum of the four hymn numbers is a prime number
    # (choose c for the 2 numbers not displayed on the board)
    "len(primes := [p for c in comb(r5, 2) if n_squares(c) \
         if is_prime(p := (ABC + sum(x for x in r5 if x not in c)))]) > 0",
  ],
  answer="ABC, primes",
  env=dict(n_squares=n_squares, comb=comb),
  digits=range(1, 10),
  reorder=0,    # advisable when using assignment statements
  verbose=0,    # use 256 to see the generated code
)

d = dict()
# process answers
for (_, ans) in p.solve():
  # store first hymn number for first digit of prime number
  for p in ans[1]:
    d[str(p)[0]] = d.get(str(p)[0], set()) | {ans[0]}

print("answers:", [vs.pop() for k, vs in d.items() if len(vs) == 1])

      Like

      • Jim Randell's avatar

        Jim Randell 10:22 pm on 14 April 2023 Permalink | Reply

        @Frits: That’s a clever use of assignment expressions. I hadn’t thought about how they could be useful in [[ SubstitutedExpression ]] recipes. Although, as you say, you need [[ reorder=0 ]].

        Like

    • GeoffR's avatar

      GeoffR 5:04 pm on 16 April 2023 Permalink | Reply

      I also found two solutions with different digits of the first hymn number.
      The method of solution is described at the start of the program.

      # Method
# I noticed that the first hymn number was a perfect square,
# and that there was at least one other perfect square,
# formed from the same three digits, which did not appear on the board.
# ... so 1 or 2 squares not on the hymn board and 1 square on the board.

from math import isqrt
from collections import defaultdict
from itertools import product, combinations
from enigma import is_prime, all_different

HYMNS = defaultdict(list)
# Dictionary key is sum of first four numbers (a prime)
# Dictionary value is a tuple of the six 3-digit numbers

def is_sq(n):
  return (isqrt(n) ** 2 == n)
    
def sq_count (n1, n2, n3, n4, n5, n6):
  try:
    cnt = 0
    for c in [n1, n2, n3, n4, n5, n6]:
      if is_sq(c):
        cnt += 1
      # 2 or 3 squares in 6 numbers
      if cnt == 2 or cnt == 3:
        return cnt
  except:
    print("Error in counting squares")
    return

# Assumed 2 or 3 squares in the 6 no. 3-digit numbers 
for sq_cnt in range(2, 4):
  for c1, c2, c3 in product(range(1, 10), repeat=3):
    if all_different(c1, c2, c3):
      # find 6 no. 3-digit numbers
      ABC, DEF = 100*c1 + 10*c2 + c3, 100*c1 + 10*c3 + c2
      GHI, JKL = 100*c2 + 10*c1 + c3, 100*c2 + 10*c3 + c1
      MNO, PQR = 100*c3 + 10*c1 + c2, 100*c3 + 10*c2 + c1
      # count number of squares in these 6 numbers
      sq_cnt = sq_count(ABC,DEF,GHI,JKL,MNO,PQR)
      
      # The number of squares in the 6 numbers is either 2 or 3
      # check for 2 squares in 6 numbers        
      if sq_cnt == 2:
        # the first 4 hymn nos. contain 1 square only (i.e. 1st)
        # .. and the last 2  numbers 1 square only
        for p1 in combinations((ABC, DEF,GHI,JKL,MNO,PQR), 6):
          if is_sq(ABC):
            # 4 hymn numbers are ABC, DEF, GHI, JKL
            if all(not is_sq(x) for x in (DEF,GHI,JKL)):
              if is_prime(ABC + DEF + GHI + JKL):
                  HYMNS[ABC+DEF+GHI+JKL] += [(ABC,DEF,GHI,JKL,MNO,PQR)]
                
      # check for 3 squares in 6 numbers        
      if sq_cnt == 3:
        for p1 in combinations((ABC,DEF,GHI,JKL,MNO,PQR), 6):
          # squares are 1st, 5th and 6th 3-digit numbers
          #... as first 4 numbers assumed 1 square only(i.e 1st)
          if is_sq(ABC) and is_sq(MNO) and is_sq(PQR):
            if is_prime(ABC + DEF + GHI + JKL):
              HYMNS[ABC+DEF+GHI+JKL] += [(ABC,DEF,GHI,JKL,MNO,PQR)]

# Find the four numbers on the hymn board                   
for k, v in HYMNS.items():
    print(f"The first hymn number on the board was {v[0][0]}.")
    print(f"HYMN NUMBERS: {v[0][0]}, {v[0][1]}, {v[0][2]}, {v[0][3]}.")
    print()

      Like

    • GeoffR's avatar

      GeoffR 7:17 pm on 17 April 2023 Permalink | Reply

      Much shorter code in MiniZinc ,with same two possible answers. 

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

var 1..9:a; var 1..9:b; var 1..9:c; 
constraint all_different([a, b, c]);
 
predicate is_sq(var int: y) =
exists(z in 1..ceil(sqrt(int2float(ub(y))))) (z*z = y );

predicate is_prime(var int: x) = 
x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
((i < x) -> (x mod i > 0));
  
% ABC, DEF, GHI and JKL are Hymn Board numbers - ABC is 1st number
var 100..999:ABC = 100*a + 10*b + c;
var 100..999:DEF = 100*a + 10*c + b;
var 100..999:GHI = 100*b + 10*a + c;
var 100..999:JKL = 100*b + 10*c + a;
% MNO and PQR are possible squares off the Hymn Board
var 100..999:MNO = 100*c + 10*a + b;
var 100..999:PQR = 100*c + 10*b + a;

constraint is_sq(ABC); % 1st number on Hymn Board is a square
% One or both numbers off the Hymn Board are squares
constraint (is_sq(MNO) \/ is_sq(PQR)) \/ (is_sq(MNO) /\ is_sq(PQR));
constraint not is_sq(DEF) /\ not is_sq(GHI) /\ not is_sq(JKL);

% The sum of the numbers on the Hymn Board is a prime
constraint is_prime(ABC + DEF + GHI + JKL);

solve satisfy;
% Four Hymn numbers are ABC, DEF,GHI and JKL
output [  "[ABC, DEF, GHI, JKL, MNO, PQR] =" 
++ show( [ABC, DEF, GHI, JKL, MNO, PQR]  )];

      Like

  • Unknown's avatar

    Jim Randell 9:14 am on 13 April 2023 Permalink | Reply
    Tags:   

    Teaser 2697: Gimme five! 

    From The Sunday Times, 1st June 2014 [link] [link]

    In the list of words below each different letter consistently represents a different digit. Each of the coded numbers has the property that the sum of its digits is divisible by (but not equal to) the number it spells out:

    THREE
    FIVE
    EIGHT
    NINE
    TEN
    ELEVEN
    THIRTEEN

    What number does FIVE represent?

    [teaser2697]

     
    • Jim Randell's avatar

      Jim Randell 9:15 am on 13 April 2023 Permalink | Reply

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

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

      Run: [ @replit ]

      #! python3 -m enigma -rr

SubstitutedExpression

"div(T + H + R + E + E, 3) > 1"
"div(F + I + V + E, 5) > 1"
"div(E + I + G + H + T, 8) > 1"
"div(N + I + N + E, 9) > 1"
"div(T + E + N, 10) > 1"
"div(E + L + E + V + E + N, 11) > 1"
"div(T + H + I + R + T + E + E + N, 13) > 1"

--template="THREE FIVE EIGHT NINE TEN ELEVEN THIRTEEN"
--answer="FIVE"

      Solution: FIVE = 8237.

      We have:

      THREE = 45177
      FIVE = 8237
      EIGHT = 72654
      NINE = 9297
      TEN = 479
      ELEVEN = 707379
      THIRTEEN = 45214779

      Like

    • GeoffR's avatar

      GeoffR 10:24 am on 14 April 2023 Permalink | Reply 

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

% Leading digits of numbers
var 1..9:T; var 1..9:F; var 1..9:E; var 1..9:N;
% Other digits in numbers
var 0..9:I; var 0..9:H; var 0..9:R;
var 0..9:G; var 0..9:V; var 0..9:L;
 
constraint all_different([T, F, E, N, I, H, R, G, V, L]);

% For each number, sum of its digits is divisible by (but not equal to) the number it spells out
constraint (T + E + N) mod 10 == 0 /\ (T + E + N) div 10 > 1;
constraint (N + I + N + E) mod 9 == 0 /\ (N + I + N + E) div 9 > 1;
constraint (T + H + R + E + E) mod 3 == 0 /\ (T + H + R + E + E) div 3 > 1;
constraint (F + I + V + E) mod 5 == 0 /\ (F + I + V + E) div 5 > 1;
constraint (E + I + G + H + T) mod 8 == 0 /\ (E + I + G + H + T) div 8 > 1;
constraint (E + L + E + V + E + N) mod 11 == 0 /\ (E + L + E + V + E + N) div 11 > 1;
constraint (T + H + I + R + T + E + E + N) mod 13 == 0 /\ (T + H + I + R + T + E + E + N) div 13 > 1;

solve satisfy;

% Digits of numbers in teaser
output ["[T,H,R,E,E ] = " ++ show([T,H,R,E,E ] )
++ "\n" ++ "[F,I,V,E] = " ++ show ([F,I,V,E] )
++ "\n" ++ "[E,I,G,H,T] = " ++ show([E,I,G,H,T] )
++"\n" ++ "[N,I,N,E] = " ++ show([N,I,N,E])
++"\n" ++ "[T,E,N] = " ++ show ([T,E,N] )
++ "\n" ++ "[E,L,E,V,E,N] = " ++ show ([E,L,E,V,E,N] )
++ "\n" ++ "[T,H,I,R,T,E,E,N] = " ++ show ([T,H,I,R,T,E,E,N] )
];

% [T,H,R,E,E ] = [4, 5, 1, 7, 7]
% [F,I,V,E] = [8, 2, 3, 7]   - so FIVE = 8237 (answer)
% [E,I,G,H,T] = [7, 2, 6, 5, 4]
% [N,I,N,E] = [9, 2, 9, 7]
% [T,E,N] = [4, 7, 9]
% [E,L,E,V,E,N] = [7, 0, 7, 3, 7, 9]
% [T,H,I,R,T,E,E,N] = [4, 5, 2, 1, 4, 7, 7, 9]
% ----------
% ==========
% Finished in 180msec

      Like

  • Unknown's avatar

    Jim Randell 9:41 am on 11 April 2023 Permalink | Reply
    Tags:   

    Teaser 2703: Bastille Day 

    From The Sunday Times, 13th July 2014 [link] [link]

    Three towns in France issue their own car licence plates. Argentan’s numbers consist of the digits 1 to 9 in some order, Beaurepaire’s consist of the digits 1 to 8 in some order, and Corbigny’s consist of the digits 1 to 7 in some order. All three towns only use numbers divisible by 11 and all such possible plates have been issued. Tomorrow is Bastille Day and, in order to minimise chaos, only cars with licence numbers divisible by 5 will be allowed in.

    In the form “one in …”

    (a) What proportion of Argentan’s cars will be allowed into Argentan?

    (b) What proportion of Beaurepaire’s cars will be allowed into Beaurepaire?

    (c) What proportion of Corbigny’s cars will be allowed into Corbigny?

    [teaser2703]

     
    • Jim Randell's avatar

      Jim Randell 9:42 am on 11 April 2023 Permalink | Reply

      I assumed each valid number plate is a rearrangement of all allowable digits (each appearing exactly once).

      This Python program constructs the valid plates, and counts those divisible by 5. It runs in 189ms.

      Run: [ @replit ]

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

# solve the puzzle
qs = dict(A=irange(1, 9), B=irange(1, 8), C=irange(1, 7))
for k in sorted(qs.keys()):
  ds = qs[k]
  # count plates divisible by 11 (t) and those divisible by 5 (n)
  t = n = 0
  for s in subsets(ds, size=len, select='P'):
    p = nconcat(s)
    if p % 11 == 0:
      t += 1
      if p % 5 == 0:
        n += 1
  # find the fraction
  (a, b) = fraction(n, t)
  # output solution
  printf("{k}: {t} plates, {n} divisible by 5 = {a}/{b}")

      Solution: (a) 1 in 11; (b) 1 in 8; (c) 1 in 8.

      The counts for total number of plates, and permitted plates are:

      A: total = 31680, permitted = 2880 (1 in 11)
      B: total = 4608, permitted = 576 (1 in 8)
      C: total = 576, permitted = 72 (1 in 8)

      Like

  • Unknown's avatar

    Jim Randell 10:12 am on 9 April 2023 Permalink | Reply
    Tags: , ,   

    Teaser 2161: Love hearts 

    From The Sunday Times, 15th February 2004 [link]

    Bobby has made a Valentine’s card for his girlfriend Chin-We. He drew some increasing rows of touching circles, like those shown, but with more rows. Then he put a red heart in as many circles as possible without three of their centres forming an equilateral triangle. Then he put a pink heart in some of the remaining circles, and a white heart in the rest.

    When Bobby counted the number of hearts of red, of pink and of white, he got three totals which (not necessarily in that order) formed three consecutive numbers.

    How many red hearts are on the card?

    Although the puzzle can be solved, the published solution was incorrect, and there are in fact two possible correct answers.

    [teaser2161]

     
    • Jim Randell's avatar

      Jim Randell 10:13 am on 9 April 2023 Permalink | Reply

      I recently revisited Enigma 82 and Enigma 144 and this puzzle can also be solved using similar techniques.

      The number of cells for an arrangement with n rows is obviously tri(n).

      And if the number of red, pink and white hearts are {k − 1, k, k + 1} (in some order), then we can only find a solution when:

      tri(n) = 3k

      And so we can skip cases where tri(n) is not divisible by 3, i.e. n = 4, 7, 10, 13, …

      Once we calculate the possible configurations that give equilateral triangles we can determine a minimum hitting set for these configurations, and all the remaining cells can then be coloured red without giving a configuration that has three reds forming an equilateral triangle, and this is the maximum possible number of reds.

      If this number in in the set {k − 1, k, k + 1} then we have a viable solution, and the cells that form the hitting set can be divided into an appropriate number of pink and white cells.

      This Python program uses the MiniZinc implementation of the minimum hitting set problem and can be used to examine the puzzle for various values of n. The first solution presents itself at n = 11, which the program solves in 3m35s (using the “scip” solver).

      from enigma import (irange, subsets, div, empty, arg, printf)
from utils_mzn import hitting_set

# distance metric (cosine rule)
# returns the square of the distance
def dist(p, q):
  ((px, py), (qx, qy)) = (p, q)
  (a, b) = (abs(px - qx), abs(py - qy))
  c = (1 if (px < qx) != (py < qy) else -1)
  return a * a + b * b - a * b * c

# specify number of rows
N = arg(9, 0, int)

# enumerate the cells
n = N - 1
vs = set((a, b) for a in irange(0, n) for b in irange(0, n - a))

# find the set of equilateral triangles
tris = set()
for (a, b, c) in subsets(vs, size=3):
  # is the triangle equilateral
  if dist(a, b) == dist(b, c) == dist(a, c):
    tris.add((a, b, c))

T = len(vs)
t = len(tris)
x = div(T, 3)
ss = ({x - 1, x, x + 1} if x is not None else empty)
printf("[N={N} -> {T} cells, {t} equilateral triangles, sequence = {ss}]", ss=sorted(ss))

# find a minimum hitting set for the equilateral triangles
hs = hitting_set(tris, solver="minizinc --solver scip")
printf("minimum hitting set size = {n}", n=len(hs))

r = T - len(hs)  # max number of red hearts
printf("maximum red hearts = {r}")
printf("*** {x}SOLUTION ***", x=('' if r in ss else 'NOT A '))

      Solution: The smallest solution has 22 red hearts (with 11 rows of circles), but 25 red hearts is also possible (with 12 rows of circles).

      t = tris; r = reds
 n     t    seq        r  [scip  ] [highs ]
 2     1    0,1,2      2           [ 188ms] [SOLUTION]
 3     5    1,2,3      4           [ 194ms]
 4    15    -          6           [ 188ms]
 5    35    4,5,6      8           [ 206ms]
 6    70    6,7,8     10           [ 242ms]
 7   126    -         12  [ 481ms] [ 449ms]
 8   210    11,12,13  14  [ 1.41s] [  1.5s]
 9   330    14,15,16  17  [ 4.77s] [  7.6s]
10   495    -         20  [ 14.0s] [ 37.5s]
11   715    21,22,23  22  [ 3m02s] [13m14s] [SOLUTION]
12  1001    25,26,27  25  [28m29s] [ 2h15m] [SOLUTION]
13  1365    -         28  [ 8h18m] [35h21m]
14  1820    34,35,36  31

      t = OEIS A000332
      r = OEIS A240114

      The numbers in seq appear to be growing more rapidly than the numbers in r, so it seems likely these are the only solutions.

      The solution at n = 2 is disallowed as the puzzle text implies that n > 3 (and also as it requires one of the colours to have no corresponding cells).

      Here are some example maximal layouts for various n values:

      The published solution is that there were 16 red hearts.

      And so the numbers of red, pink, white hearts must be 14, 15, 16 to make a total of 45 cells, hence the arrangement has 9 rows.

      However, as we have seen above, the maximum number red hearts for an arrangement with 9 rows is actually 17, so we do not get a solution at n = 9.

      It is possible that the setter(s) assumed that the “inverted-V” shape that we see in solutions for n = 4, 5, 6, which gives a solution with 2(n − 1) red cells, would provide a maximal solution for larger n.

      Like

      • Frits's avatar

        Frits 8:49 pm on 15 April 2023 Permalink | Reply

        @Jim,

        I had a look at [ http://www.hakank.org/minizinc/hitting_set.mzn ] and tried the N=11 case in the MiniZinc program.

        Your model ran for 10 min 52 secs:

        solve minimize(sum(x));
....
constraint x[52] + x[54] + x[61] > 0;
constraint x[9] + x[21] + x[29] > 0;
....
constraint x[2] + x[9] + x[58] > 0;

        The model with predicate hitting_set ran for 6 min 20 secs:

        solve :: int_search(x, most_constrained, indomain_min, complete) minimize k;
....

n = 715;
v = [
{52, 61, 54},
{9, 29, 21},
....
{9, 2, 58}
];

        I guess it’s the “exists” statement in the predicate hitting_set that makes the difference.

        Like

        • Jim Randell's avatar

          Jim Randell 12:04 pm on 16 April 2023 Permalink | Reply

          @Frits: Thanks for the link. I did some tests (with MiniZinc 2.7.2), but found that in general my original formulation ran slightly faster than hakank’s model.

          However, I did download the “scip” solver, and found that it was able to solve the N=11 case in 3m15s, and the N=12 case in just 29m.

          Like

      • Jim Randell's avatar

        Jim Randell 11:58 am on 5 May 2023 Permalink | Reply

        It is possible to install commercial solvers that integrate with MiniZinc and are able to use multiple CPUs.

        The CPLEX solver can be installed from IBM (registration required), and this enables the cplex solver in MiniZinc (you may need to tell it where CPLEX is using the --cplex-dll parameter). You can then use the --parallel <n> parameter to enable multithreading.

        The free version of CPLEX is limited to models with 1000 variables/constraints, but this is sufficient for this problem up to N = 11, which is where the first solution is found. I found CPLEX could solve this using 4 threads in an elapsed time of 42.6s.

        Installing the gurobipy package via pip provides a license to use the Gurobi solver for models with up to 2000 variables/constraints. This is a bit trickier as the free version doesn’t integrate directly with MiniZinc, but I wrote a utils_gurobi.py module to provide the same interface via gurobipy.

        It solves (using 8 threads) the N = 11 case in 22.5s, and the N = 12 case in 9m07s, and the N = 13 case in 2h41m. And it should be able to do the N = 14 case.

        The Gurobi solver uses more CPU time than the (single-threaded) SCIP solver, but because it is able to use multiple CPUs the elapsed time is shorter.

        Like

        • Jim Randell's avatar

          Jim Randell 2:09 pm on 12 May 2023 Permalink | Reply

          Update: I ran the N = 14 case using the Gurobi solver. It took >161 hours (elapsed time), and used >750 hours total CPU time, a lot of RAM, and basically tied up my machine for a week.

          The size of the minimum hitting set is 74, which means the maximum number of red hearts is 31.

          The configuration found looks like this:

          Like

        • Frits's avatar

          Frits 4:57 pm on 12 May 2023 Permalink | Reply

          @Jim, are you going to publish utils_gurobi.py?

          Like

    • Frits's avatar

      Frits 2:14 pm on 13 May 2023 Permalink | Reply

      Or calling print_triangle(hs) for a graphical representation.

         
def print_triangle(s):
  # from top to bottom
  for r in range(N - 1, -1, -1):
    # in row r only (N - r) elements may be printed
    print(((r // 2) * "  " + (" " if r % 2 else "")), end=" ")
    for c in range(N - r):
      print("." if (r, c) in s else "R", end=" ")  
    print()

      Like

  • Unknown's avatar

    Jim Randell 3:57 pm on 7 April 2023 Permalink | Reply
    Tags:   

    Teaser 3159: King coin 

    From The Sunday Times, 9th April 2023 [link] [link]

    The new King’s currency has 64 Minims (circular coins) per Suttas (notes). Each coin’s value is proportional to its face area, and is a whole number of cm in diameter, starting with 1 cm for 1 Minim.

    The King only wanted denominations such that his citizens can pay any amount below 1 Suttas using no more than a certain number of coins for the transaction. This number is the smallest possible, given the above conditions. His mint suggested that if just two values could require an extra coin, they could reduce the number of denominations needed.

    The King agreed and placed one of each minted denomination flat and face up in a rectangular display, with each coin’s edge resting along the display’s base. The order of the coins minimised the width of the display, with the smallest coin to the right of the centre.

    What are the diameters in cm, from left to right?

    [teaser3159]

     
    • Jim Randell's avatar

      Jim Randell 4:59 pm on 7 April 2023 Permalink | Reply

      A bit involved. Once we have found the set of denominations suggested by the mint, we then have to determine the minimal width arrangement of the coins (which is not quite as straightforward as it might first appear).

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

      Run: [ @replit ]

      from enigma import (Accumulator, irange, sq, subsets, sqrt, find, printf)

# the 1 denomination is given
# possible remaining denominations (squares less than 64)
ps = dict((sq(i), i) for i in irange(2, 7))

# for each set of coins record values from 1 - 63 that can be made with just
# k coins, and record the smallest possible maximum value
ts = set(irange(1, 63))
d = dict()
K = Accumulator(fn=min, collect=1)
for ss in subsets(ps.keys()):
  # make the set of coins
  cs = (1,) + ss
  # values that can be made with up to k coins
  k = 0
  vs = {0}
  r = { k: vs }
  while ts.difference(vs):
    vs = vs.union(ts.intersection(v + x for v in vs for x in cs))
    k += 1
    r[k] = vs
  # record this set of values
  d[cs] = r
  K.accumulate_data(k, cs)

# find the smallest max number of coins required
# and the sets that achieve this
(k, css) = (K.value, K.data)
printf("change in {k} coins = {css}")

# calculate the total width (without overlaps) from a sequence of radii
dist = lambda a, b: 2 * sqrt(a * b)  # = sqrt(sq(a + b) - sq(a - b))
def width(rs):
  xs = list()
  for (i, r) in enumerate(rs):
    if i == 0:
      xs.append(r)
    else:
      x = max(xs[j] + dist(a, r) for (j, a) in enumerate(rs[:i]))
      xs.append(x)
  # calculate the width
  (a, b) = (min(x - r for (x, r) in zip(xs, rs)), max(x + r for (x, r) in zip(xs, rs)))
  w = b - a
  # and check the 1 coin is (entirely) in the right half of the arrangement
  i = find(rs, 1)
  if i != -1 and not (xs[i] - 1 > a + 0.5 * w): return None
  return w

# consider sets of coins
for (cs, r) in d.items():
  # must manage change in (k + 1) coins
  if not (max(r.keys()) == k + 1): continue
  # must be a (strict) subset of one of the sets that achieve change in k coins
  ss = set(cs)
  if not any(len(ss) < len(xs) and ss.issubset(xs) for xs in css): continue
  # find the values that require 5 coins
  xs = r[k + 1].difference(r[k])
  # there must be exactly 2 of them
  if len(xs) != 2: continue
  printf("reduced set = {cs}; change in {k1} coins = {xs}", k1=k + 1, xs=sorted(xs))

  # consider possible arrangements of coin radii
  W = Accumulator(fn=min, collect=1)
  for rs in subsets(list(ps.get(x, x) for x in cs), size=len, select='P'):
    w = width(rs)
    if w:
      W.accumulate_data(w, rs)

  # output solution
  for rs in W.data:
    printf("-> minimal width arrangement = {rs}")

      Solution: The diameters of the coins (left to right) are: 4cm, 2cm, 6cm, 1cm, 3cm.

      So they are arranged as follows:

      Note that the 1cm diameter coin does not contribute to the overall width of the display, as it fits in the gap between the 6cm and 3cm coin, but it is (wholly) in the right hand side of the display.

      The width of the minimum arrangement (distance between the red lines) is: 14.04cm.

      The smallest number of coins for which all change amounts can be given is 4.

      This can be achieved using the following denominations:

      (1, 4, 9, 16, 25, 36)
      (1, 4, 9, 16, 36, 49)
      (1, 4, 9, 16, 25, 36, 49)

      The last of these is a set consisting of all possible coins, and this must be able to change all amounts using the smallest possible number of coins.

      So the King could have suggested any of these sets.

      The mint then suggested a reduced set of coins, which all change amounts can be made in at most 4 coins, except for 51 and 59 (which require 5 coins).

      This set is:

      (1, 4, 9, 16, 36)
      51 = 1× 1 + 2× 9 + 2× 16 (5 coins)
      59 = 3× 9 + 2× 16 (5 coins)

      The names “Minim” and “Suttas” were chosen as together they use the letters from “numismatist” (i.e. a collector of coins).

      >>> multiset("minim" + "suttas") == multiset("numismatist")
True

      Like

    • Brian Gladman's avatar

      Brian Gladman 6:56 pm on 8 April 2023 Permalink | Reply

      Nice work on the “circles width” algorithm Jim. I initially missed the subtleties involved here which make what seems at first to be an easy task surprisingly difficult.

      Like

      • Jim Randell's avatar

        Jim Randell 10:30 pm on 8 April 2023 Permalink | Reply

        Yes, it is quite a tricky one. It took me a couple of goes to come up with a routine to calculate the minimum width correctly, which was not as simple as I had originally thought it would be.

        Like

    • Hugo's avatar

      Hugo 7:27 pm on 16 April 2023 Permalink | Reply

      That’s a relief not to have to keep 49-minim coins in my pocket.
      Even the 36-minim coin is rather large,
      but at least this one isn’t as silly as Teasers 1812 and 2926,
      where the value of a coin is proportional to its diameter.

      We see why, in the real world, it’s more usual to have the value of a coin proportional to its weight (which is likely to rise as the cube of the diameter), and with several series (e.g. copper, nickel-silver, and some other alloy).

      Like

    • Hugo's avatar

      Hugo 1:49 pm on 17 April 2023 Permalink | Reply

      The horizontal distance between the centres of the coins of diameter 6 and 1 is √6 ≈ 2.449.
      The horizontal distance between the centres of the coins of diameter 1 and 3 is √3 ≈ 1.732.
      The horizontal distance between the centres of the coins of diameter 6 and 3 is √18 ≈ 4.263,
      which is slightly greater than the sum of the other two, so the smallest coin has room to rattle.
      Add on √8 ≈ 2.828 and √12 ≈ 3.464 and the radii 2 and 1.5 of the outer coins,
      and we get about 14.035 between Jim’s red lines (all in cm, of course).

      It’s basically a simple calculation, thanks to Pythagoras,
      but I still managed to get the wrong configuration.
      The clever bit, I reckon, was spotting the anagram of numismatist.

      Like

  • Unknown's avatar

    Jim Randell 9:26 am on 6 April 2023 Permalink | Reply
    Tags:   

    Teaser 2691: Hot × buns 

    From The Sunday Times, 20th April 2014 [link] [link]

    I have consistently replaced each of the digits 0 to 9 by a different letter to turn some numbers into words. It turns out that the number EASTER is exactly divisible by each of:

    (a) the number of days in a week;
    (b) the number of days in a year;
    (c) the seasonal product HOT × BUNS.

    What numbers do HOT and BUNS represent?

    This puzzle is included in the book The Sunday Times Brain Teasers 2 (2020), however the “×” sign is missing in condition (c).

    [teaser2691]

     
    • Jim Randell's avatar

      Jim Randell 9:26 am on 6 April 2023 Permalink | Reply

      I assume there are (a) 7 days a week; and (b) 365 days a year.

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

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

      Run: [ @replit ]

      #! python3 -m enigma -rr

SubstitutedExpression

"EASTER % 7 = 0"
"EASTER % 365 = 0"
"EASTER % (HOT * BUNS) = 0"

      Solution: HOT = 147; BUNS = 3285.

      And this is the only solution to the alphametic expression: EASTER % (HOT * BUNS) = 0.

      So it seems conditions (a) and (b) are just there to make things a bit easier.

      Like

    • GeoffR's avatar

      GeoffR 5:38 pm on 6 April 2023 Permalink | Reply 

      from itertools import permutations

for H, O, T in permutations ('1234567890', 3):
    if H == '0': continue
    HOT = int(H + O + T)
    # Find remaining seven digits
    q1 = set('1234567890').difference([H, O, T])
    for p2 in permutations(q1):
        E, A, S, R, B, U, N = p2
        if '0' in (E, B):continue
        BUNS = int(B + U + N + S)
        EASTER = int(E + A + S + T + E + R)
        if EASTER % 7 == 0 and EASTER % 365 == 0 \
           and EASTER % (HOT * BUNS) == 0:
           print(f"HOT = {HOT}, BUNS = {BUNS}, EASTER = {EASTER}")
    
# HOT = 147, BUNS = 3285, EASTER = 965790

      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