Design a site like this with WordPress.com
Get started

Tagged: by: Victor Bryant Toggle Comment Threads | Keyboard Shortcuts

  • Jim Randell 4:21 pm on 4 November 2022 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 3137: Common names 

    From The Sunday Times, 6th November 2022 [link] [link]

    Eight friends met at a party; their ages in whole numbers of years were all different. They were Alan, Cary, James, Lucy, Nick, Ricky, Steve and Victor, with Lucy being the youngest. For each of them the square of their age was a three-figure number consisting of three different digits. Furthermore, for any two of them, the squares of their ages had at least one digit in common precisely when their names had at least one letter in common.

    In alphabetical order of their names, what are the eight ages?

    [teaser3137]

     
    • Jim Randell 4:49 pm on 4 November 2022 Permalink | Reply

      This Python program runs in 61ms. (Internal runtime is 9.2ms).

      Run: [ @replit ]

      from enigma import (irange, sq, nsplit, diff, intersect, append, delete, subsets, printf)
      
      # model a symmetric relation
      class Relation(set):
        # check if x is related to y
        def __call__(self, x, y):
          return (x, y) in self or (y, x) in self
      
      # names
      names = "ALAN CARY JAMES LUCY NICK RICKY STEVE VICTOR".split()
      
      # names are related when they share a letter
      N = Relation((x, y) for (x, y) in subsets(names, size=2) if intersect([x, y]))
      
      # find 3-digits squares with no repeated digits
      sqs = dict()
      for i in irange(10, 31):
        ds = set(nsplit(sq(i)))
        if len(ds) == 3:
          sqs[i] = ds
      
      # values are related when their squares share a digit
      V = Relation((x, y) for ((x, sx), (y, sy)) in subsets(sqs.items(), size=2) if intersect([sx, sy]))
      
      # assign values to remaining names
      # names = remaining names
      # ss = used (name, value) pairs
      # vs = remaining values
      def solve(names, ss, vs):
        if not names:
          yield ss
        elif not len(names) > len(vs):
          # choose a value for the next name
          n = names[0]
          for (i, v) in enumerate(vs):
            # check values have digits in common when names have letters in common
            if all(N(n, n_) == V(v, v_) for (n_, v_) in ss):
              # solve for the remaining names
              yield from solve(names[1:], append(ss, (n, v)), delete(vs, [i]))
      
      # choose an age for LUCY (the youngest)
      n0 = "LUCY"
      ks = sorted(sqs.keys())
      for (i, k) in enumerate(ks):
        # solve for the remaining names
        for ss in solve(diff(names, {n0}), [(n0, k)], ks[i + 1:]):
          # output solution
          for (n, v) in sorted(ss):
            printf("{n} -> {v} [{s}]", s=sq(v))
          printf()
      

      Solution: The ages are: 19, 31, 29, 16, 25, 23, 28, 27.

      With squares in square brackets:

      ALAN = 19 [361]
      CARY = 31 [961]
      JAMES = 29 [841]
      LUCY = 16 [256]
      NICK = 25 [625]
      RICKY = 23 [529]
      STEVE = 28 [784]
      VICTOR = 27 [729]

      Like

    • Paul Byrne 9:54 pm on 14 November 2022 Permalink | Reply

      Hi Jim
      Thanks for all the good work on these Teasers.
      Love the simplicity of your website and your solutions.
      Re 3137 Teaser
      Is 24 instead of 31 also a correct answer? Keep up the good work!

      Like

      • Jim Randell 9:17 am on 15 November 2022 Permalink | Reply

        @Paul: Thanks for the feedback.

        We can’t swap CARY for 24 in the solution I give above, as 24² = 576, and CARY and JAMES share the letter A, so their squares need to share a digit. But 576 and 841 (= 29²) don’t have any digits in common.

        Like

    • Paul Byrne 10:21 am on 16 November 2022 Permalink | Reply

      Hi Jim, thank you very much for your response.

      Forgive me I should’ve made myself clearer.
      If Cary becomes 576, and James 784, and Steve 841, can it then work as an alternative?

      Like

      • Jim Randell 12:14 pm on 16 November 2022 Permalink | Reply

        @Paul: My program performs an exhaustive search, so there is only one solution to the puzzle.

        If we had:

        CARY = 24 [576]
        JAMES = 28 [784]
        STEVE = 29 [841]

        Then {LUCY, NICK, RICKY} must correspond to {16 [256], 23 [529], 25 [625]} in some order.

        LUCY is the youngest, so we have:

        LUCY = 16 [256]

        But then ALAN has to have digits in common with CARY [576], LUCY [256], JAMES [784], but not STEVE [841]

        Which means for ALAN we need to find a square with a 7 and a 5 or a 6. The only candidate is 24 [576], but that is already used by CARY, so it is not possible to find a value for ALAN in this scenario.

        Like

    • Paul Byrne 5:17 pm on 16 November 2022 Permalink | Reply

      Hi Jim
      Alas I’m thwarted!
      Thanks for this and all your efforts.
      They are all appreciated.
      Regards Paul

      Like

  • Jim Randell 9:28 am on 27 October 2022 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2295: Girl meets boy 

    From The Sunday Times, 17th September 2006 [link]

    In the two sums displayed, digits have consistently
    been replaced by letters, with different letters for
    different digits:

    GIRL + BOY = LOVE
    GIRLBOY = ???

    Unfortunately, I have missed out the second answer,
    but I can tell you that it is a three-letter word.

    Find my LOVER‘s number.

    [teaser2295]

     
    • Jim Randell 9:29 am on 27 October 2022 Permalink | Reply

      This Python program solves the first alphametic sum (using the [[ SubstitutedExpression.split_sum() ]] solve from the enigma.py library), and then produces potential answers for the remaining partial alphametic expression.

      It runs in 57ms. (Internal runtime is 5.8ms).

      Run: [ @replit ]

      from enigma import (SubstitutedExpression, nsplit, substitute, join, map2str, printf)
      
      # create the alphametic puzzle
      p = SubstitutedExpression.split_sum("{GIRL} + {BOY} = {LOVE}", answer="{GIRL} - {BOY}")
      
      # solve the puzzle
      for (s, ans) in p.solve(verbose=0):
        # answer should be 3 digits
        ds = nsplit(ans)
        if len(ds) != 3: continue
        # map digits to symbols
        r = dict((v, k) for (k, v) in s.items() if k in p.symbols)
        # find the answer as a word
        w = join(r.get(d, '?') for d in ds)
        # output potential answers
        LOVER = substitute(s, "LOVER")
        printf("{ans}={w} -> LOVER={LOVER} / {r}", r=map2str(r, sep=" ", enc=""))
      

      From the output we find there are 4 candidate solutions:

      answer = 586 → IEY
      answer = 715 → YGI
      answer = 879 → BI?
      answer = 914 → VG?

      Only the third of these can form a normal word.

      By assigning an unused letter to 9, we can make 879 read as BID, BIN, BIT, BIZ. (None of which are particularly appropriate).

      Solution: LOVER = 26054.

      Like

    • GeoffR 3:30 pm on 27 October 2022 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 0..9: G; var 0..9: I; var 0..9: R; var 0..9: L; var 0..9: B;
      var 0..9: O; var 0..9: Y; var 0..9: V; var 0..9: E; 
      
      constraint G > 0 /\ B > 0 /\ L > 0;
      constraint all_different([G, I, R, L, B, O, Y, V, E]);
      
      var 1000..9999:GIRL = 1000*G +100*I + 10*R + L;
      var 100..999:BOY = 100*B + 10*O + Y;
      var 1000..9999: LOVE = 1000*L + 100*O + 10*V + E;
      var 10000..99999:LOVER = 10000*L + 1000*O + 100*V + 10*E + R;
      var 100..999: sub_res;  % result of 2nd subtraction sum
      
      % The two equations
      constraint GIRL + BOY == LOVE;
      constraint GIRL - BOY == sub_res;  % a 3-digit answer
      
      solve satisfy;
      
      output [ "LOVER = " ++ show(LOVER) ++ "  sub_res = " ++ 
      show(sub_res) ++ "\n" ++ "GIRL = " ++ show(GIRL) ++ " , " ++  
      " BOY = " ++ show(BOY) ++ ", LOVE = " ++ show(LOVE) 
      ++ "\n" ++ "[G,I,R,L,B,O,Y,V,E] = " ++ show([G,I,R,L,B,O,Y,V,E]) ];
      
      % LOVER = 23905  sub_res = 914 - which is VG?
      % GIRL = 1652 ,  BOY = 738, LOVE = 2390
      % [G,I,R,L,B,O,Y,V,E] = [1, 6, 5, 2, 7, 3, 8, 9, 0]
      % ---------- 
      % LOVER = 24096  sub_res = 715 - which is YGI
      % GIRL = 1562 ,  BOY = 847, LOVE = 2409
      % [G,I,R,L,B,O,Y,V,E] = [1, 5, 6, 2, 8, 4, 7, 0, 9]
      % ----------
      % LOVER = 24783  sub_res = 586 - which is IEY
      % GIRL = 1532 ,  BOY = 946, LOVE = 2478
      % [G,I,R,L,B,O,Y,V,E] = [1, 5, 3, 2, 9, 4, 6, 7, 8]
      % ----------
      % LOVER = 26054  sub_res = 879 - which is BI?
      % GIRL = 1742 ,  BOY = 863, LOVE = 2605
      % [G,I,R,L,B,O,Y,V,E] = [1, 7, 4, 2, 8, 6, 3, 0, 5]
      % ----------
      % ==========
      % ANS: LOVER = 26054 - for only viable 2nd equation
      
      
      
      

      Like

  • Jim Randell 9:19 am on 8 September 2022 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2740: X times 

    From The Sunday Times, 29th March 2015 [link] [link]

    In this long multiplication sum, I am multiplying a three-figure number by itself. Throughout the workings one particular digit has been replaced by X wherever it occurs: all other digits have been replaced by a question mark.

    What is the three-figure number being squared?

    [teaser2740]

     
    • Jim Randell 9:21 am on 8 September 2022 Permalink | Reply

      The intermediate multiplications are presented in the opposite order to how I was taught long multiplication. But from the layout of the columns the intent is obvious.

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

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

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      #       a X b
      #  *    a X b
      #   ---------
      #   c d e      = aXb * a
      #   f g X X    = aXb * X
      #     h i j k  = aXb * b
      #   ---------
      #   X m n p q  = aXb * aXb
      
      SubstitutedExpression
      
      # added symbols are different from X
      --distinct="aX,bX,cX,dX,eX,fX,gX,hX,iX,jX,kX,mX,nX,pX,qX"
      
      # the multiplication sum
      "{aXb} * {aXb} = {Xmnpq}"
      "{aXb} * {a} = {cde}"
      "{aXb} * {X} = {fgXX}"
      "{aXb} * {b} = {hijk}"
      
      --answer="{aXb}"
      

      Solution: The number being squared is: 286.

      Note that you will find the answer even if you don’t check that the question marks are all different from X (we can use [[ --distinct="" ]] to show this), but without this check the solution is not complete.

      Like

    • GeoffR 1:33 pm on 8 September 2022 Permalink | Reply

      
      from itertools import permutations
      
      for p1 in permutations('1234567890', 3):
          a, X, b = p1
          aXb = int(a + X + b)
          # check leading digit of multiplication result
          res = aXb * aXb
          if res //10000 != int(X):continue
          
          # 1st line of multiplication
          line1 = int(a) * aXb * 100
          if X in set(str(line1)):continue
          
          # 2nd line of multiplication
          line2 = int(X) * aXb * 10
          if line2 //100 % 10 != int(X):continue
          if line2//10 % 10 != int(X):continue
          
          # 3rd line of multiplication
          line3 = int(b) * aXb
          if X in set(str(line3)):continue
          print(f"The three-figure number being squared is {aXb}.")
      
      # The three-figure number being squared is 286.
      
      
      

      Like

  • Jim Randell 4:31 pm on 19 August 2022 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 3126: Sweet success 

    From The Sunday Times, 21st August 2022 [link] [link]

    My five nieces Abby, Betty, Cathy, Dolly and Emily each had some sweets. I asked them how many they had but they refused to answer directly. Instead, in turn, each possible pair from the five stepped forward and told me the total number of sweets the two of them had. All I remember is that all ten totals were different, that Abby and Betty’s total of 8 was the lowest, and that Cathy and Dolly’s total of 18 was the second highest. I also remember one of the other totals between those two but I don’t remember whose total it was. With that limited information I have worked out the total number of sweets.

    In fact it turns out that the other total I remember was Betty and Cathy’s.

    In alphabetical order of their names, how many sweets did each girl have?

    [teaser3126]

     
    • Jim Randell 5:29 pm on 19 August 2022 Permalink | Reply

      I had to read it through a few times to get the mechanics straight.

      This Python program runs in 68ms. (Internal run time is 15.3ms).

      Run: [ @replit ]

      from collections import defaultdict
      from enigma import (irange, subsets, matrix, as_int, nCr, peek, printf)
      
      # check a collection of values
      def check(vs):
        k = len(vs)
        # all pair sums are different
        ps = set(x + y for (x, y) in subsets(vs, size=2))
        if len(ps) != nCr(k, 2): return False
        # min pair sum is 8
        m = min(ps)
        if (k == 5 and m != 8) or m < 8: return False
        # only one pair sum is > 18
        n = sum(s > 18 for s in ps)
        if (k == 5 and n != 1) or n > 1: return False
        # looks OK
        return True
      
      # generate possible (A, B, C, D, E) values
      def generate():
        # for constructing equations in A, B, C, D
        eq = matrix.equation("ABCD")
      
        # choose a non-highest pair from AC, AD, BD
        for nhp in ['AC', 'AD', 'BD']:
          # and choose values for it and BC (between 9 and 17)
          for (v1, v2) in subsets(irange(9, 17), size=2, select='P'):
            # solve the 4 equations for integer A, B, C, D
            # A + B = 8; C + D = 18; B + C = {v1}; {nhp} = {v2}
            eqs = [ eq('AB', 8), eq('CD', 18), eq('BC', v1), eq(nhp, v2) ]
            try:
              (A, B, C, D) = matrix.linear(eqs, valid=(lambda x: as_int(x, '+')))
            except ValueError:
              continue
      
            # check all A, B, C, D pairings
            if not check([A, B, C, D]): continue
      
            # choose a value for E
            for E in irange(1, 18):
              if not check([A, B, C, D, E]): continue
              yield (A, B, C, D, E)
      
      # collect candidate values
      ss = set(generate())
      
      # record candidate totals by pair sums
      d = defaultdict(set)
      for vs in ss:
        t = sum(vs)
        for (x, y) in subsets(vs, size=2):
          d[x + y].add(t)
      
      # look for a sum between 8 and 18 (exclusive), with only one candidate total
      for (k, vs) in d.items():
        if 8 < k < 18 and len(vs) == 1:
          t = peek(vs)
          printf("[{k} -> total {t}]")
          # find candidates values with the same total, and k = B + C
          for (A, B, C, D, E) in ss:
            if B + C == k and A + B + C + D + E == t:
              printf("A={A} B={B} C={C} D={D} E={E}")
      

      Solution: The numbers of sweets are: Abby = 5; Betty = 3; Cathy = 6; Dolly = 12; Emily = 7.

      So the pairs are:

      A+B = 8
      B+C = 9
      B+E = 10
      A+C = 11
      A+E = 12
      C+E = 13
      B+D = 15
      A+D = 17
      C+D = 18
      D+E = 19


      There are 4 possible total values: 33, 34, 35, 36. Each with a single set of individual values, and 4 corresponding distributions of sweets are made by swapping the A/B and C/D pairs. (So there are 16 possible distributions in total).

      But the pair sum of 9 only appears for the values that have a total of 33.

      So we are interested in distributions with a total of 33, where B + C = 9. And only one of the four distributions with a total of 33 qualifies.

      Like

      • Jim Randell 8:58 am on 20 August 2022 Permalink | Reply

        Or using [[ decompose ]] to calculate A, B, C, D. This Python program is shorter and faster.

        It runs in 52ms. (Internal run time is 557µs).

        Run: [ @replit ]

        from collections import defaultdict
        from enigma import (Decompose, irange, subsets, cproduct, peek, printf)
        
        # decompose a pair sum into viable pairs
        decompose = Decompose(2, increasing=0, sep=1, min_v=1)
        
        # record candidates by total and candidate totals by pair sums,
        (t2vs, ps2t) = (defaultdict(list), defaultdict(set))
        
        # A + B = 8; C + D = 18
        for ((A, B), (C, D)) in cproduct(decompose(x) for x in (8, 18)):
          vs4 = (A, B, C, D)
          # check pair sums (so far)
          ps4 = sorted(set(x + y for (x, y) in subsets(vs4, size=2)))
          if len(ps4) != 6 or ps4[0] < 8 or ps4[-2] > 18: continue
          # choose value for E
          for E in irange(9 - min(vs4), 18):
            # construct the pair sums
            ps = sorted(set(ps4 + [x + E for x in vs4]))
            if ps[-2] > 18: break
            # check pair sums
            if not (len(ps) == 10 and ps[0] == 8 and ps[-2] == 18): continue
            # record the results
            t = 26 + E
            t2vs[t].append(vs4 + (E,))
            for s in ps[1:-2]:
              ps2t[s].add(t)
        
        # look for a pair sum, with only 1 candidate total
        for (s, ts) in ps2t.items():
          if len(ts) == 1:
            t = peek(ts)
            printf("[{s} -> total {t}]")
            # find candidates with the same total and s = B + C
            for (A, B, C, D, E) in t2vs[t]:
              if B + C == s:
                printf("A={A} B={B} C={C} D={D} E={E}")
        

        Like

    • NigelR 1:31 pm on 20 August 2022 Permalink | Reply

      On a roll this week! enigma timer gives: [timing] total time: 0.0012704s (1.27ms)
      (PS: Thanks for advice on Thonny, Jim. Removing hints on indentation fixed crashing issue)

      def ptots():
         pairs = [[a,b],[a,c],[a,d],[a,e],[b,c],[b,d],[b,e],[c,d],[c,e],[d,e]]
         return sorted([sum(x) for x in pairs])
      # values within pairs might be other way round (ie b,a not a,b etc.)
      valid=[]
      for a in [1,2,3]:
          b = 8 - a
          for c in range(b,9):
              d = 18 - c
              for e in range(c+1,15):
                  if e == d:continue
                  tots = ptots()
                  if len(set(tots)) != 10 or min(tots) != 8: continue
                  if len([x for x in tots if x > 18]) != 1: continue
                  valid.append([a,b,c,d,e])
      # now look for unique pair total between 8 and 18 in 'valid'
      x=[]
      for res in valid:
          a,b,c,d,e = res
          tots = ptots()
          x = x + tots
      # generate dictionary with count of possible pair totals across all valid values
      totcount = {y:x.count(y) for y in set(x) if y > 8 and y < 18}
      # is there a pair total that occurs only once in all valid sets for a,b,c,d,e?
      uniqtot = [x for x in totcount.keys() if totcount[x] == 1]
      if len(uniqtot) != 1:
          print('Unique solution not found')
      else:
          uniqtot = uniqtot[0]
          print('Unique pair total is:', uniqtot)
          for res in valid:
              a,b,c,d,e=res
              bc = [[x,y] for x in [a,b] for y in [b,c] if x+y == uniqtot]
              if not bc: continue
              print('Unique set of values (not necessarily in abcde order) is:',a,b,c,d,e)
              if b != [y for x in bc for y in x][0]: a,b = b,a  #swap a and b if correct value not in b
              print('A=',a,'B=',b,'C=',c,'D=',d,'E=',e)
      

      Like

    • NigelR 5:03 pm on 20 August 2022 Permalink | Reply

      Lines 35 on above are messy and wrong – the ‘9’ in l. 37 should have been ‘uniqtot’ (which is actually 9, but putting 9 there is cheating!).
      Lines 35 on become:

       bc=[[x,y] for x in [a,b] for y in [b,c] if x+y == uniqtot]
              if not bc:continue
              print('Unique set of values (not necessarily in abcde order) is:',a,b,c,d,e)        
              if b!=[y for x in bc for y in x][0]:a,b=b,a  #swap a and b if correct value not in b
              print('A=',a,'B=',b,'C=',c,'D=',d,'E=',e)
      

      ….

      Like

      • Frits 8:41 pm on 20 August 2022 Permalink | Reply

        Hi Nigel,

        You didn’t put code to swap c and d (if needed).

        I took the liberty of rewriting part of your code and format it according the PEP 8 style (except using indentation of two spaces). The Wing Python IDE has an option to reformat the code to PEP 8.

           
        def ptots():
           return [a+b, a+c, a+d, a+e, b+c, b+d, b+e, c+d, c+e, d+e]
        
        # values within pairs might be other way round (ie b,a not a,b etc.)
        valid = []
        for a in [1, 2, 3]:
          b = 8 - a 
          for c in range(b + 1, 9):
            d = 18 - c
            for e in range(c + 1, d):  # choose e between c and d
              if len(set(ptots())) != 10: continue
              # we already know that the lowest total is 8 and second highest is 18
              valid.append([a, b, c, d, e])
        
        # now look for unique pair total between 8 and 18 in 'valid' 
        x = []
        for a, b, c, d, e in valid:
          x += ptots()
            
        # dictionary with count of possible pair totals across all valid values
        totcount = {y: x.count(y) for y in set(x) if y > 8 and y < 18}
        # is there a pair total that occurs only once in all valid sets
        # for a, b, c, d, e?
        uniqtot = [x for x in totcount.keys() if totcount[x] == 1] 
        
        if len(uniqtot) != 1: 
          print('Unique solution not found')
        else:
          uniqtot = uniqtot[0]
          print('Unique pair total is:', uniqtot)
          for a, b, c, d, e in valid:
            
            if uniqtot not in {a + c, a + d, b + c, b + d}: continue
            print('Unique set of values (not necessarily in abcde order) is:', 
                   a, b, c, d, e)        
            
            for betty in [a, b]:
              cathy = uniqtot - betty
              if cathy not in {c, d}: continue
              print(f"A= {8 - betty} B= {betty} C= {cathy} D= {18 - cathy} E= {e}")
        

        Like

    • Frits 7:27 pm on 20 August 2022 Permalink | Reply

      I totally forgot the teaser last night.

       
      from itertools import combinations
      
      # Emily has the second highest number of sweets.
      # Everyone has a different numbers of sweets (otherwise duplicate totals).
      # We temporarily assume a < b < c < e < d
      # b - a  must be different from d - c (otherwise duplicate totals)
      # which leads to: c may not be equal to a + 5
      
      d_missing = dict()         # count in how many solutions a total is missing
      sols = []
      # dictionary: a --> c values 
      a_c = {a: [x for x in range(6, 9) if x not in {a + 5, 8 - a}] 
                for a in range(1, 4)}
      
      for a in a_c:
        for c in a_c[a]:
          for e in range(7, 12):
            combis = [x + y for x, y in combinations([a, 8 - a, c, 18 - c, e], 2)]
            # 10 different combinations
            if len(set(combis)) != 10: continue
            # between 8 and 18 exactly two different totals must be missing
            missing = [x for x in range(9, 18) if x not in combis]
            if len(missing) != 2: continue
            for m in missing:
              d_missing[m] = d_missing.get(m, 0) + 1
      
            sols.append([missing, [a, 8 - a, c, 18 - c, e]])
       
      # "the other total I remember was Betty and Cathy's"
      for bc, v in d_missing.items():
        # check if a total is missing for all solutions but one ...
        if v != len(sols) - 1: continue
        # ... and find this specific solution 
        for m, (a, b, c, d, e) in sols:
          if bc in m: continue
          # we don't know which number a, b is Abby or Betty or 
          # which number c, d is Cathy or Dolly
      
          # make total <bc> out of the sum of (a or b) and (c or d)
          for betty in [a, b]:
            cathy = bc - betty
            if cathy in {c, d}:
              print("answer:", [8 - betty, betty, cathy, 18 - cathy, e])
      

      Like

    • NigelR 9:40 pm on 20 August 2022 Permalink | Reply

      Hi Frits. Thank you for taking the time to unpick my scruffy code and come up with an improvement that is so much more elegant! I had thought about the C/D swap but concluded that, by the time we get to considering B&C, C must be <D, which is implicit in the generator.

      Like

  • Jim Randell 7:35 am on 9 August 2022 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2733: Letter-writing 

    From The Sunday Times, 8th February 2015 [link] [link]

    Last year I went to calligraphy lessons. They were held weekly, on the same day each week, for nine consecutive months. Actually I only went to 15 of the lessons, and after the course was over I listed the dates of those lessons that I had attended. In order to practise my new skills I wrote the dates in words (in the format “First of January” etc.) and I found to my surprise that each date used a different number of letters.

    What were the dates of the first and last lessons that I attended?

    [teaser2733]

     
    • Jim Randell 7:36 am on 9 August 2022 Permalink | Reply

      See also: Teaser 2832.

      The lessons were for “9 months”, so let’s suppose there were 39 weekly lessons, of which the setter attended 15.

      This Python program runs in 68ms.

      Run: [ @replit ]

      from datetime import (date, timedelta)
      from enigma import (repeat, trim, int2words, group, subsets, cache, sprintf as f)
      
      # map month numbers to English names
      month = dict(enumerate([
          'january', 'february', 'march', 'april', 'may', 'june',
          'july', 'august', 'september', 'october', 'november', 'december',
        ], start=1)
      )
      
      # ordinals that aren't cardinal + "th", or cardinal - "y" + "ieth"
      _ordinal = {
        1: 'first', 2: 'second', 3: 'third', 5: 'fifth',
        8: 'eighth', 9: 'ninth', 12: 'twelfth',
      }
      
      # return the ordinal of a number
      @cache
      def ordinal(n):
        if n in _ordinal: return _ordinal[n]
        if n < 20: return int2words(n) + 'th'
        (t, r) = divmod(n, 10)
        if r == 0: return trim(int2words(n), tail=1) + 'ieth'
        return int2words(n - r) + ' ' + ordinal(r)
      
      # return the length of the inscription for a date
      @cache
      def inscribe(d):
        t = f("{d} of {m}", d=ordinal(d.day), m=month[d.month])
        return sum(x.isalpha() for x in t)
      
      # generate length <k> sequences of possible dates
      def generate(k):
        (i1, i7) = (timedelta(days=1), timedelta(days=7))
        d = date(2014, 1, 1)
        while True:
          # generate 39 weeks of dates
          ds = list(repeat((lambda d: d + i7), d, k))
          # are we done?
          if ds[-1].year > 2014: break
          yield ds
          # increase start date
          d += i1
      
      # record possible date spans
      rs = set()
      
      # consider possible dates for 39 weekly lessons
      for ds in generate(39):
        # group dates by letter count
        g = group(ds, by=(lambda d: inscribe(d)))
        # choose 15 letter counts
        for ks in subsets(g.keys(), size=15):
          # find earliest and latest possible dates
          dmin = min(min(g[k] for k in ks))
          dmax = max(max(g[k] for k in ks))
          rs.add((dmin, dmax))
      
      # output solution(s)
      for (dmin, dmax) in rs:
        print(f("{dmin} -> {dmax}"))
      

      Solution: The first lesson attended was on the 5th April. The final lesson attended was on 27th December.


      In fact there is only one sequence of 39 weekly dates in 2014 that gives at least 15 different lengths:

      10 letters: “Third of May”; “Tenth of May”
      11 letters: “Fifth of July”
      12 letters: “Fifth of April”
      13 letters: “Seventh of June”; “Twelfth of July”; “Ninth of August”
      14 letters: “Twelfth of April”; “Second of August”
      15 letters: “Fourth of October”; “First of November”; “Sixth of December”
      16 letters: “Seventeenth of May”; “Thirty first of May”; “Fourteenth of June”; “Nineteenth of July”; “Sixth of September”; “Eighth of November”
      17 letters: “Nineteenth of April”; “Twenty fourth of May”; “Twenty first of June”; “Twenty sixth of July”; “Sixteenth of August”; “Thirtieth of August”; “Eleventh of October”
      18 letters: “Twenty eighth of June”
      19 letters: “Twenty third of August”; “Eighteenth of October”; “Fifteenth of November”; “Twentieth of December”
      20 letters: “Twentieth of September”; “Twenty fifth of October”; “Thirteenth of December”
      21 letters: “Thirteenth of September”; “Twenty ninth of November”
      22 letters: “Twenty second of November”
      23 letters: “Twenty seventh of December”
      24 letters: “Twenty seventh of September”

      And this gives exactly 15 different lengths of inscription. So, each length must be represented by a single date that the setter attended.

      The period covered is 5th April – 27th December, and as 5th April is the only date with an inscription of 12 letters, and 27th December is the only date with an inscription of 23 letters, the setter must have attended the actual first and last lessons, and these give the answer to the puzzle.

      Like

  • Jim Randell 7:58 am on 2 August 2022 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2534: Fiftieth anniversary 

    From The Sunday Times, 17th April 2011 [link] [link]

    We have recently celebrated the 50th anniversary of the Teaser column. At the party for the setters they gave each letter of the alphabet a different number from 1 to 26 (e.g. they made A = 7). Appropriately, this was done in such a way that, for each setter present, the values of the letters of their surname added up to 50. Angela Newing was there (so N+E+W+I+N+G = 50), as were Nick MacKinnon and Hugh Bradley. Only two of Graham Smithers, Danny Roth, Andrew Skidmore, John Owen and Victor Bryant could make it.

    Which two?

    [teaser2533]

     
    • Jim Randell 7:59 am on 2 August 2022 Permalink | Reply

      (See also: Teaser 2884).

      With a bit of analysis we can determine the required answer, and write a program to give us a viable assignment is a reasonable amount of time.

      We are given:

      A = 7
      NEWING = 50
      MACKINNON = 50
      BRADLEY = 50

      Hence:

      3N + CIKMO = 43
      BDELRY = 43
      ⇒ 3N + BCDEIKLMORY = 86

      And BCDEIKLMORY (11 letters) must be at least 71, so:

      3N ≤ 15
      N ≤ 5

      But if N is in (1, 2, 3, 4, 5), the minimal value of BCDEIKLMORY is increased to 83, so:

      3N ≤ 3
      N = 1
      BCDEIKLMORY = 83

      So the letters BCDEIKLMORY are assigned (2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13) (in some order).

      Now, all values from 1 – 13 are accounted for, leaving GHSTW to be assigned values from 14 – 26.

      SMITHERS = 2S + TH + EIMR ≥ 73

      So SMITHERS cannot be 50.

      SKIDMORE = S + IKMO + EDR = S + (40 – C) + (43 – BLY) ≥ 51

      So SKIDMORE cannot be 50.

      OWEN = 50 ⇒ O = ING = IG + 1

      But O must have a value ≤ 13 and G must have a value ≥ 14.

      So OWEN cannot be 50.

      Hence the only remaining candidates are ROTH and BRYANT.

      All that remains is to find a viable assignment of letters to values to show the puzzle has a solution.

      And we can use the [[ SubstitutedExpression ]] solver from the enigma.py library to do that.

      The following run file executes in 66ms. (The internal run time of the generated program is 48µs).

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      SubstitutedExpression
      
      --base="27"
      --digits="1-26"
      
      # fixed values
      --assign="A,7"
      --assign="N,1"
      
      # limits on other values
      --invalid="1|2|3|4|5|6|7|8|9|10|11|12|13,GHSTW"
      --invalid="14|15|16|17|18|19|20|21|22|23|24|25|26,BCDEIKLMORY"
      
      # these sum to 50
      "N + E + W + I + N + G == 50"
      "M + A + C + K + I + N + N + O + N == 50"
      "B + R + A + D + L + E + Y == 50"
      "R + O + T + H == 50"
      "B + R + Y + A + N + T == 50"
      
      # these don't
      "S + M + I + T + H + E + R + S != 50"
      "S + K + I + D + M + O + R + E != 50"
      "O + W + E + N != 50"
      
      --template=""
      --first  # we only need a single solution
      

      Solution: The other two setters were: Danny ROTH and Victor BRYANT.


      Here is one possible assignment found by the run file:

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

      Using these values we get:

      NEWING = 1 + 3 + 14 + 5 + 1 + 26 = 50
      MACKINNON = 8 + 7 + 12 + 13 + 5 + 1 + 1 + 2 + 1 = 50
      BRADLEY = 9 + 6 + 7 + 4 + 11 + 3 + 10 = 50
      ROTH = 6 + 2 + 17 + 25 = 50
      BRYANT = 9 + 6 + 10 + 7 + 1 + 17 = 50

      SMITHERS = 15 + 8 + 5 + 17 + 25 + 3 + 6 + 15 = 94
      SKIDMORE = 15 + 13 + 5 + 4 + 8 + 2 + 6 + 3 = 56
      OWEN = 2 + 14 + 3 + 1 = 20

      Without the [[ --first ]] parameter we find there are 33,182,352 possible assignments.

      Like

    • GeoffR 9:59 am on 2 August 2022 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..26:A;   var 1..26:B;   var 1..26:C;   var 1..26:D;
      var 1..26:E;   var 1..26:F;   var 1..26:G;   var 1..26:H;   
      var 1..26:I;   var 1..26:J;   var 1..26:K;   var 1..26:L;
      var 1..26:M;   var 1..26:N;   var 1..26: O;  var 1..26:P;   
      var 1..26:Q;   var 1..26:R;   var 1..26:S;   var 1..26:T;   
      var 1..26:U;   var 1..26:V;   var 1..26:W;   var 1..26:X;   
      var 1..26:Y;   var 1..26:Z;
      
      constraint all_different ([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,
      P,Q,R,S,T,U,V,W,X,Y,Z]);
      
      constraint A == 7;
      
      % Letters of following names sum to 50
      constraint N+E+W+I+N+G = 50;
      constraint M+A+C+K+I+N+N+O+N == 50;
      constraint B+R+A+D+L+E+Y == 50;
      
      % Letters of only two of Smithers, Roth, Skidmore,
      % Owen and Bryant, sum to 50
      constraint sum([ S+M+I+T+H+E+R+S == 50, R+O+T+H == 50,
      S+K+I+D+M+O+R+E == 50, O+W+E+N == 50, B+R+Y+A+N+T == 50]) == 2;
      
      solve satisfy;
      
      output [ "SMITHERS = " ++ show(S+M+I+T+H+E+R+S) ++ "\n"
      ++ "ROTH = " ++ show(R+O+T+H) ++ "\n"
      ++ "SKIDMORE = " ++ show(S+K+I+D+M+O+R+E) ++ "\n"
      ++ "OWEN = " ++ show(O+W+E+N) ++ "\n"
      ++ "BRYANT = " ++ show(B+R+Y+A+N+T) ];
      
      % Typical solution of multiple solutions
      % SMITHERS = 90
      % ROTH = 50  <<<
      % SKIDMORE = 56
      % OWEN = 22
      % BRYANT = 50  <<<
      % ----------
      % Only ROTH and BRYANT sum to 50 for 5 extra names.
      
      

      Like

  • Jim Randell 9:07 am on 21 July 2022 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2533: A lopsided number 

    From The Sunday Times, 10th April 2011 [link] [link]

    In this letters-for-digits substitution puzzle, each letter consistently represents a different digit. In the display, each letter in the top row is the sum of the two letters directly below it:

    What number is LOPSIDED?

    [teaser2533]

     
    • Jim Randell 9:08 am on 21 July 2022 Permalink | Reply

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

      The following run file executes in 64ms. The internal runtime of the generated program is 55µs).

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      SubstitutedExpression
      
      "F + I = P"
      "I + D = O"
      "D + D = S"
      "D + L = E"
      "L + E = R"
      
      --answer="LOPSIDED"
      

      Solution: LOPSIDED = 24961353.

      And: POSER = 94657; FIDDLE = 813325.

      Like

    • GeoffR 11:38 am on 21 July 2022 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
       
      var 1..9:P; var 1..9:O; var 1..9:S; var 1..9:E; var 1..9:R;
      var 1..9:F; var 1..9:I; var 1..9:D; var 1..9:L; 
      
      constraint all_different([P, O, S, E, R, F, I, D, L]);
      
      constraint F + I == P /\ I + D == O /\ D + D == S
      /\ D + L == E /\ L + E == R;
      
      solve satisfy;
      
      output ["LOPSIDED = \(L)\(O)\(P)\(S)\(I)\(D)\(E)\(D)"];
      
      % LOPSIDED = 24961353
      % ----------
      % ==========
      
      
      

      Like

  • Jim Randell 9:01 am on 14 July 2022 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2532: In hot pursuit 

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

    George and Martha are jogging around a circular track. Martha starts at the most westerly point, George starts at the most southerly point, and they both jog clockwise at their own steady speeds. After a short while Martha is due north of George for the first time. Five minutes later she is due south of him for the first time. Then George catches up with her during their second laps at the most northeasterly point of the track.

    What is Martha’s speed (in degrees turned per minute)?

    [teaser2532]

     
    • Jim Randell 9:02 am on 14 July 2022 Permalink | Reply

      If George starts at 0° and goes at g degrees per minute, and Martha starts at 90° and goes at m degrees per minute.

      Then at time x (shortly after they set off) M is due north of G. So the angle G has gone is the same angular distance that M has to go to reach the north (180°) marker.

      So we have:

      xg = 90° − xm
      x(g + m) = 90°

      And 5 minutes later M is due south of G for the first time. The distance G has gone beyond the north (180°) marker is the same as the distance that M has to go to reach the south (360°/0°) marker.

      (x + 5)g − 180° = 270° − (x + 5)m
      (x + 5)(g + m) = 450°

      5x = x + 5
      4x = 5
      x = 5/4
      g + m = 72°/min

      Later, at some time t during lap 2, G catches up with M at the north-east (225°) marker. So G has gone 585° and M has gone 495°.

      Hence:

      585 = tg
      495 = tm

      t(g + m) = 1080
      t = 1080 / 72 = 15 min
      g = 39°/min
      m = 33°/min

      Solution: Martha’s speed is 33°/min.

      Like

  • Jim Randell 7:29 am on 12 July 2022 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2724: Headcount 

    From The Sunday Times, 7th December 2014 [link] [link]

    My grandson and I play a coin game. First we toss seven coins and I have to predict in advance the number of heads whilst he has to predict the number of tails. I then get a number of points equal to the number of heads, he gets a number of points equal to the number of tails, and anyone whose prediction was correct gets a fixed bonus number of points (less than 40). We repeat this with six coins in the second round, then five, and so on down to two. In a recent game we noticed that, after each round, the total of all the points so far awarded was equal to a prime number.

    What is the “fixed bonus” number of points? And what was the total of all the points at the end of the game?

    [teaser2724]

     
    • Jim Randell 7:30 am on 12 July 2022 Permalink | Reply

      (See also: Teaser 3009).

      In a round with n coins the points awarded are, the number of heads (+ bonus if guessed correctly) and the number of tails (+ bonus if guessed correctly). So n points are always awarded, along with 0, 1, or 2 bonuses.

      We don’t need to worry about the points won by each player, just the total number of points gained in each round.

      This Python program keeps a set of (total, bonus) pairs, and then progresses through the rounds keeping viable values.

      It runs in 57ms. (Internal runtime is 664µs).

      Run: [ @replit ]

      from enigma import (irange, is_prime, printf)
      
      # start with a total of 0, and all possible bonus values
      ss = set((0, x) for x in irange(0, 40))
      
      # start with <k> coins
      k = 7
      
      # consider subsequent rounds
      while k > 1:
        ss_ = set()
        # consider (total, bonus) in the previous round
        for (t, b) in ss:
          # consider number of bonuses awarded in this round
          for n in (0, 1, 2):
            t_ = t + k + n * b
            if is_prime(t_):
              ss_.add((t_, b))
        # move on to the next round
        (ss, k) = (ss_, k - 1)
      
      # output solutions
      for (t, b) in ss:
        printf("total = {t}, bonus={b}")
      

      Solution: The number of bonus points is 19. The total number of points at the end of the game is 103.

      The progression of the game is:

      7 coins: total = 7 (0 bonus points)
      6 coins: total = 13 (0 bonus points)
      5 coins: total = 37 (19 bonus points)
      4 coins: total = 79 (38 bonus points)
      3 coins: total = 101 (19 bonus points)
      2 coins: total = 103 (0 bonus points)

      Like

  • Jim Randell 4:40 pm on 1 July 2022 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 3119: Hidden powers 

    From The Sunday Times, 3rd July 2022 [link] [link]

    My grandson is studying “History since the Battle of Hastings”. I made him a game, which consisted of a row of nine cards, each with a different non-zero digit on it. Throw a standard die, note the number of spots displayed, count that number of places along the row and pause there. Throw the die again, move the corresponding number of places further along and pause again. Repeat this until you come off the end of the row, noting the digit or digits you paused on and put these together in the same order, to produce a number.

    Keeping the cards in the same order I asked my grandson to try to produce a square or cube or higher power. He eventually discovered that the lowest possible such number was equal to the number of one of the years that he had been studying.

    What is the order of the nine digits along the row?

    [teaser3119]

     
    • Jim Randell 5:54 pm on 1 July 2022 Permalink | Reply

      It took me a little while to understand how this puzzle is supposed to work.

      And despite my initial misgivings there is only one possible arrangement of digits that can lead to the situation described.

      The following Python program isn’t very quick (it tries all possible arrangements of digits), but it does find the required arrangement.

      The code to generate powers is adapted from Teaser 683 and Enigma 1777.

      It runs in 669ms.

      Run: [ @replit ]

      from enigma import (Primes, nsplit, subsets, irange, tuples, printf)
      
      # generate powers (x^y) in numerical order, x >= 0, y >= 2,
      def powers():
        # powers less than 2^2
        yield 0
        yield 1
        # powers from 2^2 upwards
        base = { 2: 2 }
        power = { 2: 4 }
        maxp = 2
        primes = Primes(35, expandable=1).generate(maxp + 1)
        while True:
          # find the next power
          n = min(power.values())
          yield n
          # what powers are involved
          ps = list(p for (p, v) in power.items() if v == n)
          # increase the powers
          for p in ps:
            base[p] += 1
            power[p] = pow(base[p], p)
          # do we need to add in a new power?
          if maxp in ps:
            maxp = next(primes)
            base[maxp] = 2
            power[maxp] = pow(2, maxp)
      
      # collect candidate powers
      pows = list()
      for n in powers():
        if n > 2022: break
        # split the power into digits
        ds = nsplit(n)
        # no 0 digits, or repeated digits
        if 0 in ds or len(set(ds)) != len(ds): continue
        pows.append((n, ds))
      
      # check powers that can be made with an arrangement of digits
      def play(ss):
        # find powers that can be made
        ns = list()
        for (n, ds) in pows:
          # find indices of the digits
          js = list(ss.index(d) for d in ds)
          # check entry and exit
          if js[0] > 5 or js[-1] < 3: continue
          js.insert(0, -1)
          # and corresponding dice throws
          ts = list(y - x for (x, y) in tuples(js, 2))
          if min(ts) < 1 or max(ts) > 6: continue
          # check the power is permissible
          if n < 1066: return
          ns.append(n)
        # return the list of powers
        return ns
      
      # consider possible arrangements of digits
      for ss in subsets(irange(1, 9), size=len, select="P"):
        ns = play(ss)
        if ns:
          printf("{ss} -> {ns}")
      

      Solution: The order of the digits is: 1, 9, 8, 7, 5, 2, 3, 4, 6.

      And the smallest (and onliest) power which can be made by rolling the die is 1936, with rolls of (1, 1, 5, 2, *).


      Although the puzzle talks about the lowest power that can be generated, it turns out it is the only (non-trivial) power that can be generated with the required arrangement of cards.

      The puzzle will continue to work in the future, until the year 4913 (= 17³) is incorporated into the history book.

      Like

      • Jim Randell 10:13 am on 2 July 2022 Permalink | Reply

        Here’s a faster (but slightly longer) program. Instead of just trying all possible arrangements of digits, it recursively constructs arrangements that cannot give powers less than 1066, and then finds which greater powers can be made.

        It runs in 174ms.

        Run: [ @replit ]

        from enigma import (Primes, nsplit, subsets, tuples, diff, update, printf)
        
        # generate powers (x^y) in numerical order, x >= 0, y >= 2,
        def powers():
          # powers less than 2^2
          yield 0
          yield 1
          # powers from 2^2 upwards
          base = { 2: 2 }
          power = { 2: 4 }
          maxp = 2
          primes = Primes(35, expandable=1).generate(maxp + 1)
          while True:
            # find the next power
            n = min(power.values())
            yield n
            # what powers are involved
            ps = list(p for (p, v) in power.items() if v == n)
            # increase the powers
            for p in ps:
              base[p] += 1
              power[p] = pow(base[p], p)
            # do we need to add in a new power?
            if maxp in ps:
              maxp = next(primes)
              base[maxp] = 2
              power[maxp] = pow(2, maxp)
        
        # collect candidate powers (disallowed and allowed)
        (xpows, pows) = (list(), list())
        for n in powers():
          if n > 2022: break
          # split the power into digits
          ds = nsplit(n)
          # no 0 digits, or repeated digits
          if 0 in ds or len(set(ds)) != len(ds): continue
          (xpows if n < 1066 else pows).append((n, ds))
        
        # check if digit sequence <ds> can be made from arrangement <ns>
        def play(ns, ds):
          # find indices of the digits
          js = list(ns.index(d) for d in ds)
          # check entry and exit
          if js[0] > 5 or js[-1] < 3: return False
          # check corresponding dice throws (1-6)
          js.insert(0, -1)
          return all(0 < y - x < 7 for (x, y) in tuples(js, 2))
        
        # generate arrangements <ns> that don't allow sequences <xs> to be made
        # ns = digit arrangement
        # xs = disallowed sequences
        # ss = allocated digits
        # js = indices of empty slots
        def solve(ns, xs, ss=set(), js=None):
          if not xs:
            yield ns
          else:
            # find the shortest sequences with the fewest missing digits
            fn = lambda ds: (len(set(ds).difference(ss)), len(ds))
            ds = min(xs, key=fn)
            # choose placements for the missing digits
            ms = diff(ds, ss)
            if not js: js = set(j for (j, n) in enumerate(ns) if n is None)
            for ks in subsets(js, size=len(ms), select="P"):
              ns_ = update(ns, ks, ms)
              if not play(ns_, ds):
                # solve the rest
                yield from solve(ns_, xs.difference([ds]), ss.union(ms), js.difference(ks))
        
        # find layouts that do not permit sequences from xpows
        for ns in solve([None] * 9, set(ds for (_, ds) in xpows)):
          # look for permissible powers
          ps = list(n for (n, ds) in pows if play(ns, ds))
          if ps:
            printf("{ns} -> {ps}")
        

        Liked by 1 person

    • Frits 11:28 pm on 1 July 2022 Permalink | Reply

      Reusing my code of Teaser 683 and using Jim’s early performance enhancement (also considering number 1 as a power).

         
      from itertools import permutations
      
      def prime_factors(n):
        i = 2
        factors = []
        while i * i <= n:
          if n % i:
            i = 3 if i == 2 else i + 2
          else:
            n //= i
            factors.append(i)
        if n > 1:
          factors.append(n)
           
        return factors
          
      def is_a_power(n):
        pf = prime_factors(n)
        if len(pf) < 2: 
          return False
           
        # occurences of digits  
        oc = {pf.count(x) for x in set(pf)}
        if mult_gcd(list(oc)) == 1:
          return False
        return True
       
      # calculate greatest common divisor of multiple numbers  
      def mult_gcd(li):
        if len(li) == 1:
          return li[0]
       
        for i in range(len(li) - 1):
          a = li[i]
          b = li[i+1]
          while b:
            (a, b) = (b, a % b)
           
          if a == 1: return a
           
          li[i+1] = a
        return a  
       
      # generate powers, stop if you encounter one less than 1067    
      def solve(k, s, pw=0, ns=[], rs=set()):
        if k > 0:
          # year must be before 2023
          if k == 1 and pw > 202:
            return []
          ls = len(s)
          for i in range(6):
            # check if you come off the end of the row
            if i > ls - 1: break
            p = 10 * pw + s[i]
            if p in pows and ls - i < 7:
              return [p]
            
            # recurse if worthwhile
            if p in powstart:  
              res = solve(k - 1, s[i + 1:], p, ns + [i + 1], rs)  
              if len(res) == 1:
                rs.add(res[0])
                if res[0] < 1067:
                  return []  # no solution
          
          # if we didn't encounter a low power return list of powers
          return list(rs)    
          
      # collect candidate powers
      pows = {i for i in range(1, 2023) if is_a_power(i) and \
              len(s:= str(i)) == len(set(s)) and "0" not in s}  
      
      powstart = {int(str(p)[:i]) for p in pows for i in range(1, 4)}
      
      # consider possible arrangements of digits
      for perm in permutations(range(1, 10)):
        # [performance] single digit powers cannot be in slots 3, 4, 5
        if {1, 4, 8, 9}.intersection(perm[3:6]): continue
      
        r = sorted(solve(4, perm, rs=set()))
        if r and r[0] > 1066:
          print(perm, "number", r[0])
      

      Like

      • Frits 9:29 am on 2 July 2022 Permalink | Reply

        Python 3.9 introduced multiple arguments version of math.gcd so math.gcd() can be used instead of mult_gcd().

        Like

    • Frits 2:50 pm on 2 July 2022 Permalink | Reply

      Just as with Jim ‘s third program only calling solve() for 49 permutations.

      Doing the checks for 2-digit and 3-digit powers in a general way is a bit slower.
      Also storing digit positions in a dictionary to minimize index() calls is a bit slower.

         
      from itertools import permutations
      from math import gcd
      
      def prime_factors(n):
        i = 2
        factors = []
        while i * i <= n:
          if n % i:
            i = 3 if i == 2 else i + 2
          else:
            n //= i
            factors.append(i)
        if n > 1:
          factors.append(n)
           
        return factors
          
      def is_a_power(n):
        pf = prime_factors(n)
        if len(pf) < 2: 
          return False
           
        # occurences of digits  
        oc = {pf.count(x) for x in set(pf)}
        if gcd(*oc) == 1:
          return False
        return True
       
      # generate powers, stop if you encounter one less than 1067    
      def solve(k, s, pw=0, ns=[], rs=set()):
        if k > 0:
          # year must be before 2023
          if k == 1 and pw > 202:
            return []
          ls = len(s)
          for i in range(6):
            # check if you come off the end of the row
            if i > ls - 1: break
            p = 10 * pw + s[i]
            if p in pows and ls - i < 7:
              return [p]
            
            # recurse if worthwhile
            if p in powstart:  
              res = solve(k - 1, s[i + 1:], p, ns + [i + 1], rs)  
              if len(res) == 1:
                rs.add(res[0])
                if res[0] < 1067:
                  return []  # no solution
          
          # if we didn't encounter a low power return list of powers
          return list(rs)    
          
      # collect candidate powers
      pows = {i for i in range(1, 2023) if is_a_power(i) and \
              len(s:= str(i)) == len(set(s)) and "0" not in s}  
      
      powstart = {int(str(p)[:i]) for p in pows for i in range(1, 4)}
      
      # 2-digit powers
      pows2 = [(x // 10, x % 10) for x in pows if 9 < x < 100]
      
      # 3-digit powers
      pows3 = [(x // 100, (x // 10) % 10, x % 10) for x in pows if 99 < x < 1000]
      
      # consider possible arrangements of digits
      for perm in permutations(range(1, 10)):
        # [performance] single digit powers cannot be in slots 3, 4, 5
        if {1, 4, 8, 9}.intersection(perm[3:6]): continue
        
        # check 2-digit powers
        for a, b in pows2:
          posa = perm.index(a)
          posb = perm.index(b)
          # can we make the power in 2 jumps and then come off the end of the row?
          if 0 < (posb - posa) < 7 and posa < 6 and posb > 2:
            break
        else:  # no break   
          # check 3-digit powers
          for a, b, c in pows3:
            posa = perm.index(a)
            posb = perm.index(b)
            posc = perm.index(c)
            # can we make the power in 3 jumps and 
            # then come off the end of the row?
            if not (0 < (posb - posa) < 7 and 0 < (posc - posb) < 7): continue
            if posa < 6 or posc > 2:
              break    
          else:  # no break   
            # no 2- or 3-digit power can be formed
            r = sorted(solve(4, perm, rs=set()))
            if r and r[0] > 1066:
              print(perm, "number", r[0])
      

      Like

    • Frits 4:04 pm on 2 July 2022 Permalink | Reply

      Without recursion.

         
      from itertools import permutations
      from enigma import mgcd
      
      def prime_factors(n):
        i = 2
        factors = []
        while i * i <= n:
          if n % i:
            i = 3 if i == 2 else i + 2
          else:
            n //= i
            factors.append(i)
        if n > 1:
          factors.append(n)
           
        return factors
          
      def is_a_power(n):
        pf = prime_factors(n)
        if len(pf) < 2: 
          return False
           
        # occurences of digits  
        oc = {pf.count(x) for x in set(pf)}
        if mgcd(*oc) == 1:
          return False
        return True
       
      # collect candidate powers
      pows = {i for i in range(1, 2023) if is_a_power(i) and \
              len(s:= str(i)) == len(set(s)) and "0" not in s}  
      
      # powers grouped by number of digits
      pws = [[[int(x) for x in str(p)] for p in pows 
               if 10**i <= p < 10**(i + 1)] for i in range(1, 4)]
      
      # do powers exists >= 2000 ?
      exists2xxx = any(x for x in pws[2] if x[0] == 2)
      
      # consider possible arrangements of digits
      for perm in permutations(range(1, 10)):
        # [performance] single digit powers cannot be in slots 3, 4, 5
        if {1, 4, 8, 9}.intersection(perm[3:6]): continue
        
        for ps in pws[:-1]:
          for p in ps:
            pos = [perm.index(i) for i in p]
            # first digit reachable and then come off the end of the row?
            if not(pos[0] < 6 and pos[-1] > 2): continue
            # can we make the power in <len(pos)> jumps ...
            if any(y - x not in {1, 2, 3, 4, 5, 6} for x, y in zip(pos, pos[1:])):
              continue
              
            # we have found a valid 2- or 3-digit power
            break
          else: # no break  
            continue
            
          break   # break if break occurred    
        else:  # no break
          if not exists2xxx:
            # check position of 1
            if perm.index(1) > 5: continue
          
          # check 4-digit powers
          for p in sorted(pws[2]):
            pos = [perm.index(i) for i in p]
            # it is enough to only check for increasing numbers
            if pos != sorted(pos): continue
            
            print(perm, "number", "".join(str(x) for x in p))
            break
      

      Like

    • Frits 5:48 pm on 8 July 2022 Permalink | Reply

         
      from itertools import permutations
      from functools import reduce
      from math import gcd
      
      def prime_factors(n):
        i = 2
        factors = []
        while i * i <= n:
          if n % i:
            i = 3 if i == 2 else i + 2
          else:
            n //= i
            factors.append(i)
        if n > 1:
          factors.append(n)
           
        return factors
          
      def is_a_power(n):
        if n == 1: return [1]
        pf = prime_factors(n)
        if len(pf) < 2: 
          return False
           
        # occurences of digits  
        oc = {pf.count(x) for x in set(pf)}
        if gcd(*oc) == 1:
          return False
        return True
      
      # group type
      gtype = lambda i: "first" if i == 0 else "middle" if i == 1 else "last"
              
      # collect all candidate powers
      pows = {i for i in range(1, 2023) if is_a_power(i) and 
              len(s:= str(i)) == len(set(s)) and "0" not in s} 
      
      # powers grouped by number of digits
      pws = [set(str(p) for p in pows 
               if 10**i <= p < 10**(i + 1)) for i in range(4)]
               
      # return possible arrangements of digits in group <grp> for 2-digit powers
      def arrangements(grp):
        return [p for p in permutations(grp) if all(fdgt + sdgt not in pws[1] 
                for fdgt, sdgt in [(p[0], p[1]), (p[0], p[2]), (p[1], p[2])])
               ]
      
      # return all numbers per group that don't occur in other groups
      def calc_known(grp):
        return [[x for x in grp[i] 
                if all(x not in t for t in 
                      [y for j, y in enumerate(grp) if j != i])] 
                for i in range(3)]
       
      # for all combinations in <lst> check if a 3-digit power can be made
      # with a digit in the last group
      def check_last_group(grp, lst):
        forbidden = [set() for _ in range(len(lst))]
        for i, n in enumerate(lst):
          # for all combinations in <lst> 
          for x in [(n[0] + n[1]), (n[0] + n[2]), (n[1] + n[2])]:
            for p in pws[2]:
              if x in {p[:-1]}:
                # x + p[-1] is 3-digit power so p[-1] is forbidden in last group
                forbidden[i].add(p[-1])
              
        # return numbers in the last group which are forbidden for all <lst> entries
        return reduce((lambda x, y: x & y), map(set, forbidden))
      
      # maintain groups if all numbers in a group are known
      def maintain_groups(grp, fixed):
        for i, fix in enumerate(fixed):
          # all numbers in a group are known?
          if len(fix) == 3:
            # remove other numbers from this group
            for n in [x for x in grp[i] if x not in fix]:
              print(f"{gtype(i)} group must be {','.join(fix)}:"
                    f" remove {n} from {gtype(i)} group")
            grp[i] = set(fix)
                  
      def print_groups(g):
        print("----- groups:", ",".join(sorted(g[0])), "--", 
                               ",".join(sorted(g[1])), "--", 
                               ",".join(sorted(g[2])), "-----")
      
      # maintain and print groups  
      def update(g):
        known = calc_known(g)
        maintain_groups(g, known)
        print_groups(g)
        return known
      
      
      print("-------- START -----------")
      
      print("split the nine digits in three groups of three digits")
      # list <g> contains candidate digits for each group
      g = [set("123456789"), set("123456789"), set("123456789")]
      print_groups(g)
      
      print(f"removing 1 from last group"
            f" as we need a 4-digit power 1xxx as an answer")
      g[2] -= {'1'}             # we need a 4-digit power
      
      print("removing", ", ".join(sorted(pws[0])), 
            "from middle group to prevent single digit powers")
      g[1] -= set(pws[0])       
      
      for x in calc_known(g)[0]:
        # can we can make a 2-digit power with <x>?
        for p in [p2 for p2 in pws[1] if p2[0] == x]:
          print("removing", p[1], "from middle group to prevent power", p)
          g[1].remove(p[1])         
      
      print_groups(g)
      
      # check middle group
      if len(g[1]) == 4:
        # see what happens if we remove <m> from middle group 
        for m in g[1]:
          middle = [x for x in g[1] if x != m]
          for m2 in middle:
            # if combination is a 2-digit power <m> must occur in middle group
            if m2 + m in pws[1]: 
              g[2] -= {m}
            if m + m2 in pws[1]: 
              g[0] -= {m}
         
          # get arrangements from <middle> without a 2-digit power
          lst = arrangements(middle)
          
          if len(lst) == 1:
            # we have only one arrangement for slots 3, 4 and 5 
            # can we can make a 3-digit power with this arrangement?
            arr = lst[0]
            for a in [(arr[0] + arr[1]), (arr[0] + arr[2]), (arr[1] + arr[2])]:
              # 3-digit powers that can be made from <a>
              tdp = [p3 for p3 in pws[2] if a in p3[:-1]]
              for p in tdp:
                # last digit of 3-digit power may not be used yet
                if p[-1] in (arr + ('1', )): continue
                # removing m has lead to a valid 3-digit power 
                print(f"removing {m} from the middle group can lead to"
                      f" power {p}, remove {m} from first and last group")
                g[0] -= {m}
                g[2] -= {m}
               
        # maintain and print groups
        known = update(g)
        
        # for every 3-digit power check if two of it's digits have to occur in two 
        # groups, if so we can remove the other digit from the other group
        first = 1
        for p in pws[2]:
          unknown = [i for i in range(3) if p[i] not in known[i]]  
          if len(unknown) != 1: continue
          
          i = unknown[0]
          if first: 
            print("known digits per group:", known)
            first = 0
          
          print(f"digits {' and '.join(p[j] for j in range(3) if j != i)}"
                f" of power {p} each have to occur in a different specific group:"
                f" remove {p[i]} from {gtype(i)} group")
          g[i] -= {p[i]}
        
        update(g)
        
        # get numbers in the last group which make a 3-digit power for all
        # valid combinations in the middle group
        for s in check_last_group(g, arrangements(g[1])):
          print(f"all valid combinations of middle group combined with the number"
                f" {s} lead to 3-digit power: remove {s} from last group")
          g[2] -= {s}
               
        update(g)
        print()
        
        # consider possible arrangements of digits
        for p0 in permutations(g[0]):
          for p1 in arrangements(g[1]):
            for p2 in permutations(g[2]):
              perm = p0 + p1 + p2
              # check 2-digit and 3-digit powers
              for ps in pws[1:-1]:
                for p in ps:
                  # the index positions of its digits in the row of cards
                  pos = [perm.index(i) for i in p]
                  # ensure that its first digit is reachable and that its
                  # last digit can be the final digit (with a throw of six)
                  if not(pos[0] < 6 and pos[-1] > 2): 
                    continue
                  # can we make the power in intervals of  1 - 6 jumps?
                  if any(y - x not in set(range(1, 7))
                        for x, y in zip(pos, pos[1:])):
                    continue
      
                  # we have found a valid 2-digit or 3-digit power
                  break
                else: 
                  continue
      
                break   # break again if break occurred    
              else:  
                # check 4-digit powers
                for p in sorted(pws[3]):
                  pos = [perm.index(i) for i in p]
                  
                  # checking for the correct digit order is sufficient because
                  # the highest gap between digits is five empty slots
                  if pos != sorted(pos): continue
                  
                  print(perm, "number", p)
                  break  # only print the lowest 4-digit power
      

      Like

  • Jim Randell 4:33 pm on 29 April 2022 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 3110: Many a slip 

    From The Sunday Times, 1st May 2022 [link] [link]

    I have written down three 3-figure numbers in decreasing order and added them up to give their 4-figure sum, which is a perfect square: the digit 0 occurred nowhere in my sum.

    Now I have attempted to replace digits consistently by letters and I have written the sum as:

    CUP + AND + LIP = SLIP

    However, there’s “many a slip twixt cup and lip” and unfortunately one of those thirteen letters is incorrect. If you knew which letter was incorrect then you should be able to work out the three 3-figure numbers.

    What are they?

    [teaser3110]

     
    • Jim Randell 5:15 pm on 29 April 2022 Permalink | Reply

      I used a variation on the bungled_sum() function we have used before in other puzzles (see: Puzzle 56, Teaser 2952).

      When the setter transcribed the sum to an alphametic there are two ways a mistake could be made. Firstly a symbol could be assigned to more than one digit. And secondly a digit could be assigned to more than one symbol (assuming the setter is aiming for each letter standing for a different digit – although this is not explicitly stated in the puzzle text)).

      We consider each symbol in the alphametic sum in turn, and replace it by a “wild card” symbol to create a modified sum. If the puzzle created with this modified sum has a single solution then we have found the answer to the original puzzle.

      The following Python program runs in 276ms.

      Run: [ @replit ]

      from enigma import SubstitutedExpression, irange, union, update, singleton, join, printf
      
      # the terms in the alphametic sum
      terms = ['CUP', 'AND', 'LIP', 'SLIP']
      
      # we use X to denote the bungled letter
      assert 'X' not in union(terms)
      
      # solve the alphametic sum and return the values of the terms
      def solve(terms, i, j):
        # create terms for the modified sum
        ts = update(terms, [(i, update(t, [(j, 'X')]))])
        # split the terms into the summands and the result
        ss = list("{" + x + "}" for x in ts)
        r = ss.pop(-1)
        # make the expressions
        exprs = [
          # the sum
          join(ss, sep=" + ") + " = " + r,
          # summands are in descending order
          join(ss, sep=" > "),
          # result is a square
          "is_square_p(" + r + ")",
        ]
        # distinct symbols
        syms = union(ts).difference("X")
        distinct = [ join(syms) ]
        # is the replaced symbol still present in the modified sum?
        x = terms[i][j] # replaced symbol
        if x in syms:
          # X must be different from the replaced symbol
          distinct.append('X' + x)
        else:
          # X must be the same as one of the other symbols
          exprs.append("{X} in {{" + join(syms, sep="}, {") + "}}")
        # create the modified puzzle (digits used are 1-9)
        p = SubstitutedExpression(exprs, digits=irange(1, 9), distinct=distinct, verbose=0)
        # find solutions
        for s in p.solve():
          # return the values of the terms
          yield tuple(int(p.substitute(s, t)) for t in ts)
      
      # consider the suspect term
      for (i, t) in enumerate(terms):
        # and the suspect symbol in the term
        for (j, x) in enumerate(t):
          # is there a unique solution to a modified puzzle?
          vs = singleton(solve(terms, i, j))
          if vs is None: continue
          # return: bungled symbol (term, index) and the values of the terms
          printf("term {i} [{t}], index {j} -> {vs}")
      

      Solution: The numbers are: 826, 574, 536.

      So we have:

      826 + 574 + 536 = 1936 (= 44²)

      Which when substituted as:

      CUP + AND + LIP = SLIP

      Makes the A and the first L map to 5, and the second L maps to 9.

      This corresponds to a single mistake in transcribing the 5 in 536 to L, when it should be mapped to A. (i.e. a correct transcription is: CUP + AND + AIP = SLIP).

      And this is the only sum that correspond to a mistake at the 1st digit of the 3rd summand (i.e. the L of LIP).


      The other potential sums, which are discounted as there is more than one sum corresponding to a mistake at the same position, are:

      522 + 478 + 369 = 1369 (= 37²)
      572 + 428 + 369 = 1369 (= 37²)

      These two sums correspond to mistakes in transcribing the 3rd digit of the 1st summand (i.e. the P of CUP), or the 3rd digit of the 3rd summand (i.e. the P of LIP).

      And (possibly):

      529 + 471 + 369 = 1369 (= 37²)
      579 + 421 + 369 = 1369 (= 37²)

      These two sums correspond to mistakes in transcribing the 3rd digit if the second summand (i.e. the D in AND), or the 1st digit of the result (i.e. the S in SLIP).

      Although if the setter is only attempting to “replace digits consistently by letters”, but not have “each letter standing for a different digit”, then this last scenario would not count as having a mistake in it.

      Like

    • GeoffR 8:19 pm on 29 April 2022 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % Four digit squares list
      set of int: sq4 = {x*x | x in 32..99}; 
      
      % Alternative substituted sum - to compare digits.
      % abc + efg + hij = kmnp
      var 1..9:a; var 1..9:b; var 1..9:c;
      var 1..9:e; var 1..9:f; var 1..9:g;
      var 1..9:h; var 1..9:i; var 1..9:j;
      var 1..9:k; var 1..9:m; var 1..9:n; var 1..9:p;
      
      % letters in original sum [C,U,P,A,N,D,L,I,S]
      var 1..9:C; var 1..9:U; var 1..9:P;
      var 1..9:A; var 1..9:N; var 1..9:D;
      var 1..9:L; var 1..9:I; var 1..9:S;
      
      % Components of the substituted sum
      var 100..999:abc == 100*a + 10*b + c;
      var 100..999:efg == 100*e + 10*f + g;
      var 100..999:hij == 100*h + 10*i + j;
      var 1000..9999:kmnp == 1000*k + 100*m + 10*n + p;
      
      % The substituted sum
      constraint abc + efg + hij = kmnp;
      
      % Three 3-digit numbers are in descending order
      constraint abc > efg /\ efg > hij;
      
      % 4-figure sum is a perfect square:
      constraint kmnp in sq4;
      
      % Substituted sum has 9 correct digits (1..9) from 13 digits
      constraint card({a,b,c,e,f,g,k,m,n,p}) == 9;
      
      % Teaser sum has 8 correct digits (1..9) from 13 digits
      %... since 1 digit is repeated
      constraint card( {C,U,P,A,N,D,L,I,S} ) == 8;
      
      % Teaser Sum: CUP + AND + LIP = SLIP
      %
      % Only 1 letter is repeated in capital letters sum
      % ... so compare letters in original and substituted sums
      constraint sum ([ a != C, b != U, c != P,
                        e != A, f != N, g != D,
                        h != L, i != I, j != P,
                        k != S, m != L, n != I,
                        p != P]) == 1;   
      
      solve satisfy;
      
      output [ show(abc) ++ " + " ++ show(efg) ++ " + " ++ 
      show(hij) ++ " = " ++ show(kmnp) ];
      
      % There was one unique sum from 11 total multiple outputs
      % This unique sum gives the values of CUP, AND and LIP
      
      
      

      Like

  • Jim Randell 7:40 am on 24 March 2022 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2859: Palindromic 

    From The Sunday Times, 9th July 2017 [link]

    I have assigned to each letter of the alphabet a different number from 0 to 25. Therefore, for example, a three-letter word might stand for a number of three, four, five or six digits. In fact all the letters used in PALINDROMIC have even values. Furthermore, the number represented by this word contains no zeros and is indeed palindromic.

    Find the number represented by PIN.

    [teaser2859]

     
    • Jim Randell 7:41 am on 24 March 2022 Permalink | Reply

      The representation of a word is the concatenation of the numbers representing each letter.

      There are only 10 letters present in PALINDROMIC, and there are only 10 even values that don’t contain the digit 0.

      We can use a short program to consider all possible assignments to of values to letters.

      It is not a spectacularly fast approach, but I think in this case the simplicity of the program outweighs the desire for optimisation.

      The following Python program runs in 1.69s.

      Run: [ @replit ]

      from enigma import (irange, subsets, is_palindrome, join, printf)
      
      # collect values
      vs = set(s for s in map(str, irange(2, 24, step=2)) if '0' not in s)
      
      # assign symbols to values
      for (P, A, L, I, N, D, R, O, M, C) in subsets(vs, size=10, select="P"):
        vs = (P, A, L, I, N, D, R, O, M, I, C)
        if is_palindrome(join(vs)):
          fmt = lambda s: join(s, sep=":") + " = " + join(s)
          printf("PALINDROMIC = {s1} [PIN = {s2}]", s1=fmt(vs), s2=fmt((P, I, N)))
      

      Solution: PIN = 24412.

      There are 2 ways to assign the values to the letters:

      PALINDROMIC = 24:6:18:4:12:22:14:8:16:4:2 = 24618412221481642; PIN = 24:4:12 = 24412
      PALINDROMIC = 24:8:16:4:12:22:14:6:18:4:2 = 24816412221461842; PIN = 24:4:12 = 24412

      In the first case we have A:L = 6:18 and O:M = 8:16.

      In the second case we have A:L = 8:16 and O:M = 6:18.

      But both cases give the same value for PIN.

      Like

      • Jim Randell 7:45 am on 24 March 2022 Permalink | Reply

        If we build up the values for the letters starting at the beginning and end of PALINDROMIC we can discard candidates that will not form a palindrome without having to assign the remaining letters.

        Here I have used the [[ SubstitutedExpression ]] solver from the enigma.py to keep things compact.

        Checking values (P, C), (PA, IC), (PAL, MIC) cuts the run time down to 86ms.

        Run: [ @replit ]

        #! python3 -m enigma -r
        
        SubstitutedExpression
        
        --base=26
        --digits="2,4,6,8,12,14,16,18,22,24"
        
        # we only need this
        "is_palindrome(concat(P, A, L, I, N, D, R, O, M, I, C))"
        
        # but these conditions speed things up
        --code="check = lambda x, y: zip_eq(x, reverse(y))"
        "check(concat(P), concat(C))"
        "check(concat(P, A), concat(I, C))"
        "check(concat(P, A, L), concat(M, I, C))"
        
        # answer to the puzzle
        --answer="concat(P, I, N)"
        
        # [optional] tidy up output
        --template=""
        

        Like

  • Jim Randell 4:43 pm on 4 March 2022 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 3102: Jokers 

    From The Sunday Times, 6th March 2022 [link] [link]

    A group of us wanted to play a card game. We had a standard 52-card pack but we needed to deal out a whole pack with each person getting the same number of cards, so I added just enough “jokers” to make this possible. Then I randomly shuffled the enlarged pack (in this shuffled pack there was more than a 50:50 chance that there would be at least two jokers together). Then I dealt the cards out, each of us getting the same number (more than three). There was more than a 50:50 chance that my cards would not include a joker.

    How many of us were there?

    [teaser3102]

     
    • Jim Randell 7:04 pm on 4 March 2022 Permalink | Reply

      I think I’ve got the probability calculations right.

      If there are n numbers and we choose k of them, then there are C(n, k) ways of doing this.

      And if we consider k-tuples of non-adjacent numbers, we can use the following map:

      (n[1], n[2], n[3], …, n[k]) ↔︎ (n[1], n[2] − 1, n[3] − 2, …, n[k] − k + 1)

      to put them into 1-1 correspondence with k tuples from (n − k + 1) numbers.

      So there are C(n − k + 1, k) of them. (See: Enigma 1029).

      So, when we think about n non-joker cards and j jokers, the probability of a non-adjacent shuffle is:

      C((n + j) − j + 1, j) / C(n + j, j) = C(n + 1, j) / C(n + j, j)

      And the probability of a hand of k cards not containing a joker is:

      (n / (n + j)) × ((n − 1) / (n + j − 1)) × … × ((n − k + 1) / (n + j − k + 1))

      The following Python program runs in 52ms.

      Run: [ @replit ]

      from enigma import (Rational, irange, inf, divisors_pairs, multiply, C, printf)
      
      Q = Rational()
      h = Q(1, 2)
      
      def solve(N=52):
        # consider number of jokers added to the pack (at least 2)
        for j in irange(2, inf):
          # total number of cards in the pack
          n = N + j
      
          # probability of adjacent jokers is > 50%
          Pa = 1 - Q(C(N + 1, j), C(n, j))
          if not(Pa > h): continue
      
          # number of players k is a divisor of n
          # number of cards per player = p
          for (k, p) in divisors_pairs(n, every=1):
            if p < 4: break
            if N % k + j != k: continue
      
            # probability of a hand of p cards _not_ having a joker
            Ph = multiply(Q(N - i, n - i) for i in irange(0, p - 1))
            if not(Ph > h): continue
      
            # output solution
            printf("j={j} n={n}; k={k} p={p}; P(adj)={Pa:.3f} P(hand)={Ph:.3f}", Pa=float(Pa), Ph=float(Ph))
            return
      
      solve()
      

      Solution: There were 15 in the group.

      Which required 8 jokers adding to a standard pack, to make 60 cards in total. So each player receives 4 cards in the deal.

      The probability of no 2 jokers being adjacent when the cards are shuffled is:

      C(53, 8) / C(60, 8) = 886322710 / 2558620845 ≈ 34.64%

      So it is more likely that there will be at least one pair of adjacent jokers in the shuffled pack.

      And the probability of an individual hand of 4 cards not including a joker is:

      (52/60) × (51/59) × (50/58) × (49/57) ≈ 55.52%


      I also wrote code to simulate 1 million random trials with 52 non-joker cards and 8 jokers.

      import random
      from enigma import (Record, irange, join, fdiv, printf)
      
      # run N trials
      def run(N):
      
        # 52 non-jokers + 8 jokers
        cards = ('N' * 52) + ('J' * 8)
      
        # t = number of trials
        # a = number of shuffles with adjacent jokers
        # h = number of hands _not_ having a joker
        r = Record(t=0, a=0, h=0)
      
        # run a trial
        def trial(r):
          cs = list(cards)
          # shuffle the cards
          random.shuffle(cs)
          cs = join(cs)
          # collect stats
          r.t += 1
          if 'JJ' in cs: r.a += 1
          if 'J' not in cs[:4]: r.h += 1
      
        # run the trials
        for _ in irange(N):
          trial(r)
      
        # output results
        printf("{r.t} trials: adj = {r.a} ({a:.1%}), hand = {r.h} ({h:.1%})", a=fdiv(r.a, r.t), h=fdiv(r.h, r.t))
      
      # run 1 million trials
      run(1000000)
      

      The output of a typical run is:

      1000000 trials: adj = 654261 (65.4%), hand = 555384 (55.5%)
      

      Which match the calculated probabilities above.

      Like

      • Jim Randell 9:17 am on 5 March 2022 Permalink | Reply

        Using the same probability formulae, it is perhaps a bit neater to start by considering the number of players.

        Run: [ @replit ]

        from enigma import Rational, irange, inf, ediv, C, multiply, printf
        
        Q = Rational()
        h = Q(1, 2)
        
        def solve(N=52):
          # consider number of players k
          for k in irange(3, inf):
            # how many extra jokers do we need? (at least 2)
            j = -N % k
            if j < 2: continue
        
            # n = total number of cards
            # p = number of cards per player
            n = N + j
            p = ediv(n, k)
            if p < 4: continue
        
            # probability of adjacent jokers is > 0.5
            Pa = 1 - Q(C(N + 1, j), C(n, j))
            if not(Pa > h): continue
        
            # probability of a hand of p cards _not_ containing a joker is > 0.5
            Ph = multiply(Q(N - i, n - i) for i in irange(0, p - 1))
            if not(Ph > h): continue
        
            printf("k={k} j={j} n={n} p={p}; P(adj)={Pa:.3f} P(hand)={Ph:.3f}", Pa=float(Pa), Ph=float(Ph))
            yield (k, j, n, p)
          
        # find the first solution
        for _ in solve():
          break
        

        Like

      • Tony Brooke-Taylor 5:01 pm on 7 March 2022 Permalink | Reply

        I am still working through understanding your probability calculations (my problem) but I can confirm that a long-hand calculation of all possible deals produces the same P(adjacent jokers) as in your solution… in about 10 minutes.

        For small numbers of jokers relative to non-jokers, I think you can get away with approximating each pair as an independent sample of two cards from the expanded pack (with replacement). I don’t think this is quicker computationally, but it is easier to get my head around.

        Alternatively, by observing how P(no jokers in my hand) and P(adjacent jokers dealt) change with respect to the number of jokers, one might be able to infer the solution after calculating all possible joker counts that meet the P(no jokers in my hand) condition.

        Like

  • Jim Randell 9:10 am on 10 February 2022 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2872: Appropriate arithmetic 

    From The Sunday Times, 8th October 2017 [link]

    I wrote down three two-figure numbers, one of which was double one of the others. Overall the three numbers used six consecutive digits between them. I then added up the three numbers to give a three-figure sum, and I also multiplied together the three numbers to give a five-figure product. Replacing digits consistently by letters my two answers, appropriately, were ADD and TIMES.

    What were the three original numbers?

    [teaser2872]

     
    • Jim Randell 9:11 am on 10 February 2022 Permalink | Reply

      If we suppose the three numbers are ab, cd, ef, and that 2 × ab = cd then we have:

      ab + cd + ef = ADD
      ab × cd × ef = TIMES

      And we can use the [[ SubstitutedExpression ]] solver from the enigma.py library to solve the alphametic expressions.

      The following run file executes in 59ms (the generated program has an internal runtime of 575µs).

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      SubstitutedExpression
      
      --symbols="ADEIMSTabcdef"
      --distinct="ADEIMST,abcdef"
      --answer="(ab, cd, ef)"
      
      # cd is twice ab
      "2 * ab = cd"
      
      # sum is ADD, product is TIMES
      "ab + cd + ef = ADD"
      "ab * cd * ef = TIMES"
      
      # a, b, c, d, e, f are 6 consecutive digits
      "all(y == x + 1 for (x, y) in tuples(ordered({a}, {b}, {c}, {d}, {e}, {f}), 2))"
      
      # [optional]
      --template="(ab + cd + ef = ADD) (ab * cd * ef = TIMES)"
      --solution
      

      Solution: The three original numbers are: 23, 46, 75.

      Like

      • Frits 1:17 pm on 10 February 2022 Permalink | Reply

        Instead of the all(…) condition you can also use:

        "(s := sorted([{a}, {b}, {c}, {d}, {e}, {f}]))[-1] - s[0] == 5"
        

        or

        "max(s := [{a}, {b}, {c}, {d}, {e}, {f}]) - min(s) == 5"
        

        Like

    • GeoffR 3:07 pm on 10 February 2022 Permalink | Reply

      Using Frits second suggestion proved useful in a MiniZinc solution.

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      % Digits forming three 2-digit numbers ab, cd, ef
      var 1..9:a; var 1..9:b; var 1..9:c; 
      var 1..9:d; var 1..9:e; var 1..9:f;
      
      constraint all_different([a, b, c, d, e, f]);
      
      % The three 2-digit numbers used six consecutive digits between them
      constraint max([a,b,c,d,e,f]) - min([a,b,c,d,e,f]) == 5;
      
      var 10..99:ab == 10*a + b;
      var 10..99:cd == 10*c + d;
      var 10..99:ef == 10*e + f;
      
      constraint cd == 2 * ab; 
      
      % Upper case letters
      var 1..9:A; var 0..9:D; var 1..9:T; var 1..9:I;
      var 0..9:M; var 0..9:E; var 0..9:S;
      constraint all_different([A, D, T, I, M, E, S]);
      
      % Upper case sum and multiplication values
      var 100..999:ADD = 100*A + 11*D;
      var 10000..99999:TIMES = 10000*T + 1000*I + 100*M + 10*E + S;
      
      constraint ab + cd + ef == ADD;
      constraint ab * cd * ef == TIMES;
      
      solve satisfy;
      output ["The three original numbers were " ++ show([ab, cd, ef]) ];
      
      % The three original numbers were [23, 46, 75]
      % ----------
      % ==========
      
      
      

      Like

  • Jim Randell 9:47 am on 25 January 2022 Permalink | Reply
    Tags: by: Victor Bryant   

    Brain-Teaser 904: The six ages 

    From The Sunday Times, 18th November 1979 [link]

    Problems concerning ages have always proved fruitful and entertaining exercises to both mathematicians and non-mathematicians. Trial and error methods, calculators and normal or esoteric mathematical techniques can all be deployed to find the correct solution. The most elegant or the most economical method is naturally the most commendable, but the correct solution, however obtained, is the desideratum.

    Our problem concerns six men whose ages are within the range 21 to 89 and any two of them differ by at least 9. If we take the two digits comprising each of the ages of three of the men, and reverse them, we obtain the ages of the other three men.

    What is more, if we take the sum of the ages of the first group, we find that it equals the sum of the ages of the second group of three.

    Also the sum of the squares of the three ages of the first group equals the sum of the squares of the ages of the second group of three.

    Finally, one of the ages in each group is exactly twice an age in the other group.

    What are the ages of the six men (in increasing order)?

    This puzzle appeared in the first issue of The Sunday Times to be published in nearly a year (after it was hit by industrial action). The previous issue having been published on 26th November 1978 (almost one year earlier).

    [teaser904]

     
    • Jim Randell 9:48 am on 25 January 2022 Permalink | Reply

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

      The following run file executes in 66ms. (The internal run time of the generated program is 2.17ms).

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      # suppose the ages are: AB CD EF; BA DC FE
      
      SubstitutedExpression
      
      --digits="2-8"
      
      # suppose AB CD EF are in order, and AB is the smallest of the 6 ages
      "AB < CD" "CD < EF"
      "AB < BA" "AB < DC" "AB < FE"
      
      # differences are all at least 9
      "all(abs(x - y) > 8 for (x, y) in subsets([AB, CD, EF, BA, DC, FE], size=2))"
      
      # sums of the 2 groups are equal
      "AB + CD + EF == BA + DC + FE"
      
      # sums of the squares of the 2 groups are equal
      "sumsq(AB, CD, EF) == sumsq(BA, DC, FE)"
      
      # in each group one of the ages is twice one of the ages in the other group
      "any(2 * x in {BA, DC, FE} for x in {AB, CD, EF})"
      "any(2 * x in {AB, CD, EF} for x in {BA, DC, FE})"
      
      # answer is the ages in order
      --answer="ordered(AB, CD, EF, BA, DC, FE)"
      
      # [optional]
      --template="(AB CD EF) (BA DC FE)"
      --solution=""
      

      Solution: The ages are: 23, 32, 46, 64, 78, 87.

      The two sets being: (23, 64, 78) and (32, 46, 87).

      Like

      • Jim Randell 12:23 pm on 29 January 2022 Permalink | Reply

        Some observations allow us to write a program that runs even faster.

        Suppose the six ages are (AB, CD, EF) and (BA, DC, FE).

        Each of them is between 21 and 89. So A, C, E are digits from 2-8 (as they are tens digits in the first set), and so are B, D, F (as they are tens digits in the second set).

        And the digits must all be different as the numbers are all at least 9 apart (so we can’t have two numbers with the same tens digit).

        The sums of the two sets are equal:

        AB + CD + EF = BA + DC + FE
        A + C + E = B + D + F

        And the sums of the squares are equal:

        AB² + CD² + EF² = BA² + DC² + FE²
        A² + C² + E² = B² + D² + F²

        So we can start by looking for two disjoint sets of digits from 2-8 with the same “sum of squares” value and also the same sum. (It turns out there is only one such set).

        We can then pair up the digits into two sets of ages, where each set contains an age that is twice one of the ages in the other set.

        This Python program runs in 50ms (with an internal runtime of just 246µs ).

        from enigma import irange, subsets, group, sumsq, unpack, nconcat, tuples, printf
        
        # group sets of 3 digits by the sum of their squares
        d = group(subsets(irange(2, 8), size=3), by=unpack(sumsq))
        
        # look for two disjoint sets with the same sum
        for vs in d.values():
          for (s1, s2) in subsets(vs, size=2):
            if not(sum(s1) == sum(s2) and len(set(s1 + s2)) == 6): continue
        
            # form the numbers
            (A, C, E) = s1
            for (B, D, F) in subsets(s2, size=3, select="P"):
              ns1 = set(map(nconcat, [(A, B), (C, D), (E, F)]))
              ns2 = set(map(nconcat, [(B, A), (D, C), (F, E)]))
        
              # check each set contains an element that is double one of the others
              if not any(2 * x in ns2 for x in ns1): continue
              if not any(2 * x in ns1 for x in ns2): continue
        
              # construct the answer
              ns = sorted(ns1.union(ns2))
              # check no numbers are within 9 of each other
              if any(b - a < 9 for (a, b) in tuples(ns, 2)): continue
        
              printf("{ns} [{ns1} + {ns2}]", ns1=sorted(ns1), ns2=sorted(ns2))
        

        Like

    • GeoffR 3:35 pm on 25 January 2022 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..9:A; var 1..9:B; var 1..9:C; 
      var 1..9:D; var 1..9:E; var 1..9:F;
      
      % Digits for two groups of ages
      constraint all_different([A, B, C, D, E, F]);
      
      % First group
      var 21..89: AB = 10*A + B;
      var 21..89: CD = 10*C + D;
      var 21..89: EF = 10*E + F;
      
      % Second group - ages reverse of 1st group
      var 21..89: BA = 10*B + A;
      var 21..89: DC = 10*D + C;
      var 21..89: FE = 10*F + E;
      
      % Order ages
      constraint BA > AB /\ AB < CD /\ CD < EF
      /\ BA < DC /\ DC < FE; 
      
      % Any two of the ages differ by at least 9
      constraint 
         abs(AB-CD) >=9 /\ abs(AB-EF) >=9 /\ abs(AB-BA) >=9
      /\ abs(AB-DC) >=9 /\ abs(AB-FE) >=9 /\ abs(CD-EF) >=9 
      /\ abs(CD-BA) >=9 /\ abs(CD-DC) >=9 /\ abs(CD-FE) >=9
      /\ abs(EF-BA) >=9 /\ abs(EF-DC) >=9 /\ abs(EF-FE) >=9
      /\ abs(BA-DC) >=9 /\ abs(BA-FE) >=9 /\ abs(DC-FE) >=9;
      
      % Sum of ages of the first group = sum of ages of the second group
      constraint AB + CD + EF == BA + DC + FE;
      
      % Sum of the squares of the three ages of the first group 
      % equals sum of the squares of the three ages of the second group
      constraint AB*AB + CD*CD + EF*EF == BA*BA + DC*DC + FE*FE;
      
      % One of the ages in each group is exactly twice an age in the other group
      %
      % *** This teaser condition was not needed to give the single answer ***
      % Output shows 64 = 2 * 32 and 46 = 2 * 23, which satisfies this condition.
      
      solve satisfy;
      
      output ["1st ages group = " ++ show(AB) ++ ", " ++ show(CD)
       ++  ", " ++ show(EF) ++ "\n"
      ++ "2nd ages group = " ++ show(BA) ++ ", " ++ show(DC) 
      ++ ", " ++ show(FE) ];
      
      % 1st ages group = 23, 64, 78
      % 2nd ages group = 32, 46, 87
      % ----------
      % ==========
      % Sorted ages:  23, 32, 46, 64, 78, 87
      
      

      Like

      • Jim Randell 4:43 pm on 25 January 2022 Permalink | Reply

        @GeoffR:

        Without the “in each group one of the ages is twice one of the ages in the other group” condition there is a further solution:

        (28, 64, 73) and (82, 46, 37)

        So it is needed.

        Like

    • GeoffR 5:41 pm on 25 January 2022 Permalink | Reply

      @Jim: OK. I see you got a 2nd solution, justifying the constraint.

      For me, MinZinc only came up with the single solution, even though I had set multiple output configuration to 5 solutions.

      On the Configuration Menu, I tried both unchecking and checking the check-box with the heading “Stop after this many solutions(uncheck for all). I am using the MiniZinc IDE under Windows 10.

      Like

      • Jim Randell 9:46 pm on 25 January 2022 Permalink | Reply

        @GeoffR:

        The problem is your ordering constraint is over specified.

        Try:

        constraint AB < CD /\ CD < EF /\ AB < BA /\ AB < DC /\ AB < FE; 
        

        Like

    • GeoffR 10:48 am on 26 January 2022 Permalink | Reply

      @Jim: Thanks, that solved my ordering constraint issue.

      I used your suggested ordering constraint in my code and got the two solutions. It then needs the “in each group one of the ages is twice one of the ages in the other group” constraint to get the single answer.

      Like

    • GeoffR 11:22 am on 26 January 2022 Permalink | Reply

      % A Solution in MiniZinc - revised programme
      include "globals.mzn";
      
      var 1..9:A; var 1..9:B; var 1..9:C; 
      var 1..9:D; var 1..9:E; var 1..9:F;
      
      % Digits for two groups of ages are different
      constraint all_different([A, B, C, D, E, F]);
      
      % First group
      var 21..89: AB = 10*A + B;
      var 21..89: CD = 10*C + D;
      var 21..89: EF = 10*E + F;
      
      % Second group - ages reverse of 1st group
      var 21..89: BA = 10*B + A;
      var 21..89: DC = 10*D + C;
      var 21..89: FE = 10*F + E;
      
      % Revised ordering constraint (Jim)
      constraint AB < CD /\ CD < EF /\ AB < BA /\ AB < DC /\ AB < FE; 
      
      % Any two of the ages differ by at least 9
      constraint 
         abs(AB-CD) >=9 /\ abs(AB-EF) >=9 /\ abs(AB-BA) >=9
      /\ abs(AB-DC) >=9 /\ abs(AB-FE) >=9 /\ abs(CD-EF) >=9 
      /\ abs(CD-BA) >=9 /\ abs(CD-DC) >=9 /\ abs(CD-FE) >=9
      /\ abs(EF-BA) >=9 /\ abs(EF-DC) >=9 /\ abs(EF-FE) >=9
      /\ abs(BA-DC) >=9 /\ abs(BA-FE) >=9 /\ abs(DC-EF) >=9;
      
      % Sum of ages of the first group = sum of ages of the second group
      constraint AB + CD + EF == BA + DC + FE;
      
      % Sum of the squares of the three ages of the first group 
      % equals sum of the squares of the three ages of the second group
      constraint AB*AB + CD*CD + EF*EF == BA*BA + DC*DC + FE*FE;
      
      % One of the ages in each group is exactly twice an age in the other group
      % One of 1st ages group is double one of 2nd group
      constraint 
         (AB == 2*BA \/ AB == 2*DC \/ AB == 2*FE)
      \/ (CD == 2*BA \/ CD == 2*DC \/ CD == 2*FE)
      \/ (EF == 2*BA \/ EF == 2*DC \/ EF == 2*FE);
      
      % One of 2nd ages group is double one of 1st group
      constraint 
         (BA == 2*AB \/ BA == 2*CD \/ BA == 2*EF)
      \/ (DC == 2*AB \/ DC == 2*CD \/ DC == 2*EF)
      \/ (FE == 2*AB \/ FE == 2*CD \/ FE == 2*EF);
      
      solve satisfy;
      
      output ["1st ages group = " ++ show(AB) ++ ", " ++ show(CD)
       ++  ", " ++ show(EF) ++ "\n"
      ++ "2nd ages group = " ++ show(BA) ++ ", " ++ show(DC) 
      ++ ", " ++ show(FE) ];
      
      % 1st ages group = 23, 64, 78
      % 2nd ages group = 32, 46, 87
      % ----------
      % ==========
      
      
      
      

      Like

    • Hugh+Casement 7:17 am on 30 January 2022 Permalink | Reply

      Without the upper and lower age limits
      there would be another solution: 14, 82, 69 and 41, 28, 96,
      again with group sum 165.

      Like

  • Jim Randell 9:46 am on 20 January 2022 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2878: Magic slides 

    From The Sunday Times, 19th November 2017 [link]

    I have a toy consisting of eight tiles that can move by sliding them around a three-by-three frame:

    At any stage a tile adjacent to the space can slide into that space. I gave the toy to my grandson in the state illustrated and after some moves he presented it back to me with the space once again in the bottom right-hand corner but with the “2” (amongst others) not in its original position. Furthermore, his arrangement had some “magical” properties: each row, each column, and the diagonal from bottom left to top right all added up to the same total.

    What was his arrangement?

    [teaser2878]

     
    • Jim Randell 9:47 am on 20 January 2022 Permalink | Reply

      We’ve looked at sliding puzzles before. See: Enigma 1444, Enigma 106, Enigma 1210, Enigma 1160, Enigma 588.

      In order for a position to be reachable the number of “inversions” (pairs of tiles that are out of order) must be even.

      This Python program runs in 111ms.

      Run: [ @replit ]

      from enigma import subsets, irange, all_same, printf
      
      # fill out the grid
      for (A, B, C, D, E, F, G, H) in subsets(irange(1, 8), size=len, select="P"):
        # B cannot be 2
        if B == 2: continue
        # check the magic lines
        if not all_same(
          # rows
          A + B + C, D + E + F, G + H,
          # columns
          A + D + G, B + E + H, C + F,
          # diagonal
          C + E + G,
        ): continue
      
        # the number of inversions must be even
        n = sum(i > j for (i, j) in subsets((A, B, C, D, E, F, G, H), size=2))
        if n % 2 != 0: continue
      
        # output solution
        printf("{A} {B} {C} / {D} {E} {F} / {G} {H}")
      

      Solution: The arrangement was:

      And we can use the sliding puzzle program I wrote for Enigma 1444 [link] to verify that there is a sequence of moves that produces the required arrangement:

      % python sliding-puzzle.py 3 3 2 3 7 6 1 5 4 8
      [SOLVED] Moves: 44, Elapsed Time: 0m08s
      

      Like

  • Jim Randell 9:45 am on 11 January 2022 Permalink | Reply
    Tags: by: Victor Bryant   

    Brain-Teaser 903: Ding-dong 

    From The Sunday Times, 26th November 1978 [link]

    Today a great celebration will take place on Bells Island, for it is the Feast of Coincidus. On this island there is monastery and a nunnery. At regular intervals (a whole number of minutes) the monastery bell dongs once. The nunnery bell rings at regular intervals too (different from the intervals of the monastery’s bell, but also a whole number of minutes). So the island also regularly reverberates with a ding from the nunnery’s bell. The Feast of Coincidus takes place whenever the monastery’s dong and the nunnery’s ding occur at the same moment, and that is exactly what is due to happen at noon today.

    Between consecutive Feasts the dongs from the monastery and the dings from the nunnery occur alternately and, although the two noises only coincide on Feast days, they do occur a minute apart at some other times.

    When the bells coincided last time (at noon, a prime number of days ago) this whole island indulged in its usual orgy of eating and drinking.

    How many days ago was that?

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    After this puzzle was published The Sunday Times was hit by industrial action, and the next issue was not published until 18th November 1979.

    [teaser903]

     
    • Jim Randell 9:47 am on 11 January 2022 Permalink | Reply

      If the shorter interval is i minutes, then, working forwards from the previous feast (= 0) the bell rings at (minutes):

      i, 2i, 3i, 4i, … ni

      And if the shorter interval is (i + x) minutes, then that bell rings at:

      (i + x), 2(i + x), 3(i + x), … (n − 1)(i + x)

      And the last 2 times coincide:

      ni = (n − 1)(i + x)
      i = (n − 1)x
      x = i / (n − 1)

      And there are times where the bells ring only 1 minute apart. As the bells are drifting apart at the beginning and together at the end, and their interval is a whole number of minutes, they must ring 1 minute apart immediately after and immediately before they coincide. i.e. x = 1 and n = i + 1

      So, the number of intervals for the shorter bell is 1 more than than the length of the interval in minutes.

      And in prime p days there are 1440p minutes, so we have:

      1440p = ni = (i + 1)i
      p = i(i + 1) / 1440

      So we need to find two consecutive integers, whose product is the product of a prime and 1440.

      Run: [ @replit ]

      from enigma import irange, inf, div, is_prime, printf
      
      for i in irange(1, inf):
        p = div(i * (i + 1), 1440)
        if p is not None and is_prime(p):
          printf("i={i} p={p}")
          break
      

      Solution: The last feast was 1439 days ago.

      So, almost 4 years ago.

      We have: i = p = 1439.

      Like

    • Hugh+Casement 1:15 pm on 11 January 2022 Permalink | Reply

      The periods are 24 hours for one and 23 hours 59 minutes for the other.

      Like

  • Jim Randell 3:56 pm on 30 December 2021 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 3093: Shout snap! 

    From The Sunday Times, 2nd January 2022 [link] [link]

    My grandson and I play a simple card game. We have a set of fifteen cards on each of which is one of the words ACE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING, SHOUT and SNAP. We shuffle the cards and then display them one at a time. Whenever two consecutive cards have a letter of the alphabet occurring on both we race to shout “Snap!”. In a recent game there were no snaps. I counted the numbers of cards between the “picture-cards” (J, Q, K) and there was the same number between the first and second picture-cards occurring as between the second and third. Also, the odd-numbered cards (3, 5, 7, 9) appeared in increasing order during the game.

    In order, what were the first six cards?

    [teaser3093]

     
    • Jim Randell 4:48 pm on 30 December 2021 Permalink | Reply

      The following Python 3 program runs in 478ms.

      Run: [ @replit ]

      from enigma import subsets, intersect, join, printf
      
      # the cards
      cards = "ACE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE TEN JACK QUEEN KING SHOUT SNAP".split()
      
      # which cards snap?
      snap = set()
      for (x, y) in subsets(cards, size=2):
        if intersect([x, y]):
          snap.update([(x, y), (y, x)])
      
      # generate sequences with no snaps
      def generate(cards, xs=[], pics=[], subseq=None):
        # are we done?
        if not cards:
          yield xs
        else:
          # choose the next card
          for (i, x) in enumerate(cards):
            if xs and (x, xs[-1]) in snap: continue
      
            # check subsequence cards appear in order
            ss = subseq
            if x in subseq:
              if x != subseq[0]: continue
              ss = ss[1:]
      
            # check picture cards appear equally distanced
            ps = pics
            if x in {'JACK', 'QUEEN', 'KING'}:
              ps = ps + [len(xs)]
              if len(ps) == 3 and ps[2] - ps[1] != ps[1] - ps[0]: continue
      
            # solve for the remaining cards
            yield from generate(cards[:i] + cards[i + 1:], xs + [x], ps, ss)
      
      # find solutions
      for ss in generate(cards, subseq=['THREE', 'FIVE', 'SEVEN', 'NINE']):  
        printf("{ss}", ss=join(ss, sep=" "))
      

      Solution: The first six cards were: EIGHT, SNAP, THREE, KING, ACE, SHOUT.

      And the full sequence is:

      EIGHT, SNAP, THREE, KING, ACE, SHOUT, FIVE, TWO, QUEEN, SIX, TEN, FOUR, SEVEN, JACK, NINE

      There are 4 cards between KING and QUEEN, and 4 cards between QUEEN and JACK.

      Like

      • NigelR 3:50 pm on 31 December 2021 Permalink | Reply

        A typical brute force approach from me. It is neither pretty nor quick, but it gets the job done (eventually!). I could probably have mined a bitcoin using less processing effort.

        
        # STBT 3093
        
        from itertools import permutations as perm
        
        cards=['ACE','TWO','THREE','FOUR','FIVE','SIX', 'SEVEN', 'EIGHT', 'NINE', 'TEN', 'JACK', 'QUEEN', 'KING','SHOUT','SNAP']
        oddnums=['THREE','FIVE','SEVEN','NINE']
        odds=[]
        evens=[]
        
        def oddtest(self): #test self for numbers 3-9 in correct sequence
            ind = [self.index(z) for z in oddnums]
            for z in range(0,3):
                if ind[z]>ind[z+1]:return False
            return True 
        
        def pictest(): #test picture cards for consistent spacing
            j,q,k=seq.index('JACK'),seq.index('QUEEN'),seq.index('KING')
            if q<j and q<k:return False #Q must be between J & K for equal spacing since q is an even and other two are odds
            if q>j and q>k:return False
            if abs(q-j)!=abs(k-q): return False  #check for equal spacing
            return True 
        
        def seqtest(): #test seq for no shared letters in adjacent cards
            for i in range(0,14):
                for z in seq[i]:
                    if z in seq[i+1]:return False
            return True
        
        seq=cards
        evens=[x for x in cards if 'E' in x] # there are 8 cards with letter E, so can only be placed on even slots to avoid adjacency
        odds=[x for x in cards if x not in evens]
        
        for x in list(perm(evens)):
            if not oddtest(x): continue
            for y in list(perm(odds)):
                for i in range(0,8): seq[i*2]=x[i]
                for i in range(1,8): seq[(2*i)-1]=y[i-1]
                if not pictest():continue
                if not seqtest():continue
                print ('The first six cards drawn in order were:',seq[0:6])
        
        

        Like

        • Jim Randell 10:54 am on 2 January 2022 Permalink | Reply

          My first program was quite slow too. I generated all sequences without a “snap” and then applied the remaining conditions.

          To improve the speed I moved the conditions inside the [[ generate() ]] function, and that got the code down to running in less than a second.

          Your observation that there are 8 cards with an E, and 7 cards without (so they must be interleaved, starting with an E), speeds up my code to 287ms.

          We replace line 20in my program with:

                if xs:
                  # can't snap with the previous card
                  if (x, xs[-1]) in snap: continue
                else:
                  # first card must have an E
                  if not('E' in x): continue
          

          Like

          • Brian Gladman 4:37 pm on 4 January 2022 Permalink | Reply

            @Jim I went down exactly the same path and arrived at a close to identical solution to your own.

            I missed the significance of cards with ‘E’s until it was pointed out here and this provides a major improvement in performance.

            If I add this to your version after line 18:

                pos_even = not (len(xs) & 1)
            

            and this after line 20:

                  if pos_even and 'E' not in x: continue
            

            the run time for me (using profile )drops by a factor of over 20.

            Like

          • Jim Randell 9:51 pm on 4 January 2022 Permalink | Reply

            Using the observation that the “with E” and “without E” sets of cards must be interleaved allows us to go back to the simpler approach where we generate (interleaved) sets of cards, and then check them for the remaining conditions, and still have the program run in a short time.

            from enigma import product, intersect, filter2, join, printf
            
            # the cards
            cards = "ACE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE TEN JACK QUEEN KING SHOUT SNAP".split()
            
            # partition the cards into 2 sets
            (cs1, cs2) = filter2((lambda x: 'E' in x), cards)
            assert len(cs1) == len(cs2) + 1
            
            # which cards snap?
            snap = set()
            for (x, y) in product(cs1, cs2):
              if intersect([x, y]):
                snap.update([(x, y), (y, x)])
            
            # generate sequences with no snaps, interleaving cs1 and cs2
            def generate(cs1, cs2, xs=[]):
              # are we done?
              if not cs1:
                yield xs
              else:
                # choose the next card
                for (i, x) in enumerate(cs1):
                  if xs and (x, xs[-1]) in snap: continue
                  # solve for remaining cards
                  yield from generate(cs2, cs1[:i] + cs1[i + 1:], xs + [x])
            
            # find solutions
            for ss in generate(cs1, cs2):
              pos = lambda x: ss.index(x)
              # check THREE, FIVE, SEVEN, NINE appear in order
              if not(pos('THREE') < pos('FIVE') < pos('SEVEN') < pos('NINE')): continue
              # check JACK, QUEEN, KING are evenly spaced
              (i, j, k) = sorted(pos(x) for x in ['JACK', 'QUEEN', 'KING'])
              if not(j - i == k - j): continue
              # output solution
              printf("{ss}", ss=join(ss, sep=" "))
            

            Like

  • Jim Randell 10:23 am on 30 December 2021 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2855: Fab four 

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

    Here are four numbers, where each is the same fixed whole-number multiple of the previous one. However, in some places I have consistently replaced digits by letters — and in the other places the digits have been replaced by [asterisks]. In this way the numbers have become the fabulous four:

    JOHN
    P*UL
    R***O
    ****GE

    What number is my GROUP?

    [teaser2855]

     
    • Jim Randell 10:24 am on 30 December 2021 Permalink | Reply

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

      I added lower case letters (which don’t have to be distinct from each other) to fill in the gaps in the words.

      The following run file executes in 83ms.

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      SubstitutedExpression
      
      --symbols="EGHJLNOPRUaingjeorz"
      --distinct="EGHJLNOPRU"
      --answer="GROUP"
      --reorder=0
      
      "JOHN * z = PaUL"
      "PaUL * z = RingO"
      "RingO * z = jeorGE"
      

      Solution: GROUP = 57209.

      The expressions are:

      1238 × 8 = 9904
      9904 × 8 = 79232
      79232 × 8 = 633856

      alphametically:

      JOHN × N = PPUL
      PPUL × N = RPOHO
      RPOHO × N = EHHNGE

      Like

  • Jim Randell 7:30 am on 23 December 2021 Permalink | Reply
    Tags: by: Victor Bryant   

    Brain-Teaser 891: Ups and downs 

    From The Sunday Times, 3rd September 1978 [link]

    An electrician living in a block of flats has played a joke on the tenants by rewiring the lift. The buttons numbered 0 to 9 in the lift should correspond to the ground floor, first floor, etc., but he has rewired them so that although (for his own convenience) the buttons for the ground floor and his own floor work correctly, no other button takes you to its correct floor. Indeed when you get in the lift on the ground floor and go up, three of the buttons take you twice as high as they should, and two buttons take you only half as high as they should.

    The milkman is unaware of the rewiring and so early yesterday morning, rather bleary-eyed, he followed his usual ritual which consists of taking nine pints of milk into the lift, pushing button 9, leaving one pint of milk when the lift stops, pushing button 8, leaving one pint of milk when the lift stops, and so on in decreasing order until, having pushed button and having left his last pint, he usually returns to his van.

    However, yesterday when he tried to follow this procedure all seemed to go well until, having pushed button 1 , when the lift stopped he found a pint of milk already there. So he took the remaining pint back to his van, with the result that just one of the tenants (who lived on one of the floors below the electrician’s) did not get the pint of milk she’d expected.

    The surprising thing was that during the milkman’s ups and downs yesterday he at no time travelled right past the floor which he thought at that time he was heading towards.

    List the floors which received milk, in the order in which the milkman visited them.

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser891]

     
    • Jim Randell 7:32 am on 23 December 2021 Permalink | Reply

      The electrician makes a journey by selecting buttons 9, 8, 7, …, 3, 2, 1, and in the process visits one of the floors twice and one of the floors no times. And the floor that is not visited is a lower number than the electrician’s floor (which is the only button that gives the correct floor).

      I assumed there are exactly 3 buttons that go to floor exactly twice the number on the button, and exactly 2 that go to a floor exactly half the number on the button.

      This Python 3 program chooses the buttons that go to floors twice and half their labelled values, and then fills out the rest of the mapping as it goes along. It runs in 53ms.

      Run: [ @replit ]

      from enigma import irange, update, product, subsets, diff, singleton, trim, map2str, printf
      
      # consider a journey made with buttons <bs>, visiting floors <fs> using map <m> (button -> floor)
      def journey(bs, fs, m):
        # are we done?
        if not bs:
          yield (fs, m)
        else:
          (b, f_) = (bs[0], fs[-1])
          # is the button assigned?
          f = m.get(b, None)
          if f is None:
            (ss, upd) = (irange(0, 9), 1)
          else:
            (ss, upd) = ([f], 0)
          # choose a target floor
          for f in ss:
            # if unassigned: cannot be the right floor, or twice or half
            if upd and (f == b or f == 2 * b or b == 2 * f): continue
            # cannot be a previously visited floor, except for the final floor
            if (f in fs) != (len(bs) == 1): continue
            # journey cannot pass the correct floor
            if not(f_ < b < f or f_ > b > f):
              m_ = (update(m, [(b, f)]) if upd else m)
              yield from journey(bs[1:], fs + [f], m_)
      
      # exactly 3 buttons go to twice the number, exactly 2 buttons go to half the number
      for (ds, hs) in product(subsets([1, 2, 3, 4], size=3), subsets([2, 4, 6, 8], size=2)):
        # remaining floors
        rs = diff(irange(1, 9), ds + hs)
        if len(rs) != 4: continue
      
        # choose the floor for the electrician
        for e in rs:
          if e == 1: continue
      
          # initial map
          m0 = { 0: 0, e: e }
          m0.update((k, 2 * k) for k in ds) # doubles
          m0.update((k, k // 2) for k in hs) # halfs
      
          # consider possible journeys for the milkman
          for (fs, m) in journey([9, 8, 7, 6, 5, 4, 3, 2, 1], [0], m0):
      
            # the unvisited floor is lower than e
            u = singleton(x for x in irange(1, 9) if x not in fs)
            if u is None or not(u < e): continue
      
            # output solution
            printf("{fs} {m}", fs=trim(fs, head=1, tail=1), m=map2str(m, arr='->'))
      

      Solution: The milkman visited floors: 7, 4, 2, 3, 5, 8, 6, 9.

      He then returns to floor 2, and finds he has already visited.

      The rewired map of button → floor is:

      0 → 0
      1 → 2 (twice)
      2 → 9
      3 → 6 (twice)
      4 → 8 (twice)
      5 → 5 (electrician’s floor)
      6 → 3 (half)
      7 → 2
      8 → 4 (half)
      9 → 7

      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
%d bloggers like this: