Updates from Jim Randell Toggle Comment Threads | Keyboard Shortcuts

  • 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

  • Unknown's avatar

    Jim Randell 8:40 am on 30 July 2024 Permalink | Reply
    Tags:   

    Brain-Teaser 542: Finger trouble 

    From The Sunday Times, 14th November 1971 [link]

    The Wabu tribesmen, though invariably truthful, are inveterate thieves, and this despite a tribal law which requires any man convicted of theft to have one finger amputated. Few of them now have a full complement and, since they count on their fingers, their answers to numerical questions are confusing to the outsider. (For instance, an 8-fingered man gives his answers to base 8, so that, for example, our figure 100 is for him 144).

    Despite these handicaps, they are keen cricketers, and I recently watched their First Eleven. The Chief told me: “Only little Dojo has 10 fingers; the worst-equipped are Abo, Bunto and Coco with 4 apiece”. (I need hardly add that the Wabu would never elect a Chief who had been convicted of theft).

    Later I asked some members of the team how many fingers (thumbs are, of course, included) the Eleven totalled. Epo said “242”, and Foto agreed; Gobo said “132”, and Hingo agreed. Kinko added: “I have more fingers than Iffo”.

    How many fingers each have Epo, Hingo, Iffo and Jabo (the Wicket-keeper)?

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

    [teaser542]

     
    • Jim Randell's avatar

      Jim Randell 8:41 am on 30 July 2024 Permalink | Reply

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

      The following run file executes in 83ms. (Internal runtime of the generate code is 1.9ms).

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      --base=11  # values are between 4 and 10
      --distinct=""
      
      # we are given some values
      --assign="A,4"
      --assign="B,4"
      --assign="C,4"
      --assign="D,10"
      # and the others are between 5 and 9
      --digits="5-9"
      # additional constraints
      "E = F"
      "G = H"
      "K > I"
      
      # total number of fingers
      --macro="@total = (A + B + C + D + E + F + G + H + I + J + K)"
      
      # E (and F) says "242"
      "int2base(@total, base=E) == '242'"
      
      # G (and H) says "132"
      "int2base(@total, base=G) == '132'"
      
      --answer="(E, H, I, J)"
      --template=""
      

      Solution: Epo has 5 fingers; Hingo has 7 fingers; Iffo has 8 fingers; Jabo has 9 fingers.

      The number of fingers for each member of the team are:

      A = 4
      B = 4
      C = 4
      D = 10
      E = 5
      F = 5
      G = 7
      H = 7
      I = 8
      J = 9
      K = 9
      total = 72

      And the total given in the appropriate bases:

      A, B, C → 1020 [base 4]
      D → 72 [base 10]
      E, F → 242 [base 5]
      G, H → 132 [base 7]
      I → 110 [base 8]
      J, K → 80 [base 9]

      Like

      • Ruud's avatar

        Ruud 4:14 pm on 30 July 2024 Permalink | Reply

        It is really simple to solve this one by hand.
        But, here’s my as brute as possible code:

        import itertools
        
        a = b = c = 4
        d = 10
        for e in range(5, 11):
            sum_e = int("242", e)
        
            for g in range(4, 11):
                sum_g = int("132", g)
                if sum_e == sum_g:
                    f = e
                    h = g
                    ijk = sum_e - (a + b + c + d + e + f + g + h)
                    for i, j, k in itertools.product(range(1, 10), repeat=3):
                        if i + j + k == ijk and k > i:
                            print(f"Epo={e} Hingo={h} Iffo={i} Jabo={j}")
        

        Like

    • Ruud's avatar

      Ruud 7:30 pm on 30 July 2024 Permalink | Reply

      Even more brute force:

      import itertools
      
      a = b = c = 4
      d = 10
      for e, f, g, h, i, j, k in itertools.product(range(5, 10), repeat=7):
          if e == f and g == h and (total := int("242", e)) == int("132", g) and k > i and (a + b + c + d + e + f + g + h + i + j + k) == total:
              print(f"Epo={e} Hingo={h} Iffo={i} Jabo={j}")
      

      Like

    • Frits's avatar

      Frits 1:44 pm on 31 July 2024 Permalink | Reply

      from enigma import SubstitutedExpression
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
          # G*G + 3*G - 2*(E*E + 2*E) = 0
          "is_square(1 + G * (G + 3) // 2) - 1 = E",
          
          "K > I",
          "(G * (G + 3) + 2) -  (A + B + C + D + E + E + G + G + I + J) = K",
        ],
        answer="(E, G, I, J)",
        distinct="",
        s2d=dict(A=4, B=4, C=4, D=10),
        digits=range(5, 10),
        verbose=0,    # use 256 to see the generated code
      )
      
      names= "Epo Hingo Iffo Jabo".split()
      
      # print answers
      for ans in p.answers():
        print(f"{', '.join(f'{x}: {str(y)}'for x, y in zip(names, ans))}")     
      

      Like

  • Unknown's avatar

    Jim Randell 6:58 am on 28 July 2024 Permalink | Reply
    Tags:   

    Teaser 3227: Chess club cupboard 

    From The Sunday Times, 28th July 2024 [link] [link]

    When installing the Chess Club cupboard in its new room, the members carelessly jammed it on the low ceiling and back wall, as shown from the side (not to scale).

    Measurements were duly taken and the following were noted. The floor and ceiling were level and the back wall was vertical. The cupboard was a rectangular cuboid. The ceiling height was just 2cm greater than the cupboard height. Also, the depth of the cupboard from front to back was 148 cm less than the cupboard height. Finally the point on the ceiling where the cupboard jammed was a distance from the back wall that was 125 cm less than the cupboard height.

    What is the cupboard height?

    [teaser3227]

     
    • Jim Randell's avatar

      Jim Randell 7:11 am on 28 July 2024 Permalink | Reply

      Originally I assumed some of the dimensions were whole numbers of centimetres, which allows you to find the answer, but we do not need to make this assumption.

      Here is a solution using the [[ Polynomial ]] class from the enigma.py library to generate a polynomial equation, and we can then look for positive real roots of the equation to determine the necessary dimensions.

      (Also, today is the 15th anniversary of the start of the enigma.py library).

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

      Run: [ @replit ]

      from enigma import (Polynomial, sq, printf)
      
      # let x = cupboard depth
      fx = Polynomial('x')
      
      # y = cupboard height
      fy = fx + 148
      
      # h = room height
      fh = fy + 2
      
      # d = distance top jam to top corner
      fd = fy - 125
      
      # if:
      #   a = height of upper triangle
      #   b = height of lower triangle
      # we have:
      #   h = a + b
      # and:
      #   a^2 = y^2 - d^2
      #   b = x.d/y
      #   a = h - b = (y.h - x.d)/y
      #   a^2 = (y.h - x.d)^2 / y^2 = y^2 - d^2
      #   y^2(y^2 - d^2) = (y.h - x.d)^2  # for x > 0
      f = (sq(fy) * (sq(fy) - sq(fd)) - sq(fy * fh - fx * fd)).scale()
      printf("[f(x) = {f}]", f=f.print())
      
      # look for positive real roots of f(x) = 0
      for x in f.roots(domain='F', include='+'):
        # output solution
        printf("cupboard = {x:g} x {y:g}; room height = {h:g}", y=fy(x), h=fh(x))
      

      Solution: The cupboard was 185 cm high.

      So the cupboard has dimensions: 37 cm × 185 cm, and the room is 187 cm high.

      The polynomial to determine the depth of the cupboard x is:

      f(x) = x^3 + 79x^2 − 1628x − 98568
      f(x) = (x − 37)(x^2 + 116x + 2664)

      The linear component has a positive root at:

      x = 37

      which provides the required answer for the depth of the cupboard.

      The quadratic component has two negative roots at:

      x = 10√7 − 58 ≈ −31.542
      x = −10√7 − 58 ≈ −84.458

      but these do not provide viable answers to the puzzle.

      Like

      • Jim Randell's avatar

        Jim Randell 9:09 am on 29 July 2024 Permalink | Reply

        Or the polynomial can be solved numerically, to give an approximate answer.

        And this is slightly faster. The following Python program has an internal runtime of 324µs).

        Run: [ @replit ]

        from enigma import (Polynomial, sq, find_zero, printf)
        
        # let x = cupboard depth
        # y = cupboard height
        # h = room height
        # d = distance top jam to top corner
        fx = Polynomial('x')
        fy = fx + 148
        fh = fy + 2
        fd = fy - 125
        
        # construct polynomial to solve
        f = (sq(fy) * (sq(fy) - sq(fd)) - sq(fy * fh - fx * fd)).scale()
        printf("[f(x) = {f}]", f=f.print())
        
        # find a solution numerically
        x = find_zero(f, 1, 100).v
        
        # output solution
        printf("cupboard = {x:.2f} x {y:.2f}; room height = {h:.2f}", y=fy(x), h=fh(x))
        

        Like

    • GeoffR's avatar

      GeoffR 12:21 pm on 28 July 2024 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..250:h; var 1..250:y1; var 1..100:b;
      
      % h = cupboard height
      % y1 = depth below ceiling of top cupboard jam point
      % b = distance of bottom jam point from vertical wall
      
      % Two triangles to solve by Pythagorus
      constraint h * h == (h - 125) * (h - 125) + (y1 * y1);
      
      constraint (h - 148 ) * (h - 148) == (b * b) + (h + 2 - y1) * (h + 2 - y1);
      
      solve satisfy;
      
      output ["Cupboard height = " ++ show(h) ++ "cm."];
      
      
      
      

      Like

    • GeoffR's avatar

      GeoffR 12:52 pm on 28 July 2024 Permalink | Reply

      I don’t suppose the setter intended it, but I found a second solution with a cupboard height of more than 400 cm higher than the presumed solution!

      Like

      • Jim Randell's avatar

        Jim Randell 2:32 pm on 28 July 2024 Permalink | Reply

        @GeoffR: Originally I thought there were further solutions involving cupboards with non-integer dimensions, or very large cupboards (and rooms). But now I have done the analysis I found that the depth of the cupboard is defined by a cubic equation that has one positive real root (which gives the required answer) and two negative real roots, so I don’t think there are any further solutions, even if the size of the cupboard/room are not restricted.

        Like

        • Frits's avatar

          Frits 2:54 pm on 28 July 2024 Permalink | Reply

          @Jim,

          The equations I noted down for this puzzle also had a solution 10 * (9 + sqrt(7)) but that was less than 148 cm.

          Like

          • Jim Randell's avatar

            Jim Randell 3:23 pm on 28 July 2024 Permalink | Reply

            @Frits: Presumably you were working in terms of the height of the cupboard. I was working in terms of the depth, so there was only one positive root.

            Like

        • GeoffR's avatar

          GeoffR 4:11 pm on 28 July 2024 Permalink | Reply

          @Jim: My original program gave the same outputs as your original solution.
          I increased the upper bounds of the variables to show the second solution I obtained with the second program below. Seems reasonable to use integers . Program is slow with the extra solution, but does it look OK?

          % A Solution in MiniZinc
          include "globals.mzn";
          
          var 1..1250:h; var 1..1250:y1; var 1..1000:b;
          
          % h = cupboard height, rht = room height (for output)
          % y1 = depth below ceiling of top cupboard jam point
          % b = distance of bottom jam point from vertical wall
          
          % Two triangles to solve by Pythagorus
          constraint h * h == (h - 125) * (h - 125) + (y1 * y1);
          
          constraint (h - 148 ) * (h - 148) == (b * b) + (h + 2 - y1) * (h + 2 - y1);
          
          solve satisfy;
          
          output ["Cupboard height = " ++ show(h) ++ "cm." ++ "\n" ++
          "[h, w, rht, y1, b ] = " ++ show( [h, h-148, h+2, y1, b ]  )];
          

          Like

          • Jim Randell's avatar

            Jim Randell 6:03 pm on 28 July 2024 Permalink | Reply

            @GeoffR: My very first program did not include a check that the upper and lower triangles were similar, which lead me to believe that there potentially multiple solutions without further constraints. But this allows cupboards that have a non-rectangular cross-section.

            However my subsequent analysis gives a single solution without further constraints. So we don’t need to limit the size of cupboard/room, and we don’t require measurements to have integer values.

            Liked by 1 person

    • Ruud's avatar

      Ruud 6:16 pm on 28 July 2024 Permalink | Reply

      I worked out by hand that the problem can be defined as finding the roots of the expression
      math.sqrt(250 *c -125*125)+((c-148)*(c-125)/c) – (c+2)
      I just put that in Wolfram Alpha as
      find roots of sqrt(250 *c -125*125)+((c-148)*(c-125)/c) – (c+2)
      to find the real solution (not revealed) and 10 (9 + sqrt(7)). The latter does not work here.

      Like

      • Frits's avatar

        Frits 6:55 pm on 28 July 2024 Permalink | Reply

        I did something similar with the same results.

        Adding the following to your code prevent multiple solutions:

          
        % same angles
        constraint h * b = (h - 148) * y1;
        

        Like

  • Unknown's avatar

    Jim Randell 10:49 am on 25 July 2024 Permalink | Reply
    Tags:   

    Brain-Teaser 416: Sharing sweets 

    From The Sunday Times, 27th April 1969 [link]

    The Binks family had a birthday party recently for Ann, the youngest child. A tin of toffees was shared among the seven youngest members of the family, whose ages were all different and less than 20.

    It was decided that the younger children should have more than the older; so Mr Binks suggested that each should receive the number obtained by dividing the total number of toffees by his or her age. This was done and it so happened that all the divisions worked out exactly and no toffees were left over.

    Mary received 18 sweets.

    How much older was she than Ann?

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

    [teaser416]

     
    • Jim Randell's avatar

      Jim Randell 10:51 am on 25 July 2024 Permalink | Reply

      Labelling the children in age order A, …, G, so A is Ann, and the total number of toffees is T, we have:

      T = T/A + T/B + T/C + T/D + T/E + T/F + T/G

      1 = 1/A + 1/B + 1/C + 1/D + 1/E + 1/F + 1/G

      So we need to find 7 different reciprocals (with denominators less than 20) that sum to 1. And we can use the [[ reciprocals() ]] function from the enigma.py library to do that (originally written for Enigma 348).

      We can then assign one of the values T/B, …, T/G to 18 (for Mary), and check that all the remaining T/X values give a whole number.

      The following Python program runs in 66ms. (Internal runtime is 753µs).

      Run: [ @replit ]

      from enigma import (reciprocals, printf)
      
      # find 7 different reciprocals that sum to 1
      for rs in reciprocals(7, 1, 1, M=19, g=1):
        # Ann is the youngest
        A = rs.pop(0)
        # Mary received 18 sweets
        for M in rs:
          T = M * 18
          if not all(T % r == 0 for r in rs): continue
          # output solution
          printf("A={A} M={M} [T={T} rs={rs}]", rs=[A] + rs)
      

      Solution: Mary (10) is 7 years older than Ann (3).

      There is only one set of 7 reciprocals that works:

      1 = 1/3 + 1/4 + 1/9 + 1/10 + 1/12 + 1/15 + 1/18

      There are 180 toffees, and the ages are:

      3 → 60 toffees (Ann)
      4 → 45 toffees
      9 → 20 toffees
      10 → 18 toffees (Mary)
      12 → 15 toffees
      15 → 12 toffees
      18 → 10 toffees
      total = 180 toffees

      Like

    • GeoffR's avatar

      GeoffR 1:32 pm on 25 July 2024 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..19:A; var 1..19:B; var 1..19:C; var 1..19:D;
      var 1..19:E; var 1..19:F; var 1..19:G;
      
      constraint all_different ([A, B, C, D, E, F, G]);
      % Order childrens ages
      constraint A < B /\ B < C /\ C < D /\ D < E /\ E < F /\ F < G;
      
      var 28..200:T;  % total number of toffees
      
      % Distribute toffees to seven children, with none left over
      constraint T  mod A == 0 /\ T  mod B == 0 /\ T  mod C == 0 /\ T  mod D == 0 
      /\ T  mod E == 0 /\ T  mod F == 0 /\ T  mod G == 0;
      
      constraint T == T div A  + T div B + T div C + T div D 
      + T div E + T div F + T div G;
      
      solve satisfy;
      
      output ["Childrens ages = " ++ show ( [A,B,C,D,E,F,G] )
      ++ "\n" ++ "Number of toffees = " ++ show(T) ];
      
      % Childrens ages = [3, 4, 9, 10, 12, 15, 18]
      % Number of toffees = 180
      % ----------
      % ==========
      

      As Mary received 18 sweets, she was 10 years old, as 10 * 18 = 180.
      As the youngest was Ann, she was 3 years old, 7 years younger than Mary.

      Like

    • Ruud's avatar

      Ruud 6:40 am on 26 July 2024 Permalink | Reply

      [removed]

      Like

      • Jim Randell's avatar

        Jim Randell 9:21 am on 26 July 2024 Permalink | Reply

        @Ruud: Can you explain the reasoning behind your code? I tried changing the 18 to 24 to solve a variation of the puzzle, but it did not give a correct answer. (I also added the missing imports to your program).

        Like

        • ruudvanderham's avatar

          ruudvanderham 12:02 pm on 26 July 2024 Permalink | Reply

          @Jim
          My solution was incorrect. Could you remove it?
          Here’s my revised one, which is not much different from yours:

          import itertools
          import math
          
          number_of_toffee_mary = 18
          for ages in itertools.combinations(range(1, 20), 7):
              if math.isclose(sum(1 / age for age in ages), 1):
                  for age in ages:
                      if all(divmod(age * number_of_toffee_mary, try_age)[1] == 0 for try_age in ages):
                          print(f"{ages=}. Number of toffees={number_of_toffee_mary*age}. Mary is {age-ages[0]} years older than Ann")

          Like

    • Frits's avatar

      Frits 4:59 pm on 27 July 2024 Permalink | Reply

      from itertools import combinations
      
      M = 19
      N = 7
      
      # return divisors of <n> between 2 and <m>
      def divs(n, m=M):
        lst = [d for d in range(2, int(n**.5) + 1) if n % d == 0 and d <= m]
        return lst + [d for x in lst[::-1] if x * x != n and (d := n // x) <= m]
      
      # reciprocal sum
      def rs(s): 
        i, t = 0, 0.0
        ln = len(s)
        while t < 1 and i < ln:
          t += 1 / s[i]
          i += 1
        return i == ln and round(t, 5) == 1
      
      # Mary received 18 sweets
      for m in range(2, M + 1):
        # pick <N> divisors
        for c in combinations(divs(18 * m), N):
          # reciprocal sum must be 1
          if rs(c) == 1: 
            print(f"answer: {c}")
      

      Like

  • Unknown's avatar

    Jim Randell 9:44 am on 23 July 2024 Permalink | Reply
    Tags:   

    Teaser 2576: Latin cube 

    From The Sunday Times, 5th February 2012 [link] [link]

    I have a cube and on each face of it there is a capital letter. I look at one face from the front, hold the top and bottom faces horizontal, and rotate the cube. In this way I can correctly read a four-letter Roman numeral. Secondly, I hold the cube with the original front face underneath and the original top face at the front, and I rotate the cube keeping the new top and bottom faces horizontal. In this way I correctly see another four-letter Roman numeral. Thirdly, I return the cube to its original position and rotate it with the two sides vertical to give another correct four-letter Roman numeral. The sum of the second and third numbers is less than a hundred.

    What was the third four-letter Roman numeral seen?

    [teaser2576]

     
    • Jim Randell's avatar

      Jim Randell 9:45 am on 23 July 2024 Permalink | Reply

      Some clarification of the puzzle text is required to find a single answer (and I assume the puzzle is meant to have a unique answer):

      (1) Although the letters used in Roman numerals (I, V, X, L, C, D, M) are all distinguishable whatever the orientation, the puzzle requires that when letters are read they are in a “sensible” orientation. So, I and X can be read correctly upside down. However this is not sufficient to solve the puzzle, we also require that X can be read correctly in any orientation (which may not be the case if a serif font is used, as is often the case with Roman numerals).

      (2) The mechanism to read the numbers is that the front face is read, the cube is then rotated through 90° about a major axis to change the front face, which is then read, and the same move is repeated until the four faces in a band around the cube have been read in order (and a final move would bring the cube back to the starting position).

      (3) The numbers read should be valid Roman numerals in the “usual” form. (I used the [[ int2roman() ]] and [[ is_roman() ]] functions in the enigma.py library to ensure this). I didn’t allow “IIII” to represent 4 (although if you do it doesn’t change anything).

      (4) Each of the three numbers read is different. (Possibly this is meant to be indicated by the use of “another”).


      We are not told what direction the cube is rotated, so this Python program considers rotations in each direction for the 3 numbers. Although note that for some numbers (e.g. VIII (= 8), where the second and fourth letters are the same), the direction of the rotation doesn’t matter.

      I used the [[ Cube() ]] class (originally from Teaser 2835) to keep track of the rotation of the cube (and orientation of the faces).

      This Python program considers possible values for the second and third numbers (which cover bands of the cube that include all faces, so leave the cube fully specified), and then reads the first number and looks for cases where this gives a valid Roman numeral.

      It runs in 78ms. (Internal runtime is 11ms).

      Run: [ @replit ]

      from enigma import (irange, int2roman, is_roman, join, seq2str, printf)
      from cube import (Cube, U, D, L, R, F, B, face_label as f2l)
      
      # valid orientations for roman digits
      valid = dict((k, {0}) for k in "IVXLCDM")
      valid['I'] = {0, 2}  # I can be upside down
      valid['X'] = {0, 1, 2, 3}  # X can be in any orientation
      
      # collect 4-letter roman numerals less than 100
      n2r = dict()
      for n in irange(1, 99):
        r = int2roman(n)
        if len(r) == 4:
          n2r[n] = r
      
      # read values from the front of cube <c>, and apply each of the specified moves <ms>
      # while match the values in <vs> (can be '?')
      # return (<updated cube>, <values read>)
      def read(c, ms, vs):
        rs = list()
        while True:
          # read the front face
          (v, vs0) = (c.faces[F], vs[0])
          # blank face?
          if v is None:
            v = vs0
            if v != '?':
              # fill out the new value
              c = c.update(faces=[(F, v)], orientations=[(F, 0)])
          else:
            # check it is in a valid orientation and a valid value
            if (c.orientations[F] not in valid[v]) or (vs0 != '?' and vs0 != v):
              return (None, None)
          rs.append(v)
          # any more moves?
          if not ms: break
          c = c.rotate(ms[0:1])
          ms = ms[1:]
          vs = vs[1:]
        return (c, join(rs))
      
      # start with an empty cube
      c0 = Cube(faces=[None] * 6)
      
      # choose a 4-letter roman for the second number
      for (n2, r2) in n2r.items():
        # choose the direction of rotation
        for d2 in [U, D]:
          # read the second number
          (c1, _) = read(c0.rotate([L]), [d2] * 3, r2)
          if c1 is None: continue
          # reset to original position
          c1 = c1.rotate([d2, R])
      
          # choose a 4-letter roman for the third number
          for (n3, r3) in n2r.items():
            # the first and second numbers sum to less than 100
            if n2 + n3 > 99: continue
            # choose a direction of rotation
            for d3 in [L, R]:
              # read the third number
              (c2, _) = read(c1, [d3] * 3, r3)
              if c2 is None: continue
              # all faces should now be filled out
              assert None not in c2.faces
              # reset to original position
              c2 = c2.rotate([d3])
      
              # choose a direction for the first number
              for d1 in [U, D]:
                # read the first number
                (_, r1) = read(c2, [d1] * 3, '????')
                if r1 is None: continue
                # is it a valid roman?
                n1 = is_roman(r1)
                if not n1: continue
                # check numbers are all different
                if len({n1, n2, n3}) != 3: continue
      
                # output solution
                printf("{r1} ({n1}) [{d1}]; {r2} ({n2}) [{d2}]; {r3} ({n3}) [{d3}]; {cube}",
                       d1=f2l[d1], d2=f2l[d2], d3=f2l[d3], cube=seq2str(c2.faces))
      

      Solution: The third Roman numeral seen was: LXII (= 62).

      The first two numbers were: LXIX (= 69) and XXIX (= 29), and the second and third sum to 91.

      Note that both of the first two numbers can be read using either direction of rotation (which is why my code finds 4 different ways to the answer), but the final number only works in one direction.

      The cube has faces (U, D, L, R, F, B) = (X, I, X, X, L, I).

      If we allow repeated numbers there is also a solution with the cube (U, D, L, R, F, B) = (X, I, X, X, X, I), which gives the numbers XXIX (= 29), XXIX (= 29), XXII (= 22).

      Like

    • Lise Andreasen's avatar

      Lise Andreasen 12:07 am on 24 July 2024 Permalink | Reply

      Especially (1) the orientation of X is interesting.

      Like

  • Unknown's avatar

    Jim Randell 12:59 pm on 21 July 2024 Permalink | Reply
    Tags:   

    Brain-Teaser 420: [The Island of Squares] 

    From The Sunday Times, 25th May 1969 [link]

    Here is the Island of Squares with its 22 provinces, and its capital in the middle of the central province.

    The Geographer Royal has been instructed to colour the provinces red, blue and yellow, in such a way that no two provinces with the same colouring have a common boundary-line.

    There is one further complication. Four main roads are planned each of which will go straight from the capital to one corner of the island crossing the corners of provinces on the way; one of these roads must never be in a blue province, and another must at no corner move from a yellow to a blue province or vice versa.

    What colours Geographer Royal will the use for provinces 1 and 2?

    This puzzle was originally published with no title.

    [teaser420]

     
    • Jim Randell's avatar

      Jim Randell 1:00 pm on 21 July 2024 Permalink | Reply

      This Python program colours the provinces so that no two adjacent regions share a colour, and then checks to see if there are two roads that meet the requirements.

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

      Run: [ @replit ]

      from enigma import (peek, update, join, union, map2str, printf)
      
      # adjacency matrix for provinces
      adj = {
        1: {2, 3, 4, 5},
        2: {1, 6, 7},
        3: {1, 4, 14},
        4: {1, 3, 5, 8, 15},
        5: {1, 4, 6, 9, 10},
        6: {2, 5, 7, 10, 13},
        7: {2, 6, 13, 18, 21, 22},
        8: {4, 9, 11, 16},
        9: {5, 8, 10, 11},
        10: {5, 6, 9, 12},
        11: {8, 9, 12, 17},
        12: {10, 11, 13, 17},
        13: {6, 7, 12, 18},
        14: {3, 15, 19},
        15: {4, 14, 16, 20},
        16: {8, 15, 17, 20},
        17: {11, 12, 16, 18, 21},
        18: {7, 13, 17, 21},
        19: {14, 20, 22},
        20: {15, 16, 19, 21, 22},
        21: {7, 17, 18, 20, 22},
        22: {7, 19, 20, 21},
      }
      
      # colour regions <rs> with colours <cs>
      def colour(rs, cs, m=dict()):
        # are we done?
        if not rs:
          yield m
        else:
          # choose an uncoloured region
          r = peek(rs)
          # choose a colour
          xs = cs.difference(m[x] for x in adj[r] if x in m)
          for x in xs:
            yield from colour(rs.difference([r]), cs, update(m, [(r, x)]))
      
      # regions for each road
      roads = dict(
        NW=[11, 16, 20, 19],
        NE=[11, 17, 21, 7],
        SE=[11, 10, 6, 2],
        SW=[11, 8, 4, 1],
      )
      
      # check roads
      def check(m):
        # map roads to colours
        r = dict((k, join(m[x] for x in v)) for (k, v) in roads.items())
        # find roads the do not pass through a blue province
        R1 = set(k for (k, v) in r.items() if not ('B' in v))
        if not R1: return
        # find roads that do not pass directly from blue to yellow (or vice versa)
        R2 = set(k for (k, v) in r.items() if not ('BY' in v or 'YB' in v))
        if not R2: return
        # check we can find one of each
        if len(union([R1, R2])) < 2: return
        return r
      
      # colour the regions
      for m in colour(set(adj.keys()), set("RBY")):
        # and check the roads
        r = check(m)
        if r:
          # output solution
          printf("{m}", m=map2str(m))
          printf("-> {r}", r=map2str(r))
          printf()
      

      Solution: Province 1 is red. Province 2 is yellow.

      The complete map is shown below:

      There is one province that can be either red or blue (On the extreme left of the diagram. I numbered it 14, and gave it both colours).

      The NE road passes through no blue, and the SW road does not pass directly from a blue to a yellow (or vice versa).

      We can see that there is no point trying to colour the central province blue (as that would make blue appear in every road), but I think the code is fast enough without this.

      Like

      • Ruud's avatar

        Ruud 9:27 am on 22 July 2024 Permalink | Reply

        Here’s my code:

        neighbours = {
            1: {2, 3, 4, 5},
            2: {1, 6, 7},
            3: {1, 4, 14},
            4: {1, 3, 5, 8, 15},
            5: {1, 4, 6, 9, 10},
            6: {2, 5, 7, 10, 13},
            7: {2, 6, 13, 18, 21, 22},
            8: {4, 9, 11, 16},
            9: {5, 8, 10, 11},
            10: {5, 9, 6, 12},
            11: {8, 9, 12, 17},
            12: {10, 11, 13, 17},
            13: {6, 12, 7, 18},
            14: {3, 15, 19},
            15: {4, 14, 16, 20},
            16: {8, 15, 17, 20},
            17: {11, 12, 16, 18, 21},
            18: {13, 17, 7, 21},
            19: {14, 20, 22},
            20: {15, 16, 19, 21, 22},
            21: {17, 18, 20, 7, 22},
            22: {19, 20, 21, 7},
        }
        roads = [(1, 4, 8, 11), (2, 6, 10, 11), (19, 20, 16, 11), (7, 21, 17, 11)]
        
        
        def solve(province, colors):
            for color in colors[province]:
                new_colors = colors.copy()
                new_colors[province] = color
                for neighbour in neighbours[province]:
                    new_colors[neighbour] = new_colors[neighbour].replace(color, "")
                if province == 22:
                    not_blue = set()
                    not_blue_yellow = set()
                    for road in roads:
                        road_colors = "".join(colors[province] for province in road)
                        if "b" not in road_colors:
                            not_blue.add(road)
                        if not ("yb" in road_colors or "by" in road_colors):
                            not_blue_yellow.add(road)
        
                    if len(not_blue) > 0 and len(not_blue_yellow) > 0 and len(not_blue | not_blue_yellow) >= 2:
                        print(new_colors[1], new_colors[2])
                else:
                    solve(province + 1, colors=new_colors)
        
        
        solve(province=1, colors={province: "ryb" for province in range(1, 23)})
        

        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