Updates from Jim Randell Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 9:19 am on 27 September 2024 Permalink | Reply
    Tags:   

    Teaser 2606: Cue for a queue 

    From The Sunday Times, 2nd September 2012 [link] [link]

    Alan, Brian, Colin, Dave and Ed have surnames Smith, Jones, Rogers, Mason and Hall, but not in that order. They form themselves into a queue. Brian is somewhere ahead of Mr Smith who is somewhere ahead of Ed. Similarly, Mr Jones is ahead of Colin who is ahead of Dave who is ahead of Mr Hall. Mr Mason’s two neighbours in the queue are Alan and Mr Rogers.

    If I told you Alan’s surname it would now be possible to work our all their surnames and their positions in the queue.

    What is Alan’s surname and what is his position in the queue?

    [teaser2606]

     
    • Jim Randell's avatar

      Jim Randell 9:20 am on 27 September 2024 Permalink | Reply

      I used the [[ SubstitutedExpression ]] solver from the enigma.py library to assign positions 1-5 in the queue to the forenames and surnames, such that the required conditions are met.

      We can then use the [[ filter_unique() ]] function to select solutions from the viable assignments, such that knowing Alan’s surname gives a single solution for all names.

      The following Python program runs in 89ms. (Internal runtime is 5.8ms).

      from enigma import (SubstitutedExpression, trim, filter_unique, update, peek, join, printf)
      
      # generate possible queues
      def queues():
        # allocate positions 1-5 in the queue to:
        #
        #  Alan = A; Brian = B; Colin = C; Dave = D; Ed = E
        #  Smith = S; Jones = J; Rogers = R; Mason = M; Hall = H
        #
        p = SubstitutedExpression(
          [
            # the surnames are not given in the correct order
            "A != S or B != J or C != R or D != M or E != H",
            # B is ahead of S, who is ahead of E
            "B < S", "S < E",
            # J is ahead of C, who is ahead of D, who is ahead of H
            "J < C", "C < D", "D < H",
            # M's neighbours (on different sides) are A and R
            "abs(A - R) = 2", "abs(A - M) = 1", "abs(R - M) = 1",
          ],
          base=6,
          digits=[1, 2, 3, 4, 5],
          distinct=["ABCDE", "SJRMH"],
        )
      
        # solve the puzzle
        for s in p.solve(verbose=0):
          # assemble the queue
          q = ["??"] * 6
          for k in "ABCDE": q[s[k]] = update(q[s[k]], [0], k)
          for k in "SJRMH": q[s[k]] = update(q[s[k]], [1], k)
          # return the queue
          yield trim(q, head=1)
      
      # knowing A's surname gives a unique solution
      f = (lambda q: peek(x for x in q if x[0] == 'A'))
      for q in filter_unique(queues(), f).unique:
        printf("{q}", q=join(q, sep=" "))
      

      Solution: Alan Smith is second in the queue.

      The queue is as follows:

      1st = Brian Jones
      2nd = Alan Smith
      3rd = Colin Mason
      4th = Dave Rogers
      5th = Ed Hall

      There are 5 candidate solutions:

      BJ, AS, CM, DR, EH
      BJ, CS, ER, DM, AH
      BJ, CS, DR, EM, AH
      AJ, BM, CR, DS, EH
      AJ, CM, BR, DS, EH

      The first of these is unique for AS. The next two both have AH, and the final two have AJ.

      Like

      • ruudvanderham's avatar

        ruudvanderham 5:39 pm on 27 September 2024 Permalink | Reply

        import itertools
        
        for firstnames, lastnames in zip(itertools.repeat("Alan Brian Colin Dave Ed".split()), itertools.permutations("Smith Jones Rogers Mason Hall".split(), r=5)):
            for positions in itertools.permutations(range(1, 6)):
                position = {firstname: position for firstname, position in zip(firstnames, positions)}
                position.update({lastname: position for lastname, position in zip(lastnames, positions)})
                if position["Brian"] < position["Smith"] < position["Ed"]:
                    if position["Jones"] < position["Colin"] < position["Dave"] < position["Hall"]:
                        if {position["Mason"] - position["Alan"], position["Mason"] - position["Rogers"]} == {-1, 1}:
                            if list(lastnames) != "Smith Jones Rogers Mason Hall".split():
                                for firstname, lastname in zip(firstnames, lastnames):
                                    print(f"{firstname+ " "+lastname:12} {position[firstname]}  ", end="")
                                print()
        

        This prints:

        Alan Smith   2  Brian Jones  1  Colin Mason  3  Dave Rogers  4  Ed Hall      5  
        Alan Jones   1  Brian Rogers 3  Colin Mason  2  Dave Smith   4  Ed Hall      5
        Alan Jones   1  Brian Mason  2  Colin Rogers 3  Dave Smith   4  Ed Hall      5
        Alan Hall    5  Brian Jones  1  Colin Smith  2  Dave Rogers  3  Ed Mason     4  
        Alan Hall    5  Brian Jones  1  Colin Smith  2  Dave Mason   4  Ed Rogers    3
        

        So, it has to be Alan Smith (the others are not unique) and he is in second position.

        Like

  • Unknown's avatar

    Jim Randell 10:03 am on 24 September 2024 Permalink | Reply
    Tags:   

    Brain-Teaser 231: Holidays abroad 

    From The Sunday Times, 26th September 1965 [link]

    My old friends Alf, Bert, Charlie, Duggie and Ernie went with their wives for holidays abroad last year, to Andorra, Boulogne, Calais, Dunkirk and Ethiopia. I knew that the names of the five wives were Agnes, Beatrice, Clarissa, Daphne and Ethel, but the only information I had about who was married to whom was that for each pair the names of the husband, the wife and last year’s holiday destination all began with different letters.

    In conversation with the ladies, Beatrice told me that she was not married to Alf, and that she had heard from Ernie that Charlie went to Dunkirk last year.

    Daphne, however, firmly informed me that Charlie went to Ethiopia and that Beatrice went to Dunkirk. “Unlike some people I could mention”, she added darkly, “Alf always tells the truth”.

    Clarissa said that when her husband was asked whether Ethel was married to Charlie, he replied: “No”. She went on to tell me that Duggie went to Boulogne.

    Of each of these married couples one member always told the truth and the other never did.

    Name each man’s wife and holiday resort.

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

    [teaser231]

     
    • Jim Randell's avatar

      Jim Randell 10:03 am on 24 September 2024 Permalink | Reply

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

      I assigned 5 slots (1 – 5), each of which contains one wife, husband, destination and trait (for the wife).

      The following run file fills out the slots. It runs in 77ms. (Internal runtime of the generated code is 631µs).

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      # let A = 1, B = 2, C = 3, D = 4, E = 5
      #
      #  slot       : 1 2 3 4 5
      #  wife       : A B C D E
      #  husband    : F G H I J  {Alf, Bert, Charlie, Duggie, Ernie}
      #  destination: K L M N P  {Andorra, Boulogne, Calais, Dunkirk, Ethiopia}
      #  wife trait : V W X Y Z  {0 = false or 1 = true}
      --base=6
      --distinct="FGHIJ,KLMNP,FK,GL,HM,IN,JP"
      --invalid="0,FGHIJKLMNP"
      --invalid="2|3|4|5,VWXYZ"
      --invalid="1,FK"
      --invalid="2,GL"
      --invalid="3,HM"
      --invalid="4,IN"
      --invalid="5,JP"
      
      --macro="@hs = (F, G, H, I, J)"  # husbands
      --macro="@ds = (K, L, M, N, P)"  # destinations
      --macro="@ts = (V, W, X, Y, Z)"  # traits
      
      # find a slot with value v
      --code="slot = lambda vs, v: vs.index(v)"
      
      # check statements truth value "x" says "y"
      --code="check = lambda x, y: bool(x) == bool(y)"
      
      # Beatrice says (Beatrice is not married to Alf)
      "check(W, G != 1)"
      
      # Beatrice says (Ernie says Charlie went to Dunkirk)
      "check(W, check(@ts[slot(@hs, 5)] ^ 1, @ds[slot(@hs, 3)] == 4))"
      
      # Daphne says (Charlie went to Ethiopia)
      "check(Y, @ds[slot(@hs, 3)] == 5)"
      
      # Daphne says (Beatrice went to Dunkirk)
      "check(Y, L == 4)"
      
      # Daphne says (Alf tells the truth)
      "check(Y, @ts[slot(@hs, 1)] == 0)"
      
      # Clarissa says (her husband says (Ethel is not married to Charlie))
      "check(X, check(X ^ 1, J != 3))"
      
      # Clarissa says (Duggie went to Boulogne)
      "check(X, @ds[slot(@hs, 4)] == 2)"
      
      --template="(F G H I J) (K L M N P) (V W X Y Z)"
      --solution=""
      

      And this following Python program formats the output using the appropriate labels:

      from enigma import (SubstitutedExpression, printf)
      
      p = SubstitutedExpression.from_file("teaser231.run",
        # return (<husbands>, <destinations>, <traits>)
        ["--answer=(@hs, @ds, @ts)"],
      )
      
      make_map = lambda vs: dict(enumerate(vs.split(), start=1))
      husbands = make_map("Alf Bert Charlie Duggie Ernie")
      wives = make_map("Agnes Beatrix Clarissa Daphne Ethel")
      destinations = make_map("Andorra Boulogne Calais Dunkirk Ethiopia")
      traits = { 0: 'False', 1: 'True' }
      
      for ans in p.answers(verbose=0):
        # collect the slots [wife, husband, destination, trait]
        d = dict((k, [v]) for (k, v) in wives.items())
        for (vs, labels) in zip(ans, [husbands, destinations, traits]):
          for (k, v) in enumerate(vs, start=1):
            d[k].append(labels[v])
        # output the slots
        for k in sorted(d.keys(), key=(lambda k: d[k][1])):
          (W, H, D, T) = d[k]
          printf("{H} and {W} ({T}) -> {D}")
        printf()
      

      Solution: Alf and Clarissa → Dunkirk; Bert and Daphne → Ethiopia; Charlie and Ethel → Andorra; Duggie and Agnes → Boulogne; Ernie and Beatrix → Calais

      We know:

      Alf and Clarissa → Dunkirk; (Alf = F; Clarissa = T)
      Bert and Daphne → Ethiopia; (Bert = T, Daphne = F)
      Charlie and Ethel → Andorra
      Duggie and Agnes → Boulogne
      Ernie and Beatrix → Calais (Ernie = F, Beatrix = T)

      We cannot determine the traits for Charlie and Ethel or for Duggie and Agnes.

      Like

      • Frits's avatar

        Frits 11:02 am on 24 September 2024 Permalink | Reply

        @Jim,

        I have a different naming convention for storing Python programs.
        One idea might be to use something like (assuming the filename doesn’t contain periods):

        import os
        
        runfile = os.path.basename(__file__).split(".")[0] + ".run"
        p = SubstitutedExpression.from_file(runfile, [
          # return (<husbands>, <destinations>, <traits>)
          "--answer=(@hs, @ds, @ts)",
        ])
        

        Like

        • Jim Randell's avatar

          Jim Randell 3:28 pm on 26 September 2024 Permalink | Reply

          I’ve added a [[ parsepath() ]] function to enigma.py that can be used to extract the following components of a path:

          {path} = the full path name = "{dir}/{file}"
          {stem} = path without extension = "{dir}/{name}"
          {dir}  = directory containing the file
          {file} = the filename = "{name}{ext}"
          {name} = the filename without extension
          {ext}  = the extension
          

          For example:

          {path} = "/users/jim/puzzles/enigma/enigma123.py"
          {stem} = "/users/jim/puzzles/enigma/enigma123"
          {dir}  = "/users/jim/puzzles/enigma"
          {file} = "enigma123.py"
          {name} = "enigma123"
          {ext}  = ".py"
          

          You can then call this to make a new path name from an existing one.

          For example to make a path in the same directory:

          path = parsepath("{dir}/enigma123.run", __file__)
          

          Or to just replace the extension:

          path = parsepath("{dir}/{name}.run", __file__)
          
          path = parsepath("{stem}.run", __file__)
          

          As an added bonus [[ SubstitutedExpression.from_file() ]] will automatically pass the arguments to [[ parsepath() ]] if a non-string is provided as a path, to save you the bother:

          p = SubstitutedExpression.from_file(["{stem}.run", __file__])
          

          Like

  • Unknown's avatar

    Jim Randell 2:00 am on 22 September 2024 Permalink | Reply
    Tags:   

    Teaser 3235: Dromedary lines 

    From The Sunday Times, 22nd September 2024 [link] [link]

    Zayed must cross the Setare desert to move to his summer camp, which lies 240 miles east, and a smaller whole number of miles north of his winter camp. Both camps are on a grid of wells every 5 miles north and east across the desert.

    His camels can only travel 100 miles before needing to stop for water. Being superstitious, he will only travel a whole number of miles, in a straight line, between wells. Subject to this, he attempts to minimise his journey by travelling to the well, in range, closest to the remaining straight-line route. If more than one well is equally close, he stops at the nearest one.

    During his journey he travels a total of 50 miles due east and 5 miles due north and visits 14 wells between his camps (not including the ones at the camps).

    List in order the length of each of the first five stages.

    [teaser3235]

     
    • Jim Randell's avatar

      Jim Randell 2:37 am on 22 September 2024 Permalink | Reply

      This Python program runs in 676ms. (Internal runtime is 570ms).

      from enigma import (
        Accumulator, irange, cproduct, line_distance,
        ihypot, unpack, call, tuples, printf
      )
      
      # calculate the next step of the journey; return ((x, y), dist)
      def step(x0, y0, x1, y1):
        # find the nearest wells to the line joining (x0, y0) to (x1, y1)
        r = Accumulator(fn=min, collect=1)
        for (x, y) in cproduct([irange(x0, x1, step=5), irange(y0, y1, step=5)]):
          # distance travelled should be an integer, less than 100
          d = ihypot(x - x0, y - y0)
          if (not d) or d > 100: continue
          r.accumulate_data(line_distance((x0, y0), (x1, y1), (x, y)), ((x, y), d))
        # find the minimum distance travelled
        return min(r.data, key=unpack(lambda pt, d: d))
      
      # calculate a journey to from p0 to p1; return (points, dists)
      def journey(p1, p0=(0, 0)):
        (pts, ds) = ([p0], [])
        while p0 != p1:
          (p0, d) = call(step, p0 + p1)
          pts.append(p0)
          ds.append(d)
        return (pts, ds)
      
      # consider possible distance north between camps
      for n in irange(5, 235, step=5):
        # look for a journey with 14 intermediate points
        (pts, ds) = journey((240, n))
        if len(pts) != 16: continue
        # accumulate due E and due N distances
        E = N = 0
        for ((x0, y0), (x1, y1)) in tuples(pts, 2):
          if y0 == y1: E += x1 - x0
          if x0 == x1: N += y1 - y0
        if not (E == 50 and N == 5): continue
        # output solution
        printf("n={n}: E={E} N={N} {pts}")
        printf("-> {ds}")
      

      Solution: The distances travelled in the first 5 stages of the journey are: 5, 5, 5, 85, 5 (miles).

      The summer camp is 115 miles north and 240 miles east of the winter camp.

      The full list of distances is:

      5, 5, 5, 85, 5, 85, 5, 5, 5, 25, 5, 25, 5, 5, 5 (miles)
      or:
      1, 1, 1, 17, 1, 17, 1, 1, 1, 5, 1, 5, 1, 1, 1 (units)

      involving the hypotenuses of (8, 15, 17) and (3, 4, 5) triangles.

      And the route looks like this:

      The direct route is shown in green (although only the first stage needs to come closest to this line – the direct line for subsequent steps runs from the current position to the destination).

      Like

    • Frits's avatar

      Frits 1:00 pm on 22 September 2024 Permalink | Reply

      @Jim, right now I come to the same “n” but to a different first five stages (different as of the 2nd stage).

      Having said that, I don’t understand the phrase: “If more than one well is equally close, he stops at the nearest one.”.

      Like

      • Jim Randell's avatar

        Jim Randell 1:20 pm on 22 September 2024 Permalink | Reply

        @Frits: I assumed that meant if there are multiple wells equally close to the direct line, then he chooses the one that is closest to his current position (i.e. the shortest distance to travel).

        Like

        • Frits's avatar

          Frits 1:23 pm on 22 September 2024 Permalink | Reply

          Thx, I will publish after the F1 has finished.

          Like

        • Frits's avatar

          Frits 9:30 pm on 22 September 2024 Permalink | Reply

          I finally understood the puzzle.

          # perpendicular distance from a point (x1, y1) to line ax + by + c = 0
          distance = lambda a, b, c, x1, y1: (abs(a * x1 + b * y1 + c) / 
                                             ((a * a + b * b)**.5))
                                             
          MX = 999999
          d = {n * n: n for n in range(1, 101)}
          
          def is_sqr(x, y):
            return d.get(x * x + y * y, None)
          
          # feasible diagonal routes (don't return z)  
          diags = [(x, y) for x in range(5, 100, 5) for y in range(5, 100, 5) 
                  if (z := is_sqr(x, y)) is not None]
          
          # find a solution that meets the requirements
          def check(journeys, a1, b1):
            a, b, c = a1, b1, 0
            pos = (0, 0)
            stops = []
            # keep adding stops if possible
            while pos[0] <= b1 and pos[1] <= -a1 and pos != (b1, -a1):
              mn = MX
              for j in set(journeys):
                pos2 = (pos[0] + j[0], pos[1] + j[1])       
                if not (pos2[0] <= b1 and pos2[1] <= -a1): continue
                # perpendicular distance to remaining line ax + by + c = 0
                dist = distance(a, b, c, pos2[0], pos2[1])
                if dist <= mn:
                  # if wells are equally close to the line, he stops at the nearest one
                  if dist == mn:
                    if j[0]**2 + j[1]**2 > min_j[0]**2 + min_j[1]**2:
                      continue
                  mn = dist
                  min_j = j
                  
              # set new position 
              pos = (pos[0] + min_j[0], pos[1] + min_j[1])   
          
              # calculate coefficients remaining line
              a, b = pos[1] + a1, b1 - pos[0]
              c = b * a1 - a * b1
              stops.append(min_j)
          
            # double check  
            if pos == (b1, -a1):
              yield stops
          
          E, dueE, dueN = 240, 50, 5
          # check possible north distances
          for N in range(5, E, 5):
            # check if the possible diagonal journeys with (0, 5) and (5, 0) 
            # can be fitted closest to the remaining straight-line route
            for stops in check(diags + [(0, 5), (5, 0)] , -N, E):
              if len(stops) != 15: continue
              if stops.count((0, 5)) != dueN // 5: continue
              if stops.count((5, 0)) != dueE // 5: continue
              print("answer:", [is_sqr(x, y) for x, y in stops[:5]],
                    "for N =", N)
          

          Like

  • Unknown's avatar

    Jim Randell 10:43 am on 17 September 2024 Permalink | Reply
    Tags:   

    Teaser 2604: Foreign friends 

    From The Sunday Times, 19th August 2012 [link] [link]

    The telephone number of my Japanese friend is a ten-digit number written as a group of five two-digit numbers. The phone number does not start with a 0, and no digit is used more than once. The numbers in the group are in increasing order, no two of them have a common factor greater than 1, and one of them is a fourth power. Also, the product of the numbers in the group is divisible by four of the first five primes.

    The telephone number of my Russian friend is also a ten-digit number but it is written as a group of two five-digit numbers. The number and group have the same properties as those stated above. The second digit of the Russian number is double the second digit of the Japanese number.

    What are the two telephone numbers?

    [teaser2604]

     
    • Jim Randell's avatar

      Jim Randell 10:44 am on 17 September 2024 Permalink | Reply

      Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      It runs in 772ms. (Internal runtime is 582ms, although this can be reduced to 377ms by splitting out the [[ is_coprime(@jps) ]] check into 10 separate coprime tests (one for each pair)).

      Note: An up-to-date version of enigma.py is required for the multiple argument version of is_coprime().

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      # Japanese phone number = AB CD EF GH IJ
      # Russian phone number = KLMNP QRSTU
      --distinct="ABCDEFGHIJ,KLMNPQRSTU"
      --macro="@jps = AB, CD, EF, GH, IJ"
      --macro="@rus = KLMNP, QRSTU"
      
      # neither phone number starts with 0
      --invalid="0,AK"
      
      # in the groups ...
      # the numbers are in increasing order
      "A < C" "C < E" "E < G" "G < I"
      "K < Q"
      
      # the numbers are pairwise co-prime
      "is_coprime(@jps)"
      "is_coprime(@rus)"
      
      # use "at least" or "exactly" for counting?
      --code="count = icount_at_least"  # or: icount_exactly
      
      # one of them is a fourth power
      --code="pow4s = set(i**4 for i in irange(0, 17))"
      --code="pow4 = lambda ns: count(ns, is_in(pow4s), 1)"
      "pow4([@jps])"
      "pow4([@rus])"
      
      # the product is divisible by four of {2, 3, 5, 7, 11}
      --code="_divs = (lambda n, ds, k: count(ds, (lambda d: n % d == 0), k))"
      --code="divs = (lambda ns: _divs(multiply(ns), [2, 3, 5, 7, 11], 4))"
      "divs([@jps])"
      "divs([@rus])"
      
      # 2nd digit of the Russian number is double the 2nd digit of the Japanese number
      "2 * B = L"
      --invalid="5|6|7|8|9,B"  # so, B < 5
      
      --template="(AB CD EF GH IJ) (KLMNP QRSTU)"
      --solution=""
      --denest=-1
      

      Solution: The numbers are: (23 49 50 67 81) and (46970 83521).

      The individual parts factorise as:

      (23 49 50 67 81) = ([23] [7×7] [2×5×5] [67] [3×3×3×3])
      (46970 83521) = ([2×5×7×11×61] [17×17×17×17])

      From which we see in each number there are no prime factors common to any two of the parts, so each is pairwise coprime.

      And the final part in each is the fourth power (of a prime).

      The top number has divisors of: 2, 3, 5, 7 (but not 11).

      The bottom number has divisors of: 2, 5, 7, 11 (but not 3).

      Like

      • Ruud's avatar

        Ruud 12:22 pm on 19 September 2024 Permalink | Reply

        Brute force:

        from istr import istr
        import math
        import functools
        import operator
        
        istr.repr_mode("str")
        solutions = {2: set(), 5: set()}
        
        for s in istr.permutations(istr.range(10)):
            if s[0] != 0:
                for k in (2, 5):
                    numbers = tuple(istr("".join(s[i : i + k])) for i in range(0, len(s), k))
                    if all(number0 < number1 for number0, number1 in zip(numbers, numbers[1:])):
                        if sum((float(number) ** (1 / 4)).is_integer() for number in numbers) == 1:
                            if sum(functools.reduce(operator.mul, numbers) % prime == 0 for prime in (2, 3, 5, 7, 11)) == 4:
                                if all(math.gcd(int(number0), int(number1)) == 1 for number0, number1 in istr.combinations(numbers, 2)):
                                    solutions[k].add(istr(" ").join(numbers))
        for japanese in solutions[2]:
            for russian in solutions[5]:
                if japanese[1] * 2 == russian[1]:
                    print(f"{japanese=} {russian=}")
        

        Like

    • GeoffR's avatar

      GeoffR 4:41 pm on 19 September 2024 Permalink | Reply

      # Japanese telephone number is AB CD EF GH IJ
      # Russian telephone number is KLMNP QRSTU
      
      from itertools import permutations
      from enigma import is_coprime
      
      # max 5 digits for the 4th power
      pow4 = [n * n * n * n for n in range(2, 18)]
      
      dgts = set(range(10))
      
      # Japanese Telephone Number
      for p1 in permutations(dgts, 4):
        jp_found = 0
        A, B, C, D = p1
        if 0 in (A, C): continue
        # Constraint on 2nd digit of 1st Tel No. i.e. L = 2 *  B
        if B == 0 or B > 4: continue
        if not A < C: continue
        AB, CD = 10*A + B, 10*C + D
        if not is_coprime(AB, CD): continue
      
        # Find remaining digits in Japanese Telephone Number
        q1 = dgts.difference({A, B, C, D})
        for p2 in permutations(q1):
          E, F, G, H, I, J = p2
          if 0 in (E, G, I): continue
          if not A < C < E < G < I: continue
          EF, GH, IJ = 10*E + F, 10*G + H, 10*I + J
          
          # check ten co-prime conditions 
          if is_coprime(CD, EF) and is_coprime(EF, GH) and is_coprime(GH, IJ) \
            and is_coprime(AB, EF) and is_coprime(AB, GH) and is_coprime(AB, IJ) \
            and is_coprime(CD, GH ) and is_coprime(CD, IJ) and is_coprime(EF, IJ):
              
            # Check for a fourth power
            if any (x in pow4 for x in (AB, CD, EF, GH, IJ)):
              # Find number of divisors of Japanese Tel. No.
              cnt = 0
              for num in (AB, CD, EF, GH, IJ):
                for p3 in (2, 3, 5, 7, 11):
                  if num % p3 == 0:
                    cnt += 1
                if cnt == 4:
                  print(f"Japanese No. is {AB} {CD} {EF} {GH} {IJ}.")
                  jp_found = 1
      
                # Russian Telephone Number - find first half of Tel. No.
                for p5 in permutations(dgts,5):
                  K, L, M, N, P = p5
                  if K == 0: continue
                  if L != 2 * B: continue
                  KLMNP = 10000*K + 1000*L + 100*M + 10*N + P
                  # Assume 4th power is QRSTU  
                  if KLMNP not in pow4:
                    cnt2 = 0
                    for p5 in (2, 3, 5, 7, 11):
                      if KLMNP % p5 == 0:
                        cnt2 += 1
                  if cnt2 == 4:
                      
                    # Find second half of Russian Tel. No.
                    q6 = dgts.difference({K, L, M, N, P})
                    for p7 in permutations(q6):
                      Q, R, S, T, U = p7
                      QRSTU = 10000*Q + 1000*R + 100*S + 10*T + U
                      if Q == 0: continue
                      if not KLMNP < QRSTU: continue
                      if not is_coprime(KLMNP, QRSTU): continue
                      if QRSTU in pow4 and jp_found == 1:
                        print(f"Russian No. is {KLMNP} {QRSTU}.")
      
      #Japanese No. 23 49 50 67 81
      # Russian No. is 46970 83521
      
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 6:12 am on 15 September 2024 Permalink | Reply
    Tags:   

    Teaser 3234: An existential threat thwarted 

    From The Sunday Times, 15th September 2024 [link] [link]

    “Merlin, the Saxons are on the rampage. A group of 90 soldiers is advancing towards Mount Badon. We only have 86 knights that we can muster. I think we are doomed”, said the King.

    “Not necessarily, Sire. The strength of an army is proportional to the square of the number of its troops. An army of 100 would defeat an army of 80 yet still have 60 remaining because 100^2 − 80^2 = 60^2. Tell the knights to split into three groups of particular sizes and engage the Saxons in three simultaneous battles. If the Saxons split into three groups of 30, we can prevail.”

    After the conflict there were 32 knights and 24 Saxons remaining.

    What were the sizes of the three groups the knights split into?

    [teaser3234]

     
    • Jim Randell's avatar

      Jim Randell 6:21 am on 15 September 2024 Permalink | Reply

      I am assuming we are looking for battles where there is an integer number of survivors.

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

      from enigma import (decompose, ircs, printf)
      
      # battle <xs> against <ys>, looking for integer advantages
      def battle(xs, ys):
        rx = ry = 0
        for (x, y) in zip(xs, ys):
          if x > y:
            r = ircs(x, -y)
            if r is None: return (None, None)
            rx += r
          elif y > x:
            r = ircs(y, -x)
            if r is None: return (None, None)
            ry += r
        return (rx, ry)
      
      # split the knights into 3 groups
      for ks in decompose(86, 3, increasing=1, sep=0, min_v=1):
        # battle the Knights against the groups of Saxons
        (rK, rS) = battle(ks, (30, 30, 30))
        if rK is None: continue
        # look for scenarios where the Knights prevail
        if not (rK > rS): continue
        # output solution
        printf("{ks} -> {rS} Saxons, {rK} Knights")
      

      Solution: The Knights split into groups of size: 18, 34, 34.

      So we have the following battles:

      30 Saxons vs. 18 Knights → 24 Saxons remaining
      30 Saxons vs. 34 Knights → 16 Knights remaining
      30 Saxons vs. 34 Knights → 16 Knights remaining
      total: 90 Saxons vs. 86 Knights → 24 Saxons, 32 Knights remaining; Knights prevail

      For battles with integer advantages there is one other solution, but in this case the Saxons prevail:

      30 Saxons vs. 18 Knights → 24 Saxons remaining
      30 Saxons vs. 18 Knights → 24 Saxons remaining
      30 Saxons vs. 50 Knights → 40 Knights remaining
      total: 90 Saxons vs. 86 Knights → 48 Saxons, 40 Knights remaining; Saxons prevail

      So we don’t need to know the number of survivors to solve the puzzle.


      Manually:

      There are only 6 possible battles that give an integer number of survivors where one of the sides has 30 participants, and the other side has less than 86:

      (30, 24) → (18, 0)
      (30, 18) → (24, 0)
      (30, 30) → (0, 0)
      (30, 34) → (0, 16)
      (30, 50) → (0, 40)
      (30, 78) → (0, 72)

      And by inspection, the only way for there to be 24 Saxons and 32 Knights remaining in 3 battles is:

      (30, 18) → (24, 0)
      (30, 34) → (0, 16)
      (30, 34) → (0, 16)

      Like

      • Jim Randell's avatar

        Jim Randell 6:08 pm on 15 September 2024 Permalink | Reply

        This is faster (and shorter). Internal runtime is 134µs.

        from enigma import (pythagorean_triples, subsets, printf)
        
        # if A beats B and has C survivors then:
        #   A^2 - B^2 = C^2
        #   B^2 + C^2 = A^2 (i.e. a Pythagorean triple)
        
        # record (<saxons>, <knights>, <remaining-saxons>, <remaining-knights>)
        ss = [(30, 30, 0, 0)]  # draw
        
        # find pythagorean triples involving 30
        for (x, y, z) in pythagorean_triples(84):
          if z == 30:
            ss.extend([(z, y, x, 0), (z, x, y, 0)])
          if y == 30:
            ss.append((y, z, 0, x))
          if x == 30:
            ss.append(((x, z, 0, y)))
        
        # choose 3 battles
        for bs in subsets(ss, size=3, select='R'):
          # calculate initial knights (K) and total survivors (rS, rK)
          (Ss, Ks, rSs, rKs) = zip(*bs)
          (K, rS, rK) = map(sum, (Ks, rSs, rKs))
          if K == 86 and rK > rS:
            printf("Knights = {Ks} -> {rS} Saxons, {rK} Knights [battles = {bs}]")
        

        Like

    • GeoffR's avatar

      GeoffR 5:34 pm on 15 September 2024 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % As the Knights have 32 men left and the Saxons 24 men left after three battles....
      % Assume the Saxons win the 1st battle and the Knights the next 2 battles
      % Also, the Saxons have 30 men in each of the three battles
      
      % K1 knights in 1st battle, K2 knights in 2nd battle and K3 knights in 3rd battle
      var 1..29:K1; var 31..86:K2; var 31..86:K3;
      
      constraint K1 + K2 + K3 == 86; % There are 86 knights in total
      
      predicate is_sq(var int: y) =
        exists(z in 1..ceil(sqrt(int2float(ub(y))))) (
              z*z = y );
              
      % Let the Saxons win the 1st battle
      constraint 30 * 30 - K1 * K1 == 24 * 24; % Saxons have 24 men left after 3 battles
      
      % Let the Knights win 2nd and 3rd battles
      constraint is_sq((K2 * K2 - 30 * 30)) /\ is_sq((K3 * K3 - 30 * 30));
      
      solve satisfy;
      
      output ["The three groups of the knights are " ++ show([K1, K2, K3])];
      
      
      
      
      

      A manual check on K2 and K3 knights showed there were 32 knights left.

      Like

    • Ruud's avatar

      Ruud 10:06 am on 17 September 2024 Permalink | Reply

      This code runs in 57 ms on my M4 iPad Pro.

      import itertools
      import math
      
      for sizes in itertools.product(range(87), repeat=3):
          if sum(sizes) == 86 and sizes == tuple(sorted(sizes)):
              knights = 0
              saxons = 0
              for size in sizes:
                  if (diff := math.sqrt(abs((size**2 - 30**2)))).is_integer():
                      knights += (size > 30) * int(diff)
                      saxons += (size < 30) * int(diff)
                  else:
                      break
              else:
                  if knights > saxons:
                      print(f"{sizes=} {knights=} {saxons=}")
      

      Like

  • Unknown's avatar

    Jim Randell 10:18 am on 11 September 2024 Permalink | Reply
    Tags: ,   

    Brain-Teaser 734: Golden orchard 

    From The Sunday Times, 10th August 1975 [link]

    A farmer grows apples in an orchard divided into plots —three to the East and three to the West of a central path. The apples are of two types — for eating (Cox, Laxton, Pearmain) and for cider making (Tremlitt, Coppin, Kingston).

    Adjacent plots contain apples of different basic type. The apples are of six colours (red, green, russet, golden, orange, yellow) and of six tastes (sweet, sour, acid, tart, pleasant, bitter).

    They ripen at different times, either early or late in July, August and September. Those ripening in early or late September are in plots directly opposite. Those South of Pearmain do not ripen in August. Tart are directly West of the acid variety, which ripens in early August. Yellow apples and those maturing in late September are adjacent. Yellow and orange are of the same type. Orange are North of pleasant and also North of Pearmain. Kingstons are adjacent to golden. Green is South of bitter.

    Cox ripen in early July, and Laxtons ripen early in a different month. Tremlitts are red, and Kingstons mature after Coppins, which are not sour.

    If cider apples taste unpleasant, what are the characteristics of the apples in North East plot? (Name, colour, taste, ripens).

    This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 2 (1981).

    I think the puzzle as published in The Sunday Times and in the book is open to interpretation, and my first attempt using a reasonable interpretation gave two solutions (neither of which are the published solution). After examining the given solution in the book I think the following wording is clearer:

    A farmer grows apples in an orchard divided into plots — three to the East and three to the West of a central track. Adjacent plots are separated by a shared fence. The apples are of two basic types — for eating (Cox, Laxton, Pearmain) and for cider making (Tremlitt, Coppin, Kingston).

    Neighbouring plots contain apples of different basic type. The apples are of six colours (red, green, russet, golden, orange, yellow) and of six tastes (sweet, sour, acid, tart, pleasant, bitter).

    They ripen at different times, either early or late in July, August and September. Those ripening in early or late September are in plots directly opposite each other. Those directly South of Pearmain do not ripen in August. Tart are directly West of the acid variety, which ripens in early August. Yellow apples and those maturing in late September are in adjacent plots. Yellow and orange are of the same basic type. Orange are directly North of Permain, which are pleasant. Kingstons and golden are in adjacent plots. Green is directly South of bitter.

    Cox ripen in early July, and Laxtons ripen early in a different month. Tremlitts are red, and Kingstons mature after Coppins, which are not sour.

    If cider apples are neither pleasant nor sweet, what are the characteristics of the apples in North-East plot?

    [teaser734]

     
    • Jim Randell's avatar

      Jim Randell 10:20 am on 11 September 2024 Permalink | Reply

      When I first tackled this puzzle (using the text from the 1981 book, and what I considered to be the most reasonable interpretation of the text), I found two solutions. And neither of them matched the published solution.

      According to the solution published in The Sunday Times [link] there were:

      A load of wrong answers (and some unacceptable multi-entries) in diffuse permutations brightly offset by an authentic minority including the winner …

      However, I think the wording of the puzzle is too vague to permit a single solution.

      Having looked at the answer in the book, I constructed the alternative wording, which I hope is clearer.


      Using the [[ SubstitutedExpression ]] solver from the enigma.py library, we can assign the characteristics to the plots.

      This run-file executes in 81ms. (Internal runtime of the generated code is 1.2ms).

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      # plots are:
      #
      #   1 || 2
      #   --++--
      #   3 || 4
      #   --++--
      #   5 || 6
      #
      # we need to assign each of the six characteristics from each group
      # to a different plot number
      #
      # Eating: A = Cox; B = Laxton; C = Permain
      # Cider: D = Tremlitt; E = Coppin; F = Kingston
      #
      # Colour: G = red; H = green; I = russet; J = golden; K = orange; L = yellow
      #
      # Taste: M = sweet; N = sour; P = acid; Q = tart; R = pleasant; S = bitter
      #
      # Season: T = early Jul; U = late Jul; V = early Aug; W = late Aug; X = early Sep; Y = late Sep
      
      --base=7
      --digits="1-6"
      
      --distinct="ABCDEF,GHIJKL,MNPQRS,TUVWXY"
      
      # row adjacency (W, E)
      --code="row_adj = {(1, 2), (3, 4), (5, 6)}"
      
      # col adjacency (N, S)
      --code="col_adj = {(1, 3), (2, 4), (3, 5), (4, 6)}"
      
      # adjacent plots contain apples of different types
      "{A, B, C} in ({1, 4, 5}, {2, 3, 6})"
      
      # those ripening in early/late September (X, Y) are opposite
      "ordered(X, Y) in row_adj"
      
      # Southerly neighbour of Permain (C) do not ripen in Aug (V, W)
      "C not in {5, 6}"  # implies Permain (C) is not in southernmost row
      "(C, V) not in col_adj"
      "(C, W) not in col_adj"
      
      # tart (Q) are directly West of acid (P)
      "(Q, P) in row_adj"
      
      # acid (P) ripens in early Aug (V)
      "P = V"
      
      # yellow apples (L) and those maturing in late Sep (Y) are adjacent
      "ordered(L, Y) in col_adj"
      
      # yellow (L) and orange (K) are of the same type
      "len(intersect([{L, K}, {A, B, C}])) != 1"
      
      # orange (K) are Northerly neighbours of pleasant (R), and also Northerly neighbours of Permain (C)
      "(K, R) in col_adj"
      "(K, C) in col_adj"
      
      # Kingston (F) are adjacent to golden (J)
      "ordered(F, J) in col_adj"
      
      # green (H) is Southerly neighbour of bitter (S)
      "(S, H) in col_adj"
      
      # Cox (A) ripen in early Jul (T)
      "A = T"
      
      # Laxtons (B) ripen early in [not Jul] (V, X)
      "B in {V, X}"
      
      # Tremlitts (D) are red (G)
      "D = G"
      
      # Kingstons (F) mature after Coppins (E)
      "[T, U, V, W, X, Y].index(F) > [T, U, V, W, X, Y].index(E)"
      
      # Coppins (E) are not sour (N)
      "E != N"
      
      # cider apples do not taste pleasant (R) or sweet (M)
      "R not in {D, E, F}"
      "M not in {D, E, F}"
      
      # make sure all the variables are filled out
      "true(A, B, C, D, E, F, G, H, I, J, K, L, M, N, P, Q, R, S, T, U, V, W, X, Y)"
      
      --template="(A B C D E F) (G H I J K L) (M N P Q R S) (T U V W X Y)"
      --solution=""
      --denest=-1
      

      And the following Python program can be used to make the output more friendly:

      from enigma import (SubstitutedExpression, join, printf)
      
      p = SubstitutedExpression.from_file("teaser734b.run")
      
      # labels for the characteristics
      label = dict(
        # Type:
        A="Cox", B="Laxton", C="Permain", D="Tremlitt", E="Coppin", F="Kingston",
        # Colour:
        G="red", H="green", I="russet", J="golden", K="orange", L="yellow",
        # Taste:
        M="sweet", N="sour", P="acid", Q="tart", R="pleasant", S="bitter",
        # Season:
        T="early Jul", U="late Jul", V="early Aug", W="late Aug", X="early Sep", Y="late Sep",
      )
      
      # solve the puzzle
      for s in p.solve(verbose=0):
        # collect the characteristics for each plot
        d = dict((k, list()) for k in [1, 2, 3, 4, 5, 6])
        for k in sorted(s.keys()):
          d[s[k]].append(label.get(k))
        # output the solution
        for k in sorted(d.keys()):
          printf("{k} -> {v}", v=join(d[k], sep="; "))
        printf()
      

      Solution: The North-East plot contains Cox, russet in colour, sweet in taste, and ripens in early July.

      The full solution is:

      Like

  • Unknown's avatar

    Jim Randell 12:22 am on 8 September 2024 Permalink | Reply
    Tags:   

    Teaser 3233: Not Mrs Perkins’ quilt! 

    From The Sunday Times, 8th September 2024 [link] [link]

    Sue was making a quilt in the shape of an equilateral triangle and she sewed a straight line of stitches from each corner of the quilt to its opposite edge, so as to divide each edge in the ratio 1:2 in a clockwise direction. Sue covered the region enclosed by the lines of stitches with a triangular piece of material of exactly the same size. The area of this piece was 2 square feet.

    Including the triangular quilt and the extra triangular piece, what was the total area of material used?

    Mrs. Perkins’s quilt is a puzzle by Henry Ernest Dudeney from his book “Amusements in Mathematics” (1917).

    [teaser3233]

     
    • Jim Randell's avatar

      Jim Randell 12:41 am on 8 September 2024 Permalink | Reply

      See also: Teaser 2865, Enigma 1076, Enigma 320, Enigma 1313.

      We can solve the puzzle directly using Routh’s Theorem [ @wikipedia ], which I have previously made some notes on here [ rouths-theorem.pdf ]

      In this case we have x = y = z = 2, hence:

      XYZ / ABC = (x − 1)^2 / (x^2 + x + 1)
      XYZ / ABC = 1 / 7

      We are given the area XYZ = 2, hence ABC = 14.

      And the total area of the two triangles is easily calculated.

      from enigma import (rdiv, printf)
      
      # ratio XYZ/ABC in Routh's theorem
      def routh(x, y, z):
        a = x * y * z - 1
        b = (x * y + y + 1) * (y * z + z + 1) * (z * x + x + 1)
        return rdiv(a * a, b)
      
      # compute the ratio r = XYZ / ABC
      r = routh(2, 2, 2)
      
      # calculate the areas of the triangles
      XYZ = 2
      ABC = rdiv(XYZ, r)
      
      # calculate the total area
      T = ABC + XYZ
      printf("total area = {T}")
      

      Solution: The total area of material used is: 16 square feet.

      Note that the result holds even if the triangle is not equilateral.

      Like

    • GeoffR's avatar

      GeoffR 8:07 am on 8 September 2024 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      int: x == 2;
      int: y == 2;
      int: z == 2;
       
      var 1..35:ABC;
      var 1..5:XYZ; 
      
      % Using Routh's theorem
      constraint XYZ * (x*x + x + 1) == ABC * (x - 1 ) * (x - 1);
      constraint XYZ * 7 == ABC /\ XYZ == 2;
      
      solve satisfy;
      output["Total area = " ++ show(ABC + XYZ) ++ " Sq. Ft."];
      
      

      Like

  • Unknown's avatar

    Jim Randell 6:51 pm on 4 September 2024 Permalink | Reply
    Tags:   

    Brainteaser 1047: Youth opportunities 

    From The Sunday Times, 22nd August 1982 [link]

    Five of the shops in our local High Street sell cakes, electrical goods, greengrocery, hardware and shoes. Each decided recently take on two young assistants, one of each sex, from the Youth Opportunities Scheme.

    These ten lucky youngsters include Hazel and Stephen, who live on either side of my house, and Eric from across the road. He gave me the following information:

    The initials of the assistants’ forenames are all different from the initial of the shop in which they work. Moreover no boy works with a girl whose initial is the same as his own. In addition, Emma does not work with Henry, nor does she work in the shoe shop.

    Henry doesn’t work the in the cake shop, Gordon is not in the hardware shop, Gwen is not in the shoe shop, and  neither Charles nor Sheila work in the greengrocer’s.

    If Carol works in the hardware shop, who sells the electrical goods?

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

    [teaser1047]

     
    • Jim Randell's avatar

      Jim Randell 6:51 pm on 4 September 2024 Permalink | Reply

      Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      Most of the conditions can be dealt with using the [[ --distinct ]] and [[ --invalid ]] parameters.

      The following run file executes in 70ms. (Internal runtime of the generated code is just 27µs).

      Run: [ @jdoodle ]

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      # shops: 0 1 2 3 4  (= Cakes, Electricals, Greengrocers, Hardware, Shoes)
      # boys:  Q R S T U  (= Charles, Eric, Gordon, Henry, Steven; in some order)
      # girls: V W X Y Z  (= Carol, Emma, Gwen, Hazel, Shiela; in some order)
      
      --base=5
      # boys and girls have different initials
      # but no-one works with someone with the same initial
      --distinct="QRSTU,VWXYZ,QV,RW,SX,TY,UZ"
      
      # no-one shares an initial with the shop
      # Emma does not work in the shoe shop
      # Gwen does not work in the shoe shop
      # Henry does not work in the cake shop
      # Gordon does not work in the hardware shop
      # neither Charles nor Shiela work in the greengrocers
      --invalid="0,QVS"   # C = 0
      --invalid="1,RWZ"   # E = 1
      --invalid="2,SXZT"  # G = 2
      --invalid="3,TYQ"   # H = 3
      --invalid="4,UZX"   # S = 4
      
      # Carol works in the hardware shop
      --assign="Y,0"
      
      # Henry and Emma do not work together
      "(Q != 3) or (V != 1)" "(S != 3) or (X != 1)"
      
      --answer="((Q, R, S, T, U), (V, W, X, Y, Z))"
      --template="(Q R S T U) (V W X Y Z)"
      --solution=""
      

      We can write additional Python code to format the output nicely:

      from enigma import (SubstitutedExpression, printf)
      
      # label shops and people
      shops = "Cakes Electricals Greengrocers Hardware Shoes".split()
      boys  = "Charles Eric Gordon Henry Steven".split()
      girls = "Carol Emma Gwen Hazel Shiela".split()
      
      # load the puzzle
      p = SubstitutedExpression.from_file("teaser1047.run")
      
      # solve the puzzle, and format solutions
      for (bs, gs) in p.answers(verbose=0):
        for (s, (b, g)) in enumerate(zip(bs, gs)):
          printf("{s} = {b} + {g}", s=shops[s], b=boys[b], g=girls[g])
        printf()
      

      Solution: Henry and Gwen work in the electrical goods shop.

      The full solution is:

      Cakes = Gordon + Shiela
      Electricals = Henry + Gwen
      Greengrocers = Steven + Emma
      Hardware = Eric + Carol
      Shoes = Charles + Hazel

      Like

      • Frits's avatar

        Frits 10:35 am on 5 September 2024 Permalink | Reply

        This is much more intuitive to me:

        #! python3 -m enigma -r
         
        SubstitutedExpression
         
        # shops: 0 1 2 3 4  (= Cakes, Electricals, Greengrocers, Hardware, Shoes)
        # boys:  Q R S T U  (= Charles, Eric, Gordon, Henry, Steven)
        # girls: V W X Y Z  (= Carol, Emma, Gwen, Hazel, Sheila)
         
        --base=5
        # boys and girls have different initials
        # but no-one works with someone with the same initial
        --distinct="QRSTU,VWXYZ,QV,RW,SX,TY,UZ"
         
        # no-one shares an initial with the shop
        # Emma does not work in the shoe shop
        # Gwen does not work in the shoe shop
        # Henry does not work in the cake shop
        # Gordon does not work in the hardware shop
        # neither Charles nor Sheila work in the greengrocers
        --invalid="0,QVT"   # C = 0
        --invalid="1,RW"    # E = 1
        --invalid="2,SXQZ"  # G = 2
        --invalid="3,TYS"   # H = 3
        --invalid="4,UZWX"  # S = 4
         
        # Carol works in the hardware shop
        --assign="V,3"
         
        # Henry and Emma do not work together
        "T != W"
         
        --answer="((Q, R, S, T, U), (V, W, X, Y, Z))"
        --template="(Q R S T U) (V W X Y Z)"
        --solution=""
        

        and

        from enigma import (SubstitutedExpression, printf)
         
        # label shops and people
        shops = "Cakes Electricals Greengrocers Hardware Shoes".split()
        boys  = "Charles Eric Gordon Henry Steven".split()
        girls = "Carol Emma Gwen Hazel Sheila".split()
         
        # load the puzzle
        p = SubstitutedExpression.from_file("teaser/teaser1047.run")
         
        # solve the puzzle, and format solutions
        for (bs, gs) in p.answers(verbose=0):
          for i in range(5):
            b, g = boys[bs.index(i)], girls[gs.index(i)]
            print(shops[i], "=", b, "+", g)
        

        Like

  • Unknown's avatar

    Jim Randell 6:17 am on 1 September 2024 Permalink | Reply
    Tags:   

    Teaser 3232: Digital processing 

    From The Sunday Times, 1st September 2024 [link] [link]

    I divided 1 by 5 in base 7 in the following way. I started with 1, multiplied by the base (7), recorded the result on division by 5 as a digit (1), then used the remainder (2) to repeat the process until the remainder became 0 or the pattern was about to repeat. The result was 0.1254 with those four digits then repeating.

    For some base no more than 20 I also calculated the result of dividing 1 by all numbers from 2 up to the base minus 1. With one of these divisors the result had the “digit” 14 at one point followed immediately by the “digit” 13. Some “digits” never occurred in the fractional part with any of these divisors.

    What “digits” (in increasing order) never occurred?

    [teaser3232]

     
    • Jim Randell's avatar

      Jim Randell 6:36 am on 1 September 2024 Permalink | Reply

      We can use the [[ recurring() ]] function from the enigma.py library to calculate the expansion of a fraction in different bases. (Originally written for Enigma 1247).

      The following Python program runs in 69ms. (Internal runtime is 949µs).

      Run: [ @jdoodle ]

      from enigma import (irange, recurring, int2base, base2int, format_recurring, printf)
      
      # look for digit X followed by digit Y
      (X, Y) = (14, 13)  # {14}:{13} = "ED"
      
      # examine reciprocals in base <b>
      def solve(b, verbose=0):
        # look for subsequence X:Y
        i2b = lambda n: int2base(n, base=b)
        (ss, f) = (i2b(X) + i2b(Y), 0)
        # unused digits
        ds = set(i2b(n) for n in irange(0, b - 1))
        for k in irange(2, b - 1):
          (i, nr, rr) = recurring(1, k, base=b)
          if verbose: printf("[{b}] {k} -> {x}", x=format_recurring((i, nr, rr)))
          if ss in nr + rr + rr[:1]: f = 1
          ds.difference_update(nr, rr)
        if f:
          # output solution (using integer digits)
          ds = list(base2int(d, base=b) for d in ds)
          printf("base={b} -> unused digits = {ds}", ds=sorted(ds))
      
      # consider bases up to 20
      for b in irange(max(X, Y) + 1, 20):
        solve(b)
      

      Solution: The unused digits are: 0, 12, 15, 17.

      In base 18 the reciprocals from 1/2 to 1/17 have the following expansions:

      1/2 = 0.9
      1/3 = 0.6
      1/4 = 0.49
      1/5 = 0.(3AE7)…
      1/6 = 0.3
      1/7 = 0.(2A5)…
      1/8 = 0.249
      1/9 = 0.2
      1/10 = 0.1(E73A)…
      1/11 = 0.(1B834G69ED)… [this contains E followed by D]
      1/12 = 0.19
      1/13 = 0.(16GB)…
      1/14 = 0.1(52A)…
      1/15 = 0.1(3AE7)…
      1/16 = 0.1249
      1/17 = 0.(1)…

      The digits (from 0123456789ABCDEFGH) that do not occur in the fractional parts of these expansions are:

      0
      C = 12
      F = 15
      H = 17

      The puzzle limits us to bases up to 20, but the next solutions don’t occur until bases 58, 86, 142.

      Like

      • Frits's avatar

        Frits 3:00 pm on 2 September 2024 Permalink | Reply

        @Jim, Brian’s counting of the divisors that have the special subsequence is more pure than our approach (as it doesn’t say “With at least one of these divisors”).

        Like

        • Jim Randell's avatar

          Jim Randell 4:11 pm on 2 September 2024 Permalink | Reply

          @Frits: Unless the puzzle is explicit about there being exactly one case, I usually take a relaxed interpretation where the finding of one case is sufficient (a logical existential quantification). In this puzzle we don’t need to use the strict interpretation of “exactly one”.

          Like

    • Frits's avatar

      Frits 10:44 am on 1 September 2024 Permalink | Reply

      # does list <lst2> occur in list <lst1>
      inList = lambda lst1, lst2: any(lst1[i:i + len(lst2)] == lst2
                                      for i in range(len(lst1) - len(lst2) + 1))
      
      # return digits in base b in the fraction k / b (where k < b)
      # (not repeating decimals) 
      def divide(b, k):
        r, s, rs = 1, [], set()
        while True:
          (d, r) = divmod(r * b, k)
          s.append(d)
          # break if no remainder or repeating decimals encountered
          if not r or r in rs: break
          rs.add(r)  
        return s 
      
      # consider bases from 15 to 20 (base must be higher than 14)
      for b in range(15, 21):
        found1413, seen = 0, set()
        for k in range(2, b): 
          dgts = divide(b, k)
          # does list [14, 13] occur in <dgts>?
          if inList(dgts, [14, 13]):
            found1413 = 1
          seen |= set(dgts)
          
        if found1413:
          print(f"answer: {sorted(set(range(b)).difference(seen))}")
      

      Like

      • Jim Randell's avatar

        Jim Randell 11:31 am on 2 September 2024 Permalink | Reply

        @Frits: I don’t see how you can differentiate between recurring and non-recurring expansions returned by your [[ divide() ]] routine.

        >>> divide(10, 18)
        [0, 5]
        >>> divide(10, 20)
        [0, 5]
        

        Would your program spot the occurrence of adjacent digits D and 6 in the expansion of 1/15 in base 20?

        1/15 (base 20) = 0.1(6D)… = 0.16D6D6D…

        >>> divide(20, 15)
        [1, 6, 13]
        

        Like

        • Frits's avatar

          Frits 2:48 pm on 2 September 2024 Permalink | Reply

          @Jim, the divide function has been made with the comment “(where k less than b)” so the first question I don’t understand. I don’t think I need to differentiate between recurring and non-recurring except for the valid 2nd point you make (divide(20, 15)).

          Here is the adjustment (assuming we have have to scan for only 2 “digits”):

          # does list <lst2> occur in list <lst1>
          isSubList = lambda lst1, lst2: any(lst1[i:i + len(lst2)] == lst2
                                             for i in range(len(lst1) - len(lst2) + 1))
          
          # return "digits" in base b in the fraction 1 / k (where k < b)
          # (not repeating "decimals") 
          def divide(b, k):
            assert b > k 
            r, s, dct = 1, [], dict()
            while True:
              p = r 
              (d, r) = divmod(r * b, k)
              s.append(d)
              if not r: 
                return s
              # repeating "decimals" encountered?  
              if r in dct: 
                # also suffix first "digit" of repetend as we have to look 
                # for a sequence of two "digits"
                return s if r == p else s + [dct[r]] 
              dct[p] = d
            
          # consider bases from 15 to 20 (base must be higher than 14)
          for b in range(15, 21):
            found1413, seen = 0, set()
            for k in range(2, b): 
              dgts = divide(b, k)
              # does list [14, 13] occur in <dgts>?
              if isSubList(dgts, [14, 13]):
                found1413 = 1
              seen |= set(dgts)
              
            if found1413:
              print(f"answer: {sorted(set(range(b)).difference(seen))}")
          

          Like

          • Jim Randell's avatar

            Jim Randell 4:15 pm on 2 September 2024 Permalink | Reply

            @Frits: It was the same point really. I was trying to show a case where the return value was obviously ambiguous. But I strayed outside the acceptable parameters of your function. I should have used a different example.

            Like

    • GeoffR's avatar

      GeoffR 11:38 am on 2 September 2024 Permalink | Reply

      @Jim:
      Can you please show how the first paragraph works to get an answer of 0.1245 with th same repeating digits? (as the main teaser is the second paragraph)

      Like

      • Jim Randell's avatar

        Jim Randell 12:02 pm on 2 September 2024 Permalink | Reply

        @GeoffR:

        Starting with 1 we perform the following calculations:

        (1 × 7) / 5 = 1 (remainder 2)
        (2 × 7) / 5 = 2 (remainder 4)
        (4 × 7) / 5 = 5 (remainder 3)
        (3 × 7) / 5 = 4 (remainder 1)

        At the end of these 4 steps we have written down 1254 and are about to start the next step with the remainder 1. But this is the same as the value we started with at the beginning, so we will just go through the same steps again.

        So the result is:

        1/5 [base 7] = 0. 1254 1254 1254 …

        >>> recurring(1, 5, base=7)
        Recurring(i='0', nr='', rr='1254')
        

        Like

    • Frits's avatar

      Frits 9:07 pm on 4 September 2024 Permalink | Reply

      Limiting the calls to divide().

      # return "digits" in base b in the fraction 1 / k (where k < b)
      # (not repeating "decimals") 
      def divide(b, k):
        assert b > k 
        r, s, dct = 1, [], dict()
        while True:
          p = r 
          (d, r) = divmod(r * b, k)
          s.append(d)
          if not r: 
            return s
          # repeating "decimals" encountered?  
          if r in dct: 
            # also suffix first "digit" of repetend as we have to look 
            # for a sequence of two "digits"
            return s if r == p else s + [dct[r]] 
          dct[p] = d
        
      seq = [14, 13]
      
      # consider bases to 20
      for b in range(max(seq) + 1, 21):
        for k in range(2, b):   
          # 14 = (r * b) // k
          r1 = (seq[0] * k) // b + 1
          (d2, r2) = divmod(r1 * b, k)  
          if d2 != seq[0]: continue
          (d3, r3) = divmod(r2 * b, k) 
          # seq[0] has to be followed by seq[1]
          if d3 != seq[1]: continue
          
          # check if first specified item is one of the "digits" in the fraction
          dgts = divide(b, k)
          if seq[0] not in dgts: continue
          seen = set(dgts)
          for k2 in range(2, b): 
            if k2 == k: continue
            seen |= set(divide(b, k2))
            
          print(f"answer: {sorted(set(range(b)).difference(seen))}")  
          break
      

      Like

  • Unknown's avatar

    Jim Randell 11:11 am on 29 August 2024 Permalink | Reply
    Tags: by: Simon Massarella   

    Teaser 2592: Inventive inventories 

    From The Sunday Times, 27th May 2012 [link] [link]

    It is known that there is just one 10-digit number that is “self-counting” in the sense that its first digit equals the number of 1s in it, the second digit equals the number of 2s in it, and so on, with the ninth digit equalling the number of 9s in it and the tenth digit equalling the number of 0s in it.

    Similarly, a 9-digit number is “self-counting” if its first digit equals the number of 1s in it, the second digit equals the number of 2s in it, and so on, with the ninth digit equalling the number of 9s in it (and with the 0s remaining uncounted).

    (a) What is the 10-digit self-counting number?
    (b) What is the highest 9-figure self-counting number?

    [teaser2592]

     
    • Jim Randell's avatar

      Jim Randell 11:12 am on 29 August 2024 Permalink | Reply

      This is puzzle is a variation on autobiographical numbers (or curious numbers), see: Puzzle #16, Enigma 476.

      Except in autobiographical numbers the digits (in order) usually count the number 0’s, then then numbers of 1’s, 2’s, etc.

      The following Python program runs in 386ms. (Internal runtime is 309ms).

      from enigma import (irange, decompose, join, printf)
      
      # generate self counting sequences
      def self_counting(k):
        js = (1, 2, 3, 4, 5, 6, 7, 8, 9, 0)
        assert k == 10 or k in js
        # t of the k digits are counted
        for t in (irange(0, k) if k < 10 else [10]):
          # decompose the t digits into the k counted slots
          for ns in decompose(t, k, increasing=0, sep=0, min_v=0):
            # check the counting works
            if all(ns.count(j) == n for (j, n) in zip(js, ns)):
              yield ns
      
      # find length 10 and 9 self counting numbers
      for k in [10, 9]:
        for ns in self_counting(k):
          if (ns[0] == 0 and len(ns) > 1): continue  # skip leading zeros
          printf("[{k}] {ns}", ns=join(ns))
      

      Solution: (a) 2100010006; (b) 100000000.

      There is an additional self-counting sequence of size 9 and that is (0, 0, 0, 0, 0, 0, 0, 0, 0), but that does not give a viable 9-digit self-counting number (and even if it did we are looking for largest 9-digit self-counting number).

      The full list of self-counting sequences:

      1: 0, 1
      2: 00, 10
      3: 000, 100
      4: 0000, 1000
      5: 00000, 10000
      6: 000000, 100000
      7: 0000000, 1000000
      8: 00000000, 10000000
      9: 000000000, 100000000
      10: 2100010006

      If we bring the 0 to the front of the [[ js ]] array (at line 5), then we get the more usual base 10 autobiographical numbers.

      4: 1210, 2020
      5: 21200
      7: 3211000
      8: 42101000
      9: 521001000
      10: 6210001000

      And we see for the 10-digit self-counting number (where each of the digits is counted) we can calculate the 10-digit autobiographical number and move the leading digit to the end.

      Like

  • Unknown's avatar

    Jim Randell 12:52 am on 25 August 2024 Permalink | Reply
    Tags: ,   

    Teaser 3231: In his prime 

    From The Sunday Times, 25th August 2024 [link] [link]

    Once, on my grandson’s birthday, I asked him the following five questions:

    1. How many days are there in this month?
    2. How many Mondays are there in this month?
    3. How many “prime” days (i.e. 2nd, 3rd, 5th, …) are there in this month?
    4. How many of those prime days are Saturdays?
    5. How many letters are there when you spell the month?

    The total of the five answers was a prime number.

    Then I asked him the same questions the next day. No answer was the same as for the day before, but again the total of the five answers was prime.

    When I first asked the questions what was the month and day of the week?

    As set this puzzle has multiple solutions. However there is a unique answer for the birthday of the grandson (month and day of month).

    [teaser3231]

     
    • Jim Randell's avatar

      Jim Randell 1:30 am on 25 August 2024 Permalink | Reply

      Assuming the grandson answers each of the questions correctly, if the answer to each question must be different from that of the previous day, then the next day must be in a different month to the birthday.

      This Python program works backwards, considering the answers for pairs of adjacent months, until it finds the most recent viable solution. (Assuming the system locale is set to find appropriate day and month names).

      It runs in 68ms. (Internal runtime is 2.8ms).

      Run: [ @replit ]

      from datetime import (date, timedelta)
      from enigma import (Record, repeat, inc, first, icount, primes, unpack, tuples, printf)
      
      # increment of 1 day
      day1 = timedelta(days=1)
      # function to check the weekday of a date
      weekday_is = lambda n: (lambda d, n=n: d.isoweekday() == n)
      
      # answer the questions
      def results(y, m):
        # days in the month
        ds = first(repeat(inc(day1), date(y, m, 1)), count=(lambda d, m=m: d.month == m))
        # 1. number of days in the month
        r1 = len(ds)
        # 2. number of Mondays
        r2 = icount(ds, weekday_is(1))
        # 3. number of prime days
        pds = list(d for d in ds if d.day in primes)
        r3 = len(pds)
        # 4. number of prime Saturdays
        r4 = icount(pds, weekday_is(6))
        # 5. number of letters in the month name
        r5 = len(ds[0].strftime('%B'))
        return (r1, r2, r3, r4, r5)
      
      # generate result values going back in time
      def generate(y, m):
        prev_month = unpack(lambda y, m: (y, m - 1) if m > 1 else (y - 1, 12))
        for (y, m) in repeat(prev_month, (y, m)):
          if y < 1753: break
          rs = results(y, m)
          t = sum(rs)
          yield Record(y=y, m=m, rs=rs, t=t, tprime=(t in primes))
      
      # consider adjacent months for (next-day, birthday)
      for (d1, d2) in tuples(generate(2024, 8), 2):
        # both totals are prime and no answers are the same
        if d1.tprime and d2.tprime and not any(x == y for (x, y) in zip(d1.rs, d2.rs)):
          # output solution
          nd = date(d1.y, d1.m, 1)
          bd = nd - day1
          printf("birthday = {bd} ({dow}) {d2.rs}; next day = {nd} {d1.rs}", dow=bd.strftime('%A'))
          break  # only need the most recent solution
      

      Solution: The first time the questions were asked was on a Monday in February.

      Actually on Monday, 29th February 2016.

      The answers to the questions are: (29, 5, 10, 1, 8) giving a total of 53.

      The next day is Tuesday, 1st March 2016.

      And the answers to the questions are: (31, 4, 11, 2, 5) also giving a total of 53.

      If we go further back the dates: Friday, 29th February 2008 and Saturday, 1st March 2008 also work.

      And in fact all viable dates are Monday/Friday 29th February, and Tuesday/Saturday 1st March. So there are two possible answers to the puzzle.


      The published solution is: “February, Monday or Friday (apologies for the multiple answers)”.

      Like

      • Jim Randell's avatar

        Jim Randell 10:27 am on 25 August 2024 Permalink | Reply

        > [Frits suggests that solutions earlier than the most recent give the same answer]

        @Frits: Are you sure?

        Like

      • Jim Randell's avatar

        Jim Randell 7:26 am on 26 August 2024 Permalink | Reply

        I interpreted the condition “no answer was the same as for the day before” to mean that each answer given on the second day was different from the answer given to the same question on the previous day (and I think this is the most reasonable interpretation).

        However, if we take this condition to mean that there were no values given as answers on the second day that had also been given as answers on the first day, then we do find a unique solution to the puzzle.

        Here is my program adapted for this interpretation. (The condition at line 38 is changed).

        from datetime import (date, timedelta)
        from enigma import (Record, repeat, inc, first, icount, primes, unpack, tuples, intersect, printf)
        
        # increment of 1 day
        day1 = timedelta(days=1)
        # function to check the weekday of a date
        weekday_is = lambda n: (lambda d, n=n: d.isoweekday() == n)
        
        # answer the questions
        def results(y, m):
          # days in the month
          ds = first(repeat(inc(day1), date(y, m, 1)), count=(lambda d, m=m: d.month == m))
          # 1. number of days in the month
          r1 = len(ds)
          # 2. number of Mondays
          r2 = icount(ds, weekday_is(1))
          # 3. number of prime days
          pds = list(d for d in ds if d.day in primes)
          r3 = len(pds)
          # 4. number of prime Saturdays
          r4 = icount(pds, weekday_is(6))
          # 5. number of letters in the month name
          r5 = len(ds[0].strftime('%B'))
          return (r1, r2, r3, r4, r5)
        
        # generate result values going back in time
        def generate(y, m):
          prev_month = unpack(lambda y, m: (y, m - 1) if m > 1 else (y - 1, 12))
          for (y, m) in repeat(prev_month, (y, m)):
            if y < 1753: break
            rs = results(y, m)
            t = sum(rs)
            yield Record(y=y, m=m, rs=rs, t=t, tprime=(t in primes))
        
        # consider adjacent months for (next-day, birthday)
        for (d1, d2) in tuples(generate(2024, 8), 2):
          # both totals are prime and no answers are the same
          if d1.tprime and d2.tprime and not intersect([d1.rs, d2.rs]):
            # output solution
            nd = date(d1.y, d1.m, 1)
            bd = nd - day1
            printf("birthday = {bd} ({dow}) {d2.rs}; next day = {nd} {d1.rs}", dow=bd.strftime('%A'))
        

        Note: Apparently this is not the interpretation intended by the setter. They just didn’t realise that there were multiple solutions to the puzzle.

        Like

        • Ruud's avatar

          Ruud 5:05 pm on 26 August 2024 Permalink | Reply

          That’s an interesting interpretation that indeed leads to a unique solution.
          In my code just change
          if all(answer1 != answer2 for answer1, answer2 in zip(counts1, counts2)):
          into
          if set(counts1) & set(counts2) == set():
          to get the unique result.

          Like

      • Frits's avatar

        Frits 12:02 pm on 28 August 2024 Permalink | Reply

        @Jim, please add a comment to explain the hardcoded 1753 value

        Like

    • Ruud's avatar

      Ruud 1:13 pm on 25 August 2024 Permalink | Reply

      It is obvious that the birthday must be at the end of a month to make the answer to the month name different. So we can just search by year/month. As the grandchild still has a living grandfather, I assume that the grandchild must be born after 1939. So I just check for all years between 1940 and 2024 and all months.

      It turns out that there are 6 possible solutions in this timeframe. And the month is unique, but the day of the week is ambiguous (there are two possibilities).

      import calendar
      
      
      def is_prime(n):
          if n < 2:
              return False
          if n == 2:
              return True
          if not n & 1:
              return False
      
          for x in range(3, int(n**0.5) + 1, 2):
              if n % x == 0:
                  return False
          return True
      
      
      def counts(year, month):
          number_of_days = calendar.monthrange(year, month)[1]
          number_of_mondays = 0
          number_of_prime_days = 0
          number_of_prime_saturdays = 0
          weekday = calendar.weekday(year, month, 1)
          for day in range(1, number_of_days + 1):
              number_of_mondays += weekday == 0
              number_of_prime_days += is_prime(day)
              number_of_prime_saturdays += weekday == 5 and is_prime(day)
              weekday = (weekday + 1) % 7
          number_of_letters = len(calendar.month_name[month])
          return [number_of_days, number_of_mondays, number_of_prime_days, number_of_prime_saturdays, number_of_letters]
      
      
      for year in range(2024, 1940, -1):
          for month in range(1, 13):
              counts1 = counts(year, month)
              if is_prime(sum(counts1)):
                  next_month = (month % 12) + 1
                  next_year = year + (month == 12)
                  counts2 = counts(next_year, next_month)
                  if is_prime(sum(counts2)):
                      if all(answer1 != answer2 for answer1, answer2 in zip(counts1, counts2)):
                          day = calendar.monthrange(year, month)[1]
                          print(f"{calendar.month_name[month]:10} {calendar.day_name[calendar.weekday(year,month,day)]} ({year:4}-{month:02}-{day:02})")
      

      Like

  • Unknown's avatar

    Jim Randell 10:18 am on 22 August 2024 Permalink | Reply
    Tags: by: L Poulter   

    Brain-Teaser 777: Feeler gauges 

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

    I have half-a-dozen feeler gauges on a ring like keys on a key ring. They are attached in a certain order and by selecting a single gauge or combinations of adjacent gauges it is possible to measure from 1 thou to 31 thous of an inch in steps of 1 thou.

    If I remove two adjacent gauges, replace them with a single gauge and rearrange the five on the ring I can now measure from 1 thou to 21 thous in steps of 1 thou with these five gauges by again selecting a single gauge or combinations of adjacent gauges.

    What are the thicknesses of the gauges and the order of arrangement on the ring in each case? (Start with gauge of unit thickness and then its thinner neighbour for each of the sets).

    [teaser777]

     
    • Jim Randell's avatar

      Jim Randell 10:20 am on 22 August 2024 Permalink | Reply

      This is another puzzle involving magic circles (see: Teaser 1986Enigma 985Puzzle #171, Teaser: Circular Tour).

      This Python program uses the routines for generating magic circles of a specified size that I’ve previously developed for the other puzzles.

      It runs in 72ms. (Internal runtime is 4.2ms).

      Run: [ @replit ]

      from magic_circles import magic_circle
      from enigma import (cproduct, printf)
      
      # make magic circles of size 5 and 6
      (m5s, m6s) = (list(magic_circle(n)) for n in (5, 6))
      
      # choose the circles
      for (m5, m6) in cproduct([m5s, m6s]):
      
        # find the difference between the circles
        ds = set(m6).difference(m5)
        # there should be 2 adjacent items
        if not (len(ds) == 2): continue
        (d1, d2) = (m6.index(d) for d in ds)
        if not ((d1 - d2) % 6 in {1, 5}): continue
      
        # output solution
        printf("6 set = {m6}; 5 set = {m5}")
      

      Solution: The 6-set is: (1, 3, 2, 7, 8, 10). The 5-set is: (1, 3, 10, 2, 5).


      There is only one magic circle of size 5:

      (1, 3, 10, 2, 5)

      There are 5 magic circles of size 6:

      (1, 3, 6, 2, 5, 14) [*]
      (1, 3, 2, 7, 8, 10) [*]
      (1, 2, 5, 4, 6, 13)
      (1, 7, 3, 2, 4, 14)
      (1, 2, 7, 4, 12, 5)

      Only the ones marked [*] have 4 values in common with the size 5 magic circle, and only the second one has the two values to be removed in adjacent positions.

      Like

      • Frits's avatar

        Frits 10:28 am on 23 August 2024 Permalink | Reply

        @Jim, do you assume that all the gauges are of different widths? If not then the “2 adjacent items” code doesn’t seem to be accurate.

        Like

        • Jim Randell's avatar

          Jim Randell 10:39 am on 23 August 2024 Permalink | Reply

          @Frits: With k gauges we can use them all together (1 way) or we can start with any of the k gauges and use between 1 and k − 1 of the gauges (going clockwise say).

          This gives a total of:

          n(k) = 1 + k(k − 1) = k^2 − k + 1

          possible selections.

          For k = 6 we get n(6) = 31 selections.

          So if we can measure all values between 1 and 31 all the selections must give different total values, in particular all the single gauges must give different values, and so they must all be different.

          Similarly for k = 5 we get n(5) = 21 selections.

          Like

    • Frits's avatar

      Frits 4:53 pm on 22 August 2024 Permalink | Reply

      I discovered I already had some code stored on my PC for this puzzle.

      Arthur Vause has made a blog entry on this Brain Teaser:

      [https://arthurvause.blogspot.com/2014/06/feeler-gauges-and-magic-circles.html]

      Like

  • Unknown's avatar

    Jim Randell 11:18 am on 20 August 2024 Permalink | Reply
    Tags:   

    Brain Teaser: Circular tour 

    From Sunday Times Brain Teasers 1974 [link]

    Arley, Barley, Carley, Darley, Earley and Farley are six villages connected, in that order, by a circular bus service. A passenger is allowed to board at any village and alight at any other or complete the whole circuit. The distances from any village to any other village on the route are all different and all an exact number of miles, consisting of every possible whole number from 1 mile up to the distance for the whole circuit.

    Arley to Barley is 1 mile. The distance from Farley to Arley is greater than that from Barley to Carley but less than that from Earley to Farley.

    What is the distance from Earley to Farley?

    This puzzle is taken from the book Sunday Times Brain Teasers (1974), but it is not a puzzle that originally appeared in The Sunday Times.

    [teaser-book-1974-p95]

     
    • Jim Randell's avatar

      Jim Randell 11:20 am on 20 August 2024 Permalink | Reply

      We have encountered puzzles involving magic circles before (see: Teaser 1986, Enigma 985, Puzzle #171), and developed tools for generating them

      This Python program considers magic circles of size 6, and then looks for ones that meet the specified requirements.

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

      Run: [ @replit ]

      from magic_circles import magic_circle
      from enigma import printf
      
      # look for a size 6 magic circle (including reflections)
      for ds in magic_circle(6, refl=1):
        # distance AB = 1
        assert ds[0] == 1
        # distance EF > distance FA > distance BC
        if not (ds[4] > ds[5] > ds[1]): continue
        # output solution
        printf("distance EF = {ds[4]} [ds = {ds}]")
      

      Solution: The distance from Earley to Farley is 12 miles.

      And we have the following distances around the circle:

      A→B = 1
      B→C = 2
      C→D = 7
      D→E = 4
      E→F = 12
      F→A = 5

      Like

      • Ruud's avatar

        Ruud 2:09 pm on 21 August 2024 Permalink | Reply

        A bit verbose and certainly very brute force:

        import itertools
        
        ab = 1
        for bc, cd, de, ef, fa in itertools.permutations(range(2, 20), 5):
            ac = ab + bc
            ad = ac + cd
            ae = ad + de
            af = ae + ef
            bd = bc + cd
            be = bd + de
            bf = be + ef
            ba = bf + fa
            ce = cd + de
            cf = ce + ef
            ca = cf + fa
            cb = ca + ab
            df = de + ef
            da = df + fa
            db = da + ab
            dc = db + bc
            ea = ef + fa
            eb = ea + ab
            ec = eb + bc
            ed = ec + cd
            fb = fa + ab
            fc = fb + bc
            fd = fc + cd
            fe = fd + de
        
            if ef > fa > bc and af+fa == 31:
                if {ab, ac, ad, ae, af, bc, bd, be, bf, ba, cd, ce, cf, ca, cb, de, df, da, db, dc, ef, ea, eb, ec, ed, fa, fb, fc, fd, fe} == set(range(1, 31)):
                    print(ab, ac, ad, ae, af, bc, bd, be, bf, ba, cd, ce, cf, ca, cb, de, df, da, db, dc, ef, ea, eb, ec, ed, fa, fb, fc, fd, fe)
                    print(ef)
        

        Like

    • Lise Andreasen's avatar

      Lise Andreasen 10:27 pm on 20 August 2024 Permalink | Reply

      So… The bus travels 31 miles on 1 circuit. And there’s also 2 villages, 31 miles apart on the circuit. Is this the distance from a village to itself?

      Like

      • Jim Randell's avatar

        Jim Randell 8:14 am on 21 August 2024 Permalink | Reply

        That’s right. A complete circuit is 31 miles, but we can also travel all the distances between 1 and 30 miles.

        A→B = 1; B→A = 30
        B→C = 2; C→B = 29
        A→C = 3; C→A = 28
        D→E = 4; E→D = 27
        F→A = 5; A→F = 26
        F→B = 6; B→F = 25
        C→D = 7; D→C = 24
        F→C = 8; C→F = 23
        B→D = 9; D→B = 22
        A→D = 10; D→A = 21
        C→E = 11; E→C = 20
        E→F = 12; F→E = 19
        B→E = 13; E→B = 18
        A→E = 14; E→A = 17
        F→D = 15; D→F = 16

        Like

        • Lise Andreasen's avatar

          Lise Andreasen 6:29 pm on 21 August 2024 Permalink | Reply

          Just an odd way to describe the 31 miles “distance”.

          “The distances from any village to any other village on the route are all different and all an exact number of miles, consisting of every possible whole number from 1 mile up to the distance for the whole circuit.”

          Like

    • GeoffR's avatar

      GeoffR 9:48 am on 21 August 2024 Permalink | Reply

      There are 6 single trips between villages and 6 trips for each of 2,3,4 and 5 bus stops between villages e.g. AB, BC, CD, DE, EF, FA for single stops between villages. There is only 1 circular bus trip visiting all 6 villages i.e. AB + BC + CD + DE + EF + FA.
      In total, therefore, there are 5 X 6 + 1 = 31 total bus trips.
      This MiniZinc solution enumerates all possible bus trips.

      % A Solution in MiniZinc
      include "globals.mzn";
       
      % Villages are A,B,C,D,E,F
      
      % Assumed upper bounds of six distances between villages
      var 1..15:AB; var 1..15:BC; var 1..15:CD; var 1..15:DE; var 1..15:EF; var 1..15:FA;
      
      constraint all_different ([AB, BC, CD, DE, EF, FA]);
      
      constraint FA > BC /\ FA < EF;
      constraint AB == 1; 
      
      % There are 31 possible distances between villages, as shown below:
      var set of int: soln_nums == {AB, BC, CD, DE, EF, FA,  % 1 stop
      AB+BC, BC+CD, CD+DE, DE+EF, EF+FA, FA+AB,              % 2 stops
      AB+BC+CD, BC+CD+DE, CD+DE+EF, DE+EF+FA, EF+FA+AB, FA+AB+BC,  % 3 stops
      AB+BC+CD+DE, BC+CD+DE+EF, CD+DE+EF+FA, DE+EF+FA+AB, EF+FA+AB+BC, FA+AB+BC+CD, % 4 stops
      AB+BC+CD+DE+EF, BC+CD+DE+EF+FA, CD+DE+EF+FA+AB, DE+EF+FA+AB+BC, % 5 stops
      EF+FA+AB+BC+CD, FA+AB+BC+CD+DE, 
      AB+BC+CD+DE+EF+FA};  % 6 stops
      
      set of int: req_nums = 1..31;
       
      constraint soln_nums == req_nums;
      
      constraint card(soln_nums) == AB + BC + CD + DE + EF + FA;
      
      solve satisfy;
      
      output["[AB, BC, CD, DE, EF, FA] = " ++ show( [AB, BC, CD, DE, EF, FA] )
      ++"\n" ++ "Distance from Earley to Farley =  "  ++ show(EF) ++ " miles."];
      
      % [AB, BC, CD, DE, EF, FA] = [1, 2, 7, 4, 12, 5]
      % Distance from Earley to Farley =  12 miles.
      % ----------
      % ==========
      
      
      

      Like

    • Ruud's avatar

      Ruud 11:24 am on 22 August 2024 Permalink | Reply

      A bit less verbose:

      import itertools
      
      succ = dict(zip("abcdef", "bcdefa"))
      
      for x5 in itertools.permutations(range(2, 20), 5):
          dist = dict(zip("ab bc cd de ef fa".split(), [1, *x5]))
          for d in "abcdef":
              d1 = succ[d]
              for _ in range(4):
                  dist[d + succ[d1]] = dist[d + d1] + dist[d1 + succ[d1]]
                  d1 = succ[d1]
          if dist["ef"] > dist["fa"] > dist["ac"] and set(dist.values()) == set(range(1, 31)):
              print(dist["ef"])
      

      Like

    • Frits's avatar

      Frits 4:10 pm on 22 August 2024 Permalink | Reply

      Using my Puzzle #171 code but now using decomposition.

           
      from itertools import permutations
      
      # for a list with n numbers check if the set of sums of 1...n-1 adjacent items
      # (also circular) is complete (with n.(n-1) different sums)
      def allOccurOnce(s, ln):                                         
        sms = set(s)
        for i in range(ln):
          for j in range(2, ln):
            if (sm := sum((s * 2)[i:i + j])) in sms: 
              return False
            sms.add(sm)
        return True  
      
      # decompose <t> into <k> increasing numbers from <ns>
      def decompose(t, k, ns, s=[]):
        if k == 1:
          if t in ns:
            yield s + [t]
        else:
          for i, n in enumerate(ns):
            # make sure we don't overshoot
            if 2 * t < (2 * n + k - 1) * k: break
            yield from decompose(t - n, k - 1, ns[i + 1:], s + [n])
      
      N = 6
      T = N**2 - N + 1
      H = int(T // 2)
      
      # for a magic circle with N numbers and total sum T
      # the highest possible circle number is T - N(N-1)/2 which equals H + 1
      
      # exclude mandatory numbers 1 and 2 from the decomposition
      for dc in decompose(T - 3, N - 2, range(3, H + 2)):
        # weave in the number 2
        for p in permutations([2] + dc):
          p1 = (1, ) + p
          
          # distance EF > distance FA > distance BC
          if not (p1[4] > p1[5] > p1[1]): continue
          # can we make N.(N - 1) different sums?
          if not allOccurOnce(p1, N): continue
          print(f"answer: {p1[4]} miles")
      

      Like

  • Unknown's avatar

    Jim Randell 5:35 am on 18 August 2024 Permalink | Reply
    Tags:   

    Teaser 3230: Polytunnel 

    From The Sunday Times, 18th August 2024 [link] [link]

    I have extended my market garden by the addition of a polytunnel. The polyethylene cover is supported at intervals by identical sets of three vertical pillars supporting metal arcs, of negligible thickness, resting on the level ground on both sides. In each set, the highest pillar is in the middle of the cross-section, at the highest point of the tunnel. The other two pillars are of equal height, being three quarters of the height of the central pillar. These shorter pillars are positioned on each side, 2/11 of the ground-level width of the tunnel from each edge.

    Each metal arc is part of a circle (less than a semicircle), and the highest point is exactly 3m above the ground.

    What is the ground-level width of the polytunnel in cm?

    [teaser3230]

     
    • Jim Randell's avatar

      Jim Randell 5:36 am on 18 August 2024 Permalink | Reply

      By considering two right-angled triangles we can derive a linear equation for the depth of the centre of the arc below ground level (x), from which the width of the polytunnel (2w) can be determined.

      The triangles are indicated in the following diagram:

      This Python program (appropriately enough) uses the [[ Polynomial() ]] class from the enigma.py library to perform the calculations.

      It runs in 76ms. (Internal runtime is 139µs).

      Run: [ @replit ]

      from enigma import (Rational, Polynomial, sq, sqrt, printf)
      
      Q = Rational()
      
      # suppose the polytunnel has ground-level semi-width w
      # and the centre of the circle is a distance x below ground
      # we have:
      #
      #  r = x + 300
      #  r^2 = w^2 + x^2
      #  r^2 = (7w/11)^2 + (225 + x)^2
      
      fx = Polynomial('x')  # depth of origin
      fr = fx + 300  # radius of arc
      
      f1 = sq(fr) - sq(fx)  # = w^2
      f2 = sq(fr) - sq(fx + 225)  # = (7w/11)^2
      
      f = sq(Q(7, 11)) * f1 - f2  # equate values of w^2
      
      # solve f(x) = 0 for positive real x
      for x in f.roots(domain='F', include='0+'):
        # calculate width
        W = sqrt(f1(x)) * 2
        printf("polytunnel width = {W:g} cm [x = {x:g}]")
      

      Solution: The width of the polytunnel at ground level is 660 cm.

      The polynomial to determine the depth of the centre of the circular arc simplifies to:

      f(x) = 2x − 63

      From which we easily find the depth of the centre and the radius of the circle:

      x = 31.5
      r = 331.5

      And from these we calculate the semi-width of the polytunnel:

      w^2 = r^2 − x^2 = (r + x)(r − x)
      w^2 = 363 × 300 = 108900
      ⇒ w = 330

      So the total width of the polytunnel is 660 cm.

      Like

    • Frits's avatar

      Frits 11:24 am on 18 August 2024 Permalink | Reply

      I made my narrowing down routine from scratch.
      Of course there are more efficient ways to do this (I don’t know them by heart).

      from sys import float_info
      eps = float_info.epsilon
      
      # r = x + 300    # the centre of the circle is a distance x below ground
      # 49.w^2 - 117600.x - 17_640_000 = 0
      # 49.w^2 -  72600.x - 19_057_500 = 0
      
      f1 = lambda x: 17_640_000 + 117_600 * x
      f2 = lambda x: 19_057_500 +  72_600 * x
      
      mode = ""
      x = 100         # choose an arbitrarily starting value
      delta = 5       # increment/decrement value for variable x
      
      # find a value for "x" where both f1(x) and f2(x) are (almost) the same
      while True:
        v1, v2 = f1(x), f2(x)
        # do we have an solution where both values are (almost) the same?
        if abs(v2 - v1) <= eps:
          w = (2_400 * x + 360_000)**.5
          print(f"answer:  ground-level width = {round(w, 2)} cm")
          break
        
        if v1 < v2:
          if mode == "more": 
            delta /= 2
          x += delta
          mode = "less"
        else:
          if mode == "less": 
            delta /= 2
          x -= delta
          mode = "more"     
      

      Like

      • Frits's avatar

        Frits 11:34 am on 18 August 2024 Permalink | Reply

        The program was only made if you don’t want to analyse the problem till a solution is found.

        Like

    • GeoffR's avatar

      GeoffR 6:23 pm on 18 August 2024 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % X = half tunnel width, Y =  depth below ground, R = circle radius
      % All dustances in mm.
      
      % Assumed UB's for variables
      var 1..4500:R;  var 1..4000:X; var 1..1500:Y; 
      
      constraint R == 3000 + Y;  
      
      constraint X * X  + Y * Y == R * R;
       
      % (2250 + Y)^2 + (7/11 * X)^2 = R * R
      constraint 121 * R * R == 121 * ((2250 + Y) * (2250 + Y)) + (49 * X * X);
      
      solve satisfy;
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 10:46 am on 15 August 2024 Permalink | Reply
    Tags:   

    Teaser 2623: Latecomer 

    From The Sunday Times, 30th December 2012 [link] [link]

    Imogen is having a New Year party tomorrow night and she has invited Madeline, hoping not to have a repeat of last year’s episode which completely spoilt the celebrations. Last New Year’s Eve Madeline had been due at a certain whole number of minutes past an hour but she was late, the number of minutes late being that same aforementioned “certain number of minutes” but with the digits in the reverse order. Madeline pointed out that at least the angle between the hands of the clock at the moment of her arrival was the same as it would have been when she was due.

    At what time was she due to arrive?

    [teaser2623]

     
    • Jim Randell's avatar

      Jim Randell 10:46 am on 15 August 2024 Permalink | Reply

      Madeline was expected to arrive at a time of xy minutes past a specified hour, but she was late, and arrived yx minutes later than her expected time. So yx (and xy) cannot be 00 (as then she would not be late).

      This Python program finds both possible solutions to the puzzle.

      It runs in 74ms. (Internal runtime is 3.6ms).

      Run: [ @replit ]

      from enigma import (Rational, irange, cproduct, nrev, printf)
      
      Q = Rational()
      
      # calculate angle between hands at time h:m
      # angles are between 0 (coincident) and 1 (opposite)
      def angle(h, m):
        (x, m) = divmod(m, 60)
        h = (h + x) % 12
        ah = Q(h + Q(m, 60), 6)
        am = Q(m, 30)
        a = abs(ah - am)
        return (2 - a if a > 1 else a)
      
      # consider possible scheduled arrival times
      for (h, m) in cproduct([irange(0, 11), irange(1, 59)]):
        a1 = angle(h, m)
        # calculate angle at actual arrival time
        a2 = angle(h, m + nrev(m, 2))
        # are angles the same?
        if a1 == a2:
          # output solution
          printf("expected arrival = {h:02d}:{m:02d} [angle = {a:.2f} min]", a=float(a1 * 30))
      

      There are two possible answers:

      Expected time = 11:43; Actual time = 11:43 + 34 minutes = 12:17
      Expected time = 5:43; Actual time = 5:43 + 34 minutes = 6:17

      Both of which are illustrated below, with the same shape indicating the identical angles between the hands:

      As the party in question is a New Years Eve party, presumably the setter intends us to choose the solution where Madeline was expected to arrive before midnight, but actually arrived after midnight (although this could easily have been specified in the problem text).

      Solution: Madeline was due to arrive at 11:43 pm.

      Like

  • Unknown's avatar

    Jim Randell 8:21 am on 13 August 2024 Permalink | Reply
    Tags:   

    Teaser 2586: Powerful dice 

    From The Sunday Times, 15th April 2012 [link] [link]

    George and Martha threw a die, noted the number of spots on the uppermost face, and entered that number in one of the boxes of a 3-by-3 grid of nine squares. They repeated the exercise eight more times resulting in a digit in each box.

    Then George looked at the three 3-digit numbers read across the rows and commented that each was a square or a cube. Martha looked at the three 3-digit numbers read down the columns and said the same was true for her numbers. Furthermore, their two sets of three numbers had only one in common.

    What (in increasing order) were the five different 3-digit numbers?

    [teaser2586]

     
    • Jim Randell's avatar

      Jim Randell 8:22 am on 13 August 2024 Permalink | Reply

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

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

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      #  A B C
      #  D E F
      #  G H I
      
      --digits="1-6"
      --distinct=""
      
      --code="check = cached(lambda n: is_square(n) or is_cube(n))"
      
      # check rows and columns
      "check(ABC)"
      "check(DEF)"
      "check(GHI)"
      "check(ADG)"
      "check(BEH)"
      "check(CFI)"
      
      # there is exactly one number shared between the rows and columns
      "len(intersect([{ABC, DEF, GHI}, {ADG, BEH, CFI}])) = 1"
      
      # and there are five different numbers in total
      "len({ABC, DEF, GHI, ADG, BEH, CFI}) = 5"
      
      --answer="call(ordered, {ABC, DEF, GHI, ADG, BEH, CFI})"
      --template="rows = [ ABC DEF GHI ]; cols = [ ADG BEH CFI ]"
      --solution=""
      --verbose="1-H"
      

      Solution: The numbers entered in the box were: 121, 125, 216, 256, 512.

      We have:

      121 = 11^2
      125 = 5^3
      216 = 6^3
      256 = 16^2
      512 = 8^3

      512 appears as both a row and a column.

      The most likely scenario is:

      Then George’s rows would consist of both squares and cubes, and Martha could say the same about her columns even though they are actually all cubes.

      Swapping the rows and columns yields a second viable layout, but it seems unlikely George would note that his each of his rows was a square or a cube, when they are in fact all cubes.

      Like

      • ruudvanderham's avatar

        ruudvanderham 11:50 am on 13 August 2024 Permalink | Reply

        from istr import istr
        istr.repr_mode('int')
        squares=[i*i for i in range(10,32)]
        cubes=[i*i*i for i in range (5,10)]
        squares_cubes=istr(squares+cubes)
        
        solutions=set()
        for abc in squares_cubes:
            for def_ in squares_cubes:
                for ghi in squares_cubes:
                    horizontals={abc,def_,ghi}
                    verticals={abc[i]|def_[i]|ghi[i] for i in range(3)}
                    if all(vertical in squares_cubes for vertical in verticals):
                        horizontals_verticals= horizontals | verticals
                        if len(horizontals_verticals)==5:
                            solutions.add(tuple(sorted(horizontals_verticals)))
        print(solutions)
        

        Like

        • Ruud's avatar

          Ruud 7:07 pm on 13 August 2024 Permalink | Reply

          I forgot to test whether all digits were between 1 and 6.
          Here’s an improved version (same output):

          from istr import istr
          
          istr.repr_mode("int")
          squares = [i * i for i in range(10, 32)]
          cubes = [i * i * i for i in range(5, 10)]
          squares_cubes = [i for i in istr(squares + cubes) if all(j in range(1, 7) for j in i)]
          
          solutions = set()
          for abc in squares_cubes:
              for def_ in squares_cubes:
                  for ghi in squares_cubes:
                      horizontals = {abc, def_, ghi}
                      verticals = {abc[i] | def_[i] | ghi[i] for i in range(3)}
                      if all(vertical in squares_cubes for vertical in verticals):
                          horizontals_verticals = horizontals | verticals
                          if len(horizontals_verticals) == 5:
                              solutions.add(tuple(sorted(horizontals_verticals)))
          print(solutions)
          

          Like

          • Jim Randell's avatar

            Jim Randell 5:54 pm on 14 August 2024 Permalink | Reply

            @Ruud: I think you also need to add a test for “their two sets of three numbers had only one in common”. Your code would allow a repeated row or a repeated column.

            Like

            • Ruud's avatar

              Ruud 7:07 pm on 14 August 2024 Permalink | Reply

              @Jim
              Thanks for pointing this out. You are right.
              My updated code:

              from istr import istr
              
              istr.repr_mode("int")
              squares = [i * i for i in range(10, 32)]
              cubes = [i * i * i for i in range(5, 10)]
              squares_cubes = [i for i in istr(squares + cubes) if all(j in range(1,7) for j in i)]
              
              solutions = set()
              for abc in squares_cubes:
                  for def_ in squares_cubes:
                      for ghi in squares_cubes:
                          horizontals = {abc, def_, ghi}
                          verticals = {abc[i] | def_[i] | ghi[i] for i in range(3)}
                          if all(vertical in squares_cubes for vertical in verticals):
                              if len(horizontals & verticals) == 1:
                                  solutions.add(tuple(sorted(horizontals | verticals)))
              print(solutions)
              

              Like

  • Unknown's avatar

    Jim Randell 7:04 am on 11 August 2024 Permalink | Reply
    Tags:   

    Teaser 3229: Fishy scales 

    From The Sunday Times, 11th August 2024 [link] [link]

    For loads under 99.5 kg, my scales have three 7-segment digits. The left and centre digits show the weight; the right digit shows “r” for rounded to whole kg or “E” for exact kg. The examples show 69 kg rounded, and 0 kg exactly. Overload displays “888”.

    The scales are accurate, but one of the segments in one of the digits is faulty and is always illuminated. For example, two fish boxes were recently loaded together and “68E” appeared. A fish slid off and “62E” appeared. A third box was added and “99E” appeared. The fallen fish was then put back in its box. Curiously, the display didn’t change. Then the first two boxes were removed. A new reading appeared, with rightmost digit “E”.

    Find the reading displayed for the third box alone.

    [teaser3229]

     
    • Jim Randell's avatar

      Jim Randell 7:21 am on 11 August 2024 Permalink | Reply

      The faulty segment must be lit in all the readings given, and the first likely scenario I tried gave a viable solution, so the puzzle was solved manually in a few minutes. However the following Python program performs an exhaustive exploration of the problem space.

      The final digit of the display reads “E”, “r” or “8”, and it is not possible for a single incorrect segment to change one of these displays to a different viable digit. So all the readings must end in “E”, and so we are dealing with exact integer weights, less than 100 kg. This is enough to explore the problem space without requiring any additional analysis.

      The following Python program runs in 72ms. (Internal runtime is 4.1ms).

      Run: [ @replit ]

      from enigma import (irange, intersect, append, join, printf)
      
      # segments on a 7-segment display
      segs = {
        0: {0, 1, 2, 4, 5, 6},
        1: {2, 5},
        2: {0, 2, 3, 4, 6},
        3: {0, 2, 3, 5, 6},
        4: {1, 2, 3, 5},
        5: {0, 1, 3, 5, 6},
        6: {0, 1, 3, 4, 5, 6},
        7: {0, 2, 5},
        8: {0, 1, 2, 3, 4, 5, 6},
        9: {0, 1, 2, 3, 5, 6},
        'E': {0, 1, 3, 4, 6},
        'r': {3, 4},
      }
      
      # segment display for integer weight <w>, with digit <d> segment <s> always lit
      def display(w, d=None, s=None):
        if w > 99: return [segs[8]] * 3
        ds = list(segs[k] for k in divmod(w, 10))
        ds.append(segs['E'])
        # adjust the faulty segment
        if d is not None:
          ds[d] = append(ds[d], s)
        return ds
      
      # output a display (? for a mangled digit)
      def output(ds):
        r = dict((frozenset(v), k) for (k, v) in segs.items())  # reverse the segment map
        return join(r.get(frozenset(x), '?') for x in ds)
      
      # the given displays
      (d68E, d62E, d99E) = (display(x) for x in (68, 62, 99))
      
      # choose the faulty segment
      for (d, xs) in enumerate(zip(d68E, d62E, d99E)):
        for s in intersect(xs):
          # consider the weight of box 1 and 2 (including the fish)
          for b12 in irange(2, 98):
            # display for (box 1 + box 2) is "68E"
            if display(b12, d, s) != d68E: continue
      
            # consider the weight of the fish
            for f in irange(1, b12 - 1):
              # display for (box 1 + box 2 - fish) is "62E"
              if display(b12 - f, d, s) != d62E: continue
      
              # consider the weight of box 3
              for b3 in irange(1, 99 - b12):
                # display of (box 1 + box 2 - fish + box 3) is "99E"
                if display(b12 - f + b3, d, s) != d99E: continue
                # but display does not change if the fish is returned to its box
                if display(b12 + b3, d, s) != d99E: continue
      
                # final display is just b3
                fsegs = display(b3, d, s)
      
                # output solution
                printf("{disp} = {fsegs} [d={d} s={s}; b12={b12} f={f} b3={b3}]", disp=output(fsegs))
      

      Solution: The reading for the third box alone was: “33E”.

      The faulty segment is segment 2 (top right) of the second (middle) digit of the display.

      The first two boxes together (including the fish) weigh 66 kg. The display (incorrectly) reads “68E”.

      The fish weighs 4 kg, so when it is removed the total weight is 62 kg. The display (correctly) reads “62E”.

      The third box weighs 33 kg, so when this is added the total weight is now 95 kg. The display (incorrectly) reads “99E”.

      The fish is then returned to its box, so the total weight is now 99 kg. The display (correctly) reads “99E” (again).

      The first 2 boxes (including the fish) are now removed, leaving only the third box. The display (correctly) reads “33E”.

      Like

  • Unknown's avatar

    Jim Randell 9:50 am on 7 August 2024 Permalink | Reply
    Tags:   

    Teaser 2587: Hobson’s choice 

    From The Sunday Times, 22nd April 2012 [link] [link]

    In the diagram the letters represent the numbers 1 to 16 in some order. They form a magic square, where the sum of each row, each column and each main diagonal is the same. The letters of the word “CHOICE” and some others (including all the letters not used in the magic square) have a value equal to their position in the alphabet (C=3, H=8, etc).

    What is the value of H+O+B+S+O+N?

    [teaser2587]

     
    • Jim Randell's avatar

      Jim Randell 9:52 am on 7 August 2024 Permalink | Reply

      See also: Enigma 1690.

      The 16 numbers in the grid sum to tri(16) = 136, so each row and column must sum to 1/4 of this = 34.

      We can use the [[ SubstitutedExpression ]] solver from the enigma.py library to find possible assignments.

      The following run file executes in 85ms. (Internal runtime of the generated code is 145µs).

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      #  A B C D
      #  E F G H
      #  I J K L
      #  M N O P
      
      --base=27
      --digits="1-16"
      
      # rows
      "A + B + C + D == 34"
      "E + F + G + H == 34"
      "I + J + K + L == 34"
      "M + N + O + P == 34"
      # columns
      "A + E + I + M == 34"
      "B + F + J + N == 34"
      "C + G + K + O == 34"
      "D + H + L + P == 34"
      # diagonals
      "A + F + K + P == 34"
      "D + G + J + M == 34"
      
      # given values
      --assign="C,3"
      --assign="E,5"
      --assign="H,8"
      --assign="I,9"
      --assign="O,15"
      --assign="S,19" # we only need S (from Q..Z)
      
      # required answer
      --answer="H + O + B + S + O + N"
      
      --template=""
      

      Solution: H + O + B + S + O + N = 73.

      The completed grid is:


      The Magic Square is a variation of the “Dürer” Magic Square seen in “Melencolia I”. [ @wikipedia ]

      If you recognise that the given values (C = 3, E = 5, H = 8, I = 9, O = 15) fit into this square you don’t need to do any more working out, as the square is associative (which means any number and its symmetric opposite add to 17).

      So we can calculate the required result using the given values as:

      H + O + B + S + O + N
      = H + O + (17 − O) + S + O + (17 − C)
      = 8 + 15 + 2 + 19 + 15 + 14
      = 73

      Like

    • ruudvanderham's avatar

      ruudvanderham 2:10 pm on 7 August 2024 Permalink | Reply

      Brute force solution:

      import itertools
      
      C = 3
      E = 5
      H = 8
      I = 9
      O = 15
      S = 19
      for A, B, D, F, G, J, K, L, M, N, P in itertools.permutations((1, 2, 4, 6, 7, 10, 11, 12, 13, 14, 16)):
          ABCD = A + B + C + D
          if E + F + G + H == ABCD:
              if I + J + K + L == ABCD:
                  if M + N + O + P == ABCD:
                      if A + E + I + M == ABCD:
                          if B + F + J + N == ABCD:
                              if C + G + K + O == ABCD:
                                  if D + H + L + P == ABCD:
                                      if A + F + K + P == ABCD:
                                          if D + G + J + M == ABCD:
                                              print(f"{H+O+B+S+O+N=}")
                                              print(f"{A=:2} {B=:2} {C=:2} {D=:2}")
                                              print(f"{E=:2} {F=:2} {G=:2} {H=:2}")
                                              print(f"{I=:2} {J=:2} {K=:2} {L=:2}")
                                              print(f"{M=:2} {N=:2} {O=:2} {P=:2}")
      
      

      Output:

      H+O+B+S+O+N=73
      A=16 B= 2 C= 3 D=13
      E= 5 F=11 G=10 H= 8
      I= 9 J= 7 K= 6 L=12
      M= 4 N=14 O=15 P= 1
      

      Like

    • GeoffR's avatar

      GeoffR 5:41 pm on 7 August 2024 Permalink | Reply

      A 4-stage permutation brings the run- time down to 55 msec using ABCD = 34 , or 177 msec not using ABCD = 34.

      
      from enigma import Timer
      timer = Timer('ST2587', timer='E')
      timer.start()
      
      from itertools import permutations
      #  A B C D
      #  E F G H
      #  I J K L
      #  M N O P
      
      # Given values
      C, E, H = 3, 5, 8
      I, O, S = 9, 15, 19
      
      # Find remaining digits to permute
      digits = set(range(1,17)).difference({3, 5,8,9,15})
      
      # 1st stage permutation
      for p1 in permutations (digits, 3):                       
        A, B, D = p1  # C given
        ABCD = A + B + C + D
        if ABCD != 34:continue
        
        # 2nd stage permutation
        q1 = digits.difference(p1)
        for p2 in permutations(q1, 2):
          F, G = p2  # E and H given
          EFGH = E + F + G + H
          if EFGH != ABCD:continue
          
          # 3rd stage permutation
          q2 = q1.difference(p2)
          for p3 in permutations(q2, 3):
            J, K, L = p3  # I given
            IJKL = I + J + K + L
            if IJKL != ABCD:continue
            
            # 4th stage permutation
            q3 = q2.difference(p3)
            for p4 in permutations(q3, 3):
              M, N, P = p4 # O given
              MNOP = M + N + O + P
              if MNOP != ABCD: continue
              
              # Check column and diagonal sums
              if A + E + I + M != ABCD:continue
              if B + F + J + N != ABCD:continue
              if C + G + K + O != ABCD:continue
              if D + H + L + P != ABCD:continue
              if A + F + K + P != ABCD:continue
              if D + G + J + M != ABCD:continue
                
              print(f"HOBSON = {H + O + B + S + O + N}")
              print(A,B,C,D)
              print(E,F,G,H)
              print(I,J,K,L)
              print(M,N,O,P)
              timer.stop()      
              timer.report()
              # [ST2587] total time: 0.1775740s (177.57ms) - without ABCD = 34
              # [ST2587] total time: 0.0553104s (55.31ms) - with ABCD = 34
      
      # HOBSON = 73
      # 16 2 3 13
      # 5 11 10 8
      # 9 7  6 12
      # 4 14 15 1
      
      
      

      Like

      • ruudvanderham's avatar

        ruudvanderham 6:48 am on 8 August 2024 Permalink | Reply

        Nice solution.
        I guess that if you first try the EFGH permutations, performance might slightly improve because there are only 2 choices there.

        Like

        • ruudvanderham's avatar

          ruudvanderham 6:54 am on 8 August 2024 Permalink | Reply

          Or even faster (maybe): go vertical vertical and first do AEIM, then CGKO (twice 2 choices only).

          Like

        • Frits's avatar

          Frits 10:00 am on 8 August 2024 Permalink | Reply

          Brian did some analysis and discovered that L must be 12.

          [ https://brg.me.uk/?page_id=3378 ]

          Like

          • Jim Randell's avatar

            Jim Randell 11:03 am on 8 August 2024 Permalink | Reply

            @Frits: By using the given values and simplifying the 10 equations we can get:

            B + N = 16

            And we know values for all the other letters in HOBSON, so the result follows directly.

            (Although it is not a constructive solution – it assumes that it is possible to make a viable Magic Square).

            Like

    • GeoffR's avatar

      GeoffR 10:07 am on 8 August 2024 Permalink | Reply

      I got about a 5 ms speed increase trying the EFGH permutation first, but the second suggestion i.e. AEIM, then CGKO did not come out easily – may have another look later.

      Like

    • GeoffR's avatar

      GeoffR 11:57 am on 9 August 2024 Permalink | Reply

      This solution uses the fact that this an associative magic square to find the value of HOBSON only. The full ten constraints for summing rows, columns and diagonals were still needed to find a unique magic square.

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      %   A B C D
      %   E F G H
      %   I J K L
      %   M N O P
      
      var 1..16:A; var 1..16:B; var 1..16:C; var 1..16:D;
      var 1..16:E; var 1..16:F; var 1..16:G; var 1..16:H;
      var 1..16:I; var 1..16:J; var 1..16:K; var 1..16:L;
      var 1..16:M; var 1..16:N; var 1..16:O; var 1..16:P;
      int:S == 19;
      
      constraint all_different([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P]);
      
      % Given values
      constraint C == 3 /\ E == 5 /\ H == 8 /\ I == 9 /\ O == 15;
      
      % LB = 1+2+3+4+5+6 = 21, UB = 19 + 4*16 = 83
      var 21..83: HOBSON == H + O + B + S + O + N;
      
      % Symmetric sum = 4^2 + 1 = 17, for this associative magic square
      % So symmetrically opposite numbers add to 17 
      constraint A + P == 17 /\ B + O == 17 /\ C + N == 17 /\ D + M == 17;
      constraint E + L == 17 /\ F + K == 17 /\ G + J == 17;  % Given H + I = 17
      
       solve satisfy;
       output["HOBSON = " ++ show(HOBSON) ];
      %  HOBSON = 73
      % ----------
      % ==========
      
      

      Like

  • Unknown's avatar

    Jim Randell 6:16 am on 4 August 2024 Permalink | Reply
    Tags:   

    Teaser 3228: Prime tiles 

    From The Sunday Times, 4th August 2024 [link] [link]

    Ann, Beth and Chloe play a game with tiles. The prime numbers from 3 to 41 inclusive are written on 12 tiles, and each player receives 4 tiles. An odd starting number is chosen at random, then each player in turn tries, if possible, to increase the total to a prime number, by adding two of their tiles. For example, if the starting number is 5, Ann could play 11 and 31 to make the total 47, then Beth might be able to play 5 and 7 to make 59 and so on.

    In a game where the starting number was 3, Ann was first, but couldn’t play. Beth and Chloe both took their turns, but again Ann was unable to play.

    In ascending order, which four tiles did Beth and Chloe play?

    [teaser3228]

     
    • Jim Randell's avatar

      Jim Randell 6:32 am on 4 August 2024 Permalink | Reply

      This Python program runs in 68ms. (Internal runtime is 2.8ms).

      Run: [ @replit ]

      from enigma import (primes, subsets, diff, ordered, printf)
      
      # available tiles
      tiles = list(primes.between(3, 41))
      
      # starting total
      t0 = 3
      
      # choose 4 tiles for A
      for As in subsets(tiles, size=4):
        # A is unable to play
        if any(t0 + x + y in primes for (x, y) in subsets(As, size=2)): continue
      
        # B plays two tiles
        for (b1, b2) in subsets(diff(tiles, As), size=2):
          t1 = t0 + b1 + b2
          if t1 not in primes: continue
      
          # C plays 2 tiles
          for (c1, c2) in subsets(diff(tiles, As, (b1, b2)), size=2):
            t2 = t1 + c1 + c2
            if t2 not in primes: continue
      
            # A is unable to play
            if any(t2 + x + y in primes for (x, y) in subsets(As, size=2)): continue
      
            # output solution
            played = ordered(b1, b2, c1, c2)
            printf("played = {played} [A={As}; {t0} -> ({b1}, {b2}) -> {t1} -> ({c1}, {c2}) -> {t2}]")
      

      Solution: The tiles Beth and Chloe played were 7, 23, 31, 37.

      A’s tiles were: 5, 13, 19, 41.

      There are 3 possible games:

      3 → (7, 31) → 41 → (23, 37) → 101
      3 → (7, 37) → 47 → (23, 31) → 101
      3 → (31, 37) → 71 → (7, 23) → 101

      but in all cases the tiles played by B and C are: 7, 23, 31, 37.

      Like

      • Ruud's avatar

        Ruud 10:52 am on 5 August 2024 Permalink | Reply

        Similar to @Frits:

        import itertools
        
        
        def is_prime(n):
            if n < 2:
                return False
            if n == 2:
                return True
            if not n & 1:
                return False
            for x in range(3, int(n**0.5) + 1, 2):
                if n % x == 0:
                    return False
            return True
        
        
        primes = set(n for n in range(3, 42) if is_prime(n))
        
        for a in itertools.combinations(primes, 4):
            bc = primes - set(a)
            total = 3
            if not any(is_prime(total + sum(a2)) for a2 in itertools.combinations(a, 2)):
                for b2 in itertools.combinations(bc, 2):
                    if is_prime(total + sum(b2)):
                        for c2 in itertools.combinations(bc - set(b2), 2):
                            if is_prime(total + sum(b2) + sum(c2)):
                                if not any(is_prime(total + sum(b2) + sum(c2) + sum(a2)) for a2 in itertools.combinations(a, 2)):
                                    print(sorted(b2 + c2))
        

        Like

    • Frits's avatar

      Frits 10:05 am on 4 August 2024 Permalink | Reply

      from itertools import combinations
      
      # determine valid primes up to approx 6 * 41
      P = {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, 240, 2) if all(x % p for p in P)}
      
      sols, t = set(), 3  
      tiles = {p for p in P if 3 <= p <= 41}
      
      # pick four tiles for Ann
      for a4 in combinations(tiles, 4):
        # check if any two of Ann's tiles make a prime (with 3)
        for a2 in combinations(a4, 2):
          if (sum(a2) + t) in P: break
        else: # no break, Ann couldn't play  
          # pick 2 playable tiles for Beth
          for b2 in combinations(tiles.difference(a4), 2):
            if (t_b := (sum(b2) + t)) not in P: continue
            # pick 2 playable tiles for Chloe
            for c2 in combinations(tiles.difference(a4 + b2), 2):
              if (t_c := (sum(c2) + t_b)) not in P: continue
              # check if any two of Ann's tiles can make a prime
              for a2 in combinations(a4, 2):
                if (sum(a2) + t_c) in P: break
              else: # no break, Ann couldn't play  
                sols.add(tuple(sorted(b2 + c2)))
                
      # print the solution(s)          
      for s in sols:
        print(f"answer: {s}")     
      

      Like

    • Frits's avatar

      Frits 12:10 pm on 4 August 2024 Permalink | Reply

      Less efficient.

      from itertools import combinations
      
      # determine valid primes up to approx 6 * 41
      P = {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, 240, 2) if all(x % p for p in P)}
      
      sols, t = set(), 3  
      tiles = [p for p in P if 3 <= p <= 41]
      
      # combinations of 4 tiles that sum to a certain total
      d = {t: [c4 for c4 in combinations(tiles, 4) 
               if sum(c4) == t] for t in range(26, 139, 2)}
               
      # pick four tiles for Ann
      for a4 in combinations(tiles, 4):
        # starting totals where Ann cannot play
        npt = {t for t in range(3, 142, 2) 
               if all((sum(a2) + t) not in P for a2 in combinations(a4, 2))}
        if 3 not in npt: continue
        
        # check non-playing totals (besides total <t>)
        for np in npt:
          if np == t: continue
          # get 4 tiles for Beth and Chloe ...
          for t4 in d[np - t]:
            # ... that differ from Ann's tiles
            if len(set(a4 + t4)) != 8: continue
            
            # can we make a prime with 2 numbers of <t4>
            for b2 in combinations(t4, 2):
              if (t_b := sum(b2) + t) not in P: continue
              # can we make a prime with 2 numbers of <t4>
              c2 = set(t4).difference(b2)
              if (t_c := sum(c2) + t_b) not in P: continue
              sols.add(tuple(sorted(b2 + tuple(c2))))
      
      # print the solution(s)          
      for s in sols:
        print(f"answer: {s}")           
      

      Like

  • Unknown's avatar

    Jim Randell 9:44 am on 1 August 2024 Permalink | Reply
    Tags:   

    Teaser 2584: Truncation 

    From The Sunday Times, 1st April 2012 [link] [link]

    Callum is learning about squares and primes. He told me that he had discovered a four-figure square that becomes a three-figure prime if you delete its last digit. I could not work out his square from this information and he informed me that, if I knew the sum of its digits, then I would be able to work it out. So I then asked whether the square had a repeated digit: his answer enabled me to work out his square.

    What was it?

    [teaser2584]

     
    • Jim Randell's avatar

      Jim Randell 9:44 am on 1 August 2024 Permalink | Reply

      This Python program runs in 81ms. (Internal runtime is 381µs).

      Run: [ @replit ]

      from enigma import (
        powers, is_prime, filter_unique, dsum,
        is_duplicate, singleton, group, printf
      )
      
      # find 4-digit squares, where the first 3 digits form a prime
      sqs = list(n for n in powers(32, 99, 2) if is_prime(n // 10))
      
      # select numbers unique by digit sum
      ns = filter_unique(sqs, f=dsum).unique
      
      # group results by whether there are repeated digits
      g = group(ns, by=is_duplicate)
      
      # look for unique values
      for (k, vs) in g.items():
        n = singleton(vs)
        if n is not None:
          printf("(duplicate = {k}) => n = {n}")
      

      Solution: Callum’s number was: 5476.

      There are 8 candidate squares that can be truncated to a prime, but only 3 have a unique digit sum:

      dsum = 10 → 2116
      dsum = 13 → 3136
      dsum = 19 → 1936, 4096
      dsum = 22 → 5476
      dsum = 25 → 5776, 7396, 8836

      Two of these 3 have repeated digits, so Callum must have answered that square did not have repeated digits, which uniquely identifies 5476 as his number.

      Like

    • GeoffR's avatar

      GeoffR 4:17 pm on 1 August 2024 Permalink | Reply

      
      from collections import defaultdict
      from enigma import is_prime, dsum
      
      ans = defaultdict(list)
      
      sq4 = [ x**2 for x in range(32, 100)]
      
      for n1 in sq4:
          flag = 0  # for repeating or non-repeating digits
          n2 = int(str(n1)[0:3])
          if is_prime(n2):
              # non rpeeating digits in squares
              if len(set(str(n1))) == len(str(n1)):
                  flag = 1
                  ans[(flag, dsum(n1))] += [n1]
              # repeating digits in squares
              if len(set(str(n1))) != len(str(n1)):
                  flag = 2
                  ans[(flag, dsum(n1))] += [n1]
      
      for k, v in ans.items():
          print(k,v)
      
      '''
      (1, 19) [1936, 4096] <<< multiple squares for digit sum
      (2, 10) [2116] <<< same number of repeating digits as square 3136
      (2, 13) [3136] <<< same number of repeating digits as square 2116
      (1, 22) [5476]  <<< Answer
      (2, 25) [5776, 8836] <<< multiple squares for digit sum
      (1, 25) [7396]  <<< same digit sum as squares 5776, 8836
      '''
      
      
      
      

      Like

    • Ruud's avatar

      Ruud 8:50 pm on 1 August 2024 Permalink | Reply

      from istr import istr
      import math
      import collections
      
      
      def is_prime(n):
          if n < 2:
              return False
          if n % 2 == 0:
              return n == 2  # return False
          k = 3
          while k * k <= n:
              if n % k == 0:
                  return False
              k += 2
          return True
      
      
      squares_per_sum_digits = collections.defaultdict(list)
      
      for i in range(round(math.sqrt(1000)), round(math.sqrt(10000))):
          square = istr(i * i)
          if is_prime(square[:-1]):
              prime = square[:-1]
              sum_digits = sum(n for n in square)
              squares_per_sum_digits[sum_digits].append(square)
      
      potential_squares = [squares[0] for squares in squares_per_sum_digits.values() if len(squares) == 1]
      has_repeated_digits = collections.defaultdict(list)
      for square in potential_squares:
          has_repeated_digits[len(set(square))!=4].append(square)
      
      solution = [square[0] for square in has_repeated_digits.values() if len(square) == 1]
      print(*solution)
      

      Like

    • GeoffR's avatar

      GeoffR 7:57 pm on 3 August 2024 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..9:A; var 0..9:B; var 1..9:C; var 0..9:D;
      var 1024..9081: sq_dig4 == 1000*A + 100*B + 10*C + D;
      
      set of int: sq4 = {n * n | n in 32..99};  
      
      predicate is_prime(var int: x) = 
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x)))))
       ((i < x) -> (x mod i > 0));
       
      % Square with last digit deleted is a prime
      constraint is_prime(100*A + 10*B + C);
      constraint sq_dig4 in sq4;
      
      solve satisfy;
      
      output[ "Digit sum = " ++ show(A + B + C + D) ++
      ", Square = " ++ show(sq_dig4) ];
      
      % Digit sum = 10, Square = 2116 - repeating digits - 2nd stage elimination
      % ----------
      % Digit sum = 19, Square = 1936 - not a square with a single digit sum - 1st stage elimination
      % ----------
      % Digit sum = 13, Square = 3136 - repeating digits - 2nd stage eliminations
      % ----------
      % Digit sum = 25, Square = 8836 - not a square with a single digit sum - 1st stage elimination
      % ----------
      % Digit sum = 22, Square = 5476 - *** ANSWER *** (unique digit sum, no repeating digits)
      % ----------
      % Digit sum = 25, Square = 5776 - not a square with a single digit sum - 1st stage elimination
      % ----------
      % Digit sum = 19, Square = 4096 - not a square with a single digit sum - 1st stage elimination
      % ----------
      % Digit sum = 25, Square = 7396 - not a square with a single digit sum - 1st stage elimination
      % ----------
      % ==========
      

      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