Tagged: by: Adrian Somerfield Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 10:16 am on 8 August 2025 Permalink | Reply
    Tags: by: Adrian Somerfield   

    Teaser 2334: Tetrahedral cubes 

    From The Sunday Times, 17th June 2007 [link]

    I have constructed a tetrahedron (a solid with four triangular faces and six edges). On measuring those six edges, I find that their lengths, in centimetres, form six consecutive perfect cubes. Furthermore, if you managed to construct a tetrahedron with the same properties, the longest side of yours could not be shorter than any side of mine.

    How long is the longest side of my tetrahedron?

    [teaser2334]

     
    • Jim Randell's avatar

      Jim Randell 10:17 am on 8 August 2025 Permalink | Reply

      So we want to find the smallest set of consecutive cubes that allows us to construct a tetrahedron.

      This is a problem that we have encountered before, see Enigma 1152 (also set by Adrian Somerfield, 6 years before this puzzle).

      from enigma import (Enumerator, powers, inf, tuples, ipartitions, sq, is_triangle, printf)
      
      # compute the Cayley-Menger determinant (= 288 vol^2)
      def CMdet(x, y, z, X, Y, Z):
        (x2, X2, y2, Y2, z2, Z2) = map(sq, (x, X, y, Y, z, Z))
        # calculate: Matrix([[0, 1, 1, 1, 1], [1, 0, x2, y2, Z2], [1, x2, 0, z2, Y2], [1, y2, z2, 0, X2], [1, Z2, Y2, X2, 0]]).det()
        return (
          2 * x2 * X2 * (y2 + Y2 + z2 + Z2 - x2 - X2) +
          2 * y2 * Y2 * (x2 + X2 + z2 + Z2 - y2 - Y2) +
          2 * z2 * Z2 * (x2 + X2 + y2 + Y2 - z2 - Z2) -
          (x2 - X2) * (y2 - Y2) * (z2 - Z2) -
          (x2 + X2) * (y2 + Y2) * (z2 + Z2)
        )
      
      # check length form a tetrahedron: base = (x, y, z), opposite edges = (X, Y, Z)
      # return 288 V^2 if the tetrahedron is viable, else None
      def is_tetra(x, y, z, X, Y, Z):
        # check each face is a triangle
        if not all(is_triangle(*s) for s in [(x, y, z), (x, Y, Z), (X, y, Z), (X, Y, z)]): return
        # does it have a positive volume? d = 288 V^2
        d = CMdet(x, y, z, X, Y, Z)
        if d < 0: return
        return d
      
      # generate tetrahedra for sides in cs
      def tetras(cs):
        # group the sides into pairs
        for ((x, X), (y, Y), (z, Z)) in ipartitions(cs, 2):
          # do they form a tetrahedron?
          if is_tetra(x, y, z, X, Y, Z):
            yield ((x, X), (y, Y), (z, Z))
      
      # generate consecutive cubes
      for cs in tuples(powers(1, inf, 3), 6):
        ss = Enumerator(tetras(cs))
        for ((x, X), (y, Y), (z, Z)) in ss:
          # output solution
          printf("({x}, {X}) ({y}, {Y}) ({z}, {Z}) -> max = {m}", m=cs[-1])
        if ss.count > 0: break  # stop at smallest solution
      

      Solution: The longest side is 2197 cm.

      So it is quite a large tetrahedron.

      Like

  • Unknown's avatar

    Jim Randell 7:29 am on 14 March 2025 Permalink | Reply
    Tags: by: Adrian Somerfield   

    Teaser 2568: Ending 2011 

    From The Sunday Times, 11th December 2011 [link] [link]

    I have written down three positive whole numbers consisting of two primes and a perfect square. Between them they use nine digits and no digit is repeated.

    If you form an addition sum with the three numbers, then what do you end up with as the total? Appropriately enough you end up with 2011.

    What, in increasing order, are the three numbers?

    [teaser2568]

     
    • Jim Randell's avatar

      Jim Randell 7:30 am on 14 March 2025 Permalink | Reply

      This Python program looks at possible squares (without repeated digits), and then checks to see if the remainder can be made from the sum of two primes.

      The year to be made can be specified on the command line.

      It runs in 62ms. (Internal runtime is 3.4ms).

      from enigma import (powers, inf, primes, distinct_chars, arg, printf)
      
      # total to find
      N = arg(2011, 0, int)
      
      # consider possible squares
      for s in powers(1, inf, 2):
        r = N - s
        if r < 5: break
        if distinct_chars(s) is None: continue
      
        # look for pairs of primes that sum to r
        for p in primes.between(2, r // 2):
          q = r - p
          # q is also a prime
          if q not in primes: continue
          # check for 9 different digits
          if distinct_chars(p, q, s) != 9: continue
          # output solution
          printf("{ns} -> {N} [primes = {p}, {q}; square = {s}]", ns=sorted([p, q, s]))
      

      Solution: The numbers are: 263, 841, 907.

      263 and 907 are prime, and 841 = 29^2.


      We could be a bit cleverer with finding pairs of primes that sum to r. For instance, if r is odd, then one of the primes would have to be 2. But it makes the code a bit longer, and the version above is already fast enough, so I haven’t included it.

      Like

    • Frits's avatar

      Frits 5:05 am on 15 March 2025 Permalink | Reply

      Designed for a low internal run time.

      from itertools import compress
      
      # total to find
      N = 2011
      
      # 2 < primes < n 
      def primesbelow(n):
        # rwh_primes1v2(n):
        """ Returns a list of 2 < primes < n for n > 2 """
        sieve = bytearray([True]) * (n // 2 + 1)
        for i in range(1, int(n ** 0.5) // 2 + 1):
          if sieve[i]:
            sieve[2 * i * (i + 1)::2 * i + 1] = \
            bytearray((n // 2 - 2 * i * (i + 1)) // (2 * i + 1) + 1)
        return {*compress(range(3, n, 2), sieve[1:])}
      
      P = primesbelow(1885)  # max prime is 2011 - 23 - 104
      
      # split number <n> in two different odd prime endings, unequal to <o>
      split = lambda n, o: [(i, i2) for i in range(1, 11, 2) 
                           if (i2 := (10 + n - i) % 10) > i and
                           {i, i2}.isdisjoint([5, o])]
      
      # odd prime number endings per odd square number ending
      pes = {se: split(11 - se, se) for se in [1, 5, 9] for i in range(1, 10, 2)}
      pes = {k: {x for v in vs for x in v} for k, vs in pes.items()}
      
      # all three numbers must be odd as 2 + abcd + efgh > 4000
      
      # consider odd possible squares (with at least 2 digits)
      for n in range(5, 45, 2):
        r = N - (sq := n * n)
        # square ending must allow for valid prime endings
        if not (se := pes[sq % 10]): continue
        if len(set(s := str(sq))) != len(s): continue
        
        # look for pairs of odd primes that sum to r 
        for p in sorted(P):
          # a 2-digit square requires a prime of 1xxx
          if '1' in s and len(s) == 2: break
          if p > r // 2: break
          # valid prime number ending
          if (p % 10) not in se: continue
      
          q = r - p
          # q is also a prime, no repeated digits
          if q not in P: continue
          if len(set(s1 := s + str(p) + str(q))) == len(s1) == 9: 
            # output solution
            print("answer:", sorted([sq, p, q]))
      

      Like

    • ruudvanderham's avatar

      ruudvanderham 11:31 am on 15 March 2025 Permalink | Reply

      import istr
      
      primes = [n for n in istr(range(100, 1000)) if n.is_prime() and n.all_distinct()]
      squares = [n * n for n in istr(range(10, 32)) if (n * n).all_distinct()]
      
      for (n1, n2), n3 in istr.product(istr.combinations(primes, r=2), squares):
          if (n1 | n2 | n3).all_distinct() and n1 + n2 + n3 == 2011:
              print(sorted((n1, n2, n3)))
      

      Like

      • Jim Randell's avatar

        Jim Randell 5:01 pm on 15 March 2025 Permalink | Reply

        @Ruud: Note that it is not specified that the three numbers are all 3-digit numbers (although it turns out that the numbers in the solution are).

        But if the puzzle had been set in 1990, the solution would not be three 3-digit numbers:

        % python3 teaser2568.py 1990
        [59, 324, 1607] -> 1990 [primes = 59, 1607; square = 324]
        

        Like

        • Ruud's avatar

          Ruud 5:13 pm on 15 March 2025 Permalink | Reply

          @Jim
          You are right. I had misread the problem description.
          The code below does not assume that the numbers have three digits.

          import istr
          
          primes = [n for n in istr(range(1, 2011)) if n.is_prime() and n.all_distinct()]
          squares = [n * n for n in istr(range(1, 45)) if (n * n).all_distinct()]
          
          for (n1, n2), n3 in istr.product(istr.combinations(primes, r=2), squares):
              if (n1 | n2 | n3).all_distinct() and n1 + n2 + n3 == 2011:
                  print(sorted((n1, n2, n3)))
          

          Like

          • Frits's avatar

            Frits 2:53 am on 16 March 2025 Permalink | Reply

            @Ruud, you would have reported three solutions for year 1990 .

            “Between them they use nine digits” means exactly nine digits.

            Like

    • Frits's avatar

      Frits 4:21 am on 16 March 2025 Permalink | Reply

      712 is the first year that there is a solution.
      Up to year 2011 there are 454 solutions.
      The program runs in 163ms but is not valid for years a little higher than 2011.

      from itertools import compress
      
      # 2 < primes < n 
      def primesbelow(n):
        # rwh_primes1v2(n):
        """ Returns a list of 2 < primes < n for n > 2 """
        sieve = bytearray([True]) * (n // 2 + 1)
        for i in range(1, int(n ** 0.5) // 2 + 1):
          if sieve[i]:
            sieve[2 * i * (i + 1)::2 * i + 1] = \
            bytearray((n // 2 - 2 * i * (i + 1)) // (2 * i + 1) + 1)
        return {*compress(range(3, n, 2), sieve[1:])}
      
      M = 2011
      # max prime is N - 23 - 104
      P = {p for p in primesbelow(M - 126) if len(set(s := str(p))) == len(s)}
      P2 = sorted(p for p in P if p < 100)
      P3 = sorted(p for p in P if 100 <= p < 1000)
      
      c = 0
      for N in range(1, M + 1):
        # consider possible squares (with at least 2 digits)
        for n in range(4 + (N % 2), int(N**.5) + 1, 2):
          r = N - (sq := n * n)
          if r < 120: break # at least a 2-digit and a 3-digit prime 
          if len(set(s := str(sq))) != (ln := len(s)): continue
          
          # determine which primes to use
          # consider the number of digits in the square number
          # 2 : p + q = 7 so 3 and 4
          # 3 : p + q = 6 so 2 and 4  or  3 and 3
          # 4 : p + q = 5 so 2 and 3
          plst = []
          if ln != 2:
            # add list of 2-digit primes
            plst.append([] if '1' in s and ln == 3 else P2)
          if ln != 4:    
            # add list of 3-digit primes
            plst.append([p for p in P3 if r - p < 1000] if ln == 3 else 
                        [] if '1' in s else P3)
          
          for prms in plst:   
            # look for pairs of primes that sum to r
            for p in prms: 
              q = r - p
              if q < p: break
              # q is also a prime, no repeated digits
              if q not in P: continue
              # between them they use nine digits
              if len(set(s1 := s + str(p) + str(q))) == len(s1) == 9: 
                c += 1
                # output solution
                print(c, f"{N = }", "answer:", sorted([sq, p, q])) 
      

      Like

  • Unknown's avatar

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

    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).

      #! 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 9:44 am on 23 July 2024 Permalink | Reply
    Tags: by: Adrian Somerfield   

    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).

      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 9:31 am on 20 June 2023 Permalink | Reply
    Tags: by: Adrian Somerfield   

    Teaser 2156: Some cubes 

    From The Sunday Times, 11th January 2004 [link]

    In what follows, digits have consistently been replaced by letters, with different letters used for different digits:

    THREE
    CAN
    BE
    CUBES

    As stated, three of those numbers are cubes (and the other one is less than five away from a cube).

    What is the value of CUBE?

    [teaser2156]

     
    • Jim Randell's avatar

      Jim Randell 9:32 am on 20 June 2023 Permalink | Reply

      This Python program uses the [[ SubstitutedExpression() ]] solver from the enigma.py library to find candidate values that are each individually within 5 of a cube number. We then check the answers for cases where three of the distances are 0.

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

      Run: [ @replit ]

      from enigma import (SubstitutedExpression, iroot, printf)
      
      # distance to nearest kth root
      def dist(n, k=3):
        x = iroot(n, k)
        return min(n - x**k, (x + 1)**k - n)
      
      # make an alphametic puzzle
      p = SubstitutedExpression(
        [
          # each must be less than 5 away from a cube
          "dist(THREE) < 5",
          "dist(CAN) < 5",
          "dist(BE) < 5",
          "dist(CUBES) < 5",
        ],
        answer="(THREE, CAN, BE, CUBES)",
        env=dict(dist=dist),
        verbose=0
      )
      # solve the puzzle
      for ans in p.answers():
        # count the distances
        ds = list(dist(x) for x in ans)
        # three must have distance 0
        if ds.count(0) != 3: continue
        # output solution
        CUBE = ans[-1] // 10
        printf("CUBE = {CUBE} {ans}")
      

      Solution: CUBE = 1968.

      The numbers are:

      THREE = 74088 = 42³
      CAN = 125 = 5³
      BE = 68 = 4³ + 4
      CUBES = 19683 = 27³

      Like

    • Frits's avatar

      Frits 1:57 pm on 20 June 2023 Permalink | Reply

      More messy (the reorder=0 isn’t even necessary).

         
      #!/usr/bin/env pypy -m enigma -r
       
      SubstitutedExpression
      
      # each must be a cube or less than 5 away from a cube
      "(c1 := is_cube_p(BE)) or \
        BE - (r := int(BE**(1/3)))**3 < 5        or (r + 1)**3 - BE < 5"
      "(c2 := is_cube_p(CUBES)) or (c1 and \
        (CUBES - (r := int(CUBES**(1/3)))**3 < 5 or (r + 1)**3 - CUBES < 5))"
      "(c3 := is_cube_p(CAN)) or (c1 and c2 and \
        (CAN - (r := int(CAN**(1/3)))**3 < 5     or (r + 1)**3 - CAN < 5))"
      "is_cube_p(THREE) or (c1 and c2 and c3 and \
        (THREE - (r := int(THREE**(1/3)))**3 < 5 or (r + 1)**3 - THREE < 5))"
      
      --answer="(THREE, CAN, BE, CUBES)"
      
      # [optional] less verbose output
      --template=""
      
      --reorder=0
      

      Like

      • Frits's avatar

        Frits 7:02 pm on 20 June 2023 Permalink | Reply

        The 2 missing ” and ” don’t cause a syntax error.

        Like

      • Jim Randell's avatar

        Jim Randell 8:26 am on 21 June 2023 Permalink | Reply

        @Frits: I think I see what this is doing. (I removed the extraneous trailing commas, and fixed up some missing and keywords).

        But I think it would allow the case where all four of the words were cubes.


        This is what my [[ SubstitutedExpression ]] run file looks like:

        Run: [ @replit ]

        #! python3 -m enigma -rr
        
        SubstitutedExpression
        
        # distance to nearest kth root
        --code="def _dist(n, k=3): x = iroot(n, k); return min(n - x**k, (x + 1)**k - n)"
        --code="dist = cache(_dist)"
        
        # check cube distance is less than 5 (if flag) or 0
        --code="def check(n, f): x = dist(n); return (0 < x < 5 if f else x == 0)"
        
        # n = 1..4 denotes which statement is not a cube
        --invalid="0|5|6|7|8|9,n"
        
        # each is less than 5 away from a cube
        "check({THREE}, {n} ==  1)"
        "check({CAN}, {n} == 2)"
        "check({BE}, {n} == 3)"
        "check({CUBES}, {n} == 4)"
        
        --distinct="ABCEHNRSTU"
        --answer="CUBE"
        --template="(THREE, CAN, BE, CUBES)"
        --solution="n"
        

        Like

    • GeoffR's avatar

      GeoffR 5:43 pm on 20 June 2023 Permalink | Reply

      Using Frits method of solution i.e.each number must be a cube or less than 5 away from a cube.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..9:T; var 0..9:H; var 0..9:R; var 0..9:E;
      var 1..9:C; var 0..9:A; var 0..9:N; var 1..9:B;
      var 0..9:U; var 0..9:S;
      
      constraint all_different ([T, H, R, E, C, A, N, B, U, S]);
      
      % Four numbers are BE, CAN, CUBES, THREE
      var 10..99:BE == 10*B + E;
      var 100..999:CAN == 100*C + 10*A + N;
      var 10000..99999:CUBES == 10000*C + 1000*U + 100*B + 10*E + S;
      var 10000..99999:THREE == 10000*T + 1000*H + 100*R + 11*E;
      
      % Required answer is CUBE
      var 1000..9999:CUBE == 1000*C + 100*U + 10*B + E; 
      
      % Sets of cubes for 2-digit, 3-digit and 5-digit numbers
      set of int: cb2 = {27, 64};
      set of int: cb3 = {n * n * n | n in 5..9};
      set of int: cb5 = {n * n * n | n in 22..46};
      
      % Three of the numbers are cubes
      constraint sum([THREE in cb5, CAN in cb3, BE in cb2, CUBES in cb5]) == 3;
      
      % Allow for the fourth number to be less than five away from a cube
      % Number BE
      constraint BE in cb2 \/ (BE - 1) in cb2  \/ (BE - 2) in cb2 
      \/ (BE - 3) in cb2   \/ (BE - 4) in cb2  \/ (BE + 1) in cb2 
      \/ (BE + 2) in cb2   \/ (BE + 3) in cb2  \/ (BE + 4) in cb2; 
      % Number CAN
      constraint CAN in cb3 \/ (CAN - 1) in cb3 \/ (CAN - 2) in cb3
       \/ (CAN - 3) in cb3  \/ (CAN - 4) in cb3 \/ (CAN + 1) in cb3 
       \/ (CAN + 2) in cb3  \/ (CAN + 3) in cb3 \/ (CAN + 4) in cb3;
      % Number THREE
      constraint THREE in cb5 \/ (THREE - 1) in cb5  \/ (THREE - 2) in cb5
       \/ (THREE - 3) in cb5  \/ (THREE - 4) in cb5  \/ (THREE + 1) in cb5 
       \/ (THREE + 2) in cb5  \/ (THREE + 3) in cb5  \/ (THREE + 4) in cb5;
      % Number CUBES
      constraint CUBES in cb5 \/ (CUBES - 1) in cb5 \/ (CUBES - 2) in cb5
       \/ (CUBES - 3) in cb5  \/ (CUBES - 4) in cb5 \/ (CUBES + 1) in cb5 
       \/ (CUBES + 2) in cb5  \/ (CUBES + 3) in cb5 \/ (CUBES + 4) in cb5;
                                                                                        
      solve satisfy;
      
      output["CUBE = " ++ show(CUBE)  ++ "\n" ++   
      "[THREE, CAN, BE, CUBES] = " ++ show ([THREE, CAN, BE, CUBES]) ];
      
      % CUBE = 1968
      % [THREE, CAN, BE, CUBES] = [74088, 125, 68, 19683]
      % ----------
      % ==========
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 11:52 am on 13 June 2023 Permalink | Reply
    Tags: by: Adrian Somerfield   

    Teaser 2177: Basic sum 

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

    You might look askance at the addition sum:

    But in fact each of the numbers is written in a different base. Just one of the four numbers is prime and just one is divisible by three. Also, when written in the normal decimal form, the last digits of the three numbers being added are all different, and the total is still a four-figure number.

    What is the total?

    [teaser2177]

     
    • Jim Randell's avatar

      Jim Randell 11:52 am on 13 June 2023 Permalink | Reply

      See also: Enigma 1358.

      This Python program collects numerical values of “1101” in various bases, such that the value is not more than 4 digits in decimal.

      It then looks for three of these values that sum to a fourth, and applies the remaining conditions.

      It runs in 56ms. (Internal runtime is 518µs).

      Run: [ @replit ]

      from enigma import (
        irange, inf, base2int, subsets, icount_exactly,
        is_prime, seq_all_different, join, printf
      )
      
      # is x divisible by 3?
      div3 = lambda x: x % 3 == 0
      
      # find values for <s> in various bases
      d = dict()
      for b in irange(2, inf):
        n = base2int('1101', base=b)
        if n > 9999: break
        d[n] = b
      
      # look for 3 of the values that sum to a 4th
      for ns in subsets(d.keys(), size=3, fn=list):
        t = sum(ns)
        if t < 1000 or t not in d: continue
        # the last digits of the summands (in base 10) are all different
        if not seq_all_different(n % 10 for n in ns): continue
        ns.append(t)
        # exactly one of the 4 numbers is divisible by 3
        if not icount_exactly(ns, div3, 1): continue
        # exactly one of the 4 numbers is prime
        if not icount_exactly(ns, is_prime, 1): continue
        # output solution
        bs = list(d[n] for n in ns)
        printf("{ns} = {t} [bases = {bs}]",
          ns=join(ns[:-1], sep=" + "),
          bs=join(bs, sep=", ", enc="()"),
        )
      

      Solution: The result of the sum is 7221 (in decimal).

      The sum is:

      1101 [base 6] = 253 [decimal] +
      1101 [base 9] = 811 [decimal] +
      1101 [base 18] = 6157 [decimal] =
      1101 [base 19] = 7221 [decimal]

      Like

      • Frits's avatar

        Frits 12:01 pm on 14 June 2023 Permalink | Reply

        @Jim, you don’t seem to have a proper check on “the total is still a four-figure number”.

        Like

    • GeoffR's avatar

      GeoffR 10:21 pm on 13 June 2023 Permalink | Reply

      
      from enigma import is_prime, all_different
      from itertools import combinations
      
      # max base for 4 digits is 21
      # sum is n1 + n2 + n3 = n4
      for b1, b2, b3, b4 in combinations(range(2, 22),4):
        n4 = int('1101', base = b4)
        # the total n4 is a four-figure number
        if n4 < 10000:
          n1 = int('1101', base = b1)
          n2 = int('1101', base = b2)
          n3 = int('1101', base = b3)
          # one of the four numbers is prime
          if sum  ((is_prime(n1), is_prime(n2), is_prime(n3),\
                    is_prime(n4))) == 1:
            # last digits of the three summands are all different
            if all_different( str(n1)[:-1], str(n2)[:-1], \
                              str(n3)[:-1]):
              # one of the four numbers is divisible by three
              if sum((n1 % 3 == 0, n2 % 3 == 0, n3 % 3 == 0, \
                      n4 % 3 == 0))== 1:
                # check total of sum is correct
                if n4 == n1 + n2 + n3:
                  print(f"Sum is : {n1} + {n2} + {n3} = {n4}.")
                  print(f"The bases are {b1}, {b2}, {b3} and {b4}.")
      
      # Sum is : 253 + 811 + 6157 = 7221.
      # The bases are 6, 9, 18 and 19.
      
      

      Like

    • GeoffR's avatar

      GeoffR 8:38 am on 14 June 2023 Permalink | Reply

      Quite slow in MiniZinc – nearly 3 sec with the Chuffed Solver.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      predicate is_prime(var int: x) = 
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
      ((i < x) -> (x mod i > 0));
      
      % Four numbers with four different number bases
      % min LB = 8 + 4 + 0 + 1 = 13
      % max UB = 21**3 + 21**2 + 0 + 1 = 9703
      var 13..9703:N1; var 13..9703:N2; var 13..9703:N3; var 13..9703:N4;
      var 2..21:b1; var 2..21:b2; var 2..21:b3; var 2..21:b4;
       
      % put bases in order
      constraint b2 > b1 /\ b3 > b2 /\ b4 > b3;
      
      % Form 4 numbers in 4 different bases in format 1101
      constraint N1 == 1 * b1 * b1 * b1 + 1 * b1 * b1 + 0 + 1;
      constraint N2 == 1 * b2 * b2 * b2 + 1 * b2 * b2 + 0 + 1;
      constraint N3 == 1 * b3 * b3 * b3 + 1 * b3 * b3 + 0 + 1;
      constraint N4 == 1 * b4 * b4 * b4 + 1 * b4 * b4 + 0 + 1;
      
      % Main sum
      constraint N1 + N2 + N3 == N4;
      
      % One of the four numbers is prime
      constraint sum([is_prime(N1), is_prime(N2), is_prime(N3), is_prime(N4)]) == 1;
      
      % One of the four numbers is prime is exactly divisible by three
      constraint sum([N1 mod 3 == 0, N2 mod 3 == 0, N3 mod 3 == 0, N4 mod 3 == 0]) == 1;
      
      % the last digits of the three summands are different
      constraint all_different([N1 mod 10, N2 mod 10, N3 mod 10]);
      
      solve satisfy;
      
      output["Total is " ++ show(N4) ++ "\n" 
      ++ "Sum is " ++ show(N1) ++ " + " ++ show(N2) ++ " + " ++ show(N3) ++ " = " ++ show(N4)
      ++ "\n" ++ "Bases are " ++ show([b1, b2, b3, b4])];
      
      % Total is 7221
      % Sum is 253 + 811 + 6157 = 7221
      % Bases are [6, 9, 18, 19]
      % ----------
      % ========== 
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 7:40 am on 30 May 2023 Permalink | Reply
    Tags: by: Adrian Somerfield   

    Teaser 2100: Uncle Hex 

    From The Sunday Times, 15th December 2002 [link]

    The standard hexadecimal notation used in some computations needs 16 “hex-digits”, so it uses 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E and F — e.g. the hex-number DEC15 represents the decimal number: 13×16⁴ + 14×16³ + 12×16² + 1×16 + 5 = 912405.

    Of course, only a few dates (like today’s) can look like a hex-number in that way (with some dates having a choice of hex-number, like DEC08/DEC8). My Uncle Hex and I have noticed we both have birthdays that look like hex-numbers. We have each worked out a decimal number that our birthday can represent and, comparing notes, we see that between them those two decimal numbers use each of the digits 0 to 9 at least once. Uncle Hex’s next birthday comes before mine.

    When is Uncle Hex’s birthday?

    Teaser 21002105 were originally published in The Sunday Times with the numbers 30003005.

    [teaser2100]

     
    • Jim Randell's avatar

      Jim Randell 7:41 am on 30 May 2023 Permalink | Reply

      This Python program generates all the dates in a leap year, and finds those that give viable “hex-dates” (obviously it would be more efficient to just consider months that consist entirely of hex digits).

      We then look for a pair of hex-dates that have values that between them use all 10 digits when represented in decimal form.

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

      Run: [ @replit ]

      from datetime import (date, timedelta)
      from enigma import (repeat, inc, sprintf, base2int, catch, subsets, union, int2base, printf)
      
      # generate possible "hex-dates"
      def generate():
        # month names
        months = "? JAN FEB MAR APR MAY JUN JUL AUG SEP OCT NOV DEC".split()
        # consider dates in 2000 (a leap year)
        for d in repeat(inc(timedelta(days=1)), date(2000, 1, 1)):
          if d.year > 2000: break
          (m, d) = (months[d.month], d.day)
          for fmt in ["{m}{d}", "{m}{d:02d}"]:
            s = sprintf(fmt)
            v = catch(base2int, s, base=16)
            if v is not None:
              yield (s, v)
      
      # collect "hex-dates"
      d = dict(generate())
      
      # find pairs that use 10 different digits when expressed in decimal
      for ((k1, v1), (k2, v2)) in subsets(d.items(), size=2):
        ds = union(int2base(v, base=10) for v in (v1, v2))
        if len(ds) != 10: continue
        # output solution
        printf("{k1} -> {v1}; {k2} -> {v2}")
      

      Solution: Uncle Hex’s birthday is 4th February.

      The two dates are:

      FEB4 [base 16] = 65204 [base 10]
      DEC03 [base 16] = 912387 [base 10]

      The puzzle was set on 15th December, so the next of these dates to occur is 4th February.

      Like

      • Frits's avatar

        Frits 6:54 pm on 30 May 2023 Permalink | Reply

        @Jim, I don’t see the requirement that each “hex-date” has to use distinct digits.

        Like

        • Jim Randell's avatar

          Jim Randell 7:13 pm on 30 May 2023 Permalink | Reply

          I don’t know where that came from. The [[ is_duplicate() ]] test can be removed, and you still get the same answer.

          Like

      • Frits's avatar

        Frits 8:39 pm on 30 May 2023 Permalink | Reply

        Slow but more than three times faster with PyPy.

         
        from enigma import SubstitutedExpression, int2base
        
        months = "JAN FEB MAR APR MAY JUN JUL AUG SEP OCT NOV DEC"
        days = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
        
        # check for valid "hex-date"
        def check(i):
          s = int2base(i, base=16)
          if not (3 < len(s) < 6): return 0
          f = months.find(s[:3])
          if f < 0: return 0
          
          d = s[3:]
          if not d.isnumeric(): return 0
          d = int(d)
          
          f //= 4            # so we have indices 0-11
          if not (0 < d <= days[f]): return 0
          
          return 100 * f + d
          
          
        # the alphametic puzzle
        p = SubstitutedExpression(
          [
            # uncle HEX: UVWXYZ     me: SOMERF
            
            "UVWXYZ > 43680", # start from AAA1
            
            "check(UVWXYZ)",
            "len(set([U, V, W, X, Y, Z])) >= 4",
            
            "SOMERF > 43681", # start from AAA2
            
            # those numbers use each of the digits 0 to 9 at least once
            "len(set([U, V, W, X, Y, Z, S, O, M, E, R, F])) == 10",
            
            # my number
            "check(SOMERF)",
            
            # uncle Hex's next birthday comes before mine
            "0 < check(UVWXYZ) < check(SOMERF)",
          ],
          answer="int2base(UVWXYZ, base=16)",
          d2i="",
          distinct="",
          env=dict(check=check),
          #reorder=0,
          verbose=0,    # use 256 to see the generated code
        )
        
        # print answers
        for (_, ans) in p.solve():
          print(f"Uncle Hex's birthday: {ans}")  
        

        Like

  • Unknown's avatar

    Jim Randell 9:08 am on 16 May 2023 Permalink | Reply
    Tags: by: Adrian Somerfield   

    Teaser 2218: Speed trap 

    From The Sunday Times, 20th March 2005 [link]

    In Ireland they have changed from miles to kilometres. In European spirt and always using the rule of thumb that five miles convert to eight kilometres, I note that FIVE miles will convert into HUIT kilometres. Also UNE miles equals roughly four-fifths of TWO kilometres.

    Here, letters consistently stand for the same digit, and no two letters stand for the same digit.

    In figures, how many kilometres do NINE miles convert to?

    [teaser2218]

     
    • Jim Randell's avatar

      Jim Randell 9:09 am on 16 May 2023 Permalink | Reply

      This Python program uses the [[ SubstitutedExpression() ]] solver from the enigma.py library to find values where FIVE / HUIT = 5 / 8, and then selects a solution with the minimum distance between UNE miles and 0.8× TWO kilometres.

      It runs in 63ms.

      Run: [ @replit ]

      from enigma import (SubstitutedExpression, Accumulator, printf)
      
      # make the alphametic problem
      p = SubstitutedExpression(
        ["div(FIVE * 8, 5) = HUIT"],
        answer="(UNE, TWO, FIVE, HUIT, NINE)",
        verbose=0
      )
      # solve it and collect answers
      r = Accumulator(fn=min, collect=1)
      for (s, ans) in p.solve():
        (UNE, TWO, FIVE, HUIT, NINE) = ans
        # difference between UNE miles and 0.8 TWO km (in km)
        r.accumulate_data(abs(1.6 * UNE - 0.8 * TWO), ans)
      
      # output minimal solutions
      for (UNE, TWO, FIVE, HUIT, NINE) in r.data:
        printf("FIVE ({FIVE}) miles = HUIT ({HUIT}) km")
        printf("diff(UNE ({UNE}) miles, 0.8x TWO ({TWO}) km) = {r.value:.3f} km")
        km = 1.6 * NINE
        printf("NINE ({NINE}) miles = {km:g} km")
        printf()
      

      Solution: NINE miles = 15512 km.

      We have:

      FIVE (4605) miles = HUIT (7368) km
      diff(UNE (395) miles, 0.8× TWO (812) km) = 17.600 km
      NINE (9695) miles = 15512 km

      Like

      • Frits's avatar

        Frits 11:57 am on 17 May 2023 Permalink | Reply

        @Jim, is there a reason why you didn’t use “accumulate=min” in SubstitutedExpression?

        Like

        • Jim Randell's avatar

          Jim Randell 12:45 pm on 17 May 2023 Permalink | Reply

          @Frits: I wanted to neaten up the output, and we are minimising a function of the answer parameter, so things end up a bit messier.

          But it is perfectly possible to do this:

          Run: [ @replit ]

          #! python3 -m enigma -rr
          
          SubstitutedExpression
          
          # FIVE miles is HUIT kilometres
          "div(HUIT * 5, 8) = FIVE"
          
          # UNE miles is roughly 4/5 of TWO kilometres
          --code="diff = lambda v1, v2: abs(1.6 * v1 - 0.8 * v2)"
          # answer is NINE miles, expressed as km
          --code="ans = lambda n: 1.6 * n"
          --answer="(diff(UNE, TWO), ans(NINE), UNE, TWO, FIVE, HUIT, NINE)"
          --accumulate="min"
          

          Like

    • Frits's avatar

      Frits 11:55 am on 17 May 2023 Permalink | Reply

       
      % A Solution in MiniZinc
      include "globals.mzn";
       
      var 1..9:F; var 0..9:I ; var 0..9:V ; var 0..9: E; var 1..9: H; 
      var 1..9:U; var 1..9:T ; var 0..9:W ; var 0..9: O; var 1..9: N; 
      
      function var int: toNum(array[int] of var int: a) =
                let { int: len = length(a) }
                in
                sum(i in 1..len) (
                  ceil(pow(int2float(10), int2float(len-i))) * a[i]
                );  
      
      % the digits are all different
      constraint all_different ([F,I,V,E,H,U,T,W,O,N]);
      
      %  FIVE miles will convert into HUIT kilometres
      constraint 1.6 * toNum([F, I, V, E]) == toNum([H, U, I, T]);
      
      solve minimize(abs(1.6 * toNum([U, N, E]) - 0.8 * toNum([T, W, O])));
       
      output["NINE = " ++ show(1.6 * toNum([N, I, N, E])) ++
             " diff = " ++ show(abs(1.6 * toNum([U, N, E]) - 0.8 * toNum([T, W, O])))];
      

      Like

  • Unknown's avatar

    Jim Randell 8:18 am on 21 February 2023 Permalink | Reply
    Tags: by: Adrian Somerfield   

    Teaser 2716: Millennial squares 

    From The Sunday Times, 12th October 2014 [link] [link]

    I asked my class to take some pieces of card and to write a digit on each side of each card so that any year of this millennium that is a perfect square could be spelt out using four of the cards. One clever pupil achieved this with the smallest number of cards possible. He also pointed out that with his cards he could go way beyond the end of this millennium — in fact he had designed them so that, when trying to make this list of consecutive square years yet to come, he was able to go as far as possible with that number of cards.

    What is the last square he could make?

    [teaser2716]

     
    • Jim Randell's avatar

      Jim Randell 8:19 am on 21 February 2023 Permalink | Reply

      First we note that the digit 9 can use the same symbol as the digit 6, so we only need to consider the symbols 0-8. (Although it turns out that we get the same answer even if the digits 6 and 9 use different symbols).

      We can quickly find a theoretical minimum collection of symbols required to express the squares between 2001 – 3000 by considering the multiset union of each of those squares (considered as a multiset of corresponding symbols). And with two symbols per card we can determine the theoretical minimum number of cards required to accommodate these symbols. (Although this does not tell us that an appropriate set of cards can be constructed).

      We can then start adding in additional squares until we can no longer fit all the required symbols on the required number of cards, and this gives us a theoretical maximum constructible square to answer the puzzle.

      We can then check that this solution is achievable by constructing a collection of cards of the appropriate size that allows all the required squares to be made.

      This Python program runs in 56ms. (Internal runtime is 809µs).

      Run: [ @replit ]

      from enigma import (irange, inf, sq, nsplit, join, multiset, divc, delete, cache, printf)
      
      # symbols used to represent digits (6 and 9 are the same symbol)
      sym = dict(zip(irange(0, 9), "0123456786"))
      
      # words to be spelled out
      word = cache(lambda n: join(sym[d] for d in nsplit(n)))
      
      # find the minimum number of cards required (n symbols per card)
      min_cards = lambda m, n=2: divc(m.size(), n)
      
      # collect the symbols required to make the initial set of numbers
      ns = list(sq(i) for i in irange(45, 54))
      m = multiset()
      for n in ns:
        m.union_update(word(n))
      k = min_cards(m)
      printf("{k} cards = [{a} .. {b}] ({s} symbols)", a=ns[0], b=ns[-1], s=m.size())
      
      # add extra numbers until another card is required
      for i in irange(55, inf):
        n = sq(i)
        w = word(n)
        m_ = m.union(w)
        k_ = min_cards(m_)
        printf("{k_} cards = [{a} .. {b}] ({s} symbols)", a=ns[0], b=n, s=m_.size())
        if k_ > k: break
        ns.append(n)
        m = m_
      
      # now try to construct a set of <k> cards that covers the numbers <ns>
      
      # can we make word <w> with cards <cs>
      def make(w, cs):
        if not w:
          return True
        x = w[0]
        for (i, c) in enumerate(cs):
          if x in c and make(w[1:], delete(cs, [i])):
            return True
        return False
      
      # make a set of <k> cards, the can make words <ws>, symbol counts in <m>
      def cards(k, ws, m, cs=[]):
        # are we done?
        if k == 0:
          if all(make(w, cs) for w in ws):
            yield tuple(sorted(cs))
        elif k > 0 and m:
          # make the next card
          x = m.min()
          for y in m.keys():
            if x < y:
              c = x + y
              if (not cs) or (not c < cs[-1]):
                yield from cards(k - 1, ws, m.difference([x, y]), cs + [c])
      
      # try to make a <k>-set of cards that covers numbers <ns>
      if m.size() % 2 == 1: m.add('?')
      for cs in cards(k, list(word(n) for n in ns), m):
        printf("cards = {cs}", cs=join(cs, sep=" ", enc="()"))
        break
      

      Solution: The last square that he could make was 3721.


      To make the squares 2025 – 2916 requires a collection of 13 symbols, so we need 7 cards to accommodate these.

      And if we also include the squares up to 3721 then we need a collection of 14 symbols, which still requires 7 cards.

      But to also include the next square (3844) would require 15 symbols (as we need to have two 4’s), and this cannot be accommodated with 7 cards.

      There are many sets of 7 cards that allow the squares 2025 – 3721 to be made, for example:

      (02 07 13 18 26 39 45)

      (And this set works if 6 and 9 are different digits, or if they are the same digit).

      Like

  • Unknown's avatar

    Jim Randell 8:40 am on 16 February 2023 Permalink | Reply
    Tags: by: Adrian Somerfield   

    Teaser 2266: Planck play 

    From The Sunday Times, 26th February 2006 [link]

    Conventional measurements are based on units of mass (M), length (L) and time (T). Any speed, such as the speed of light (c), is a length divided by a time, and we say it has “dimensions” 0 in mass, +1 in length, −1 in time. Similarly, Planck’s Constant (h) involves a mass times an area divided by time, and so has dimensions +1, +2, −1; and the Gravitation Constant (G) has dimensions −1, +3, −2. It is possible to use c, h and G respectively as the basic triplet of units. If this is done, the dimensions of the metre are −1.5, 0.5 and 0.5.

    What are those of (a) the kilogram and (b) the second?

    [teaser2266]

     
    • Jim Randell's avatar

      Jim Randell 8:41 am on 16 February 2023 Permalink | Reply

      We can write the constants (c, h, G) in terms of the dimensions (M, L, T):

            M  L  T
      c = ( 0 +1 −1)
      h = (+1 +2 −1)
      G = (−1 +3 −2)
      

      And, if we invert the matrix we can instead express the dimensions (M, L, T) in terms of (c, h, G).

      The [[ Matrix ]] class in the enigma.py library provides some useful routines for manipulating 2d matrices, including matrix inversion.

      This Python program runs in 54ms. (Internal runtime is 3.1ms).

      Run: [ @replit ]

      from enigma import (Matrix, join, printf)
      
      # matrix of (c, h, G) in terms of (M, L, T)
      m = Matrix([
        # M   L   T
        ( 0, +1, -1), # c
        (+1, +2, -1), # h
        (-1, +3, -2), # G
      ])
      
      # invert the matrix
      r = m.inv()
      
      # the dimensions (M, L, T) are the rows of the result
      for (k, ds) in zip(['kg', 'm', 's'], r.rows()):
        printf("{k} -> {ds}", ds=join(ds, sep=", ", enc="()"))
      

      Solution: The (c, h, G) dimensions are: (a) kg = (0.5, 0.5, −0.5); (b) s = (-2.5, 0.5, 0.5).

      Like

    • Hugh Casement's avatar

      Hugh Casement 2:39 pm on 16 February 2023 Permalink | Reply

      In fact since at least 2006 the speed of light has been a defined quantity,
      so that effectively the metre is defined in terms of the second.
      Since 2018 Planck’s constant has also been a defined quantity:
      was Adrian Somerfield a visionary?

      However, the Newtonian gravitational constant is known only to low precision,
      so would not make a good primary unit. And to have fractional dimensions for most of the familiar units does also not seem a good idea. Perhaps one should instead choose the Rydberg constant (inverse metres) or the related Hartree energy (joules, dimensions 1, 2, -2) for which we have very precise values.

      If I have not forgotten how to invert a matrix, we would then have (respectively)
      mass (-1, 1, 1); length ( 0, 0, -1); time (-1, 0, -1) or
      mass (-2, 0, 1); length ( 1, 1, -1); time 0, 1, 1).

      Like

  • Unknown's avatar

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

    Teaser 1948: Square ladder 

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


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

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

    Fill in the grid.

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

    [teaser1948]

     
    • Jim Randell's avatar

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

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

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

      It runs in 47ms.

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

      Solution: The completed grid is:

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

      Like

    • Frits's avatar

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

      I didn’t use recursion as depth is limited.

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

      Like

      • Jim Randell's avatar

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

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

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

        Like

        • Frits's avatar

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

          You are right.

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

          Like

    • GeoffR's avatar

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

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

      Like

  • Unknown's avatar

    Jim Randell 10:55 am on 3 November 2020 Permalink | Reply
    Tags: by: Adrian Somerfield   

    Teaser 1929: Square trip 

    From The Sunday Times, 5th September 1999 [link]

    My car has an odometer, which measures the total miles travelled. It has a five-figure display (plus two decimal places). There is also a “trip” counter with a three-figure display.

    One Sunday morning, when the car was nearly new, the odometer showed a whole number which was a perfect square and I set the trip counter to zero. At the end of that day the odometer again showed a whole number that was a perfect square, and the trip counter showed an odd square.

    Some days later, the display on the odometer was four times the square which had been displayed on that Sunday evening, and once again both displays were squares.

    What were the displays on that last occasion?

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

    [teaser1929]

     
    • Jim Randell's avatar

      Jim Randell 10:55 am on 3 November 2020 Permalink | Reply

      I supposed that the initial reading was less than 1000 miles, and the car travels less than 1000 miles on the particular Sunday.

      This Python program runs in 49ms.

      Run: [ @repl.it ]

      from enigma import irange, inf, is_square, printf
      
      def solve():
        # consider initial readings (when the car was nearly new)
        for a in irange(1, 31):
          r1 = a * a
      
          # at the end of the day
          for b in irange(a + 1, inf):
            r2 = b * b
            # the trip reading is an odd square
            t2 = r2 - r1
            if t2 > 1000: break
            if not(t2 % 2 == 1 and is_square(t2)): continue
      
            # some days later the odometer reads 4 times as far
            r3 = 4 * r2
            # and the trip reading is also a square
            t3 = (r3 - r1) % 1000
            if not is_square(t3): continue
      
            yield ((r1, 0), (r2, t2), (r3, t3))
      
      # find the first solution
      for ((r1, t1), (r2, t2), (r3, t3)) in solve():
        printf("{r1} + {t1}; {r2} + {t2}; {r3} + {t3}")
        break
      

      Solution: The displays were 2500, and 100.

      The trip was set to zero when the car had done 400 miles (= 20²), so it was still fairly new.

      Then after another 225 miles, the odometer would read 625 miles (= 25²), and the trip would read 225 (= 15²).

      The final reading was taken after another 1875 miles. The odometer reads 2500 miles (= 50²), and the trip reads the 3 least significant digits of 2100, which are 100 (= 10²).

      Like

      • Jim Randell's avatar

        Jim Randell 2:19 pm on 3 November 2020 Permalink | Reply

        As r1, r2, t2 are all squares, such that: r1 + t2 = r2 we can solve this puzzle using Pythagorean triples.

        Run: [ @repl.it ]

        from enigma import pythagorean_triples, is_square, printf
        
        # consider pythagorean triples
        for (x, y, z) in pythagorean_triples(100):
          # readings
          (r1, t1) = (y * y, 0)
          (r2, t2) = (z * z, x * x)
          if not(r1 < 1000 and t2 < 1000 and t2 % 2 == 1): continue
          r3 = 4 * r2
          t3 = (r3 - r1) % 1000
          if not is_square(t3): continue
          # output solution
          printf("{r1} + {t1}; {r2} + {t2}; {r3} + {t3} [{x}, {y}, {z}]")
        

        And it is probably not a great surprise that there is a (3, 4, 5) triangle hiding in the solution.

        Like

  • Unknown's avatar

    Jim Randell 8:57 am on 25 October 2020 Permalink | Reply
    Tags: by: Adrian Somerfield   

    Teaser 1923: Get back to me 

    From The Sunday Times, 25th July 1999 [link]

    I met a nice girl at a party and asked for her phone number. To prove that she was no pushover she made me work for it.

    “My number has seven digits, all different”, she told me. “If you form the largest number you can with those seven digits and subtract from it the reverse of that largest number, then you get another seven-digit number”, she added.

    “Then if you repeat the process with that new seven-digit number, you get another seven-digit number”, she added. “And if you repeat the process enough times you’ll get back to my phone number”.

    This information did enable me to get back to her!

    What is her telephone number?

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

    [teaser1923]

     
    • Jim Randell's avatar

      Jim Randell 8:58 am on 25 October 2020 Permalink | Reply

      When we apply the process to a number the order of the digits does not matter, as we immediately reorder the digits to make the largest possible number, and it’s reverse. So we only need to consider the possible collections of 7 distinct digits. If the same set of digits pops out of the process after several applications we have found a solution.

      As we keep applying the process we must eventually get to a collection of digits we have seen before (as there are only a finite number of collections of 7 digits). So if we haven’t found a solution by the time we get a repeated set of digits, then we are never going to find one.

      This Python program runs in 53ms.

      Run: [ @repl.it ]

      from enigma import subsets, irange, inf, nconcat, nsplit, ordered, printf
      
      # check the process, using a sequence of 7 ordered digits
      def check(ds):
        seen = set()
        ss = ds
        for i in irange(1, inf):
          if ss in seen: return None
          seen.add(ss)
          # make the largest number, and it's reverse
          n = nconcat(ss[::-1])
          r = nconcat(ss)
          # and subtract them
          s = n - r
          # are the digits in s the starting digits?
          ss = ordered(*(nsplit(s)))
          if len(ss) != 7: return None
          if i > 2 and ss == ds: return s
      
      # choose the 7 different digits in the phone number
      for ds in subsets(irange(0, 9), size=7):
        n = check(ds)
        if n is not None:
          printf("number = {n:07d}")
      

      Solution: The telephone number is: 7509843.

      Repeated application of the process yields:

      7509843: 9875430 − 0345789 = 9529641
      9529641: 9965421 − 1245699 = 8719722
      8719722: 9877221 − 1227789 = 8649432
      8649432: 9864432 − 2344689 = 7519743
      7519743: 9775431 − 1345779 = 8429652
      8429652: 9865422 − 2245689 = 7619733
      7619733: 9776331 − 1336779 = 8439552
      8439552: 9855432 − 2345589 = 7509843

      So we have to apply the process 8 times.

      Like

    • Frits's avatar

      Frits 2:24 pm on 27 October 2020 Permalink | Reply

      # nice girl's phone number abcdefg
      #
      # last transformation:
      #
      # h1h2h3ml3l2l1 = abcdefg + l1l2l3mh3h2h1
      #
      # c1...c5 carry bits
      #
      # h1 = a + l1
      # h2 = b + l2 + c5
      # h3 = c + l3 + c4 - 10*c5
      # m  = d + m  + c3 - 10*c4
      # l3 = e + h3 + c2 - 10*c3
      # l2 = f + h2 + c1 - 10*c2
      # l1 = g + h1 - 10*c1
      #
      # l1 < h1 --> c1 = 1
      # l2 < h2 + 1 --> c2 = 1
      # l3 < h3 + 1 --> c3 = 1
      # m = d + m + 1 - 10*c4 --> d = 10*c4 - 1 --> c4 = 1 --> d = 9
      #
      # h1 = a + l1 = a + g + h1 - 10 --> a + g = 10
      # h2 = b + l2 + c5 = b + f + h2 - 9 + c5 --> b + f = 9 - c5
      # h3 = c + l3 + 1 - 10*c5 = c + e + h3 - 9 + 1 - 10*c5 --> c + e = 8 + 10*c5
      # --> c5 = 0 and c + e = 8
      

      With A+G = 10, B+F = 9, C+E = 8, D = 9 enigma [[SubstitutedExpression]] leaves 64 ABCDEFG combinations to check.

      Like

      • Frits's avatar

        Frits 2:47 pm on 27 October 2020 Permalink | Reply

        Don’t know why I didn’t use carry bit c6 but the result is the same (c6 = 0).

        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