Updates from Jim Randell Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 9:33 am on 15 June 2023 Permalink | Reply
    Tags:   

    Teaser 2016: T for two 

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

    I have in mind a whole number less than 100. If I were to tell you the first letter in the spelling of that number, you would not be able to determine the number. But if I were to tell you both the first and last letters in the spelling of the number, then you would be able to determine it. Now, If I were to tell you just the last letter in the spelling of the number, you would be able to determine it.

    What is the number?

    [teaser2016]

     
    • Jim Randell's avatar

      Jim Randell 9:33 am on 15 June 2023 Permalink | Reply

      I supposed the numbers were from 1 to 99 (although you can also use 0 if you like).

      This Python program combines the [[ int2words() ]] and [[ filter_unique() ]] functions from the enigma.py library.

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

      Run: [ @replit ]

      from enigma import (irange, int2words, filter_unique, intersect, join, printf)
      
      # numbers from 1 to 99 as words
      ns = dict((n, int2words(n)) for n in irange(1, 99))
      
      # return a function to select letters at indices <js> from the spelling of a number
      select = lambda *js: (lambda k: join(ns[k][j] for j in js))
      
      # the number is ambiguous by first letter
      ss1 = filter_unique(ns.keys(), f=select(0)).non_unique
      
      # but unique by first + last letter
      ss2 = filter_unique(ns.keys(), f=select(0, -1)).unique
      
      # from these it is unique by last letter
      ss = filter_unique(intersect([ss1, ss2]), f=select(-1)).unique
      
      # output solution
      printf("{ss}", ss=join(ss, sep=", "))
      

      Solution: The number is 98.

      Like

    • Frits's avatar

      Frits 2:06 pm on 15 June 2023 Permalink | Reply

      Maintaining a dictionary.

         
      from enigma import int2words
      
      # lowercase letters
      letters = ''.join(chr(ord('a') + i) for i in range(26))
       
      # numbers from 1 to 99 as words
      nums = [int2words(n) for n in range(1, 100)]
      
      # the number is ambiguous by first letter
      d = {l: [x for x in nums if x[0] == l] for l in letters}
      d = {k: vs for k, vs in d.items() if len(vs) > 1}
      
      # but unique by first + last letter
      d = {l1 + l2: [x for x in nums if x[0] == l1 and x[-1] == l2 and x[0] in d] 
                     for l1 in letters for l2 in letters}
      d = {k: vs for k, vs in d.items() if len(vs) == 1}       
      
      # from these it is unique by last letter
      d = {k[-1]: [vs2 for k2, vs2 in d.items() if k[-1] == k2[-1]] for k in d}   
      d = {k: vs for k, vs in d.items() if len(vs) == 1}
      
      for k, v in d.items():
        print("answer:", *v[0])
      

      Like

  • Unknown's avatar

    Jim Randell 11:52 am on 13 June 2023 Permalink | Reply
    Tags:   

    Teaser 2177: Basic sum 

    From The Sunday Times, 6th June 2004 [link]

    You might look askance at the addition sum:

    But in fact each of the numbers is written in a different base. Just one of the four numbers is prime and just one is divisible by three. Also, when written in the normal decimal form, the last digits of the three numbers being added are all different, and the total is still a four-figure number.

    What is the total?

    [teaser2177]

     
    • Jim Randell's avatar

      Jim Randell 11:52 am on 13 June 2023 Permalink | Reply

      See also: Enigma 1358.

      This Python program collects numerical values of “1101” in various bases, such that the value is not more than 4 digits in decimal.

      It then looks for three of these values that sum to a fourth, and applies the remaining conditions.

      It runs in 56ms. (Internal runtime is 518µs).

      Run: [ @replit ]

      from enigma import (
        irange, inf, base2int, subsets, icount_exactly,
        is_prime, seq_all_different, join, printf
      )
      
      # is x divisible by 3?
      div3 = lambda x: x % 3 == 0
      
      # find values for <s> in various bases
      d = dict()
      for b in irange(2, inf):
        n = base2int('1101', base=b)
        if n > 9999: break
        d[n] = b
      
      # look for 3 of the values that sum to a 4th
      for ns in subsets(d.keys(), size=3, fn=list):
        t = sum(ns)
        if t < 1000 or t not in d: continue
        # the last digits of the summands (in base 10) are all different
        if not seq_all_different(n % 10 for n in ns): continue
        ns.append(t)
        # exactly one of the 4 numbers is divisible by 3
        if not icount_exactly(ns, div3, 1): continue
        # exactly one of the 4 numbers is prime
        if not icount_exactly(ns, is_prime, 1): continue
        # output solution
        bs = list(d[n] for n in ns)
        printf("{ns} = {t} [bases = {bs}]",
          ns=join(ns[:-1], sep=" + "),
          bs=join(bs, sep=", ", enc="()"),
        )
      

      Solution: The result of the sum is 7221 (in decimal).

      The sum is:

      1101 [base 6] = 253 [decimal] +
      1101 [base 9] = 811 [decimal] +
      1101 [base 18] = 6157 [decimal] =
      1101 [base 19] = 7221 [decimal]

      Like

      • Frits's avatar

        Frits 12:01 pm on 14 June 2023 Permalink | Reply

        @Jim, you don’t seem to have a proper check on “the total is still a four-figure number”.

        Like

    • GeoffR's avatar

      GeoffR 10:21 pm on 13 June 2023 Permalink | Reply

      
      from enigma import is_prime, all_different
      from itertools import combinations
      
      # max base for 4 digits is 21
      # sum is n1 + n2 + n3 = n4
      for b1, b2, b3, b4 in combinations(range(2, 22),4):
        n4 = int('1101', base = b4)
        # the total n4 is a four-figure number
        if n4 < 10000:
          n1 = int('1101', base = b1)
          n2 = int('1101', base = b2)
          n3 = int('1101', base = b3)
          # one of the four numbers is prime
          if sum  ((is_prime(n1), is_prime(n2), is_prime(n3),\
                    is_prime(n4))) == 1:
            # last digits of the three summands are all different
            if all_different( str(n1)[:-1], str(n2)[:-1], \
                              str(n3)[:-1]):
              # one of the four numbers is divisible by three
              if sum((n1 % 3 == 0, n2 % 3 == 0, n3 % 3 == 0, \
                      n4 % 3 == 0))== 1:
                # check total of sum is correct
                if n4 == n1 + n2 + n3:
                  print(f"Sum is : {n1} + {n2} + {n3} = {n4}.")
                  print(f"The bases are {b1}, {b2}, {b3} and {b4}.")
      
      # Sum is : 253 + 811 + 6157 = 7221.
      # The bases are 6, 9, 18 and 19.
      
      

      Like

    • GeoffR's avatar

      GeoffR 8:38 am on 14 June 2023 Permalink | Reply

      Quite slow in MiniZinc – nearly 3 sec with the Chuffed Solver.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      predicate is_prime(var int: x) = 
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
      ((i < x) -> (x mod i > 0));
      
      % Four numbers with four different number bases
      % min LB = 8 + 4 + 0 + 1 = 13
      % max UB = 21**3 + 21**2 + 0 + 1 = 9703
      var 13..9703:N1; var 13..9703:N2; var 13..9703:N3; var 13..9703:N4;
      var 2..21:b1; var 2..21:b2; var 2..21:b3; var 2..21:b4;
       
      % put bases in order
      constraint b2 > b1 /\ b3 > b2 /\ b4 > b3;
      
      % Form 4 numbers in 4 different bases in format 1101
      constraint N1 == 1 * b1 * b1 * b1 + 1 * b1 * b1 + 0 + 1;
      constraint N2 == 1 * b2 * b2 * b2 + 1 * b2 * b2 + 0 + 1;
      constraint N3 == 1 * b3 * b3 * b3 + 1 * b3 * b3 + 0 + 1;
      constraint N4 == 1 * b4 * b4 * b4 + 1 * b4 * b4 + 0 + 1;
      
      % Main sum
      constraint N1 + N2 + N3 == N4;
      
      % One of the four numbers is prime
      constraint sum([is_prime(N1), is_prime(N2), is_prime(N3), is_prime(N4)]) == 1;
      
      % One of the four numbers is prime is exactly divisible by three
      constraint sum([N1 mod 3 == 0, N2 mod 3 == 0, N3 mod 3 == 0, N4 mod 3 == 0]) == 1;
      
      % the last digits of the three summands are different
      constraint all_different([N1 mod 10, N2 mod 10, N3 mod 10]);
      
      solve satisfy;
      
      output["Total is " ++ show(N4) ++ "\n" 
      ++ "Sum is " ++ show(N1) ++ " + " ++ show(N2) ++ " + " ++ show(N3) ++ " = " ++ show(N4)
      ++ "\n" ++ "Bases are " ++ show([b1, b2, b3, b4])];
      
      % Total is 7221
      % Sum is 253 + 811 + 6157 = 7221
      % Bases are [6, 9, 18, 19]
      % ----------
      % ========== 
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 11:09 am on 11 June 2023 Permalink | Reply
    Tags:   

    Brain-Teaser 276: Electing a Chairman 

    From The Sunday Times, 14th August 1966 [link]

    The ten directors of the Everlasting Mutual Trust Company, Chairman (C), Secretary (S), Treasurer (T), Directors 1, 2, 3, 4, 5, 6, and Vice-Chairman (V), sat in that order to elect a new chairman.

    They all got one vote. No director voted for himself, or for his neighbour, or for the man who voted for him. No officer voted for an officer. C voted for the man who voted for the man who voted for 2, i.e. C vote vote vote 2 for short; and T vote vote vote 4, and V vote vote vote 5, and S vote vote vote 6. Director 4 did not vote for an officer. Neither C nor S voted for 3. The man getting a vote from 6 did not vote for 3.

    For whom did C, S, T, 1, 2, 3, 4, 5, 6, V respectively vote?

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

    [teaser276]

     
    • Jim Randell's avatar

      Jim Randell 11:09 am on 11 June 2023 Permalink | Reply

      Presumably each of them cast one vote, and received one vote.

      We can write “X vote vote vote Y” even more compactly as “X vote^3 Y”.

      This Python 3 program generates possible voting patterns, taking direct voting restrictions into account, and then checks the restrictions on voting chains.

      In Python 3.7+ dict() objects remember their insertion order, so the output should be in the required order.

      It runs in 111ms. (Internal runtime is 52ms).

      Run: [ @replit ]

      from enigma import (tuples, remove, update, map2str, printf)
      
      # multiple lookups on dict <d>
      def nget(d, k, n):
        while n > 0:
          k = d[k]
          n -= 1
        return k
      
      # the voters
      voters = "CST123456V"
      
      # determine invalid votes:
      invalid = dict((k, set()) for k in voters)
      # no-one votes for themselves
      for k in voters:
        invalid[k].add(k)
      # no-one votes for their neighbours
      for (x, y, z) in tuples(voters, 3, circular=1):
        invalid[y].update((x, z))
      # officers (CSTV) don't vote for other officers
      officers = "CSTV"
      for k in officers:
        invalid[k].update(officers)
      
      # generate possible votes
      # return <m>, map of <voter> -> <vote>
      def votes(ks, vs, m=dict()):
        # are we done?
        if not ks:
          yield m
        else:
          k = ks[0]
          xs = invalid[k]
          for v in vs:
            # reject invalid votes and reciprocal votes
            if v not in xs and (v not in m or m[v] != k):
              yield from votes(ks[1:], remove(vs, v), update(m, [(k, v)]))
      
      # 4 did not vote for an officer
      invalid['4'].update(officers)
      # neither C nor S voted for 3
      invalid['C'].add('3')
      invalid['S'].add('3')
      
      # who votes for who?
      for v in votes(voters, set(voters)):
        # check vote chains:
        # the man getting a vote from 6 did not vote for 3
        if nget(v, '6', 2) == '3': continue
        # C vote^3 2
        if nget(v, 'C', 3) != '2': continue
        # T vote^3 4
        if nget(v, 'T', 3) != '4': continue
        # V vote^3 5
        if nget(v, 'V', 3) != '5': continue
        # S vote^3 6
        if nget(v, 'S', 3) != '6': continue
        # output solution
        printf("{v}", v=map2str(v, sort=0))
      

      Solution: The votes are: C→6, S→2, T→3, 1→5, 2→C, 3→V, 4→1, 5→T, 6→S, V→4.

      Or as cycles:

      C → 6 → S → 2 (→ C)
      T → 3 → V → 4 → 1 → 5 (→ T)

      Like

    • Frits's avatar

      Frits 4:35 pm on 11 June 2023 Permalink | Reply

       
      from enigma import SubstitutedExpression
      
      # invalid digit / symbol assignments
      d2i = dict()
      for d in range(0, 10):
        vs = set()
        # no officer voted for an officer
        # director 4 did not vote for an officer 
        
        if d < 1 or d > 6: vs.update('NCSTV')
        else:  # 1 <= d <= 6
          # no director voted for himself or for his neighbour ..
          vs.update("KLMNOP"[max(0, d - 2):d + 1])
        
        if d == 0:
          vs.update("K")
        
        if d == 7:
          vs.update("P")
        
        # neither C nor S voted for 3
        if d == 3:
          vs.update("CS")   
        
        d2i[d] = vs
      
      # return index of person in sequence {seq> who voted <n>
      voted = lambda seq, n: seq.index(n)
      # return the man who voted for the man who voted for <n>
      vote3 = lambda seq, n: voted(seq, voted(seq, n))
      
      # officers CSTV and directors KLMNOP
      # VKLMNOPCST
      # 0123456789
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
         # choose assignment to T as C and S have fewer candidate values
         # T vote^3 4
         "vote3([V, K, L, M, N, O, P, C, S, -1], 4) = T",
      
         # the man getting a vote from 6 did not vote for 3
         "(r := [V, K, L, M, N, O, P, C, S, T])[P] != 3",
         
         # C vote^3 2 (C voted for the man who voted for the man who voted for 2)
         "vote3(r, 2) == C",
         # V vote^3 5
         "vote3(r, 5) == V",
         # S vote^3 6
         "vote3(r, 6) == S",
         
         # no director voted for the man who voted for him
         "all(x != voted(r, i) for i, x in enumerate([K, L, M, N, O, P], 1))",
        ],
        answer="[C, S, T, K, L, M, N, O, P, V]",
        d2i=d2i,
        env=dict(vote3=vote3, voted=voted),
        reorder=0,
        verbose=0,    # use 256 to see the generated code
      )
      
      # print answers
      for (_, ans) in p.solve():
        print(f"answer: {ans}")
      

      Like

  • Unknown's avatar

    Jim Randell 4:31 pm on 9 June 2023 Permalink | Reply
    Tags:   

    Teaser 3168: Number cruncher 

    From The Sunday Times, 11th June 2023 [link] [link]

    The gaslight glittered on the polished brass of the machine. “My Number Cruncher can calculate mechanically the result of a calculation on three positive whole numbers used once each, provided it is restricted to plus, times and brackets operations, declared the Engineer. He opened the delicate cover and made meticulous adjustments. “There, I have disposed it for one particular expression. Please put it to the test”.

    I chose three numbers, all greater than 1, and rotated the three dials to those positions. Then I cranked the handle until a delicate bell rang, and the result was indicated as 451. I made one more try, using the same three numbers although in a different order; this time the machine yielded 331.

    In ascending order, what were the three numbers I selected?

    [teaser3168]

     
    • Jim Randell's avatar

      Jim Randell 4:59 pm on 9 June 2023 Permalink | Reply

      Here is a generic solution:

      Each operation combines two numbers, so if we start with three numbers and end with one number there must be two operations involved.

      And if we get different results by reordering the numbers then the operations must be different.

      So we are looking at one of the following expressions:

      (a + b) × c
      (a × b) + c

      So we can start with the output number and try reversing one of the operations to give us two numbers, and then choose one of these numbers, reverse the other operation on it, and we end up with the three original numbers.

      We then need to find which of the expressions gives a sequence of input numbers that are common to both the output numbers.

      This Python program runs in 63ms. (Internal runtime is 4.7ms).

      Run: [ @replit ]

      from enigma import (irange, divisors_pairs, intersect, printf)
      
      # destruct an addition
      def destruct_add(n):
        for a in irange(2, n // 2):
          yield [a, n - a]
      
      # destruct a multiplication
      def destruct_mul(n):
        for (a, b) in divisors_pairs(n):
          if a > 1:
            yield [a, b]
      
      # find sets that can give the result <n> using operations <ops>
      def destruct(ns, ops):
        # are we done?
        if not ops:
          yield tuple(sorted(ns))
        else:
          op = ops[0]
          # choose one of the numbers to destruct
          for (i, x) in enumerate(ns):
            for xs in op(x):
              yield from destruct(ns[:i] + xs + ns[i + 1:], ops[1:])
      
      # numbers to solve
      ns = [451, 331]
      
      # consider possible operation orders
      exprs = {
        '(a * b) + c': (destruct_add, destruct_mul),
        '(a + b) * c': (destruct_mul, destruct_add),
      }
      for (k, ops) in exprs.items():
        # find input numbers in all sets
        for ss in intersect(destruct([n], ops) for n in ns):
          printf("{ns} -> {ss} [{k}]")
      

      Solution: The numbers are: 16, 19, 27.

      So the machine was set to calculate:

      (a × b) + c → result

      And the calculations were:

      a=16, b=27, c=19 → result = (16 × 27) + 19 = 451
      a=16, b=19, c=27 → result = (16 × 19) + 27 = 331

      Like

      • Jim Randell's avatar

        Jim Randell 10:47 pm on 9 June 2023 Permalink | Reply

        Or we can solve the specific problem from the puzzle text in a much faster way:

        (a × b) + c = x
        (a × c) + b = y

        (a + 1)(b + c) = x + y

        This Python program runs in 57ms. (Internal runtime is 98µs).

        Run: [ @replit ]

        from enigma import (irange, divisors_pairs, divf, divc, ordered, printf)
        
        (x, y) = (451, 331)
        for (p, q) in divisors_pairs(x + y, every=1):
          if p < 3: continue
          a = p - 1
          for c in irange(divc(y - q + 2, a), divf(y - 2, a)):
            b = q - c
            if a * b + c == x and a * c + b == y:
              printf("({x}, {y}) -> {ns}", ns=ordered(a, b, c))
        

        And this approach can be used to give a manual solution where there are only a few cases to consider.

        (But I still like the generic solution).


        Manually:

        331 is prime, so the expression cannot be of the form (a + b) × c, so we must be looking at (a × b) + c.

        So we need to find a, b, c such that:

        (a × b) + c = 451
        (a × c) + b = 331

        Adding these equations gives:

        (a + 1)(b + c) = 782

        And if we have:

        782 = p × q
        ⇒ a = p − 1; c = (331 − q) / (a − 1); b = q − c

        So we can examine the divisors of 782.

        There are only four possible decompositions: 1 × 782, 2 × 391, 17 × 46, 23 × 24.

        Hence a ∈ {16, 22, 33, 45}.

        And only a = 16 gives integer values for b and c.

        782 = 17 × 46 ⇒ a = 16; c = 19; b = 27

        Like

        • Frits's avatar

          Frits 11:06 pm on 9 June 2023 Permalink | Reply

          Nice, we already know that the first 2 divisors pairs can be ignored.

          Like

        • Frits's avatar

          Frits 11:05 pm on 10 June 2023 Permalink | Reply

          @Jim, I tried to understand the boundaries of your latest version and saw that the minimum for variable c wasn’t tight enough for the first value of a.

          We don’t have to loop over c as we can state:

          c = (y – q) / (a – 1)

          which has to be a whole number greater than 1

          Like

          • Jim Randell's avatar

            Jim Randell 11:36 pm on 10 June 2023 Permalink | Reply

            @Frits: That is cool. Makes things even simpler, and saves a few more µs.

            from enigma import (divisors_pairs, div, ordered, printf)
            
            (x, y) = (451, 331)
            
            for (p, q) in divisors_pairs(x + y, every=1):
              if p < 3: continue
              a = p - 1
              c = div(y - q, a - 1)
              if c is None or c < 2: continue
              b = q - c
              if b < 2: continue
              printf("({x}, {y}) -> {ns}", ns=ordered(a, b, c))
            

            Like

    • Frits's avatar

      Frits 6:37 pm on 9 June 2023 Permalink | Reply

      Less pythonic but more chance to optimise.

         
      from enigma import divisor_pairs
      
      # determine lowest number to minimize number of iterations
      nums = sorted([451, 331])
      
      # a + b + c and a * b * c are not possible (nothing changes)
      # (a + b) * c is not possibe as 331 is a prime number
      
      # check a + (b * c)
      for a in range(2, nums[0] - 3):
        # ignore divisor_pair with 1
        for b, c in list(divisor_pairs(nums[0] - a))[1:]:
          # check 2 options
          if nums[1] in {b + (a * c), c + (b * a)}:
            pr("answer", sorted([a, b, c]))
      

      Like

      • Frits's avatar

        Frits 10:48 pm on 9 June 2023 Permalink | Reply

        More complex but a little different.

           
        from enigma import is_square, div
        
        # determine lowest number to minimise number of iterations
        nums = sorted([451, 331])
        
        # a + b + c and a * b * c are not possible (nothing changes)
        # (a + b) * c is not possibe as 331 is a prime number
        
        
        # check a + (b * c)
        
        # I: a + b.c = 331, b + a.c = 451
        #    a + b = 331 - 120 * b / (b - a)
        
        for a in range(2, nums[0] - 3):
          for b in range(2, int((nums[0] - a) / 2) + 1):
            if b == a: continue
            if a + b != 331 - (120 * b) / (b - a): continue
            
            c, r = divmod(nums[1] - b, a)
            if r or c < 2: continue
            
            # double check 
            if a + b * c == nums[0]:
              pr("answer", sorted([a, b, c]))
            
        # II: a + b.c = 331, c + a.b = 451
        #     a.b^2 - 451b + 331 - a = 0
        #     4a^2 - 1324a + 203401 must be square
        for a in range(2, nums[0] - 3):
          D = 4 * a**2 - 1324 * a + 203401
          D = is_square(D) 
          if D is None: continue 
          
          for b in [d for i in (-1, 1) if (d := div(451 + i * D, 2 * a))]:
            c = nums[1] - a * b
            
            # double check 
            if c > 1 and a + b * c == nums[0]:
              pr("answer", sorted([a, b, c]))
        

        Like

  • Unknown's avatar

    Jim Randell 8:38 am on 8 June 2023 Permalink | Reply
    Tags:   

    Teaser 2052: Back to back 

    From The Sunday Times, 13th January 2002 [link]

    Your Teaser today is to take the 10 digits 0 to 9. Use three of them to make a three-figure prime number. Then write that number down backwards (i,e. with the digits in reverse order). Then take three of the remaining digits, use them to form a larger prime number, and write that number down backwards. Finally, use the remaining four digits to form a four-figure perfect square and then write that number down backwards. You should do all this in such a way that the sum of the two reversed primes equals the reversed square.

    What are the two primes?

    [teaser2052]

     
    • Jim Randell's avatar

      Jim Randell 8:39 am on 8 June 2023 Permalink | Reply

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

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

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      #     C B A -> ABC is prime
      #  +  F E D -> DEF is prime
      #   -------
      #   J I H G -> GHIJ is square
      #   =======
      
      SubstitutedExpression
      
      "CBA + FED = JIHG"
      
      "is_prime(ABC)"
      "is_prime(DEF)"
      "A < D"
      "is_square(GHIJ)"
      
      --answer="(ABC, DEF)"
      

      Solution: The two primes are: 467 and 523.

      And the sum is:

      764 + 325 = 1089

      Like

    • Frits's avatar

      Frits 1:19 pm on 8 June 2023 Permalink | Reply

         
      from enigma import is_square_p
      from itertools import combinations
      
      # prime numbers between 100 and 1000 with different digits
      # without using digit 1
      P = [3, 5, 7]
      P += [x for x in range(11, 33, 2) if all(x % p for p in P)]
      P = [s for x in range(203, 1000, 2) if all(x % p for p in P) and 
           '1' not in (s := str(x)) and len(set(s)) == 3]
      
      # pick two primes 
      for p1, p2 in combinations(P, 2):
        # different digits
        if len(s := set(p1 + p2)) != 6: continue
        
        # sum of reversed primes should be a 4-digit number using different digits 
        sm = int(p1[::-1]) + int(p2[::-1])
        if sm < 1000 or s.difference(str(sm)) != s: continue
        # and a square
        if not is_square_p(sm): continue
        
        print(f"the two primes are {p1} and {p2}")
      

      Like

    • GeoffR's avatar

      GeoffR 7:46 am on 9 June 2023 Permalink | Reply

      
      from enigma import is_prime
      from math import isqrt
      
      def is_sq(x):
         return isqrt(x) ** 2 == x
      
      digits = set('1234567890')
      
      from itertools import permutations
      for p1 in permutations(digits, 3):
          A, B, C = p1
          if '0' in (A, C):continue
          # 1st prime
          ABC = A + B + C
          if not is_prime(int(ABC)):continue
          q1 = digits.difference([A, B, C])
          
          # find 2nd prime
          for p2 in permutations(q1, 3):
              D, E, F = p2
              if D < A: continue  # 2nd prime > 1st prime
              if '0' in (D, F):continue
              DEF = D + E + F
              if not is_prime(int(DEF)):continue
              q2 = q1.difference(p2)
              for p3 in permutations(q2):
                  G, H, I, J = p3
                  if '0' in (G, J):continue
                  GHIJ = G + H + I + J
                  rGHIJ = GHIJ[::-1]
                  
                  # check sum of two reversed primes equals the reversed square
                  if int(ABC[::-1]) + int(DEF[::-1]) == int(rGHIJ):
                      if is_sq(int(rGHIJ)):
                          print(f"Two primes are {ABC} and {DEF}.")
                                                  
      # Two primes are 467 and 523.
      
      

      Like

  • Unknown's avatar

    Jim Randell 8:01 am on 6 June 2023 Permalink | Reply
    Tags:   

    Brain-Teaser 973: Square-rigger 

    From The Sunday Times, 15th March 1981 [link]

    Young Mary, who is good at manipulating figures, was playing with her standard set of dominoes and seeing what numerical structures she could form with them, treating each half-domino as a digit according to its number of spots (“blank” being 0).

    Starting with double-6/double-5/double-4 laid end-to-end in a row, she built forwards and downwards from that beginning, placing dominoes across and apparently at  random, until she had completed a solid rectangle by slotting into the only remaining gaps, in its farther half, her last two dominoes which were 4-&-blank and 2-&-blank.

    Whereupon she called out to me: “Uncle, do come and look! I’ve managed to arrange all my dominoes in a rectangle so that the numbers formed by the four halves in each column are all dissimilar 4-digit squares”.

    “Are you quite sure about that?” I temporised.

    “Certain,” she replied. “And they’re pretty well in correct order of magnitude too!”.

    When I protested that this was quite impossible with dominoes, she said reproachfully: “But Uncle, I never said that ALL the squares appear in the right order, did I?  Actually there are just two of them — both among the seven smallest present — which do not; but every single square except those two is definitely just where it would be if all those appearing were strictly in order of magnitude”.

    She was perfectly correct. And you don’t need dominoes to figure out …

    Which four of Mary’s together formed columns 7 and 8 of her rectangle? (Use figures, e.g. 4-0 = four-&-blank).

    This was the final puzzle to use the title Brain-Teaser. The next puzzle was Brain teaser 974.

    [teaser973]

     
    • Jim Randell's avatar

      Jim Randell 8:04 am on 6 June 2023 Permalink | Reply

      A standard set of dominoes has 28 dominoes, each with 2 numbers on, so there are 56 numbers in total, consisting of 8 copies of each of the digits from 0 to 6.

      The program starts by constructing a list of square numbers that can be constructed using only the digits available on dominoes (i.e. the digits 0-6). It then constructs a viable sequence of squares that use the required 56 digits between them, and we consider swapping a pair of the numbers in the second half of the list to give Mary’s list of squares.

      We then turn the numbers into a 14×4 grid and use the [[ DominoGrid() ]] solver from the enigma.py library to find viable arrangements of dominoes.

      The program runs in 558ms. (Internal runtime is 412ms).

      Run: [ @replit ]

      from enigma import (
        DominoGrid, irange, subsets, multiset, flatten, unzip, union, group,
        update, seq_ordered as ordered, seq_get as get, join, printf
      )
      
      # available digits on dominoes
      digits = set("0123456")
      
      # find 4-digit squares that can be represented by dominoes
      sqs = list()
      for i in irange(32, 81):
        s = str(i * i)
        if not digits.issuperset(s): continue
        sqs.insert(0, s)
      
      # construct viable sequences of squares (in descending order)
      # - each of the digits 0-6 must be used exactly 8 times
      # - the sequence must start: 6xxx, 6xxx, 5xxx, 5xxx, 4xxx, 4xxx
      def squares(sqs, ds=None, ss=[]):
        # ds counts the digits remaining to be used
        if ds is None: ds = multiset.from_seq('0123456', count=8)
        # are we done?
        n = len(ss)
        if n == 14:
          yield ss
        elif not (n + len(sqs) < 14):
          # choose the next square to include
          for (i, sq) in enumerate(sqs):
            # 0, 1 must be 6xxx
            if n < 2:
              if sq[0] < '6': break
            # 2, 3 must be 5xxx
            elif n < 4:
              if sq[0] > '5': continue
              if sq[0] < '5': break
            # 4, 5 must be 4xxx
            elif n < 6:
              if sq[0] > '4': continue
              if sq[0] < '4': break
            # can we add sq to the sequence?
            if ds.issuperset(sq):
              # solve for the remaining squares in the list
              yield from squares(sqs[i + 1:], ds.difference(sq), ss + [sq])
      
      # domino ordering
      order = lambda xs: ordered(xs, reverse=1)
      
      # find dominoes used in specified columns (1-indexed)
      def dominoes(p, grid, cols):
        # indices of columns
        ks = union(irange(x - 1, 55, step=14) for x in cols)
        # find the dominoes at the specified indices
        g = group(ks, by=get(grid), f=get(p.grid))
        # extract dominoes that are entirely in selected columns
        for v in g.values():
          if len(v) == 2:
            yield order(v)
      
      # collect solutions
      rs = set()
      
      # consider possible sequences of squares
      for ss in squares(sqs):
        # choose two squares from index 7-13 to swap
        for (i, j) in subsets(irange(7, 13), size=2):
          ss_ = update(ss, [(i, ss[j]), (j, ss[i])])
          # construct the grid
          p = DominoGrid(14, 4, list(int(x) for x in flatten(unzip(ss_))))
          # and solve it
          for (grid, used) in p.solve(fixed=[(0, 1), (2, 3), (4, 5)]):
            # check that (4, 0) and (2, 0) occur in columns 8 - 14
            ds = set(dominoes(p, grid, irange(8, 14)))
            if not ((4, 0) in ds and (2, 0) in ds): continue
      
            # find the 4 dominoes in columns 7 and 8
            ds = order(dominoes(p, grid, [7, 8]))
            if len(ds) != 4: continue
            rs.add(ds)
      
            printf("squares = {ss_}", ss_=join(ss_, sep=" "))
            printf()
            p.output_solution((grid, used))
            printf("cols 7/8 = {ds}", ds=join(ds, sep=" "))
            printf("--")
      
      # output solution
      for ds in rs:
        printf("answer = {ds}", ds=join(ds, sep=" "))
      

      Solution: The dominoes making up columns 7 and 8 are: [6-0] [5-0] [3-3] [2-0].

      There is only one arrangement of square numbers that use each of the digits 0-6 exactly 8 times:

      6400, 6241, 5625, 5041, 4356, 4225, 3600, 3025, 3136, 3364, 2401, 2304, 1521, 1156

      And there are 2 (slightly) different ways the required grid can be constructed from a set of dominoes, here is one way:

      The [6-3] and [6-4] dominoes can be placed either horizontally or vertically to give the two layouts.

      If the indicated columns were swapped the squares would be in strict descending numerical order.

      The [2-0] and [4-0] dominoes (highlighted) were placed last in the right-hand half of the layout. If this condition is removed more arrangements are viable (16 in total), but the sequence of squares (and answer to the puzzle) remains the same.

      Like

  • Unknown's avatar

    Jim Randell 8:40 am on 4 June 2023 Permalink | Reply
    Tags:   

    Brain-Teaser 568: Batting averages 

    From The Sunday Times, 21st May 1972 [link]

    Allen and Biggin, stalwarts of our village cricket side, have an annual wager: whichever finishes the season with the lower batting average buys the other a dinner.

    Last season the result was in doubt until the last ball of the last match to which Allen, offering no stroke, was adjudged “out”, leg-before-wicket. Had he been given “not out” (which, incidentally, would have been the first “not out” innings either had played) his batting average — a whole number — would have beaten Biggin’s by exactly 0.5 of a run. In the event Biggin won by exactly 0.5 of a run.

    Both players comfortably passed a season’s total of 300 runs but neither reached 500. Biggin had three fewer innings than Allen.

    How many runs did Biggin score during the season?

    [Note for the non-cricketer: batting average is calculated by dividing a player’s total runs by his number of completed innings; i.e., times he was “out”].

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

    [teaser568]

     
    • Jim Randell's avatar

      Jim Randell 8:41 am on 4 June 2023 Permalink | Reply

      If A’s average is A/a and B’s average is B/b, then we have:

      B/b − 1/2 = A/a
      B/b + 1/2 = A/(a − 1) = an integer
      a = b + 3
      300 < A, B < 500

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

      Run: [ @replit ]

      from enigma import (irange, divisors_pairs, div, printf)
      
      # consider values for A's runs
      for A in irange(301, 499):
        # A / (a - 1) is an integer
        for (a1, k) in divisors_pairs(A, every=1):
          a = a1 + 1
          b = a - 3
          if b < 1: continue
      
          # calculate B's runs (B/b - 1/2 = A/a)
          B = div((2 * A + a) * b, 2 * a)
          if B is None or not (300 < B < 500): continue
          # check (B/b + 1/2 = A/(a - 1))
          if not (a1 * (2 * B + b) == 2 * A * b): continue
      
          # output solution
          printf("A={A} B={B} a={a} b={b}")
      

      Solution: Biggin scores 369 runs.

      A is 420 for 21, an average of 20.

      B is 369 for 18, an average of 20.5.

      Had A been out only 20 times, his average would have been 21.

      Like

    • Frits's avatar

      Frits 7:47 pm on 4 June 2023 Permalink | Reply

      Two iterations.

       
      from math import ceil
      
      # A = a(a-1)
      
      # A = a^2 - a > 300, (a - 1/2)^2 > 300.25, a - 1/2 > 17.328, a > 17.828
      # A = a^2 - a < 500, (a - 1/2)^2 < 500.25, a - 1/2 < 22.367, a < 22.867
      
      # make sure B is a whole number (a has to be odd)
      mn = (a := int(300.25**.5 + 0.5)) + (2 if a % 2 else 1)
      mx = ceil(500.25**.5 + 0.5)
      
      # loop over odd a's
      for a in range(mn, mx, 2):
        # B/b - 1/2 = A/a, B = (a - 1/2)b
        B = (a - 0.5) * (a - 3)
        if not (300 < B < 500): continue
        print(f"Biggin scored {int(B)} runs during the season")  
      

      Like

    • GeoffR's avatar

      GeoffR 8:36 pm on 4 June 2023 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 301..499:A; % Allen's total runs in the season
      var 301..499:B; % Biggin's total runs in the season
      
      % 26 weeks looks a reasonable average time for a cricket season (Apr - Sept)
      var 1..26: ai;  % Allen's total innings for the season
      var 1..26: bi;  % Biggin's total innings for the season
      
      % Allen's possible average scores are integers
      constraint A mod ai == 0  /\ A mod (ai - 1) == 0 ;
      
      % Biggin had three fewer innings than Allen
      constraint ai == bi + 3;
      
      % if Biggin wins by 1/2 point
      % B / bi - 1 / 2 = A / ai
      constraint 2 * (ai * B - bi * A) = ai * bi;
      
      % if Allen wins by 1/2 point
      % B / bi + 1 / 2 = A /(ai - 1)
      constraint 2 * (A * bi - B *(ai -  1)) == (ai - 1) * bi;
      
      solve satisfy;
      
      output ["[A, ai, B, bi] = " ++ show( [A, ai, B, bi] )];
      
      % [A, ai, B, bi] = [420, 21, 369, 18]
      % ----------
      % ==========
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 3:59 pm on 2 June 2023 Permalink | Reply
    Tags:   

    Teaser 3167: Binary primes 

    From The Sunday Times, 4th June 2023 [link] [link]

    Grace and Helen play a turn-based card game. Each player is given two cards with a 0 printed on them, and unlimited cards with a 1 printed on them. Before the game starts a 1 is placed on the table. Sitting on the same side of the table, a turn then involves placing a card to the left of the table cards, such that the value shown in binary remains prime or one (allowing leading zeros). The winner is the player who is last able to play a card, earning points equal to the value on the table at that time.

    Being expert logicians, they play the best possible cards to maximise their points or minimise their opponent’s points. Grace goes first.

    Who wins and with what cards on the table from left to right?

    [teaser3167]

     
    • Jim Randell's avatar

      Jim Randell 4:35 pm on 2 June 2023 Permalink | Reply

      This Python program plays the game with each player aiming to maximise their winnings (or minimise their losses) at each stage. So it performs a depth first traversal of the game tree.

      It runs in 56ms. (Internal runtime is 138µs).

      Run: [ @replit ]

      from enigma import (Accumulator, is_prime, int2base, compare, printf)
      
      # explore the outcome of this move
      def explore(n, k, a0, b0, rs):
        (rn, rk) = play(n, k, a0, b0)  # play the move
        rs.accumulate_data(-rn, rk)  # swap the result
      
      # play the game with current value <n> from <k> cards
      # player A to move, with <a0> zero cards
      # player B has <b0> zero cards
      # return (<pts>, <k>) [+ve for win, -ve for loss]
      def play(n, k, a0, b0):
        # choose the best move (maximum points)
        rs = Accumulator(fn=max)
        # play 0
        if a0 > 0: explore(n, k + 1, b0, a0 - 1, rs)
        # play 1
        n_ = n + (1 << k)
        if is_prime(n_): explore(n_, k + 1, b0, a0, rs)
        # make the best available move
        if rs.count: return (rs.value, rs.data)
        # if there are no moves, current points go to opponent
        return (-n, k)
      
      # play starting with value 1, on 1 card, and 2 zero cards for each player
      (n, k) = play(1, 1, 2, 2)
      # determine points won and the sequence of cards
      pts = abs(n)
      ss = int2base(pts, base=2, width=k)
      # output solution
      printf("{w} wins, {pts} pts, cards = {ss}", w=compare(n, 0, 'B?A'))
      

      Solution: Helen wins. The cards on the table are: (0 1 0 0 1 1 1 0 1).

      The game proceeds:

      start → (1) = 1
      G chooses 0 → (0 1) = 1
      H chooses 1 → (1 0 1) = 5
      G chooses 1 → (1 1 0 1) = 13
      H chooses 1 → (1 1 1 0 1) = 29
      G chooses 0 → (0 1 1 1 0 1) = 29
      H plays 0 → (0 0 1 1 1 0 1) = 29
      G plays 1 → (1 0 0 1 1 1 0 1) = 157
      H plays 0 → (0 1 0 0 1 1 1 0 1) = 157
      G cannot play; H wins 157 points

      The the final moves (0, 1, 0, out) are forced.

      There are 61 positions in the game tree, 17 of them are terminal positions, and only 2 of these are wins for the player who goes first.

      Like

      • Mark Valentine's avatar

        Mark Valentine 11:11 pm on 5 June 2023 Permalink | Reply

        What does run time vs zeros per person look like? How many zeroes can you reasonably solve for?

        Like

        • Jim Randell's avatar

          Jim Randell 10:43 am on 6 June 2023 Permalink | Reply

          Hi, Mark. Thanks for the puzzle!

          I ran my program for games with up to 28 zero cards per player. The number of positions grows at a reasonable rate, but things start to get a bit slow above z = 20.

          But we can switch to using the Miller-Rabin primality test [[ is_prime_mr() ]] for larger primes, which allows us to check up to z = 55 in under 1s (or [[ gmpy2.is_prime() ]] which is even faster).

           z    pos   winner       pts  runtime
          
           1     17    B            23
           2     61    B           157
           3    130    B            17
           4    237    B           769
           5    376    B          1223
           6    554    B          1223
           7    772    B         65543
           8   1036    B         65537
           9   1353    B         65537
          10   1727    B       2097169
          11   2141    B         65537
          12   2631    B         65537
          13   3158    B         65537
          14   3770    B         65537
          15   4455    B         65537
          16   5220    B       2097169  [101ms]
          17   6029    B         65537  [128ms]
          18   6909    B         65537  [243ms]
          19   7854    B         65537  [482ms]
          20   8870    B         65537  [886ms]
          21   9954    B         65537  [1.96s]
          22  11130    B         65537  [5.34s]
          23  12378    B     268435493  [10.7s]
          24  13736    B         65537  [23.6s]
          25  15160    B         65537  [38.6s]
          26  16663    B  274877906957  [81.6s]
          27  18234    B         65537  [ 161s]
          28  19904    B         65537  [1279s] [107ms with is_prime_mr]
          29  21668    B         65537          [127ms]
          30  23532    B         65537          [156ms]
          31  25463    B         65537          [181ms]
          32  27475    B         65537          [213ms]
          33  29559    B         65537          [225ms]
          34  31731    B         65537          [253ms]
          35  34001    B         65537          [265ms]
          36  36384    B         65537          [292ms]
          37  38847    B         65537          [305ms]
          38  41407    B         65537          [336ms]
          39  44048    B         65537          [346ms]
          

          z = 40 ends with a win for B with 302231454903657293676551 points.

          It doesn’t seem like going first is an advantage. In the z = 2 case only 2 of the 17 terminal positions are wins for A.

          Like

          • Mark Valentine's avatar

            Mark Valentine 3:37 pm on 6 June 2023 Permalink | Reply

            Impressive, it doesn’t blow up as much as I would have thought. I guess the primes becoming increasingly scarce helps.

            Like

    • Frits's avatar

      Frits 3:39 pm on 9 June 2023 Permalink | Reply

      @Jim, if you start with a list of prime numbers is there an upper limit for a prime number that you beforehand can determine?

      Like

      • Jim Randell's avatar

        Jim Randell 5:41 pm on 9 June 2023 Permalink | Reply

        @Frits: Do you mean can we determine what the largest possible value on the table can be without playing the game?

        Each position in the game must be a left-truncatable prime in binary (treating 1 as prime), and as there are a limited number of zeros, it is reasonable to suppose there are only a limited number of such primes. (See: Enigma 1075 for more on truncatable primes).

        With up to 4 zeros there are 28 left-truncatable binary primes, and the largest is:

        01100111101 = 829 [base 10]

        (Although determining this is pretty much the same as playing the game anyway).

        And 829 does indeed show up as the largest possible score for player B in the game tree.

        Like

    • Frits's avatar

      Frits 10:09 am on 11 June 2023 Permalink | Reply

      @Jim, thanks.

      On PuzzlingInPython (see below) I published a program where I start with a list of all prime numbers up to a certain limit where you keep pruning this list until you have all 17 games.

      I hoped to find by logic a limit on the number of consecutive 1’s but in some cases none of the new primes end on a 5 anymore (fi if the last used power of 2 ends on an 8 and your last prime ends on a 1 then your next primes will end on (7, 9, 3, 1, 7, 9, 3, 1, 7, ….) ).

      It was relative easy to generate the 17 games by recursion but picking the winner from this list I found difficult to program.

      Do you also plan to add some kind of binary tree implementation to enigma.py? I guess not that many puzzles you have published can be solved from a binary tree.

      [ https://brg.me.uk/?p=8290#comment-3820 ]

      Like

      • Jim Randell's avatar

        Jim Randell 3:33 pm on 12 June 2023 Permalink | Reply

        @Frits: In these game puzzles I usually find it is easiest to write a recursive function to do a depth first traversal of the game tree. From the current position you can examine all possible moves, and then choose the “best” one for the player, and this means we can determine what the outcome of a game is from the result of the initial position (presuming the players are aiming to maximise their metric at each position). (And in some games we don’t even need to explore the entire tree).

        I’ve done a couple of recent Tantalizer puzzles using this approach (see: Tantalizer 4, Tantalizer 7a), but there are other puzzles where the same approach works.

        This particular puzzle is relatively simple, in that there are at most two plays from any position (playing “0” or “1”), but in other games there may be many more plays available, so the game tree is not always binary.

        I didn’t really think about constructing the graph by starting from the all potential endpoints and then removing those that are not reachable. It seems that this might not be tractable on more complex games as the number of potential positions could be very large, and only a sparse subset of them would be reachable. I think it would be more efficient to build the tree going forward from the starting position.

        Like

  • Unknown's avatar

    Jim Randell 9:00 am on 1 June 2023 Permalink | Reply
    Tags:   

    Teaser 2108: Touch of magic 

    From The Sunday Times, 9th February 2003 [link]

    Place a single digit into each of the nine squares, such that:

    • There is no repeat in any row and no repeat in any column.
    • Each row, read in either direction, is a three-figure prime.
    • Each column, read up or down, is a three-figure prime.

    What is the sum of your nine digits?

    [teaser2108]

     
    • Jim Randell's avatar

      Jim Randell 9:01 am on 1 June 2023 Permalink | Reply

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

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

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      #  A B C
      #  D E F
      #  G H I
      
      # no repeats in rows/columns
      --distinct="ABC,DEF,GHI,ADG,BEH,CFI"
      
      # rows are 3-digit primes (in either direction)
      "is_prime(ABC)" "is_prime(CBA)"
      "is_prime(DEF)" "is_prime(FED)"
      "is_prime(GHI)" "is_prime(IHG)"
      
      # columns are 3-digit primes (in either direction)
      "is_prime(ADG)" "is_prime(GDA)"
      "is_prime(BEH)" "is_prime(HEB)"
      "is_prime(CFI)" "is_prime(IFC)"
      
      # answer is the sum of the digits
      --answer="A + B + C + D + E + F + G + H + I"
      
      --template="(ABC DEF GHI)"
      --solution=""
      

      Solution: The sum of the digits is 50.

      One arrangement is:

      We also get a solution if we reverse the rows (left to right), or reverse the order of the rows (top to bottom), or both.

      Like

    • Frits's avatar

      Frits 5:19 pm on 2 June 2023 Permalink | Reply

        
      from itertools import permutations
      
      # 143 prime numbers between 100 and 1000
      P = [3, 5, 7]
      P += [x for x in range(11, 33, 2) if all(x % p for p in P)]
      P = [str(x) for x in range(101, 1000, 2) if all(x % p for p in P)]
      
      # a list of all valid prime numbers
      p_both = [p for p in P if len(set(p)) == 3 and p[::-1] in P]
      # a list of all valid prime numbers without it's reverse
      p_single = [p for p in p_both if p[0] < p[2]]
      
      
      #       2 ends  (also for middle layers)
      #      /     \
      #   +---+---+---+
      #   |   |   |   |
      #   +---+---+---+
      #   |   |   |   | <-- edge
      #   +---+---+---+
      #   |   |   |   |
      #   +---+---+---+
      #      \  |  /
      #     1 side
      
      ends = set(y for x in p_single for y in (x[0], x[2]))
      edges = set(x[1] for x in p_single if x[1] in ends)
      middle_layers = [x[::k] for x in p_single if set([x[0], x[2]]) <= edges 
                       for k in (-1, 1)]
      
      # a side of 3 cells must have an odd edge and it's edge must be an end
      sides = [x[::k] for x in p_single if x[1] in "13579" and x[1] in ends 
               for k in (-1, 1)]
      
      # pick 2 different sides for top and bottom horizontal layer
      for p in permutations(sides, 2):
        s1, s2 = p
        # vertically digits may not match
        if any(s1[i] == s2[i] for i in range(3)): continue
        # pick a horizontal middel layer
        for m in middle_layers:
          # check column for prime numbers 
          if any(s1[i] + m[i] + s2[i] not in p_both for i in range(3)): continue
          sm = sum(int(s1[i]) + int(m[i]) + int(s2[i]) for i in range(3))
          print(f"{s1}\n{m}  with sum {sm}\n{s2}\n ") 
      

      Like

    • GeoffR's avatar

      GeoffR 8:12 pm on 2 June 2023 Permalink | Reply

      # reusing first part of Frits' code
      P = [3, 5, 7]
      P += [x for x in range(11, 33, 2) if all(x % p for p in P)]
      P = [str(x) for x in range(101, 1000, 2) if all(x % p for p in P)]
      
      # a list of all valid reversed prime numbers - only 22 no.
      p_both = [str(p) for p in P if len(set(p)) == 3 and p[::-1] in P]
      
      # grid
      # a b c = prime q1 
      # d e f = prime q2 
      # g h i = prime q3 
      
      from enigma import all_different
      from itertools import permutations
      
      for p1 in permutations(p_both, 3):
          q1, q2, q3 = p1
          # find digits in L.H. column
          a, d, g =  q1[0],  q2[0],  q3[0]
          adg, gda = a + d + g, g + d + a
          if adg in p_both and gda in p_both:
              
             # find digits in middle column
             b, e, h =  q1[1], q2[1], q3[1]
             beh, heb = b + e + h, h + e + b
             if beh in p_both and heb in p_both:
                 
                 # find digits in R.H. column
                 c, f, i = q1[2], q2[2], q3[2],
                 cfi, ifc = c + f + i, i + f + c
                 if cfi in p_both and ifc in p_both:
                     # check all rows and columns are different
                     if all_different(q1, q2, q3, adg, beh, cfi):
                         print(q1); print(q2); print(q3)
                         # find total of all digits in the grid
                         total = sum(int(i) for i in (a,b,c,d,e,f,g,h,i))
                         print('Total of all digits = ', total)
                         print()
      
      # 937
      # 743
      # 179
      # Total of all digits =  50
      
      
      

      Like

      • Frits's avatar

        Frits 1:39 pm on 3 June 2023 Permalink | Reply

        or

           
        from itertools import permutations
        
        # 143 prime numbers between 100 and 1000
        P = [3, 5, 7]
        P += [x for x in range(11, 33, 2) if all(x % p for p in P)]
        P = [str(x) for x in range(101, 1000, 2) if all(x % p for p in P)]
         
        # a list of all valid prime numbers
        p_both = [p for p in P if len(set(p)) == 3 and p[::-1] in P]
         
        for p in permutations(p_both, 3):
          # transpose the permutations to get the columns
          if any(''.join(col) not in p_both for col in zip(*p)): continue
        
          print('\n'.join(p))
          print("sum = ", sum(int(y) for x in p for y in x), "\n")  
        

        Like

    • GeoffR's avatar

      GeoffR 2:56 pm on 3 June 2023 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % a b c
      % d e f 
      % g h i 
      
      % Reversible primes can only start or end  with 1,3,7 ot 9.
      set of int: pr = {1,3,7,9}; 
      
      var pr:a; var pr:b; var pr:c; 
      var pr:d; var 0..9:e; var pr:f;
      var pr:g; var pr:h; var pr:i; 
      
      % Reversible primes, as  found in the Python solution
      set of int: primes = {107, 149, 157, 167, 179, 347,
      359, 389, 701, 709, 739, 743, 751, 761, 769, 907,
      937, 941, 953, 967, 971, 983};
      
      % Reversible prime rows and columns
      constraint (100*a + 10*b + c) in primes;
      constraint (100*c + 10*b + a) in primes;
      
      constraint (100*d + 10*e + f) in primes;
      constraint (100*f + 10*e + d) in primes;
      
      constraint (100*g + 10*h + i) in primes;
      constraint (100*i + 10*h + g) in primes;
      
      constraint (100*a + 10*d + g) in primes;
      constraint (100*g + 10*d + a) in primes;
      
      constraint (100*b + 10*e + h) in primes;
      constraint (100*h + 10*e + b) in primes;
      
      constraint (100*c + 10*f + i) in primes;
      constraint (100*i + 10*f + c) in primes;
      
      % all rows and columns are different
      constraint all_different([ (100*a + 10*b + c) ,
      (100*d + 10*e + f), (100*g + 10*h + i), (100*a + 10*d + g),
      (100*b + 10*e + h), (100*c + 10*f + i)]);
      
      solve satisfy;
      
      output[ show(a), show(b),show(c) ++
      "\n" ++ show(d),show(e),show(f) ++
      "\n" ++ show(g),show(h),show(i) ++
      "\nDigit total = " ++ show(a+b+c+d+e+f+g+h+i)];
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 7:40 am on 30 May 2023 Permalink | Reply
    Tags:   

    Teaser 2100: Uncle Hex 

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

    The standard hexadecimal notation used in some computations needs 16 “hex-digits”, so it uses 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E and F — e.g. the hex-number DEC15 represents the decimal number: 13×16⁴ + 14×16³ + 12×16² + 1×16 + 5 = 912405.

    Of course, only a few dates (like today’s) can look like a hex-number in that way (with some dates having a choice of hex-number, like DEC08/DEC8). My Uncle Hex and I have noticed we both have birthdays that look like hex-numbers. We have each worked out a decimal number that our birthday can represent and, comparing notes, we see that between them those two decimal numbers use each of the digits 0 to 9 at least once. Uncle Hex’s next birthday comes before mine.

    When is Uncle Hex’s birthday?

    Teaser 21002105 were originally published in The Sunday Times with the numbers 30003005.

    [teaser2100]

     
    • Jim Randell's avatar

      Jim Randell 7:41 am on 30 May 2023 Permalink | Reply

      This Python program generates all the dates in a leap year, and finds those that give viable “hex-dates” (obviously it would be more efficient to just consider months that consist entirely of hex digits).

      We then look for a pair of hex-dates that have values that between them use all 10 digits when represented in decimal form.

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

      Run: [ @replit ]

      from datetime import (date, timedelta)
      from enigma import (repeat, inc, sprintf, base2int, catch, subsets, union, int2base, printf)
      
      # generate possible "hex-dates"
      def generate():
        # month names
        months = "? JAN FEB MAR APR MAY JUN JUL AUG SEP OCT NOV DEC".split()
        # consider dates in 2000 (a leap year)
        for d in repeat(inc(timedelta(days=1)), date(2000, 1, 1)):
          if d.year > 2000: break
          (m, d) = (months[d.month], d.day)
          for fmt in ["{m}{d}", "{m}{d:02d}"]:
            s = sprintf(fmt)
            v = catch(base2int, s, base=16)
            if v is not None:
              yield (s, v)
      
      # collect "hex-dates"
      d = dict(generate())
      
      # find pairs that use 10 different digits when expressed in decimal
      for ((k1, v1), (k2, v2)) in subsets(d.items(), size=2):
        ds = union(int2base(v, base=10) for v in (v1, v2))
        if len(ds) != 10: continue
        # output solution
        printf("{k1} -> {v1}; {k2} -> {v2}")
      

      Solution: Uncle Hex’s birthday is 4th February.

      The two dates are:

      FEB4 [base 16] = 65204 [base 10]
      DEC03 [base 16] = 912387 [base 10]

      The puzzle was set on 15th December, so the next of these dates to occur is 4th February.

      Like

      • Frits's avatar

        Frits 6:54 pm on 30 May 2023 Permalink | Reply

        @Jim, I don’t see the requirement that each “hex-date” has to use distinct digits.

        Like

        • Jim Randell's avatar

          Jim Randell 7:13 pm on 30 May 2023 Permalink | Reply

          I don’t know where that came from. The [[ is_duplicate() ]] test can be removed, and you still get the same answer.

          Like

      • Frits's avatar

        Frits 8:39 pm on 30 May 2023 Permalink | Reply

        Slow but more than three times faster with PyPy.

         
        from enigma import SubstitutedExpression, int2base
        
        months = "JAN FEB MAR APR MAY JUN JUL AUG SEP OCT NOV DEC"
        days = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
        
        # check for valid "hex-date"
        def check(i):
          s = int2base(i, base=16)
          if not (3 < len(s) < 6): return 0
          f = months.find(s[:3])
          if f < 0: return 0
          
          d = s[3:]
          if not d.isnumeric(): return 0
          d = int(d)
          
          f //= 4            # so we have indices 0-11
          if not (0 < d <= days[f]): return 0
          
          return 100 * f + d
          
          
        # the alphametic puzzle
        p = SubstitutedExpression(
          [
            # uncle HEX: UVWXYZ     me: SOMERF
            
            "UVWXYZ > 43680", # start from AAA1
            
            "check(UVWXYZ)",
            "len(set([U, V, W, X, Y, Z])) >= 4",
            
            "SOMERF > 43681", # start from AAA2
            
            # those numbers use each of the digits 0 to 9 at least once
            "len(set([U, V, W, X, Y, Z, S, O, M, E, R, F])) == 10",
            
            # my number
            "check(SOMERF)",
            
            # uncle Hex's next birthday comes before mine
            "0 < check(UVWXYZ) < check(SOMERF)",
          ],
          answer="int2base(UVWXYZ, base=16)",
          d2i="",
          distinct="",
          env=dict(check=check),
          #reorder=0,
          verbose=0,    # use 256 to see the generated code
        )
        
        # print answers
        for (_, ans) in p.solve():
          print(f"Uncle Hex's birthday: {ans}")  
        

        Like

  • Unknown's avatar

    Jim Randell 4:29 pm on 26 May 2023 Permalink | Reply
    Tags: ,   

    Teaser 3166: All their marbles 

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

    In their art class, Jack and Jill each had a box of spherical glass marbles. Each box contained marbles of at least three different sizes, and the radius of every marble was a whole number of cm.

    Jack placed three marbles of equal size from his box onto a desk, and placed each of the other [sizes] in turn on top so that all four marbles touched each other and formed a triangular pyramid. He worked out the height of each pyramid (from desk to top of top marble) and obtained a different whole number of cm each time.

    Jill was also able to do this with her marbles but they were all of different sizes to Jack’s.

    None of the pyramids was higher than 30cm.

    List all of the different marble radii in ascending order.

    [teaser3166]

     
    • Jim Randell's avatar

      Jim Randell 5:53 pm on 26 May 2023 Permalink | Reply

      Presumably “at least three” is “exactly three”, otherwise there would be multiple solutions.

      But I think this puzzle is flawed. We don’t find 2 possible sets of marbles that satisfy the specified conditions of the puzzle. Although by increasing the maximum allowable pyramid height we can find a solution to the puzzle as worded. But these involve quite sizeable marbles (using mm instead of cm would make the puzzle more reasonable).

      By calculating the height h of the the (not regular) tetrahedron formed by the centres of the spheres we can determine the height of a pyramidal configuration of spheres, and reject non-viable configurations. And we can then look for disjoint sets of three spheres (a base size and two viable top sizes) for Jack and Jill that give valid configurations.

      Run: [ @replit ]

      from enigma import (
        irange, subsets, sq, is_square, group, item, delete,
        cproduct, disjoint_union, arg, printf
      )
      
      MAX_H = arg(30, 0, int)  # max pyramid height
      MAX_R = (MAX_H - 1) // 2  # max sphere radius
      
      # calculate integer height of a pyramid configuration
      # with base spheres radius <R> and top sphere radius <r>
      def height(R, r):
        if R % 3 != 0: return
        # vertical height between centres of spheres = h
        h = is_square(sq(r) + 2 * R * r - sq(R) // 3)
        if h is None: return
        H = h + R + r
        # check it is a valid pyramid
        if not (H > 2 * R): return
        return H
      
      # generate possible base/top radii
      def generate():
        # consider possible radii
        for (R, r) in subsets(irange(1, MAX_R), size=2, select="P"):
          # calculate height of the pyramid = H
          H = height(R, r)
          # check it forms a pyramid with H not exceeding MAX_H
          if H is None or H > MAX_H: continue
          printf("[R={R} r={r} -> H={H}]")
          yield (R, r)
      
      # group top radii by base radius
      g = group(generate(), by=item(0), f=item(1))
      # discard sets with fewer than 3 different sizes
      g = delete(g, (k for (k, vs) in g.items() if len(vs) < 2))
      
      # look for 2 disjoint sets of 3 radii
      for ((k1, vs1), (k2, vs2)) in subsets(g.items(), size=2):
        for (ts1, ts2) in cproduct(subsets(vs, size=2) for vs in (vs1, vs2)):
          ss = disjoint_union([ts1, ts2, [k1, k2]])
          if ss is None: continue
          # output solution
          printf("radii = {ss} [base = {k1} + tops = {ts1}; base = {k2} + tops = {ts2}]", ss=sorted(ss))
      

      My interpretation of the puzzle text is that in order for the marbles to form a structure that could be described as a triangular pyramid, the uppermost point of the top marble in the arrangement must project above the uppermost points of the three marbles forming the base. So that three planar triangles, each supported by two of the base marbles and the top marble, would form the inclined faces of a triangular based pyramid that exactly encloses the marbles.

      However, with this interpretation, there is no solution to the puzzle with the restrictions given.

      If we increase the maximum allowed height of the arrangements (to between 72 and 95), we can find a unique solution using valid pyramids:

      set 1 = (7, 12, 14) [base = 12, top = 7 → height = 32; base = 12, top = 14 → height 48]
      set 2 = (13, 18, 21) [base = 18, top = 13 → height 54; base = 18, top = 21 → height 72]

      And this gives an answer of: (7, 12, 13, 14, 18, 21).

      The marbles are quite large though, so perhaps this would work better if the radii were specified in millimetres instead of centimetres.


      Another way to find a solution is to abandon the requirement for a “triangular pyramid” arrangement, and just place the three base marbles on the desk, touching each other in a triangular arrangement, and then place the fourth marble on top of these. And we measure the elevation of the uppermost point of the top marble above the desk. (We don’t care if this is below the level of the uppermost points of the base marbles, or at the same level).

      And using such arrangements we can get a unique solution within the height restriction given in the puzzle text:

      set 1 = (1, 6, 7) [base = 6, top = 1 → height 8; base = 6, top = 7 → height 24]
      set 2 = (2, 4, 12) [base = 12, top =2 → height 16; base = 12, top 4 → height 24]

      Which gives an answer of: (1, 2, 4, 6, 7, 12).

      And it seems likely this is the intended solution.


      The published solution is: “1, 2, 4, 6, 7 and 12 cm”.

      Like

      • Frits's avatar

        Frits 9:52 pm on 26 May 2023 Permalink | Reply

        @Jim, using r = R in your height formula I don’t recognize the published height of a tetrahedron with 2 layers (2r(1 + sqrt(2/3)).

        No idea yet how to find the formula myself.

        Like

        • Jim Randell's avatar

          Jim Randell 10:01 pm on 26 May 2023 Permalink | Reply

          That is exactly what you get from my formula when R = r:

          H = 2r + √(r² +2r² − r²/3)
          H = 2r + √(8r²/3)
          H = 2r + 2r√(2/3)
          H = 2r(1 + √(2/3))

          The formula itself comes from a bit of trigonometry on a triangle whose hypotenuse connects the centres of the top sphere and one of the base spheres.

          Like

          • Frits's avatar

            Frits 10:38 pm on 26 May 2023 Permalink | Reply

            OK, I thought “h” was the height of the pyramid.

            Like

          • Frits's avatar

            Frits 11:01 pm on 26 May 2023 Permalink | Reply

            I verified your formula (using the formula for the distance between the centre of an equilateral triangle and any of its vertices)

            Like

      • Jim Randell's avatar

        Jim Randell 10:59 pm on 27 May 2023 Permalink | Reply

        If we ignore all the stuff about making “pyramids”, and just arrange 3 marbles of the same size in a triangular arrangement on the desk, with each marble touching the other two, and then place a different size fourth marble on top of these three marbles in the hollow between the lower three marbles. We can then measure the distance between the surface of the desk and the top of the fourth marble. And it is this distance we require to be an integer.

        With this wording the puzzle does have a unique solution, with distances not exceeding 30cm, and it is quite possible these are the sets the setter was intending us to find.

        My program (above) can be adapted for this scenario by removing the validity check at line 18.

        I’ve also uploaded a more generic program that allows you to experiment with various criteria for valid configurations. [@replit]

        Like

  • Unknown's avatar

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

    Teaser 2183: The punishment fits the crime 

    From The Sunday Times, 18th July 2004 [link]

    Recently I was teaching the class about Pascal’s triangle, which starts:

    1
    1  1
    1  2  1
    1  3  3  1
    1  4  6  4  1

    Subsequent rows have a 1 at each end of each row, with any other number in the row obtained by adding the two numbers diagonally above it. Then a row gives, for example:

    (1 + x)⁴  = 1 + 4x + 6x² + 4x³ + x

    Six pupils disrupted the lesson, and so I kept them in after school. I gave each of them a different prime number and told them to work out its 10th power without a calculator.

    “That’s too easy”, said Blaise, whose prime was 3. “I’ll work out the product of everyone else’s answers instead”. Then she read out the 41-digit answer and left!

    What was her 41-digit answer?

    [teaser2183]

     
    • Jim Randell's avatar

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

      In order for the 10th power to be a 41 digit number the product of the 5 primes must be in the range:

      min = ceil(10^(40/10)) = ceil(10^4) = 10000
      max = floor(10^(41/10)) = floor(10^4.1) = 12589

      Excluding 3, the five smallest primes are (2, 5, 7, 11, 13) which have a product of 10010, which is in the range we require.

      And:

      10010^10 = 10100451202102522101200450100010000000000

      We can calculate this number using Pascal’s Triangle as follows:

      10010^10 = (10(1000 + 1))^10
      = (10^10)(1000 + 1)^10

      And row 10 (numbering from 0) of Pascal’s triangle is:

      10: (1  10  45  120  210  252  210  120  45  10  1)

      So we can calculate (1000 + 1)^10, using the polynomial derived from this row with x = 1000).

      The terms are separated by 1000, and each value in the row is 3 digits or less, so we can just write the result out by padding the values in the row to 3 digits:

      001 010 045 120 210 252 210 120 045 010 001

      Multiplying this by 10^10 just involves adding 10 zeros to the end, to give the 41 digit number:

      10100451202102522101200450100010000000000


      Or using Python.

      The following Python program runs in 57ms. (Internal runtime is 228µs).

      Run: [ @replit ]

      from enigma import (intc, intf, fdiv, primes, inf, subsets, diff, multiply, ndigits, printf)
      
      def solve(n, k):
        # min and max products for an n digit number
        m = intc(pow(10, fdiv(n - 1, k)))
        M = intf(pow(10, fdiv(n, k)))
        printf("[n={n} -> [{m}, {M}]]")
      
        # consider the largest prime
        for p in primes.irange(2, inf):
          if p == 3: continue
          # choose 4 smaller primes (excluding 3)
          f = 0
          for ps in subsets(diff(primes.between(2, p - 1), [3]), size=4, fn=list):
            ps.append(p)
            x = multiply(ps)
            if x > M:
              if f == 0: return
              break
            if not (x < m or x > M):
              x10 = pow(x, 10)
              printf("{ps} -> {x} -> {x10} [{d} digits]", d=ndigits(x10))
            f = 1
      
      # solve for 41 digit numbers
      solve(41, 10)
      

      Like

    • GeoffR's avatar

      GeoffR 4:45 pm on 26 May 2023 Permalink | Reply

      primes = (2, 5, 7, 11, 13, 17, 19)  # prime 3 excluded from description
      
      # The highest product of primes to power of 10 in the tuple below
      # .. i.e. (7,11,13,17,19) gives a 56 digit number
      # .. so a more than an adequate range to find a 41 digit product.
      
      from itertools import combinations
      
      for P1 in combinations(primes, 5):
          # choose 5 primes from a tuple of 7 primes
          p1, p2, p3, p4, p5 = P1
      
          num = p1**10 * p2**10 * p3**10 * p4**10 * p5**10
          if len(str(num)) == 41:
             print(f"41 digit number is {num}")
             exit()  # only one answer needed
      
      # 41 digit number is 10100451202102522101200450100010000000000
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 8:30 am on 23 May 2023 Permalink | Reply
    Tags: by: Ahmet Cetinbudaklar   

    Teaser 2182: Team bonding 

    From The Sunday Times, 11th July 2004 [link]

    The 21 members of the football club’s squad (who wear shirts numbered from 1 to 21) were asked to turn up for training. But some missed the session because of injuries. The club trainer asked the players present to stand in a circle so that, for any adjacent pair of players, one of their numbers was a multiple of the other. The trainer, a keen puzzler, took this opportunity because he realised that this was the largest number of players from the squad for whom the exercise could work.

    After a little effort, the players arranged themselves as requested. One player noticed that the sum of his two neighbours’ numbers equalled the lowest of the injured players numbers, and (a little further around the circle in a clockwise direction) another player noticed the sum of his two neighbours’ numbers equalled the highest of the injured players’ numbers. In no case did a player’s two neighbours add up to 20.

    Starting at 1, list the order of the players clockwise around the circle.

    [teaser2182]

     
    • Jim Randell's avatar

      Jim Randell 8:30 am on 23 May 2023 Permalink | Reply

      This Python program generates possible maximal length chains where in each pair of adjacent numbers, one is a multiple of the other. We start the chain with 1, so we know it can form a circle.

      We then look for chains that satisfy the remaining conditions.

      It runs in 220ms. (Internal runtime is 120ms).

      Run: [ @replit ]

      from enigma import (Accumulator, irange, diff, tuples, printf)
      
      ordered = lambda x, y: (x, y) if x < y else (y, x)
      
      # generate possible chains, such that for each pair of adjacent
      # numbers one is a multiple of the other
      def generate(ss, rs):
        yield ss
        for n in rs:
          (a, b) = ordered(ss[-1], n)
          if b % a == 0:
            yield from generate(ss + [n], rs.difference([n]))
      
      # start with 1 and solve for the remaining numbers
      r = Accumulator(fn=max, collect=1)
      for ss in generate([1], set(irange(2, 21))):
        r.accumulate_data(len(ss), ss)
      
      # find position whose neighbours satisfy fns
      def find(ss, fns):
        n = len(ss)
        d = dict(enumerate(fns))
        r = [None] * len(fns)
        for (i, (x, y, z)) in enumerate(tuples(ss, 3, circular=1)):
          for (k, fn) in list(d.items()):
            if fn(x, z):
              r[k] = (i + 1) % n
              del d[k]
          if not d: break
        return r
      
      # consider maximal arrangements
      for ss in r.data:
        # find the missing numbers
        xs = diff(irange(1, 20), ss)
        # look for positions where the neighbours are:
        # i = equal to the smallest missing number
        # j = equal to the largest missing number
        # k = equal to 20
        fn = lambda z: (lambda x, y, z=z: x + y == z)
        (i, j, k) = find(ss, [fn(xs[0]), fn(xs[-1]), fn(20)])
        if i is None or j is None or k is not None: continue
        # calculate clockwise distance: i -> j
        n = len(ss)
        d = (j - i) % n
        if 2 * d > n: continue
        # output solution
        printf("{ss} (i={i} j={j})")
      

      Solution: 1, 9, 18, 6, 12, 4, 16, 8, 2, 14, 7, 21, 3, 15, 5, 10, 20.

      The missing numbers are: 11, 13, 17, 19.

      And Player 20 has neighbours that sum to 11 (= 10 + 1). Player 9 has neighbours that sum 19 (= 1 + 18). No-one has neighbours that sum to 20.

      Like

  • Unknown's avatar

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

    Brain-Teaser 386: South Pacific 

    From The Sunday Times, 29th September 1968 [link]

    Among those innumerable South Pacific islands in which the vicinity of longitude 180° abounds, there are three neighbouring ones between which an ancient ferryboat maintains each week a regular schedule. This schedule, which is strictly adhered to except when ordered otherwise, is:

    ALOHA: dep. Monday 9 a.m.
    BALI-HAI: arr. Tuesday 7.p.m.
    BALI-HAI: dep. Tuesday 10 p.m.
    CRACKATOEA: arr. Friday 9 p.m.
    CRACKATOEA: dep. Saturday 7 a.m.
    ALOHA: arr. Sunday 7 p.m.

    The ferry maintains the same leisurely speed throughout each leg of the triangular circuit.

    To Port Authority at the home port of Aloha, one Thursday at 9 p.m, radioed to the ferry on its course between the other two islands that a hurricane in the area was imminent, and ordered it to proceed at once to the nearest of the three for shelter.

    Without altering speed, the captain immediately complied.

    Which island did he accordingly reach, and what were the day and hour of his arrival there?

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

    [teaser386]

     
    • Jim Randell's avatar

      Jim Randell 9:23 am on 21 May 2023 Permalink | Reply

      The boat travels at a steady speed, so we can equate journey times with distances, and I think we are to assume it travels directly between the islands in straight line distances.

      So the first problem is that the apparent distances between islands (34h, 71h, 36h) do not form a triangle.

      But as we are “in the vicinity of longitude 180°”, it could be the case that the islands straddle the International Date Line, and so some of them could have local times that are 24 hours ahead of the others, and the times mentioned are local to the corresponding islands.

      (I suppose potentially there could be more than 2 timezones involved, and the timezones do not necessarily differ by 24 hours, but I think that would not lead to a unique solution. And I also suppose that the puzzle doesn’t mention that all times are local times so that it doesn’t give away any clues to the solution).

      This Python program considers possible collections of the 3 islands that are 24 hours ahead of the remaining islands, and looks to see if the actual elapsed journey times can form a triangle. If so, we check that a call made at 93 hours after midnight on Monday (local to A), would be received by the boat while it is on the B→C journey, and if so calculates which of the islands it is closest to, and the time it would arrive.

      Run: [ @replit ]

      from enigma import (empty, call, subsets, fdiv, sq, sqrt, divf, sprintf, seq2str, map2str, printf)
      
      # check the side lengths form a triangle
      def is_triangle(a, b, c):
        return all([0 < a < b + c, 0 < b < a + c, 0 < c < a + b])
      
      # adjust a time = what time is it in <x> when in <y> it is <t>?
      def adjust(x, y, t, ahead):
        if x not in ahead and y in ahead: return t - 24
        if x in ahead and y not in ahead: return t + 24
        return t
      
      # local time, Mon 12am + <h> hours
      days = "Mon Tue Wed Thu Fri Sat Sun".split()
      def time(h):
        d = divf(h, 24)
        h -= d * 24
        return sprintf("{d} {h:.4g}h", d=days[d % 7])
      
      # calculate time direct to A from BC leg, given time out from B
      def timeA(elapsed, tB):
        (AB, BC, CA) = (elapsed[k] for k in ('AB', 'BC', 'CA'))
        # cosine rule
        return sqrt(sq(tB) + sq(AB) - tB * fdiv(sq(AB) + sq(BC) - sq(CA), BC))
      
      # solve the puzzle where specified ports are +24 hours ahead of the others
      def solve(times, ahead=empty):
        # calculate the actual elapsed times
        elapsed = dict()
        for (k, t) in times.items():
          (x, y) = k
          elapsed[k] = adjust(x, y, t, ahead)
        # check the elapsed times form a triangle
        if not call(is_triangle, elapsed.values()): return
      
        # the call is made at 93h/A
        # at which time the boat is on the BC leg (46h/B -> 117h/C)
        depB = adjust('A', 'B', 46, ahead)
        arrC = adjust('A', 'C', 117, ahead)
        (tB, tC) = (93 - depB, arrC - 93)
        if not (tB > 0 and tC > 0): return
        # calculate direct route to A
        tA = timeA(elapsed, tC)
        # make the shortest journey
        printf("[ahead = {ahead}, elapsed = {elapsed}]", ahead=seq2str(ahead), elapsed=map2str(elapsed))
        t = min(tA, tB, tC)
        ans = lambda x, t=t: ('= NEAREST' if x == t else '')
        # divert to A
        arr = 93 + tA
        printf("-> A = {tA:.4g}h, arrive {arr} (local) {x}", arr=time(arr), x=ans(tA))
        # return to B
        arr = adjust('B', 'A', 93, ahead) + tB
        printf("-> B = {tB:.4g}h, arrive {arr} (local) {x}", arr=time(arr), x=ans(tB))
        # continue to C as planned
        printf("-> C = {tC:.4g}h, arrive {arr} (local) {x}", arr=time(117), x=ans(tC))
        printf()
      
      # the apparent journey times (from the schedule)
      times = dict(AB=34, BC=71, CA=36)
      
      # consider possible islands with local time 24h ahead
      for ahead in subsets('ABC', min_size=0, max_size=2):
        solve(times, ahead)
      

      Solution: The boat reached Bali-Hai on Thursday, 8pm (local time).


      A and C are 24h ahead of B.

      So the corresponding elapsed journey times are: A→B = 58h; B→C = 47h; C→A = 36h.

      The call is made from A at 9pm on Thursday (A/C time), and received on the boat at at 9pm on Wednesday (B time).

      At this point it is 23 hours into the 47 hour journey, so B is 23 hours away and C is 24 hours away. (And A is about 42 hours away).

      The boat returns to B, and arrives at 8pm on Thursday (B time).

      If it continues to C, it would arrive 1 hour later at 9pm on Friday (C time) (as scheduled).

      Like

    • Hugo's avatar

      Hugo 2:22 pm on 21 May 2023 Permalink | Reply

      Not local times (which differ by 4 minutes for each degree of longitude) but zone times.
      We also have to assume that all the zone times are a whole number of hours fast or slow of GMT;
      Chatham Island (for example) is on GMT + 12:45.

      Like

    • Frits's avatar

      Frits 3:54 pm on 23 May 2023 Permalink | Reply

      Also calculating the distance to Aloha.

         
      from enigma import SubstitutedExpression
      
      # check the side lengths form a triangle
      def is_triangle(a, b, c):
        return all([0 < a < b + c, 0 < b < a + c, 0 < c < a + b])
        
      # distance to A to point (p, 0) on line BC 
      def dista(ab, bc, ac, p):  
        x = (ab**2 - ac**2 - bc**2) / (-2 * bc)
        y = (ac**2 - x**2)**.5
        
        # return distance between (x, y) and (p, 0)
        return ((x - p)**2 + (y - 0)**2)**.5
      
      # return local time, Mon 0am + <h> hours
      def time(h):
        weekdays = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday",
                    "Saturday", "Sunday"]
      
        (d, h) = divmod(h, 24)
        return weekdays[d % 7] + " " + str(h % 12) + ('am' if h < 12 else 'pm')
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
         # (K, L, M) = ahead bits for (A, B, C)
         "K + L + M < 3",
         
         # check that the adjusted times/distances form a triangle
         "is_triangle(((depb := 46 + 24 * (K - L)) - 3) - 9, \
                       (arrc := 117 + 24 * (K - M)) - depb, \
                       163 - (arrc + 10))",
                       
         # at time of the radio call the boat is still at sea (between B and C)
         "(93 - depb) and (arrc - 93)",
        ],
        answer="(da := dista((depb - 3) - 9, \
                             arrc - depb, \
                             163 - (arrc + 10), \
                             93 - depb), \
                93 - depb, arrc - 93), \
                (93 + da, 186 - depb + 24 * (L - K), arrc)",
        d2i=dict([(k, "KLM") for k in range(2, 10)]),
        distinct="",
        env=dict(is_triangle=is_triangle, dista=dista),
        reorder=0,
        verbose=0,    # use 256 to see the generated code
      )
      
      islands = ("Aloha", "Bali-Hai", "Crackatoea")
      # print answers
      for (_, ans) in p.solve():
         # determine shortest route
        for ind in [i for i, x in enumerate(ans[0]) if x == min(ans[0])]:
          print(f"reached island: {islands[ind]}, arrival: {time(ans[1][ind])}")
      

      Like

      • Jim Randell's avatar

        Jim Randell 9:39 pm on 23 May 2023 Permalink | Reply

        Yes, it does say the boat should proceed to the “nearest of the three islands”, so I’ve added in code to calculate the distance to A (using the cosine rule), and also to give a bit more information with the solution.

        Like

  • Unknown's avatar

    Jim Randell 4:38 pm on 19 May 2023 Permalink | Reply
    Tags:   

    Teaser 3165: Round the bend 

    From The Sunday Times, 21st May 2023 [link] [link]

    My new craft project involves card folding and requires a certain amount of precision and dexterity. For the penultimate stage a rectangular piece of card, with sides a whole number of centimetres (each less than 50cm), is carefully folded so that one corner coincides with that diagonally opposite to it. The resulting five-sided polygon also has sides of integer lengths in cm. The perimeter of the polygon is five twenty-eighths smaller than that of the perimeter of the original rectangular card.

    As a final check I need to find the new area of the card.

    What, in square centimetres, is the area of the polygon?

    [teaser3165]

     
    • Jim Randell's avatar

      Jim Randell 5:27 pm on 19 May 2023 Permalink | Reply

      See also: Teaser 2687.

      If the original rectangle has sides a and b (where a < b), then it has a perimeter of:

      p4 = 2a + 2b

      If the diagonal of the rectangle is h = hypot(a, b), then the length of the fold is:

      f = (a/b) h

      and this forms one of the sides of the pentagon, and so must be an integer.

      The side b is split by the fold into two (integer) lengths:

      b = x + y
      x = (b/2) − (a²/2b) = (b² − a²)/(2b)
      y = (b/2) + (a²/2b) = (b² + a²)/(2b) = h²/(2b)

      And so the perimeter of the pentagon is:

      p5 = 2a + 2x + f

      And the area of the pentagon is (the yellow area plus half the blue area):

      P = a(x + y/2) = a(b + x)/2

      The following Python program considers Pythagorean Triples for (a, b, h).

      It runs in 55ms. (Internal runtime is 73µs).

      Run: [ @replit ]

      from enigma import (pythagorean_triples, div, printf)
      
      # consider (a, b, h) values for the original rectangle
      for (a, b, h) in pythagorean_triples(68):
        if not (b < 50): continue
      
        # calculate the length of the fold = f
        f = div(a * h, b)
        if f is None: continue
      
        # calculate the shorter split of side b
        x = div((b - a) * (b + a), 2 * b)
        if x is None: continue
      
        # check perimeters
        p4 = 2 * (a + b)
        p5 = 2 * (a + x) + f
        if 28 * p5 != 23 * p4: continue
      
        # calculate the area of the pentagon
        P = 0.5 * a * (x + b)
      
        # output solution
        printf("a={a} b={b} h={h} f={f} x={x}; p4={p4} p5={p5}; P={P:g}")
      

      Solution: The area of the pentagon is 468 cm².

      The original rectangle is 24 × 32 (perimeter = 112).

      The fold divides the 32 side into 7 + 25, with a fold length of 30. Making the perimeter of the pentagon 92. (92/112 = 23/28).

      The rectangle is divided into 4 triangles: 2× T1 (base x, height a, area 84), 2× T2 (base y, height a, area 300), total area = 768.

      And the area of the pentagon is 2×T1 + T2 = 468.

      Liked by 1 person

      • Jim Randell's avatar

        Jim Randell 4:12 pm on 21 May 2023 Permalink | Reply

        Looking at my diagram the yellow triangles are an (x, a, y) Pythagorean triple (and b = x + y), so it gives us the dimensions of the rectangle immediately, and we then just need to find the length of the fold f.

        Run: [ @replit ]

        from enigma import (pythagorean_triples, ihypot, printf)
        
        # consider (a, b) values for the original rectangle, b = x + y
        for (x, a, y) in pythagorean_triples(54):
          b = x + y
          if not (a < b < 50): continue
        
          # calculate the length of the fold
          f = ihypot(y - x, a)
          if f is None: continue
        
          # check the perimeters
          p4 = 2 * (a + b)
          p5 = 2 * (a + x) + f
          if 28 * p5 != 23 * p4: continue
        
          # calculate the area of the pentagon
          P = 0.5 * a * (x + b)
        
          # output solution
          printf("a={a} b={b} x={x} y={y} f={f}; p4={p4} p5={p5}; P={P:g}")
        

        Like

        • Frits's avatar

          Frits 8:53 am on 22 May 2023 Permalink | Reply

          Nice.

          You can even go with a maximum allowed hypotenuse of 48 (int((48**2 + 49**2) / (2 * 49))).

          Like

    • Frits's avatar

      Frits 3:01 pm on 20 May 2023 Permalink | Reply

      Using a different pythagorean triple .

      There also is a relationship between a and b (for a specific (p, q, r) setting):

      (p * a) mod r = (q * b) mod r

       
      from enigma import (pythagorean_triples, div, printf)
       
      # consider (a, b, ?) values for the original rectangle
      
      # f also is the hypothenuse of a pythagorean triple
      # as f^2 = (a^2 / b)^2 + a^2     (see my explanation at PuzzlingInPython)
      for (y, a, f) in pythagorean_triples(int((47**2 + 48**2)**.5)):
        if not (a < 49): continue
        
        # y = a^2 / b
        b = div(a * a, y)
        if b is None or b > 49: continue
        
        # calculate the shorter split of side b
        x = div((b - a) * (b + a), 2 * b)
        if x is None: continue
       
        # check perimeters
        p4 = 2 * (a + b)
        p5 = 2 * (a + x) + f
        if 28 * p5 != 23 * p4: continue
       
        # calculate the area of the pentagon
        P = 0.5 * a * (x + b)
       
        # output solution
        printf("a={a} b={b} f={f} x={x}; p4={p4} p5={p5}; P={P:g}")  
      

      Like

      • Jim Randell's avatar

        Jim Randell 3:26 pm on 20 May 2023 Permalink | Reply

        @Frits: Neat – it eliminates h from the equations.

        And we can calculate x more succinctly at line 15:

        x = div(b - y, 2)
        

        (y here is y − x in my analysis above).

        And in both these programs we are down to a single candidate solution before the perimeter check is performed (suggesting this condition is superfluous for rectangles in the specified range).

        Like

  • Unknown's avatar

    Jim Randell 8:37 am on 18 May 2023 Permalink | Reply
    Tags:   

    Teaser 2630: River crossing 

    From The Sunday Times, 17th February 2013 [link] [link]

    Two lads walking together had to get back to their tent which was a short distance south-east of them. However, it involved crossing a river which was running from west to east and was a constant five metres wide. Whichever route they chose, they made sure that they were in the water for the shortest distance possible.

    One lad took the obvious such route and went due south and then due east, but the other took the shortest possible such route, thus cutting his friend’s distance by a quarter.

    What was the length of that shortest route?

    [teaser2630]

     
    • Jim Randell's avatar

      Jim Randell 8:38 am on 18 May 2023 Permalink | Reply

      See also: Teaser 3103.

      They both cross the river at right angles to give a river crossing of 5m.

      We can then remove the river, and the remaining (walking) paths are the sides of a right-angled triangle. The optimal route being the hypotenuse, and the first lad traversing the other two sides.

      So if the triangle has sides (x, y, z), the total length of the first path (including river crossing) is: (x + y + 5) and the total length of the second (optimal) path is (z + 5).

      And so:

      (z + 5) / (x + y + 5) = 3/4
      4z + 5 = 3(x + y)

      In order to get a unique solution to the puzzle we need to assume that the tent is exactly SE of the lads (i.e. on a bearing of 135°).

      Then the first lad travels the same total distance on the south leg of his journey (= x + 5) as he does on the east leg (= y).

      So we have:

      y = x + 5
      z = (3(x + y) − 5)/4 = (3x + 5)/2

      and:

      x² + y² = z²
      x² + (x + 5)² = (3x + 5)²/4
      8x² + 40x + 100 = 9x² + 30x + 25
      x² − 10x − 75 = 0
      (x + 5)(x − 15) = 0
      x = 15, y = 20, z = 25

      So the optimal distance is z + 5 = 30m.

      Solution: The shortest route is 30m.

      And the first lad’s distance is 40m.


      We can solve the quadratic equation using the [[ Polynomial() ]] class from the enigma.py library:

      Run: [ @replit ]

      from enigma import (Polynomial, sq, printf)
      
      # construct the polynomial (quadratic)
      px = Polynomial([0, 1])
      py = px + 5
      pz = (3 * px + 5) * 0.5
      p = sq(px) + sq(py) - sq(pz)
      printf("[p = {p}]")
      
      # find (real, positive) roots
      for x in p.quadratic_roots(domain='F', include='+'):
        (y, z) = (py(x), pz(x))
        printf("x={x:g} y={y:g} z={z:g} -> A={A:g} B={B:g}", A=x + y + 5, B=z + 5)
      

      Or we can solve the problem numerically, using the [[ find_value() ]] solver from the enigma.py library:

      Run: [ @replit ]

      from enigma import (find_value, hypot, fdiv, printf)
      
      # A's distance
      A = lambda x: 2 * (x + 5)
      
      # B's distance
      B = lambda x: hypot(x, x + 5) + 5
      
      # find a value where B/A = 3/4
      f = lambda x: fdiv(B(x), A(x))
      r = find_value(f, 0.75, 0, 1000)
      
      x = r.v
      (a, b) = (A(x), B(x))
      printf("B={b:g} A={a:g} -> B/A={f:g}", f=r.fv)
      

      If we had been told that the total distances travelled were whole numbers of metres, then we could look for appropriate right-angled triangles:

      Run: [ @replit ]

      from enigma import (pythagorean_triples, printf)
      
      for (x, y, z) in pythagorean_triples(995, primitive=0):
        if 4 * z + 5 == 3 * (x + y) and y == x + 5:
          printf("A={A} B={B} [x={x} y={y} z={z}]", A=x + y + 5, B=z + 5)
      

      The triangle we are looking for is a (15, 20, 25) triangle = 5× (3, 4, 5).

      Removing the [[ y == x + 5 ]] condition at line 4 allows us to find further (integer) solutions, where the tent is south and east of the starting position, but not on a bearing of 135°.

      Like

  • Unknown's avatar

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

    Teaser 2218: Speed trap 

    From The Sunday Times, 20th March 2005 [link]

    In Ireland they have changed from miles to kilometres. In European spirt and always using the rule of thumb that five miles convert to eight kilometres, I note that FIVE miles will convert into HUIT kilometres. Also UNE miles equals roughly four-fifths of TWO kilometres.

    Here, letters consistently stand for the same digit, and no two letters stand for the same digit.

    In figures, how many kilometres do NINE miles convert to?

    [teaser2218]

     
    • Jim Randell's avatar

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

      This Python program uses the [[ SubstitutedExpression() ]] solver from the enigma.py library to find values where FIVE / HUIT = 5 / 8, and then selects a solution with the minimum distance between UNE miles and 0.8× TWO kilometres.

      It runs in 63ms.

      Run: [ @replit ]

      from enigma import (SubstitutedExpression, Accumulator, printf)
      
      # make the alphametic problem
      p = SubstitutedExpression(
        ["div(FIVE * 8, 5) = HUIT"],
        answer="(UNE, TWO, FIVE, HUIT, NINE)",
        verbose=0
      )
      # solve it and collect answers
      r = Accumulator(fn=min, collect=1)
      for (s, ans) in p.solve():
        (UNE, TWO, FIVE, HUIT, NINE) = ans
        # difference between UNE miles and 0.8 TWO km (in km)
        r.accumulate_data(abs(1.6 * UNE - 0.8 * TWO), ans)
      
      # output minimal solutions
      for (UNE, TWO, FIVE, HUIT, NINE) in r.data:
        printf("FIVE ({FIVE}) miles = HUIT ({HUIT}) km")
        printf("diff(UNE ({UNE}) miles, 0.8x TWO ({TWO}) km) = {r.value:.3f} km")
        km = 1.6 * NINE
        printf("NINE ({NINE}) miles = {km:g} km")
        printf()
      

      Solution: NINE miles = 15512 km.

      We have:

      FIVE (4605) miles = HUIT (7368) km
      diff(UNE (395) miles, 0.8× TWO (812) km) = 17.600 km
      NINE (9695) miles = 15512 km

      Like

      • Frits's avatar

        Frits 11:57 am on 17 May 2023 Permalink | Reply

        @Jim, is there a reason why you didn’t use “accumulate=min” in SubstitutedExpression?

        Like

        • Jim Randell's avatar

          Jim Randell 12:45 pm on 17 May 2023 Permalink | Reply

          @Frits: I wanted to neaten up the output, and we are minimising a function of the answer parameter, so things end up a bit messier.

          But it is perfectly possible to do this:

          Run: [ @replit ]

          #! python3 -m enigma -rr
          
          SubstitutedExpression
          
          # FIVE miles is HUIT kilometres
          "div(HUIT * 5, 8) = FIVE"
          
          # UNE miles is roughly 4/5 of TWO kilometres
          --code="diff = lambda v1, v2: abs(1.6 * v1 - 0.8 * v2)"
          # answer is NINE miles, expressed as km
          --code="ans = lambda n: 1.6 * n"
          --answer="(diff(UNE, TWO), ans(NINE), UNE, TWO, FIVE, HUIT, NINE)"
          --accumulate="min"
          

          Like

    • Frits's avatar

      Frits 11:55 am on 17 May 2023 Permalink | Reply

       
      % A Solution in MiniZinc
      include "globals.mzn";
       
      var 1..9:F; var 0..9:I ; var 0..9:V ; var 0..9: E; var 1..9: H; 
      var 1..9:U; var 1..9:T ; var 0..9:W ; var 0..9: O; var 1..9: N; 
      
      function var int: toNum(array[int] of var int: a) =
                let { int: len = length(a) }
                in
                sum(i in 1..len) (
                  ceil(pow(int2float(10), int2float(len-i))) * a[i]
                );  
      
      % the digits are all different
      constraint all_different ([F,I,V,E,H,U,T,W,O,N]);
      
      %  FIVE miles will convert into HUIT kilometres
      constraint 1.6 * toNum([F, I, V, E]) == toNum([H, U, I, T]);
      
      solve minimize(abs(1.6 * toNum([U, N, E]) - 0.8 * toNum([T, W, O])));
       
      output["NINE = " ++ show(1.6 * toNum([N, I, N, E])) ++
             " diff = " ++ show(abs(1.6 * toNum([U, N, E]) - 0.8 * toNum([T, W, O])))];
      

      Like

  • Unknown's avatar

    Jim Randell 12:12 pm on 14 May 2023 Permalink | Reply
    Tags:   

    Brain-Teaser 556: Air ways 

    From The Sunday Times, 27th February 1972 [link]

    Al, Bill, Cab, Don, Ed, Fred, Gil, Hal, and Ian were waiting at the airport. Three would take a plane going east, three plane going north and three a plane going south.

    Hal, but neither Ian nor Fred, was going south. Al would be travelling with Don or Cab. Fred would be travelling with Bill or Ed.

    Gil, unlike Ian, would be travelling east. Cab would take a seat next to Ed or Al. Ian would travel in a different plane from Bill, and in a different plane from Cab.

    If Don would still be waiting at the airport after Bill and Ed had left, who were the three going north?

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

    [teaser556]

     
    • Jim Randell's avatar

      Jim Randell 12:13 pm on 14 May 2023 Permalink | Reply

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

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

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      # allocate directions: 1=E, 2=N, 3=S
      --digits="1,2,3"
      --distinct=""
      
      # 3 go in each direction
      "multiset.from_seq([A, B, C, D, E, F, G, H, I]).all_same(3)"
      
      # H is going S; but I, F are not
      "H = 3" "I != 3" "F != 3"
      
      # A is travelling with D or C
      "A in {D, C}"
      
      # F is travelling with B or E
      "F in {B, E}"
      
      # G is travelling E; but I is not
      "G = 1" "I != 1"
      
      # C is travelling with E or A
      "C in {E, A}"
      
      # I is not travelling with B or C
      "I not in {B, C}"
      
      # D is not travelling with B or E
      "D not in {B, E}"
      
      --template=""
      

      Solution: Al, Don, Ian are travelling north.

      The full solution:

      East = B, F, G
      North = A, D, I
      South = C, E, H

      Like

      • Frits's avatar

        Frits 3:24 pm on 14 May 2023 Permalink | Reply

        Or:

        3 go in each direction

        “div(216, A * B * C * D * E * F * G * H) = I”

        Like

        • Jim Randell's avatar

          Jim Randell 3:40 pm on 14 May 2023 Permalink | Reply

          A good job I used non-zero digits ;-).

          Like

          • Frits's avatar

            Frits 5:19 pm on 14 May 2023 Permalink | Reply

            With zero you can use other non-zero digits d and 3d + 1 with check

            “(calculate 12d + 3) – sum([A, B, C, D, E, F, G, H]) = I”

            Like

  • Unknown's avatar

    Jim Randell 4:22 pm on 12 May 2023 Permalink | Reply
    Tags:   

    Teaser 3164: Touching base 

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

    Liam has a pack of twenty cards; each card has a number printed on it as a word rather than figures.

    There are two cards with ONE, two cards with TWO etc., up to two cards with TEN. He has taken four of the cards to construct an addition sum. The largest value card he has used is the sum of the values of the other cards, e.g.:

    ONE + ONE + TWO = FOUR.

    If I now work in the base equal to that sum (i.e., base 4 in the example), and consistently replace letters with single digits, this gives a correct sum. All of the possible digits in that base are used.

    Leaving the answer in the working base, what is the total of my addition sum?

    [teaser3164]

     
    • Jim Randell's avatar

      Jim Randell 4:50 pm on 12 May 2023 Permalink | Reply

      This Python program constructs the viable alphametic sums and then uses the [[ SubstitutedExpression.split_sum() ]] solver from the enigma.py library to evaluate them (assuming “standard” alphametic rules, i.e. leading zeros are not allowed, and each letter stands for a different digit).

      It runs in 73ms. (Internal runtime is 16.8ms).

      Run: [ @replit ]

      from enigma import (
        SubstitutedExpression, irange, multiset, subsets, int2words,
        union, join, substitute, sprintf as f, printf
      )
      
      # the cards
      cards = multiset.from_seq(irange(1, 10), count=2)
      
      # choose 3 of the cards
      for cs in subsets(cards, size=3, select="mC", fn=list):
        # add in the the sum of the 3 cards
        t = sum(cs)
        cs.append(t)
        # check they make a valid set of 4 cards
        if not cards.issuperset(cs): continue
        # construct the corresponding words
        ws = list(int2words(x).upper() for x in cs)
        # check there are t different letters
        if len(union(ws)) != t: continue
      
        # construct the alphametic sum
        expr = f("{terms} = {result}", terms=join(ws[:-1], sep=" + "), result=ws[-1])
        p = SubstitutedExpression.split_sum(expr, base=t, verbose=0)
        # and solve it
        for s in p.solve():
          # output solution
          ss = substitute(s, expr)
          printf("{expr} / {ss} [base {t}]")
      

      Or a faster (but longer) version [ @replit ]. (Internal runtime is 6.1ms).

      Solution: The result of the sum is: 61503 (in base 8).

      There are 2 candidate alphametic sums (under “standard” alphametic rules):

      ONE + ONE + FIVE = SEVEN (7 letters)
      TWO + THREE + THREE = EIGHT (8 letters)

      Only the one with 8 letters yields solutions in the appropriate base.

      So the sum is:

      TWO + THREE + THREE = EIGHT
      327 + 30466 + 30466 = 61503 [base 8]
      215 + 12598 + 12598 = 25411 [base 10]

      In Python:

      >>> 0o327 + 0o30466 + 0o30466 == 0o61503
      True
      

      Like

    • Frits's avatar

      Frits 9:21 pm on 12 May 2023 Permalink | Reply

      The commented code seems to work but somehow it runs slower than threee separate checks.

         
      from itertools import permutations
      from math import ceil
      
      # convert a string in the specified base to an integer
      d2n = lambda s, b: int(''.join(str(x) for x in s), b)
      
      # the numbers
      numbers = ('ONE', 'TWO', 'THREE', 'FOUR', 'FIVE', 
                 'SIX', 'SEVEN', 'EIGHT', 'NINE', 'TEN')
      
      # choose 3 of the cards (below ten)
      for a in range(1, 4):
        # a + 2b <= 10
        for b in range(a, ceil((10 - a) / 2) + 1):
          for c in range(b, 11 - a - b):
            if a == b == c: continue
            t = sum([a, b, c])
            
            # get all the letters
            ltrs = [x for n in (a, b, c, t) for x in numbers[n - 1]]
            if len(set(ltrs)) != t: continue
            
            # get words
            ws = [numbers[n - 1] for n in (a, b, c, t)]
            
            # skip if RHS word is too short
            if any(len(ws[i]) > len(ws[-1]) for i in range(3)):
              continue
              
            ltrs = list(set(ltrs))
            # determine non-zero positions
            nz_ltrs = set(x[0] for x in ws)
            nz_pos = [i for i, x in enumerate(ltrs) if x in nz_ltrs]
            (u_pos, t_pos, h_pos) = ([ltrs.index(x) for x in [x[-i] for x in ws]]
                                      for i in range(1, 4))
                
            # check all possible letter values
            for p in permutations(range(t)):
              # skip for leading zeroes
              if any(not p[x] for x in nz_pos): continue
              
              '''
              sm = 0
              # already check unit/ten/hundred sums
              if any((sm := (sm // t + sum(p[x] for x in chk[:-1]))) % t != p[chk[-1]]
                     for chk in (u_pos, t_pos, h_pos)
                    ): continue
              '''
              # check unit sum
              if (usum := sum(p[x] for x in u_pos[:-1])) % t != p[u_pos[-1]]: 
                continue
              
              # check ten sum
              if (tsum := (usum // t + sum(p[x] for x in t_pos[:-1]))) % t != \
                           p[t_pos[-1]]: continue
              
              # check hundred sum
              if (hsum := (tsum // t + sum(p[x] for x in h_pos[:-1]))) % t != \
                           p[h_pos[-1]]: continue
              
              # perform the complete check via dictionary lookup
              d = {ltr: v for ltr, v in zip(ltrs, p)}
              # get the terms in base t
              ns = [[d[x] for x in ws[i]] for i in range(4)]
              # check the sum in base t
              if sum(d2n(n, t) for n in ns[:-1]) != d2n(ns[-1], t): continue
              
              print(ws)
            
              print("answer:", ''.join(str(x) for x in ns[-1]))
      

      Like

    • Frits's avatar

      Frits 11:04 am on 13 May 2023 Permalink | Reply

      from enigma import SubstitutedExpression
      from math import ceil
      
      # the numbers
      numbers = ('ONE', 'TWO', 'THREE', 'FOUR', 'FIVE', 
                 'SIX', 'SEVEN', 'EIGHT', 'NINE', 'TEN')
      
      carry_ltrs = "ABCD" # maximum word length is 5 so 4 free letters needed             
      
      # choose 3 of the cards (below ten)
      for a in range(1, 4):
        # a + 2b <= 10
        for b in range(a, ceil((10 - a) / 2) + 1):
          for c in range(b, 11 - a - b):
            if a == b == c: continue
            t = sum([a, b, c])
            
            # get string of used letters 
            ltrs = ''.join(set(x for n in (a, b, c, t) for x in numbers[n - 1]))
            if len(set(ltrs)) != t: continue
            
            # get words
            ws = [numbers[n - 1] for n in (a, b, c, t)]
            lenRHS = len(ws[-1])
            
            # skip if RHS word is too short
            if any(len(ws[i]) > lenRHS for i in range(3)):
              continue
            
            # letters per column
            c_ltrs = [[ws[j][-i] if i <= len(ws[j]) else '0' for j in range(4)]
                     for i in range(1, lenRHS + 1)]
            carries = ['0'] + list(carry_ltrs[:lenRHS - 1]) + ['0']
          
            # build expressions per column
            exprs = []
            for i, s in enumerate(c_ltrs):
              exprs.append("(" + '+'.join(s[:-1]) + "+" + carries[i] + ") % " + 
                           str(t) + " = " + s[-1])
              exprs.append("(" + '+'.join(s[:-1]) + "+" + carries[i] + ") // " + 
                           str(t) + " = " + carries[i + 1])
            
            # the alphametic puzzle
            p = SubstitutedExpression(
              exprs,
              base=t,
              answer='(' + '), ('.join(list(','.join(w) for w in ws)) + ')',
              d2i=dict([(0, set(w[0] for w in ws))] + 
                       [(k, carries[1:-1]) for k in range(3, t)]),
              distinct=ltrs,   
              verbose=0,
            )
            
            # print answer
            for (_, ans) in p.solve():
              print(f"{' + '.join(ws[:-1])} = {ws[-1]}")
              print("answer:", ''.join(str(x) for x in ans[-1]))   
      

      Like

    • Frits's avatar

      Frits 1:19 pm on 13 May 2023 Permalink | Reply

      Another variation. This program sometimes runs under 10ms.

       
      from itertools import permutations
      from math import ceil
      
      # the numbers
      numbers = ('ONE', 'TWO', 'THREE', 'FOUR', 'FIVE',
                 'SIX', 'SEVEN', 'EIGHT', 'NINE', 'TEN')
                 
      # process sum per column for each column in <cols>
      def solve_column(base, rng, cols, carry, d=dict()):
        if not cols:
          yield d
        else:
          col = cols[0]
          novalue = set(x for x in col if x not in d and x != '0')
          for p in permutations(rng, len(novalue)):
            d_ = d.copy()  
            d_['0'] = 0        # for dummy letter
           
            i = 0
            # assign letters without value
            for c1 in set(col):
              if c1 not in d_:
                d_[c1] = p[i]
                i += 1
           
            # substitute letters by value
            lst = [d_[c2] for c2 in col]
         
            # check column sum
            if (csum := (carry + sum(lst[:-1]))) % base == lst[-1]:
              yield from solve_column(base, set(rng).difference(p), cols[1:],
                                      csum // base, d_)
      
      # choose 3 of the cards (below ten)
      for a in range(1, 4):
        # a + 2b <= 10
        for b in range(a, ceil((10 - a) / 2) + 1):
          for c in range(b, 11 - a - b):
            if a == b == c: continue
            t = sum([a, b, c])
           
            # get all the letters
            ltrs = [x for n in (a, b, c, t) for x in numbers[n - 1]]
            if len(set(ltrs)) != t: continue
           
            # get words
            ws = [numbers[n - 1] for n in (a, b, c, t)]
            lenRHS = len(ws[-1])
                 
            # skip if RHS word is too short
            if any(len(ws[i]) > lenRHS for i in range(3)):
              continue
             
            # determine non-zero letters
            nz_ltrs = set(x[0] for x in ws if len(x) > 1)
           
            # letters per column
            c_ltrs = [[ws[j][-i] if i <= len(ws[j]) else '0' for j in range(4)]
                      for i in range(1, lenRHS + 1)]
           
            # solve sums for all columns
            for d1 in solve_column(t, range(t), c_ltrs, 0):
              # check for leading zeroes
              if any(d1[x] == 0 for x in nz_ltrs): continue
              print("answer:", ''.join(str(d1[x]) for x in ws[-1]))
      

      Like

    • Frits's avatar

      Frits 3:23 pm on 17 May 2023 Permalink | Reply

      With range based logic (maybe domain is a better word).

       
      from itertools import permutations
      from math import ceil
      
      # the numbers
      numbers = ('ONE', 'TWO', 'THREE', 'FOUR', 'FIVE', 
                 'SIX', 'SEVEN', 'EIGHT', 'NINE', 'TEN')
      
      # pick one value from each entry of a <ns> 
      # so that all <k> values are different
      def pickOneFromEach(k, ns, s=[]):
        if k == 0:
           yield s
        else:
          for n in ns[k - 1]:
            if n not in s:
              yield from pickOneFromEach(k - 1, ns, [n] + s)
      
      # try to reduce ranges with analysis
      def reduce_ranges(base, words, cols, rngs):
        # check first column 
        chars = [x for x in cols[-1][:-1] if x != '0']
      
        # no letters to add?
        if not chars:
          # total digit in first column must be 1
          rngs = {k: [1] if k == cols[-1][-1] else set(v).difference([1]) 
                     for k, v in rngs.items()}
      
        # only one letter has to be added more than once 
        elif len(set(chars)) == 1 and len(chars) > 1:
          mx = (base - 1) // len(chars)
          rngs[chars[0]] = [x for x in rngs[chars[0]] if x <= mx]
      
          mn = rngs[chars[0]][0]
          # total digit may have a new minimum
          rngs[cols[-1][-1]] = [x for x in rngs[cols[-1][-1]] if x >= mn * len(chars)]  
      
        # check last column 
        chars = [x for x in cols[0][:-1] if x != '0']
      
        # only one letter has to be added 
        if len(set(chars)) == 1 and chars[0] != cols[0][-1]:
          # a multiple of zero is zero
          rngs[chars[0]] = [x for x in rngs[chars[0]] if x != 0]
      
        # stop with the analysis
        return rngs  
      
      # process sum per column for each column in <cols>
      def solve_column(base, used, cols, carry, d={'0': 0}):
        if not cols:
          yield d
        else:
          col = cols[0]
          unused_ltrs = sorted(set(x for x in col if x not in d and x != '0'))
          # get ranges for unused letters (without used values)
          rs = [[y for y in ranges[x] if y not in used] for x in unused_ltrs]
          for p in pickOneFromEach(len(unused_ltrs), rs):
            d_ = d.copy()  
            d_.update(zip(unused_ltrs, p))    
      
            # substitute letters by value
            vs = [d_[c2] for c2 in col]
      
            # check column sum
            if (csum := (carry + sum(vs[:-1]))) % base == vs[-1]: 
              yield from solve_column(base, used | set(p), cols[1:], 
                                      csum // base, d_)
      
      # choose 3 of the cards (below ten)
      for a in range(1, 4):
        # a + 2b <= 10
        for b in range(a, ceil((10 - a) / 2) + 1):
          for c in range(b if b > a else b + 1, 11 - a - b):
            t = sum([a, b, c])
      
            # get all the letters
            ltrs = [x for n in (a, b, c, t) for x in numbers[n - 1]]
            if len(set(ltrs)) != t: continue
      
            # get words
            ws = [numbers[n - 1] for n in (a, b, c, t)]
            lenRHS = len(ws[-1])
      
            # skip if RHS word is too short
            if any(len(ws[i]) > lenRHS for i in range(3)):
              continue
      
            # determine non-zero letters
            nz_ltrs = set(x[0] for x in ws if len(x) > 1)
      
            # letters per column
            c_ltrs = [[ws[j][-i] if i <= len(ws[j]) else '0' for j in range(4)]
                      for i in range(1, lenRHS + 1)]
      
            # determine initial range per letter
            ranges = {ltr: range(0 if ltr not in nz_ltrs else 1, t) for ltr in ltrs}
            ranges = reduce_ranges(t, ws, c_ltrs, ranges)          
      
            # solve sums for all columns
            for d1 in solve_column(t, set(), c_ltrs, 0):
              print("answer:", ''.join(str(d1[x]) for x in ws[-1]))  
      

      Like

  • 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

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