Design a site like this with WordPress.com
Get started

Updates from December, 2020 Toggle Comment Threads | Keyboard Shortcuts

  • Jim Randell 4:36 pm on 18 December 2020 Permalink | Reply
    Tags:   

    Teaser 3039: Three patterned paving 

    From The Sunday Times, 20th December 2020 [link]

    James is laying foot-square stones in a rectangular block whose short side is less than 25 feet. He divides this area into three rectangles by drawing two parallel lines between the longest sides and into each of these three areas he lays a similar pattern.

    The pattern consists of a band or bands of red stones laid concentrically around the outside of the rectangles with the centre filled with white stones. The number of red stone bands is different in each of the rectangles but in each of them the number of white stones used equals the number of outer red stones used.

    The total number of stones required for each colour is a triangular number (i.e., one of the form 1+2+3+…).

    What is the total area in square feet of the block?

    [teaser3039]

     
    • Jim Randell 5:51 pm on 18 December 2020 Permalink | Reply

      (See also: Teaser 3007).

      After some head scratching I realised that the parallel lines are parallel to the short sides of the rectangular block, not the long sides.

      Considering a section of paving that is n stones wide and h stones long.

      If we count the number of border layers on both sides of the central area, we get an even number b, such that b < n.

      And if the border area is the same as the central area we have:

      (n − b)(h − b) = nh/2
      h = 2b(n − b) / (n − 2b)

      So for any (n, b) pair we can calculate a value for h, and accept values where b < h.

      The following Python program runs in 44ms.

      Run: [ @replit ]

      from enigma import (irange, div, subsets, all_different, is_triangular, printf)
      
      # consider values for the short side of the rectangle
      for n in irange(3, 24):
        # collect sets of (<section-length>, <border-width>)
        ss = list()
        # consider possible border values
        for b in irange(2, (n - 1) // 2, step=2):
          # calculate section length
          h = div(2 * b * (n - b), n - 2 * b)
          if h is None or not (b < h): continue
          printf("[n={n} b={b} -> h={h}]")
          ss.append((h, b))
        # choose the 3 sections
        for ((h1, b1), (h2, b2), (h3, b3)) in subsets(ss, size=3):
          # the borders are all different
          if not all_different(b1, b2, b3): continue
          # total length of the sections
          h = h1 + h2 + h3
          if not (h > n): continue
          # total number of stones for each colour
          t = div(n * h, 2)
          if t is None or not is_triangular(t): continue
      
          # output solution
          printf("{n} x {h} -> A={A} (t={t}); sections = (h={h1}, b={b1}) (h={h2}, b={b2}) (h={h3}, b={b3})", A=2 * t)
      

      Solution: The total area of the block is 2352 square feet.

      The block is 24 feet wide and 98 feet long, and is split into three sections:

      24 feet × 10 feet, border 2 deep. (120 slabs of each colour).

      24 feet × 18 feet, border 3 deep. (216 slabs of each colour).

      24 feet × 70 feet, border 5 deep. (840 slabs of each colour).

      In total 1176 slabs of each colour are required, and 1176 = T(48).

      Here’s a diagram of the three sections, with the longest one in the middle:

      Like

    • Frits 6:37 pm on 19 December 2020 Permalink | Reply

      I tried pythagorean_triples in combination with SubstitutedExpression (as n^2 + h^2 must be square) but that was too slow.

      from enigma import SubstitutedExpression, is_square
      
      # number of red stones: (n - b)(h - b)
      # number of white stones: nh/2
      # b^2 - (n + h)b + nh/2 = 0 
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [ 
        # AB = number of border layers on both sides of the central area
        # CDE = long side
        # FG = short side
        # FG is at least 15, 2+4+6 = 12, sum 3 different numbers of border layers
        #                    plus 3 whites
        "FG > 14",
        "FG < 25",
        "AB * AB - (CDE + FG) * AB + CDE * FG / 2 == 0",
        "AB > 0",
        "AB < CDE",
        "CDE > 0",
       
        # IJ = number of border layers on both sides of the central area
        # KLM = long side
        "IJ * IJ - (KLM + FG) * IJ + KLM * FG / 2 == 0",
        "IJ > 0",
        "KLM > 0",
        "IJ < KLM",
        "KLM > CDE", 
        
        # QR = number of border layers on both sides of the central area
        # STU = long side
        "QR * QR - (STU + FG) * QR + STU * FG / 2 == 0",
        "QR > 0",
        "STU > 0",
        "QR < STU",
        "STU > KLM",
        
        # the numbers of border layers are all different
        "len([AB, IJ, QR]) == len(set([AB, IJ, QR]))",
        
        # total number of stones for each colour must be triangular
        # if t is the nth triangular number, then t = n*(n+1)/2
        # and n = (sqrt(8t+1) - 1) / 2
      
        "is_square(4* FG * (CDE + KLM + STU) + 1)"
        ],
        answer="FG * (CDE + KLM + STU), FG, CDE, AB, KLM, IJ, STU, QR",
        # short side is even and < 25
        d2i=dict([(0, "F")] + \
                 [(1, "GBJR")] + \
                 [(k, "FGBJR") for k in {3, 5, 7, 9}] + \
                 [(k, "F") for k in {4, 6, 8}]),
        distinct="",
        reorder=0,
        verbose=0)   
      
      # collect and print answers 
      answs = sorted([y for _, y in p.solve()])
      print(" area,  n  h1  b1 h2  b1 h3  b3")
      for a in answs:
        print(f"{a}")
      

      Like

  • Jim Randell 4:30 pm on 11 December 2020 Permalink | Reply
    Tags:   

    Teaser 3038: Progressive raffle 

    From The Sunday Times, 13th December 2020 [link]

    George and Martha were participating in the local village raffle. 1000 tickets were sold, numbered normally from 1 to 1000, and they bought five each. George noticed that the lowest-numbered of his tickets was a single digit, then each subsequent number was the same multiple of the previous number, e.g. (7, 21, 63, 189, 567). Martha’s lowest number was also a single digit, but her numbers proceeded with a constant difference, e.g. (6, 23, 40, 57, 74). Each added together all their numbers and found the same sum. Furthermore, the total of all the digits in their ten numbers was a perfect square.

    What was the highest numbered of the ten tickets?

    [teaser3038]

     
    • Jim Randell 4:52 pm on 11 December 2020 Permalink | Reply

      If the sum of the 5 terms of the geometric progression is t, and this is also the sum of the 5 term arithmetic progression (a, a + d, a + 2d, a + 3d, a + 4d), then we have:

      t = 5(a + 2d)

      So the sum must be a multiple of 5.

      The following Python program runs in 44ms.

      Run: [ @repl.it ]

      from enigma import irange, div, union, nsplit, is_square, printf
      
      # generate geometric progressions with k elements
      # n = max value for 1st element, N = max value for all elements
      def geom(k, n=9, N=1000):
        # first element
        for a in irange(1, n):
          # second element is larger
          for b in irange(a + 1, N):
            # calculate remaining elements
            (gs, rs, x) = ([a, b], 0, b)
            while len(gs) < k:
              (x, r) = divmod(x * b, a)
              gs.append(x)
              rs += r
            if x > N: break
            if rs == 0:
              yield tuple(gs)
      
      # digit sum of a sequence
      dsums = lambda ns: sum(nsplit(n, fn=sum) for n in ns)
      
      # consider geometric progressions for G
      for gs in geom(5):
        x = div(sum(gs), 5)
        if x is None: continue
        
        # arithmetic progressions for M, with the same sum
        # and starting with a single digit
        for a in irange(1, 9):
          d = div(x - a, 2)
          if d is None: continue
          ms = tuple(irange(a, a + 4 * d, step=d))
          ns = union([gs, ms])
          if len(ns) != 10: continue
      
          # the sum of the digits in all the numbers is a perfect square
          r = is_square(dsums(ns))
          if r is None: continue
      
          m = max(gs[-1], ms[-1])
          printf("max = {m}; gs = {gs}, ms = {ms}; sum = {t}, dsum = {r}^2", t=5 * x)
      

      Solution: The highest numbered ticket is 80.

      Note that the [[ geom() ]] function will generate all possible geometric progressions, including those that have a non-integer common ratio, (e.g. for a 4 element progression we could have (8, 28, 48, 343)), but for a 5 element progression we would need the initial term to have a factor that is some (non-unity) integer raised to the 4th power, and the smallest possible value that would allow this is 2^4 = 16, which is not possible if the initial term is a single digit. So for this puzzle the solution can be found by considering only those progressions with an integer common ratio (which is probably what the puzzle wanted, but it could have said “integer multiple” to be completely unambiguous).

      Like

    • GeoffR 7:48 pm on 11 December 2020 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % terms of arithmetic series
      var 1..9: A1; var 2..100: A2;var 2..150: A3;
      var 2..250: A4; var 2..500: A5;
      
      % terms of geometric series
      var 1..9: G1; var 2..100: G2;var 2..150: G3;
      var 2..250: G4; var 2..500: G5;
      
      % geometric ratio and arithmetic difference
      var 2..9:Gratio; 
      var 2..200:Adiff;
      
      %  total sum of  geometric and arithmetic series 
      var 2..500: Gsum; 
      var 2..500: Asum;
      
      % maximum raffle ticket number
      var 2..999: max_num;  
      
      constraint A2 == A1 + Adiff;
      constraint A3 == A2 + Adiff;
      constraint A4 == A3 + Adiff;
      constraint A5 == A4 + Adiff;
      
      constraint Asum = A1 + A2 + A3 + A4 + A5;
      
      constraint G2 == G1*Gratio;
      constraint G3 == G2*Gratio;
      constraint G4 == G3*Gratio;
      constraint G5 == G4*Gratio;
      
      constraint Gsum = G1 + G2 + G3 + G4 + G5;
      
      constraint Gsum == Asum;
      
      constraint all_different ([A1,A2,A3,A4,A5,G1,G2,G3,G4,G5]);
      
      constraint max_num = max({A1,A2,A3,A4,A5,G1,G2,G3,G4,G5});
      
      solve satisfy;
      
      output[ "Geometric Series: " ++ show([G1,G2,G3,G4,G5])  
      ++ "\n" ++ "Arithmetic Series = " ++ show([A1,A2,A3,A4,A5]) 
      ++ "\n" ++ "Max ticket number = " ++ show(max_num) ];
      

      This programme produces three solutions, all with the same maximum value.
      In only one of the solutions do the digits add to a perfect square.

      Like

    • Jim Randell 8:05 pm on 11 December 2020 Permalink | Reply

      @Geoff: There’s only one copy of each ticket, so both George and Martha’s sets of numbers are fully determined. (Even though we are only asked for the highest numbered ticket).

      Like

    • Frits 2:30 pm on 12 December 2020 Permalink | Reply

      for k in range(2, 6):
        print(sum(k**i for i in range(5)))
      

      The result of this piece of code are all numbers ending on a 1. This limits George’s lowest-numbered ticket to one number.

      Like

    • Frits 7:57 pm on 12 December 2020 Permalink | Reply

      The generated code can be seen with option verbose=256.

      from enigma import SubstitutedExpression, is_prime, is_square, \
                         seq_all_different
      
      # Formula
      # G * (1 + K + K^2 + K^3 + K^4) == 5 * (M + 2*D) 
      
      # (1 + K + K^2 + K^3 + K^4) equals (K^5 - 1) / (K - 1) 
      # (idea Brian Gladman)
      
      # sum the digits of the numbers in a sequence
      dsums = lambda seq: sum(sum(int(x) for x in str(s)) for s in seq)
      
      # domain lists
      dlist = list(range(3))  # d < 250
      elist = list(range(10))
      flist = list(range(10))
      glist = list(range(1, 10))
      klist = []
      mlist = list(range(1, 10))
      
      lastdigit = set()           # last digit of the total of 5 tickets
      # K^4 may not be higher than 1000, so K < 6
      for k in range(2, 6):
        t = sum(k**i for i in range(5))
        klist.append(k)
        lastdigit.add(t % 10)
        
      lastdigit = list(lastdigit)  
      
      if 5 not in lastdigit:
        # George's lowest ticket must be 5 as total is a multiple of 5
        glist = [5]
        
      if len(lastdigit) == 1:
        # Martha's tickets sum to 5 * (M + 2*D) 
        if lastdigit[0] % 2 == 1:
          # Martha's lowest ticket must be odd
          mlist = [1, 3, 5, 7, 9]
        else:
          # Martha's lowest ticket must be even
          mlist =[2, 4, 6, 8]
        
      if len(glist) == 1:
        # George's highest ticket may not be higher than 1000
        klist = [x for i, x in enumerate(klist, start=2) 
                               if i**4 * glist[0] <= 1000]
        # calculate highest sum of 5 tickets                       
        t = sum(max(klist)**i for i in range(5)) * glist[0]
        
        # Martha's highest ticket may not be higher than (t/5 - M) / 2
        dlist = [x for x in dlist if x <= (t / 10) // 100]
        if dlist == [0]:
          elist = [x for x in elist if x <= (t // 10) // 10]
          
        mlist = [x for x in mlist if x != glist[0]]
        
      # build dictionary for invalid digits 
      vars = "DEFGKM"
      invalid = "dict("
      for i in range(10):
        txt = ""
        for j, li in enumerate([dlist, elist, flist, glist, klist, mlist]):
          if i not in li:
            txt += vars[j]
        invalid += "[(" + str(i) + ", '" + txt + "')] + "
      
      invalid = invalid[:-3] + ")"  
      
      
      exprs = []
      
      # George's and Martha's sum was the same
      exprs.append("G * (K ** 5 - 1) // (K - 1) == 5 * (M + 2 * DEF)")
      # all ticket numbers have to be different
      exprs.append("seq_all_different([G, G * K, G * K**2, G * K**3, G * K**4, \
                                     M, M + DEF, M + 2*DEF, M + 3*DEF, M + 4*DEF])")
      # total of all the digits in the ten numbers was a perfect square                               
      exprs.append("is_square(dsums([G, G * K, G * K**2, G * K**3, G * K**4, \
                                     M, M + DEF, M + 2*DEF, M + 3*DEF, M + 4*DEF]))")    
                                     
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        exprs,
        answer="(G, G * K, G * K**2, G * K**3, G * K**4), \
                (M, M + DEF, M + 2*DEF, M + 3*DEF, M + 4*DEF), 5 * (M + 2 * DEF)",
        d2i=eval(invalid),
        env=dict(dsums=dsums),
        distinct="GM",
        verbose=0)   
      
      # Print answers 
      for (_, ans) in p.solve():
          print(f"{ans}")
      

      Like

    • Tony Brooke-Taylor 9:10 am on 14 December 2020 Permalink | Reply

      My first solution generated the series explicitly and then applied the tests to each series, but then I realised we could equate the expressions for the sums of each series to reduce the sets of parameters we need to test. My second attempt was similar to below but instead of constraining the sum to a multiple of 5 I initially constrained my ‘b’ parameter to an integer, which I think is mathematically equivalent but came inside another loop so was less efficient.

      #Generator function to create possible combinations of parameters for George and Martha
      def core_parameters():
        #George's tickets form the geometric progression x.(y^0, y^1, y^2, y^3, y^4)
        #Martha's tickets form the arithmetic progression (a+b*0, a+b*1, a+b*2, a+b*3, a+b*4)
      
        for x in range(1,10): #we are told that George's first ticket has a single-digit value
          max_y = int((1000/x)**(0.25)//1)+1 #defined by the maximum possible value for George's highest-value ticket
          for y in range(2,max_y): #y=1 not possible because this would give all George's tickets the same value
      
            sum_values = x*(1-y**5)/(1-y) #sum of finite geometric progression
            #sum_values = a*5 + b*10      #sum of finite arithmetic progression
            #=> b = (sum_values - a*5)/10 = sum_values/10 - a/2
            if sum_values%5 == 0:      #equality also requires that the sum is a multiple of 5
      
              for a in range(1,10): #we are told that Martha's first ticket has a single-digit value
                if a != x:          #Martha's first ticket cannot have the same value as George's
                  b = sum_values/10 - a/2
                  yield x, y, a, b
      
      #Function to sum all digits in an integer
      def digit_sum(num):
        s = 0
        for dig in str(num):
          s = s + int(dig)
        return s  
      
      #Control program
      
      for first_george_ticket, george_multiple, first_martha_ticket, martha_multiple in core_parameters():
        george_tix = [first_george_ticket*george_multiple**n for n in range(5)]
        martha_tix = [int(first_martha_ticket+martha_multiple*m) for m in range(5)]
      
        #they can't both have the same ticket and we are told that the sum of all digits is a square
        if set(martha_tix).intersection(george_tix) == set() and \
        ((sum([digit_sum(j) for j in george_tix]) + sum([digit_sum(k) for k in martha_tix]))**(1/2))%1 == 0: 
        
          print("George:", george_tix)
          print("Martha:", martha_tix)
          print("Highest-valued ticket:",max(george_tix + martha_tix))     
          break
      

      Like

  • Jim Randell 4:51 pm on 4 December 2020 Permalink | Reply
    Tags:   

    Teaser 3037: Prime advent calendar 

    From The Sunday Times, 6th December 2020 [link]

    Last year I was given a mathematical Advent calendar with 24 doors arranged in four rows and six columns, and I opened one door each day, starting on December 1. Behind each door is an illustrated prime number, and the numbers increase each day. The numbers have been arranged so that once all the doors have been opened, the sum of the numbers in each row is the same, and likewise for the six columns. Given the above, the sum of all the prime numbers is as small as it can be.

    On the 24th, I opened the last door to find the number 107.

    In order, what numbers did I find on the 20th, 21st, 22nd and 23rd?

    [teaser3037]

     
    • Jim Randell 6:52 pm on 4 December 2020 Permalink | Reply

      I think this is the first Teaser in quite a while that has taken me more than a few minutes to solve. Fortunately all the numbers we are dealing with are different, so that simplifies things a bit.

      My original program [link] was shorter, but less efficient (it runs in 3.4s). The following Python 3 program is longer, but runs in only 81ms.

      Run: [ @repl.it ]

      from enigma import Primes, subsets, diff, intersect, div, join, peek, sprintf, printf
      
      # choose length k sets from ns, where each set sums to t
      def rows(ns, k, t, ss=[]):
        # are we done?
        if not ns:
          yield ss
        else:
          # take the first element
          n = ns[0]
          # and k-1 other elements to go with it
          for s in subsets(ns[1:], size=k - 1):
            if sum(s) == t - n:
              s = (n,) + s
              yield from rows(diff(ns, s), k, t, ss + [s])
      
      # make a column that sums to t, by choosing an element from each row
      def make_col(rs, t, s=[]):
        if len(rs) == 1:
          if t in rs[0]:
            yield tuple(s + [t])
        else:
          for x in (rs[0][:1] if len(s) == 0 else rs[0]):
            t_ = t - x
            if t_ > 0:
              yield from make_col(rs[1:], t_, s + [x])
      
      # make columns from the rows, where each column sums to t
      def cols(rs, t, ss=[]):
        # are we done?
        if not rs[0]:
          yield ss
        else:
          # make one column
          for s in make_col(rs, t):
            # and then make the rest
            yield from cols(list(diff(r, [x]) for (r, x) in zip(rs, s)), t, ss + [s])
      
      # solve the puzzle
      def solve():
        # possible primes
        primes = Primes(107)
      
        # find viable sets of primes
        for ps in sorted(subsets(primes, size=23), key=sum):
          ps += (107,)
          # total sum = T, row sum = R, col sum = C
          T = sum(ps)
          R = div(T, 4)
          C = div(T, 6)
          if R is None or C is None: continue
          printf("[T={T} R={R} C={C}]")
      
          # choose rows of 6, each sums to R
          for rs in rows(ps, 6, R):
            # select columns, each sums to C
            for cs in cols(rs, C):
              yield (ps, rs, cs)
      
      # find the first solution
      for (ps, rs, cs) in solve():
        # output solution
        printf("ps = {ps} -> {T}", T=sum(ps))
        printf("rs = {rs} -> {R}", R=sum(rs[0]))
        printf("cs = {cs} -> {C}", C=sum(cs[0]))
      
        # output solution grid
        for r in rs:
          printf("{r}", r=join(sprintf("[{x:3d}]", x=peek(intersect((r, c)))) for c in cs))
      
        # we only need the first solution
        break
      

      Solution: The numbers on the 20th, 21st, 22nd, 23rd were: 73, 79, 83, 101.

      One possible layout is shown below, but there are many others:

      Each row sums to 270. Each column sums to 180. Altogether the numbers sum to 1080.

      I let my program look for solutions with a higher sum, and it is possible to construct a calendar for every set of primes whose sum is a multiple of 24.

      Like

    • Frits 12:02 pm on 5 December 2020 Permalink | Reply

      @Jim, you can also remove 2 from primes (as column sum needs to be even (row sum, 1.5 * column sum, must be a whole number) and there is only 1 even prime in primes).

      With this, your first reported T,R,C combination can be discarded as R may not be odd (sum of 6 odd numbers is even).

      I also have the same first solution but it takes a long time (mainly in checking column sums).
      I first tried a program with SubstitutedExpression but I had problems with that.

      Like

      • Jim Randell 5:18 pm on 5 December 2020 Permalink | Reply

        @Frits: Thanks. I realised that 2 wasn’t going to be involved in final grid. But if you exclude it at the start, and only allow even row and column sums, then the runtime of my program goes down to 58ms. (And the internal runtime is down to 14ms).

        Like

        • Frits 8:17 pm on 5 December 2020 Permalink | Reply

          @Jim,

          A further improvement could be to skip checking subsets (line 45) when testing sum 1080 as the number of primes to be used is fixed.

          Sum of primes from 3 to 107 is 1369 (for 27 primes)
          1369 – 1080 = 289 which can only be formed by 3 primes with (89, 97 and 103 ).
          The 24 remaining primes can be used to do the rows and cols logic.

          Like

          • Jim Randell 10:15 pm on 5 December 2020 Permalink | Reply

            @Frits: I’m not sure I understand. In my program the sets of primes are tackled in sum order (to ensure we find the set with the lowest sum), so only one set of primes with sum 1080 will be checked (as there is only one set that sums to 1080).

            Like

            • Frits 11:46 pm on 5 December 2020 Permalink | Reply

              You can analyze that 1080 is the first sum to check (sum has to be a multiple of 24).

              So you don’t need to execute line 45 if you first have a separate check for 1080 (with the 24 primes) and you do find an answer for it.

              The disadvantage is that it will make the code less concise.

              Like

            • Frits 11:51 pm on 5 December 2020 Permalink | Reply

              Meaning:

              handle 1080 sum, exit program if solution found
              
              for ps in sorted(subsets(primes, size=23), key=sum)
                if sum == 1080: continue
                .....
              

              Like

    • Frits 10:17 am on 6 December 2020 Permalink | Reply

      A little bit different and less efficient.

      from itertools import combinations as comb
      from itertools import product as prod
      from enigma import group
      
      flat = lambda group: {x for g in group for x in g}
      
      # Prime numbers up to 107 
      Pr =  [2, 3, 5, 7]
      Pr += [x for x in range(11, 100, 2) if all(x % p for p in Pr)]
      Pr += [x for x in range(101, 108, 2) if all(x % p for p in Pr)]
      
      min1 = sum(Pr[1:24]) + 107
      max1 = sum(Pr[-24:])
      print("    sum    row     column")  
      print("min", min1, " ", round(min1 / 4, 2), " ", round(min1 / 6, 2))
      print("max", max1, " ", round(max1 / 4, 2), " ", round(max1 / 6, 2))
      
      Pr = Pr[1:-1]              # exclude 2 and 107
      
      sumPr = sum(Pr + [107])
      lenPr = len(Pr + [107])
      
      # length Pr + [107]: 27, sum(Pr + [107]) = 1369
      #
      #     sum    row     column
      # min 1068   267.0   178.0
      # max 1354   338.5   225.66666666666666
        
      # pick one value from each entry of a <k>-dimensional list <ns>
      def pickOneFromEach(k, ns, s=[]):
        if k == 0:
           yield s 
        else:
          for n in ns[k-1]:
            yield from pickOneFromEach(k - 1, ns, s + [n])  
            
      # decompose <t> into <k> increasing numbers from <ns>
      # so that sum(<k> numbers) equals <t>
      def decompose(t, k, ns, s=[], used=[], m=1):
        if k == 1:
          if t in ns and not(t in s or t in used) :
            if not(t < m): 
              yield s + [t]
        else:
          for (i, n) in enumerate(ns):
            if not(n < t): break
            if n in s or n in used: continue
            if (n < m): continue
            yield from decompose(t - n, k - 1, ns[i:], s + [n], used, n)
            
      # check if sums are the same for all columns
      def checkColSums(rs, t):
        correctSumList = [p for p in prod(*rs) if sum(p) == t]
        uniqueFirstCols = len(set(x[0] for x in correctSumList))
         
        if uniqueFirstCols < 6:        # elements are not unique
          return
        elif uniqueFirstCols == 6:
          groupByFirstCol = [x for x in group(correctSumList, 
                             by=(lambda d: d[0])).values()]
          for p in list(pickOneFromEach(6, groupByFirstCol)):
            if len(set(flat(p))) == 24:
              yield p
        else:  
          for c in comb(correctSumList, 6):
            if len(set(flat(c))) == 24:
              yield c        
      
      # check sums by starting with smallest 
      for T in {x for x in range(min1, max1 + 1) if x % 24 == 0}:
        dif = sumPr - T
        rsum = T // 4
        csum = T // 6
        print("\nTotal sum",T, "row sum",rsum, "col sum",csum, "difference", dif)
        
        # check which primes are to be dropped
        c = 0
        for di in decompose(dif, lenPr - 24, Pr): 
          if c == 0:
            Pr2 = [x for x in Pr if x not in di] + [107]
          c += 1  
          
        if c > 1:           # more possibilities to drop primes
          Pr2 = list(Pr)
        
        print(f"\nPrimes to check={Pr2}")
        
        # first make 4 lists of 6 numbers which add up to rsum
        for s1 in decompose(rsum - 107, 5, Pr2, [107]):
          s1 = s1[1:] + [s1[0]]                   # put 107 at the end
          for s1 in decompose(rsum, 6, Pr2, s1, m=s1[0]):
            for s1 in decompose(rsum, 6, Pr2, s1, m=s1[6]):
              for s1 in decompose(rsum, 6, Pr2, s1, m=s1[12]):
                rs = [s1[0:6], s1[6:12], s1[12:18], s1[18:24]]
                # check if all columns add up to csum
                for cs in checkColSums(rs, csum):
                  print("\nSolution: \n")
                  for r in zip(*cs[::-1]):        # rotate matrix
                    for x in r:
                      print(f"{x:>3}", end = " ")
                    print()  
                  
                  print("\nNumbers on the 20th, 21st, 22nd and 23rd:")  
                  print(", ".join(str(x) for x in sorted(flat(cs))[-5:-1]))
                  exit(0)  
      

      Like

      • Jim Randell 2:30 pm on 6 December 2020 Permalink | Reply

        @Frits: I don’t think you want to use a set() at line 70. The set() will remove duplicates, but you are not guaranteed to get the numbers out in increasing order. In this case we know that there are no duplicates, and we definitely want to consider the numbers in increasing order (so we can be sure we have found the smallest).

        Changing the brackets to () or [] will do, but I think there are clearer ways to write the loop.

        Like

        • Frits 7:18 pm on 6 December 2020 Permalink | Reply

          @Jim. Thanks.

          I normally run python programs with PyPy and PyPy preserves the order of dictionaries and sets.

          Running with Python solved the sum 1152 and not for 1080.

          Like

          • Jim Randell 11:10 am on 7 December 2020 Permalink | Reply

            @Frits: OK. I knew about the PyPy’s behaviour for dict(), but not for set().

            FWIW: I try to post code that runs on as wide a variety of Pythons as possible. I currently check against CPython 2.7.18 and 3.9.0 (although sometimes I use features that only became available in Python 3).

            Like

    • GeoffR 10:43 am on 7 December 2020 Permalink | Reply

      I found a solution in MiniZinc, but the run time was very slow (just over 5 min)

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      % grid of Advent calendar doors
      % a b c d e f
      % g h i j k l
      % m n o p q r
      % s t u v w x
      
      % set of primes, excluding 2 as non viable for this puzzle
      set of int: primes = {3, 5, 7, 11, 13, 17, 19, 23,
      29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
      83, 89, 97, 101, 103, 107};
      
      set of int: Digit = 3..107;
      
      % 24 prime numbers
      var Digit: a; var Digit: b; var Digit: c; var Digit: d;
      var Digit: e; var Digit: f; var Digit: g; var Digit: h; 
      var Digit: i; var Digit: j; var Digit: k; var Digit: l; 
      var Digit: m; var Digit: n; var Digit: o; var Digit: p; 
      var Digit: q; var Digit: r; var Digit: s; var Digit: t;
      var Digit: u; var Digit: v; var Digit: w; var Digit: x; 
      
      var 0..1400: psum = sum([a, b, c, d, e, f, g, h, i, j,
       k, l, m, n, o, p, q, r, s, t, u, v, w, x]);
       
      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]);
      
      % allocate 24 primes
      constraint a in primes /\ b in primes /\ c in primes
      /\ d in primes /\ e in primes /\ f in primes;
      
      constraint g in primes /\ h in primes /\ i in primes
      /\ j in primes /\ k in primes /\ l in primes;
      
      constraint m in primes /\ n in primes /\ o in primes
      /\ p in primes /\ q in primes /\ r in primes;
      
      constraint s in primes /\ t in primes /\ u in primes
      /\ v in primes /\ w in primes;
      
      % put highest prime in Xmas Eve Box to fix grid
      constraint x == 107;
      
      % row totals add to the same value
      constraint (a + b + c + d + e + f) == (g + h + i + j + k + l)
      /\ (a + b + c + d + e + f) == (m + n + o + p + q + r)
      /\ (a + b + c + d + e + f) == (s + t + u + v + w + x);
      
      % column totals add to the same value
      constraint (a + g + m + s) == (b + h + n + t)
      /\ (a + g + m + s) == (c + i + o + u)
      /\ (a + g + m + s) == (d + j + p + v)
      /\ (a + g + m + s) == (e + k + q + w)
      /\ (a + g + m + s) == (f + l + r + x);
      
      % sum of grid primes is divisible by 12 - LCM of 4 and 6
      % as 4 x row sum = psum and 6 x column sum = psum
      constraint psum mod 12 == 0;
       
      % minimise total sum of prime numbers used
      solve minimize psum;
      
      % find unused primes in original max list of primes
      var set of int: digits_not_used = primes diff 
      {a, b, c, d, e, f, g, h, i, j,
       k, l, m, n, o, p, q, r, s, t, u, v, w, x};
      
      % output grid and grid row and column totals
      output ["  Grid is: " 
      ++ "\n " ++ show([a, b, c, d, e, f]) 
      ++ "\n " ++ show([g, h, i, j, k, l])
      ++ "\n " ++ show([m, n, o, p, q, r])
      ++ "\n " ++ show([s, t, u, v, w, x]) 
      
      ++ "\n Prime Sum overall = " ++ 
      show(sum([a, b, c, d, e, f, g, h, i, j,
      k, l, m, n, o, p, q, r, s, t, u, v, w, x]))
      
      ++ "\n Row sum = " ++ show(sum([a + b + c + d + e + f])) 
      ++ "\n Column sum = " ++ show(sum([a + g + m + s]))
      ++ "\n Unused primes : " ++ show(digits_not_used) ];
      
      

      Like

      • Frits 1:33 pm on 8 December 2020 Permalink | Reply

        Finding a solution takes less than a second.

        I used the fact that psum has to be a multiple of 24 and has a minimum/maximum of 1080/1344.

        Biggest time gain seems to have come from replacing the psum definition from the sum of 24 variables to 6 times the sum of 4 variables.

        % A Solution in MiniZinc
        include "globals.mzn";
         
        % grid of Advent calendar doors
        % a b c d e f
        % g h i j k l
        % m n o p q r
        % s t u v w x
         
        % set of primes, excluding 2 as non viable for this puzzle
        set of int: primes = {3, 5, 7, 11, 13, 17, 19, 23,
        29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
        83, 89, 97, 101, 103, 107};
        
        % psum is a multiple of 24 as column total is a multiple of 4
        % (otherwise row total would be odd which is not possible)
        set of int: psums = {1080, 1104, 1128, 1152, 1176, 1200,
        1224, 1248, 1272, 1296, 1320, 1344};
         
        set of int: Digit = 3..107;
         
        % 24 prime numbers
        var Digit: a; var Digit: b; var Digit: c; var Digit: d;
        var Digit: e; var Digit: f; var Digit: g; var Digit: h; 
        var Digit: i; var Digit: j; var Digit: k; var Digit: l; 
        var Digit: m; var Digit: n; var Digit: o; var Digit: p; 
        var Digit: q; var Digit: r; var Digit: s; var Digit: t;
        var Digit: u; var Digit: v; var Digit: w; var Digit: x; 
         
        %var 1080..1344: psum = sum([a, b, c, d, e, f, g, h, i, j,
        % k, l, m, n, o, p, q, r, s, t, u, v, w, x]);
        var 1080..1344: psum = 6 * (a + g + m + s);
        constraint psum = 4 * (a + b + c + d + e + f);
        constraint psum in psums;
         
        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]);
         
        % allocate 24 primes
        constraint a in primes /\ b in primes /\ c in primes
        /\ d in primes /\ e in primes /\ f in primes;
         
        constraint g in primes /\ h in primes /\ i in primes
        /\ j in primes /\ k in primes /\ l in primes;
         
        constraint m in primes /\ n in primes /\ o in primes
        /\ p in primes /\ q in primes /\ r in primes;
         
        constraint s in primes /\ t in primes /\ u in primes
        /\ v in primes /\ w in primes;
         
        % put highest prime in Xmas Eve Box to fix grid
        constraint x == 107;
         
        % row totals add to the same value
        constraint (a + b + c + d + e + f) == (g + h + i + j + k + l)
        /\ (a + b + c + d + e + f) == (m + n + o + p + q + r)
        /\ (a + b + c + d + e + f) == (s + t + u + v + w + x);
        
        % column totals add to the same value
        constraint (a + g + m + s) == (b + h + n + t)
        /\ (a + g + m + s) == (c + i + o + u)
        /\ (a + g + m + s) == (d + j + p + v)
        /\ (a + g + m + s) == (e + k + q + w)
        /\ (a + g + m + s) == (f + l + r + x);
         
        % minimise total sum of prime numbers used
        solve minimize psum;
         
        % find unused primes in original max list of primes
        var set of int: digits_not_used = primes diff 
        {a, b, c, d, e, f, g, h, i, j,
         k, l, m, n, o, p, q, r, s, t, u, v, w, x};
         
        % output grid and grid row and column totals
        output ["  Grid1 is: " 
        ++ "\n " ++ show([a, b, c, d, e, f]) 
        ++ "\n " ++ show([g, h, i, j, k, l])
        ++ "\n " ++ show([m, n, o, p, q, r])
        ++ "\n " ++ show([s, t, u, v, w, x]) 
         
        ++ "\n Prime Sum overall = " ++ 
        show(sum([a, b, c, d, e, f, g, h, i, j,
        k, l, m, n, o, p, q, r, s, t, u, v, w, x]))
         
        ++ "\n Row sum = " ++ show(sum([a + b + c + d + e + f])) 
        ++ "\n Column sum = " ++ show(sum([a + g + m + s]))
        ++ "\n Unused primes : " ++ show(digits_not_used) ];
        

        Like

        • GeoffR 9:48 pm on 8 December 2020 Permalink | Reply

          Thanks to Frits for his optimisation of my code to make it run a lot faster.

          I have added an explanation of the range calculation for psum ie 1080..1344.

          I also found I could tidy code further by just using psum mod24 == 0. It was not necessary to use a list of prime sums in this revised code. It ran in about 0.6 sec.

          % A Solution in MiniZinc  - version 3
          include "globals.mzn";
            
          % grid of Advent calendar doors
          % a b c d e f
          % g h i j k l
          % m n o p q r
          % s t u v w x
            
          % set of primes, excluding 2 as non viable for this puzzle
          set of int: primes = {3, 5, 7, 11, 13, 17, 19, 23,
          29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
          83, 89, 97, 101, 103, 107};
           
          set of int: Digit = 3..107;
          
          % The minimum prime sum = sum of first 23 + 107 = 1068
          % The maximum prime sum = sum of last 24 = 1354
          % The prime sum (psum) = 4 * row_sum = 6 * column_sum
          % But, since the row and column sums are both even, psum 
          % is a multiple of both 8 and 12 and hence also of their 
          % lowest common multiple 24, giving 1080 <= psum <= 1344
          var 1080..1344: psum;      
          
          % 24 prime numbers
          var Digit: a; var Digit: b; var Digit: c; var Digit: d;
          var Digit: e; var Digit: f; var Digit: g; var Digit: h; 
          var Digit: i; var Digit: j; var Digit: k; var Digit: l; 
          var Digit: m; var Digit: n; var Digit: o; var Digit: p; 
          var Digit: q; var Digit: r; var Digit: s; var Digit: t;
          var Digit: u; var Digit: v; var Digit: w; var Digit: x; 
          
          constraint psum = 4 * (a + b + c + d + e + f)
                  /\ psum = 6 * (a + g + m + s) 
                  /\ psum mod 24 == 0;
            
          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]);
            
          % allocate 24 primes
          constraint a in primes /\ b in primes /\ c in primes
          /\ d in primes /\ e in primes /\ f in primes;
            
          constraint g in primes /\ h in primes /\ i in primes
          /\ j in primes /\ k in primes /\ l in primes;
            
          constraint m in primes /\ n in primes /\ o in primes
          /\ p in primes /\ q in primes /\ r in primes;
            
          constraint s in primes /\ t in primes /\ u in primes
          /\ v in primes /\ w in primes;
            
          % put highest prime in Xmas Eve Box to fix grid
          constraint x == 107;
            
          % row totals add to the same value
          constraint (a + b + c + d + e + f) == (g + h + i + j + k + l)
          /\ (a + b + c + d + e + f) == (m + n + o + p + q + r)
          /\ (a + b + c + d + e + f) == (s + t + u + v + w + x);
           
          % column totals add to the same value
          constraint (a + g + m + s) == (b + h + n + t)
          /\ (a + g + m + s) == (c + i + o + u)
          /\ (a + g + m + s) == (d + j + p + v)
          /\ (a + g + m + s) == (e + k + q + w)
          /\ (a + g + m + s) == (f + l + r + x);
            
          % minimise total sum of prime numbers used
          solve minimize psum;
            
          % find unused primes in original max list of primes
          var set of int: digits_not_used = primes diff 
          {a, b, c, d, e, f, g, h, i, j,
           k, l, m, n, o, p, q, r, s, t, u, v, w, x};
            
          % output grid and grid row and column totals
          output ["  Grid is: "
          ++ "\n " ++ show([a, b, c, d, e, f]) 
          ++ "\n " ++ show([g, h, i, j, k, l])
          ++ "\n " ++ show([m, n, o, p, q, r])
          ++ "\n " ++ show([s, t, u, v, w, x]) 
            
          ++ "\n Prime Sum overall = " ++
          show(sum([a, b, c, d, e, f, g, h, i, j,
          k, l, m, n, o, p, q, r, s, t, u, v, w, x]))
            
          ++ "\n Row sum = " ++ show(sum([a + b + c + d + e + f])) 
          ++ "\n Column sum = " ++ show(sum([a + g + m + s]))
          ++ "\n Unused primes : " ++ show(digits_not_used) ];
          
          
          
          
          
          

          Like

      • Frits 1:48 pm on 8 December 2020 Permalink | Reply

        Another program using many nested loops.

        from itertools import product as prod
        
        # Prime numbers up to 107 
        Pr =  [2, 3, 5, 7]
        Pr += [x for x in range(11, 100, 2) if all(x % p for p in Pr)]
        Pr += [x for x in range(101, 108, 2) if all(x % p for p in Pr)]
        
        # sum has to be a multiple of 24 
        # (if column sum is not a multiple of 4 then the row sum will be odd)
        min1 = sum(Pr[1:24]) + 107
        min1 = [x for x in range(min1, min1 + 24) if x % 24 == 0][0]
        max1 = sum(Pr[-24:])
        max1 = [x for x in range(max1 - 23, max1 + 1) if x % 24 == 0][0]
        
        Pr = Pr[1:-1]              # exclude 2 and 107
        
        sumPr = sum(Pr + [107])
        lenPr = len(Pr + [107])
        
        # make sure loop variable value is not equal to previous ones
        def domain(v):
          # find already used loop values  ...
          vals = set()
          # ... by accessing previously set loop variable names
          for s in lvd[v]:
            vals.add(globals()[s])
        
          return [x for x in Pr2 if x not in vals]
          
        # decompose <t> into <k> increasing numbers from <ns>
        # so that sum(<k> numbers) equals <t>
        def decompose(t, k, ns, s=[], used=[], m=1):
          if k == 1:
            if t in ns and not(t in s or t in used) :
              if not(t < m): 
                yield s + [t]
          else:
            for (i, n) in enumerate(ns):
              if not(n < t): break
              if n in s or n in used: continue
              if (n < m): continue
              yield from decompose(t - n, k - 1, ns[i:], s + [n], used, n)
        
        # pick <k> elements from list <li> so that all combined fields are different
        def uniqueCombis(k, li, s=[]):
          if k == 0:
            yield s
          else:
            for i in range(len(li)):
              if len(s + li[i]) == len(set(s + li[i])):
                yield from uniqueCombis(k - 1, li[i:], s + li[i])
              
        # check if sums are the same for all columns
        def checkColSums(rs, t):
          correctSumList = [list(p) for p in prod(*rs) if sum(p) == t]
          for u in uniqueCombis(6, correctSumList): 
            yield [u[0:4], u[4:8], u[8:12], u[12:16], u[16:20], u[20:]] 
            break       
                
                
        # set up dictionary of for-loop variables
        lv = ["A","B","C","D","E","F","G","H","I","J","K","L",
              "M","N","O","P","Q","R","S","T","U","V","W","X"]
        lvd = {v: lv[:i] for i, v in enumerate(lv)}        
        
        # check sums by starting with smallest 
        for T in [x for x in range(min1, max1 + 1) if x % 24 == 0]:
          dif = sumPr - T
          rsum = T // 4
          csum = T // 6
          print("\nTotal sum",T, "row sum",rsum, "col sum",csum, "difference", dif)
          
          # check which primes are to be dropped
          c = 0
          for di in decompose(dif, lenPr - 24, Pr): 
            if c == 0:
              Pr2 = [x for x in Pr if x not in di] 
            c += 1  
            
          if c > 1:           # more possibilities to drop primes
            Pr2 = list(Pr)
          
          print(f"\nPrimes to check = {Pr2}")
          
          for A in Pr2:
           for B in domain('B'):
            if B < A: continue
            for C in domain('C'):
             if C < B: continue
             for D in domain('D'):
              if D < C: continue
              for E in domain('E'):
               if E < D: continue
               for F in [107]:
                RSUM = sum([A,B,C,D,E,F])
                if RSUM < min1 // 4 or RSUM > max1 // 4 or RSUM % 6 != 0: continue
                for G in domain('G'):
                 for H in domain('H'):
                  if H < G: continue
                  for I in domain('I'):
                   if I < H: continue
                   for J in domain('J'):
                    if J < H: continue
                    for K in domain('K'):
                     if K < J: continue
                     L = RSUM - sum([G,H,I,J,K])
                     if L < K or L not in Pr2: continue
                     if L in {A,B,C,D,E,F,G,H,I,J,K}: continue
                     for M in domain('M'):
                      for N in domain('N'):
                       if N < M: continue
                       for O in domain('O'):
                        if O < N: continue
                        for P in domain('P'):
                         if P < O: continue
                         for Q in domain('Q'):
                          if Q < P: continue
                          R = RSUM - sum([M,N,O,P,Q])
                          if R < Q or R not in Pr2: continue
                          if R in {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q}: continue
                          for S in domain('S'):
                           for T in domain('T'):
                            if T < S: continue
                            for U in domain('U'):
                             if U < T: continue
                             for V in domain('V'):
                              if V < U: continue
                              for W in domain('W'):
                               if W < V: continue
                               X = RSUM - sum([S,T,U,V,W])
                               if X < W or X not in Pr2: continue
                               if X in {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W}:
                                 continue
                               rs = [[A,B,C,D,E,F],[G,H,I,J,K,L],
                                     [M,N,O,P,Q,R],[S,T,U,V,W,X]]
                               CSUM = (RSUM * 2) // 3
                               
                               # select columns, each sums to CSUM
                               for cs in checkColSums(rs, CSUM):
                                print("\nSolution: \n")
                                for r in zip(*cs[::-1]):        # rotate matrix
                                 for x in r:
                                  print(f"{x:>3}", end = " ")
                                 print() 
                                exit(0)
        

        Like

    • GeoffR 7:41 pm on 8 December 2020 Permalink | Reply

      I get an error on the Idle and Wing IDE’s when I try to run this code:

      i.e Syntax Error: too many statically nested blocks

      Is there an easy fix?

      Like

      • Jim Randell 7:59 pm on 8 December 2020 Permalink | Reply

        @Geoff: There is a limit of 20 nested loops in the standard Python interpreter. But the PyPy interpreter doesn’t have this limit, so you can use it to execute code with lots of nested loops.

        Like

  • Jim Randell 1:54 pm on 27 November 2020 Permalink | Reply
    Tags:   

    Teaser 3036: That old chestnut 

    From The Sunday Times, 29th November 2020 [link]

    Clearing out an old drawer I found a wrinkled conker. It was my magnificent old 6709-er, a title earned by being the only survivor of a competition that I had had with friends. The competition had started with five conkers, veterans of many campaigns; each had begun at a different value between 1300 and 1400.

    We used the rule that if an m-er beat an n-er in an encounter (by destroying it, of course!) the m-er would become an m+n+1-er; in effect, at any time the value of a conker was the number of destroyed conkers in all confrontations in its “ancestry”.

    I recall that at the beginning of, and throughout, the competition, the value of every surviving conker was a prime number.

    What were the values of the five conkers at the start?

    [teaser3036]

     
    • Jim Randell 2:10 pm on 27 November 2020 Permalink | Reply

      There are 5 conkers (with values, say A, B, C, D, E), and there are 4 matches where one conker is destroyed in each match. The ultimate winner ending up with a value of (A + B + C + D + E + 4), and we know this value is 6079.

      This Python 3 program runs in 49ms.

      from enigma import Primes, subsets, printf
      
      # target for the champion
      T = 6709
      
      # for checking primes
      primes = Primes(T)
      
      # play values against each other until there is an ultimate winner
      def solve(vs, ss=[]):
        # are we done?
        if len(vs) == 1:
          yield ss
        # choose 2 conkers to play
        for ((i, m), (j, n)) in subsets(enumerate(vs), size=2):
          v = m + n + 1
          if v in primes:
            yield from solve(vs[:i] + vs[i + 1:j] + vs[j + 1:] + [v], ss + [(m, n)])
            
      
      # choose 5 initial primes values between 1300 and 1400
      for vs in subsets(primes.irange(1300, 1400), size=5):
        if sum(vs) + 4 != T: continue
        # check for a possible sequence of matches
        for ss in solve(list(vs)):
          # output solution
          printf("{vs} -> {ss}")
          break # we only need one possibility
      

      Solution: The values of the five starting conkers were: 1301, 1303, 1361, 1367, 1373.

      The conkers are:

      A = 1301
      B = 1303
      C = 1361
      D = 1367
      E = 1373

      And one possible sequence of matches is:

      A vs C → AC = 2663
      D vs E → DE = 2741
      AC vs B → ABC = 3967
      ABC vs DE → ABCDE = 6709

      An alternative sequence is:

      B vs E → BE = 2677
      C vs D → CD = 2729
      BE vs CD → BCDE = 5407
      A vs BCDE → ABCDE = 6709

      Note that by selecting pairs of conkers for battle by index (rather than value) we ensure that the program works even if more than one conker has the same value. It turns out that in the solution sequence all the conkers do have different values, so it is possible to get the correct answer with a less rigorous program.

      Like

      • Jim Randell 12:49 pm on 14 December 2020 Permalink | Reply

        Here’s a solution using [[ multiset() ]] from the enigma.py library, which is a bit neater than using indices (and also more efficient).

        This Python 3 program runs in 44ms.

        from enigma import Primes, subsets, multiset, ordered, printf
        
        # target for the champion
        T = 6709
        
        # for checking primes
        primes = Primes(T)
        
        # play values against each other until there is an ultimate winner
        def solve(vs, ss=[]):
          # are we done?
          if len(vs) == 1:
            yield ss
          # choose 2 conkers to play
          for (m, n) in subsets(vs, size=2, select="mC"):
            v = m + n + 1
            if v in primes:
              yield from solve(vs.difference((m, n)).add(v), ss + [ordered(m, n)])
        
        # choose 5 initial primes values between 1300 and 1400
        for vs in subsets(primes.irange(1300, 1400), size=5):
          if sum(vs) + 4 != T: continue
          # check for a possible sequence of matches
          for ss in solve(multiset(vs)):
            # output solution
            printf("{vs} -> {ss}")
            break # we only need one possibility
        

        Like

    • Frits 5:58 pm on 28 November 2020 Permalink | Reply

      2 encounters are enough to filter out a unique solution (we have been told there is a solution).
      Coding more encounters would have resulted in an even more messy code.

      from enigma import SubstitutedExpression, is_prime
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [ 
        # 5 increasing prime numbers between 1300 and 1400
        "is_prime(1300 + AB)",
        "CD > AB",
        "is_prime(1300 + CD)",
        "EF > CD",
        "is_prime(1300 + EF)",
        "GH > EF",
        "is_prime(1300 + GH)",
        "IJ > GH",
        "is_prime(1300 + IJ)",
        
        # winner has value of (A + B + C + D + E + 4), has to be 6709.
        "AB + CD + EF + GH + IJ == 205",
       
       # 1st encounter 
        "is_prime(2601 + V*AB + W*CD + X*EF + Y*GH + Z*IJ)",
        
        # 1st encounter : pick 2
        "V + W + X + Y + Z == 2",
        
        # 2nd encounter 
        "is_prime(1301 + \
                  (1 - P)*1300 + P*(2601 + V*AB + W*CD + X*EF + Y*GH + Z*IJ) + \
                  Q*(1-V)*AB + R*(1-W)*CD + S*(1-X)*EF + T*(1-Y)*GH + U*(1-Z)*IJ)",
                  
        # 2nd encounter: pick exactly 2          
        "P + Q*(1-V) + R*(1-W) + S*(1-X) + T*(1-Y) + U*(1-Z) == 2",    
        
        # limit number of same solutions
        "Q * V == 0",        # force Q to be 0 if V equals 1
        "R * W == 0",        # force R to be 0 if W equals 1
        "S * X == 0",        # force S to be 0 if X equals 1
        "T * Y == 0",        # force T to be 0 if Y equals 1
        "U * Z == 0",        # force U to be 0 if Z equals 1
        ],
        answer="AB, CD, EF, GH, IJ, 2601 + V*AB + W*CD + X*EF + Y*GH + Z*IJ, \
                1301 + (1 - P)*1300 + P*(2601 + V*AB + W*CD + X*EF + Y*GH + Z*IJ) + \
                Q*(1-V)*AB + R*(1-W)*CD + S*(1-X)*EF + T*(1-Y)*GH + U*(1-Z)*IJ, \
                P,Q,R,S,T,U,V,W,X,Y,Z",
        d2i={k:"PQRSTUVWXYZ" for (k) in range(2,10)},
        distinct="",
        verbose=0)   
      
      # Print answers 
      prev = ""
      print("   I    II    III   IV     V    e1    e2   "
            "P, Q, R, S, T, U, V, W, X, Y, Z]")
      for (_, ans) in p.solve():
        if ans[:5] != prev:
          print([x if i > 4 else x + 1300 for (i, x) in enumerate(ans)])
        prev = ans[:5]
      

      Like

  • Jim Randell 4:25 pm on 20 November 2020 Permalink | Reply
    Tags:   

    Teaser 3035: Friend of the Devil 

    From The Sunday Times, 22nd November 2020 [link]

    My friend, “Skeleton” Rose, rambled on with me and my uncle (“The Devil” and “Candyman”) about Mr Charlie, who gave, between us, three identical boxes of rainbow drops.

    Each identical box’s card template had a white, regular convex polygonal base section with under ten sides, from each of which a similar black triangular star point extended. All these dark star points folded up to an apex, making an enclosed box.

    The number of sweets per box equalled the single-figure sum of its own digits times the sum of the star points and the box’s faces and edges. If I told you how many of the “star point”, “face” and “edge” numbers were exactly divisible by the digit sum, you would know this number of sweets.

    How many sweets were there in total?

    [teaser3035]

     
    • Jim Randell 4:52 pm on 20 November 2020 Permalink | Reply

      If the base of the box is a k-gon (so 3 ≤ k < 10), then there are k “star points” and the closed box forms a polyhedron with (k + 1) faces and 2k edges.

      So if there are n sweets in the box, we have:

      n = dsum(n) × (k + (k + 1) + 2k)
      ⇒ k = ((n / dsum(n)) − 1) / 4

      The largest possible digit sum is 9, and the largest possible value for k is also 9, so the maximum value for n is 9×(4×9 + 1) = 333.

      This Python program considers sweet numbers (up to 333) and finds numbers unique by the given measure. It runs in 45ms.

      Run: [ @repl.it ]

      from enigma import irange, nsplit, div, unpack, filter_unique, printf
      
      # generate possible numbers of sweets
      def sweets(N=333):
        # consider numbers of sweets (n)
        for n in irange(1, N):
          # calculate the digit sum of n
          d = sum(nsplit(n))
          if d > 9: continue
          # calculate the number of sides of the polygon
          k = div(n - d, 4 * d)
          if k is None or k < 3 or k > 9: continue
          # measure = how many of (k, k + 1, 2k) are divisible by d
          m = sum(x % d == 0 for x in (k, k + 1, 2 * k))
          yield (n, m)
      
      # find values for n, unique by measure m
      r = filter_unique(sweets(), unpack(lambda n, m: m), unpack(lambda n, m: n))
      
      # output solution
      for (n, m) in r.unique:
        printf("n={n} [m={m}]")
      

      Solution: There were 666 sweets in total.

      There are 222 sweets in each of the three boxes.

      The digit sum of 222 is 6.

      The base of each box is a regular nonagon (9 sides), so the number of star points is 9, the number of faces of the shape formed by the (closed) box is 10, and the number of edges is 18.

      The digit sum (6), multiplied by the sum of the star points (9), faces (10), and edges (18) = 6×(9 + 10 + 18) = 6×37 = 222, the same as the number of sweets in the box.

      And this is the only case where just one the three summands (edges = 18) is divisible by the digit sum (6).

      There are 8 candidate numbers of sweets, grouped by the shape of the boxes:

      k=3: n=117
      k=4: n=153
      k=6: n=150, 225
      k=7: n=261
      k=9: n=111, 222, 333

      Like

      • Jim Randell 9:08 am on 21 November 2020 Permalink | Reply

        Here is a more efficient version, that also does not need the upper bound on the number of sweets.

        Run: [ @repl.it ]

        from enigma import irange, nsplit, unpack, filter_unique, printf
        
        # generate possible numbers of sweets
        def sweets():
          # consider number of sides of the polygon (k)
          for k in irange(3, 9):
            # consider possible digit sums (d)
            for d in irange(1, 9):
              # calculate number of sweets (n)
              n = d * (4 * k + 1)
              # check the digit sum of n
              if sum(nsplit(n)) != d: continue
              # measure = how many of (k, k + 1, 2k) are divisible by d
              m = sum(x % d == 0 for x in (k, k + 1, 2 * k))
              yield (n, m)
        
        # find values for n, unique by measure m
        r = filter_unique(sweets(), unpack(lambda n, m: m), unpack(lambda n, m: n))
        
        # output solution
        for (n, m) in r.unique:
          printf("n={n} [m={m}]")
        

        Like

  • Jim Randell 5:07 pm on 13 November 2020 Permalink | Reply
    Tags:   

    Teaser 3034: Reservoir development 

    From The Sunday Times, 15th November 2020 [link]

    A straight track from an observation post, O, touches a circular reservoir at a boat yard, Y, and a straight road from O meets the reservoir at the nearest point, A, with OA then extended by a bridge across the reservoir’s diameter to a disembarking point, B. Distances OY, OA and AB are whole numbers of metres, with the latter two distances being square numbers.

    Following development, a larger circular reservoir is constructed on the other side of the track, again touching OY at Y, with the corresponding new road and bridge having all the same properties as before. For both reservoirs, the roads are shorter than 500m, and shorter than their associated bridges. The larger bridge is 3969m long.

    What is the length of the smaller bridge?

    [teaser3034]

     
    • Jim Randell 5:44 pm on 13 November 2020 Permalink | Reply

      We can solve this puzzle using applications of Pythagoras’ Theorem.

      This Python program runs in 47ms.

      Run: [ @repl.it ]

      from enigma import powers, div, is_square, printf
      
      # difference of 2 squares
      diff_sq = lambda x, y: (x + y) * (x - y)
      
      # length of the larger bridge (= B)
      B = 3969
      
      # consider the length of the road to the larger reservoir (= R)
      for R in powers(1, 22, 2):
        # calculate distance OY (= t)
        t2 = is_square(diff_sq(B + 2 * R, B))
        if t2 is None: continue
        t = div(t2, 2)
        if t is None: continue
      
        # consider length of the road to the smaller reservior (= r)
        for r in powers(1, 22, 2):
          # calculate the length of the bridge over the smaller reservoir (= b)
          b = div(diff_sq(t, r), r)
          if b is None or not(r < b < B and is_square(b)): continue
      
          # output solution
          printf("B={B} R={R}, t={t}, r={r} b={b}")
      

      Solution: The smaller bridge is 2304 m long.

      The layout looks like this:

      And the puzzle can be solved by considering the right-angled triangles OYX’ and OYX.

      The calculated distances are:

      OY = 1040 m
      OA = 400 m (20²)
      AB = 2304 m (48²)
      OA’ = 256 m (16²)
      A’B’ = 3969 m (63²)

      Like

      • Jim Randell 2:29 pm on 14 November 2020 Permalink | Reply

        Or, with a bit more analysis:

        from enigma import irange, inf, is_square, div, printf
        
        # length of the larger bridge (= B)
        B = 3969 # = 63^2
        
        # consider increasing squares (larger than B)
        for z in irange(64, inf):
          # calculate length of the road to the larger reservoir (= R)
          R = z * z - B
          if not(R < 500): break
          # calculate the length of the track OY (= t)
          t = is_square(R)
          if t is None: continue
          t *= z
        
          # consider length of the road to the smaller reservoir (= r)
          for j in irange(1, 22):
            r = j * j 
            # calculate the length of the bridge over the smaller reservoir (= b)
            b = div((t + r) * (t - r), r)
            if b is None or not(r < b < B and is_square(b)): continue
        
            # output solution
            printf("B={B} R={R}, t={t}; r={r} b={b}")
        

        Like

    • Tony Brooke-Taylor 11:34 am on 17 November 2020 Permalink | Reply

      I first did this assuming that (using your notation) R+B also had to be a square. If I interpret your code correctly, I think that is also what you have done. I got the same value for R as your code produces. Following this through you get a unique solution for r. However, on reflection I don’t think the puzzle applies that constraint. In the puzzle’s notation, that would require OB and its equivalent to be squares, which I cannot see in the puzzle. If I relax the constraint I get three solutions. I am guessing that either the puzzle requires the addition of that constraint or I cannot read, but the more interesting question for me is whether or not it is more than a coincidence that the unique solution has that additional property.

      Like

      • Jim Randell 11:56 am on 17 November 2020 Permalink | Reply

        @Tony: Thanks for your comment.

        We don’t need to assume that (R + B) is a perfect square (and the puzzle doesn’t tell us that), but it follows from considering the right-angled triangle OYX’ (where X’ is the centre point of the larger reservoir).

        We have (where integer t is the length of the track OY):

        t² + (B/2)² = (R + B/2)²
        ⇒ t² = R(R + B)

        Now, we are told that R is a square number, and obviously t² is, so it follows that (R + B) must also be a perfect square.

        Like

    • Tony Brooke-Taylor 6:31 pm on 17 November 2020 Permalink | Reply

      Thanks Jim. The constraint I had failed to apply was that t must be an integer.

      Like

    • Frits 9:20 pm on 17 November 2020 Permalink | Reply

      from enigma import SubstitutedExpression
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
         # PQRS = track OY, AE = sqrt(road OA), BX = sqrt(AB), FGH = road OC 
         # X is center of smaller reservoir
         
         # roads are shorter than 500m
         "AE > 0 and AE < 23",
         
         # roads are shorter than their associated bridges 
         "AE < BX",
         
         # one diameter is larger
         "BX > 0 and BX**2 < 3969",
       
         "PQRS > 0",
         
         # Pythagoras: OY^2 + YX^2 = (OA + YX)^2
         # so OY^2 = OA^2 + OA*AB
         "PQRS**2 == AE**4 + AE**2 * BX**2",
         
         "FGH < 500",
         # one road is longer
         "FGH < AE**2",
            
         # Pythagoras: OY^2 + (3969/2)^2 = ((3969/2) + OC)^2
         "PQRS**2 + 3938240.25 == (1984.5 + FGH)**2", 
        ],
        answer="BX**2, AE**2, PQRS, FGH",
        d2i={},
        distinct="",
        reorder=0,
        verbose=256)   
      
      # Print answers 
      print("Large bridge  small bridge  long road  track  short road")
      for (_, ans) in p.solve():
        print(f"    3969          {ans[0]}         {ans[1]}       {ans[2]}"
              f"     {ans[3]}")
      

      Like

  • Jim Randell 4:38 pm on 6 November 2020 Permalink | Reply
    Tags:   

    Teaser 3033: Goldilocks and the bear commune 

    From The Sunday Times, 8th November 2020 [link]

    In the bears’ villa there are three floors, each with 14 rooms. The one switch in each room bizarrely toggles (on ↔ off) not only the single light in the room but also precisely two other lights on the same floor; moreover, whenever A toggles B, then B toggles A.

    As Goldilocks moved from room to room testing various combinations of switches, she discovered that on each floor there were at least two separate circuits and no two circuits on a floor had the same number of lights. Furthermore, she found a combination of 30 switches that turned all 42 lights from “off” to “on”, and on one floor she was able turn each light on by itself.

    (a) How many circuits are there?
    (b) How many lights are in the longest circuit?

    [teaser3033]

     
    • Jim Randell 5:47 pm on 6 November 2020 Permalink | Reply

      (See also: Puzzle #51, Enigma 1137, Enigma 1127).

      I think there are multiple solutions to this puzzle. Although if no floor is allowed to have the same configuration of circuits as another floor, then I think we can find a unique solution:

      If each light is connected to two other lights, then they must form a circular arrangement (like the candles in Puzzle #51).

      In a circuit where the number of lights is a multiple of 3, the lights can be toggled by switching the central light in each non-overlapping consecutive group of three. Otherwise the lights can be toggled by operating each switch once. Each light is toggled 3 times, so ends up in the opposite state.

      Only in those circuits where the number of lights is not a multiple of 3 can a single light be illuminated. And if one single light can be illuminated, then all the others in that circuit can also be illuminated singly.

      This Python program finds decompositions of 14 into 2 or more different circular circuits; finds those sets that require 30 switches to be operated to toggle every light; and also one of the sets must be composed entirely of circuits that do not consist of a multiple of 3 lights.

      It runs in 49ms.

      Run: [ @repl.it ]

      from enigma import irange, subsets, flatten, printf
      
      # decompose t into increasing numbers
      def decompose(t, m=3, ns=[]):
        if t == 0:
          if len(ns) > 1:
            yield ns
        else:
          for n in irange(m, t):
            yield from decompose(t - n, n + 1, ns + [n])
      
      # number of switches required for circuit with k lights
      def count(k):
        (n, r) = divmod(k, 3)
        return (n if r == 0 else k)
      
      # find 3 splits of 14
      for ss in subsets(decompose(14), size=3, select="C"):
        # sum the number of switches required
        ks = flatten(ss)
        t = sum(count(k) for k in ks)
        if t != 30: continue
        # and one floor must not contain a multiple of 3
        if all(any(k % 3 == 0 for k in s) for s in ss): continue
        # output solution
        a = len(ks)
        b = max(ks)
        printf("{a} circuits; longest = {b}; {ss}")
      

      Solution: (a) There are 7 circuits; (b) There are 10 lights in the longest circuit.

      The three configurations are: (3, 5, 6), (4, 10), (5, 9).

      The (4, 10) configuration requires switches to be operated 14 times to toggle the state of all lights, and in each circuit it is possible to illuminate the lights individually.

      The (3, 5, 6) and (5, 9) configurations, both require switches to be operated 8 times to toggle the state of all lights, and it is not possible to illuminate single lights in the 3, 6 or 9 circuits.

      If we are allowed to use the same configuration of circuits on 2 different floors, then there are two further solutions:

      (3, 5, 6), (3, 5, 6), (4, 10)
      (5, 9), (5, 9), (4, 10)

      The other solutions can be found by changing the select parameter at line 18 to [[ select="R" ]].

      The number of lights in the longest circuit is the same for all solutions. But the total number of circuits differs in each case.

      Like

    • Frits 12:44 pm on 8 November 2020 Permalink | Reply

      @Jim,

      “and on one floor she was able turn each light on by itself” and line 24.

      I don’t see this as “on at least one floor”.

      Like

      • Jim Randell 1:02 pm on 8 November 2020 Permalink | Reply

        @Frits: Unless the puzzle says “exactly one” (or “precisely one”, or “only one”, etc) I usually treat such statements as “at least one”. In this case “at least one” or “exactly one” will lead to the same solution(s).

        Like

  • Jim Randell 9:49 am on 30 October 2020 Permalink | Reply
    Tags:   

    Teaser 3032: Darts display 

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

    I noticed a dartboard in a sports shop window recently. Three sets of darts were positioned on the board. Each set was grouped as if the darts had been thrown into adjacent numbers (e.g., 5, 20, 1) with one dart from each set in a treble. There were no darts in any of the doubles or bulls.

    The darts were in nine different numbers but the score for the three sets was the same. If I told you whether the score was odd or even you should be able to work out the score. The clockwise order of numbers on a dartboard is:

    20, 1, 18, 4, 13, 6, 10, 15, 2, 17, 3, 19, 7, 16, 8, 11, 14, 9, 12, 5

    What was the score that all three sets of darts made?

    [teaser3032]

     
    • Jim Randell 10:05 am on 30 October 2020 Permalink | Reply

      This Python program runs in 49ms.

      Run: [ @repl.it ]

      from collections import defaultdict
      from enigma import tuples, unpack, subsets, union, filter_unique, printf
      
      # the scores on the dartboard
      board = (20, 1, 18, 4, 13, 6, 10, 15, 2, 17, 3, 19, 7, 16, 8, 11, 14, 9, 12, 5)
      
      # group possible scores together
      d = defaultdict(list)
      for (a, b, c) in tuples(board, 3, circular=1):
        for k in (3 * a + b + c, a + 3 * b + c, a + b + 3 * c):
          d[k].append((a, b, c))
      
      # find scores with three disjoint sets of sectors
      rs = list()
      for (k, vs) in d.items():
        for sss in subsets(vs, size=3):
          if len(union(sss)) == 9:
            rs.append((k, sss))
      
      # find scores unique by parity
      rs = filter_unique(rs, unpack(lambda k, sss: k % 2), unpack(lambda k, sss: k)).unique
      
      # output solution
      for (k, sss) in rs:
        printf("score = {k} {sss}")
      

      Solution: The score was 56.

      The three groups of darts are:

      2; treble 17; 3
      19; treble 7; 16
      treble 11; 14; 9

      This is the only disjoint collection with an even score.

      It is possible to make odd scores of 43, 47, 61.

      And the score of 61 can be made in 4 different ways, so is the answer to a variation on the puzzle where: “if I told you the score, you still wouldn’t be able to work out the set of sectors where the darts were placed”.

      Like

  • Jim Randell 4:43 pm on 23 October 2020 Permalink | Reply
    Tags:   

    Teaser 3031: End of the beginning 

    From The Sunday Times, 25th October 2020 [link]

    Jenny is using her calculator, which accepts the input of numbers of up to ten digits in length, to prepare her lesson plan on large numbers. She can’t understand why the results being shown are smaller than she expected until she realizes that she has entered a number incorrectly.

    She has entered the number with its first digit being incorrectly entered as its last digit. The number has been entered with its second digit first, its third digit second etc. and what should have been the first digit entered last. The number she actually entered into her calculator was 25/43rds of what it should have been.

    What is the correct number?

    [teaser3031]

     
    • Jim Randell 4:59 pm on 23 October 2020 Permalink | Reply

      See also: Enigma 1036, Enigma 1161, Teaser 2565.

      If we have a number, where the leading digit is a and the remaining k digits are bcdefg… = r, then we have:

      r.10 + a = (25/43)(a.10^k + r)

      The following Python program runs in 45ms.

      Run: [ @repl.it ]

      from enigma import irange, div, int2base, printf
      
      # consider k digit numbers
      for k in irange(1, 9):
        m = 10 ** k
        # consider possible leading digit
        for a in irange(1, 9):
          r = div(a * (25 * m - 43), 405)
          if r is None or not(r < m): continue
          # output solution
          printf("{a}{r} -> {r}{a}", r=int2base(r, width=k))
      

      Solution: The correct number is: 530864197.

      So the number entered is: 308641975.

      >>> fraction(308641975, 530864197)
      (25, 43)
      

      For this particular puzzle we can do some analysis can reduce the solution space further. (From the 9×9 = 81 cases to consider in the general case).

      In the equation:

      43(r.10 + a) = 25(a.10^k + r)

      we see that that each side is divisible by 5, so a must be 5 (as it cannot be 0).

      Which leaves:

      r = (25.10^k − 43) / 81

      Which we can then check with the 9 possible values for k manually or with an even shorter program:

      from enigma import irange, div, int2base, printf
      
      for k in irange(1, 9):
        r = div(25 * 10 ** k - 43, 81)
        if r is not None:
          printf("5{r} -> {r}5", r=int2base(r, width=k))
      

      Or, for a complete manual solution:

      Numbers of the form: (25.10^k − 43) / 9, look like this:

      k=1: 23
      k=2: 273
      k=3: 2773
      k=4: 27773

      To divide by 9 again we need the number to have a digital root of 9, and the only one in the required range is:

      k=8: 277777773

      Dividing this by 9 gives:

      r = 277777773 / 9 = 30864197

      Hence the correct number is 530864197, and the incorrect number 308641975.

      Like

      • hans droog 10:01 am on 6 November 2020 Permalink | Reply

        Hi Jim. would be obliged if you could explain formula in teaser 3031. Many thanks, Hans Droog

        Like

        • Jim Randell 10:10 am on 6 November 2020 Permalink | Reply

          @hans:

          As an example, if we had an 7 digit number abcdefg which was entered incorrectly on the calculator as bcdefga, then we would have:

          bcdefga = (25/43)(abcdefg)

          If we represent the 6 digit number bcdefg as r we can write this expression as:

          r.10 + a = (25/43)(a.10^6 + r)

          The expression I give in my solution is the general case when r is a k digit number.

          (“.” is multiplication. “^” is exponentiation).

          Is that clear?

          Like

    • Frits 1:42 pm on 24 October 2020 Permalink | Reply

      Similar.

      print(["5"+str(lastpart // 81) for k in range(2, 10) 
            if (lastpart := (25 * 10**k - 43)) % 81 == 0][0])
      

      Like

    • Hugh Casement 4:15 pm on 7 November 2020 Permalink | Reply

      Hans may have been put off by Jim’s use of a decimal point to mean multiplication.
      The international convention is a raised dot.

      Like

      • Jim Randell 10:13 am on 8 November 2020 Permalink | Reply

        If I were handwriting a decimal number I would use a “middle dot” for the decimal point, and a dot on the line to denote multiplication. Of course when typing the “.” (full stop) symbol has to do for both.

        Fortunately we don’t often have to deal with numbers with decimal points in puzzles.

        Like

    • hans droog 9:01 am on 8 November 2020 Permalink | Reply

      thats right Hugh

      Like

  • Jim Randell 4:44 pm on 16 October 2020 Permalink | Reply
    Tags:   

    Teaser 3030: Pot success 

    From The Sunday Times, 18th October 2020 [link]

    In snooker, pot success (PS) is the percentage of how many pot attempts have been successful in that match (e.g. 19 pots from 40 attempts gives a PS of 47.5%). In a recent match, my PS was a whole number at one point. I then potted several balls in a row to finish a frame, after which my improved PS was still a whole number. At the beginning of the next frame, I potted the same number of balls in a row, and my PS was still a whole number. I missed the next pot, my last shot in the match, and, remarkably, my PS was still a whole number.

    If I told you how many balls I potted during the match, you would be able to work out those various whole-number PS values.

    How many balls did I pot?

    [teaser3030]

     
    • Jim Randell 5:03 pm on 16 October 2020 Permalink | Reply

      This Python program runs in 46ms.

      Run: [ @repl.it ]

      from enigma import irange, div, peek, printf
      
      # calculate PS
      PS = lambda p, t: div(100 * p, t)
      
      # generate scenarios with p balls potted (at the end)
      def generate(p):
        # consider total number of attempts (at the end)
        for t in irange(p + 1, 100):
          # final PS (ps4)
          ps4 = PS(p, t)
          if ps4 is None: continue
          # last shot was a miss, and the PS before it (ps3)
          ps3 = PS(p, t - 1)
          if ps3 is None: continue
          # before that 2 lots of k balls were potted
          for k in irange(2, (p - 1) // 2):
            ps2 = PS(p - k, t - 1 - k)
            if ps2 is None: continue
            ps1 = PS(p - 2 * k, t - 1 - 2 * k)
            if ps1 is None or not(ps1 < ps2): continue
            # return (t, k, PS) values
            yield (t, k, (ps1, ps2, ps3, ps4))
      
      # consider number of balls potted (at the end)
      for p in irange(5, 99):
        # accumulate ps values
        s = set(ps for (t, k, ps) in generate(p))
        # is there only one?
        if len(s) == 1:
          # output solution
          printf("balls potted = {p} -> PS = {ps}", ps=peek(s))
      

      Solution: You potted 13 balls.

      This corresponds to the following scenario:

      13 balls potted (2 runs of 5), PS = (3/15 = 20%; 8/20 = 40%; 13/25 = 52%; 13/26 = 50%)

      The other possible scenarios are:

      12 balls potted (2 runs of 5), PS = (2/5 = 40%; 7/10 = 70%; 12/15 = 80%; 12/16 = 75%)
      12 balls potted (2 runs of 4), PS = (4/16 = 25%; 8/20 = 40%; 12/24 = 50%; 12/25 = 48%)

      57 balls potted (2 runs of 15), PS = (27/45 = 60%; 42/60 = 70%; 57/75 = 76%; 57/76 = 75%)
      57 balls potted (2 runs of 25), PS = (7/28 = 25%; 32/50 = 64%; 57/75 = 76%; 57/76 = 75%)

      It seems plausible that these could correspond to a snooker match (it is possible to pot 10 reds + 10 colours + 6 colours = 26 balls in one frame, and we know at least 2 frames are involved). Although if just one of them did not, then the other scenario would provide a further solution.

      The program ensures that the PS values we are considering are non-zero, but allowing the initial PS to be zero gives a further solution:

      18 balls potted (2 runs of 9), PS = (0/6 = 0%; 9/15 = 60%; 18/24 = 75%; 18/25 = 72%)

      Like

    • Frits 11:06 am on 17 October 2020 Permalink | Reply

      @Jim, I think you should also consider p=4 as ps1 might be zero and zero also is a whole number .

      Also if t would be (p + 1) then ps1, ps2 and ps3 would be 100 and ps2 would not be higher than ps1.
      If you start t from (p+ 2) you don’t have to code the ps1 < ps2 check as it will always be the case.

      Of course there always is a balance between efficiency and seeing right away that the code solves the requirements.

      Like

      • Jim Randell 11:50 am on 17 October 2020 Permalink | Reply

        @Frits: Unfortunately the term “whole number” isn’t precise. It can be used to mean the integers, the non-negative integers, or just the positive integers.

        For this puzzle I took it to be the positive integers (which gets around a possible problem when considering PS values of 0), so I didn’t have to consider PS values of zero. Which is probably what the setter intended, as I’m sure the puzzle is meant to have a unique solution.

        I also wanted to make the [[ ps1 < ps2 ]] condition explicit in the code (as without it there would be further solutions – which can be seen by removing the test).

        Like

    • Frits 1:28 pm on 17 October 2020 Permalink | Reply

      Assuming whole numbers are in the range (1, …, 100) and with the “improved PS” check (which is not needed if we use “AB < CD").

      If we include zero as a whole number there are 2 solutions.

      from enigma import  SubstitutedExpression, multiset
      
      r = multiset()
      
      p = SubstitutedExpression([
          # we start with AB balls potted from CD attempts
          "AB <= CD",
          "CD > 0",
          # "I then potted several balls (XY > 1) in a row"
          # Assume CD + 2 * XY + 1 is roughly less than 100
          "XY > 1",
          "XY < (99 - CD) // 2",
           # the 4 pot successes being whole numbers (meaning 1..100 ???)
          "div(100 * AB, CD) > 0",
          "div(100 * (AB + XY), CD + XY) > 0",
          "div(100 * (AB + 2 * XY), CD + 2 * XY) > 0",
          "div(100 * (AB + 2 * XY), CD + 2 * XY + 1) > 0",
          # improved PS
          "div(100 * (AB + XY), CD + XY) > div(100 * AB, CD)",
          ],
          verbose=0,
          d2i={},
          answer="AB + 2 * XY, AB, CD, XY, " 
                 "(100 * AB / CD, 100 * (AB + XY) / (CD + XY),"
                 " 100 * (AB + 2 * XY) / (CD + 2 * XY),"
                 " 100 * (AB + 2 * XY) / (CD + 2 * XY + 1))",
          distinct="",
      )
      
      # Solve and print answers
      
      print("potted   start  several     pot success" )
      for (_, ans) in p.solve():
        print(f" {ans[0]:>2}     {str(ans[1:3]):<9}  {str(ans[3]):<3}  {ans[4]}")
        r.add(ans[0])
      
      for (k, v) in r.items():
        if v == 1:
          print(f"\n{k} balls potted")
      

      Like

  • Jim Randell 4:38 pm on 9 October 2020 Permalink | Reply
    Tags:   

    Teaser 3029: Square jigsaws 

    From The Sunday Times, 11th October 2020 [link]

    I chose a whole number and asked my grandson to cut out all possible rectangles with sides a whole number of centimetres whose area, in square centimetres, did not exceed my number. (So, for example, had my number been 6 he would have cut out rectangles of sizes 1×1, 1×2, 1×3, 1×4, 1×5, 1×6, 2×2 and 2×3). The total area of all the pieces was a three-figure number of square centimetres.

    He then used all the pieces to make, in jigsaw fashion, a set of squares. There were more than two squares and at least two pieces in each square.

    What number did I originally choose?

    [teaser3029]

     
    • Jim Randell 5:17 pm on 9 October 2020 Permalink | Reply

      (See also: Enigma 1251, Enigma 1491).

      If the squares are composed of at least two pieces, they must be at least 3×3.

      This Python program works out the only possible original number that can work, but it doesn’t demonstrate the the rectangles can be assembled into the required squares.

      It runs in 44ms.

      Run: [ @repl.it ]

      from enigma import irange, inf, printf
      
      # generate rectangles with area less than n
      def rectangles(n):
        for i in irange(1, n):
          if i * i > n: break
          for j in irange(i, n // i):
            yield (i, j)
      
      # decompose t into squares
      def decompose(t, m=1, ss=[]):
        if t == 0:
          yield ss
        else:
          for k in irange(m, t):
            s = k * k
            if s > t: break
            yield from decompose(t - s, k, ss + [k])
      
      # make squares from the rectangular pieces, with total area A
      def fit(rs, A):
        # determine the maximum dimension of the rectangles
        m = max(j for (i, j) in rs)
        for n in irange(m, A):
          if n * n > A: break
          # decompose the remaining area into squares
          for ss in decompose(A - n * n, 3):
            if len(ss) < 2: continue
            yield ss + [n]
      
      # consider the chosen number
      for n in irange(2, inf):
        # collect the rectangles and total area
        rs = list(rectangles(n))
        A = sum(i * j for (i, j) in rs)
        if A < 100: continue
        if A > 999: break
      
        # fit the rectangles in a set of squares
        for ss in fit(rs, A):
          printf("n={n}, A={A} -> ss={ss}")
      

      Solution: The original number was 29.

      The rectangles cut out are:

      1, 2, 3, …, 29
      2, 3, …, 14
      3, …, 9
      4, 5, 6, 7
      5

      With a total area of 882 cm².

      The 1×29 piece must fit into a square of size 29×29 or larger, but this is the largest square we can make, so there must be a 29×29 square, which leaves an area of 41 cm². This can be split into squares as follows:

      41 = 3² + 4² + 4²
      41 = 4² + 5²

      It turns out that it only possible to construct a packing using the second of these.

      I used the polyominoes.py library that I wrote for Teaser 2996 to assemble the rectangles into a viable arrangement of squares. It runs in 19 minutes. (The adapted program is here).

      Here is a diagram showing one way to pack the rectangles into a 4×4, 5×5 and a 29×29 square:

      Like

      • Frits 2:27 pm on 10 October 2020 Permalink | Reply

        @Jim,

        Wouldn’t it be easier to use the chosen number n as maximum dimension (line 23)?

        Like

        • Jim Randell 11:51 am on 11 October 2020 Permalink | Reply

          @Frits: Probably. When I started writing the program I was thinking about a constructive solution, that would produce a packing of the rectangles into the required squares. This is a cut-down version of the program which finds possible sets of squares to investigate – fortunately the solutions found all correspond to the same original number, so if there is an answer we know what it must be.

          And it turns out that we don’t need to examine the set of rectangles to determine the maximum dimension, so we could just pass it in. In fact we don’t need to collect the rectangles at all. Here’s a better version of the cut-down program:

          from enigma import irange, inf, divisors_pairs, printf
          
          # decompose t into squares
          def decompose(t, m=1, ss=[]):
            if t == 0:
              yield ss
            else:
              for k in irange(m, t):
                s = k * k
                if s > t: break
                yield from decompose(t - s, k, ss + [k])
          
          # find at least 3 potential squares with total area A
          # that can accomodate a rectangle with max dimension m
          def fit(A, m):
            for n in irange(m, A):
              a = A - n * n
              if a < 18: break
              # decompose the remaining area into at least 2 squares
              # with minimum dimension 3
              for ss in decompose(a, 3):
                if len(ss) > 1:
                  yield ss + [n]
          
          # collect rectangles with increasing area
          A = 0
          for n in irange(1, inf):
            # add in rectangles of area n
            A += sum(i * j for (i, j) in divisors_pairs(n))
          
            # look for 3-digit total area
            if A < 100: continue
            if A > 999: break
          
            # find a set of squares with the same area
            for ss in fit(A, n):
              printf("n={n} A={A} -> ss={ss}")
          

          I did complete a program that finds a viable packing, but it takes a while to run (19 minutes).

          I’ll post the diagram with the answer later.

          Like

          • Frits 5:59 pm on 11 October 2020 Permalink | Reply

            @Jim, a nice solution with the divisor pairs.
            I think we can only form one 3×3 square at most (out of 3 possibilities).

            Like

    • Frits 1:29 pm on 10 October 2020 Permalink | Reply

      I did a manual check to see if the reported squares can be formed in 2-D with the rectangular pieces.

       
      # select numbers from list <li> so that sum of numbers equals <n>
      def decompose(n, li, sel=[]):
        if n == 0:
          yield sel
        else:
          for i in {j for j in range(len(li)) if li[j] <= n}:
            yield from decompose(n - li[i], li[i:], sel + [li[i]])     
              
      # squares under 1000, square 2x2 can't be formed from rectangles                 
      squares = [n*n for n in range(3, 32)]
      
      rectangles = lambda n: [(i, j) for i in range(1, n + 1) 
                              for j in range(i, n + 1) if i * j <= n]
      
      area = lambda li: sum(i * j for (i, j) in li)
      
      # candidates with three-figure number area; area must be
      # at least largest square (i*i) plus the 2 smallest squares 9 and 16
      cands = lambda: {i: area(rectangles(i)) for i in range(7, 32) 
                       if area(rectangles(i)) in range(100, 1000) and
                          area(rectangles(i)) >= i * i + 25}
      
      # check if solution exist for candidates
      for (n, a) in cands().items(): 
        # biggest square should be at least n x n due to 1 x n piece
        for big in range(n, 32):
          # list of squares to consider (excluding the biggest square)
          sq = [x for x in squares if x <= a - (big * big) - 9]
          # select squares which together with biggest square will sum to area <a>
          for s in decompose(a - (big * big), sq):
            if len(s) > 1:
              print(f"number chosen = {n}, area={a}, squares={s + [big * big]}")
      

      Like

  • Jim Randell 4:49 pm on 2 October 2020 Permalink | Reply
    Tags:   

    Teaser 3028: Rainbow numeration 

    From The Sunday Times, 4th October 2020 [link]

    Dai had seven standard dice, one in each colour of the rainbow (ROYGBIV). Throwing them simultaneously, flukily, each possible score (1 to 6) showed uppermost. Lining up the dice three ways, Dai made three different seven-digit numbers: the smallest possible, the largest possible, and the “rainbow” (ROYGBIV) value. He noticed that, comparing any two numbers, only the central digit was the same, and also that each number had just one single-digit prime factor (a different prime for each of the three numbers).

    Hiding the dice from his sister Di’s view, he told her what he’d done and what he’d noticed, and asked her to guess the “rainbow” number digits in ROYGBIV order. Luckily guessing the red and orange dice scores correctly, she then calculated the others unambiguously.

    What score was on the indigo die?

    I’ve changed the wording of the puzzle slightly to make it clearer.

    [teaser3028]

     
    • Jim Randell 5:17 pm on 2 October 2020 Permalink | Reply

      (Note: I’ve updated my program (and the puzzle text) in light of the comment by Frits below).

      This Python program runs in 49ms.

      Run: [ @repl.it ]

      from enigma import irange, subsets, nconcat, filter_unique, printf
      
      # single digit prime divisor
      def sdpd(n):
        ps = list(p for p in (2, 3, 5, 7) if n % p == 0)
        return (ps[0] if len(ps) == 1 else None)
      
      # if flag = 0, check all values are the same
      # if flag = 1, check all values are different
      check = lambda flag, vs: len(set(vs)) == (len(vs) if flag else 1)
      
      # all 6 digits are represented
      digits = list(irange(1, 6))
      
      # but one of them is repeated
      ans = set()
      for (i, d) in enumerate(digits):
        ds = list(digits)
        ds.insert(i, d)
        # make the smallest and largest numbers
        smallest = nconcat(ds)
        p1 = sdpd(smallest)
        if p1 is None: continue
        largest = nconcat(ds[::-1])
        p2 = sdpd(largest)
        if p2 is None or p2 == p1: continue
        printf("smallest = {smallest} ({p1}); largest = {largest} ({p2})")
      
        # find possible "rainbow" numbers
        rs = list()
        for s in subsets(ds[:3] + ds[4:], size=len, select="P", fn=list):
          s.insert(3, ds[3])
          # rainbow has only the central digit in common with smallest and largest
          if not all(check(i != 3, vs) for (i, vs) in enumerate(zip(s, ds, ds[::-1]))): continue
          rainbow = nconcat(s)
          p3 = sdpd(rainbow)
          if p3 is None or not check(1, (p1, p2, p3)): continue
      
          rs.append(tuple(s))
      
        # find rainbow numbers unique by first 2 digits
        for rainbow in filter_unique(rs, (lambda s: s[:2])).unique:
          n = nconcat(rainbow)
          printf("-> rainbow = {n} ({p3})", p3=sdpd(n))
          # record the indigo value
          ans.add(rainbow[5])
      
      # output solution
      printf("indigo = {ans}")
      

      Solution: The score on the indigo die is 4.

      Each of the digits 1-6 is used once, and there is an extra copy of one of them. So there is only one possible set of 7 digits used.

      The smallest number is: 1234456 (divisible by 2).

      And the largest number is: 6544321 (divisibly by 7).

      There are 17 possible values for the “rainbow” number, but only 3 of them are uniquely identified by the first 2 digits: 2314645, 3124645, 3614245 (and each is divisible by 5).

      The scores on the green, indigo and violet dice are the same for all three possible “rainbow” numbers: 4, 4, 5. So this gives us our answer.

      Like

    • Frits 11:02 pm on 2 October 2020 Permalink | Reply

      “each number had just one prime factor under 10 (different for each number)”.

      The three numbers you report seem to have same prime factors under 10, maybe I have misunderstood.

      Like

      • Jim Randell 11:10 pm on 2 October 2020 Permalink | Reply

        @Frits: I think you could be right. I took it to mean that it wasn’t the same prime in each case (two of the numbers I originally found share a prime). But requiring there to be three different primes does also give a unique answer to the puzzle (different from my original solution). So it could well be the correct interpretation (and it would explain why we weren’t asked to give the rainbow number). Thanks.

        Like

    • Frits 11:35 pm on 2 October 2020 Permalink | Reply

      @Jim: I hope to publish my program tomorrow (for three different prime numbers). I don’t have a clean program yet.

      Your solution also seems to be independent of the indigo question (it could have been asked for another colour). In my solution this specific colour is vital for the solution.

      Like

    • Frits 11:26 am on 3 October 2020 Permalink | Reply

      Next time I try to use the insert function (list).

       
      from enigma import factor, irange, concat, peek 
      from itertools import permutations as perm
      from collections import defaultdict
      
      P = {2, 3, 5, 7}
      
      # number of same characters at same positions
      nr_common = lambda x, y: sum(1 for i, a in enumerate(x) if a == y[i])
      
      # prime factors under 10
      factund10 = lambda x: [p for p in P if int(x) % p == 0]
      
      # if list contains one entry then return possible values at position i
      charvals = lambda s, i: {x[0][i] for x in s if len(x) == 1}
      
      n = 6
      digits = concat([x for x in irange(1, n)])
      
      # for each digit i occuring twice in lowest and highest number
      for i in irange(1, n):
        str_i = str(i)
        # build lowest and highest number
        low = digits[:i] + str_i + digits[i:]
        hgh = low[::-1]
       
        # get prime factors under 10 
        u10low = factund10(low) 
        u10hgh = factund10(hgh) 
        
        # each number with one prime factor under 10 (different for each number)
        if len(u10low) != 1 or len(u10hgh) != 1 or u10low[0] == u10hgh[0]:
           continue
       
        rainbow = defaultdict(list)
       
        # for this combination of lowest and highest check the rainbow possibilities
        for pe in perm(low[:n//2] + low[n//2 + 1:]):
          # weave central digit into permutation pe at center position
          rb = concat(pe[:n//2] + tuple(low[n//2]) + pe[n//2:])
          
          # check rainbow number on only the central digit being the same
          if nr_common(rb, low) != 1 or nr_common(rb, hgh) != 1: 
            continue
      
          u10rb = factund10(int(rb)) 
          # all three prime factors under 10 are different
          if len(u10rb) == 1 and u10rb[0] != u10low[0] and u10rb[0] != u10hgh[0]:
            # store rainbow number with as key first 2 digits
            rainbow[rb[:2]].append(rb)
            
        # if first 2 digits rainbow number is unique then list indigo values
        indigo = charvals(rainbow.values(), 5)  
        if len(indigo) == 1:
          print(f"The score on the indigo die: {peek(indigo)}")
      

      Like

    • Frits 2:58 pm on 4 October 2020 Permalink | Reply

      A more efficient program (without explaining the choices as this is a new puzzle).

       
      from enigma import factor, irange, concat, diff 
      from itertools import permutations as perm
      from collections import defaultdict
      
      # number of same characters at same positions
      nr_common = lambda x, y: sum(1 for i, a in enumerate(x) if a == y[i])
      
      # prime factors under 10
      factund10 = lambda x: [p for p in {2, 5, 7} if int(x) % p == 0]
      
      # if list contains one entry then return possible values at position i
      charvals = lambda s, i: {x[0][i] for x in s if len(x) == 1}
      
      n = 6
      digits = concat([x for x in irange(1, n)])
      
      # for each digit i occuring twice in lowest and highest number
      for i in irange(1, n):
        if i % 3 == 0: continue
        
        # build lowest and highest number
        low = digits[:i] + str(i) + digits[i:]
        hgh = low[::-1]
       
        # get prime factors under 10 
        u10low = factund10(low)       
        u10hgh = factund10(hgh)       
       
        if len(u10hgh) != 1 or u10hgh[0] != 7: continue
        
        # each number with one prime factor under 10 (different for each number)
        if len(u10low) != 1: continue
        
        rainbow = defaultdict(list)
         
        # for this combination of lowest and highest check the rainbow possibilities
        center = str(i)
        remaining = diff(low[:n//2] + low[n//2 + 1:], "5")
        # try possibilities for first digit  
        for d1 in diff(remaining, "1" + str(n)):
          # find values for positions without the edges and the center
          for pe2 in perm(diff(remaining, d1) , n - 2):
            # build rainbow number
            rb = d1 + concat(pe2[:(n-1)//2]) + center + \
                 concat(pe2[(n-1)//2:]) + "5"
            
            if int(rb) % u10hgh[0] == 0:      
              continue
           
            # check rainbow number on only the central digit being the same
            if nr_common(rb, low) != 1 or nr_common(rb, hgh) != 1: 
              continue
            
            # store rainbow number with as key first 2 digits
            rainbow[rb[:2]].append(rb)
        
        # if first 2 digits rainbow number is unique then list indigo values
        indigo = charvals(rainbow.values(), 5)  
        if len(indigo) == 1:
          print(f"The score on the indigo die: {indigo.pop()}")  
      

      Like

  • Jim Randell 4:40 pm on 25 September 2020 Permalink | Reply
    Tags:   

    Teaser 3027: Long shot 

    From The Sunday Times, 27th September 2020 [link]

    Callum and Liam play a simple dice game together using standard dice (numbered 1 to 6). A first round merely determines how many dice (up to a maximum of three) each player can use in the second round. The winner is the player with the highest total on their dice in the second round.

    In a recent game Callum was able to throw more dice than Liam in the second round but his total still gave Liam a chance to win. If Liam had been able to throw a different number of dice (no more than three), his chance of winning would be a whole number of times greater.

    What was Callum’s score in the final round?

    [teaser3027]

     
    • Jim Randell 5:13 pm on 25 September 2020 Permalink | Reply

      This Python program runs in 49ms.

      Run: [ @repl.it ]

      from enigma import multiset, subsets, irange, div, printf
      
      # calculate possible scores with 1, 2, 3 dice
      fn = lambda k: multiset.from_seq(sum(s) for s in subsets(irange(1, 6), size=k, select="M"))
      scores = dict((k, fn(k)) for k in (1, 2, 3))
      
      # choose number of dice for Liam and Callum (L < C)
      for (kL, kC) in subsets(sorted(scores.keys()), size=2):
        (C, L) = (scores[kC], scores[kL])
        tL = len(L)
        # consider scores for Callum
        for sC in C.keys():
          # and calculate Liam's chance of winning
          nL = sum(n for (s, n) in L.items() if s > sC)
          if nL == 0: continue
      
          # but if Liam had been able to throw a different number of dice, his
          # chance of winning would be a whole number of times greater (L < H)
          for (kH, H) in scores.items():
            if not(kH > kL): continue
            tH = len(H)
            nH = sum(n for (s, n) in H.items() if s > sC)
            d = div(nH * tL, nL * tH)
            if d is None or not(d > 1): continue
      
            # output solution
            printf("Callum: {kC} dice, score = {sC} -> Liam: {kL} dice, chance = {nL} / {tL}")
            printf("-> Liam: {kH} dice, chance = {nH} / {tH} = {d} times greater")
            printf()
      

      Solution: Callum scored 10 in the final round.

      The result of the first round was that Callum was to throw 3 dice, and Liam was to throw 2.

      Callum scored 10 on his throw. Which meant that Liam had a chance to win by scoring 11 (two ways out of 36) or 12 (one way out of 36), giving a total chance of 3/36 (= 1/12) of winning the game.

      However if Liam had been able to throw 3 dice, he would have had a total chance of 108/216 (= 1/2 = 6/12) of scoring 11 to 18 and winning the game. This is 6 times larger.

      Like

  • Jim Randell 5:13 pm on 18 September 2020 Permalink | Reply
    Tags:   

    Teaser 3026: Party time 

    From The Sunday Times, 20th September 2020 [link]

    A four-digit number with different positive digits and with the number represented by its last two digits a multiple of the number represented by its first two digits, is called a PAR.

    A pair of PARs is a PARTY if no digit is repeated and each PAR is a multiple of the missing positive digit.

    I wrote down a PAR and challenged Sam to use it to make a PARTY. He was successful.

    I then challenged Beth to use my PAR and the digits in Sam’s PAR to make a different PARTY. She too was successful.

    What was my PAR?

    [teaser3026]

     
    • Jim Randell 5:30 pm on 18 September 2020 Permalink | Reply

      This Python program uses the [[ SubstitutedExpression() ]] general alphametic solver from the enigma.py library to find possible PARTYs. It then collects pairs of PARs together and looks for a PAR that has two possible pairings that share the same digits.

      It runs in 56ms.

      Run: [ @repl.it ]

      from collections import defaultdict
      from enigma import SubstitutedExpression, irange, subsets, nsplit, printf
      
      # find possible PARTYs
      p = SubstitutedExpression(
        ["CD % AB = 0", "ABCD % X = 0", "GH % EF = 0", "EFGH % X = 0", "ABCD < EFGH"],
        digits=irange(1, 9),
        answer="(ABCD, EFGH, X)",
      )
      
      # collect results by PARs
      d = defaultdict(list)
      for (_, (ABCD, EFGH, X)) in p.solve(verbose=0):
        d[ABCD].append(EFGH)
        d[EFGH].append(ABCD)
      
      # collect the digits of a number
      digits = lambda n: sorted(nsplit(n))
      
      # choose the initial PAR
      for (k, vs) in d.items():
        # choose two related PARs ...
        for (p1, p2) in subsets(vs, size=2):
          # ... that have the same digits
          if digits(p1) == digits(p2):
            printf("{k} -> {p1}, {p2}")
      

      Solution: Your PAR was 1785.

      1785 can be paired with both 2496 and 4692 (missing digit = 3) to make a PARTY.

      There are 7 possible PARTYs:

      (1938, 2754, 6)
      (1854, 3672, 9)
      (1836, 2754, 9)
      (1785, 4692, 3)
      (1785, 2496, 3)
      (1734, 2958, 6)
      (1456, 3978, 2)

      There are only 2 PARs that appear in more than one PARTY: 1785 and 2754. Each of these appears in two PARTYs, but only 1785 is paired with two other PARs that share the same digits.

      Like

      • Jim Randell 12:28 pm on 20 September 2020 Permalink | Reply

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

        This run file executes in 94ms.

        #!/usr/bin/env python -m enigma -r
        
        SubstitutedExpression
        
        # Graham's PAR = ABCD
        "CD % AB = 0"
        
        # Sam's PAR = EFGH ...
        "GH % EF = 0"
        
        # ... makes a PARTY with ABCD and X
        "ABCD % X = 0"
        "EFGH % X = 0"
        
        # Beth's PAR = IJKL ...
        "KL % IJ = 0"
        
        # ... makes a different PARTY with ABCD and X
        "IJKL % X = 0"
        "EFGH != IJKL"
        
        # solver parameters
        --digits="1-9"
        --distinct="ABCDEFGHX,ABCDIJKLX"
        --answer="ABCD"
        

        Like

    • Frits 9:12 pm on 19 September 2020 Permalink | Reply

       
      from enigma import nconcat
      from itertools import permutations, combinations
       
      difference = lambda a, b: [x for x in a if x not in b]  
       
      def getPARs(ds, k):
        li = []
        # check all permutations of digits
        for p1 in permutations(ds): 
          # first digit can't be high
          if p1[0] > 4: continue
          
          n12 = nconcat(p1[:2])
          n34 = nconcat(p1[2:])
          n = 100 * n12 + n34
          # number last two digits is a multiple of number first 2 digits
          # and four-digit number is a multiple of k
          if n34 % n12 != 0 or n % k != 0: continue
          # store the PAR 
          li.append(n)
        return li  
            
      sol = [] 
      # loop over missing digits 
      for k in range(1,10):
        digits = difference(range(1,10), [k])
        # choose the lowest remaining digit
        low = min(digits)
        digits = difference(digits, [low])
        # pick 3 digits to complement low
        for c1 in combinations (digits, 3): 
          par1 = getPARs((low,) + c1, k) 
          if par1: 
            par2 = getPARs(difference(digits, c1), k) 
            # PAR(s) related to two or more PARs?
            if len(par1) == 1 and len(par2) == 1:
              continue
            if len(par2) == 1: 
              sol.append([par2, par1])
            elif par2:
              sol.append([par1, par2])
           
      for i in range(len(sol)):
        print(f"{sol[i][0]} --> {sol[i][1]}")
      

      Like

    • Will Harris 3:14 pm on 19 December 2020 Permalink | Reply

      Not much help now but wrote this for my coursework project using GNU prolog [ https://www.tutorialspoint.com/execute_prolog_online.php ]

      :- initialization(main).
      % This program has been developed for GNU Prolog | https://www.tutorialspoint.com/execute_prolog_online.php
      
      %Question 2.1
      convert(P, Q) :-
          Q is P - 48,
          Q > 0.
      
      unique(List) :-
          sort(List, Sorted),
          length(List, OriginalLength),
          length(Sorted, SortedLength),
          OriginalLength =:= SortedLength.
      
      multiple_of([A,B,C,D]) :-
          get_num(A,B,X),
          get_num(C,D,Y),
          check_mod(X,Y).
          
      get_num(P,Q,R) :-
          R is P * 10 + Q.
      
      check_mod(N,M) :-
          M mod N =:= 0.
          
      par(Number) :-
          number_codes(Number,ListCharCodes), 
          maplist(convert,ListCharCodes,ListDigits),
          length(ListDigits, 4),
          unique(ListDigits),
          multiple_of(ListDigits).
      
      
      %Question 2.2
      candidate_pars(P, Q, []) :-
          P > Q.
      candidate_pars(P, Q, [P|W]) :-
          par(P),
          P1 is P + 1,
          candidate_pars(P1, Q, W).
      candidate_pars(P, Q, W) :- 
          P1 is P + 1,
          candidate_pars(P1, Q, W).
      
      pars( PARS ) :-
          candidate_pars(1234, 9876, PARS).
      
      
      %Question 2.3
      missing_digit(V,W,CombDigits) :-
          number_codes(V, ListOne),
          number_codes(W, ListTwo),
          maplist(convert, ListOne, ListDigitsOne),
          maplist(convert, ListTwo, ListDigitsTwo),
          append(ListDigitsOne, ListDigitsTwo, CombDigits).
      
      party(V, W) :-
          missing_digit(V, W, CombDigits),
          subtract([1,2,3,4,5,6,7,8,9], CombDigits, MissingDigits),
          length(MissingDigits, 1),
          par(V),
          par(W),
          nth(1, MissingDigits, M),
          check_mod(M,V),
          check_mod(M,W).
      
      
      %Question 2.4
      comparison(PARS, I, J) :-
          member(I, PARS), 
          member(J, PARS), 
          party(I,J).
      
      partys( PARTYS ) :-
          pars(PARS),
          findall([I,J], comparison(PARS, I, J), PARTYS).
      
      main :-
          partys( PARTYS ), write(PARTYS).
      
      /*
      There is only a single solution to Teaser 3026:
      There are only 2 PARs that appear in more than one PARTY: 1785 and 2754. 
      Each of these appears in two PARTYs, but only 1785 is paired with two other
      PARs that share the same digits. 1785 can be paired with both 2496 and 4692 
      (missing digit = 3) to make a PARTY.
      */
      

      Like

      • Jim Randell 3:26 pm on 19 December 2020 Permalink | Reply

        @Will: Thanks for your comment.

        I’m not sure if the code came through correctly (WordPress can get confused by text with < and > characters in it).

        If it’s wrong, can you post again with the code in:

        [code]
        code goes here
        [/code]
        

        and I’ll fix it up.

        Like

    • GeoffR 4:57 pm on 16 December 2021 Permalink | Reply

      
      from itertools import permutations
      
      digits = set('123456789')
      
      for p1 in permutations(digits, 5):
          A, B, C, D, I = p1
          # my PAR is ABCD and I is the missing digit
          ABCD = int(A + B + C + D)
          if ABCD % int(I) !=0: continue
          AB, CD = int(A + B), int(C + D)
          if not(CD % AB == 0):continue
          
          # find another two PARs to make two PARTYs
          q1 = digits.difference(p1)
          for p2 in permutations(q1):
              E, F, G, H = p2
              EFGH = int(E + F + G + H)
              if not EFGH % int(I) == 0: continue
              EF, GH = int(E + F), int(G + H)
              if not (GH % EF == 0):continue
              
              # form 2nd PAR with digits (E, F, G, H)
              for p3 in permutations(p2):
                  e, f, g, h = p3
                  efgh = int(e + f + g + h)
                  # there must be two different PARs from EFGH
                  if EFGH == efgh:continue
                  if efgh % int(I) != 0: continue
                  ef, gh = int(e + f), int(g + h)
                  if not (gh % ef == 0):continue
                  print(f"My PAR = {ABCD}")
                  print(f"Sam / Beth's PARTY = {ABCD}, {EFGH}")
                  print(f"Sam / Beth's PARTY = {ABCD}, {efgh}")
                  print()
      
      # My PAR = 1785
      # Sam / Beth's PARTY = 1785, 4692
      # Sam / Beth's PARTY = 1785, 2496
      
      
      
      

      Like

  • Jim Randell 4:44 pm on 11 September 2020 Permalink | Reply
    Tags:   

    Teaser 3025: Please mind the gap 

    From The Sunday Times, 13th September 2020 [link]

    Ann, Beth and Chad start running clockwise around a 400m running track. They run at a constant speed, starting at the same time and from the same point; ignore any extra distance run during overtaking.

    Ann is the slowest, running at a whole number speed below 10 m/s, with Beth running exactly 42% faster than Ann, and Chad running the fastest at an exact percentage faster than Ann (but less than twice her speed).

    After 4625 seconds, one runner is 85m clockwise around the track from another runner, who is in turn 85m clockwise around the track from the third runner.

    They decide to continue running until gaps of 90m separate them, irrespective of which order they are then in.

    For how long in total do they run (in seconds)?

    [teaser3025]

     
    • Jim Randell 5:28 pm on 11 September 2020 Permalink | Reply

      For the distances involved they must be very serious runners.

      I amused myself by writing a generic function to check the runners are evenly spaced. Although for the puzzle itself it is possible to use a simpler formulation that does not always produce the correct result. But once you’ve got that sorted out the rest of the puzzle is straightforward.

      This Python program runs in 55ms.

      Run: [ @replit ]

      from enigma import (irange, div, tuples, printf)
      
      # one lap of the track is 400m
      L = 400
      
      # time for separation of 85m
      T = 4625
      
      # check for equal separations
      def check_sep(ps, v):
        k = len(ps) - 1
        # calculate the remaining gap
        g = L - k * v
        if not (k > 0 and g > 0): return False
        # calculate positions of the runners
        ps = sorted(p % L for p in ps)
        # calculate the distances between them
        ds = list((b - a) % L for (a, b) in tuples(ps, 2, circular=1))
        # look for equal spacings
        return (g in ds and ds.count(v) >= k)
      
      # consider speeds for A
      for A in irange(1, 9):
        # A's distance after T seconds
        dA = A * T
        # B's distance after T seconds
        dB = div(dA * 142, 100)
        if dB is None: continue
        # A and B are separated by 85m or 170m
        if not (check_sep((dA, dB), 85) or check_sep((dA, dB), 170)): continue
      
        # now choose a whole number percentage increase on A
        for x in irange(143, 199):
          # C's distance after T seconds
          dC = div(dA * x, 100)
          if dC is None: continue
          # A, B, C are separated by 85m
          if not check_sep((dA, dB, dC), 85): continue
          printf("A={A} -> dA={dA} dB={dB}; x={x} dC={dC}")
      
          # continue until separation is 90m
          for t in irange(T + 1, 86400):
            dA = A * t
            dB = div(dA * 142, 100)
            dC = div(dA * x, 100)
            if dB is None or dC is None: continue
            if not check_sep((dA, dB, dC), 90): continue
            # output solution
            printf("-> t={t}; dA={dA} dB={dB} dC={dC}")
            break
      

      Solution: They run for 7250 seconds (= 2 hours, 50 seconds).

      After which time A will have covered 29 km (about 18 miles), B will have covered 41.2 km (about 25.6 miles), and C (who runs at a speed 161% that of A) will have covered 46.7 km (about 29 miles), which is pretty impressive for just over 2 hours.

      For comparison, Mo Farah on his recent world record breaking run of 21,330 m in 1 hour [link], would not have been able to keep up with C (who maintained a faster pace for just over 2 hours), and would be only slightly ahead of B at the 1 hour mark.

      Like

  • Jim Randell 4:42 pm on 4 September 2020 Permalink | Reply
    Tags:   

    Teaser 3024: Triple jump 

    From The Sunday Times, 6th September 2020 [link]

    From a set of playing cards, Tessa took 24 cards consisting of three each of the aces, twos, threes, and so on up to the eights. She placed the cards face up in single row and decided to arrange them such that the three twos were each separated by two cards, the threes were separated by three cards and so forth up to and including the eights, duly separated by eight cards. The three aces were numbered with a one and were each separated by nine cards. Counting from the left, the seventh card in the row was a seven.

    In left to right order, what were the numbers on the first six cards?

    [teaser3024]

     
    • Jim Randell 5:03 pm on 4 September 2020 Permalink | Reply

      (See also: Enigma 369).

      I assume that for each set of three cards with value n (the aces have a value of 9): the leftmost one is separated from the middle one by n other cards, and the middle one is separated from the rightmost one by n other cards. (So the leftmost and rightmost instances are not separated by n cards).

      I treat the puzzle as if cards with values 2 to 9 were used (3 copies of each). Then when we have found a solution we can replace the value 9 cards with aces.

      This Python program runs in 50ms.

      Run: [ @repl.it ]

      from enigma import update, join, printf
      
      # generate sequences in <s> where 3 occurrences of the numbers in <ns> are
      # separated by <n> other slots
      def generate(s, ns):
        if not ns:
          yield s
        else:
          n = ns[0]
          for (i, x) in enumerate(s):
            j = i + n + 1
            k = j + n + 1
            if not(k < len(s)): break
            if not(x is None and s[j] is None and s[k] is None): continue
            yield from generate(update(s, [i, j, k], [n, n, n]), ns[1:])
      
      # start with 24 slots
      s = [None] * 24
      # we are told where the 7's are:
      s[6] = s[14] = s[22] = 7
      # place the remaining cards
      for ss in generate(s, [9, 8, 6, 5, 4, 3, 2]):
        # output solution
        printf("{ss}", ss=join(("??23456781"[x] for x in ss), sep=" "))
      

      Solution: The first 6 cards are: 1, 2, 6, 8, 2, 5.

      Without pre-placing the 7’s there are four sequences that work (or two sequences, and their reverses):

      (1 2 6 8 2 5 7 2 4 6 1 5 8 4 7 3 6 5 4 3 1 8 7 3)
      (3 1 7 5 3 8 6 4 3 5 7 1 4 6 8 5 2 4 7 2 6 1 2 8)
      (8 2 1 6 2 7 4 2 5 8 6 4 1 7 5 3 4 6 8 3 5 7 1 3)
      (3 7 8 1 3 4 5 6 3 7 4 8 5 1 6 4 2 7 5 2 8 6 2 1)
      

      The answer to the puzzle is the first of these sequences.

      Like

      • Jim Randell 11:15 am on 5 September 2020 Permalink | Reply

        Here is a MiniZinc model to solve the puzzle:

        %#! minizinc -a
        
        include "globals.mzn";
        
        % index of middle cards with values 2 to 9
        var 11..14: i9;
        var 10..15: i8;
        var  9..16: i7;
        var  8..17: i6;
        var  7..18: i5;
        var  6..19: i4;
        var  5..20: i3;
        var  4..21: i2;
        
        % each card is in a different slot
        constraint all_different([
          i9, i9 - 10, i9 + 10,
          i8, i8 - 9, i8 + 9,
          i7, i7 - 8, i7 + 8,
          i6, i6 - 7, i6 + 7,
          i5, i5 - 6, i5 + 6,
          i4, i4 - 5, i4 + 5,
          i3, i3 - 4, i3 + 4,
          i2, i2 - 3, i2 + 3,
        ]);
        
        % there is a 7 in slot 7
        constraint i7 - 8 = 7;
        
        solve satisfy;
        

        Like

        • Jim Randell 4:32 pm on 5 September 2020 Permalink | Reply

          And here’s an alternative implementation in Python that collects the indices of the central cards of each value, rather than filling out the slots:

          from enigma import irange, update, join, printf
          
          # generate indices for the central number in <ns> where the 3
          # occurrences are separated by <n> other slots
          def solve(ns, m=dict(), used=set()):
            if not ns:
              yield m
            else:
              n = ns[0]
              # consider possible indices for the middle card with value n
              d = n + 1
              for i in irange(d, 23 - d):
                (j, k) = (i - d, i + d)
                if not used.intersection((i, j, k)):
                  yield from solve(ns[1:], update(m, [(n, i)]), used.union((i, j, k)))
          
          # place 7 (at 6, 14, 22), and solve for the remaining cards
          for m in solve([9, 8, 6, 5, 4, 3, 2], { 7: 14 }, set([6, 14, 22])):
            # construct the solution sequence
            s = [0] * 24
            for (n, i) in m.items():
              d = n + 1
              s[i] = s[i - d] = s[i + d] = (1 if n == 9 else n)
            # output solution
            printf("{s}", s=join(s, sep=" "))
          

          Like

    • Frits 8:57 pm on 5 September 2020 Permalink | Reply

      Based on Jim’s MiniZinc model.

      Only the last”v” call is necessary, the rest is added for performance., it’s a bit messy.

       
      from enigma import SubstitutedExpression, irange, seq_all_different
      
      p = SubstitutedExpression([
          "K < 3",
          "M < 3",
          "O < 3",
          "O > 0",
          "A < 3 and AB > 3 and AB < 22",       # i2
          "C < 3 and CD > 4 and CD < 21",       # i3
          "E < 3 and EF > 5 and EF < 20",       # i4
          "G < 3 and GH > 6 and GH < 19",       # i5
          "IJ > 7 and IJ < 18",                 # i6
          "KL = 15",                            # i7
          "MN > 9 and MN < 16",                 # i8
          "OP > 10 and OP < 15",                # i9
          "v([KL, KL - 8, KL + 8, \
              MN, MN - 9, MN + 9])",
          "v([KL, KL - 8, KL + 8, \
              MN, MN - 9, MN + 9, \
              OP, OP - 10, OP + 10])",
          "v([AB, AB - 3, AB + 3, \
              KL, KL - 8, KL + 8, \
              MN, MN - 9, MN + 9, \
              OP, OP - 10, OP + 10])",
          "v([AB, AB - 3, AB + 3, \
              CD, CD - 4, CD + 4, \
              KL, KL - 8, KL + 8, \
              MN, MN - 9, MN + 9, \
              OP, OP - 10, OP + 10])",
          "v([AB, AB - 3, AB + 3, \
              CD, CD - 4, CD + 4, \
              EF, EF - 5, EF + 5, \
              KL, KL - 8, KL + 8, \
              MN, MN - 9, MN + 9, \
              OP, OP - 10, OP + 10])",
          "v([AB, AB - 3, AB + 3, \
              CD, CD - 4, CD + 4, \
              EF, EF - 5, EF + 5, \
              GH, GH - 6, GH + 6, \
              IJ, IJ - 7, IJ + 7, \
              KL, KL - 8, KL + 8, \
              MN, MN - 9, MN + 9, \
              OP, OP - 10, OP + 10])",
         ],
          verbose=0,
          d2i="",          # allow leading zeroes
          code="v = lambda x: seq_all_different(x)",
          answer="(AB, CD, EF, GH, IJ, KL, MN, OP)",
          distinct="",
      )
      
      out = [2, 3, 4, 5, 6, 7, 8, 1]
      
      # Print answers
      for (_, ans) in p.solve(verbose=0):
        print("Numbers on first 6 cards: ", end="")
        for k in range(1,7):
          for i in range(8):
            if ans[i] == k: print(f"{out[i]} ", end="")
            if ans[i] - i - 3 == k: print(f"{out[i]} ", end="")
        print()
      

      Like

  • Jim Randell 7:09 pm on 28 August 2020 Permalink | Reply
    Tags:   

    Teaser 3023: Timely coincidence 

    From The Sunday Times, 30th August 2020 [link]

    George and Martha possess two digital “clocks”, each having six digits. One displays the time on a 24-hour basis in the format hh mm ss, typically 15 18 45, and the other displays the date in the format dd mm yy, typically 18 07 14.

    On one occasion, George walked into the room to find that the two “clocks” displayed identical readings. Martha commented that the long-term (400-year) average chance of that happening was 1 in just over a six-digit number. That six-digit number gives the birth date of one their daughters.

    On what date was that daughter born?

    [teaser3023]

     
    • Jim Randell 7:35 pm on 28 August 2020 Permalink | Reply

      On any particular day (ignoring jumps in time, such as leap seconds, daylight savings time, calendar reforms, etc.) there is either a 1/86400 chance of observing the clocks displaying the same an any given second (assuming they clocks are equally likely to be observed at any particular second of the day – which is unlikely), or a 0/86400 chance if the date does not correspond to a valid time.

      The following Python program runs in 100ms.

      Run: [ @repl.it ]

      import datetime
      from enigma import int2base, printf
      
      # consider a 400 year period, and count dates that give a valid time
      d = datetime.date(day=1, month=1, year=1900)
      i = datetime.timedelta(days=1)
      n = 0
      t = 0
      while d.year < 2300:
        if d.day < 24 and d.year % 100 < 60: n += 1
        d += i
        t += 1
      
      # output solution
      t *= 86400
      x = t // n
      printf("p = {n} / {t} (~ 1 / {x}); date = {b}", b=int2base(x, group=2, sep=".", width=6))
      

      Solution: The daughter was born on 19th May 1961.


      In order for the date to be read as a valid time we need the day of the month to be in the range 1-23, and the last 2 digits of the year to be in the range 0-59.

      In each year of the required range there are 23×12 = 276 viable days.

      In each 100 year period there are 60×276 = 16560 viable days.

      In each 400 year period there are 4×16560 = 66240 viable days.

      And in a 400 year period there is a total of 400×365 + 100 − 3 = 400×365.2425 = 146097 days.

      Converting to seconds we get a chance of 1 in (146097 × 86400 / 66240) = 190561.304….

      Truncating this result to an integer and reading as a date gives: Friday, 19th May 1961.

      Like

  • Jim Randell 4:38 pm on 21 August 2020 Permalink | Reply
    Tags:   

    Teaser 3022: Sporty set 

    From The Sunday Times, 23rd August 2020 [link]

    There are 100 members of my sports club where we can play tennis, badminton, squash and table tennis (with table tennis being the least popular). Last week I reported to the secretary the numbers who participate in each of the four sports. The digits used overall in the four numbers were different and not zero.

    The secretary wondered how many of the members were keen enough to play all four sports, but of course he was unable to work out that number from the four numbers I had given him. However, he used the four numbers to work out the minimum and the maximum possible numbers playing all four sports. His two answers were two-figure numbers, one being a multiple of the other.

    How many played table tennis?

    [teaser3022]

     
    • Jim Randell 11:26 pm on 21 August 2020 Permalink | Reply

      If the numbers that participate in each sport are A, B, C, D (in increasing order), and the sum of these values is T.

      Then the maximum size of their intersection is easily determined – it is the size of the smallest set, in this case A; (or as John points out below, if all 100 members participate in at least one of the available sports, the maximum is: floor((T − 100) / 3), if this is smaller than A).

      So our maximum is: min(A, floor((T − 100) / 3).

      The minimum size of the intersection is trickier to determine. But if we have a family of subsets S[i] of some universal set U, then the minimum size of the intersection is given by:

      X = \left|\bigcap_{i=1}^{n}S_i\right| \medskip \newline N = |U| \medskip \newline T = \sum_{i=1}^{n}|S_i| \medskip \newline \newline X \geq 0 \medskip \newline X \geq T - (n - 1)N

      So in this case the minimum size is: max(0, T − 300).

      The following Python program runs in 138ms.

      Run: [ @repl.it ]

      from enigma import subsets, irange, diff, nconcat, divf, div, multiset, printf
      
      # generate k increasing 2-digit numbers from the supplied (increasing) digits
      def generate(k, ds, ns=[]):
        # choose the tens digits
        for d10s in subsets(ds, size=k, select="C"):
          # choose the units digits
          for d1s in subsets(diff(ds, d10s), size=k, select="P"):
            # construct the numbers
            yield tuple(nconcat(z) for z in zip(d10s, d1s))
      
      # collect solutions (size of the smallest set)
      ss = multiset()
      
      # choose increasing numbers of participants for each of the 4 sports
      for ns in generate(4, irange(1, 9)):
        T = sum(ns)
        # maximum size of intersection
        M = min(ns[0], divf(T - 100, 3))
        # minimum size of intersection
        m = max(0, T - 300)
      
        # min is a 2-digit numbers
        if m < 10: continue
        # M is a multiple of m
        k = div(M, m)
        if k is None or not(k > 1): continue
      
        printf("[ns={ns}; min={m} max={M} k={k}]")
        ss.add(ns[0])
      
      # output solutions
      for (k, v) in ss.most_common():
        printf("min(ns) = {k} [{v} solutions]")
      

      Solution: 65 played table tennis.

      The other three sports are represented by the numbers (70, 80, 90) + (1, 3, 4) assembled in some order.

      The minimum size of the intersection is 13, and the maximum size is 65 (= 5×13).

      Like

      • Jim Randell 8:54 am on 23 August 2020 Permalink | Reply

        We don’t need to work out the actual sizes of the 3 larger sets, to calculate the sum of their sizes. We only need to know what the tens and units digits are.

        So here is a faster version of my program. You can also pass a command line argument to specify if members playing zero sports are allowed (1) or not (0). It runs in 54ms.

        Run: [ @repl.it ]

        from enigma import irange, subsets, diff, divf, div, arg, printf
        
        # set z to:
        # 0 - if members playing 0 sports are not allowed
        # 1 - if members playing 0 sports are allowed
        z = arg(0, 0, int)
        
        # allowable digits
        digits = irange(1, 9)
        
        # choose the 10s digits for the sets
        for d10s in subsets(digits, size=4):
          t10 = sum(d10s) * 10
          if t10 < 280: continue
        
          # choose the units digits
          for d1s in subsets(diff(digits, d10s), size=4):
            # size of the union of the sets
            T = t10 + sum(d1s)
            # minimum size of intersection
            m = T - 300
            # is a 2 digit number
            if not(9 < m < 100): continue
        
            # choose a units digit for the smallest set
            for d1 in d1s:
              # maximum size of intersection
              A = 10 * d10s[0] + d1
              M = (A if z else min(A, divf(T - 100, 3)))
              # is a multiple of m
              k = div(M, m)
              if k is None or not(k > 1): continue
        
              # output solution
              printf("min(ns) = {A} [min={m} max={M} k={k}; ns = {d10s} x {d1s}] [z={z}]")
        

        Like

        • Frits 10:11 pm on 24 August 2020 Permalink | Reply

          Very nice solution.

          “if t10 Don’t we already know d10s must always be equal to (6, 7, 8, 9)?

          if it is (5, 7, 8, 9) then t10 = 290 and sum(d1s) <= 15 (fi 2,3,4,6)
          So T <= 305 which is not acceptable.

          Like

          • Frits 12:12 pm on 25 August 2020 Permalink | Reply

             
            from enigma import irange, diff, div, printf
            
            # minimum A + B + C + D - 300 > 9 
            # so 10s digits must be (6,7,8,9)
            
            # (A + B + C + D - 100) / 3 >= 70
            # which is bigger than A, so maximum M equals A
            
            # allowable digits for units
            digits = irange(1, 5)
            
            # d is the units digit which is not used in A, B, C and D
            for d in digits:
              # sum of A, B, C and D
              T = 315 - d
              # minimum size of intersection
              m = T - 300
              # choose a units digit for the smallest set
              d1s = diff(digits, (d,))
              for d1 in d1s:
                # maximum size of intersection (is A)
                M = 60 + d1    
                # is a multiple of m
                k = div(M, m)
                if k is None or not(k > 1): continue
            
                # output solution
                printf("min(ns) = {M} [min={m} max={M} k={k}; ns = (6,7,8,9) x {d1s}]")
            

            Like

          • Jim Randell 12:51 pm on 25 August 2020 Permalink | Reply

            @Frits: It looks like your comment didn’t make it through WordPress unscathed. Usually this happens when you use < and > in a comment. WordPress sees everything in between as an HTML tag, and then doesn’t recognise it, so it throws it away. You can use &lt; and &gt; to make < and > appear correctly. (If you want to send me a corrected version, I’ll fix it up).

            It looks like you are asking about line 9 of my code. It’s really just a quick bit of early rejection so the code doesn’t go on to evaluate cases that can’t possibly work, and the program works just as well (and not much slower) without it.

            I reasoned that if (T − 300) is to be a 2-digit number, then (T − 300) > 9, so: T > 309. The maximum possible value of the units digits of the four numbers that make up T is 6+7+8+9 = 30, so the sum of the tens parts of the numbers must be more than 309 − 30 = 279, which is what that test does, and it cuts the number of cases considered drastically.

            With a bit more work we can see that there is only one possible set of values for the tens digits, and we are half way towards a manual solution.

            When programming a solution there is always an amount of choice on how much analysis is necessary to get a program that runs in a reasonable time. But normally if it doesn’t make much difference to the run time I let the computer do the checks.

            Like

            • Frits 6:26 pm on 25 August 2020 Permalink | Reply

              @Jim, Thanks.

              I like to make use of –> which WordPress doesn’t like.

              Yes, I was trying to understand line 9 of your code and wondered why you had chosen this (for me suboptimal) limit.

              I still need to verify for myself that the minimum and maximum formula are indeed correct.

              Is there not an easy way of allowing us to edit our own posts (as it is linked to an email address)?
              Many times directly after posting I see errors/improvements.

              Like

              • Jim Randell 10:37 am on 26 August 2020 Permalink | Reply

                @Frits: Sadly WordPress doesn’t treat comments at the same level as posts. Even for logged-in users. So the only way they can be edited is by a site administrator (who can make changes to any aspect of the site).

                It is the main reason I sometimes think about moving away from WordPress, but I have not yet found a suitable alternative.

                At one point I had hoped that WordPress would implement some level of editing (or even just the basic courtesy of previewing a comment before it is posted), but it has become clear that they really have no interest in this.

                On the upside the system does make it relatively easy to manage a site, and has remained (mostly) problem free for the last 8 years.

                In the meantime, the best I can offer as site administrator is to make amendments to comments if you send me any revisions.

                Like

    • Frits 2:38 pm on 22 August 2020 Permalink | Reply

      Making use of Jim’s analysis (and Brian’s at [{broken link removed}]) .

       
      from enigma import  SubstitutedExpression, irange 
      
      # AB = table tennis
      # minimum played is AB + CD + EF + GH - 300
      # maximum played is AB
      # maximum = X * minimum
      
      p = SubstitutedExpression([
          "GH > EF", 
          "EF > CD", 
          "CD > AB", 
          "AB % (AB + CD + EF + GH - 300) == 0", 
          "(AB + CD + EF + GH - 300) > 10",
         ], 
          verbose=0, 
          answer="AB,CD,EF,GH",
          digits=irange(1, 9))
        
      # Print answers
      for (_, ans) in p.solve(verbose=0):
        print(f"{ans} minimum={sum(ans)-300} maximum={ans[0]}")
      
      # Output:
      #
      # (65, 74, 83, 91) minimum=13 maximum=65
      # (65, 73, 84, 91) minimum=13 maximum=65
      # (65, 74, 81, 93) minimum=13 maximum=65
      # (65, 71, 84, 93) minimum=13 maximum=65
      # (65, 73, 81, 94) minimum=13 maximum=65
      # (65, 71, 83, 94) minimum=13 maximum=65
      

      Like

    • GeoffR 3:25 pm on 22 August 2020 Permalink | Reply

      @Frits: You probably don’t know, but there is a sort of convention in Brian/Jim’s groups for programmed solutions with the answer not to be published early. This helps to minimise people entering the Sunday Times Prize Draw competition if they are just looking for the answer to take part in the draw, without attempting the puzzle.

      Like

      • Frits 4:46 pm on 22 August 2020 Permalink | Reply

        @GeoffR.
        Thanks. I keep that in mind.

        Like

    • John Crabtree 6:22 pm on 23 August 2020 Permalink | Reply

      The maximum is not A, but min(A, (A + B + C + D – 100) / 3)

      Like

      • Jim Randell 8:45 pm on 23 August 2020 Permalink | Reply

        @John: You are, of course, quite right. Thanks.

        I originally came up with the maximum without making the assumption that every member participated in at least one sport. But then I used that assumption to determine the minimum, and I neglected to revisit the maximum.

        I have provided code above that allows you to select whether participation in zero sports is allowed or not.

        Like

        • Jim Randell 10:08 pm on 26 August 2020 Permalink | Reply

          Actually, it looks like it doesn’t matter if we allow members who participate in 0 sports or not. The possible numbers presented to the secretary are the same in both cases, and so is the answer to the puzzle.


          The minimum intersection size is given by: max(0, T − 300).

          And we require this to be a 2 digit number.

          So we must have:

          T − 300 ≥ 10
          T ≥ 310

          And T is the sum of four 2-digit numbers, all with different non-zero digits.

          The largest we can make the units digits of our four numbers is 6 + 7 + 8 + 9 = 30.

          So the tens digits have to sum to at least 28, so the numbers are of the form:

          4a + 7b + 8c + 9d = 280 + (a + b + c + d)
          5a + 6b + 8c + 9d = 280 + (a + b + c + d)
          5a + 7b + 8c + 9d = 290 + (a + b + c + d)
          6a + 7b + 8c + 9d = 300 + (a + b + c + d)

          In the first case the maximum value of (a + b + c + d) is (6 + 5 + 3 + 2) = 16, giving a maximum possible total of 296, so this is not feasible.

          In the second case the maximum value of(a + b + c + d) is (7 + 4 + 3 + 2) = 16, giving a maximum possible total of 296, so this is not feasible.

          In the third case the maximum value of(a + b + c + d) is (6 + 4 + 3 + 2) = 15, giving a maximum possible total of 305, so this is not feasible.

          In the fourth case the maximum value of (a + b + c + d) is (5 + 4 + 3 + 2) = 14, giving a maximum possible total of 314, so this is feasible.

          So the four numbers must be of the form: 6a, 7b, 8c, 9d

          The size of the smallest set is thus: 61, 62, 63, 64, or 65.

          And the smallest possible value of floor((T − 100) / 3) = floor((310 − 100) / 3) = 70.

          So, in this case, the maximum intersection size is always the same as the size of the smallest set, whether we allow participants of zero sports or not.

          Like

  • Jim Randell 9:34 pm on 14 August 2020 Permalink | Reply
    Tags:   

    Teaser 3021: Field for thought 

    From The Sunday Times, 16th August 2020 [link]

    Farmer Giles had a rectangular field bordered by four fences that was 55 hectares in size. He divided the field into three by planting two hedges, from the mid-point of two fences to two corners of the field. He then planted two more hedges, from the mid-point of two fences to two corners of the field. All four hedges were straight, each starting at a different fence and finishing at a different corner.

    What was the area of the largest field when the four hedges had been planted?

    [teaser3021]

     
    • Jim Randell 10:24 pm on 14 August 2020 Permalink | Reply

      The x and y co-ordinates of the intersections of the hedges helpfully divide the edges of the rectangle into equal divisions.

      The area of the central quadrilateral is then easily calculated.

      Solution: The central field has an area of 11 hectares.

      In the first diagram, each of the four coloured triangular areas has an area of xy/5, so the central region also has an area of xy/5.

      Another way to think of it is that there are five quadrilaterals each identical to the central one, but four of them have had bits sliced off them, and then the sliced off bits have been repositioned to make the original rectangle.

      This gives a handy practical construction achievable using folding and straight edge to divide a rectangle into 5 equal strips (or a 5×5 grid of identical smaller rectangles).


      This is a bit like Routh’s Theorem (see: Enigma 1313Enigma 320Enigma 1076, Teaser 2865) but for a rectangle instead of a triangle.

      In general, if the the lines are drawn from a corner to a point a fraction f along a side we can determine the area of the central quadrilateral (as a fraction of the overall parallelogram) as:

      A = (1 − f)² / (1 + f²)

      In the case of f = 1/2 we get:

      A = (1/2)² / (1 + (1/2)²) = (1/4) / (5/4) = 1/5

      Like

  • Jim Randell 4:35 pm on 7 August 2020 Permalink | Reply
    Tags:   

    Teaser 3020: Baz’s bizarre arrers 

    From The Sunday Times, 9th August 2020 [link]

    “Bizarrers” dartboards have double and treble rings and twenty sectors ordered as on this normal dartboard [shown above]. However, a sector’s central angle (in degrees) is given by (100 divided by its basic score). The 20 sector incorporates the residual angle to complete 360º.

    Each player starts on 501 and reduces this, eventually to 0 to win. After six three-dart throws, Baz’s seventh could win. His six totals were consecutive numbers. Each three-dart effort lodged a dart in each of three clockwise-adjacent sectors (hitting, in some order, a single zone, a double zone and a treble zone). [Each] three-sector angle sum (in degrees) exceeded that total.

    The sectors scored in are calculable with certainty, but not how many times hit with certainty, except for one sector.

    Which sector?

    This puzzle uses a different spelling for “arraz” from the previous puzzle involving Baz (Teaser 2934).

    [teaser3020]

     
    • Jim Randell 5:21 pm on 7 August 2020 Permalink | Reply

      This Python program runs in 52ms.

      Run: [ @replit ]

      from fractions import Fraction as F
      from collections import defaultdict
      from itertools import product
      from enigma import tuples, subsets, multiset, seq_all_same, intersect, join, printf
       
      # sectors of the dartboard
      board = [ 20, 1, 18, 4, 13, 6, 10, 15, 2, 17, 3, 19, 7, 16, 8, 11, 14, 9, 12, 5 ]
      
      # map scores from 1 to 19 to sector angles (in degrees)
      angle = dict((n, F(100, n)) for n in board if n != 20)
      # the 20 sector completes the board
      angle[20] = 360 - sum(angle.values())
       
      # consider 3 adjacent sectors
      d = defaultdict(list) # store the results by the score (single, double, treble)
      for ss in tuples(board + board[:2], 3):
        # calculate the sector angle sum
        a = sum(angle[s] for s in ss)
        # choose multipliers for the scores
        for ms in subsets(ss, size=len, select="P"):
          # calculate the total
          t = sum(s * m for (m, s) in enumerate(ms, start=1))
          # which is less than the angle sum
          if not (t < a): continue
          d[t].append(ms)
      
      # look for 6 consecutive scores
      for ts in tuples(sorted(d.keys()), 6):
        if not (ts[0] + 5 == ts[-1]): continue
        # produce possible sets of scoring sectors
        mss = list(multiset.from_seq(*ss) for ss in product(*(d[t] for t in ts)))
        # each set of sectors should be the same
        if not seq_all_same(set(m.keys()) for m in mss): continue
        # look for common (sector, count) pairs for all possible scores
        ps = intersect(m.items() for m in mss)
        if len(ps) == 1:
          # output solution
          for (s, n) in ps:
            printf("sector = {s} [count = {n}]")
          printf("  scores = {ts}")
          for t in ts:
            printf("    {t}: {ss}", ss=join(d[t], sep=" "))
      

      Solution: We can say for certain that the 4 sector was hit twice.

      Baz’s 6 scores were (in consecutive order): 58, 59, 60, 61, 62, 63.

      So he has 138 left to score. (Which is achievable in many ways with 3 darts (assuming standard rules of darts apply), for example: treble 20, treble 20, double 9).

      Possible ways to make the first 6 scores with consecutive sectors are:

      58 = (single 3, double 2, treble 17)
      59 = (single 20, double 18, treble 1); (single 10, double 2, treble 15); (single 2, double 3, treble 17)
      60 = (single 4, double 1, treble 18)
      61 = (single 18, double 20, treble 1)
      62 = (single 2, double 15, treble 10)
      63 = (single 1, double 4, treble 18)

      We don’t know which of the alternatives makes up the 59, but whichever is chosen the 4 sector is used twice (in scoring 60 and 63), and the full list of sectors used is: 1, 2, 3, 4, 10, 15, 17, 18, 20.

      There is only one other possible consecutive set of consecutive scores: (41, 42, 43, 44, 45, 46), but this leaves a 240 finish which is not possible with 3 darts (at least not using the standard rules of darts, but maybe there is a way to score at least 80 with one dart on this strange dartboard, or another rule that would allow Baz to win that we don’t know about). But it also turns out that with this set of scores we cannot be certain which sectors were definitely used to make the scores either, so this possibility is excluded without us needing to know the exact rules for the variation of darts being used in the puzzle.

      Like

      • Frits 12:17 pm on 9 August 2020 Permalink | Reply

        It wasn’t easy for me to understand this puzzle. Only after seeing the code it became clear.

        “After six three-dart throws, Baz’s seventh could win”.

        You don’t seem to check that after six three-dart throws Baz has scored at least 331 points.

        With this extra check the 41-46 range can be eliminated earlier (ts[0] ≥ 52).

        Like

        • Jim Randell 12:24 pm on 9 August 2020 Permalink | Reply

          @Frits: There are two possible sets of six consecutive scores, but one is eliminated by the requirement that we can be certain of the sectors that were definitely used to make the scores. It also turns out that it would not be possible to win with three darts from this position (at least on a normal dart board), and it is possible for the other set of six consecutive scores (in many ways, which can easily be seen), so I didn’t incorporate that test into my code, as it seemed to be superfluous (although probably useful in a manual solution).

          Like

          • Frits 5:17 pm on 9 August 2020 Permalink | Reply

            Agree.

            If the six totals had come out as f.i. 54-59 the score after six three-dart throws would have been 339 leaving 162 which is not a finish at darts.

            If the program is intended to find a quick solution which has to be checked manually that’s OK with me.

            Like

            • Jim Randell 8:30 am on 12 August 2020 Permalink | Reply

              Here is a modified version of my program that ensures that Baz can finish on his 7th throw [ @replit ].

              Although as previously noted, this doesn’t change the solutions found.

              The puzzle text only states that the remaining total should be reduced to 0, so that’s what I’ve implemented. No requirement for the final dart to be a double, and as no inner or outer bull is mentioned I have not included them either.

              New Scientist Puzzle #06 explores scores achievable with n darts (on a standard dartboard).

              Like

    • Robert Brown 1:07 am on 10 August 2020 Permalink | Reply

      That total doesn’t work. You need 58-63, which can be made 3 different ways. Total is 363 leaving 138 which can be finished with any 3 darts that sum to 46, all of which are trebles. It’s quite quick to manually check the 3 different sequences: there’s one sector that appears the same number of times in each sequence, which is the required answer.

      Like

      • Jim Randell 8:55 am on 10 August 2020 Permalink | Reply

        @Robert: I’m not sure what total you are objecting to. Also I understood that in standard rules of darts you have to finish on a double. (Although in the version of the game used in the puzzle we are not told what the rules for finishing are. Fortunately though, of the two possible consecutive sequences of scores one of them is ruled out for reasons that are explained in the puzzle, so we don’t need to know the rules for finishing. We are just told that Baz could finish on his next throw, which is nice for him, but inconsequential for us).

        Like

    • Robert Brown 8:22 pm on 10 August 2020 Permalink | Reply

      I don’t know the rules of darts! The total that I found (58,59,60,61,62,63) needs 138 to finish, so I assumed finishing on trebles was ok. But they tell me that a bull’s eye counts as 50, so you can finish with 2 bull’s eyes & a double 19.
      I was objecting to Frits’s 6 totals (54-59) which I don’t see as a possibility. The important thing about my sequence is that there are 3 way to make 59, which changes the number of times that each sector is called, except for one which is the answer.

      Like

      • Jim Randell 10:23 pm on 10 August 2020 Permalink | Reply

        @Robert: Right. I believe Frits only gave those numbers as a hypothetical example to illustrate his point.

        You have found the right set of scores that leads to the answer. And fortunately (as I said above) you don’t need to know the rules of darts to eliminate the only other possible consecutive sequence of scores.

        Like

    • GeoffR 8:40 am on 12 August 2020 Permalink | Reply

      I had the idea of defining a valid function for three adjacent sectors – i.e.valid if the six totals were less than the sum of the three angles. This enabled the code below to find the unique six consecutive totals, but not the single requested sector.

      
      from itertools import permutations
      from collections import defaultdict
      D = defaultdict(set)
      
      L, L2 = [], []
      
      # function to check if a three-sector is valid
      # a, b, c are adjacent sector numbers
      def is_valid(a, b, c):
        asum = sum(100 / x for x in (a, b, c))
        ps = []
        for p3 in permutations((a, b, c)):
          score = sum(m * x for m, x in zip((1, 2, 3), p3))
          if score < asum:
            ps.append(score)
        return ps
      
      # the scores starting at north and running clockwise
      db = (20, 1, 18, 4, 13, 6, 10, 15,  2, 17,
            3, 19, 7, 16, 8, 11, 14, 9, 12, 5)
      
      for p in range(20):
        p3 = tuple((p + i) % 20 for i in (0, 1, 2))
        sc = tuple(db[i] for i in p3)
        L.append(sc)
      
      for x in range(20):
        a, b, c = L[x]
        s6 = is_valid(a, b, c)
        if s6:
          L2.append(s6)
      
      for p in permutations(L2,6):
        L1, L2, L3, L4, L5, L6 = p
        
        L22 = sorted(L1 + L2 + L3 + L4 + L5 + L6)
        L22 = sorted(list(set(L22)))
        
        for b in range(0, len(L22)-6):
          b1  = L22[b:b+6]
          # split slice into six totals
          a0, b0, c0, d0, e0, f0 = b1
          # total of six scores
          s = a0 + b0 + c0 + d0 + e0 + f0
          # total must be less than 180 to close with the 7th set of 3 darts
          # else there is another set of 6 consecutive numbers in the forties
          if 501 - s > 180:
            continue
          # check six numbers are consecutive
          if b0-a0 == c0-b0 == d0-c0 == e0-d0 == f0-e0 == 1:
            D[s].add ((a0,b0,c0,d0,e0,f0))
      
      for k,v in D.items():
        print(f"Sum of six 3 dart totals = {k}")
        print(f"Unique six totals are {v}")
        sc_left = 501 - k
        print(f"Seventh group of three darts score = {sc_left}")
        print(f"7th 3 darts group could be 3*18 + 3*20 + 2*12 = 138")
        print(f"Finishing on a double!")
      
      # Sum of six 3 dart totals = 363
      # Unique six totals are {(58, 59, 60, 61, 62, 63)}
      # Seventh group of three darts score = 138
      # 7th 3 darts group could be 3*18 + 3*20 + 2*12 = 138
      # Finishing on a double!
      
      
      

      I looked at a print out of Jim’s dictionary which gives the same six consecutive totals and the triples used in each of the numbers 58,59,60,61, 62 and 63.

      scores = (58, 59, 60, 61, 62, 63)
      58: (3, 2, 17)
      59: (20, 18, 1) (10, 2, 15) (2, 3, 17)
      60: (4, 1, 18)
      61: (18, 20, 1)
      62: (2, 15, 10)
      63: (1, 4, 18)

      The number 59 has three triples and all these digits appear in the numbers 58,60,61,62 and 63. The total of 363 can therefore be made up three ways. All three ways require the numbers 60 and 63, which also contain the digit ‘4’, so we can say thet the digit ‘4’ definitely occurs twice.

      A minor variation to my programme found the only eight valid sectors were:
      (20, 1, 18), (1, 18, 4), (4, 13, 6), (10, 15, 2),
      (15, 2, 17), (2, 17, 3), (3, 19, 7), (5, 20, 1)

      Jim’s dictionary above show that only four of these eight triples were needed for the final solution;
      i.e (2,3,17), (20,18,1), (10,2,15), (4,1,18)

      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: