Design a site like this with WordPress.com
Get started

Tagged: by: Susan Bricket Toggle Comment Threads | Keyboard Shortcuts

  • Jim Randell 4:35 pm on 30 September 2022 Permalink | Reply
    Tags: by: Susan Bricket   

    Teaser 3132: Bilateral symmetry 

    From The Sunday Times, 2nd October 2022 [link] [link]

    My son, at a loose end after A-levels, asked me for a mental challenge. As we’d been discussing palindromes, I suggested he try to find an arrangement of the digits 1 to 9 with the multiplication symbol “×” to give a palindrome as the answer, and he came up with:

    29678 × 1453 = 43122134.

    I said: “Now try to find the smallest such palindromic product starting in 4, where the last digit of the smallest number is still 3”. He found that smallest product, and, interestingly, if he added the two smaller numbers instead of multiplying them, then added 100, he also got a palindrome.

    What is the smallest product?

    [teaser3132]

     
    • Jim Randell 4:55 pm on 30 September 2022 Permalink | Reply

      Using the [[ SubstitutedExpression() ]] solver from the enigma.py library.

      This Python program runs in 98ms.

      Run: [ @replit ]

      from enigma import (
        Accumulator, SubstitutedExpression, irange,
        is_npalindrome as is_npal, sprintf as f, printf
      )
      
      # find the smallest product
      r = Accumulator(fn=min, collect=1)
      
      # symbols to use
      syms = "ABCDEFGHI"
      
      n = len(syms)
      for i in irange(1, n // 2):
      
        # construct the alphametic puzzle; X < Y
        (X, Y) = (syms[:i], syms[i:])
        (x, y) = (X[-1], Y[-1])
        # X * Y is palindromic and starts (and ends) in the digit 4
        exprs = [ f("is_npal({X} * {Y})"), f("({x} * {y}) % 10 = 4") ]
        if len(X) == len(Y): exprs.append(f("{X[0]} < {Y[0]}"))
        p = SubstitutedExpression(
          exprs,
          digits=irange(1, 9),  # digits are 1-9
          s2d={ x: 3 },  # final digit of X is 3
          answer=f("({X}, {Y})"),
          env=dict(is_npal=is_npal),
        )
        # solve it
        for (s, (x, y)) in p.solve(verbose=0):
          z = x * y
          printf("[{x} * {y} = {z}]")
          r.accumulate_data(z, (x, y))
      
      # output solution
      printf("min product = {r.value}")
      for (x, y) in r.data:
        v = x + y + 100
        printf("  = {x} * {y}; {x} + {y} + 100 = {v} [{s}palindrome]", s=('' if is_npal(v) else 'not '))
      

      Solution: The smallest product is 40699604.

      Ignoring the final palindromic addition check, there are 3 candidate palindromic products that meet the criteria (in decreasing order)

      424393424 = 7163 × 59248
      43122134 = 1453 × 29678
      40699604 = 23 × 1769548

      The final one gives the answer to the puzzle, and is also the only one where the sum of the multiplicands and 100 is also palindromic.

      There are also two further palindromic products where the larger of the multiplicands ends in the digit 3:

      449757944 = 56219743 × 8
      49900994 = 167453 × 298

      Like

      • Frits 10:22 am on 1 October 2022 Permalink | Reply

        @Jim,

        I expected “for i in irange(5, n – 1):” ( where the last digit of the smallest number is still 3)

        Like

    • GeoffR 10:10 am on 3 October 2022 Permalink | Reply

      The only way I could find a MiniZinc solution was to assume that one of the multipliers was two digits long, so this is not a rigorous solution. Although I coded requirements for the second palindrome, as stated in the teaser, I found it was not strictly necessary to find the smallest palindromic product.

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      % re-using Frits' toNum function
      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]
                );
                
      % Digits for the two numbers being multiplied together
      % which are AB and CDEFGHI
      var 1..9:A; var 1..9:B; var 1..9:C; var 1..9:D; var 1..9:E; 
      var 1..9:F; var 1..9:G; var 1..9:H; var 1..9:I;
      
      constraint all_different ([A,B,C,D,E,F,G,H,I]);
      
      var 10..99:AB;
      var 1000000.. 9999999:CDEFGHI;
      
      % last digits of the two numbers 
      constraint B == 3 /\ I == 8;
      
      % abcdefgh - main product
      var 1..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 1..9:h;
      
      % mnopqrst - 2nd palindrome
      var 1..9:m; var 0..9:n; var 0..9:o; var 0..9:p;
      var 0..9:q; var 0..9:r; var 0..9:s; var 1..9:t;
      
      % Two palindromes
      var 40000000..45000000:abcdefgh;
      var 1000000..2000000:mnopqrs;
      
      % Two numbers being multiplied together
      constraint AB == toNum([A,B]);
      constraint CDEFGHI == toNum([C,D,E,F,G,H,I]);
      
      % Main and 2nd palindromes
      constraint abcdefgh == toNum([a,b,c,d,e,f,g,h]);
      constraint mnopqrs == toNum([m,n,o,p,q,r,s]); 
      
      % check main product is palindromic
      constraint (a == 4 /\ h == 4) /\ b == g /\ c == f /\ d == e;
      
      % main palindromic product
      constraint CDEFGHI * AB == abcdefgh;
      
      % form 2nd palindrome 
      constraint mnopqrs == CDEFGHI + AB + 100;
      constraint m = s /\ n == r /\ o == q;
      
      % find smallest palindromic product
      solve minimize(abcdefgh);
      
      output["Smallest palindrome = " ++ show(abcdefgh) ++ "\n" ++
      "Sum is: " ++show(CDEFGHI) ++ " * " ++ show(AB) ++ " = " ++ 
       show(abcdefgh) ++ "\n2nd palindrome = "  ++ show(mnopqrs)];
      
      

      Like

    • NigelR 11:28 am on 3 October 2022 Permalink | Reply

      Shorter but not quicker! The palin lambda proves I was listening last week, though!!

      from itertools import combinations as comb, permutations as perm
      #test whether number 'num' is palindromic
      palin = lambda num:sum(str(num)[n]!=str(num)[-n-1] for n in range(len(str(num))//2)) == 0
      digs=['1','2','4','5','6','7','8','9']
      res=999999999
      #work through possible values for 'left' of two smaller numbers
      for i in range(1,8):
          for x in comb(digs,i):
              for y in perm(x):
                  l = int("".join(y))
                  #work through possible values for 'right' of two smaller numbers (ending in 3)
                  for v in perm([w for w in digs if w not in y]):
                      r=int("".join(v))*10+3
                      if r>l:continue   #number ending in 3 is smallest number
                      prod=l*r
                      #test for output conditions
                      if str(prod)[0]!='4':continue
                      if not palin(prod):continue
                      if not palin(l+r+100):continue
                      if prod<res:res=prod
      print('Smallest valid product is:', res)
      

      Like

      • NigelR 11:36 am on 3 October 2022 Permalink | Reply

        Given that the number ending in ‘3’ is the smaller of the two numbers, I could have made line 7
        ‘for i in range(5,8)’, which shaves a bit of time off.

        Like

      • Frits 3:19 pm on 3 October 2022 Permalink | Reply

        Easier: palin = lambda num: (s := str(num)) == s[::-1]

        The “for x .. for y ..” can be replaced by “for y in perm(digs, i):”

        Like

        • NigelR 12:31 pm on 4 October 2022 Permalink | Reply

          Thanks Frits . Much neater – and I now know how to assign a variable within an expression. Onwards and upwards!

          Like

      • Frits 10:57 pm on 3 October 2022 Permalink | Reply

        I spent some time in making a generic version of GeoffR’s Minizinc program.

        As the numFirst and numAsOf functions do not work with “var int” parameters I had to call them several times.

        Using the fact that the first digit of the largest number must be a 1 (as p1 + p2 plus 100 is palindromic and has to end in 1) didn’t help to bring the run time under one second.

         
        % A Solution in MiniZinc
        include "globals.mzn";
        
        % return <n>-th digit of number <a> with length<len>
        function var int: nthDigit(var int: a, var int: len, var int: n) =
          ((a mod pows[len + 2 - n]) div pows[len + 1 - n]);                        
                       
        % return number of the first <len> digits        
        function var int: numFirst(array[int] of var int: a, var int: len) =
          sum(i in 1..len) (pows[len + 1 - i] * a[i]);            
        
        % return number as of the <b>-th digit                        
        function var int: numAsOf(array[int] of var int: a, var int: b) =
          let { int: len = length(a) }in
               sum(i in b..len) (pows[len + 1 - i] * a[i]);  
        
        % count how many digits have a correct mirror digit              
        function var int: palin(var int: a, var int: len, var int: b) =
          sum(i in 1..b) (
              nthDigit(a, len, i) == nthDigit(a, len, len + 1 - i)
          );        
        
        % digits used in the two numbers
        var 1..9: a; var 1..9: b; var 1..9: c; var 1..9: d;
        var 1..9: e; var 1..9: f; var 1..9: g; var 1..9: h; var 1..9: i;
        
        % make a tables of powers of 10
        set of int: pows = {pow(10, j) | j in 0..8};
        
        constraint i == 8;  % largest number has to end in 8
        
        constraint all_different ([a, b, c, d, e, f, g, h, i]);
        
        var 1..9999: p1;           % smallest number
        var 1..99999999: p2;       % largest number
        var 1..999999999: prod;    % product
        var 8..9: L;               % length palindrome
        var 1..4: L1;              % length smallest number
        
        % set smallest number to p1
        constraint p1 == numFirst([a, b, c, d, e, f, g, h, i], L1);
        % set largest number to p2          
        constraint p2 == numAsOf([a, b, c, d, e, f, g, h, i], L1 + 1);
        
        constraint p1 mod 10 == 3;    % last digit of smallest number is 3
        
        % first digit of product must be a 4  (needed for performance)
        constraint nthDigit(prod, L, 1) == 4;
                   
        constraint prod == p1 * p2;
        
        % set length variable L
        constraint (prod  > 99999999 /\ L == 9) \/
                   (prod <= 99999999 /\ L == 8);
        
        % product should be a palindrome
        constraint palin(prod, L, 4) == 4;
        
        % find smallest palindromic product
        solve minimize(prod);
         
        output["Smallest palindrome = " ++ show(prod)];
        

        Like

    • GeoffR 9:24 am on 4 October 2022 Permalink | Reply

      @Frits:
      An excellent full programming solution in MiniZinc, with some new functions.

      Like

    • GeoffR 8:50 am on 20 October 2022 Permalink | Reply

      # last digits of a = 3 and for b = 8 with a < b
      for a in range(13, 100, 10):  # UB assumed value
          # check 8-digit products up to teaser stated product
          for b in range(100008, 43122134 // a, 10):
              prod1 = a * b
              if prod1 < 40000004:continue
              
              # we need all digits in range 1..9 in prod1
              all_dig = str(a) + str(b)
              if '0' in all_dig:continue
              if len(set(all_dig)) != 9:continue
              
              # check product is a palindrome
              if str(prod1) == str(prod1)[::-1]:
                  # 2nd palindrome condition
                  pal2 = a + b + 100
                  if str(pal2) == str(pal2)[::-1]:
                      print(f"Sum is {a} * {b} = {prod1}")
      
      # Sum is 23 * 1769548 = 40699604
      
      
      
      

      Like

  • Jim Randell 4:50 pm on 8 July 2022 Permalink | Reply
    Tags: by: Susan Bricket   

    Teaser 3120: Bus stop blues 

    From The Sunday Times, 10th July 2022 [link] [link]

    While waiting for buses, I often look out for interesting number plates on passing cars. From 2001 the UK registration plate format has been 2 letters + a 2-digit number + 3 more letters, the digits being last two of the year of registration with 50 added after six months (for example in 2011, the possible numbers were 11 and 61). I spotted one recently with its five letters in alphabetical order, all different and with no vowels. Looking more closely, I saw that if their numerical positions in the alphabet (A = 1, B = 2 etc.) were substituted for the 5 letters, their sum plus 1 was the 2-digit number and the sum of their reciprocals was equal to 1.

    Find the 7-character registration.

    [teaser3120]

     
    • Jim Randell 4:59 pm on 8 July 2022 Permalink | Reply

      I used the [[ reciprocals() ]] function from the enigma.py library (originally written for Enigma 348).

      This Python program runs in 63ms. (Internal run time is 174µs).

      Run: [ @replit ]

      from enigma import (reciprocals, printf)
      
      # letters (1-indexed)
      letters = "?ABCDEFGHIJKLMNOPQRSTUVWXYZ"
      
      # vowels: A=1, E=5, I=9, O=15, U=21
      vowels = set(letters.index(x) for x in "AEIOU")
      
      # find 5 reciprocals that sum to 1
      for ns in reciprocals(5, M=26, g=1):
        # no vowels allowed
        if vowels.intersection(ns): continue
        # calculate the year
        y = sum(ns) + 1
        if not (1 < y < 23 or 50 < y < 72): continue
        # output the registration
        (A, B, X, Y, Z) = (letters[n] for n in ns)
        printf("reg = [{A}{B} {y:02d} {X}{Y}{Z}]")
      

      Solution: The registration is: BD 51 HLX.

      Note that the “vowels” restriction is not necessary if the restriction on the year number being within [02, 22] or [51, 71] is observed.

      Like

    • Frits 6:39 pm on 8 July 2022 Permalink | Reply

         
      from enigma import SubstitutedExpression
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
          # its five letters converted to numerical positions
          # AB, CD, EF, GH, IJ
          "1 < AB < 23",
          "AB < CD < 24",
          "CD < EF < 25",
          "EF < GH < 26",
          "GH < IJ < 27",
          
          # no vowels allowed, A=1, E=5, I=9, O=15, U=21
          "all(x not in {1, 5, 9, 15, 21} for x in [AB, CD, EF, GH, IJ])",
          # ranges for the sum
          "(AB + CD + EF + GH + IJ) < 22 or \
           49 < (AB + CD + EF + GH + IJ) < 72",
          # the sum of their reciprocals was equal to 1
          "1 / AB + 1 / CD + 1 / EF + 1 / GH + 1 / IJ == 1",
        ],
        answer="AB, CD, EF, GH, IJ",
        d2i="",
        distinct="",
        verbose=0,    # use 256 to see the generated code
      )
      
      # print answers
      for (_, ans) in p.solve():
        reg = chr(ord('A') + ans[0] - 1) + \
              chr(ord('A') + ans[1] - 1) + " "
        reg += str(sum(ans) + 1) + " "
        reg += chr(ord('A') + ans[2] - 1) + \
               chr(ord('A') + ans[3] - 1) + \
               chr(ord('A') + ans[4] - 1)
        print("registration =", reg)
      

      Like

      • Jim Randell 9:38 pm on 8 July 2022 Permalink | Reply

        Or we can use base 27 to make things a bit neater:

        #! python3 -m enigma -r
        
        SubstitutedExpression
        
        # allow digits 1-26
        --base=27
        # but exclude 0, 1, 5, 9, 15, 21
        --digits="2,3,4,6,7,8,10,11,12,13,14,16,17,18,19,20,22,23,24,25,26"
        
        # numbers are in increasing order
        "A < B" "B < X" "X < Y" "Y < Z"
        
        # reciprocals sum to 1
        "fraction(1, A,  1, B,  1, X,  1, Y,  1, Z) == (1, 1)"
        
        # check year
        --code="year = lambda n: (2 <= n <= 22) or (51 <= n <= 71)"
        "year(A + B + X + Y + Z + 1)"
        
        # output the registration
        --code="l = lambda x: int2base(x, base=27, digits='?ABCDEFGHIJKLMNOPQRSTUVWXYZ')"
        --code="n = lambda x: int2base(x, width=2)"
        --code="reg = lambda A, B, X, Y, Z: sprintf('{A}{B} {y} {X}{Y}{Z}', A=l(A), B=l(B), X=l(X), Y=l(Y), Z=l(Z), y=n(A + B + X + Y + Z + 1))"
        --answer="reg(A, B, X, Y, Z)"
        --template=""
        

        Like

    • GeoffR 8:27 pm on 8 July 2022 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % Omitting vowel values for A,E,I,O,U
      % Used to translate numerical letters in output(v,w,x,y,z) to letters
      int:B == 2; int:C == 3; int:D == 4; int:F == 6; int:G == 7;
      int:H == 8; int:J == 10; int:K == 11; int:L == 12; int:M == 13;
      int:N == 14; int:P == 16; int:Q == 17; int:R == 18; int:S == 19;
      int:T == 20; int:V == 22; int:W == 23; int:X == 24; int:Y == 25;
      int:Z == 26;
      
      % number plate format is v w num x y z  (num is 2 digits)
      var 2..26:v; var 2..26:w; var 2..26:x;
      var 2..26:y; var 2..26:z;
      
      % last 2 digits in number plate - range = 2001 to 2022 + 50
      var 01..72: num;
      
      set of int: letters = {B,C,D,F,G,H,J,K,L,M,N,P,Q,R,S,T,V,W,X,Y,Z};
      
      % Five number plate letters
      constraint v in letters /\ w in letters /\ x in letters
      /\ y in letters /\ z in letters;
      
      % five letters in number plate are in alphabetical order
      constraint w > v /\ x > w /\ y > x /\ z > y;
      
      % Reciprocals of letter values sum to 1
      constraint z * 1/v + z * 1/w + z * 1/x + z * 1/y + z/z == z;
      
      % Two middle digits are the sum of letter values plus 1
      constraint v + w + x + y + z + 1 == num;
      
      solve satisfy;
      
      output [ "Number plate = " ++ show( [v, w, num, x, y, z ] ) ];
      % uses translation table to convert numbers to letters
      
      
      

      Like

    • GeoffR 3:39 pm on 10 July 2022 Permalink | Reply

      
      from itertools import combinations
      import string
      
      # Dictionary mapping numbers to upper case letters
      DN = dict(zip(range(1, 27), string.ascii_uppercase))
      
      # omit values for vowels A, E, I, O, U
      vowels = {1, 5, 9, 15, 21}
      
      for C1 in combinations(set(range(1, 27)).difference(vowels), 5):
        a, b, c, d, e = C1
        #  five letters are in alphabetical order
        if a < b < c < d < e:
          # the sum of their reciprocals was equal to 1
          # i.e. 1/a + 1/b + 1/c + 1/d + 1/e == 1:
          if b*c*d*e + a*c*d*e + a*b*d*e + a*b*c*e + a*b*c*d == a*b*c*d*e:
            
            # last two digits of the year
            year2d = a + b + c + d + e + 1
            if year2d <= 22 or (51 <= year2d <= 72):
              print('Reg. No. = ', DN[a], DN[b], year2d, DN[c], DN[d], DN[e])
      
      
      

      Like

  • Jim Randell 4:05 pm on 29 October 2021 Permalink | Reply
    Tags: by: Susan Bricket   

    Teaser 3084: Face value 

    From The Sunday Times, 31st October 2021 [link] [link]

    Plato: I have written a different whole number (chosen from 1 to 9 inclusive) on each of the faces of one of my regular solids and have labelled each vertex with the product of the numbers on its adjacent faces. If I tell you the sum of those eight vertex labels, you can’t deduce my numbers, but if I rearrange the numbers on the faces and tell you the new sum, then you can deduce the numbers.

    Eudoxus: Tell me the new sum then.

    Plato: No, but I’ll tell you it’s a 10th power.

    Eudoxus: Aha! I know your numbers now.

    Plato: Yes, that’s right. But if I now told you the original sum, you couldn’t work out which numbers were originally opposite each other.

    What was the original sum?

    [teaser3084]

     
    • Jim Randell 5:01 pm on 29 October 2021 Permalink | Reply

      The cube is the only Platonic Solid [@wikipedia] with 8 vertices.

      This Python program runs in 51ms.

      Run: [ @replit ]

      from enigma import (irange, inf, subsets, partitions, group, unpack, peek, powers, printf)
      
      # generate face pairs and vertex sum for a set of numbers
      def arrange(ns):
        for fs in partitions(ns, 2, distinct=1):
          ((U, D), (L, R), (F, B)) = fs
          # calculate the values on the vertices
          vs = (
            U * L * F, U * R * F, U * L * B, U * R * B,
            D * L * F, D * R * F, D * L * B, D * R * B,
          )
          yield (ns, fs, sum(vs))
      
      # generate all possible face pairs and vertex sums
      def generate():
        for ns in subsets(irange(1, 9), size=6):
          yield from arrange(ns)
      
      # map vertex sum to sets of numbers
      d = group(generate(), by=unpack(lambda ns, fs, t: t), f=unpack(lambda ns, fs, t: ns), fn=set)
      
      # look for vertex sums that are 10th powers
      m = max(d.keys())
      for k in powers(1, inf, 10):
        if k > m: break
        vs = d.get(k, None)
        if vs is None: continue
        printf("{k} -> {vs}")
        assert len(vs) == 1
      
        # map vertex sums (for this set of numbers) to face pairs
        r = group(arrange(peek(vs)), by=unpack(lambda ns, fs, t: t), f=unpack(lambda ns, fs, t: fs))
      
        # look for sums with multiple face pairs (and multiple number sets)
        for (t, fs) in r.items():
          if not (len(fs) > 1 and len(d[t]) > 1): continue
          printf("  {t} -> {fs}")
      

      Solution: Plato’s original labelling gave a vertex sum of 1188.

      There are many ways to achieve this, so we couldn’t tell which set of numbers he used:

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

      But he then rearranged his numbers to give a vertex sum of 1024, which can only be done in one way:

      (2+6)(3+5)(7+9)

      So we know he used the numbers (2, 3, 5, 6, 7, 9).

      He then tells us that even though we know the numbers, we still can’t tell his original arrangement.

      This is because there are two ways to achieve 1188 using this set of numbers:

      (2+7)(3+9)(5+6)
      (2+9)(3+6)(5+7)

      And this is the only set of numbers for 1188 that has more than one arrangement.


      Manually, noting:

      (U + D)(L + R)(F + B) = ULF + ULB + URF + URB + DLF + DLB + DRF + DRB

      gives us a quick way to calculate the vertex sum. It is the same as the product of the three sums of opposite face pairs.

      And this lets us simplify the arrange() function above:

      from enigma import multiply
      def arrange(ns):
        for fs in partitions(ns, 2, distinct=1):
          yield (ns, fs, multiply(x + y for (x, y) in fs))
      

      And we see that the only possible value for the 10th power is 2^10 = 1024.

      So the values on opposite faces must sum to powers of 2:

      (1, 3) = 2^2
      (1, 7) = 2^3
      (2, 6) = 2^3
      (3, 5) = 2^3
      (7, 9) = 2^4

      The only arrangement that gives 1024 is:

      (2, 6) (3, 5) (7, 9)

      We can then look for 2 different arrangements of these numbers into pairs that give the same vertex sum. And 1188 is the only possibility.

      Like

      • Frits 11:54 am on 30 October 2021 Permalink | Reply

        @Jim, len(vs) is likely to be 1 but I am not sure if it can be used for checking if the numbers can be deduced.

        Like

        • Jim Randell 12:03 pm on 30 October 2021 Permalink | Reply

          Yes, we can check the values in vs all use the same numbers:

          vs = set(tuple(sorted(flatten(v))) for v in vs)
          assert len(vs) == 1
          

          And then ns is just this single value.

          I’ll update my code.

          (In fact, I’ve rewritten it to be a bit faster and more compact).

          Like

    • Frits 11:19 am on 30 October 2021 Permalink | Reply

        
      from enigma import SubstitutedExpression, tri
      
      ndigits = 9
      nfaces = 6
      npairs = nfaces // 2
      # highest possible sum
      h = ((tri(ndigits) - tri(ndigits - nfaces)) / npairs) ** npairs
      powers = [i for i in range(2, int(h ** 0.1) + 1)]
      
      # based on the entries in <powers> we can easily deduct the digits used
      # in the new sum (in this case the highest pair sum must be a 4th power)
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [ # find 2 different arrangements with same sum
          "A < C < E",                    # order the pairs
          "A < B and C < D and E < F",    # order within the pairs
          "G < I < K",                    # order the pairs
          "G < H and I < J and K < L",    # order within the pairs
          
          # different arrangements
          "(A, B, C, D, E, F) < (G, H, I, J, K, L)",
          
          # same sum
          "(A + B) * (C + D) * (E + F) == (G + H) * (I + J) * (K + L)",
        ],
        answer="((A, B), (C, D), (E, F)), ((G, H), (I, J), (K, L)), \
                (A + B) * (C + D) * (E + F)",
        # from manual analysis        
        digits=(2, 3, 5, 6, 7, 9),
        distinct=("ABCDEF","GHIJKL"),
        verbose=0,
      )
      
      # print answers
      for (_, ans) in p.solve():
        print(f"the original sum was {ans[2]}")
      

      Like

      • Jim Randell 1:11 pm on 30 October 2021 Permalink | Reply

        Or you could do:

        from enigma import (partitions, multiply, filter_unique, printf)
        
        # possible face pairs
        pairs = partitions((2, 3, 5, 6, 7, 9), 2, distinct=1)
        
        # calculate vertex sum
        fn = lambda fs: multiply(x + y for (x, y) in fs)
        
        # find vertex sums with multiple face pairs
        for fs in filter_unique(pairs, fn).non_unique:
          printf("{t} -> {fs}", t=fn(fs))
        

        Like

    • GeoffR 9:31 am on 5 November 2021 Permalink | Reply

      from enigma import all_different
      from itertools import combinations, permutations
      from collections import defaultdict
      
      D3084 = defaultdict(list)
      
      # If the cube sides are (L1, L2, R1, R2, U, D), the sum
      # of eight vertices = (L1 + L2) * (R1 + R2) * (U + D)
      
      # Since 2 ^ 10 = 1024 and 3 ^ 10 = 59049 and the maximum
      # vertices sum for face digits (1..9) = 2805 (17*15*11)
      # ... the 10th power must be 2 ^ 10 = 1024
      
      # find cube face values for 10th power = 1024
      for p1 in permutations(range(1, 10), 6):
        L1, L2, R1, R2, U, D = p1
        if (L1 + L2) * (R1 + R2) * (U + D) == 1024:
          set_faces = set((L1, L2, R1, R2, U, D))
      
      face_pairs = list(combinations(set_faces, 2))
      
      # map six cube face values to sum of eight vertices
      for A, B, C in combinations(face_pairs, 3):
        if all_different(A[0], A[1], B[0], B[1], C[0], C[1]):
          # digits must be same as 10th power of 1024
          if {A[0], A[1], B[0], B[1], C[0], C[1]} == set_faces:
            VSum = (A[0] + A[1]) * (B[0] + B[1]) * (C[0] + C[1])
            D3084[VSum].append(((A[0], A[1]), (B[0], B[1]), (C[0], C[1])))
      
      for k, v in D3084.items():
        # original number must have non-unique face values
        if len(v) > 1:
          print(f"The original number was {k}")
          print(f"Face Values are {v}")
      
      
      
      

      Like

    • GeoffR 9:53 am on 8 November 2021 Permalink | Reply

      This programme ran in 300ms with the Chuffed Solver, but took much longer with the Geocode Solver. I had a constraint to limit the set length of 15 values to 14 (i.e. 1 No. duplicated), but it proved not necessary in practice, and increased the run time substantially to 9.5s. This constraint is commented out in the programme.

      The tenth power of two is shown in the output after the code, as is the original sum of 1188 (i.e. the answer), for two instances.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % min vertex sum = (1+2) * (3+4) * (5+6) = 231
      % max vertex sum = (9+8) * (7+6) * (5+4) = 1989
      % ..as 2^10 = 1024 and 3^10 = 59049, therefore 1024 is the only
      % possible 10th power within min and max sum limits
      
      % the cube has six faces with different digits 1..9
      var 1..9: a; var 1..9: b; var 1..9: c;
      var 1..9: d; var 1..9: e; var 1..9: f;
      
      constraint all_different([a, b, c, d, e, f]);
      
      % N1..N15 are all the cube possible vertex totals
      var 231..1989: N1; var 231..1989:N2; var 231..1989:N3;
      var 231..1989: N4; var 231..1989:N5; var 231..1989:N6;
      var 231..1989: N7; var 231..1989:N8; var 231..1989:N9;
      var 231..1989: N10; var 231..1989:N11; var 231..1989:N12;
      var 231..1989: N13; var 231..1989:N14; var 231..1989:N15;
      
      % the fifteen possible vertex totals,
      % from six of the possible nine digits 1..9
      constraint N1 == (a+b) * (c+d) * (e+f);
      constraint N2 == (a+b) * (c+e) * (d+f);
      constraint N3 == (a+b) * (c+f) * (d+e);
      
      constraint N4 == (a+c) * (b+d) * (e+f);
      constraint N5 == (a+c) * (b+e) * (d+f);
      constraint N6 == (a+c) * (b+f) * (d+e);
      
      constraint N7 == (a+d) * (b+c) * (e+f);
      constraint N8 == (a+d) * (b+e) * (c+f);
      constraint N9 == (a+d) * (b+f) * (c+e);
      
      constraint N10 == (a+e) * (b+c) * (d+f);
      constraint N11 == (a+e) * (b+d) * (c+f);
      constraint N12 == (a+e) * (b+f) * (c+d);
      
      constraint N13 == (a+f) * (b+c) * (d+e);
      constraint N14 == (a+f) * (b+d) * (c+e);
      constraint N15 == (a+f) * (b+e) * (c+d);
      
      % One of the vertex totals is a 10th power i.e.2 ^ 10 = 1024
      % ...this constraint fixes the six digits for the solution
      constraint sum([
      N1 == 1024, N2 == 1024, N3 == 1024, N4 == 1024, N5 == 1024,
      N6 == 1024, N7 == 1024, N8 == 1024, N9 == 1024, N10 == 1024,
      N11 == 1024, N12 == 1024, N13 == 1024, N14 == 1024, N15 == 1024
      ]) == 1;
                      
      % constraint card ({N1, N2, N3, N4, N5, N6, N7, N8,
      % N9, N10, N11, N12, N13, N14,  N15}) == 14;
                      
      solve satisfy;
      
      output["N1 = " ++ show(N1) ++ ", sides: " ++ show([a,b]) 
      ++ ", " ++ show([c,d]) ++ ", " ++ show([e,f]) 
      ++ "\nN2 = " ++ show(N2) ++ ", sides: " ++ show([a,b]) 
      ++ ", " ++ show([c,e]) ++ ", " ++ show([d,f])
      ++ "\nN3 = " ++ show(N3) ++ ", sides: " ++ show([a,b]) 
      ++ ", " ++ show([c,f]) ++ ", " ++ show([d,e])
      
      ++ "\nN4 = " ++ show(N4) ++ ", sides: " ++ show([a,c]) 
      ++ ", " ++ show([b,d]) ++ ", " ++ show([e,f])
      ++ "\nN5 = " ++ show(N5) ++ ", sides: " ++ show([a,c]) 
      ++ ", " ++ show([b,e]) ++ ", " ++ show([d,f])
      ++ "\nN6 = " ++ show(N6) ++ ", sides: " ++ show([a,c])
       ++ ", " ++ show([b,f]) ++ ", " ++ show([d,e])
      
      ++ "\nN7 = " ++ show(N7) ++ ", sides: " ++ show([a,d]) 
      ++ ", " ++ show([b,c]) ++ ", " ++ show([e,f])
      ++ "\nN8 = " ++ show(N8) ++ ", sides: " ++ show([a,d]) 
      ++ ", " ++ show([b,e]) ++ ", " ++ show([c,f])
      ++ "\nN9 = " ++ show(N9) ++ ", sides: " ++ show([a,d]) 
      ++ ", " ++ show([b,f]) ++ ", " ++ show([c,e])
      
      ++ "\nN10 = " ++ show(N10) ++ ", sides: " ++ show([a,e])
      ++ ", " ++ show([b,c]) ++ ", " ++ show([d,f])
      ++ "\nN11 = " ++ show(N11) ++ ", sides: " ++ show([a,e])
      ++ ", " ++ show([b,d]) ++ ", " ++ show([c,f])
      ++ "\nN12 = " ++ show(N12) ++ ", sides: " ++ show([a,e])
      ++ ", " ++ show([b,f]) ++ ", " ++ show([c,d])
      
      ++ "\nN13 = " ++ show(N13) ++ ", sides: " ++ show([a,f]) 
      ++ ", " ++ show([b,c]) ++ ", " ++ show([d,e])
      ++ "\nN14 = " ++ show(N14) ++ ", sides: " ++ show([a,f]) 
      ++ ", " ++ show([b,d]) ++ ", " ++ show([c,e])
      ++ "\nN15 = " ++ show(N15) ++ ", sides: " ++ show([a,f]) 
      ++ ", " ++ show([b,e]) ++ ", " ++ show([c,d])
      ];
      
      % 15 Possible vertex totals for 6 sides of a cube
      % N1 = 1210, sides: [3, 7], [9, 2], [5, 6]
      % N2 = 1120, sides: [3, 7], [9, 5], [2, 6]
      % N3 = 1050, sides: [3, 7], [9, 6], [2, 5]
      % N4 = 1188, sides: [3, 9], [7, 2], [5, 6]   <<< original sum = 1188 (answer)
      % N5 = 1152, sides: [3, 9], [7, 5], [2, 6]
      % N6 = 1092, sides: [3, 9], [7, 6], [2, 5]
      % N7 = 880, sides: [3, 2], [7, 9], [5, 6]
      % N8 = 900, sides: [3, 2], [7, 5], [9, 6]
      % N9 = 910, sides: [3, 2], [7, 6], [9, 5]
      % N10 = 1024, sides: [3, 5], [7, 9], [2, 6]   <<< 10th power = 1024 (2^10)
      % N11 = 1080, sides: [3, 5], [7, 2], [9, 6]
      % N12 = 1144, sides: [3, 5], [7, 6], [9, 2]
      % N13 = 1008, sides: [3, 6], [7, 9], [2, 5]
      % N14 = 1134, sides: [3, 6], [7, 2], [9, 5]
      % N15 = 1188, sides: [3, 6], [7, 5], [9, 2]   <<< original sum = 1188 (answer)
      % ----------
      
      
      
      

      Like

      • Frits 12:47 pm on 9 November 2021 Permalink | Reply

        The all_different clause has been replaced by a < b < c < d < e < f.
        Also the card statement has been changed to less equal to 14.

        Now the Geocode solver takes less than half a second (printing all solutions) .
        Chuffed still takes 11 seconds.

         
        % A Solution in MiniZinc
        include "globals.mzn";
         
        % min vertex sum = (1+2) * (3+4) * (5+6) = 231
        % max vertex sum = (9+8) * (7+6) * (5+4) = 1989
        % ..as 2^10 = 1024 and 3^10 = 59049, therefore 1024 is the only
        % possible 10th power within min and max sum limits
         
        % the cube has six faces with different digits 1..9
        var 1..4: a; var 2..5: b; var 3..6: c;
        var 4..7: d; var 5..8: e; var 6..9: f;
         
        constraint a < b /\ b < c /\ c < d /\ d < e /\ e < f;
         
        % N1..N15 are all the cube possible vertex totals
        var 231..1989: N1; var 231..1989:N2; var 231..1989:N3;
        var 231..1989: N4; var 231..1989:N5; var 231..1989:N6;
        var 231..1989: N7; var 231..1989:N8; var 231..1989:N9;
        var 231..1989: N10; var 231..1989:N11; var 231..1989:N12;
        var 231..1989: N13; var 231..1989:N14; var 231..1989:N15;
         
        % the fifteen possible vertex totals,
        % from six of the possible nine digits 1..9
        constraint N1 == (a+b) * (c+d) * (e+f);
        constraint N2 == (a+b) * (c+e) * (d+f);
        constraint N3 == (a+b) * (c+f) * (d+e);
         
        constraint N4 == (a+c) * (b+d) * (e+f);
        constraint N5 == (a+c) * (b+e) * (d+f);
        constraint N6 == (a+c) * (b+f) * (d+e);
         
        constraint N7 == (a+d) * (b+c) * (e+f);
        constraint N8 == (a+d) * (b+e) * (c+f);
        constraint N9 == (a+d) * (b+f) * (c+e);
         
        constraint N10 == (a+e) * (b+c) * (d+f);
        constraint N11 == (a+e) * (b+d) * (c+f);
        constraint N12 == (a+e) * (b+f) * (c+d);
         
        constraint N13 == (a+f) * (b+c) * (d+e);
        constraint N14 == (a+f) * (b+d) * (c+e);
        constraint N15 == (a+f) * (b+e) * (c+d);
         
        % One of the vertex totals is a 10th power i.e.2 ^ 10 = 1024
        % ...this constraint fixes the six digits for the solution
        constraint sum([
        N1 == 1024, N2 == 1024, N3 == 1024, N4 == 1024, N5 == 1024,
        N6 == 1024, N7 == 1024, N8 == 1024, N9 == 1024, N10 == 1024,
        N11 == 1024, N12 == 1024, N13 == 1024, N14 == 1024, N15 == 1024
        ]) == 1;
                         
        constraint card ({N1, N2, N3, N4, N5, N6, N7, N8,
         N9, N10, N11, N12, N13, N14,  N15}) <= 14;
                         
        solve satisfy;
         
        output["N1 = " ++ show(N1) ++ ", sides: " ++ show([a,b]) 
        ++ ", " ++ show([c,d]) ++ ", " ++ show([e,f]) 
        ++ "\nN2 = " ++ show(N2) ++ ", sides: " ++ show([a,b]) 
        ++ ", " ++ show([c,e]) ++ ", " ++ show([d,f])
        ++ "\nN3 = " ++ show(N3) ++ ", sides: " ++ show([a,b]) 
        ++ ", " ++ show([c,f]) ++ ", " ++ show([d,e])
         
        ++ "\nN4 = " ++ show(N4) ++ ", sides: " ++ show([a,c]) 
        ++ ", " ++ show([b,d]) ++ ", " ++ show([e,f])
        ++ "\nN5 = " ++ show(N5) ++ ", sides: " ++ show([a,c]) 
        ++ ", " ++ show([b,e]) ++ ", " ++ show([d,f])
        ++ "\nN6 = " ++ show(N6) ++ ", sides: " ++ show([a,c])
         ++ ", " ++ show([b,f]) ++ ", " ++ show([d,e])
         
        ++ "\nN7 = " ++ show(N7) ++ ", sides: " ++ show([a,d]) 
        ++ ", " ++ show([b,c]) ++ ", " ++ show([e,f])
        ++ "\nN8 = " ++ show(N8) ++ ", sides: " ++ show([a,d]) 
        ++ ", " ++ show([b,e]) ++ ", " ++ show([c,f])
        ++ "\nN9 = " ++ show(N9) ++ ", sides: " ++ show([a,d]) 
        ++ ", " ++ show([b,f]) ++ ", " ++ show([c,e])
         
        ++ "\nN10 = " ++ show(N10) ++ ", sides: " ++ show([a,e])
        ++ ", " ++ show([b,c]) ++ ", " ++ show([d,f])
        ++ "\nN11 = " ++ show(N11) ++ ", sides: " ++ show([a,e])
        ++ ", " ++ show([b,d]) ++ ", " ++ show([c,f])
        ++ "\nN12 = " ++ show(N12) ++ ", sides: " ++ show([a,e])
        ++ ", " ++ show([b,f]) ++ ", " ++ show([c,d])
         
        ++ "\nN13 = " ++ show(N13) ++ ", sides: " ++ show([a,f]) 
        ++ ", " ++ show([b,c]) ++ ", " ++ show([d,e])
        ++ "\nN14 = " ++ show(N14) ++ ", sides: " ++ show([a,f]) 
        ++ ", " ++ show([b,d]) ++ ", " ++ show([c,e])
        ++ "\nN15 = " ++ show(N15) ++ ", sides: " ++ show([a,f]) 
        ++ ", " ++ show([b,e]) ++ ", " ++ show([c,d])
        ];
        

        Like

      • Frits 12:50 pm on 9 November 2021 Permalink | Reply

        @Jim/GeoffR,

        Please let me know how you post minizinc programs.

        Like

        • Jim Randell 2:08 pm on 9 November 2021 Permalink | Reply

          @Frits: Details on using [code] ... [/code] tags are here [link].

          For languages that don’t have a supported syntax highlighter you can use [[ language="text" ]].

          Like

  • Jim Randell 12:21 pm on 27 May 2021 Permalink | Reply
    Tags: by: Susan Bricket   

    Teaser 2797: Sunday Times table 

    From The Sunday Times, 1st May 2016 [link] [link]

    Do you remember reciting your “times tables” — for example, one seven is 7, two sevens are 14, three sevens are 21, continuing 28, 35, … ” and going on for ever?

    I have consistently replaced some digits by letters and in this way the five-figure number TIMES can be found in the times table of each of its digits but not in the times table of any other digit. On the other hand, TABLE can be found in the times table of seven different digits, each of which is a digit of TIMES or TABLE.

    What number would be BEST?

    [teaser2797]

     
    • Jim Randell 12:21 pm on 27 May 2021 Permalink | Reply

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

      It runs in 130ms.

      Run: [ @replit ]

      #!/usr/bin/env python3 -m enigma -r
      
      SubstitutedExpression
      
      # collect digits that divide x
      --code="divs = lambda x: set(d for d in irange(1, 9) if x % d == 0)"
      
      # TIMES is divisible by each of its digits, but no other digits
      "divs(TIMES) == {E, I, M, S, T}"
      
      # TABLE is divisible by 7 different digits, each of which is in TIMES or TABLE
      "(lambda ds=divs(TABLE): len(ds) == 7 and ds.issubset({A, B, E, I, L, M, S, T}))()"
      
      --answer="BEST"
      

      Solution: BEST = 3842.

      Like

    • Frits 10:39 am on 30 May 2021 Permalink | Reply

      from itertools import permutations
      
      # return 1-digit divisors of n
      divs = lambda n: [i for i in range(1, 10) if n % i == 0]
      # are all elements of sequence s2 part of sequence s1?
      issubset = lambda s1, s2: all(str(y) in s1 for y in s2)
      
      for T, I, M, E, S in permutations("123456789", 5):
       TIMES = T + I + M + E + S
       ds = divs(int(TIMES))
       # TIMES is divisible by each of its digits, but no other digits
       if len(ds) != 5: continue
       if not issubset(TIMES, ds): continue
       
       remaining = set('123456789').difference([T, I, M, E, S])
      
       for A, B, L in permutations(remaining, 3):
         TABLE = TIMES[0] + A + B + L + TIMES[3]
         
         ds = divs(int(TABLE))
         # TABLE is divisible by 7 different digits, 
         # each of which is in TIMES or TABLE
         if len(ds) == 7: 
           if issubset(TIMES + TABLE, ds):
             print("BEST =", B + E + S + T)
      

      Like

  • Jim Randell 9:51 am on 6 May 2021 Permalink | Reply
    Tags: by: Susan Bricket   

    Teaser 2791: Four-square family 

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

    My four sons are all under 20 and just one of them is a teenager. Their ages (or, more precisely, the squares of their ages) have some remarkable properties. Firstly, two years ago the square of one of their ages equalled the sum of the squares of the other three ages. Secondly, this year the sum of the squares of two of their ages equals the sum of the squares of the other two ages.

    What, in increasing order, are their ages?

    [teaser2791]

     
    • Jim Randell 9:51 am on 6 May 2021 Permalink | Reply

      The following Python program runs in 48ms.

      Run: [ @replit ]

      from enigma import (irange, subsets, is_square, sq, printf)
      
      # choose the age of the teenager
      for d in irange(13, 19):
        # and the ages of the 2 youngests non-teenagers
        for (a, b) in subsets(irange(2, 12), size=2):
          # calculate c: a^2 + d^2 = b^2 + c^2
          c = is_square(sq(a) + sq(d) - sq(b))
          if c is None or c < b or c > 12: continue
          # check the ages 2 years ago: (a-2)^2 + (b-2)^2 + (c-2)^2 = (d-2)^2
          if not (sq(a - 2) + sq(b - 2) + sq(c - 2) == sq(d - 2)): continue
          # output solution
          printf("a={a} b={b} c={c} d={d}")
      

      Solution: Their current ages are: 4, 8, 11, 13.

      This year we have: 4² + 13² = 185 = 8² + 11².

      Two years ago the ages were: 2, 6, 9, 11, and 2² + 6² + 9² = 121 = 11².

      Like

  • Jim Randell 9:07 am on 23 March 2021 Permalink | Reply
    Tags: by: Susan Bricket   

    Teaser 2781: Number time 

    From The Sunday Times, 10th January 2016 [link] [link]

    I have written down some numbers and then consistently replaced digits by capital letters, with different letters used for different digits. In this way my numbers have become:

    TRIPLE (which is a multiple of three)
    EIGHT (which is a cube)
    NINE (which is divisible by nine)
    PRIME (which is a prime)

    What is the number TIME?

    [teaser2781]

     
    • Jim Randell 9:08 am on 23 March 2021 Permalink | Reply

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

      The following run file executes in 122ms.

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      SubstitutedExpression
      
      "TRIPLE % 3 = 0"
      "is_cube(EIGHT)"
      "NINE % 9 = 0"
      "is_prime(PRIME)"
      
      --answer="TIME"
      

      Solution: TIME = 3901.

      There are 4 solutions to the alphametic expressions, but the value for TIME is the same in all of them.

      Like

    • Frits 12:39 pm on 23 March 2021 Permalink | Reply

      With a complicated formula for N.

      from enigma import is_prime
      
      alldiff = lambda seq: len(seq) == len(set(seq))
      
      # EIGHT is a cube
      for i in range(22, 47):
        s3 = str(i ** 3)
        E = int(s3[0])
        I = int(s3[1])
        T = int(s3[-1])
        if T == 0: continue             
        if E % 2 == 0: continue  # E may not be even (due to PRIME)
        if not alldiff(s3): continue
        
        # NINE is a multiple of 9
        # sumIE plus 2*N must be equal to k*9   (k is 1,2 or 3)
        sumIE = I + E
        N = (9 + 18 * (sumIE > 9) - sumIE) // 2 if sumIE % 2 else (18 - sumIE) // 2  
        if N == 0 or not alldiff(s3 + str(N)): continue   
        
        # TRIPLE is a multiple of 3
        LMPR = [x for x in range(10) if str(x) not in s3 + str(N)]
        candsM = [x for x in LMPR if (sumIE + T + sum(LMPR) - x) % 3 == 0]
         
        for M in candsM:
          LPR = [x for x in LMPR if x != M]
          for L in LPR:
            # PRIME may not be a multiple of 3
            if (sumIE + M + sum(LPR) - L) % 3 == 0: continue
            PR = [x for x in LPR if x != L]
            # consider permutations of PR
            for (P, R) in zip(PR, PR[::-1]):
              if P == 0: continue
              PRIME = 10000*P + 1000*R + 100*I + 10*M + E
              if not is_prime(PRIME): continue
              print(f"TIME={T}{I}{M}{E}")
      

      Like

  • Jim Randell 8:47 am on 4 March 2021 Permalink | Reply
    Tags: by: Susan Bricket   

    Teaser 2778: Cold turkey 

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

    We are having a “cold turkey” party on Boxing Day. Fewer than 100 people have indicated that they are coming, and the percentage of them choosing the vegetarian option is (to the nearest whole number) a single-digit number. My vegetarian aunt might also come. If she does, then (to the nearest whole number) the percentage having the vegetarian option will remain the same.

    If she does come, how many people will be there and how many of them will have the vegetarian option?

    [teaser2778]

     
    • Jim Randell 8:48 am on 4 March 2021 Permalink | Reply

      This Python program runs in 47ms.

      Run: [ @repl.it ]

      from enigma import divf, irange, printf
      
      # percentage a/b to the nearest whole number
      percent = lambda a, b: divf(200 * a + b, 2 * b)
      
      # total number of people expected (including aunt)
      for n in irange(2, 100):
        # consider number of vegetarians
        for v in irange(1, n):
          # percentage vegetarians (to nearest whole number)
          p = percent(v, n)
          if p > 9: break
      
          # and if aunt doesn't come, is percentage the same?
          if percent(v - 1, n - 1) == p:
            # output solution
            printf("{n} total; {v} veg [{p}% veg]")
      

      Solution: If the aunt comes there will be 95 people in total. 9 of them vegetarian.

      In this case the percentage of vegetarians is 9/95 ≈ 9.47%, which rounds down to 9%.

      But if the aunt doesn’t come both the number of guests and the number of vegetarians is reduced by 1, giving a percentage of 8/94 ≈ 8.51%, which rounds up to 9%.


      Note that Python 3’s built-in [[ round() ]] function might not do what you expect:

      % python3.9
      >>> round(11.5)
      12
      >>> round(12.5)
      12
      >>> round(1.15, 1)
      1.1
      >>> round(0.115, 2)
      0.12
      

      The decimal module allows more control over rounding behaviour.

      To keep things predictable, in my program I avoided float approximations by keeping the calculations in the integer domain, and I used the common “round half up” rule.

      Like

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

    Teaser 3033: Goldilocks and the bear commune 

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

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

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

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

    [teaser3033]

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

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

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

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

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

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

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

      It runs in 49ms.

      Run: [ @repl.it ]

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

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

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

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

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

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

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

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

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

      Like

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

      @Jim,

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

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

      Like

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

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

        Like

  • Jim Randell 4:32 pm on 1 November 2019 Permalink | Reply
    Tags: , by: Susan Bricket   

    Teaser 2980: Egyptian weights and measures 

    From The Sunday Times, 3rd November 2019 [link]

    We were wondering why ancient Egyptians chose to represent arbitrary fractions as sums of distinct unit fractions of the form 1/n (thus 5/7 = 1/2 + 1/5 + 1/70). One of us recalled long ago watching our greengrocer use four brass weights of 1/2, 1/4, 1/8, 1/16 lb to weigh any number of ounces up to 15 by stacking some of them on one side of her balancing scales. We wanted to make a metric equivalent, a set of distinct weights of unit fractions of a kilo, each weighing a whole number of grams, to weigh in 10g steps up to 990g.

    Naturally, we wanted to use as little brass as possible, but we found that there were several possible such sets. Of these, we chose the set containing the fewest weights.

    List, in increasing order, the weights in our set.

    [teaser2980]

     
    • Jim Randell 5:03 pm on 1 November 2019 Permalink | Reply

      Possible weights are the divisors of 1000.

      This Python program looks for subsets that permit all the required weights to be made, and then selects those sets with the minimal possible weight. It runs in 501ms.

      Run: [ @repl.it ]

      from enigma import divisors, inf, subsets, printf
      
      # find weights that are unit fractions of 1000
      weights = divisors(1000)
      weights.remove(1000)
      
      # find minimal weight sets of weights that can be used to weigh all
      # multiples of 10 from 10 to 990
      (w, rs) = (inf, list())
      
      # choose a set of weights
      for ws in subsets(weights, min_size=7):
        k = sum(ws)
        if k < 990 or k > w: continue
      
        # collect amounts
        amounts = set()
        # choose a subset of the weights to use
        for s in subsets(ws, min_size=1):
          # calculate the total weight
          t = sum(s)
          # is it a multiple of 10 between 10 and 990?
          if 9 < t < 991 and t % 10 == 0:
            amounts.add(t)
      
        # can we make 99 different amounts?
        if len(amounts) == 99:
          if k < w: (w, rs) = (k, list())
          rs.append(ws)
          printf("[{k} = {ws} ({n})]", n=len(ws))
      
      # and find the minimum number weights in the set
      n = min(len(ws) for ws in rs)
      
      # output solutions
      for ws in rs:
        if len(ws) == n:
          printf("min = {w}; set of {n} weights = {ws}")
      

      Solution: There are 10 weights in the set: 2g, 5g, 8g, 10g, 25g, 40g, 50g, 100g, 250g, 500g.

      The total weight of the set is 990g (which is obviously the minimum possible total to be able to weigh up to 990g).

      There are 4 viable sets of weights that have a total weight of 990g:

      set of 10 weights = (2, 5, 8, 10, 25, 40, 50, 100, 250, 500)
      set of 11 weights = (1, 2, 4, 8, 10, 25, 40, 50, 100, 250, 500)
      set of 12 weights = (1, 2, 4, 5, 8, 10, 20, 40, 50, 100, 250, 500)
      set of 13 weights = (1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 125, 200, 500)

      When I initially read the puzzle I solved it allowing weights to be placed on both sides of the scales, and I found two sets of 7 weights which can be used to achieve the required values, where both sets weigh 990g in total:

      set of 7 weights = (5, 20, 40, 50, 125, 250, 500)
      set of 7 weights = (5, 20, 40, 100, 125, 200, 500)

      Like

  • Jim Randell 10:22 am on 10 July 2019 Permalink | Reply
    Tags: by: Susan Bricket   

    Teaser 2900: An ancestral equation 

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

    I recently discovered a 16th-century ancestor called David, which happens to be my maiden name. (I never really liked Bricket, even when pronounced in the French way). I have always been partial to word arithmetic (or cryptarithms) and the other day I found a solution to this one:

    MY × NAME = DAVID

    When eight distinct digits are substituted for the eight letters and no number starts with zero, the equation holds. Amazingly the solution gave me more information about my ancestor. MY turned out to be his age when he died and NAME was the year he was born.

    What was that year?

    [teaser2900]

     
    • Jim Randell 10:24 am on 10 July 2019 Permalink | Reply

      This is a simple alphametic puzzle that can be solved using the [[ SubstitutedExpression() ]] solver from the enigma.py library.

      The multiplication expression is enough to find a unique solution, but we can also check that the date is in the required range.

      This run file executes in 166ms.

      Run: [ @replit ]

      #! python -m enigma -r
      
      SubstitutedExpression
      
      # this is enough to solve the puzzle
      "MY * NAME = DAVID"
      
      # [optional] check they were alive in the 16th century (1501 - 1600)
      "1500 - MY < NAME < 1601"
      

      Solution: He was born in 1543.

      And died aged 49 around 1592.

      Like

    • GeoffR 12:13 pm on 11 July 2019 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 0..9:M; var 0..9:Y; var 0..9:N; var 0..9:A; 
      var 0..9:E; var 0..9:D; var 0..9:V; var 0..9:I; 
      
      % 16th-century means N = 1 and A = 5, as year born = NAME
      constraint M > 0 /\ D > 0 /\ N == 1 /\ A == 5;
      constraint all_different([M, Y, N, A, E, D, V, I]);
      
      var 10..99: MY = 10*M + Y;
      var 1000..9999: NAME = 1000*N + 100*A + 10*M + E;
      var 10000..99999: DAVID = 10001*D + 1000*A + 100*V + 10*I;
      
      constraint MY * NAME == DAVID;
      
      solve satisfy;
      output[ "Equation: "  ++ show(MY) ++ " * " ++ show(NAME) ++ " = " ++ show(DAVID)]
      ++ [ "\nYear born = " ++ show(NAME) ];
      
      % Equation: 49 * 1543 = 75607
      % Year born = 1543
      % ----------
      % ==========
      
      

      Like

  • Jim Randell 1:37 pm on 5 May 2019 Permalink | Reply
    Tags: by: Susan Bricket   

    Teaser 2916: Pointless batting averages 

    From The Sunday Times, 12th August 2018 [link]

    When my son was chosen to play cricket for his School First XI, I kept a record of the number of runs he scored in each of his first five innings. After each innings I calculated his batting average (the total number of runs scored so far divided by the number of innings) and found an interesting pattern:

    (i) Each score was under 30
    (ii) They [the scores] were all different
    (iii) Each of the five averages was a whole number

    When he asked me how he could maintain this pattern with his sixth innings, I was able to tell him the smallest score that would achieve this.

    What is the largest number this could have been?

    [teaser2916]

     
    • Jim Randell 1:37 pm on 5 May 2019 Permalink | Reply

      If the scores in the first five innings are (a, b, c, d, e) and there are scores for the sixth innings f, (between 0 and 29), that continue the pattern. And there will be a smallest such value:

      (a, b, c, d, e, f) → f_min

      So, we can look at all possible (a, b, c, d, e, f) values and find the largest possible f_min value.

      This Python program runs in 569ms.

      Run: [ @repl.it ]

      from enigma import irange, Accumulator, printf
      
      # possible next scores
      def scores(ss, avgs):
        t = sum(ss)
        n = len(ss) + 1
        for s in irange(-t % n, 29, step=n):
          if s not in ss:
            yield (ss + [s], avgs + [(t + s) // n])
      
      # find sequences of length k
      def solve(ss=[], avgs=[], k=5):
        if len(ss) == k:
          yield (ss, avgs)
        else:
          for (ss1, avgs1) in scores(ss, avgs):
            yield from solve(ss1, avgs1, k)
      
      # find the largest of the smallest values
      r = Accumulator(fn=max)
      
      for (ss, avgs) in solve():
        # find the smallest score to maintain this
        for (ss1, avgs1) in scores(ss, avgs):
          s = ss1[-1]
          r.accumulate(s)
          if s == r.value: printf("scores={ss} (avgs={avgs}) -> score={s} (avg={avg})", avg=avgs1[-1])
          break # we only want the smallest value
      
      # output the solution
      printf("max value = {r.value}")
      

      Solution: The largest number it could have been is 23.

      I found 142 sequences that give this largest possible f_min value, although only 15 of these also have the averages take on 5 different values.

      One possible sequence is:

      (5, 11, 17, 27, 25)

      which give the corresponding averages of:

      (5, 8, 11, 15, 17)

      A score in the sixth innings of 23, would give an average of 18 over the six innings.

      Like

  • Jim Randell 7:58 am on 22 March 2019 Permalink | Reply
    Tags: by: Susan Bricket   

    Teaser 2931: Unfortunate 57 

    From The Sunday Times, 25th November 2018 [link]

    In the early days of the internet, I used a secret shorthand for my important passwords:

    Bank=1/7, Credit Card=2/7, ISP=3/7, etc.

    Like all fractions, the decimal expansions:

    1/7 = 0.142857142857142…
    2/7 = 0.285714285714285…

    eventually repeat themselves, in this case in sequences of six digits. In each case, my password was the set of digits that repeat (“Unfortunate 57” is a mnemonic for 142857). As password requirements became stricter, I changed my system to base 11, using an X for the extra digit for “ten”; so for instance in base 11:

    234 (= 1 × 11² + 10 × 11¹ + 3 × 11⁰) is 1X3 [base 11], and;
    1/2 = 0.5555… [base 11] = 5 / (11¹) + 5 / (11²) + 5 / (11³) + …

    In the sequence 1/2, 1/3, …, what is the first password of length greater than six that my base-11 system produces?

    The setter is probably conflating “the internet” with “the world wide web”.

    [teaser2931]

     
    • Jim Randell 7:58 am on 22 March 2019 Permalink | Reply

      For Enigma 1247 I wrote the [[ recurring() ]] function, which will calculate the recurring representation of a fraction in a given base.

      We can use this routine in a short Python program to solve this puzzle. It runs in 74ms.

      Run: [ @repl.it ]

      from enigma import irange, inf, recurring, format_recurring, printf
      
      for x in irange(2, inf):
        (i, nr, rr) = recurring(1, x, base=11, digits='0123456789X')
        printf("1 / {x} = {f} [period = {n}]", f=format_recurring(i, nr, rr), n=len(rr))
        if len(rr) > 6: break
      

      Solution: The first password with length greater than 6 is: 093425X17685.

      It is produced by the fraction 1/13 (in decimal notation).

      Like

  • Jim Randell 11:54 am on 12 February 2019 Permalink | Reply
    Tags: by: Susan Bricket   

    Teaser 2935: A palindrome 

    From The Sunday Times, 23rd December 2018

    → See: [ Teaser 2935: A palindrome at Enigmatic Code ]

    [teaser2935]

     
  • Jim Randell 11:52 am on 12 February 2019 Permalink | Reply
    Tags: by: Susan Bricket   

    Teaser 2907: Combinatorial cards 

    From The Sunday Times, 10th June 2018

    → See: [ Teaser 2907: Combinatorial cards at Enigmatic Code ]

    [teaser2907]

     
c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
%d bloggers like this: