Updates from Jim Randell Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 8:07 am on 17 December 2020 Permalink | Reply
    Tags:   

    Teaser 2767: Cutting corners 

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

    To make an unusual paperweight a craftsman started with a cuboidal block of marble whose sides were whole numbers of centimetres, the smallest sides being 5cm and 10cm long. From this block he cut off a corner to create a triangular face; in fact each side of this triangle was the diagonal of a face of the original block. The area of the triangle was a whole number of square centimetres.

    What was the length of the longest side of the original block?

    [teaser2767]

     
    • Jim Randell's avatar

      Jim Randell 8:08 am on 17 December 2020 Permalink | Reply

      Assuming the block is a rectangular cuboid (like a brick), lets us calculate the diagonals of the faces using Pythoagoras’ Theorem. (But this isn’t the only type of cuboid, see: [ @wikipedia ]).

      Suppose the sides of the block are (a, b, c).

      Then the lengths of the diagonals are: (x, y, z) = (√(a² + b²), √(a² + c²), √(b² + c²)).

      Using the following variant of Heron’s Formula [ @wikipedia ] for the area of a triangle with sides (x, y, z)

      4A = √(4x²y² − (x² + y² − z²)²)

      We can simplify this to calculate the area of a triangle formed by the diagonals as:

      4A = √(4(a² + b²)(a² + c²) − (2a²)²)
      2A = √(a²b² + a²c² + b²c²)

      And we are interested in when the area A is an integer, for given values of a and b.

      A = (1/2)√(a²b² + a²c² + b²c²)

      This Python program looks for the smallest solution for side c. It runs in 44ms.

      Run: [ @replit ]

      from enigma import (irange, inf, is_square, div, printf)
      
      # the smallest 2 sides are given
      (a, b) = (5, 10)
      (a2, b2) = (a * a, b * b)
      
      # consider values for the longest side
      for c in irange(b + 1, inf):
        c2 = c * c
      
        # calculate the area of the triangle
        r = is_square(a2 * b2 + a2 * c2 + b2 * c2)
        if r is None: continue
        A = div(r, 2)
        if A is None: continue
      
        # output solution
        printf("a={a} b={b} c={c}; A={A}")
        break # only need the first solution
      

      Solution: The longest side of the original block was 40 cm.


      In this case we are given a = 5, b= 10, so we have:

      4A² = 2500 + 125c²
      4A² = 125(20 + c²)
      c² = 4A²/125 − 4.5
      c = √(4A²/125 − 20)

      For c to be an integer, it follows the 4A² is divisible by 125 = 5³. So A is some multiple of 25, larger than 25.

      And we quickly find a solution, either manually, or using a program:

      from enigma import (irange, inf, is_square, div, printf)
      
      # consider values for the longest side
      for A in irange(50, inf, step=25):
        c = is_square(div(4 * A * A, 125) - 20)
        if c is not None:
          # output solution
          printf("a={a} b={b} c={c}; A={A}", a=5, b=10)
          break # only need the first solution
      

      However, this is not the only solution. If we leave the program running we find larger solutions:

      a=5 b=10 c=40; A=225
      a=5 b=10 c=720; A=4025
      a=5 b=10 c=12920; A=72225
      a=5 b=10 c=231840; A=1296025
      a=5 b=10 c=4160200; A=23256225
      a=5 b=10 c=74651760; A=417316025
      a=5 b=10 c=1339571480; A=7488432225

      These further solutions could have been eliminated by putting a limit on the size of the block (e.g. if the longest side was less than 7m long, which it probably would be for a desk paperweight).

      But we can generate these larger solutions more efficiently by noting that we have a form of Pell’s equation:

      4A² = a²b² + a²c² + b²c²
      (2A)² − (a² + b²)c² = a²b²

      writing:

      X = 2A
      D = a² + b²
      Y = c
      N = a²b²

      we get:

      X² − D.Y² = N

      And we are interested in solutions to the equation where X is even, and Y > b.

      We can use the pells.py solver from the py-enigma-plus repository to efficiently generate solutions:

      from enigma import (arg, ifirst, printf)
      import pells
      
      (a, b) = (5, 10)
      
      # given (a, b) generate solutions for (c, A) in c order
      def solve(a, b):
        (a2, b2) = (a * a, b * b)
        # solve: (a^2 + b^2).c^2 - 4.A^2 = -(a^2.b^2)
        for (c, A) in pells.diop_quad(a2 + b2, -4, -a2 * b2):
          if c > b:
            yield (c, A)
      
      # output the first N solutions
      N = arg(20, 0, int)
      for (c, A) in ifirst(solve(a, b), N):
        printf("a={a} b={b} c={c}; A={A}")
      

      Which gives the following output:

      a=5 b=10 c=40; A=225
      a=5 b=10 c=720; A=4025
      a=5 b=10 c=12920; A=72225
      a=5 b=10 c=231840; A=1296025
      a=5 b=10 c=4160200; A=23256225
      a=5 b=10 c=74651760; A=417316025
      a=5 b=10 c=1339571480; A=7488432225
      a=5 b=10 c=24037634880; A=134374464025
      a=5 b=10 c=431337856360; A=2411251920225
      a=5 b=10 c=7740043779600; A=43268160100025
      a=5 b=10 c=138889450176440; A=776415629880225
      a=5 b=10 c=2492270059396320; A=13932213177744025
      a=5 b=10 c=44721971618957320; A=250003421569512225
      a=5 b=10 c=802503219081835440; A=4486129375073476025
      a=5 b=10 c=14400335971854080600; A=80500325329753056225
      a=5 b=10 c=258403544274291615360; A=1444519726560481536025
      a=5 b=10 c=4636863460965394995880; A=25920854752758914592225
      a=5 b=10 c=83205138753102818310480; A=465130865823099981124025
      a=5 b=10 c=1493055634094885334592760; A=8346434730063040745640225
      a=5 b=10 c=26791796274954833204359200; A=149770694275311633440400025
      ...
      

      Solutions for the longest side (c) and area (A) can be calculated by the following recurrence relation:

      (c, A) → (40, 225)
      (c, A) → (9c + 8A/5, 50c + 9A)

      Like

  • Unknown's avatar

    Jim Randell 9:20 am on 15 December 2020 Permalink | Reply
    Tags:   

    Teaser 1967: Domino effect 

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

    I have placed a full set of 28 dominoes on an eight-by-seven grid, with some of the dominoes horizontal and some vertical. The array is shown above with numbers from 0 to 6 replacing the spots at each end of the dominoes.

    Fill in the outlines of the dominoes.

    This puzzle is included in the book Brainteasers (2002). The puzzle text above is taken from the book.

    [teaser1967]

     
    • Jim Randell's avatar

      Jim Randell 9:20 am on 15 December 2020 Permalink | Reply

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

      Run: [ @repl.it ]

      from enigma import DominoGrid
      
      DominoGrid(8, 7, [
        1, 6, 3, 3, 5, 6, 6, 0,
        2, 6, 2, 5, 4, 4, 3, 3,
        3, 6, 6, 5, 0, 4, 1, 3,
        2, 4, 5, 0, 0, 1, 1, 4,
        4, 4, 1, 1, 0, 2, 0, 6,
        0, 4, 3, 2, 0, 2, 2, 6,
        2, 1, 5, 5, 5, 5, 1, 3,
      ]).run()
      

      Solution: The completed grid is shown below:

      Like

    • Frits's avatar

      Frits 2:00 pm on 19 December 2020 Permalink | Reply

      You have to press a key each time for finding new dominoes/stones.

      import os
      from collections import defaultdict
        
      # grid dimensions (rows, columns)
      (R, C) = (7 ,8)
       
      g = [
          1, 6, 3, 3, 5, 6, 6, 0,
          2, 6, 2, 5, 4, 4, 3, 3,
          3, 6, 6, 5, 0, 4, 1, 3,
          2, 4, 5, 0, 0, 1, 1, 4,
          4, 4, 1, 1, 0, 2, 0, 6,
          0, 4, 3, 2, 0, 2, 2, 6,
          2, 1, 5, 5, 5, 5, 1, 3,
          ]
      
      # return coordinates of index number <n> in list <g>
      coord = lambda n: (n // C, n % C)
      
      # return index number in list <g>
      gnum = lambda x, y: x * C + y
      
      # return set of stone numbers in list <li>, like {'13', '15', '12'}
      domnums = lambda li: set("".join(sorted(str(li[i][1]) + str(li[i+1][1]))) 
                           for i in range(0, len(li), 2))
      
      # build dictionary of coordinates per stone
      def collect_coords_per_stone()  : 
        # empty the dictionary
        for k in coords_per_stone: coords_per_stone[k] = []
        
        for (i, d) in enumerate(g):
          if d < 0: continue           # already placed?
          # (x, y) are the coordinates in the 2 dimensional matrix
          (x, y) = divmod(i, C) 
          js = list()
          # horizontally
          if y < C - 1 and not(g[i + 1] < 0): js.append(i + 1)
          # vertically
          if x < R - 1 and not(g[i + C] < 0): js.append(i + C)
          
          # try possible placements
          for j in js:
            stone = tuple(sorted((g[i], g[j])))
            if ((coord(i), coord(j))) in ex: continue
           
            if not stone in done:
              coords_per_stone[stone] += [[coord(i), coord(j)]]
           
      # coordinate <mand> has to use stone {mandstone> so remove other possibilities
      def remove_others(mand, mandstone, reason):  
        global stop
        mandval = g[gnum(mand[0], mand[1])]
        stones = stones_per_coord[mand]
        for i in range(0, len(stones), 2):
          otherval = stones[i+1][1] if stones[i][0] == mand else stones[i][1]
          stone = sorted([mandval, otherval])
          # stone at pos <mand> unequal to <mandstone> ?
          if stone != mandstone:
            otherco = stones[i+1][0] if stones[i][0] == mand else stones[i][0]
            tup = tuple(sorted([mand, otherco]))
            if tup in ex: continue
            print(f"stone at {yellow}{str(tup)[1:-1]}{endc} "
                  f"cannot be {stone} {reason}")
            ex[tup] = stone
            stop = 0
      
      # check for unique stones and for a coordinate occurring in all entries 
      def analyze_coords_per_stone():
        global step, stop
        for k, vs in sorted(coords_per_stone.items()): 
          k_stone = tuple(sorted(k))
          if len(vs) == 1:
            pair = vs[0]
            x = gnum(pair[0][0], pair[0][1])
            y = gnum(pair[1][0], pair[1][1])
            if list(k_stone) in done: continue
      
            print(f"----  place stone {green}{k_stone}{endc} at coordinates "
                  f"{yellow}{pair[0]}, {pair[1]}{endc} (stone occurs only once)")
            done.append(k_stone)
            g[x] = g[y] = step
            step -= 1
            stop = 0
          elif len(vs) != 0:
            # look for a coordinate occurring in all entries
            common = [x for x in vs[0] if all(x in y for y in vs[1:])]
            if len(common) != 1: continue
            reason = " (coordinate " + yellow + str(common)[1:-1] + \
                     endc + " has to use stone " + str(k) + ")"
            # so remove <common> from other combinations
            remove_others(common[0], sorted(k), reason)
      
      # build dictionary of stones per coordinate
      def collect_stones_per_coord():
        stones = defaultdict(list)
        # collect stones_per_coord per cell
        for (i, d) in enumerate(g):
          if d < 0: continue      # already placed?
          # (x, y) are the coordinates in the 2 dimensional matrix
          (x, y) = divmod(i, C) 
          
          js = list()
          # horizontally
          if y < C - 1 and not(g[i + 1] < 0): js.append(i + 1)
          if y > 0     and not(g[i - 1] < 0): js.append(i - 1)
          # vertically
          if x < R - 1 and not(g[i + C] < 0): js.append(i + C)
          if x > 0     and not(g[i - C] < 0): js.append(i - C)
          # try possible placements
          for j in js:
            t = [[coord(i), g[i]], [coord(j), g[j]]]
            t2 = tuple(sorted((coord(i), coord(j))))
            if t2 not in ex:
              stones[(x, y)] += t
              
        return stones
        
      # check if only one stone is possible for a coordinate  
      def one_stone_left():
        global step, stop
        for k, vs in sorted(stones_per_coord.items()): 
          if len(vs) != 2: continue  
      
          pair = vs
          x = gnum(pair[0][0][0], pair[0][0][1])
          y = gnum(pair[1][0][0], pair[1][0][1])
          if g[x] < 0 or g[y] < 0: return
          
          stone = sorted([g[x], g[y]])  
          if stone in done: continue
      
          print(f"----  place stone {green}{tuple(stone)}{endc} at coordinates "
                f"{yellow}{str(sorted((pair[0][0], pair[1][0])))[1:-1]}{endc}, "
                f"(only one possible stone left)")
          done.append(stone)
          g[x] = g[y] = step
          step -= 1
          stop = 0
      
      
      # if n fields only allow for n stones we have a group
      def look_for_groups():
        global stop
        for n in range(2, 5):
          for group in findGroups(n, n, list(stones_per_coord.items())):
            # skip for adjacent fields 
            a1 = any(x[0] == y[0] and abs(x[1] - y[1]) == 1 
                     for x in group[1] for y in group[1])
            if a1: continue
            a2 = any(x[1] == y[1] and abs(x[0] - y[0]) == 1 
                     for x in group[1] for y in group[1])
            if a2: continue
      
            for d in group[0]:
              # get stone number
              tup = tuple(int(x) for x in d)
              for c in coords_per_stone[tup]:
                # skip coordinates in our group 
                if len(set(c) & set(group[1])) > 0: continue
                
                tup2 = tuple(c)
                if g[gnum(tup2[0][0], tup2[0][1])] < 0: continue
                if g[gnum(tup2[1][0], tup2[1][1])] < 0: continue
                if tup2 in ex: continue
                print(f"stone at {yellow}{str(tup2)[1:-1]}{endc} cannot be "
                      f"{list(tup)}, group ({', '.join(group[0])}) "
                      f"exists at coordinates {yellow}{str(group[1])[1:-1]}{endc}")
                ex[tup2] = list(tup)
                stop = 0
          if stop == 0: return    # skip the bigger groups
      
      # pick <k> elements from list <li> so that all picked elements use <n> values
      def findGroups(n, k, li, s=set(), f=[]):
        if k == 0:
          yield (list(s), f)
        else:
          for i in range(len(li)):
            # get set of stone numbers
            vals = domnums(li[i][1])
            if len(s | vals) <= n:
              yield from findGroups(n, k - 1, li[i+1:], s | vals, f + [li[i][0]])  
      
      def print_matrix(mat, orig):
        # https://en.wikipedia.org/wiki/Box-drawing_character
        global g_save
        nw = '\u250c'    #   N
        ne = '\u2510'    # W   E
        ho = '\u2500'    #   S
        ve = '\u2502' 
        sw = '\u2514' 
        se = '\u2518'
        
        numlist = "".join(["    " + str(i) for i in range(C)]) + "   "
        print("\n\x1b[6;30;42m" + numlist + "\x1b[0m")
        for i in range(R):
          top = ""
          txt = ""
          bot = ""
          prt = 0
          for j in range(C):
            v = mat[i*C + j]
            # original value
            ov = orig[i*C + j] if orig[i*C + j] > -1 else " "
            
            cb = green if v != g_save[i*C + j] else ""
            ce = endc if v != g_save[i*C + j] else ""
            
            o = orientation(mat, i*C + j, v)
            
            if o == 'N': 
              top += nw+ho+ho+ho+ne
              txt += ve+cb+ " " + str(ov) + " " + ce+ve
              bot += ve+ "   " + ve
            if o == 'S': 
              top += ve+ "   " + ve
              txt += ve+cb+ " " + str(ov) + " " + ce+ve
              bot += sw+ho+ho+ho+se  
            if o == 'W':   # already handle East as well
              top += nw+ho+ho+ho+ho+ho+ho+ho+ho+ne
              txt += ve+cb+ " " + str(ov) + "    " + str(orig[i*C + j + 1]) + " " + ce+ve
              bot += sw+ho+ho+ho+ho+ho+ho+ho+ho+se
            if o == '':  
              top += "     "
              txt += "  " + str(ov) + "  " 
              bot += "     "
          print("\x1b[6;30;42m \x1b[0m " + top + "\x1b[6;30;42m \x1b[0m")  
          print("\x1b[6;30;42m" + str(i) + "\x1b[0m " + txt + "\x1b[6;30;42m" + str(i) + "\x1b[0m")
          print("\x1b[6;30;42m \x1b[0m " + bot + "\x1b[6;30;42m \x1b[0m")  
        print("\x1b[6;30;42m" + numlist + "\x1b[0m")  
          
        g_save = list(g)
          
      def orientation(mat, n, v):
        if v > -1: return ""
        
        # (x, y) are the coordinates in the 2 dimensional matrix
        (x, y) = divmod(n, C) 
        # horizontally
        if y < C - 1 and mat[n + 1] == v: return "W"
        if y > 0     and mat[n - 1] == v: return "E"
        # vertically
        if x < R - 1 and mat[n + C] == v: return "N"
        if x > 0     and mat[n - C] == v: return "S"
        
        return ""
                     
       
      coords_per_stone = defaultdict(list)
      
      stop = 0
      step = -1
      green = "\033[92m"    
      yellow = "\033[93m"   
      endc = "\033[0m"    # end color
       
       
      done = []
      ex = defaultdict(list)
      
      os.system('cls||clear')
      
      g_orig = list(g)
      g_save = list(g)
      
      for loop in range(222):
        stop = 1
        prevstep = step
        
        stones_per_coord = collect_stones_per_coord()
        
        one_stone_left()
        
        if step == prevstep:
          collect_coords_per_stone()    
          analyze_coords_per_stone()
      
        if step < prevstep:
          print_matrix(g, g_orig) 
          if all(y < 0 for y in g):
            exit(0)
          letter = input('Press any key: ')
          os.system('cls||clear')
          print()
          continue
      
        # collect again as some possible placements may have been ruled out
        stones_per_coord = collect_stones_per_coord()
        look_for_groups()
      
        if stop: break
      
      
      print("----------------------- NOT SOLVED -----------------------------")
      
      print_matrix(g, g_orig) 
      

      Like

  • Unknown's avatar

    Jim Randell 9:45 am on 13 December 2020 Permalink | Reply
    Tags:   

    Teaser 1984: Which whatsit is which? 

    From The Sunday Times, 24th September 2000 [link]

    I have received three boxes of whatsits. They all look alike but those in one of the boxes weigh 6 grams each, those in another box all weigh 7 grams each, and all those in the remaining box weigh 8 grams each.

    I do not know which box is which but I have some scales which enable me to weigh accurately anything up to 30 grams. I with to use the scales to determine which whatsit is which.

    How can I do this with just one weighing?

    The text of this puzzle is taken from the book Brainteasers (2002), the wording differs only slightly from the puzzle originally published in the newspaper.

    The following note was added to the puzzle in the book:

    When this Teaser appeared in The Sunday Times, instead of saying “some scales” it said “a balance”. This implied to some readers that you could place whatsits on either side of the balance — which opens up all sorts of alternative approaches which you might like to think about.

    There are now 400 Teaser puzzles available on the site.

    [teaser1984]

     
    • Jim Randell's avatar

      Jim Randell 9:45 am on 13 December 2020 Permalink | Reply

      Evidently we need to find some selection from the three types of whatsit, such that from the value of their combined weight we can determine the weights of the individual types.

      If the scale did not have such a low maximum weight we could weigh 100 type A whatsits, 10 type B whatsits, and 1 type C whatsit, to get a reading of ABC, which would tell us immediately the weights of each type. (For example, if the total weight was 768g, we would know A = 7g, B = 6g, C = 8g).

      We first note that if we can determine the weights for two of the types, then the third types weight must be the remaining value. (Equivalently if the selection (a, b, c) determines the weights, so does selection (0, b − a, c − a) where a is the smallest count in the selection).

      So we need to find a pair of small numbers (as 6 or more of the lightest whatsits will give an error on the scales), that give a different outcome for each possible choice of whatsits.

      This Python program runs in 45ms.

      Run: [ @repl.it ]

      from enigma import (group, subsets, printf)
      
      # display for a weight of x
      weigh = lambda x: ("??" if x > 30 else str(x))
      
      # check the qunatities <ns> of weights <ws> are viable
      def check(ns, ws):
        # collect total weight
        d = group(subsets(ws, size=len, select="P"), by=(lambda ws: weigh(sum(n * w for (n, w) in zip(ns, ws)))))
        # is this a viable set?
        return (d if all(len(v) < 2 for v in d.values()) else None)
      
      # consider (a, b) pairs, where a + b < 6
      for (a, b) in subsets((1, 2, 3, 4), size=2):
        if a + b > 5: continue
        ns = (0, a, b)
        d = check(ns, (6, 7, 8))
        if d:
          # output solution
          printf("ns = {ns}")
          for k in sorted(d.keys()):
            printf("  {k:2s} -> {v}", v=d[k])
          printf()
      

      Solution: You should choose one whatsit from one of the boxes, and three whatsits from another box.

      The combined weight indicates what the weight of each type of whatsit is:

      25g → (0 = 8g, 1 = 7g, 3 = 6g)
      26g → (0 = 7g, 1 = 8g, 3 = 6g)
      27g → (0 = 8g, 1 = 6g, 3 = 7g)
      29g → (0 = 6g, 1 = 8g, 3 = 7g)
      30g → (0 = 7g, 1 = 6g, 3 = 8g)
      <error> → (0 = 6g, 1 = 7g, 3 = 8g) (actual weight = 31g)

      Like

    • Frits's avatar

      Frits 12:01 pm on 13 December 2020 Permalink | Reply

      from enigma import SubstitutedExpression, group
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [# pick not more than 5 whatsits from one or two boxes
         "min(X, Y, Z) == 0 and sum([X, Y, Z]) < 6",
         
         # don't allow all whatits to be picked from one box only
         "max(X, Y, Z) != sum([X, Y, Z])"
        ],
        answer="(X, Y, Z), X*6 + Y*7 + Z*8",
        d2i=dict([(k, "XYZ") for k in range(5,10)]),
        distinct="",
        verbose=0)   
      
      # collect weighing results
      res = [y for _, y in p.solve()]
      
      # group items based on X,Y,Z combinations    
      grp = group(res, by=(lambda a: "".join(str(x) for x in sorted(a[0]))))
      
      for g, vs in grp.items(): 
        # there should be 6 different weighing results in order to determine 
        # which whatsit is which 
        if (len(vs)) != 6: continue
        
        # group data by sum of weights
        grp2 = group(vs, by=(lambda a: a[1]))
        
        morethan30 = [1 for x in grp2.items() if x[0] > 30]
        if (len(morethan30) > 1): continue 
        
        ambiguous = [1 for x in grp2.items() if len(x[1]) > 1]
        if len(ambiguous) > 0: continue
        
        print("Solution", ", ".join(g), "\nweighings: ", vs)
      

      Like

      • Frits's avatar

        Frits 12:17 pm on 13 December 2020 Permalink | Reply

        I could have used “[X, Y, Z].count(0) == 1” but somehow count() is below my radar (probably because I have read that count() is/was quite expensive).

        Like

  • Unknown's avatar

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

    Teaser 3038: Progressive raffle 

    From The Sunday Times, 13th December 2020 [link] [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's avatar

      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's avatar

      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's avatar

      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's avatar

      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's avatar

      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's avatar

      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

  • Unknown's avatar

    Jim Randell 9:23 am on 10 December 2020 Permalink | Reply
    Tags:   

    Teaser 1966: Square of primes 

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

    If you place a digit in each of the eight unshaded boxes, with no zeros in the corners, then you can read off various three-figure numbers along the sides of the square, four in a clockwise direction and four anticlockwise.

    Place eight different digits in those boxes with the largest of the eight in the top right-hand corner so that, of the eight resulting three-figure numbers, seven are prime and the other (an anticlockwise one) is a square.

    Fill in the grid.

    This puzzle is included in the book Brainteasers (2002). The puzzle text above is taken from the book.

    [teaser1966]

     
    • Jim Randell's avatar

      Jim Randell 9:24 am on 10 December 2020 Permalink | Reply

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

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

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      #  A B C
      #  D   E
      #  F G H
      
      SubstitutedExpression
      
      # no zeros in the corners
      --invalid="0,ACFH"
      
      # C is the largest number
      "C > max(A, B, D, E, F, G, H)"
      
      # all the clockwise numbers are prime
      "is_prime(ABC)"
      "is_prime(CEH)"
      "is_prime(HGF)"
      "is_prime(FDA)"
      
      # three of the anticlockwise numbers are prime
      "icount((ADF, FGH, HEC, CBA), is_prime) = 3"
      
      # and the other one is square
      "icount((ADF, FGH, HEC, CBA), is_square) = 1"
      
      # answer grid
      --answer="((A, B, C), (D, E), (F, G, H))"
      

      Solution: The completed grid looks like this:

      Like

      • Frits's avatar

        Frits 2:42 pm on 10 December 2020 Permalink | Reply

        @Jim,

        A further optimization would be to limit A, F, and H to {1, 3, 5, 7} and C to {7, 9}.

        Like

    • Frits's avatar

      Frits 10:54 am on 10 December 2020 Permalink | Reply

      A solution with miniZinc.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      %  A B C
      %  D   E
      %  F G H
      
      % no zeros in the corners 
      var 1..9:A; var 0..9:B; var 1..9:C; 
      var 0..9:D; var 0..9:E; 
      var 1..9:F; var 0..9:G; var 1..9:H;
      
      % 3-digit numbers clockwise
      var 100..999: ABC = 100*A + 10*B + C;
      var 100..999: CEH = 100*C + 10*E + H;
      var 100..999: HGF = 100*H + 10*G + F;
      var 100..999: FDA = 100*F + 10*D + A;
      
      % 3-digit numbers anticlockwise
      var 100..999: CBA = 100*C + 10*B + A;
      var 100..999: HEC = 100*H + 10*E + C;
      var 100..999: FGH = 100*F + 10*G + H;
      var 100..999: ADF = 100*A + 10*D + F;
      
      constraint all_different([A, B, C, D, E, F, G, H]);
      
      predicate is_prime(var int: x) = 
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
      ((i < x) -> (x mod i > 0));
       
      predicate is_square(var int: y) = exists(z in 1..ceil(sqrt(int2float(ub(y)))))
       (z*z = y );
       
      % C is the largest number
      constraint C > max([A, B, D, E, F, G, H]);
      
      % all the clockwise numbers are prime
      constraint is_prime(ABC) /\ is_prime(CEH)
      /\ is_prime(HGF) /\ is_prime(FDA);
      
      % three of the anticlockwise numbers are prime
      constraint (is_prime(CBA) /\ is_prime(HEC)/\ is_prime(FGH))
      \/ (is_prime(CBA) /\ is_prime(HEC)/\ is_prime(ADF)) 
      \/ (is_prime(CBA) /\ is_prime(FGH) /\ is_prime(ADF))
      \/ (is_prime(HEC) /\ is_prime(FGH) /\ is_prime(ADF));
      
      % and the other one is square
      constraint is_square(CBA) \/ is_square(HEC)
      \/ is_square(FGH) \/ is_square(ADF);
       
      solve satisfy;
       
      output [ show(ABC) ++ "\n" ++ show(D) ++ " " ++ show(E) ++ "\n" ++ show(FGH) ];
      

      Like

    • GeoffR's avatar

      GeoffR 9:44 am on 11 December 2020 Permalink | Reply

      A solution in Python. formatted to PEP8:

      
      import time
      start = time.time()
      
      from itertools import permutations
      from enigma import is_prime
      
      digits = set(range(10))
      
      def is_sq(n):
        a = 2
        while a * a < n:
          a += 1
        return a * a == n
      
      for P1 in permutations(digits, 4):
        A, F, H, C = P1
        if C not in (7, 9):
          continue
        if 0 in (A, F, H, C):
          continue
        Q1 = digits.difference(P1)
        for P2 in permutations(Q1, 4):
          B, D, E, G = P2
          if C > max(A, B, D, E, F, G, H):
      
            # Four clockwise primes
            ABC, CEH = 100 * A + 10 * B + C, 100 * C + 10 * E + H
            HGF, FDA = 100 * H + 10 * G + F, 100 * F + 10 * D + A
            if sum([is_prime(ABC), is_prime(CEH),
                    is_prime(HGF), is_prime(FDA)]) == 4:
              ADF, FGH = 100 * A + 10 * D + F, 100 * F + 10 * G + H
              HEC, CBA = 100 * H + 10 * E + C, 100 * C + 10 * B + A
      
              # Three anti-clockwise primes
              if sum([is_prime(ADF), is_prime(FGH),
                      is_prime(HEC), is_prime(CBA)]) == 3:
      
                # One anti-clockwise square
                if sum([is_sq(ADF), is_sq(FGH),
                        is_sq(HEC), is_sq(CBA)]) == 1:
                  print(f"{A}{B}{C}")
                  print(f"{D} {E}")
                  print(f"{F}{G}{H}")
                  print(time.time() - start) # 0.515 sec
      
      # 389
      # 6 0
      # 157
      
      
      

      A solution in MiniZinc, first part similar to previous MiniZinc solution, the last part using a different approach to find the seven primes and the one square number:

      
      % A Solution in MiniZinc
      include "globals.mzn";
      %  A B C
      %  D   E
      %  F G H
       
      var 0..9:A; var 0..9:B; var 0..9:C; 
      var 0..9:D; var 0..9:E; var 0..9:F; 
      var 0..9:G; var 0..9:H;
      
      constraint A > 0 /\ C > 0 /\ H > 0 /\ F > 0;
      constraint all_different([A, B, C, D, E, F, G, H]);
       
      % Four 3-digit numbers clockwise
      var 100..999: ABC = 100*A + 10*B + C;
      var 100..999: CEH = 100*C + 10*E + H;
      var 100..999: HGF = 100*H + 10*G + F;
      var 100..999: FDA = 100*F + 10*D + A;
       
      % Four 3-digit numbers anti-clockwise
      var 100..999: CBA = 100*C + 10*B + A;
      var 100..999: HEC = 100*H + 10*E + C;
      var 100..999: FGH = 100*F + 10*G + H;
      var 100..999: ADF = 100*A + 10*D + F;
       
      set of int: sq3 = {n*n | n in 10..31}; 
       
      % Hakank's prime predicate
      predicate is_prime(var int: x) =
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
      ((i < x) -> (x mod i > 0));
       
      % C is the largest number
      constraint C > max([A, B, D, E, F, G, H]);
      
      % four clockwise prime numbers
      constraint sum([is_prime(ABC), is_prime(CEH), is_prime(HGF),
       is_prime(FDA)]) == 4;
       
      % three anti-clockwise prime numbers
      constraint sum([is_prime(CBA), is_prime(HEC), is_prime(FGH),
      is_prime(ADF)]) == 3;
      
      % one anti-clockwise square
      constraint sum([CBA in sq3, HEC in sq3, FGH in sq3,
      ADF in sq3]) == 1;
      
      solve satisfy;
        
      output ["Completed Grid: " ++ "\n"  ++ 
      show(ABC) ++ "\n" ++ 
      show(D) ++ " " ++ show(E) ++ "\n" ++ show(FGH) ];
      
      % Completed Grid: 
      % 389
      % 6 0
      % 157
      % ----------
      % ==========
      
      
      
      

      Like

    • Frits's avatar

      Frits 2:05 pm on 12 December 2020 Permalink | Reply

      Further analysis leads to C = 9 and square 361.

      from enigma import SubstitutedExpression
      
      #  A B C
      #  D   E
      #  F G H
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
        # C = 9
        # All corner numbers have to be odd and can't be number 5"
        # (otherwise somewhere a number xx5 is not prime and has to be square.
        #  xx5 is either 225 or 625 but their 1st digit is not odd)
         
        # all the clockwise numbers are prime
        "is_prime(10*AB + 9)",  # ABC
        "is_prime(900 + EH)",   # CEH
        "is_prime(HGF)",
        "is_prime(FDA)",
         
        # three of the anticlockwise numbers are prime
        "icount((ADF, FGH, 10*HE + 9, 900 + BA), is_prime) = 3",
         
        # and the other one is square
        "icount((ADF, FGH, 10*HE + 9, 900 + BA), is_square) = 1",
       
        ],
        answer="((A, B, 9), (D, E), (F, G, H))",
        digits=range(0, 9),
        d2i=dict([(k, "AFH") for k in {0, 2, 4, 5, 6, 8}] +
                 [(k, "BEDG") for k in {1, 3, 7}]),
        distinct="ABDEFGH",
        verbose=0)   
      
      # Print answers 
      for (_, ans) in p.solve():
          print(f"{ans}")
      
      # ((3, 8, 9), (6, 0), (1, 5, 7))
      

      Only one square is possible:

      from enigma import is_prime
      
      alldiff = lambda seq: len(seq) == len(set(seq))
      
      sqs = []
      # check 3-digit squares
      for i in range(11, 32):
        i2 = i * i
        # digits in square must all be different 
        # and number must start/end with an odd digit
        if not(alldiff(str(i2)) and i2 % 2 == 1 and (i2 // 100) % 2 == 1):
          continue
        # reverse square has to be prime
        if not(is_prime(int(str(i2)[::-1]))): continue
        sqs.append(i2)
      
      print("possible squares:")  
      for sq in sqs: 
        print(sq)
      
      # possible squares:
      # 361
      

      Like

  • Unknown's avatar

    Jim Randell 9:31 am on 8 December 2020 Permalink | Reply
    Tags:   

    Brain-Teaser 44: The Omnibombulator 

    From The Sunday Times, 21st January 1962 [link]

    This unusual instrument is operated by selecting one of the four switch positions: A, B, C, D, and turning the power on. The effects are:

    A: The pratching valve glows and the queech obulates;
    B: The queech obulates and the urfer curls up, but the rumption does not get hot;
    C: The sneeveling rod turns clockwise, the pratching valve glows and the queech fails to obulate;
    D: The troglodyser gives off hydrogen but the urfer does not curl up.

    Whenever the pratching valve glows, the rumption gets hot. Unless the sneeveling rod turns clockwise, the queech cannot obulate, but if the sneeveling rod is turning clockwise the troglodyser will not emit hydrogen. If the urfer does not curl up, you may be sure that the rumption is not getting hot.

    In order to get milk chocolate from the machine, you must ensure:

    (a) that the sneeveling rod is turning clockwise AND;
    (b) that if the troglodyser is not emitting hydrogen, the queech is not obulating.

    1. Which switch position would you select to get milk chocolate?

    If, tiring of chocolate, you wish to receive the Third Programme, you must take care:

    (a) that the rumption does not get hot AND;
    (b) either that the urfer doesn’t curl and the queech doesn’t obulate or that the pratching valve glows and the troglodyser fails to emit hydrogen.

    2. Which switch position gives you the Third Programme?

    No setter was given for this puzzle.

    This puzzle crops up in several places on the web. (Although maybe it’s just because it’s easy to search for: “the queech obulates” doesn’t show up in many unrelated pages).

    And it is sometimes claimed it “appeared in a national newspaper in the 1930s” (although the BBC Third Programme was only broadcast from 1946 to 1967 (after which it became BBC Radio 3)), but the wording always seems to be the same as the wording in this puzzle, so it seems likely this is the original source (at least in this format).

    “Omnibombulator” is also the title of a 1995 book by Dick King-Smith.

    [teaser44]

     
    • Jim Randell's avatar

      Jim Randell 9:33 am on 8 December 2020 Permalink | Reply

      Consider the following conditions:

      P = “the pratching valve glows”
      Q = “the queech obulates”
      R = “the rumption gets hot”
      S = “the sneeveling rod turns clockwise”
      T = “the troglodyser gives off hydrogen”
      U = “the urfer curls up”

      Then the positions can be described as:

      A = P ∧ Q
      B = Q ∧ U ∧ ¬R
      C = S ∧ P ∧ ¬Q
      D = T ∧ ¬U

      And we are also given the following constraints:

      P → R
      Q → S
      S → ¬T
      ¬U → ¬R

      And the conditions that produce outcomes we are told about are:

      milk chocolate = S ∧ (¬T → ¬Q)
      third programme = ¬R ∧ ((¬U ∧ ¬Q) ∨ (P ∧ ¬T))

      The following Python program looks at all possible combinations of P, Q, R, S, T, U, and checks that the constraints are not violated, then looks for which positions are operated, and which outcomes occur.

      It runs in 49ms.

      from enigma import (subsets, implies, join, printf)
      
      # consider possible values of the statements
      for (P, Q, R, S, T, U) in subsets((True, False), size=6, select="M"):
      
        # check the constraint hold:
        # P -> R
        if not implies(P, R): continue
        # Q -> S
        if not implies(Q, S): continue
        # S -> not(T)
        if not implies(S, not T): continue
        # not(U) -> not(R) [same as: R -> U]
        if not implies(not U, not R): continue
      
        # which positions are operated?
        ps = list()
        if P and Q: ps.append('A')
        if Q and U and (not R): ps.append('B')
        if S and P and (not Q): ps.append('C')
        if T and (not U): ps.append('D')
      
        # possible outcomes
        ss = list()
        if S and implies(not T, not Q): ss.append('milk chocolate')
        if (not R) and (((not U) and (not Q)) or (P and (not T))): ss.append('third programme')
      
        # output solution
        if ps:
          if not ss: ss = [ "???" ]
          printf("{ps} -> ({ss}) {vs}", ps=join(ps, sep=","), ss=join(ss, sep=", "), vs=[P, Q, R, S, T, U])
      

      Solution: 1. Position C produces milk chocolate; 2. Position D gives you the Third Programme.

      We don’t know what A and B do, but we can describe their affects on the machine:

      A: the pratching valve glows; the queech obulates; the rumption gets hot; the sneeveling rod turns clockwise; the troglodyser does not give off hydrogen; the urfer curls up

      B: the pratching valve does not glow; the queech obulates; the rumption does not get hot; the sneeveling rod turns clockwise; the troglodyser does not give off hydrogen; the urfer curls up

      C: the pratching valve glows; the queech obulates; the rumption gets hot; the sneeveling rod turns clockwise; the troglodyser does not give off hydrogen; the urfer curls up

      D: the pratching valve does not glow; the queech does not obulate; the rumption does not get hot; the sneeveling rod turns anticlockwise; the troglodyser gives off hydrogen; the urfer does not curl up

      Like

    • John Crabtree's avatar

      John Crabtree 4:39 am on 14 December 2020 Permalink | Reply

      Let a positive action be represented by an uppercase letter, and a negative action by a lowercase letter.
      Expressed as Boolean logic where “.” means AND and “+” means OR, the conditions are:
      1. P.R + p = 1
      2. q.s + S.t = 1
      3. r.u + U = 1
      Combining 1 and 3 gives ( P.R + p).(r.u + U) = P.R.U + p.u.r + p.U = 1
      And so (P.R.U + p.r,u + p.U).(q.s + S,t) = 1

      The four switches give:
      A. P.Q = 1 and so P.R.U.Q.S.t = 1
      B. r.U.Q = 1 and so p.r.U.Q.S.t = 1
      C. P.q.S = 1, and so P.R.U.q.S.t = 1, (milk chocolate)
      D. u.T = 1 and so p.r.u.q.s.T = 1, (Third programme)

      Switch C selects milk chocolate. Switch D gets the Third programme.

      A similar technique can also be used in Brain-Teasers 506 and 520.

      Like

  • Unknown's avatar

    Jim Randell 12:28 pm on 6 December 2020 Permalink | Reply
    Tags: by: K. G. Messenger   

    Brain-Teaser 14: Cross-country 

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

    In the annual cross-country race between the Harriers and the Greyhounds each team consists of eight men, of whom the first six in each team score points. The first man home scores one point, the second two, the third three, and so on. When these are added together, the team with the lower total wins the match.

    In this year’s match, the Harriers’ captain came in first and as his team followed he totted up the score. When five more Harriers and a number of Greyhounds had arrived, he found that it would be possible still for his team either to lose or to draw or to win, depending on the placings of the two Harriers yet to come.

    The tension was relieved slightly when the seventh Harrier arrived, since now the worst that could happen was a draw. Then, in an exciting finish, the eighth Harrier just beat one of his rivals to gain a win for his site by a single point.

    What were the scores? And what were the placings of the 16 runners assuming that no two runners tied for a place?

    [teaser14]

     
    • Jim Randell's avatar

      Jim Randell 12:28 pm on 6 December 2020 Permalink | Reply

      (See also: Enigma 1073, Enigma 1322, Enigma 1418).

      This Python program runs in 79ms.

      Run: [ @repl.it ]

      from enigma import (defaultdict, subsets, irange, diff, compare, printf)
      
      # record by first 6 H, if it is a win, draw, loss for H
      d6 = defaultdict(set)
      # and by first 7 H
      d7 = defaultdict(set)
      # and if H wins by 1 point
      rs = list()
      
      # calculate the scores, by positions of H runners
      def scores(hs):
        # scores are the sum of the positions of the first 6 runners
        return (sum(hs[:6]), sum(diff(irange(1, 16), hs)[:6]))
      
      # consider the positions of the H runners
      for hs in subsets(irange(2, 16), size=7):
        hs = (1,) + hs
        (H, G) = scores(hs)
      
        # compare scores: -1 = win for H; 0 = draw; +1 = win for G
        x = compare(H, G)
        d6[hs[:6]].add(x)
        d7[hs[:7]].add(x)
        if G == H + 1: rs.append(hs)
      
      # consider possible final outcomes
      for hs in rs:
        # look for situations where after the first 6 H's w/d/l is possible
        if d6[hs[:6]] != { -1, 0, 1 }: continue
        # and after the first 7 H's only w/d is possible
        if d7[hs[:7]] != { -1, 0 }: continue
      
        # output solution
        (H, G) = scores(hs)
        printf("H={H} G={G}; hs={hs}")
      

      Solution: The scores were Harriers = 40, Greyhounds = 41. Harriers took positions (1, 5, 7, 8, 9, 10, 11, 13). Greyhounds took positions (2, 3, 4, 6, 12, 14, 15, 16).

      Like

  • Unknown's avatar

    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] [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's avatar

      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's avatar

      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's avatar

        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's avatar

          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's avatar

            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's avatar

              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's avatar

              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's avatar

      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's avatar

        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's avatar

          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's avatar

            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's avatar

      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's avatar

        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's avatar

          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's avatar

        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's avatar

      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's avatar

        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

  • Unknown's avatar

    Jim Randell 11:53 am on 3 December 2020 Permalink | Reply
    Tags: ,   

    Teaser 1956: Moving the goalpost 

    From The Sunday Times, 12th March 2000 [link]

    We have a large rectangular field with a wall around its perimeter and we wanted one corner of the field fenced off. We placed a post in the field and asked the workment to make a straight fence that touched the post and formed a triangle with parts of two sides of the perimeter wall. They were to do this in such a way that the area of the triangle was as small as possible. They worked out the length of fence required (less than 60 metres) and went off to make it.

    Meanwhile, some lads played football in the field and moved the post four metres further from one side of the field and two metres closer to another.

    Luckily when the men returned with the fence it was still the right length to satisfy all the earlier requirements. When they had finished erecting it, the triangle formed had each of its sides equal to a whole number of metres.

    How long was the fence?

    This puzzle is included in the book Brainteasers (2002). The puzzle text above is taken from the book.

    [teaser1956]

     
    • Jim Randell's avatar

      Jim Randell 11:54 am on 3 December 2020 Permalink | Reply

      I thought the wording in this puzzle was a bit confusing. Moving the post 4 metres further from one side of the field is necessarily moving it 4 meters closer to another side of the field. I think we are to suppose the sides of the field are those that are used in forming the perimeter of the triangle, but in my code I considered all 8 potential positions.

      If the post is at (a, b), then we can show that the minimal area triangle (made with the x– and y-axes) is achieved when the fence runs from (2a, 0) to (0, 2b). So the post is at the mid-point of the fence.

      The final triangle is a Pythagorean triple with hypotenuse z, less than 60, and, if the hypotenuse passes through the point (a′, b′), then the other sides are, 2a′ and 2b′.

      So we need to look for points (a, b), where a and a′ differ by 2 or 4, and b and b′ differ by 4 or 2, such that (2a)² + (2b)² = z².

      This Python program runs in 46ms.

      Run: [ @replit ]

      from enigma import (pythagorean_triples, cproduct, Rational, printf)
      
      # choose a rational implementation
      Q = Rational()
      
      # consider pythagorean triples for the final triangle
      for (x, y, z) in pythagorean_triples(59):
        # and the position of the post
        (a1, b1) = (Q(x, 2), Q(y, 2))
        # consider the original position of the post
        for ((dx, dy), mx, my) in cproduct([((2, 4), (4, 2)), (1, -1), (1, -1)]):
          (a, b) = (a1 + mx * dx, b1 + my * dy)
          if a > 0 and b > 0 and 4 * (a * a + b * b) == z * z:
            printf("({x}, {y}, {z}) -> (a1, b1) = ({a1}, {b1}), (a, b) = ({a}, {b})")
      

      Solution: The fence is 25m long.

      The triangles are a (7, 24, 25) and a (15, 20, 25) triangle.

      The program finds 2 solutions as we don’t know which is the starting position and which is the final position:

      However, if the post is moved 2m closer to one of the axes and 4m further from the other axis, then blue must be the starting position and red the final position.

      Like

    • John Crabtree's avatar

      John Crabtree 3:30 pm on 4 December 2020 Permalink | Reply

      As shown above, the post is at the midpoint of the fence.
      Let the initial sides be A and B, and the new sides be A + 8 and B – 4.
      One can show that B = 2A + 10, and if the hypotenuse = B + n then A = 2n + sqrt(5n^2 + 20n),
      n = 1 gives A = 7, ie (7, 24, 25) and (15, 20, 25)
      n = 5 gives A = 25, ie (25, 60, 65) and (33, 56, 65)
      This explains the limit on the length of the fence being less than 60 metres
      BTW, n = 16 gives (72, 154, 170) and (80, 150, 170)

      Like

  • Unknown's avatar

    Jim Randell 9:17 am on 1 December 2020 Permalink | Reply
    Tags:   

    Teaser 2769: Coming home 

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

    George, Martha and their daughter all drive at their own steady speeds (whole numbers of mph), the daughter’s speed being 10mph more than Martha’s. One day George left home to drive to his daughter’s house at the same time as she left her house to visit her parents: they passed each other at the Crossed Keys pub. Another time Martha left her daughter’s to return home at the same time as her daughter started the reverse journey: they too passed at the Crossed Keys. The distance from George’s to the pub is a two-figure number of miles, and the two digits in reverse order give the distance of the pub from their daughter’s.

    How far is it from George’s home to the Crossed Keys?

    [teaser2769]

     
    • Jim Randell's avatar

      Jim Randell 9:17 am on 1 December 2020 Permalink | Reply

      This Python program considers candidate 2-digit distances from the parent’s house to the pub. It runs in 43ms.

      Run: [ @repl.it ]

      from enigma import irange, nreverse, div, printf
      
      # consider 2 digit distance from parent's house to X
      for p in irange(10, 99):
        # distance to the daughter's house to X is the reverse
        d = nreverse(p)
        if not(d < p): continue
      
        # in the second journey the mother's speed is...
        vm = div(10 * d, p - d)
        if vm is None: continue
        vd = vm + 10
      
        # in the first journey the father's speed is...
        vf = div(p * vd, d)
        if vf is None: continue
      
        printf("p={p} d={d}, vm={vm} vd={vd} vf={vf}")
      

      Solution: It is 54 miles from George’s house to the Crossed Keys.

      So it is 45 miles from the daughter’s house.

      The speeds are: mother = 50 mph, daughter = 60 mph, father = 72 mph.

      Like

  • Unknown's avatar

    Jim Randell 9:27 am on 29 November 2020 Permalink | Reply
    Tags:   

    Teaser 1958: Pent up 

    From The Sunday Times, 26th March 2000 [link]

    The schoolchildren run around in a walled regular pentagonal playground, with sides of 20 metres and with an orange spot painted at its centre. When the whistle blows each child has to run from wherever they are to touch each of the five walls, returning each time to their starting point, and finishing back at the same point.

    Brian is clever but lazy and notices that he can minimize the distance he has to run provided that his starting point is within a certain region. Therefore he has chalked the boundary of this region and he stays within in throughout playtime.

    (a) How many sides does Brian’s region have?
    (b) What is the shortest distance from the orange spot to Brian’s chalk line?

    This puzzle is included in the book Brainteasers (2002). The puzzle text above is taken from the book.

    [teaser1958]

     
    • Jim Randell's avatar

      Jim Randell 9:28 am on 29 November 2020 Permalink | Reply

      I wrote a program to plot points with a path distance that is the same as that of the central point, and you get a plot like this:

      This makes sense, as the shortest distance from a point to the line representing any particular side is a line through the point, perpendicular to the side. So for each side, if we sweep it towards the opposite vertex, we cover a “house shaped” region of the pentagon, that excludes two “wings” on each side. (The regions that overhang the base).

      Sweeping each of the five sides towards the opposite vertex, the intersection of these five “house shaped” regions is the shaded decagon:

      A line from the centre of one of the sides of this decagon, through the orange spot to the centre of the opposite side, is a minimal diameter of the decagon, and we see that this distance is the same as the length of one of the sides of the original pentagon. (It corresponds to the side swept towards the opposite vertex, in the position when it passes through the exact centre of the pentagon).

      So the minimum distance from the centre to the perimeter of the decagon is half this distance.

      Solution: (a) The region has 10 sides; (b) The shortest distance is 10 metres.


      If the playground had been a regular 4-gon (square) or 3-gon (equilateral triangle), then every interior point would correspond to a minimal path.

      For a 6-gon (hexagon) we get a smaller 6-gon inside as the minimal area, and for a 7-gon the area is the shape of a 14-gon.

      In general for a k-gon we get an area in the shape of a smaller k-gon (when k is even) or 2k-gon (when k is odd).

      The areas get smaller and smaller as k increases. In the limit we have a circular playground with a single point at the centre corresponding to the minimal path.

      Like

    • Hugh Casement's avatar

      Hugh Casement 1:23 pm on 29 November 2020 Permalink | Reply

      I think he chalks a line that runs (for example) from the north vertex to a point roughly two thirds of the way down the ESE wall, then to the midpoint of the S wall, to a point roughly a third of the way up the WSW wall, and back to the N vertex. He then stays on that line rather than within it. When the whistles blows he can run right round the line, clockwise or anticlockwise, touching two walls at the N vertex. His total distance is about 81.75 m.

      Like

      • Jim Randell's avatar

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

        @Hugh: Except that after touching each wall you have to return to your starting point before you can set off to touch the next wall.

        Like

        • Hugh Casement's avatar

          Hugh Casement 3:17 pm on 29 November 2020 Permalink | Reply

          Oh, I misread it, thinking he just has to return to the start point at the end.
          Sorry to introduce a red herring.
          Anyway in my version I was wrong that the intermediate points are about a third of the way along the walls from the south: they’re precisely two thirds of the way.

          Like

          • Hugh Casement's avatar

            Hugh Casement 4:50 pm on 29 November 2020 Permalink | Reply

            Oops! Got it wrong again. Precisely one third, six and 2/3 metres.
            I’m really not awake today. Feel free to delete all my posts on this subject.

            Like

    • Hugh Casement's avatar

      Hugh Casement 2:31 pm on 29 November 2020 Permalink | Reply

      Put t = tan(72°) = sqrt{5 + 2 sqrt(5)}.
      Then if the midpoint of the south wall has coordinates (0,0) and the north vertex is at (0, 10t),
      the lower right wall is y = t(x – 10) and the lower left wall is y = t(10 – x).

      Then a bit of calculus — or some trial & error by program — shows that the intermediate points that he touches are at roughly (±12.060113, 6.340375) and the length of his path is about 81.75134 metres. If he starts at a point off the line (on either side) his overall path is longer.

      Of course his chalk line could start at any vertex and go via the midpoint of the opposite side. He could draw five such overlapping quadrilaterals, and stick to any of them, swapping between them at will, so long as when the whistle blows he is not confused as to which line he is on.

      Like

  • Unknown's avatar

    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] [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's avatar

      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's avatar

        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's avatar

      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

  • Unknown's avatar

    Jim Randell 9:10 am on 26 November 2020 Permalink | Reply
    Tags:   

    Teaser 2766: Two by two 

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

    Animals board the ark in pairs.

    EWE and RAM
    HEN and COCK

    In fact these are numbers with letters consistently replacing digits; one pair of the numbers being odd, the other pair being even, and both pairs have the same sum. The three digits of the number ARK are consecutive digits in a muddled order. All this information uniquely determines the number NOAH.

    What is the number NOAH?

    [teaser2766]

     
    • Jim Randell's avatar

      Jim Randell 9:10 am on 26 November 2020 Permalink | Reply

      This puzzle can be solved using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      The following run file executes in 136ms.

      #! python -m enigma -rr
      
      SubstitutedExpression
      
      # one pair is even, the other is odd
      "E % 2 == M % 2"
      "N % 2 == K % 2"
      "E % 2 != N % 2"
      
      # each pair has the same sum
      "EWE + RAM == HEN + COCK"
      
      # A, R, K are consecutive (in some order)
      "max(A, R, K) - min(A, R, K) == 2"
      
      # answer
      --answer="NOAH"
      

      Solution: NOAH = 2074.

      The pairs are:

      (EWE, RAM) = (595, 873)
      (HEN, COCK) = (452, 1016)

      Both pairs sum to 1468.

      And (A, R, K) rearranged gives the consecutive numbers (6, 7, 8).

      Like

    • Frits's avatar

      Frits 10:13 am on 26 November 2020 Permalink | Reply

      Trying not to copy all Jim’s equations.

      from itertools import permutations
      
      c = 1
      digits = set(range(10)).difference({1})
      
      for Q in permutations(digits):
        e,w,r,a,m,h,n,o,k = Q
        # letter combinations don't start with zero
        if 0 in [e, r, h, n, a]: continue
        # pairs EWE, RAM and HEN, COCK are even or odd
        if (e + m) % 2 == 1 : continue
        if (n + k) % 2 == 1 : continue
        # one pair of the numbers being odd, the other pair being even
        if (e + n) % 2 == 0: continue
        #  both pairs have the same sum
        s1 = (e + r) * 100 + (w + a) * 10 + e + m
        s2 = c * 1000 + (h + o) * 100 + (e + c) * 10 + n + k
        if s1 != s2: continue
        # a,r,k are three consecutive digits in a muddled order
        s3 = sum(abs(x - y) for (x, y) in zip([a, r, k, a], [r, k, a]))
        if s3 != 4: continue
        print(f"NOAH = {n}{o}{a}{h}")
      

      Like

    • GeoffR's avatar

      GeoffR 12:24 pm on 26 November 2020 Permalink | Reply

      
      % A Solution in MiniZinc 
      include "globals.mzn";
      
      var 0..9:E; var 0..9:W; var 0..9:R;
      var 0..9:A; var 0..9:M; var 0..9:C;
      var 0..9:O; var 0..9:K; var 0..9:N;
      var 0..9:H;
      
      constraint E > 0 /\ R > 0 /\ H > 0 /\ C > 0 /\ N > 0;
      constraint all_different ([E, W, R, A, M, C, O, K, N, H]);
      
      var 100..999:EWE = 100*E + 10*W + E;
      var 100..999:RAM = 100*R + 10*A + M;
      var 100..999:HEN = 100*H + 10*E + N;
      var 1000..9999:COCK = 1000*C + 100*O + 10*C + K;
      var 1000..9999:NOAH = 1000*N + 100*O +10*A + H;
      
      % One pair of the numbers being odd, the other pair being even
      constraint 
      ((EWE mod 2 == 0 /\ RAM mod 2 == 0) /\ (HEN mod 2 == 1 /\ COCK mod 2 == 1))
      \/ 
      ((EWE mod 2 == 1 /\ RAM mod 2 == 1) /\ (HEN mod 2 == 0 /\ COCK mod 2 == 0));
      
      % Both pairs of numbers have the same sum
      constraint EWE + RAM == HEN + COCK;
      
      % The three digits of the number ARK are consecutive digits in a muddled order
      % Re-using Jim's equation i.e. "max(A, R, K) - min(A, R, K) == 2"
      constraint max([A,R,K]) - min([A,R,K]) == 2;
      
      solve satisfy;
      
      output ["NOAH = " ++ show(NOAH) ++ "\n"
      ++ "EWE = " ++ show(EWE) ++ " , " ++ "RAM == " ++ show(RAM) ++ "\n"
      ++ "HEN = " ++ show(HEN) ++ " , " ++ "COCK = " ++ show(COCK) ];
      
      % NOAH = 2074
      % EWE = 595 , RAM == 873
      % HEN = 452 , COCK = 1016
      % ----------
      % ==========
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 8:38 am on 24 November 2020 Permalink | Reply
    Tags:   

    Teaser 2765: Prime points 

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

    In my fantasy football league each team plays each other once, with three points for a win and one point for a draw. Last season Aberdeen won the league, Brechin finished second, Cowdenbeath third, and so on, in alphabetical order. Remarkably each team finished with a different prime number of points. Dunfermline lost to Forfar.

    In order, what were Elgin’s results against Aberdeen, Brechin, Cowdenbeath, and so on (in the form WWLDL…)?

    [teaser2765]

     
    • Jim Randell's avatar

      Jim Randell 8:38 am on 24 November 2020 Permalink | Reply

      This Python program considers possible numbers of teams (up to a maximum of 26, as each team is named for a letter of the alphabet), and looks for possible sequences of primes that could correspond to the points. Once a candidate sequence is found we try to fill out a table of match outcomes (win, lose, draw) that gives the desired number of points for each team.

      It runs in 49ms.

      Run: [ @repl.it ]

      from enigma import irange, T, Primes, subsets, express, update, join, printf
      
      points = { 'w': 3, 'd': 1 } # points for win, draw
      swap = { 'w': 'l', 'l': 'w', 'd': 'd' } # how a match went for the other team
      
      # complete the table by filling out row i onwards
      def complete(k, table, ps, i=0):
        # are we done?
        if not(i < k):
          yield table
        else:
          # collect: (total, empty squares)
          (t, js) = (ps[i], list())
          for (j, x) in enumerate(table[i]):
            if x == ' ':
              js.append(j)
            else:
              t -= points.get(x, 0)
          # find ways to express t using 3 (= w) and 1 (= d)
          for (d, w) in express(t, (1, 3)):
            # and the remaining games are lost
            l = len(js) - d - w
            if l < 0: continue
            # look for ways to fill out the row
            for row in subsets('w' * w + 'd' * d + 'l' * l, size=len, select="mP"):
              # make an updated table
              t = update(table, [(i, update(table[i], js, row))])
              for (j, x) in zip(js, row):
                t[j] = update(t[j], [(i, swap[x])])
              # and solve for the remaining points
              yield from complete(k, t, ps, i + 1)
      
      # list of primes
      primes = Primes(75)
      
      # consider the number of teams in the league
      for k in irange(6, 26):
      
        # total number of matches
        n = T(k - 1)
      
        # maximum possible number of points
        m = 3 * (k - 1)
      
        # choose a set of k distinct primes for the points
        for ps in subsets(primes.irange(2, m), size=k):
          # calculate the total number of points scored
          t = sum(ps)
          # number of drawn and won/lost matches
          d = 3 * n - t
          w = n - d
          if d < 0 or w < 0 or d > n or w > n: continue 
      
          # make the initial table
          table = list()
          for i in irange(k):
            row = [' '] * k
            row[i] = '-'
            table.append(row)
          # given data (D (= 3) lost to F (= 5))
          for (r, c, v) in [(3, 5, 'l')]:
            table[r][c] = v
            table[c][r] = swap[v]
      
          # complete the table for the list of points
          for t in complete(k, table, ps[::-1]):
            # output the table
            printf("[{k} teams, {n} matches ({d} drawn, {w} won/lost)]")
            ts = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"[:k]
            printf("   {ts}", ts=join(ts, sep=' '))
            for (n, r) in zip(ts, t):
              p = sum(points.get(x, 0) for x in r)
              printf("{n}: {r}  ->  {p:2d} pts", r=join(r, sep=' '))
            printf()
      

      Solution: Elgin’s results were: L L L L W D W.

      The complete table looks like this:

      [8 teams, 28 matches (7 drawn, 21 won/lost)]
         A B C D E F G H
      A: - d w w w w w w  ->  19 pts
      B: d - w d w w w w  ->  17 pts
      C: l l - d w w w w  ->  13 pts
      D: l d d - w l w w  ->  11 pts
      E: l l l l - w d w  ->   7 pts
      F: l l l w l - d d  ->   5 pts
      G: l l l l d d - d  ->   3 pts
      H: l l l l l d d -  ->   2 pts
      

      Like

    • Frits's avatar

      Frits 11:48 am on 25 November 2020 Permalink | Reply

      from itertools import product
      
      P = [2, 3, 5, 7]
      P += [x for x in range(11, 100, 2) if all(x % p for p in P)]
      P += [x for x in range(101, 104, 2) if all(x % p for p in P)]
      
      SCORES = [0, 1, 3]
      LDW = "LD-W"
      LETTERS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
      
      # determine the outcome of 0.5 * n * (n - 1) games
      def solve(n, i, pzl):
        if i < 0:
          yield pzl
       
        # determine number of unknown values
        cnt = sum(pzl[i][j] == -1 for j in range(n))
        
        for p in product(SCORES, repeat=cnt):
          save = list(pzl[i])
      
          x = 0
          for j in range(n):
            if pzl[i][j] == -1:
              pzl[i][j] = p[x]
              pzl[j][i] = (1 if p[x] == 1 else abs(p[x] - 3))
              x += 1
      
          if sum(pzl[i]) == P[n - i - 1]:    # correct total
            yield from solve(n, i - 1, pzl)  # solve next team
          pzl[i] = save                      # backtrack
      
      # generate cumulative sum list of primes
      cumsum = [sum(P[:i+1]) for i in range(len(P))]
      nlist = []
      
      # primes for teams must be minimal (2,3,5 ..) as otherwise the highest prime
      # exceeds the maximum score (n * 3)
      #
      # Dunfermline lost to Forfar so Forfar must have at least 3 points
      # and this can't happen in a league with 6 teams (6th team has 2 points)
      # so n > 6
      
      print("teams  games  draws  points max    high     reject reason")  
      for n in range(7, 27):
        games = int(0.5 * n * (n - 1)) 
        reason = ""
        if (n-1) * 3 - 1 == P[n-1]:
          reason = "high = max - 1"
        if (n-1) * 3 < P[n-1]:
          reason = "high > max"  
        print(f"{n:<6} {games:<6} {games * 3 - cumsum[n-1]:<6} {cumsum[n-1]:<6} "
              f"{(n-1) * 3:<6} {P[n-1]:<6}   {reason}")
        if reason == "":
          nlist.append(n)
       
      # solve and print table 
      for n in nlist:
        # create matrix
        pzl = [[-1 for i in range(n)] for j in range(n)]
        pzl[3][5] = 0      # Dunfermline lost to Forfar
        pzl[5][3] = 3      # Forfor won from Dunfermline
        
        for i in range(n): 
          pzl[i][i] = 0    # don't calculate x against x
       
        # solve which games have been played
        sol = solve(n, n-1, pzl)
        
        # print table
        print(f"\nnumber of teams: {n} \n")
        for s in sol: 
          print("   " + "  ".join(list(LETTERS[:n])))   # column header
          for i in range(len(s)):
            r = " " + "  ".join(str(x) if k != i else "-" 
                                for k, x in enumerate(s[i]))
            print(LETTERS[:n][i], r)   # row qualifier
          
          print("\nElgin's results:", 
                " ".join([LDW[x] for k, x in enumerate(s[4]) if k != 4]))  
         
      # teams  games  draws  points max    high     reject reason
      # 7      21     5      58     18     17       high = max - 1
      # 8      28     7      77     21     19
      # 9      36     8      100    24     23       high = max - 1
      # 10     45     6      129    27     29       high > max
      # 11     55     5      160    30     31       high > max
      # 12     66     1      197    33     37       high > max
      # 13     78     -4     238    36     41       high > max
      # 14     91     -8     281    39     43       high > max
      # 15     105    -13    328    42     47       high > max
      # 16     120    -21    381    45     53       high > max
      # 17     136    -32    440    48     59       high > max
      # 18     153    -42    501    51     61       high > max
      # 19     171    -55    568    54     67       high > max
      # 20     190    -69    639    57     71       high > max
      # 21     210    -82    712    60     73       high > max
      # 22     231    -98    791    63     79       high > max
      # 23     253    -115   874    66     83       high > max
      # 24     276    -135   963    69     89       high > max
      # 25     300    -160   1060   72     97       high > max
      # 26     325    -186   1161   75     101      high > max
      #
      # number of teams: 8
      #
      #    A  B  C  D  E  F  G  H
      # A  -  1  3  3  3  3  3  3
      # B  1  -  3  1  3  3  3  3
      # C  0  0  -  1  3  3  3  3
      # D  0  1  1  -  3  0  3  3
      # E  0  0  0  0  -  3  1  3
      # F  0  0  0  3  0  -  1  1
      # G  0  0  0  0  1  1  -  1
      # H  0  0  0  0  0  1  1  -
      # 
      # Elgin's results: L L L L W D W
      

      Like

  • Unknown's avatar

    Jim Randell 9:08 am on 22 November 2020 Permalink | Reply
    Tags:   

    Teaser 1948: Square ladder 

    From The Sunday Times, 16th January 2000 [link]


    Your task is to place a non-zero digit in each box so that:

    • the number formed by reading across each row is a perfect square, with the one in the top row being odd;
    • if a digit is used in a row, then it is also used in the next row up;
    • only on one occasion does the same digit occur in two boxes with an edge in common.

    Fill in the grid.

    This puzzle is included in the book Brainteasers (2002). The puzzle text above is taken from the book.

    [teaser1948]

     
    • Jim Randell's avatar

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

      This Python 3 program constructs “ladders” such that the digits used in each row are a superset of the digits used in the smaller row below.

      We then check the ladders produced to find ones that satisfy the remaining conditions.

      It runs in 47ms.

      from enigma import (irange, group, grid_adjacency, join, printf)
      
      # collect 1-5 digit squares
      squares = group((str(i * i) for i in irange(0, 316)), by=len, st=(lambda s: '0' not in s))
      
      # construct a ladder of squares
      def ladder(k, ss):
        n = len(ss)
        # are we done?
        if n == k:
          yield ss
        else:
          # add an (n+1)-digit square whose digits are a superset of the previous square
          ps = set(ss[-1])
          for s in squares[n + 1]:
            if ps.issubset(s):
              yield from ladder(k, ss + [s])
      
      # adjacency matrix for 5x5 grid
      adj = grid_adjacency(5, 5)
      
      # choose a starting 1 digit square
      for s in squares[1]:
        for ss in ladder(5, [s]):
          # the final square is odd
          if ss[-1][-1] not in '13579': continue
      
          # form the digits into a square array (linearly indexed)
          g = join(s.ljust(5) for s in ss)
      
          # count the number of edges between 2 identical digits
          n = sum(any(i < j and d == g[j] for j in adj[i]) for (i, d) in enumerate(g) if d != ' ')
          if n != 1: continue
      
          # output solution
          for s in ss[::-1]:
            printf("{s}", s=join(s, sep=" "))
          printf()
      

      Solution: The completed grid is:

      The squares are: (95481, 5184, 841, 81, 1) = (309, 72, 29, 9, 1)².

      Like

    • Frits's avatar

      Frits 3:49 pm on 22 November 2020 Permalink | Reply

      I didn’t use recursion as depth is limited.

      from itertools import permutations as perm
      from enigma import is_square
      
      to_num = lambda li: int("".join(li))
      
      # check if new value is correct
      def check(n, new, old):
        # as 5th row must be a square
        if not any(j in new for j in ('1', '4', '9')): 
          return False
        # check how many digits are same in same position 
        same[n] = sum(a == b for (a, b) in zip(tuple(old), new))
        if sum(same[:n+1]) > 1: 
          return False
        # new must be a square number
        if not is_square(to_num(new)): 
          return False   
        return True
       
      # generate 5 digit squares
      s5 = [i2 for i in range(101, 317) if '0' not in (i2 := str(i * i)) and 
                                           i2[-1] in ('1', '3', '5', '7', '9') and
                                           any(j in i2 for j in ('1', '4', '9'))] 
                 
      same = [0] * 4 
      for p5 in s5: 
        for p4 in perm(p5, 4):
          if not check(0, p4, p5): continue
          for p3 in perm(p4, 3):
            if not check(1, p3, p4): continue
            for p2 in perm(p3, 2):
              if not check(2, p2, p3): continue
              for p1 in perm(p2, 1):
                if not check(3, p1, p2): continue
                if sum(same) != 1: continue
                print(f"{p5}\n{to_num(p4)}\n{to_num(p3)}\n"
                      f"{to_num(p2)}\n{to_num(p1)}")
                
      # 95481
      # 5184
      # 841
      # 81
      # 1
      

      Like

      • Jim Randell's avatar

        Jim Randell 4:33 pm on 22 November 2020 Permalink | Reply

        I used a more literal interpretation of: “if a digit is used in a row, then it is also used in the next row up”.

        Which would allow (for example), 4761 to appear above 144.

        Like

        • Frits's avatar

          Frits 4:46 pm on 22 November 2020 Permalink | Reply

          You are right.

          from enigma import SubstitutedExpression, is_square
          
          # ABCDE
          # FGHI
          # JKL
          # MN
          # O
          
          # the alphametic puzzle
          p = SubstitutedExpression(
            [
            "is_square(ABCDE)",
            "is_square(FGHI)",
            "is_square(JKL)",
            "is_square(MN)",
            "is_square(O)",
            
            # connect 2 rows
            "all(j in str(ABCDE) for j in str(FGHI))",
            "all(j in str(FGHI) for j in str(JKL))",
            "all(j in str(JKL) for j in str(MN))",
            "str(O) in str(MN)",
            
            # check how many digits are equal in same position
            "sum([A==F, B==G, C==H, D==I, F==J, G==K, H==L, J==M, K==N, M==O]) == 1",
            ],
            answer="ABCDE, FGHI, JKL, MN, O",
            digits=range(1, 10),
            # top row is odd
            d2i=dict([(k, "E") for k in {2, 4, 6, 8}]),
            distinct="",
            verbose=0)   
          
          # Print answers 
          for (_, ans) in p.solve():
            print(f"{ans}")
          
          # (95481, 5184, 841, 81, 1)
          

          Like

    • GeoffR's avatar

      GeoffR 12:07 pm on 10 December 2020 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      %  Grid
      %  a b c d e
      %  f g h i
      %  j k l
      %  m n
      %  p
      
      var 0..9: a; var 0..9: b; var 0..9: c; var 0..9: d;
      var 0..9: e; var 0..9: f; var 0..9: g; var 0..9: h; 
      var 0..9: i; var 0..9: j; var 0..9: k; var 0..9: l; 
      var 0..9: m; var 0..9: n; var 0..9: p; 
      
      constraint a > 0 /\ f > 0 /\ j > 0 /\ m > 0 /\ p > 0;
      
      var 10..99:mn = 10*m + n;
      var 100..999:jkl = 100*j + 10*k + l;
      var 1000..9999:fghi = 1000*f + 100*g + 10*h + i;
      var 10000..99999: abcde = 10000*a + 1000*b + 100*c + 10*d + e;
      
      % sets of 2,3,4 and 5-digit squares
      set of int: sq2 = {n*n | n in 4..9};
      set of int: sq3 = {n*n | n in 10..31};  
      set of int: sq4 = {n*n | n in 32..99};  
      set of int: sq5 = {n*n | n in 100..316};
              
      % form five rows of required squares
      constraint p == 1 \/ p == 4 \/ p == 9;
      constraint mn in sq2 /\ jkl in sq3 /\ fghi in sq4;
      % square in the top row is odd
      constraint abcde in sq5 /\ abcde mod 2 == 1;
      
      % if a digit is used in a row, then it is also used
      % in the next row up - starting at bottom of ladder 
      constraint {p} subset {m, n};
      constraint {m, n} subset {j, k, l};
      constraint {j, k, l} subset {f, g, h, i};
      constraint {f, g, h, i} subset {a, b, c, d, e};
      
      % assume same digit occurs in two adjacent vertical boxes only
      constraint (sum ([a - f == 0, b - g == 0, c - h == 0, 
      d - i == 0, f - j == 0, g - k == 0, h - l == 0, 
      j - m == 0, k - n == 0, m - p == 0]) == 1)
      /\ % and check same digit does not occur in any two horizontal boxes
      (sum ([a - b == 0, b - c == 0, c - d == 0, d - e == 0,
      f - g == 0, g - h == 0, h - i == 0,
      j - k == 0, k - l == 0, m - n == 0]) == 0); 
      
      solve satisfy;
      
      output ["Grid: " ++ "\n" ++  show(abcde) ++ "\n" ++ show(fghi) ++ "\n" 
      ++ show(jkl) ++ "\n" ++ show(mn) ++ "\n" ++ show(p) ];
      % Grid: 
      % 95481
      % 5184
      % 841
      % 81
      % 1
      % time elapsed: 0.04 s
      % ----------
      % ==========
      % Finished in 477msec
      
      
      

      Like

  • Unknown's avatar

    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] [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's avatar

      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's avatar

        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

  • Unknown's avatar

    Jim Randell 9:59 am on 19 November 2020 Permalink | Reply
    Tags:   

    Teaser 2764: Three little lists 

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

    I have chosen five different numbers, each less than 20, and I have listed these numbers in three ways. In the first list the numbers are in increasing numerical order. In the second list the numbers are written in words and are in alphabetical order. In the third list they are again in words and as you work down the list each word uses more letters than its predecessor. Each number is in a different position in each of the lists.

    What are my five numbers?

    [teaser2764]

     
    • Jim Randell's avatar

      Jim Randell 9:59 am on 19 November 2020 Permalink | Reply

      This Python program runs in 68ms.

      Run: [ @repl.it ]

      from enigma import irange, subsets, int2words, join, printf
      
      # the numbers (in numerical order)
      nums = list(irange(1, 19))
      
      # map numbers to words
      word = dict((n, int2words(n)) for n in nums)
      
      # map number to word length
      length = dict((n, len(word[n])) for n in nums)
      
      # choose 5 numbers for the first list
      for s1 in subsets(nums, size=5):
      
        # make the third list by ordering the numbers by word length
        k3 = lambda n: length[n]
        # check all word lengths are distinct
        if len(set(k3(n) for n in s1)) < 5: continue
        s3 = sorted(s1, key=k3)
      
        # make the second list by ordering the numbers alphabetically
        k2 = lambda n: word[n]
        s2 = sorted(s1, key=k2)
      
        # no number is the same place in 2 or more lists
        if any(len(set(x)) < 3 for x in zip(s1, s2, s3)): continue
      
        # output solution (lists 2 and 3 formatted as words)
        fmt = lambda ns: join((word[n] for n in ns), sep=", ", enc="()")
        printf("1: {s1}")
        printf("2: {s2}", s2=fmt(s2))
        printf("3: {s3}", s3=fmt(s3))
        printf()
      

      Solution: The 5 numbers are: 3, 6, 9, 17, 19.

      Like

  • Unknown's avatar

    Jim Randell 10:27 am on 17 November 2020 Permalink | Reply
    Tags:   

    Brain-Teaser 13: [Fill out the grid] 

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

    The numbers 1 to 9, in any order and using each once only, are to be placed one at a time in the nine squares A to J. As each number replaces a letter in a square, any numbers standing at that moment in adjacent squares (left, right, up or down, but not diagonally) are to be multiplied by three.

    Thus, if we decided to begin with 4 in A, then 9 in E, 7 in B and 2 in D, etc., we should have:

    and so on. On completion, the nine final numbers are added together to find the score.

    There are obviously 81 ways of making the first move, and there are 131,681,894,400 ways of completing the array; yet the number of possible scores in quite small.

    What is the smallest possible score?

    This puzzle was originally published with no title.

    [teaser13]

     
    • Jim Randell's avatar

      Jim Randell 10:28 am on 17 November 2020 Permalink | Reply

      We can drastically reduce the number of possibilities we have consider:

      When the game is played the squares are filled out in a particular order. If, when we play the game, instead of filling in numbers we just note how many times the value in each particular square is trebled, then at the end we can find the minimum score for that particular ordering of squares by assigning 9 to the square that is trebled the fewest number of times (i.e. the final square filled out), 8 to the next lowest number of treblings, and so on until 1 is assigned to the square with the largest number of treblings.

      This Python program considers all possible orderings for filling out the squares. It runs in 420ms.

      Run: [ @repl.it ]

      from enigma import grid_adjacency, subsets, irange, printf
      
      # numbers to fill out
      nums = list(irange(1, 9))
      
      # grid adjacency matrix
      adj = grid_adjacency(3, 3)
      
      # multipliers (for number of treblings)
      mul = [1, 3, 9, 27, 81]
      
      # find the minimal score for a ordering of squares
      def play(js):
        # initial grid
        grid = [None] * 9
        # place the numbers
        for j in js:
          # place the number
          grid[j] = 0
          # and increase adjacent counts
          for i in adj[j]:
            if grid[i] is not None:
              grid[i] += 1
        # determine the minimum score
        return sum(n * mul[k] for (n, k) in zip(nums, sorted(grid, reverse=1)))
      
      # choose an ordering for the squares, and find the minimum score
      r = min(play(js) for js in subsets(irange(9), size=len, select="P"))
      printf("min score = {r}")
      

      Solution: The smallest possible score is 171.

      One way of getting this total is:

      [ A, B, C ] [ D, E, F ] [ G, H, J ]
      [ 2, B, C ] [ D, E, F ] [ G, H, J ]
      [ 6, 3, C ] [ D, E, F, ] [ G, H, J ]
      [ 6, 9, 4 ] [ D, E, F ] [ G, H, J ]
      [ 6, 27, 4 ] [ D, 1, F ] [ G, H, J ]
      [ 18, 27, 4, ] [ 5, 3, F ] [ G, H, J ]
      [ 18, 27, 12 ] [ 5, 9, 6 ] [ G, H, J ]
      [ 18, 27, 12 ] [ 15, 9, 6 ] [ 7, H, J ]
      [ 18, 27, 12 ] [ 15, 27, 6 ] [ 21, 8, J ]
      [ 18, 27, 12 ] [ 15, 27, 18 ] [ 21, 24, 9 ] = 171

      We can make the program run faster by exploiting the symmetry of the grid. For example, for the first move, we only need to consider one corner square, one edge square and the central square. It does make the program longer though.

      Like

    • Frits's avatar

      Frits 11:02 am on 19 November 2020 Permalink | Reply

      The first part finds the minimum score for different kind of treblings under the condition that they add up to 12. It turns out this minimum can also be achieved by our number placing rules.

      I didn’t immediately see how I could check if a list [A,B,C,D,E,F,G,H,J] from the result can be achieved so I reused Jim’s code to find the first permutation which has a score equal to this minimum.

      from enigma import SubstitutedExpression, grid_adjacency, subsets
      
      # numbers to fill out
      nums = list(range(1, 10))
      
      # grid adjacency matrix
      adj = grid_adjacency(3, 3)
      
      # multipliers (for number of treblings)
      mul = [1, 3, 9, 27, 81]
      
      score = lambda li: sum(n * mul[k] 
                         for (n, k) in zip(nums, sorted(li, reverse=1)))
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
        # if field x has adjacent fields x1...xn and k of them have already been set
        #
        # then k fields will now get trebled which previously didn't treble field x
        # and (n - k) fields will not get trebled now but later on will treble 
        # field x (n - k) times. So for every trebling there is an instance of 
        # non-trebling.
        #
        # adjacent field matrix;
        #
        #  2  3  2    sum of all elements is 24  
        #  3  4  3    half of them will not get trebled
        #  2  3  2
        "sum([A,B,C,D,E,F,G,H,J]) == 12", 
        ],
        answer="score([A,B,C,D,E,F,G,H,J]), A,B,C,D,E,F,G,H,J",
        digits=range(0, 5),
        env=dict(score=score),
        accumulate=min,  
        d2i={3 : "ACGJ", 4: "ACGJBDFH"},
        distinct="",
        verbose=0)   
        
      # solve the puzzle
      r = p.run()
      min = list(r.accumulate)[0]
      
      lst = []
      prt = ["A", "B", "C", "D", "E", "F", "G", "H", "J"]
      
      # check if this minimum can be achieved
      for js in subsets(range(9), size=len, select="P"):
        grid = [None] * 9
        # place the numbers
        for j in js:
          # place the number
          grid[j] = 0
          # and increase adjacent counts
          for i in adj[j]:
            if grid[i] is not None:
              grid[i] += 1
              
        if score(grid) == min:
          print("smallest possible score:", min, "\n\nexample:\n")
         
          # sort grid (descending)
          lst = sorted(grid, reverse=True)
         
          # print all the steps
          for i in range(9):  
            for k, j in enumerate(js):
              if j != i: continue
              g = grid[k]
              ind = lst.index(g) 
              lst[ind] = -1          # set to "processed"
              prt[k] = ind + 1       # set field
              
              # treble adjacent fields
              for m in adj[k]:
                if type(prt[m]) == int:
                  prt[m] *= 3
                
              print(f"{prt[:3]} {prt[3:6]} {prt[6:]}")
          break  # we only print one example
          
      # smallest possible score: 171
      #
      # example:
      #
      # [2, 'B', 'C'] ['D', 'E', 'F'] ['G', 'H', 'J']
      # [6, 3, 'C'] ['D', 'E', 'F'] ['G', 'H', 'J']
      # [6, 9, 4] ['D', 'E', 'F'] ['G', 'H', 'J']
      # [6, 27, 4] ['D', 1, 'F'] ['G', 'H', 'J']
      # [18, 27, 4] [5, 3, 'F'] ['G', 'H', 'J']
      # [18, 27, 12] [5, 9, 6] ['G', 'H', 'J']
      # [18, 27, 12] [15, 9, 6] [7, 'H', 'J']
      # [18, 27, 12] [15, 27, 6] [21, 8, 'J']
      # [18, 27, 12] [15, 27, 18] [21, 24, 9]    
      

      Like

  • Unknown's avatar

    Jim Randell 9:26 am on 15 November 2020 Permalink | Reply
    Tags:   

    Teaser 1946: Not the millennium bug 

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

    Do you remember all that fuss over the “Millennium bug”?

    On that New Year’s Day I typed a Teaser on my word processor. When I typed in 2000 it actually displayed and printed 1900. This is because whenever I type a whole number in figures the machine actually displays and prints only a percentage of it, choosing a random different whole number percentage each time.

    The first example was bad enough but the worrying this is that is has chosen even lower percentages since then, upsetting everything that I prepare with numbers in it. Luckily the percentage reductions have not cut any number by half or more yet.

    What percentage did the machine print on New Year’s Day?

    This puzzle is included in the book Brainteasers (2002). The puzzle text above is taken from the book.

    [teaser1946]

     
    • Jim Randell's avatar

      Jim Randell 9:26 am on 15 November 2020 Permalink | Reply

      See also: Enigma 1419.

      We assume that both the original puzzle (prepared on 2000-01-01), and the puzzle text presented above were created using the faulty program.

      So, on 2000-01-01 the setter typed a whole number, X, which was replaced by the value aX, where a is some whole number percentage less than 100% and greater than 50%.

      In relating the story for this puzzle, the setter has typed the values X and aX, and these have been replaced by values multiplied by b and c respectively, where b and c are different whole number percentages, less than a and greater than 50%.

      So, we have:

      bX = 2000
      c.aX = 1900

      This Python program runs in 44ms.

      Run: [ @replit ]

      from enigma import (irange, div, printf)
      
      # choose a percentage for b
      for b in irange(51, 98):
        X = div(2000 * 100, b)
        if X is None: continue
      
        # a > b
        for a in irange(b + 1, 99):
          aX = div(a * X, 100)
          if aX is None: continue
          c = div(1900 * 100, aX)
          if c is None or c == b or not (a > c > 50): continue
      
          # output solution
          printf("a={a} b={b} c={c} -> X={X} aX={aX}")
      

      Solution: On 2000-01-01 the machine used a value of 80%.

      So the setter was attempting to enter 3125, but instead the program printed 80% of this = 2500.

      In relating the story, the setter typed: “When I typed in 3125 it actually printed 2500”, but these values were replaced using percentages of 64% and 76%, to appear as: “When I typed in 2000 it actually printed 1900”, as in the puzzle text.

      Like

  • Unknown's avatar

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

    Teaser 3034: Reservoir development 

    From The Sunday Times, 15th November 2020 [link] [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's avatar

      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.

      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's avatar

        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's avatar

      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's avatar

        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's avatar

      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's avatar

      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

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
Design a site like this with WordPress.com
Get started