Recent Updates Toggle Comment Threads | Keyboard Shortcuts

  • Jim Randell 10:11 am on 14 August 2022 Permalink | Reply
    Tags: by: Richard Diamond   

    Brain-Teaser 46 

    From The Sunday Times, 4th February 1962 [link]

    Don and Derek live on intermediate floors in neighbouring blocks of flats each provided with a lift. Neither lift is subject to direction change by users and they both travel continuously and steadily from the ground floor to the top floor and back, stopping at each floor, and waiting at the top and bottom twice as long as at other stops. During the year the number of floors in each block is increased, though not necessarily by the same number. Don, who lives on a higher floor than Derek, notices that if his lift is not on his floor, it is twice as likely to be going down when it first comes to him as it used to be. Derek makes a similar observation on his lift.

    The following year each moves four floors up and they each notice that if the lift is not on his floor, it has the same likelihood of going down when it first comes to him as it had originally.

    On which floors do Don and Derek live now?

    [teaser46]

     
    • Jim Randell 10:13 am on 14 August 2022 Permalink | Reply

      If we consider a building with n floors, numbered from 0 to (n − 1), then this is consistent with the way building floors are numbered in the UK (i.e. 0 = ground floor, 1 = first floor, 2 = second floor, etc), assuming there are no basement levels.

      If I live on floor k (0 < k < (n − 1)) of an n storey building, then the lift has 2n states (= each floor × {up, down}), and (2n − 2) are not at my floor. Of these the lift will be travelling up when it arrives only if it is below my floor, i.e. in 2k states.

      So the likelihood of an arriving lift going up is:

      up(n, k) = 2k / (2n − 2) = k / (n − 1)

      And the likelihood of it going down is:

      down(n, k) = ((2n − 2) − 2k) / (2n − 2) = (n − k − 1) / (n − 1)

      This Python program considers building with 3 to 40 floors.

      It runs in 60ms. (Internal runtime is 5.8ms).

      Run: [ @replit ]

      from collections import defaultdict
      from enigma import (Rational, irange, unpack, subsets, printf)
      
      # generate (n, k, m) values
      def generate():
        Q = Rational()
      
        # record probabilities of lift going down
        # d: down(n, k) -> (n, k)
        d = defaultdict(list)
        # n = floors of the building
        for n in irange(3, 40):
          # consider each floor
          for k in irange(1, n - 1):
            # calculate probability of lift going down
            p = Q(n - k - 1, n - 1)
            # is it the same value as the (k - 4)th floor of a lower building?
            # and half the value as the (k - 4)th floor in this building
            for (n_, k_) in d[p]:
              if k == k_ + 4 and n_ < n and (n, k_) in d[p * 2]:
                yield (n_, k_, n)
            # record this value
            d[p].append((n, k))
      
      # collect solution values sorted by k
      ss = sorted(generate(), key=unpack(lambda n, k, m: k))
      
      # choose values for Derek (lower floor) and Don (higher floor)
      for vs in subsets(ss, size=2):
        for (t, (n, k, m)) in zip(["Derek", "Don"], vs):
          printf("{t}: floor {k} of {n} -> floor {k} of {m} -> floor {k4} of {m}", k4=k + 4)
        printf()
      

      Solution: Derek lives on the eighth floor of his building. Don lives on the sixteenth floor of his building.


      Derek starts on floor 4 of 7 (numbered 0 to 6). There are 4 lift states above him and 8 lift states below him, so the probability of waiting for a down lift is 4/12 = 1/3.

      The building is then expanded to 13 floors, which adds 12 lift states above him, so the probability of waiting for a down lift is now 16/24 = 2/3.

      So the probability of a down lift is twice what it was before.

      Derek then moves up 4 floors to floor 8 of 13. There are 8 lift states above him and 16 lift states below him, so the probability of waiting for a down lift is now 8/24 = 1/3, the same as it was originally.

      And Don starts on floor 12 of 16. There are 6 lift states above him, and 24 lift states below him, so the probability of waiting for a down lift is 6/30 = 1/5.

      The building is then expanded to 21 floors, which adds 10 lift states above him, so the probability of waiting for a down lift is now 16/40 = 2/5.

      Don then moves up 4 floors to floor 16 of 21. There are 8 lift states above him and 32 lift states below him, so the probability of waiting for a down lift is 8/40 = 1/5.

      Like

      • Jim Randell 10:16 am on 14 August 2022 Permalink | Reply

        With a bit more analysis:

        When the building is extended to m floors, we are interested in situations where:

        down(m, k) = 2 × down(n, k)

        and also:

        down(m, k + 4) = down(n, k)

        which give:

        down(m, k) = 2 × down(m, k + 4)
        (m − k − 1) / (m − 1) = 2 (m − (k + 4) − 1) / (m − 1)
        ⇒ m = k + 9

        down(m, k) = 2 × down(n, k)
        ⇒ n = (k² + 9k + 4) / (k + 4)
        ⇒ n = (k + 5) − 16 / (k + 4)

        For integer values of n we need (k + 4) to be a divisor of 16.

        (k + 4) = {1, 2, 4, 8, 16}
        ⇒ k = {4, 12}

        So, Derek starts on floor 4 of (4 + 5 − 16/8) = 7, then floor 4 of (4 + 9) = 13, then floor (4 + 4) = 8 of 13.

        And, Don starts on floor 12 of (12 + 5 − 16/16) = 16, then floor 12 of (12 + 9) = 21, then floor (12 + 4) = 16 of 21.

        This Python program runs in 55ms. (Internal run time is 152µs).

        Run: [ @replit ]

        from enigma import (divisors_pairs, unpack, subsets, printf)
        
        # generate (n, k, m) values
        def generate():
          for (k4, x) in divisors_pairs(16, every=1):
            k = k4 - 4
            if k > 0:
              yield (k + 5 - x, k, k + 9)
        
        # collect solution values sorted by k
        ss = sorted(generate(), key=unpack(lambda n, k, m: k))
        
        # choose values for Derek (lower floor) and Don (higher floor)
        for vs in subsets(ss, size=2):
          for (t, (n, k, m)) in zip(["Derek", "Don"], vs):
            printf("{t}: floor {k} of {n} -> floor {k} of {m} -> floor {k4} of {m}", k4=k + 4)
          printf()
        

        Like

  • Jim Randell 3:56 pm on 12 August 2022 Permalink | Reply
    Tags:   

    Teaser 3125: The bearings’ trait 

    From The Sunday Times, 14th August 2022 [link]

    At Teaser Tor trig. point I found a geocaching box. The three-figure compass bearings (bearing 000=north, 090=east, etc.) from there to the church spires at Ayton, Beeton and Seaton were needed to decode the clue to the next location.

    Each spire lay in a different compass quadrant (eg 000 to 090 is the North-East quadrant). Curiously, each of the numerals 1 to 9 occurred in these bearings and none of the bearings were prime values.

    Given the above, if you chose one village at random to be told only its church spire’s bearing, it might be that you could not calculate the other two bearings with certainty, but it would be more likely you could.

    Give the three bearings, in ascending order.

    [teaser3125]

     
    • Jim Randell 4:28 pm on 12 August 2022 Permalink | Reply

      This Python program uses the [[ SubstitutedExpression ]] solver from the enigma.py library to find possible sets of bearings.

      We then examine each set of bearings and count how many of the bearings appear in only one set (i.e. this set). It is more likely than not that if we are given the value of one of the bearings we will be able to identify all of the bearings in the set (so there need to be more unique bearings than non-unique bearings in the set), but it is possible that we won’t be able to identify the entire set given one of the bearings (so there must be at least one non-unique bearing in the set). Hence we are looking for a set with 2 unique bearings and 1 non-unique bearing in it. (I assume this is the intended interpretation of the penultimate paragraph of the puzzle text. And it does lead to a unique answer to the puzzle).

      It runs in 86ms.

      Run: [ @replit ]

      from enigma import (SubstitutedExpression, irange, multiset, printf)
      
      # find possible bearings
      p = SubstitutedExpression(
        [
          # each of the bearings
          "0 <= ABC < 360", "0 <= DEF < 360", "0 <= GHI < 360",
          # none is prime
          "not is_prime(ABC)", "not is_prime(DEF)", "not is_prime(GHI)",
          # each in a different quadrant
          "len({ABC // 90, DEF // 90, GHI // 90}) = 3",
          # remove duplicate triples
          "A < D < G",
        ],
        digits=irange(1, 9),
        answer="(ABC, DEF, GHI)",
        verbose=0
      )
      
      # collect the bearings
      ss = list(ans for (_, ans) in p.solve())
      
      # find bearings that only appear in one set
      unique = set(x for (x, k) in multiset.from_seq(*ss).items() if k == 1)
      
      # consider possible situations
      for bs in ss:
        # are there 2 unique bearings?
        xs = unique.intersection(bs)
        if len(xs) == 2:
          printf("bearings = {bs} -> unique = {xs}", xs=sorted(xs))
      

      Solution: [To Be Revealed]

      Like

      • Jim Randell 7:28 am on 13 August 2022 Permalink | Reply

        The digit 0 is not used, which excludes all 3-digit bearings below 111. So the bearings must be 1xx, 2xx, 3xx (where the x‘s are the digits 4-9) in the SE, SW, NW quadrants.

        This Python program is a little shorter and a little faster than my previous solution.

        It runs in 57ms. (Internal run time is 892µs).

        Run: [ @replit ]

        from enigma import (irange, subsets, nconcat, primes, multiset, printf)
        
        # generate possible bearings sets
        def generate():
          primes.extend(360)
        
          # allocate the digits 4-9 in X = 1xx, Y = 2xx, Z = 3xx
          for (a, b, c, d, e, f) in subsets(irange(4, 9), size=len, select="P"):
            X = nconcat(1, a, b)
            Y = nconcat(2, c, d)
            Z = nconcat(3, e, f)
            if not(X < 180 and Y < 270 and Z < 360): continue
            if any(n in primes for n in (X, Y, Z)): continue
            yield (X, Y, Z)
        
        # collect the bearings
        ss = list(generate())
        
        # find bearings that only appear in one set
        unique = set(x for (x, k) in multiset.from_seq(*ss).items() if k == 1)
        
        # consider possible situations
        for bs in ss:
          # are there 2 unique bearings?
          xs = unique.intersection(bs)
          if len(xs) == 2:
            printf("bearings = {bs} -> unique = {xs}", xs=sorted(xs))
        

        Like

    • GeoffR 8:42 am on 13 August 2022 Permalink | Reply

      Similar method to Jim’s first solution.

      From the multiple output answers, unique values for ABC and DEF bearings are readily apparent,
      making the identification of the unique triple bearing more than likely.

      
      % 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));
      
      set of int: INT = 1..9;
      
      var INT: A;var INT: B;var INT: C;
      var INT: D;var INT: E;var INT: F;
      var INT: G;var INT: H;var INT: I;
      
      constraint all_different([A,B,C,D,E,F,G,H,I]);
      
      % the three bearings must be in quadrants 2, 3 and 4
      % i.e 90-180, 180-270 and 270-360
      % for the digits of all bearings to be in the range 1..9
      
      var 123..179: ABC == 100*A + 10*B + C;
      var 181..269: DEF == 100*D + 10*E + F;
      var 271..359: GHI == 100*G + 10*H + I;
      
      % all bearings are not prime numbers
      constraint sum([is_prime(ABC), is_prime(DEF), is_prime(GHI)]) == 0;
      
      % output bearings in ascending order
      constraint increasing([ABC, DEF, GHI]);
      
      solve satisfy;
      output[ " [ABC, DEF, GHI ] = "  ++ show([ABC, DEF, GHI ]) ];
      
      

      Like

    • Frits 12:17 pm on 13 August 2022 Permalink | Reply

       
      from itertools import permutations
      
      # primes between 145 and 360
      P = {3, 5, 7, 11, 13, 17, 19}
      P = {x for x in range(145, 361, 2) if all(x % p for p in P)}
      
      ns = "456789"     # numbers to use for tens and units
      
      # generate additional quadrant bearings 
      def bearings(mx, bs=['']): 
        return [{new} | set(b) for b in bs 
                for p in permutations([s for s in ns if s not in "".join(b)], 2) 
                if int(new := mx[0] + "".join(p)) not in P and new < mx]           
      
      # bearings can't reside in the first NE quadrant
      
      three_barings = bearings('180', bearings('270', bearings('360')))   
      
      unique_bearings = {b for b in set(x for s in three_barings for x in s) 
                         if sum(b in s for s in three_barings) == 1}
      
      # find solutions which have at least two unique bearings so the chance
      # of calculating the other two bearings with certainty is at least 2/3
      for b3 in three_barings:
        ln = len(b3 & unique_bearings)
        if ln > 1:
          print(f"answer : {', '.join(sorted(b3))}")
      

      Like

      • Frits 3:49 pm on 15 August 2022 Permalink | Reply

        Inspired by Nigel.

        I remembered that to rotate a matrix M we can use zip(*M).

           
        from itertools import permutations
        
        # primes between 145 and 360
        P = {3, 5, 7, 11, 13, 17, 19}
        P = {x for x in range(145, 360, 2) if all(x % p for p in P)}
        
        ns = "456789"     # numbers to be used for tens and units
        
        # generate additional quadrant bearings 
        def bearings(mx, bs=['']): 
          return [sorted({new} | set(b)) for b in bs 
                  for p in permutations([s for s in ns if s not in "".join(b)], 2)
                  if int(new := mx[0] + "".join(p)) not in P and new <= mx]   
        
        # bearings can't reside in the first NE quadrant
        three_barings = bearings('180', bearings('270', bearings('360')))   
        
        # find solutions which have at least two unique bearings so the chance
        # of calculating the other two bearings with certainty is at least 2/3
        print("answer", *[b for b in three_barings 
                          if sum([list(zip(*three_barings))[i].count(s) == 1 
                                  for i, s in enumerate(b)]) > 1])
        

        Like

    • Frits 12:59 pm on 14 August 2022 Permalink | Reply

      Too hot to go outside.

      Bringing down the number of viable bearings down to 15.

         
      # pick one value from each entry of a <k>-dimensional list <ns>
      # so that all elements in the picked <k> values are different
      def pickOneFromEach(ns, k=None, s=set()):
        if k == 0:
           yield s
        else:
          if k is None:
            k = len(ns)
      
          elements = set(y for x in s for y in x)
          for n in ns[k - 1]:
            if all(x not in elements for x in n):
              yield from pickOneFromEach(ns, k - 1, s | {n})
      
      # as 1, 2 and 3 are reserved for hundreds only consider 
      # bearings with last two digits 45 and higher
      
      P = {3, 5, 7, 11, 13, 17, 19}
      P = {x for x in range(145, 360, 2) if all(x % p for p in P)}
      
      dgts = set([str(i) for i in range(1, 10)])
      mx = [180, 270, 360]
      
      # determine bearings for quadrants SE, SW and NW
      quadrants = [[str(b) for b in range(100 * i + 45, mx[i - 1] + 1) 
            if b not in P                      # bearing not a prime
            and len(set(s := str(b))) == 3     # different digits
            and "0" not in s                   # no zeroes
            # do not use the hundreds digit from other quadrants
            and all(k not in s for k in "123" if k != str(i)) 
           ] for i in range(1, 4)]
      
      prt = False
      updates = True    
      while updates:
        # try to reduce the number of bearings
        updates = False
        # dictionary: digit --> bearings
        d = {i: [b for q in quadrants for b in q if i in str(b)] for i in dgts}
       
        # does a bearing lead to another bearing that leads to no solution?
        for i, q in enumerate(quadrants):
          for b1 in q:
            # check digits (except digits in bearing <b1>)
            for dgt, vs in d.items():
              if dgt in b1: continue
              
              # determine which bearings (in different quadrants) 
              # can still can occur for digit <dgt>
              b2 = [v for v in vs if v[0] != b1[0] and 
                    len(set(b1[1:]).difference(v[1:])) == 2]
                                    
              ln = len(b2)                      
              if ln == 0:
                if prt: print("remove", b1, 
                        "as then no bearings remain for digit", str(dgt) + ":",
                        tuple(d[dgt]))
                quadrants[i].remove(b1)
                break
              elif ln == 1:
                b2 = b2[0]
                # bearing <b1> leads to bearing <b2> so determine third bearing
                b3 = "".join(sorted(dgts.difference(b2 + b1)))
                
                # check if bearings xyz (b3) and xzy exist in remaining quadrant
                if all(x not in quadrants[int(b3[0]) - 1]
                       for x in [b3, b3[0] + b3[2] + b3[1]]):
                  if prt: print("remove", b1,
                          "as bearing", b1, "leads to bearing", b2, 
                          "with no bearing for remaining digits", ", ".join(b3))
                  quadrants[i].remove(b1)
                  break
            else: 
              continue  
            
            # a break occurred so there were updates
            updates = True    
          
      three_bearings = list(pickOneFromEach(quadrants))
      
      unique_bearings = {b for b in set(x for s in three_bearings for x in s) 
                         if sum(b in s for s in three_bearings) == 1}
      
      # find solutions which have at least two unique bearings so the chance
      # of calculating the other two bearings with certainty is at least 2/3
      for b3 in three_bearings:
        ln = len(b3 & unique_bearings)
        if ln > 1:
          print(f"answer: {', '.join(sorted(b3))}")
      

      Like

    • GeoffR 5:46 pm on 14 August 2022 Permalink | Reply

      from itertools import permutations
      from enigma import is_prime, multiset, printf
      
      BEARINGS = []  # list of all potential bearings
      # Bearings are ABC, DEF and GHI
      
      for p1 in permutations('123456789', 3):
          A, B, C = p1
          ABC = int(A + B + C)
          if is_prime(ABC):continue
          q1 = set('123456789').difference({A, B, C})
          for p2 in permutations(q1, 3):
              D, E, F = p2
              DEF = int(D + E + F)
              if is_prime(DEF):continue
              q2 = set(q1).difference({D, E, F})
              for p3 in permutations(q2):
                  G, H, I = p3
                  GHI = int(G + H + I)
                  if is_prime(GHI): continue
                  # three 3-digit bearings using digits 1..9
                  # ...must be in quadrants 2,3 and 4 only
                  if (123 < ABC <= 179 and 181 < DEF <= 269
                     and 271 < GHI <= 359):
                      BEARINGS.append([ABC, DEF, GHI])
      
      # Output Code Credit : Jim Randell 
      # find bearings that only appear in one set
      unique = set(x for (x, k) in multiset.from_seq(*BEARINGS).items() if k == 1)
       
      # consider possible situations
      for bs in BEARINGS:
        # are there 2 unique bearings?
        xs = unique.intersection(bs)
        if len(xs) == 2:
          printf("bearings = {bs} -> unique = {xs}", xs=sorted(xs))
      
      
      
      
      

      Like

    • NigelR 12:54 pm on 15 August 2022 Permalink | Reply

      Version below seems to run astonishingly quickly (2.1ms) unless I’m missing something!

      from itertools import permutations as perm
      from enigma import is_prime,timer
      timer.start()
      
      def test(n): #test set of bearings whether in the right sectors and non-prime
          if n[0]>180 or n[1]>270 or n[2]>359: return False
          if [m for m in n if is_prime(m)]:return False
          return True       
      
      #generate valid sets of bearings in format [1xx,2xx,3xx]
      digs='456789' #digits without 1, 2, or 3
      y = lambda a : [int('1'+a[0]+a[1]),int('2'+a[2]+a[3]),int('3'+a[4]+a[5])]
      brgs = [y(x) for x in perm(digs) if test(y(x))]
      #regroup sets of bearings by values for each village
      vals = [[x[0] for x in brgs],[x[1] for x in brgs], [x[2] for x in brgs]]
      #check for 2 unique values in set of bearings
      sols = [x for x in brgs if [vals[0].count(x[0]),vals[1].count(x[1]),vals[2].count(x[2])].count(1)==2]
      if len(sols)==1: print('unique solution is:',sols)
      else: print ('possible sets of values are :',sols)
      timer.stop()
      timer.report()
      

      Like

      • Frits 2:49 pm on 15 August 2022 Permalink | Reply

        Well done.

        Using

           
        if any(is_prime(m) for m in n): return False 
        

        it is even more efficient.

        Like

  • Jim Randell 7:28 am on 11 August 2022 Permalink | Reply
    Tags:   

    Teaser 2727: Happy New Year 

    From The Sunday Times, 28th December 2014 [link] [link]

    I have written down five positive whole numbers whose sum is a palindromic number. Furthermore, the largest of the five numbers is the sum of the other four. I have reproduced the five numbers below, but have consistently replaced digits by letters, with different letters used for different digits.

    We are about to enter an odd-numbered new year and so it is appropriate that my numbers have become:

    A
    VERY
    HAPPY
    NEW
    YEAR

    What is the odd-numbered YEAR?

    This puzzle was not included in the book The Sunday Times Brain Teasers Book 1 (2019).

    [teaser2727]

     
    • Jim Randell 7:29 am on 11 August 2022 Permalink | Reply

      The largest of the numbers is HAPPY, so we have:

      A + VERY + NEW + YEAR = HAPPY

      And also the sum of all 5 numbers (= 2 × HAPPY) is palindromic.

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

      The following run file executes in 89ms. (The internal run time of the generated program is 22.8ms).

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      SubstitutedExpression
      
      # sum is palindromic
      "is_palindrome(nsplit(2 * HAPPY))"
      
      # largest number (HAPPY) is the sum of the other four
      "A + VERY + NEW + YEAR = HAPPY"
      
      # YEAR is odd
      "R % 2 = 1"
      
      --answer="YEAR"
      

      Solution: YEAR = 6925.

      Like

    • GeoffR 11:01 am on 11 August 2022 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      set of int: INT = 1..9;
      var INT: A; var INT: V; var INT: E;
      var INT: R; var INT: Y; var INT: N;
      var INT: W; var INT: H; var INT: P;
      
      constraint all_different([A, V, E, R, Y, N, W, H, P]);
      
      var 1000..9999:VERY = 1000*V + 100*E + 10*R + Y;
      var 1000..9999:YEAR = 1000*Y + 100*E + 10*A + R;
      var 100..999:NEW = 100*N + 10*E + W;
      var 10000..99999:HAPPY = 10000*H + 1000*A + 110*P + Y;
      var 10000..99999:HAPPY2;  % NEW + YEAR + VERY < 21000
      
      constraint YEAR mod 2 == 1;
      constraint A + VERY + NEW + YEAR == HAPPY;
      constraint HAPPY2 == 2 * HAPPY;
      
      % check 2 * HAPPY is a 5-digit palindromic number
      % 1st and 5th digits are the same
      constraint HAPPY2 div 10000 == HAPPY2 mod 10
      % 4th and 2nd digits are the same
      /\ HAPPY2 div 1000 mod 10 == HAPPY2 div 10 mod 10;
      
      solve satisfy;
      
      output ["YEAR = " ++ show(YEAR) ++ ", HAPPY2 = " ++ show(HAPPY2)
      ++"\n[A,V,E,R,Y,N,W,H,P] = " ++ show( [A,V,E,R,Y,N,W,H,P]  )];
      
      % YEAR = 6925, HAPPY2 = 25552
      % [A, V, E, R, Y, N, W, H, P] = 
      % [2, 4, 9, 5, 6, 8, 3, 1, 7]
      % ----------
      % ==========
      
      
      
      

      Like

    • Frits 12:47 pm on 11 August 2022 Permalink | Reply

      Only loop over A and R.

         
      from enigma import SubstitutedExpression
      
      # invalid digit / symbol assignments
      d2i = dict()
      for d in range(0, 10):
        vs = set()
        # starting letters
        if d == 0: vs.update('AVN')
        
        # exclude s2d values H and Y
        if d in {1, 6}: vs.update('AENPRVW')
        
        # 2 * A < 10
        if d > 4: vs.update('A')
        # YEAR is odd
        if d % 2 == 0: vs.update('R')
        
        d2i[d] = vs
      
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
          # 2 * HAPPY is not a 6-digit number, it's last digit must be even (not 1)
          # so 2 * HAPPY == KLMLK
          
          # L must be odd as 2 * Y > 9 and 2 * P is even
          "2 * A + 1 = L",
          
          # P > 4 as 2 * A + 1 = L (carry over from middle column)
          
          # (2 * P + 1) % 10 = L and P > 4 so 2 * P + 1 - 10 = L  (4th column)
          "div(L + 9, 2) = P", 
          # (2 * P + 1) % 10 = M and P > 4 so 2 * P + 1 - 10 = M  (middle column)
          # so M = L
          "L = M",
          "2 * HAPPY == KLMLK",
         
          # rewrite (R + A + W) % 10 = 0 so we have a formula for W
          "10 - (R + A) % 10 = W", 
       
          # 10 * HAPP - 10 * VER - 10 * NE - 10 * YEA - (R + A + W) = 0
          # tens: (P - R - E - A - (R + A + W) / 10) % 10 = 0
          "(30 + P - R - A - (R + A + W) // 10) % 10 = E",
          
          "HAPPY - A - NEW - YEAR = VERY",
        ],
        answer="YEAR",
        d2i=d2i,
        # A + VERY + NEW + YEAR = HAPPY --> H = 1 as 9xxx + 8xxx is not high enough
        # 2 * H = K and (2 * Y) % 10 = K --> Y = H + 5
        s2d=dict(H=1, Y=6, K=2),
        # exclude the s2d entries from the distinct parameter
        # they are handled more cleanly/efficiently by adding them to d2i
        distinct="AENPRVW",
        verbose=0,    # use 256 to see the generated code
      )
      
      # print answers
      for (_, ans) in p.solve():
        print(f"year = {ans}")
      

      Jim, might it be an idea to internally remove the s2d symbols from distinct and add their values internally to d2i?

      Like

    • GeoffR 3:23 pm on 11 August 2022 Permalink | Reply

      A full permutation solution was quicker than expected.

      
      from itertools import permutations
      from enigma import is_palindrome as is_pal, timer
      
      timer.start() 
      for p1 in permutations ('123456789'):
          a, v, e, r, y, n, w, h, p = p1
          year = int(y + e + a + r)
          if year % 2 != 1: continue
          new = int(n + e + w)
          very = int(v + e + r + y)
          happy = int(h + a + p + p + y)
      
          # check happy * 2 is a palindrome
          if is_pal(str(2 * happy)):
              # the alphametic sum
              if int(a) + new + very + year == happy:       
                 print(f"YEAR = {year}, Palindrome = {2 * happy}")
                 timer.stop()
                 timer.report()
      
      # YEAR = 6925, Palindrome = 25552
      # [timing] total time: 0.1265317s (126.53ms)
      
      

      Like

  • Jim Randell 7:35 am on 9 August 2022 Permalink | Reply
    Tags:   

    Teaser 2733: Letter-writing 

    From The Sunday Times, 8th February 2015 [link] [link]

    Last year I went to calligraphy lessons. They were held weekly, on the same day each week, for nine consecutive months. Actually I only went to 15 of the lessons, and after the course was over I listed the dates of those lessons that I had attended. In order to practise my new skills I wrote the dates in words (in the format “First of January” etc.) and I found to my surprise that each date used a different number of letters.

    What were the dates of the first and last lessons that I attended?

    [teaser2733]

     
    • Jim Randell 7:36 am on 9 August 2022 Permalink | Reply

      See also: Teaser 2832.

      The lessons were for “9 months”, so let’s suppose there were 39 weekly lessons, of which the setter attended 15.

      This Python program runs in 68ms.

      Run: [ @replit ]

      from datetime import (date, timedelta)
      from enigma import (repeat, trim, int2words, group, subsets, cache, sprintf as f)
      
      # map month numbers to English names
      month = dict(enumerate([
          'january', 'february', 'march', 'april', 'may', 'june',
          'july', 'august', 'september', 'october', 'november', 'december',
        ], start=1)
      )
      
      # ordinals that aren't cardinal + "th", or cardinal - "y" + "ieth"
      _ordinal = {
        1: 'first', 2: 'second', 3: 'third', 5: 'fifth',
        8: 'eighth', 9: 'ninth', 12: 'twelfth',
      }
      
      # return the ordinal of a number
      @cache
      def ordinal(n):
        if n in _ordinal: return _ordinal[n]
        if n < 20: return int2words(n) + 'th'
        (t, r) = divmod(n, 10)
        if r == 0: return trim(int2words(n), tail=1) + 'ieth'
        return int2words(n - r) + ' ' + ordinal(r)
      
      # return the length of the inscription for a date
      @cache
      def inscribe(d):
        t = f("{d} of {m}", d=ordinal(d.day), m=month[d.month])
        return sum(x.isalpha() for x in t)
      
      # generate length <k> sequences of possible dates
      def generate(k):
        (i1, i7) = (timedelta(days=1), timedelta(days=7))
        d = date(2014, 1, 1)
        while True:
          # generate 39 weeks of dates
          ds = list(repeat((lambda d: d + i7), d, k))
          # are we done?
          if ds[-1].year > 2014: break
          yield ds
          # increase start date
          d += i1
      
      # record possible date spans
      rs = set()
      
      # consider possible dates for 39 weekly lessons
      for ds in generate(39):
        # group dates by letter count
        g = group(ds, by=(lambda d: inscribe(d)))
        # choose 15 letter counts
        for ks in subsets(g.keys(), size=15):
          # find earliest and latest possible dates
          dmin = min(min(g[k] for k in ks))
          dmax = max(max(g[k] for k in ks))
          rs.add((dmin, dmax))
      
      # output solution(s)
      for (dmin, dmax) in rs:
        print(f("{dmin} -> {dmax}"))
      

      Solution: The first lesson attended was on the 5th April. The final lesson attended was on 27th December.


      In fact there is only one sequence of 39 weekly dates in 2014 that gives at least 15 different lengths:

      10 letters: “Third of May”; “Tenth of May”
      11 letters: “Fifth of July”
      12 letters: “Fifth of April”
      13 letters: “Seventh of June”; “Twelfth of July”; “Ninth of August”
      14 letters: “Twelfth of April”; “Second of August”
      15 letters: “Fourth of October”; “First of November”; “Sixth of December”
      16 letters: “Seventeenth of May”; “Thirty first of May”; “Fourteenth of June”; “Nineteenth of July”; “Sixth of September”; “Eighth of November”
      17 letters: “Nineteenth of April”; “Twenty fourth of May”; “Twenty first of June”; “Twenty sixth of July”; “Sixteenth of August”; “Thirtieth of August”; “Eleventh of October”
      18 letters: “Twenty eighth of June”
      19 letters: “Twenty third of August”; “Eighteenth of October”; “Fifteenth of November”; “Twentieth of December”
      20 letters: “Twentieth of September”; “Twenty fifth of October”; “Thirteenth of December”
      21 letters: “Thirteenth of September”; “Twenty ninth of November”
      22 letters: “Twenty second of November”
      23 letters: “Twenty seventh of December”
      24 letters: “Twenty seventh of September”

      And this gives exactly 15 different lengths of inscription. So, each length must be represented by a single date that the setter attended.

      The period covered is 5th April – 27th December, and as 5th April is the only date with an inscription of 12 letters, and 27th December is the only date with an inscription of 23 letters, the setter must have attended the actual first and last lessons, and these give the answer to the puzzle.

      Like

  • Jim Randell 5:26 pm on 5 August 2022 Permalink | Reply
    Tags:   

    Teaser 3124: Lawn order 

    From The Sunday Times, 7th August 2022 [link] [link]

    A gardener was laying out the border of a new lawn; he had placed a set of straight lawn edging strips, of lengths 16, 8, 7, 7, 7, 5, 4, 4, 4 & 4 feet, which joined at right angles to form a simple circuit. His neighbour called over the fence, “Nice day for a bit of garden work, eh? Is that really the shape you’ve decided on? If you took that one joined to its two neighbours, and turned them together through 180°, you could have a different shape. Same with that one over there, or this one over here — oh, look, or that other one”. The gardener wished that one of his neighbours would turn through 180°.

    What is the area of the planned lawn, in square feet?

    [teaser3124]

     
    • Jim Randell 12:41 pm on 6 August 2022 Permalink | Reply

      This Python program generates possible layouts from the given strips, and then checks to see if they form a non-crossing closed circuit. If so, it counts how many adjacent groups of 3 strips can be rotated to also form a different non-crossing closed circuit. If we find 4 (or more), then the original layout is a viable solution.

      The following program runs in 399ms.

      Run: [ @replit ]

      from enigma import (multiset, tuples, irange, update, reverse, ediv, join, printf)
      
      # fit the sections together, with right-angled joins, to form a circuit
      def solve(ss, x=0, y=0, dx=1, dy=0, rs=[]):
        # last section?
        if ss.size() == 1:
          r = ss.peek()
          (x_, y_) = (x + r * dx, y + r * dy)
          if x_ == y_ == 0:
            rs_ = tuple(rs + [(r, (dx, dy))])
            if check(rs_):
              yield rs_
        else:
          # choose a section
          for r in ss.keys():
            ss_ = ss.copy().remove(r)
            (x_, y_) = (x + r * dx, y + r * dy)
            if abs(x_) + abs(y_) > ss_.sum(): continue
            rs_ = rs + [(r, (dx, dy))]
            # turn one way ...
            yield from solve(ss_, x_, y_, dy, dx, rs_)
            if not rs: break
            # ... or the other
            yield from solve(ss_, x_, y_, -dy, -dx, rs_)
      
      # check the sections form a simple circuit
      def is_circuit(rs):
        x = y = 0
        # walk the path, ensuring each step visits a new spot
        pts = set()
        for (r, (dx, dy)) in rs:
          for i in irange(1, r):
            k = (x, y) = (x + dx, y + dy)
            if k in pts: return False
            pts.add(k)
        # are we back at the start?
        return (x == y == 0)
      
      # remove rotations / reflections
      def is_duplicate(rs, seen=set()):
        # have we seen it before?
        if rs in seen: return True
        # record this shape, along with its rotation / reflection
        seen.add(rs)
        (rs1, rrs) = (rs[:1], reverse(rs[1:]))
        seen.add(rs1 + rrs)
        seen.add(rs1 + tuple((r, (dx, -dy)) for (r, (dx, dy)) in rrs))
        return False
      
      # check the sections meet the puzzle requirements
      def check(rs):
        # have we seen this shape before?
        if is_duplicate(rs): return False
        # does the initial layout form a simple circuit?
        if not is_circuit(rs): return False
      
        # count the number of rotatable groups of 3 adjacent sections
        k = 0
        n = len(rs)
        for (j, ss) in enumerate(tuples(rs, 3, circular=1)):
          ((r1, d1), _, (r3, d3)) = ss
          if r1 != r3 or d1 != d3:
            # rotate the group
            rs_ = update(rs, [j, (j + 2) % n], [(r3, d3), (r1, d1)])
            k += is_circuit(rs_)
        # we need at least 4 rotatable groups
        if k < 4: return False
        # looks good
        return True
      
      # calculate the area of a polygon with vertices <vs> [see Enigma 664]
      def area(vs, m=0.5):
        return m * sum(x1 * y2 - x2 * y1 for ((x1, y1), (x2, y2)) in tuples(vs, 2, circular=1))
      
      # calculate the area of a circuit
      def circuit_area(rs):
        vs = list()
        (x, y) = (0, 0)
        for (r, (dx, dy)) in rs:
          vs.append((x, y))
          x += r * dx
          y += r * dy
        return ediv(abs(area(vs, m=1)), 2)
      
      # format a circuit
      def _fmt(rs):
        d = { (1, 0): 'E', (0, 1): 'N', (-1, 0): 'W', (0, -1): 'S' }
        for (r, k) in rs:
          yield join((d[k], r))
      fmt = lambda rs: join(_fmt(rs), sep=" ", enc="[]")
      
      # the sections
      sections = multiset.from_seq([16, 8, 7, 7, 7, 5, 4, 4, 4, 4])
      
      # find viable circuits
      for rs in solve(sections):
        printf("area = {a} {rs}", rs=fmt(rs), a=circuit_area(rs))
      

      Solution: The area of the planned lawn is 176 square feet.


      The planned layout looks like this:

      (The code used to generate the diagram is given in my program on replit [link]).

      Starting from the bottom left-hand corner and proceeding anti-clockwise around the shape the length of the sections are:

      16 (turn left)
      4 (turn right)
      5 (turn left)
      4 (turn left)
      7 (turn right)
      4 (turn left)
      7 (turn left)
      4 (turn right)
      7 (turn left)
      8 (back to start)

      (Of course rotations and reflections of this shape will also work).

      And the four groups of three adjacent sections that can be rotated through 180°, are shown below:

      Liked by 2 people

      • Jim Randell 4:37 pm on 9 August 2022 Permalink | Reply

        And here is a faster (but slightly longer) alternative implementation.

        Instead of representing the sections as (length, (dx, dy)) tuples, we just use their lengths, as the directions alternate horizontal and vertical, and we use the sign of the length to indicate direction.

        We select sections by dividing the available sections into 2 groups the lengths of which can be assigned positive/negative values to give a zero sum in both horizontal and vertical directions.

        We then proceed as described above.

        This program runs in 63ms. (Internal run time is 7.3ms).

        Run: [ @replit ]

        from enigma import (multiset, ediv, interleave, sign, irange, reverse, tuples, update, join, printf)
        
        # choose <n> sections from <ss>, with length sum <t>
        def choose(ss, n, t, xs=[]):
          # final section?
          if n == 1:
            if t in ss or -t in ss:
              yield xs + [t]
          else:
            # choose the next section
            for x in ss.keys():
              ss_ = ss.copy().remove(x)
              yield from choose(ss_, n - 1, t - x, xs + [x])
              yield from choose(ss_, n - 1, t + x, xs + [-x])
        
        # fit sections together, with right-angled joins, to form a circuit
        def solve(ss):
          # number of horizontal/vertical sections (which must alternate)
          n = ediv(ss.size(), 2)
          # choose an initial horizontal section
          h = ss.peek()
          # find n - 1 more to get back to the start
          for hs in choose(ss.copy().remove(h), n - 1, -h, [h]):
            ss_ = ss.difference(abs(x) for x in hs)
            # choose an initial vertical section
            for v in ss_.keys():
              # find n - 1 more to get back to the start
              for vs in choose(ss_.copy().remove(v), n - 1, -v, [v]):
                rs = tuple(interleave(hs, vs))
                if check(rs):
                  yield rs
        
        # check the sections form a simple circuit
        def is_circuit(rs):
          x = y = 0
          # walk the path, ensuring each step visits a new spot
          pts = set()
          for (i, r) in enumerate(rs):
            if i % 2 == 0:
              (r, dx, dy) = (abs(r), sign(r), 0)
            else:
              (r, dx, dy) = (abs(r), 0, sign(r))
            for i in irange(1, r):
              k = (x, y) = (x + dx, y + dy)
              if k in pts: return False
              pts.add(k)
          # are we back at the start?
          return (x == y == 0)
        
        # remove rotations / reflections
        def is_duplicate(rs, seen=set()):
          # have we seen it before?
          if rs in seen: return True
          # record this shape, along with its rotation / reflection
          seen.add(rs)
          (rs1, rrs) = (rs[:1], reverse(rs[1:]))
          seen.add(rs1 + rrs)
          seen.add(rs1 + tuple((-r if i % 2 == 1 else r) for (i, r) in enumerate(rrs, start=1)))
          return False
        
        # check the sections meet the puzzle requirements
        def check(rs):
          # have we seen this shape before?
          if is_duplicate(rs): return False
          # does the initial layout form a simple circuit?
          if not is_circuit(rs): return False
        
          # count the number of rotatable groups of 3 adjacent sections
          k = 0
          n = len(rs)
          for (j, ss) in enumerate(tuples(rs, 3, circular=1)):
            (r1, _, r3) = ss
            if r1 != r3:
              # rotate the group
              rs_ = update(rs, [j, (j + 2) % n], [r3, r1])
              k += is_circuit(rs_)
          # we need at least 4 rotatable groups
          if k < 4: return False
          # looks good
          return True
        
        # calculate the area of a polygon with vertices <vs> [see Enigma 664]
        def area(vs, m=0.5):
          return m * sum(x1 * y2 - x2 * y1 for ((x1, y1), (x2, y2)) in tuples(vs, 2, circular=1))
        
        # calculate the area of a circuit
        def circuit_area(rs):
          # calculate the co-ordinates of the vertices
          vs = list()
          (x, y) = (0, 0)
          for (i, r) in enumerate(rs):
            vs.append((x, y))
            if i % 2 == 0:
              x += r
            else:
              y += r
          return ediv(abs(area(vs, m=1)), 2)
        
        # format a circuit
        def _fmt(rs):
          d = { (0, 1): 'E', (1, 1): 'N', (0, -1): 'W', (1, -1): 'S' }
          for (i, r) in enumerate(rs):
            yield join((d[(i % 2, sign(r))], abs(r)))
        fmt = lambda rs: join(_fmt(rs), sep=" ", enc="[]")
        
        # the sections
        sections = multiset.from_seq([16, 8, 7, 7, 7, 5, 4, 4, 4, 4])
        
        # find viable circuits
        for rs in solve(sections):
          printf("area = {a} {rs}", rs=fmt(rs), a=circuit_area(rs))
        

        Like

        • Frits 6:23 pm on 9 August 2022 Permalink | Reply

          @Jim,

          Can you tell me the scope of the “seen” parameter in is_duplicate() ?
          I expected is_duplicate() to do nothing as “seen” seems to be a local variable.

          Test:

           
          def xx(a=0):
            a += 1
            print("a =", a)
            return
            
          xx()
          xx()
          
          # a = 1
          # a = 1
          
          def yy(n, b=set()):
            b.add(n)
            print("b =", b)
            return
            
          yy(2)
          yy(3)
          
          # b = {2}
          # b = {2, 3}
          

          Do set parameters always have a global scope?

          Like

          • Jim Randell 7:33 pm on 9 August 2022 Permalink | Reply

            In Python the default parameters are attributes of the object (stored under the __defaults__ key), that are initialised when the function is created and shared between calls to the function. So if you use a mutable default the value persists between calls.

            This can be a problem. If you start with a default parameter that is the empty list, add things to it and then return it at the end. The next time the function is called the the list is still full of the values from the previous invocation. This is why pylint reports mutable defaults as “dangerous”.

            But in this case I do want the value to persist between multiple invocations of the function. (So it functions like a static variable in C).

            Originally I used a global variable, but I think this looks neater. However it may not be considered “Pythonic”. But I think as you need to be aware how mutable defaults work, you should be able to use them to your advantage.

            Like

            • Frits 8:03 pm on 9 August 2022 Permalink | Reply

              Thanks.

              Like

            • Jim Randell 8:43 am on 10 August 2022 Permalink | Reply

              There is a [[ static() ]] decorator defined in the enigma.py library, that serves a similar purpose (and works by setting attributes on the function). Using it the code for is_duplicate() would look like this:

              @static(seen=set())
              def is_duplicate(rs, seen=None):
                if seen is None: seen = is_duplicate.seen
                ...
              

              Which would probably makes it clearer to someone who is not familiar with the behaviour of mutable default function arguments.

              This is very similar to just using a global variable:

              _is_duplicate_seen = set()
              def is_duplicate(rs, seen=_is_duplicate_seen):
                ...
              

              And removing the global reference to the set() gets us back to the start:

              def is_duplicate(rs, seen=set()):
                ...
              

              Really we are just changing which namespace the set seen is stored in.

              Like

        • Frits 5:57 pm on 10 August 2022 Permalink | Reply

          @Jim,

          I noticed this program processes 64 circuits and my program 160 circuits.
          My program probably processes too many circuits as I didn’t bother filtering out all rotations/reflections.

          You choose an initial vertical section (v). Are you sure this is allowed?

          It seems you disregard the option that v may not have to be attached to the initial horizontal section (h) in the final solution.

          Like

          • Jim Randell 6:09 pm on 10 August 2022 Permalink | Reply

            @Frits: It’s not right. It is only supposed to be the direction of the initial vertical section that is fixed. I’ll fix that up.

            (Fixed now. As it was it seemed to always choose an initial vertical 4, and one of those must be attached to 16, so all viable possibilities were considered anyway).

            Like

            • Frits 6:58 pm on 10 August 2022 Permalink | Reply

              Now you process the expected 80 circuits.

              Like

    • Frits 2:20 pm on 7 August 2022 Permalink | Reply

      Based on Jim’s ground work. Working with points is probably less efficient than working with directions dx/dy. The program runs in 15ms.

      Uncomment the four plot related lines for displaying the polygon.

       
      from itertools import permutations, combinations, product
      #import matplotlib.pyplot as plt
      
      # circular list,  example [H,B,C,A]: [(H,B,C), (B,C,A), (C,A,H), (A,H,B)]
      quads = lambda lst, n: [(lst[i],
                               lst[(i + 1) % n],
                               lst[(i + 2) % n],
                               lst[(i + 3) % n]) for i in range(n)]
      
      # return entries from <a> minus the entries from <b>
      def diff(a, b):
        a_ = a.copy()
        for x in b:
          a_.remove(x)
        return a_  
      
      # calculate the area of a polygon with vertices <vs>
      def area(vs):
        return abs(sum(x1 * y2 - x2 * y1
                   for ((x1, y1), (x2, y2)) in zip(vs, vs[1:] + [vs[0]]))) // 2
      
      # return all positive and negative possibilities of numbers in <lst>
      def pos_neg_possibilities(lst):
        return list(product(*((x, -x) for x in lst)))  
      
      # return vertices list from two lists of directions  
      def build_vertices(lst):
        vs = []
        (x, y) = (0, 0)
        # weave elements from two lists
        for j, p in enumerate([y for x in list(zip(lst[0], lst[1])) for y in x]):
          (x, y) = (x + p * (j % 2 == 0), y + p * (j % 2))
          vs.append((x, y))  
       
        return vs
      
      # return all points on horizontal or vertical line between points p1 and p2
      # (excluding p2 itself)  
      def points(p1, p2):
        assert p1[0] == p2[0] or p1[1] == p2[1]
       
        ver = 1 if p1[0] == p2[0] else 0
        hor = 1 - ver
        stp = 1 if p2[0] > p1[0] or p2[1] > p1[1] else -1
        if hor:
          pts = [(i, p1[1]) for i in range(p1[0], p2[0], stp)]
        else:
          pts = [(p1[0], i) for i in range(p1[1], p2[1], stp)]
       
        return pts
         
      # check if the circuit sections overlap
      def do_overlap(vs, prt=0):
        (x, y) = (0, 0)
        pts = {(x, y)}
       
        vertices = []
        # select 2 adjacent points p and q
        for j, (p, q) in enumerate(zip(vs, vs[1:] + [vs[0]])):
          for p in points(p, q):
            # only accept overlap for origin (0, 0) on last check
            if p in pts and (p != (0, 0) or j < len(vs) - 1):
              return True
            pts.add(p)  
      
        return False
         
      # check if the circuit allows for more than three rotations
      def check_rotation(vs):
        # count the number of rotatable groups of 3 adjacent sections
        k = 0
        n = len(vs)
       
        # 3 adjacent sections so check a group of 4 points
        for (j, ss) in enumerate(quads(vs, n)):
          ((x1, y1), (x2, y2), (x3, y3), (x4, y4)) = ss
          # check on different length or different direction
          if abs(x2 - x1) + abs(y2 - y1) != abs(x4 - x3) + abs(y4 - y3) or \
             ((x2 - x1 + y2 - y1) > 0) != ((x4 - x3 + y4 - y3) > 0):
           
            # rotate the group by adjusting the middle points
            vs_ = vs.copy()
            vs_[(j + 1) % n] = (x1 + x4 - x3, y1 + y4 - y3)
            vs_[(j + 2) % n] = (x4 + x1 - x2, y4 + y1 - y2)
           
            k += not(do_overlap(vs_))
       
        # we need 4 (or more) rotatable groups
        return (k > 3)  
      
      strips = sorted([16, 8, 7, 7, 7, 5, 4, 4, 4, 4], reverse=True)
      
      opts = []  
      # definition direction: direction strip (-1 or 1) times length of the strip
      
      # we split the strips into two groups for horizontal and vertical directions
      # always place the first strip horizontally
      
      # find 4 strips besides the first strip (16)
      for c in combinations(strips[1:], 4):  
        hor = c + (strips[0], )
        vert = diff(strips, hor)  # rest of strips
       
        # do combinations of negative/positive <hor> elements sum to zero?
        hor_dir = set(tuple(sorted(x)) for x in pos_neg_possibilities(hor)
                      if sum(x) == 0 and -strips[0] not in x)
        if hor_dir:
          # do combinations of negative/positive <vert> elements sum to zero?
          vert_dir = set(tuple(sorted(x)) for x in pos_neg_possibilities(vert)
                         if sum(x) == 0)
          if not vert_dir: continue        
          opts.append([(hor, vert), (hor_dir, vert_dir)])
      
      
      # check if we can find valid circuits with enough rotations
      for (hor, vert), (hor_dir, vert_dir) in opts:
        # for all combinations of directions
        for h1, v1 in product(hor_dir, vert_dir):
          # make sure highest strip (16) is up front
          # for every possible permutation of horizontals and vertical directions
          for (h2, v2) in list(set(product([(h1[-1], ) + x
                                             for x in permutations(h1[:-1])],
                                           permutations(v1)))):
            # build vertices from two lists of directions                                
            vertices = build_vertices((h2, v2))
            # integrity check  (not needed)
            if vertices[-1] != (0, 0):
              continue
           
            if do_overlap(vertices, 0): continue
            if not check_rotation(vertices): continue
           
            print("area =", area(vertices), vertices)
            #plt.plot(*zip(*vertices), '-o')
            #plt.title(vertices)
            #plt.show()
      

      Liked by 1 person

      • Jim Randell 5:26 pm on 7 August 2022 Permalink | Reply

        @Frits: Good stuff. I was beginning to worry no-one else was going to try this one.

        Like

        • Frits 6:56 pm on 7 August 2022 Permalink | Reply

          @Jim, it was not so easy this week. I had problems with the “turn 180 degrees “concept.

          Like

    • Frits 2:18 pm on 14 August 2022 Permalink | Reply

      Code to print polygons with 90 degree angles.

      (I have problems installing matplotlib under PyPy)

         
      # plot polygon with print statements
      # input is a list of vertices
      def print_polygon(pts):
      
        # return all points between integer coordinates p1 and p2 
        def line_points(p1, p2):
          if any(type(x) != int for x in [p1[0], p1[1], p2[0], p2[1]]):
            # not integer coordinates
            return []
          
          # number of intermediate points
          n = max(abs(p2[0] - p1[0]), abs(p2[1] - p1[1])) - 1
          
          # calculate intervals
          x1, rx = divmod(p2[0] - p1[0], n + 1)
          y1, ry = divmod(p2[1] - p1[1], n + 1)
          
          return tuple((p1[0] + i * x1 + (i * rx / (n + 1) if rx else 0), 
                        p1[1] + i * y1 + (i * ry / (n + 1) if ry else 0))
                       for i in range(n + 2))
       
        x_lo = min(x for (x, y) in pts)
        x_hi = max(x for (x, y) in pts)
        y_lo = min(y for (x, y) in pts)
        y_hi = max(y for (x, y) in pts)
        
        # build a set of all points on the polygon
        pts_pol = set()
        for p1, p2 in zip(pts, pts[1:] + [pts[0]]):  
          pts_pol.update(line_points(p1, p2))
          
        #print(sorted(pts_pol, key = lambda x: x[::-1] , reverse=True))
        
        print()
        # draw lines from top to bottom
        for v in range(y_hi, y_lo - 1, -1):
          on_line = {x for x, y in pts_pol if y == v}
          print("    |" if v % 5 else str(v).ljust(3) + "-|", end="")
          for h in range(x_lo, x_hi + 1):
            print("*" if h in on_line else  " ", end=" ")
          print()  
        
        # print three horizontal scale lines
        print("    |", end="")
        for x in range(x_lo + 1, x_hi + 1):
          print("__", end="")
        print("_")  
        
        print("    ", end="")
        for i, x in enumerate(range(x_lo, x_hi + 1)):
          print("  " if x % 5 else " |", end="")
        print()  
        
        print("    ", end="")
        for x in range(x_lo, x_hi + 1):
          print("  " if x % 5 else str(x).rjust(2), end="")
        print()  
      
      print_polygon([(16, 0), (16, 4), (21, 4), (21, 8), (14, 8), (14, 12), (7, 12), (7, 8), (0, 8), (0, 0)])       
      
       
       
          |              * * * * * * * *
          |              *             *
      10 -|              *             *
          |              *             *
          |* * * * * * * *             * * * * * * * *
          |*                                         *
          |*                                         *
      5  -|*                                         *
          |*                               * * * * * *
          |*                               *
          |*                               *
          |*                               *
      0  -|* * * * * * * * * * * * * * * * *
          |___________________________________________
           |         |         |         |         |
           0         5        10        15        20
      

      Like

      • Jim Randell 5:14 pm on 14 August 2022 Permalink | Reply

        @Frits: You might be interested in the simple plotting library I use to generate a lot of the diagrams for puzzles (including for the solution of this puzzle – I included code to plot the shapes in the code I put on replit). It only requires the tkinter library. I use it with pypy all the time.

        I have uploaded it to GitHub. [@github]

        Like

  • Jim Randell 8:26 am on 4 August 2022 Permalink | Reply
    Tags:   

    Teaser 2725: Darts match 

    From The Sunday Times, 14th December 2014 [link] [link]

    Andrew, Alexander, Austin, Anthony, Benjamin, Charles, Christopher, Elijah, Jacob, Jayden, Jackson, James, Jason, Mason, Michael, Nathan, Newman, Robert, Samuel and William entered a darts competition, arranged into five teams of four players. It turned out that, for any pair of members of any team, there were just two letters of the alphabet that occurred (once or more) in both their names. The names in each team were arranged alphabetically, the first name being the captain and the last name the reserve. Then the teams were numbered 1 to 5 in alphabetical order of the captains.

    In the order 1 to 5, who were the reserves?

    [teaser2725]

     
    • Jim Randell 8:27 am on 4 August 2022 Permalink | Reply

      This puzzle is slightly different from the usual kind of grouping puzzle, but we can still use some of the [[ grouping ]] functions from the enigma.py library.

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

      Run: [ @replit ]

      from enigma import (grouping, join, printf)
      
      # available players
      names = [
        'Andrew', 'Alexander', 'Austin', 'Anthony', 'Benjamin', 'Charles',
        'Christopher', 'Elijah', 'Jacob', 'Jayden', 'Jackson', 'James', 'Jason',
        'Mason', 'Michael', 'Nathan', 'Newman', 'Robert', 'Samuel', 'William',
      ]
      
      # grouping function
      fn = grouping.share_letters(2)
      
      # form the names <ns> into teams of size <k>
      def teams(ns, k, ts=[]):
        # are we done?
        if not ns:
          yield ts
        else:
          # find the next captain
          cap = min(ns)
          # and 3 team members
          for team in grouping.gang(k - 1, cap, ns.difference([cap]), fn):
            team = [cap] + sorted(team)
            # solve for the remaining names
            yield from teams(ns.difference(team), k, ts + [team])
      
      for ts in teams(set(names), 4):
        for (i, team) in enumerate(ts, start=1):
          printf("Team {i}: {team}", team=join(team, sep=", "))
        printf()
      

      Solution: The reserves are (Team 1-5): William, Samuel, Robert, Newman, Michael.

      The full teams are:

      Team 1: Alexander, Austin, James, William
      Team 2: Andrew, Christopher, Jason, Samuel
      Team 3: Anthony, Benjamin, Charles, Robert
      Team 4: Elijah, Jackson, Nathan, Newman
      Team 5: Jacob, Jayden, Mason, Michael

      Like

    • Frits 8:04 pm on 5 August 2022 Permalink | Reply

      A lot more work but already solved before recursion (ie parameter teams will have 5 teams) .

         
      from itertools import combinations
      
      # check that each string shares exactly <k> letters
      shr_lttrs = lambda s1, s2, k: len(set(s1.lower()) & set(s2.lower())) == k
      
      # form the names <ns> into teams of size <k>
      def form_teams(ns, k, ts=[]):
        # are we done?
        if not ns:
          yield ts
        else:
          # find the name with the least matches
          key = min({k: v for k, v in d.items() if k in ns}.items(), 
                     key=lambda x: len(x[1]))
          # and 3 team members
          for rest in combinations([x for x in key[1] if x in ns], 3):
            # these 3 names should have exactly 2 letters in common
            if any(not y in d[x] for x, y in zip(rest, rest[1:])): continue
            
            team = sorted((key[0], ) + rest)
            # solve for the remaining names
            yield from form_teams(ns.difference(team), k, ts + [team])
            
      
      # available players
      vs = [
        'Andrew', 'Alexander', 'Austin', 'Anthony', 'Benjamin', 'Charles',
        'Christopher', 'Elijah', 'Jacob', 'Jayden', 'Jackson', 'James', 'Jason',
        'Mason', 'Michael', 'Nathan', 'Newman', 'Robert', 'Samuel', 'William',
      ]
      
      vs = sorted(vs)
      
      # create dictionary: name --> matches
      d = {vs[i]: {x for j, x in enumerate(vs[:i] + vs[i + 1:]) 
                       if shr_lttrs(vs[i], x, 2)} for i in range(len(vs))}
      
      teams = []
      dsize = -1
      # process until no more changes to dictionary
      while dsize != sum(len(v) for v in d.values()):
        dsize = sum(len(v) for v in d.values())
        
        # if a match doesn't share exactly 2 letters with at least 2 other matches
        # it can be removed from the dictionary as we we need 4 members in a team
        d = {k: {x for x in v if sum(x != y and y in d[x] for y in v) > 1} 
                 for k, v in d.items()}
       
        # if only three matches left we have finalized a team 
        match3 = [x for k, v in list(d.items()) 
                  for x in [k] + list(v) if len(v) == 3]
        
        # add these persons to teams (removing duplicates while preserving order)
        teams += list(dict.fromkeys(match3))
       
        # maintain dictionary for persons in teams
        d = {k: [x for x in v if x not in teams] 
                 for k, v in d.items() if k not in teams}
               
      # reduce values for persons in teams
      vs = [x for x in vs if x not in teams]
      
      # solve for remaining people
      for ts in form_teams(set(vs), 4):
        i = 0
        for (i, team) in enumerate(ts, start=1):
          print(f"Team {i}: {', '.join(team)}")
        for j in range(len(teams) // 4):
          i += 1
          print(f"Team {i}: {', '.join(sorted(teams[j * 4:j * 4 + 4]))}")
        print()
      

      Like

  • Jim Randell 7:58 am on 2 August 2022 Permalink | Reply
    Tags:   

    Teaser 2534: Fiftieth anniversary 

    From The Sunday Times, 17th April 2011 [link] [link]

    We have recently celebrated the 50th anniversary of the Teaser column. At the party for the setters they gave each letter of the alphabet a different number from 1 to 26 (e.g. they made A = 7). Appropriately, this was done in such a way that, for each setter present, the values of the letters of their surname added up to 50. Angela Newing was there (so N+E+W+I+N+G = 50), as were Nick MacKinnon and Hugh Bradley. Only two of Graham Smithers, Danny Roth, Andrew Skidmore, John Owen and Victor Bryant could make it.

    Which two?

    [teaser2533]

     
    • Jim Randell 7:59 am on 2 August 2022 Permalink | Reply

      (See also: Teaser 2884).

      With a bit of analysis we can determine the required answer, and write a program to give us a viable assignment is a reasonable amount of time.

      We are given:

      A = 7
      NEWING = 50
      MACKINNON = 50
      BRADLEY = 50

      Hence:

      3N + CIKMO = 43
      BDELRY = 43
      ⇒ 3N + BCDEIKLMORY = 86

      And BCDEIKLMORY (11 letters) must be at least 71, so:

      3N ≤ 15
      N ≤ 5

      But if N is in (1, 2, 3, 4, 5), the minimal value of BCDEIKLMORY is increased to 83, so:

      3N ≤ 3
      N = 1
      BCDEIKLMORY = 83

      So the letters BCDEIKLMORY are assigned (2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13) (in some order).

      Now, all values from 1 – 13 are accounted for, leaving GHSTW to be assigned values from 14 – 26.

      SMITHERS = 2S + TH + EIMR ≥ 73

      So SMITHERS cannot be 50.

      SKIDMORE = S + IKMO + EDR = S + (40 – C) + (43 – BLY) ≥ 51

      So SKIDMORE cannot be 50.

      OWEN = 50 ⇒ O = ING = IG + 1

      But O must have a value ≤ 13 and G must have a value ≥ 14.

      So OWEN cannot be 50.

      Hence the only remaining candidates are ROTH and BRYANT.

      All that remains is to find a viable assignment of letters to values to show the puzzle has a solution.

      And we can use the [[ SubstitutedExpression ]] solver from the enigma.py library to do that.

      The following run file executes in 66ms. (The internal run time of the generated program is 48µs).

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      SubstitutedExpression
      
      --base="27"
      --digits="1-26"
      
      # fixed values
      --assign="A,7"
      --assign="N,1"
      
      # limits on other values
      --invalid="1|2|3|4|5|6|7|8|9|10|11|12|13,GHSTW"
      --invalid="14|15|16|17|18|19|20|21|22|23|24|25|26,BCDEIKLMORY"
      
      # these sum to 50
      "N + E + W + I + N + G == 50"
      "M + A + C + K + I + N + N + O + N == 50"
      "B + R + A + D + L + E + Y == 50"
      "R + O + T + H == 50"
      "B + R + Y + A + N + T == 50"
      
      # these don't
      "S + M + I + T + H + E + R + S != 50"
      "S + K + I + D + M + O + R + E != 50"
      "O + W + E + N != 50"
      
      --template=""
      --first  # we only need a single solution
      

      Solution: The other two setters were: Danny ROTH and Victor BRYANT.


      Here is one possible assignment found by the run file:

      A = 7
      B = 9
      C = 12
      D = 4
      E = 3
      G = 26
      H = 25
      I = 5
      K = 13
      L = 11
      M = 8
      N = 1
      O = 2
      R = 6
      S = 15
      T = 17
      W = 14
      Y = 10
      (F J P Q U V X Z) = (16, 18, 19, 20, 21, 22, 23, 24)

      Using these values we get:

      NEWING = 1 + 3 + 14 + 5 + 1 + 26 = 50
      MACKINNON = 8 + 7 + 12 + 13 + 5 + 1 + 1 + 2 + 1 = 50
      BRADLEY = 9 + 6 + 7 + 4 + 11 + 3 + 10 = 50
      ROTH = 6 + 2 + 17 + 25 = 50
      BRYANT = 9 + 6 + 10 + 7 + 1 + 17 = 50

      SMITHERS = 15 + 8 + 5 + 17 + 25 + 3 + 6 + 15 = 94
      SKIDMORE = 15 + 13 + 5 + 4 + 8 + 2 + 6 + 3 = 56
      OWEN = 2 + 14 + 3 + 1 = 20

      Without the [[ --first ]] parameter we find there are 33,182,352 possible assignments.

      Like

    • GeoffR 9:59 am on 2 August 2022 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..26:A;   var 1..26:B;   var 1..26:C;   var 1..26:D;
      var 1..26:E;   var 1..26:F;   var 1..26:G;   var 1..26:H;   
      var 1..26:I;   var 1..26:J;   var 1..26:K;   var 1..26:L;
      var 1..26:M;   var 1..26:N;   var 1..26: O;  var 1..26:P;   
      var 1..26:Q;   var 1..26:R;   var 1..26:S;   var 1..26:T;   
      var 1..26:U;   var 1..26:V;   var 1..26:W;   var 1..26:X;   
      var 1..26:Y;   var 1..26:Z;
      
      constraint all_different ([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,
      P,Q,R,S,T,U,V,W,X,Y,Z]);
      
      constraint A == 7;
      
      % Letters of following names sum to 50
      constraint N+E+W+I+N+G = 50;
      constraint M+A+C+K+I+N+N+O+N == 50;
      constraint B+R+A+D+L+E+Y == 50;
      
      % Letters of only two of Smithers, Roth, Skidmore,
      % Owen and Bryant, sum to 50
      constraint sum([ S+M+I+T+H+E+R+S == 50, R+O+T+H == 50,
      S+K+I+D+M+O+R+E == 50, O+W+E+N == 50, B+R+Y+A+N+T == 50]) == 2;
      
      solve satisfy;
      
      output [ "SMITHERS = " ++ show(S+M+I+T+H+E+R+S) ++ "\n"
      ++ "ROTH = " ++ show(R+O+T+H) ++ "\n"
      ++ "SKIDMORE = " ++ show(S+K+I+D+M+O+R+E) ++ "\n"
      ++ "OWEN = " ++ show(O+W+E+N) ++ "\n"
      ++ "BRYANT = " ++ show(B+R+Y+A+N+T) ];
      
      % Typical solution of multiple solutions
      % SMITHERS = 90
      % ROTH = 50  <<<
      % SKIDMORE = 56
      % OWEN = 22
      % BRYANT = 50  <<<
      % ----------
      % Only ROTH and BRYANT sum to 50 for 5 extra names.
      
      

      Like

  • Jim Randell 11:56 am on 31 July 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 161: 100-yard race 

    From The Sunday Times, 10th May 1964 [link]

    Harry, Kenneth, Lionel, Martin, Nicholas and Oliver were, the competitors in the 100-yard race on Sports Day. They wore cards numbered 1, 2, 3, 4, 5, 6 but not in that order. In no case was the position of any of the competitors the same as his card number but two of the competitors had positions equal to each other’s card number.

    Nicholas was 5th and his card number was the same as Kenneth’s position. Harry’s card number was the same as Oliver’s position which was 4th. Martin’s card number was 1.

    It was found that the sum of the products of each competitor’s position and card number was 61.

    Place the competitors in the order in which they finished the race and give their card numbers.

    This puzzle was included in the book Sunday Times Brain Teasers (1974, edited by Ronald Postill).

    [teaser161]

     
    • Jim Randell 11:57 am on 31 July 2022 Permalink | Reply

      This Python program runs in 56ms. (Internal run time is 1.3ms).

      Run: [ @replit ]

      from enigma import (irange, subsets, reverse, diff, singleton, printf)
      
      pos = list(irange(1, 6))
      
      # consider the cards in each position (1st, ..., 6th)
      for ps in subsets(pos, size=6, select="D"):
        # card: map pos -> card
        card = dict(enumerate(ps, start=1))
        # the sum of the position/card products is 61
        if sum(i * p for (i, p) in card.items()) != 61: continue
        # there is (at least) one 2-cycle
        if not any(card[p] == i for (i, p) in card.items()): continue
      
        # name: map pos -> name
        # "N was 5th"
        # "O was 4th"
        # "K's position is N's card number (N is 5th)"
        # "H's card number is O's position (O is 4th)"
        # "M's card number is 1"
        # so we have enough information to fill out the map
        rcard = reverse(card)
        ks = [5, 4, card[5], rcard[4], rcard[1]]
        ks.append(singleton(diff(pos, ks)))
        if ks[-1] is None: continue
        name = dict(zip(ks, "NOKHML"))
        # check disallowed order
        if all(name[i] == x for (i, x) in zip(pos, "HKLMNO")): continue
      
        # output solution
        for i in pos:
          printf("{i}: {n} = #{c}", c=card[i], n=name[i])
        printf()
      

      Solution: The finishing positions are:

      1st: Lionel (#6)
      2nd: Harry (#4)
      3rd: Kenneth (#2)
      4th: Oliver (#5)
      5th: Nicholas (#3)
      6th: Martin (#1)

      Like

    • Frits 11:53 am on 3 August 2022 Permalink | Reply

       
      from enigma import SubstitutedExpression
      
      # get position from card number
      pos = lambda n, lst: [i for i, x in enumerate(lst, start=1) if x == n][0]
      
      l1 = "[A, B, C, D, E, F]"          # card numbers
      l2 = "[1, 2, 3, 4, 5, 6], " + l1   # positions and card numbers
      z = "zip(" + l2 + ")"
      
      exprs = []
      # position unequal to card number for all competitors
      exprs.append("all(x != y for x, y in " + z + ")")
      # sum of the products of each competitor's position and card number was 61
      exprs.append("sum(x * y for x, y in " + z + ") == 61")
      # two of the competitors had positions equal to each other's card number
      exprs.append("sum((y, x) in " + z + " for x, y in " + z + ") == 2")
      # M ( , 1)
      # N (5, x)
      # O (4,  )
      # H ( , 4)
      # K (x,  )
      # L ( ,  )
      # check on five different positions
      exprs.append("len({pos(1, " + l1 + "), pos(4, " + l1 + "), E, 4, 5}) == 5")
                    
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        exprs,
        answer="((1, A), (2, B), (3, C), (4, D), (5, E), (6, F))",
        digits=range(1, 7),
        distinct=("ABCDEF"),
        env=dict(pos=pos),
        verbose=0,    # use 256 to see the generated code
      )
      
      names = ["", "", "", "Oliver", "Nicholas", ""]
      for (_, ans) in p.solve():
        # dictionary, card --> postion
        d = {y: x for x, y in ans}
        
        names[d[1] - 1] = "Martin"
        names[d[4] - 1] = "Harry"
        names[ans[4][1] - 1] = "Kenneth"
        
        for i in range(6):
          if names[i] == "":
            names[i] = "Lionel"
         
        # integrity check 
        if len(set(names)) != 6: continue
        
        for i in range(6):
          print(f"{ans[i][0]}: {names[i]} with card number {ans[i][1]}")   
      

      Like

  • Jim Randell 3:16 pm on 29 July 2022 Permalink | Reply
    Tags:   

    Teaser 3123: A six-pipe problem 

    From The Sunday Times, 31st July 2022 [link] [link]

     

    A factory makes six types of cylindrical pipe, A to F in decreasing size, whose diameters in centimetres are whole numbers, with type A 50 per cent wider than type B. The pipes are stacked in the yard as a touching row of As with an alternating row of touching Bs and Cs in the next layer, with each B touching two As. Type Ds fill the gap between the As and the ground; Es fill the gap between As and the Bs; and Fs fill the gap between As, Ds and the ground. Finally another row of As is put on top of the stack, giving a height of less than 5 metres.

    What is the final height of the stack in centimetres?

    [teaser3123]

     
    • Jim Randell 3:55 pm on 29 July 2022 Permalink | Reply

      The title of this puzzle is presumably an allusion to Sherlock Holmes’ “three pipe problem” in The Red-Headed League.

      Some judicious applications of Pythogoras’ theorem gets us the answer.

      This Python program runs in 54ms. (Internal runtime is 313µs).

      Run: [ @replit ]

      from enigma import (irange, div, is_square, sq, printf)
      
      # suppose the pipes have diameters a, b, c, d, e, f (in cm)
      # we know h = 2a + c < 500; b = (2/3)a
      for a in irange(6, 249, step=3):
        b = div(2 * a, 3)
        # from pipes ABC
        c = a - b
        # calculate the height of the stack (in centimetres)
        h = 2 * a + c
        if not(h < 500): break
        # from pipes AAD: (a + d)^2 = a^2 + (a - d)^2
        d = div(a, 4)
        if d is None: continue
        # from pipes ABC: (a + e)^2 = (a + c - b - e)^2 + (b + c)^2
        e = div(sq(b) + sq(c) - a * (b - c), 2 * a - b + c)
        if e is None: continue
        # from pipes ADF: (d + f)^2 = (d - f)^2 + x^2; (a + f)^2 = (a - f)^2 + y^2; x + y = a
        r = is_square(a * d)
        if r is None: continue
        f = div(sq(a), 4 * (a + d + 2 * r))
        if f is None: continue
        if a > b > c > d > e > f > 0:
          # output solution (in cm)
          printf("height = {h} cm [a={a} b={b} c={c} d={d} e={e} f={f}]")
      

      Solution: The height of the stack is 420 cm.

      Note that the derivation of d requires a to also be divisible by 4 (as well as 3), so we could consider just multiples of 12 for a for a slight increase in speed.


      Manually:

      If we suppose a = 180k, then we can simplify the expressions used in the program to give the following values:

      a = 180k
      b = 120k
      c = 60k
      d = 45k
      e = 24k
      f = 20k

      And we require all these values to be positive integers, so k takes on a positive integer value.

      The total height of the stack is h = 2a + c = 420k, and we require h < 500.

      So the only permissible value is k = 1, and the answer follows directly.

      Like

    • Frits 2:26 pm on 2 August 2022 Permalink | Reply

      Problem is when to stop with your analysis.
      Ultimately each diameter can be expressed in terms of the smallest diameter.

         
      from enigma import SubstitutedExpression
      
      # AGH, BIJ, CK, DL, EM and FN variables are diameters
      # if (x - y)^2 = z^2 then (2x - 2y)^2 = (2z)^2
      # so we can also calculate with diameters in the Pythagorean formulae
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
          # type A 50 per cent wider than type B
          # diameter A is equal to diameter C + two times radius B
          # a height of less than 5 metres so 2a + c = 7c < 500
          "1 < CK < 72",
          "3 * CK = AGH",
          "2 * CK = BIJ",
          
          # (a + d)^2 = a^2 + (a - d)^2 so 4ad = a^2
          "div(AGH, 4) = DL",
          
          # (a + e)^2 = (a + c - b - e)^2 + (b + c)^2 using a = 3c and b = 2c
          # 6ce + 9c^2 = 4c^2 - 4ce + 9c^2
          "div(2 * CK, 5) = EM",
          
          # (d + f)^2 = (d - f)^2 + x^2; (a + f)^2 = (a - f)^2 + (a - x)^2;
          # so 4df = x^2 and 4af = (a - x)^2
          "4.0 * AGH * FN == (AGH - 2 * (DL * FN)**.5)**2",
          
          # A to F in decreasing size
          "AGH > BIJ > CK > DL > EM > FN"
        ],
        answer="2 * AGH + CK, (AGH, BIJ, CK, DL, EM, FN)",
        d2i=dict([(k, "CF") for k in range(8, 10)]),
        distinct="",
        verbose=0,    # use 256 to see the generated code
      )
      
      # print answers
      for (_, ans) in p.solve():
        print(f"the final height of the stack in centimetres: {ans[0]}")
      

      Like

  • Jim Randell 9:10 am on 28 July 2022 Permalink | Reply
    Tags:   

    Teaser 2726: Christmas star 

    From The Sunday Times, 21st December 2014 [link] [link]

    I asked Peter to place the numbers 1 to 10 at the ten intersection points of the Christmas star so that in each of the five lines the four numbers added to the same total. He found that this was impossible so instead he did it with the numbers 1 to 9 together with just one of those digits repeated. In his answer there was just one line in which that digit did not appear.

    [In ascending order] what were the four numbers in that line?

    [teaser2726]

     
    • Jim Randell 9:12 am on 28 July 2022 Permalink | Reply

      (See also: Enigma 1063).

      I assume were are talking about a layout like this:

      There are 5 lines, and each of the numbers appears on two of the lines.

      If we add the lines we will be counting each number twice, and the total will be 5 times the common sum, T.

      So, if X is the repeated digit we have:

      2 × (1 + 2 + … + 9 + X) = 5 × T
      T = 18 + (2/5)X

      Hence: X = 5, and T = 20.

      To remove duplicate solutions we can suppose the line that doesn’t include X is (B, C, D, E) and that B < E.

      The following run file executes in 98ms.

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      # suppose the line with no repeated digit is BCDE
      
      SubstitutedExpression
      
      --digits="1-9"
      --distinct="BCDE"
      
      # the 5 lines have the same sum (= 20)
      "A + C + F + I = 20"
      "A + D + G + J = 20"
      "B + C + D + E = 20"
      "B + F + H + J = 20"
      "E + G + H + I = 20"
      
      # all 9 digits are used
      "len({A, B, C, D, E, F, G, H, I, J}) = 9"
      
      # 5 is in all the lines except BCDE
      "5 not in {B, C, D, E}"
      "5 in {A, C, F, I}"
      "5 in {A, D, G, J}"
      "5 in {B, F, H, J}"
      "5 in {E, G, H, I}"
      
      # remove duplicate solutions
      "B < E"
      
      --answer="ordered(B, C, D, E)"
      --template=""
      

      Solution: The four numbers on the line without the repeated digit are: 1, 3, 7, 9.

      There are 12 essentially different layouts, here is one:

      Like

  • Jim Randell 9:17 am on 26 July 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 727: Right hand 

    From The Sunday Times, 22nd June 1975 [link]

    When South, who was bored with being dummy, had left the card room of the Logic Club for good, West extracted four kings, three queens and two jacks from the pack, showed them round, shuffled them, and dealt three cards to each of the three.

    “Forget the suits”, he said. “Let each of us look at his own three cards and see if he can make a sure statement about any kings, queens or jacks in the next man’s hand; we will use as evidence what we see in our own hands and what we hear each other say.

    They played with the full rigours of logic. West began by announcing that he could say nothing about North’s hand; North then said that he could say nothing about East’s hand; thereupon East said that he could deduce the value of one card — and one only — in West’s hand.

    What can you say about the cards that were dealt to East?

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 2 (1981, edited by Victor Bryant and Ronald Postill).

    [teaser727]

     
    • Jim Randell 9:18 am on 26 July 2022 Permalink | Reply

      There are 9 possible hands that could be dealt to W, and in each case W would be able to say something about the cards that are dealt to N:

      KKK → N holds at most 1K
      KKQ → N holds at most 2K, at most 2Q
      KKJ → N holds at most 2K, at most 1J
      KQQ → N holds at most 1Q
      KQJ → N holds at most 2Q, at most 1J
      KJJ → N holds no J
      QQQ → N holds at least 1K, no Q
      QQJ → N holds at least 1K, at most 1Q, at most 1J
      QJJ → N holds at least 1K, at most 2Q, no J

      So let’s use a tighter definition that each must declare if they know for certain cards that are held by the next player.

      This reduces the list to:

      QQQ → N holds at least 1K
      QQJ → N holds at least 1K
      QJJ → N holds at least 1K

      And this allows us to find an answer to the puzzle.

      This Python program runs in 58ms. (Internal runtime is 1.2ms).

      Run: [ @replit ]

      from collections import defaultdict
      from enigma import (multiset, join, printf)
      
      # format a hand
      fmt = lambda x: join(x).upper()
      
      # deal groups of <k> cards from <cards>
      def deal(cards, k, ss=[]):
        if not cards:
          yield ss
        else:
          # choose the first hand
          for hand in cards.subsets(size=3):
            yield from deal(cards.difference(hand), k, ss + [tuple(hand.sorted())])
      
      # initial cards
      cards = multiset(K=4, Q=3, j=2)
      values = sorted(cards.keys())
      
      # possible deals
      hands = list(deal(cards, 3))
      
      # look at W's hand, record the number of Ks, Qs, Js in N's
      w = defaultdict(lambda: defaultdict(set))
      for (W, N, E) in hands:
        for k in values:
          w[W][k].add(N.count(k))
      
      # W can't be sure of any cards held by N
      Ws = set(W for (W, d) in w.items() if all(0 in d[k] for k in values))
      printf("[W = {Ws}]", Ws=join(map(fmt, Ws), sep=", ", enc="{}"))
      
      # look at N's hand, record the number of Ks, Qs, Js in E's
      n = defaultdict(lambda: defaultdict(set))
      for (W, N, E) in hands:
        if W not in Ws: continue
        for k in values:
          n[N][k].add(E.count(k))
      
      # N can't be sure of any cards held by E
      Ns = set(N for (N, d) in n.items() if all(0 in d[k] for k in values))
      printf("[N = {Ns}]", Ns=join(map(fmt, Ws), sep=", ", enc="{}"))
      
      # look at E's hand, record the number of Ks, Qs, Js in W's
      e = defaultdict(lambda: defaultdict(set))
      for (W, N, E) in hands:
        if W not in Ws or N not in Ns: continue
        for k in values:
          e[E][k].add(W.count(k))
      
      # E can be sure of exactly 1 card held by W
      for (E, d) in e.items():
        if sorted(min(v) for v in d.values()) == [0, 0, 1]:
          printf("E = {E}", E=fmt(E))
      

      Solution: East held a King, a Queen, and a Jack.

      Like

      • John Crabtree 6:50 pm on 26 July 2022 Permalink | Reply

        In manually reaching the same solution, I concluded that West must hold at least one King, and that North must hold at least one King and one Queen. That gives three possible sets of hands.
        Do you agree? Thanks.

        Like

        • Jim Randell 8:20 am on 27 July 2022 Permalink | Reply

          @John: Yes, I found three possible sets of hands:

          W = KQJ; N = KKQ; E = KQJ
          W = KKJ; N = KQQ; E = KQJ
          W = KKQ; N = KQJ; E = KQJ

          Like

  • Jim Randell 2:04 pm on 24 July 2022 Permalink | Reply
    Tags: ,   

    Brain-Teaser 159: Fallen leaves 

    From The Sunday Times, 26th April 1964 [link]

    Three leaves fall from a book. The total of the page numbers remaining in the second half of the book is now three times the total of the page numbers remaining in the first half.

    The total of the page numbers on the fallen leaves lies between 1050 and 1070, and is the highest which could have produced this effect.

    How many numbered pages did the book contain originally?

    I found many solutions, which improve on the published answer. So I have marked the puzzle as flawed.

    This puzzle was included in the book Sunday Times Brain Teasers (1974, edited by Ronald Postill).

    [teaser159]

     
    • Jim Randell 2:06 pm on 24 July 2022 Permalink | Reply

      I think this puzzle is flawed, as I found many solutions that seem to satisfy the puzzle text, and are different from the published solution.

      If we suppose the book consists of n leaves (= 2n pages), and that the leaves are 1|2, 3|4, …, (2n − 1)|(2n).

      And the two halves of the book are pages 1 – n and (n + 1)(2n).

      Then the initial sum of page numbers in each half of the book are:

      first half = sum(1 .. n) = n(n + 1)/2
      second half = sum(n+1 .. 2n) = n(3n + 1)/2

      Now, if the three leaves removed are (2a − 1)|(2a), (2b − 1)|(2b), (2c − 1)|(2c).

      Then the total of the page numbers removed is t = 4(a + b + c) − 3, and this is in the range 1050 – 1070.

      So (a + b + c) is in the range 264 – 268, and we want this to take on the highest possible value (i.e. 268 if possible, which corresponds to t = 1069).

      If the sum of the removed pages in the first and second halves is t1, t2 (t1 + t2 = t), then we have:

      n(3n + 1)/2 − t2 = 3(n(n + 1)/2 − t1)
      n = 3.t1 − t2

      This Python program starts looking for values of t from 268 down to 264, and stops when it finds a value that gives viable books. It runs in 74ms. And it finds many possible solutions.

      Run: [ @replit ]

      from enigma import (irange, decompose, printf)
      
      # solve with leaves removed (even page numbers given)
      def solve(*vs):
        # calculate the removed page numbers
        (x, y, z) = (2 * v for v in vs)
        ps = (x - 1, x, y - 1, y, z - 1, z)
        # split the pages at index i
        for i in irange(2, 4):
          t1 = sum(ps[:i])
          t2 = sum(ps[i:])
          # calculate the number of leaves (so there are 2n pages)
          n = 3 * t1 - t2
          if n < 3 or ps[-1] > 2 * n: continue
          # and check the split occurs between the halves
          if i > 0:
            if ps[i - 1] > n: continue
          if i < 6:
            if not(ps[i] > n): continue
          yield (n, ps, t1, t2)
      
      # record solutions (number of pages = twice the number of leaves)
      ss = set()
      
      # t = a + b + c
      for t in irange(268, 264, step=-1):
        # calculate possible a, b, c values
        for (a, b, c) in decompose(t, 3):
          for (n, ps, t1, t2) in solve(a, b, c):
            printf("[t={t}: a={a} b={b} c={c} -> {ps}; t1={t1} t2={t2}; n={n}]")
            ss.add(2 * n)
        # are we done?
        if ss:
          printf("pages = {ss}", ss=sorted(ss))
          break
      

      Solution: The book could have: 310, 318, 342, 350, 374, 406, 438, 470, 502, 534, 566, 598, 630, 662, 694, 6414 pages.


      Here is one of the solutions found:

      If the book has 203 leaves = 406 pages, numbered 1|2, 3|4, …, 203|204, …, 405|406.

      Then the sum of the page numbers in the first half of the book is: sum(1..203) = 20706.

      And the sum of the page numbers in the second half of the book is: sum(204..406) = 61915.

      (Note that if leaf 203|204 is removed, that is one page from each half of the book).

      Now, if pages 1|2, 157|158, 375|376 are removed (total = 1069, the largest possible value).

      Then the pages removed from the first half are: 1, 2, 157, 158; sum = 318, so the sum of the remaining pages in the first half is 20706 − 318 = 20388.

      And the pages removed from the second half are: 375, 376; sum = 751, so the sum of the remaining pages in the second half is 61915 − 751 = 61164.

      And: 61164 = 3 × 20388, as required.


      The published solution (and that given in the 1974 book) is that the book initially had 302 pages (i.e. 151 leaves), and the removed pages are 75|76, 151|152, 301|302. Which gives a total of 1057.

      But I have shown above that this is not the largest total possible.

      It was also noted: “Only 4 correct answers in a very small entry”. So it seems I wasn’t the only one that had issues with this puzzle.

      The solution in the book only considers 3 ways that leaves can be removed: 1 from the first half + 2 from the second half; 2 from the first half + 1 from the second half; 1.5 from each half. In terms of pages these are 2+4, 3+3, 4+2, but my program also considers 0+6, 1+5, 5+1, 6+0. However the example I give is a 4+2 combination, which should be accounted for by the published solution. But it has arrived at the conclusion that the maximum viable total of the numbers on the removed pages for a book with x leaves is 7x, so 1057 is the maximum possible (with 151 leaves), but I think this is faulty reasoning.

      (The only thing I can think of is that the two halves of the book are considered after the leaves have been removed. (Although the solution given in the book doesn’t seem to support this). But even with this interpretation there are multiple solutions with a total of 1069 – any that removes 3 pages from the first half and three from the second half will leave the boundary unchanged).

      Like

  • Jim Randell 4:03 pm on 22 July 2022 Permalink | Reply
    Tags:   

    Teaser 3122: Bank robbery 

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

    Five witnesses were interviewed following a robbery at the bank in the High Street. Each was asked to give a description of the robber and his actions.

    The details given were: height; hair colour; eye colour; weapon carried; escape method.

    Witness 1: short; fair; brown; cricket bat; motorbike.

    Witness 2: tall; fair; grey; gun; car.

    Witness 3: tall; dark; brown; crowbar; motorbike.

    Witness 4: short; ginger; blue; knife; car.

    Witness 5: tall; dark; blue; stick; pushbike.

    When the police caught up with the perpetrator, they found that each of the five witnesses had been correct in exactly two of these characteristics.

    What was the robber carrying, and how did he get away?

    [teaser3122]

     
    • Jim Randell 4:15 pm on 22 July 2022 Permalink | Reply

      It is straightforward to try all possible combinations. (Assuming the robber has a unique single value for each characteristic).

      I include an “other” value for each characteristic to account for possibilities where none of the witnesses have correctly described it.

      This Python program runs in 58ms. (Internal runtime is 1.9ms).

      Run: [ @replit ]

      from enigma import (cproduct, join, printf)
      
      # descriptions
      descs = [
        dict(S='short', T='tall', X='other'),
        dict(F='fair', D='dark', G='ginger', X='other'),
        dict(R='brown', G='grey', L='blue', X='other'),
        dict(B='cricket bat', G='gun', C='crowbar', K='knife', S='stick', X='other'),
        dict(M='motorbike', C='car', P='pushbike', X='other'),
      ]
      
      # statements
      statements = [ 'SFRBM', 'TFGGC', 'TDRCM', 'SGLKC', 'TDLSP' ]
      
      # how many characteristics are correct?
      correct = lambda xs, ys: sum(x == y for (x, y) in zip(xs, ys))
      
      # consider characteristics of the perp
      for cs in cproduct(d.keys() for d in descs):
        # each witness gave 2 correct statements
        if all(correct(xs, cs) == 2 for xs in statements):
          # output solution
          printf("{cs}", cs=join((d[k] for (d, k) in zip(descs, cs)), sep=", "))
      

      Solution: The robber was carrying a knife. He made his escape by motorbike.

      In fact we can determine a complete description:

      height = tall
      hair = fair
      eyes = blue
      weapon = knife
      vehicle = motorbike

      Like

      • Jim Randell 8:48 am on 26 July 2022 Permalink | Reply

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

        The following run file executes in 72ms.

        Run: [ @replit ]

        #! python3 -m enigma -r
        
        # statements:
        #
        #  A = height is short; B = height is tall
        #  C = hair is fair; D = hair is dark; E = hair is ginger
        #  F = eyes are brown; G = eyes are grey; H = eyes are blue
        #  I = weapon is cricket bat; J = weapon is gun; K = weapon is crowbar; L = weapon is knife; M = weapon is stick
        #  N = vehicle is motorbike; P = vehicle is car; Q = vehicle is pushbike
        
        SubstitutedExpression
        
        --distinct=""
        --digits="0,1"
        
        # at most one of the statements in each category is true
        "not(A + B > 1)"
        "not(C + D + E > 1)"
        "not(F + G + H > 1)"
        "not(I + J + K + L + M > 1)"
        "not(N + P + Q > 1)"
        
        # witnesses each make exactly 2 true statements
        "A + C + F + I + N = 2"
        "B + C + G + J + P = 2"
        "B + D + F + K + N = 2"
        "A + E + H + L + P = 2"
        "B + D + H + M + Q = 2"
        
        --template=""
        

        This construction also leads to a simple manual solution:

        In the matrix of statements (lines 24 – 28), each row sums to 2. So the total sum of all matrix elements is 10.

        Looking at the columns of the matrix we get the following potential column totals:

        height: 0 (X), 2 (A), 3 (B)
        hair: 0 (X), 1 (E), 2 (C, D)
        eyes: 0 (X), 1 (G), 2 (F, H)
        weapon: 0 (X), 1 (I, J, K, L, M)
        vehicle: 0 (X), 1 (Q), 2 (N, P)

        A grand total of 10 can only be achieved by taking the maximum value for each column.

        So we can eliminate all the X’s and A, E, G, Q (all of which must = 0). Hence B = 1.

        One of C, D = 1 (and the other = 0). If D = 1, then witnesses 3 and 5 have achieved their 2 correct statements so: F, H, K, M, N = 0, but one of F, H = 1. So D = 0 and C = 1.

        We can then complete the assignment of values, and determine the true statements are: B, C, H, L, N.

        Like

    • GeoffR 5:51 pm on 23 July 2022 Permalink | Reply

      
      # List of possible witness statements
      statements = []
      
      # Witness statements
      W1 = ['short', 'fair', 'brown', 'cricket bat', 'motorbike']
      W2 = ['tall', 'fair', 'grey', 'gun', 'car' ]
      W3 = ['tall', 'dark', 'brown', 'crowbar', 'motorbike' ]
      W4 = ['short', 'ginger', 'blue', 'knife', 'car' ] 
      W5 = ['tall', 'dark', 'blue', 'stick', 'pushbike' ]
      
      # Form lists of all possible witness statements
      for a in ('short', 'tall'): 
        for b in ('fair', 'dark', 'ginger'):
          for c in ('brown', 'grey', 'blue'):
            for d in ('cricket bat', 'gun', 'crowbar', 'knife', 'stick'):
              for e in ('motorbike', 'car', 'pushbike'):
                statements.append([a, b, c, d, e])
      
      for st in statements:
          a, b, c, d, e = st
          # Two statements from five are true for each witness
          # test Witness No.1 statements
          if sum([a == 'short', b == 'fair', c == 'brown', \
                  d == 'cricket bat', e == 'motorbike']) == 2:
            
            #test Witness No.2 statements
            if sum([a == 'tall', b == 'fair', c == 'grey', \
                    d == 'gun', e == 'car']) == 2:
              
              # test Witness No.3 statements
              if sum([ a == 'tall', b == 'dark', c == 'brown', \
                       d == 'crowbar', e == 'motorbike']) == 2:
              
                # test Witness No.4 statements
                if sum([a == 'short', b == 'ginger', c == 'blue', \
                        d == 'knife', e == 'car']) == 2:
                  
                  # test Witness No.5 statements
                  if sum([ a == 'tall', b == 'dark', c == 'blue', \
                           d == 'stick', e == 'pushbike']) == 2:
                    print(f"The robber was {a}.")
                    print(f"He had {b} coloured hair and {c} colour eyes.")
                    print(f"He carried a {d} as a weapon, escaping on a {e}.")
                    
      
      
      

      Like

    • GeoffR 9:41 pm on 23 July 2022 Permalink | Reply

      Indexing the witness statement lists is neater:

      
      # List of possible witness statements
      statements = []
      
      # Witness statements
      W1 = ['short', 'fair', 'brown', 'cricket bat', 'motorbike']
      W2 = ['tall', 'fair', 'grey', 'gun', 'car' ]
      W3 = ['tall', 'dark', 'brown', 'crowbar', 'motorbike' ]
      W4 = ['short', 'ginger', 'blue', 'knife', 'car' ] 
      W5 = ['tall', 'dark', 'blue', 'stick', 'pushbike' ]
      
      # Form lists of all possible witness statements
      for a in ('short', 'tall'): 
        for b in ('fair', 'dark', 'ginger'):
          for c in ('brown', 'grey', 'blue'):
            for d in ('cricket bat', 'gun', 'crowbar', 'knife', 'stick'):
              for e in ('motorbike', 'car', 'pushbike'):
                statements.append([a, b, c, d, e])
      
      for st in statements:
          a, b, c, d, e = st
          # Two statements from five are true for each witness
          # test Witness No.1 statements
          if sum([a == W1[0], b == W1[1], c == W1[2], \
                  d == W1[3], e == W1[4]]) == 2:
            
            # test Witness No.2 statements
            if sum([a == W2[0], b == W2[1], c == W2[2], \
                    d == W2[3], e == W2[4]]) == 2:
              
              # test Witness No.3 statements
              if sum([ a == W3[0], b == W3[1], c == W3[2], \
                       d == W3[3], e == W3[4]]) == 2:
              
                # test Witness No.4 statements
                if sum([a == W4[0], b == W4[1], c == W4[2], \
                        d == W4[3], e == W4[4]]) == 2:
                  
                  # test Witness No.5 statements
                  if sum([ a == W5[0], b == W5[1], c == W5[2], \
                           d == W5[3], e == W5[4]]) == 2:
                    print(f"The robber was {a}.")
                    print(f"He had {b} coloured hair and {c} colour eyes.")
                    print(f"He carried a {d} as a weapon, escaping on a {e}.")
                    
      
      
      
      

      Like

    • GeoffR 12:07 pm on 1 August 2022 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      set of int: TF = {1,0};
      
      var TF:short; var TF:tall;
      var TF:h_fair; var TF:h_dark; var TF:h_ginger;
      var TF:e_brown; var TF:e_grey; var TF:e_blue;
      var TF:c_bat; var TF:gun; var TF:c_bar; var TF:knife; var TF:stick;
      var TF:mbike; var TF:car; var TF:pbike;
      
      % Values are 0 or 1 for main variables 
      % ..i.e. for height, hair colour, eye colour, weapon, vehicle
      constraint sum([short, tall]) < 2;
      constraint sum([h_fair, h_dark, h_ginger]) < 2;
      constraint sum([e_brown, e_grey, e_blue]) < 2;
      constraint sum([c_bat, gun, c_bar, knife, stick]) < 2;
      constraint sum([mbike, car, pbike]) < 2;
      
      % 5 witness statements - 2 are true for each witness
      constraint sum([short, h_fair, e_brown,c_bat, mbike]) == 2;
      constraint sum([tall, h_fair, e_grey, gun, car]) == 2;
      constraint sum([tall, h_dark, e_brown, c_bar, mbike]) == 2;
      constraint sum([short, h_ginger, e_blue, knife, car]) == 2;
      constraint sum([tall, h_dark, e_blue, stick, pbike]) ==  2;
      
      solve satisfy;
      
      output [" [short, tall ] = " ++ show([ short, tall ]) ++ "\n"
      ++ " [h_fair, h_dark, h_ginger] = " ++ show([ h_fair, h_dark, h_ginger])  
      ++ "\n" ++ " [e_brown, e_grey, e_blue] = " ++ show([e_brown, e_grey, e_blue] )
      ++ "\n" ++ " [c_bat, gun, c_bar, knife, stick] = " 
      ++ show([c_bat, gun, c_bar, knife, stick]) 
      ++ "\n" ++ " [mbike, car, pbike] = "  ++ show([mbike, car, pbike]) ];
      
      %  [short, tall ] = [0, 1]
      %  [h_fair, h_dark, h_ginger] = [1, 0, 0]
      %  [e_brown, e_grey, e_blue] = [0, 0, 1]
      %  [c_bat, gun, c_bar, knife, stick] = [0, 0, 0, 1, 0]
      %  [mbike, car, pbike] = [1, 0, 0]
      % ----------
      % ==========
      % i.e. Robber was tall, had fair hair, blue eyes, with a knife, escaping on a motorbike.
      
      
      
      

      Like

  • Jim Randell 9:07 am on 21 July 2022 Permalink | Reply
    Tags:   

    Teaser 2533: A lopsided number 

    From The Sunday Times, 10th April 2011 [link] [link]

    In this letters-for-digits substitution puzzle, each letter consistently represents a different digit. In the display, each letter in the top row is the sum of the two letters directly below it:

    What number is LOPSIDED?

    [teaser2533]

     
    • Jim Randell 9:08 am on 21 July 2022 Permalink | Reply

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

      The following run file executes in 64ms. The internal runtime of the generated program is 55µs).

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      SubstitutedExpression
      
      "F + I = P"
      "I + D = O"
      "D + D = S"
      "D + L = E"
      "L + E = R"
      
      --answer="LOPSIDED"
      

      Solution: LOPSIDED = 24961353.

      And: POSER = 94657; FIDDLE = 813325.

      Like

    • GeoffR 11:38 am on 21 July 2022 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
       
      var 1..9:P; var 1..9:O; var 1..9:S; var 1..9:E; var 1..9:R;
      var 1..9:F; var 1..9:I; var 1..9:D; var 1..9:L; 
      
      constraint all_different([P, O, S, E, R, F, I, D, L]);
      
      constraint F + I == P /\ I + D == O /\ D + D == S
      /\ D + L == E /\ L + E == R;
      
      solve satisfy;
      
      output ["LOPSIDED = \(L)\(O)\(P)\(S)\(I)\(D)\(E)\(D)"];
      
      % LOPSIDED = 24961353
      % ----------
      % ==========
      
      
      

      Like

  • Jim Randell 6:31 am on 19 July 2022 Permalink | Reply
    Tags:   

    Teaser 2721: Milliner’s hat-trick 

    From The Sunday Times, 16th November 2014 [link] [link]

    A football tournament has four groups each of four teams, with the teams in the same group playing each other once. So far the teams have each played two games and in each group the distribution of points is different. Also, in each group just one pair of teams are level on points and their positions have been determined by their “goals scored”. Milliner has scored four (including a hat-trick), Orlando two, and nine other players have scored one goal each. Despite his success, Orlando’s team is not the top of their group.

    What are the results of the two games that Milliner’s team have played? And the two games that Orlando’s team have played?

    [teaser2721]

     
    • Jim Randell 6:33 am on 19 July 2022 Permalink | Reply

      The puzzle is not explicit on the scoring system used (i.e. 2 points for a win, or 3 points for a win), although it turns out it doesn’t matter which is used, the answer to the puzzle is the same in both cases.

      In each group each team has played 2 of their 3 matches. So there have been 4 matches played (and there are 2 matches left to play). So among the 4 groups there have been 16 matches played in total.

      The minimum possible number of goals scored among the 4 matches in a group is 2. So the maximum possible number of goals scored is 15 − 3×2 = 9. (Although it may be possible to reduce this theoretical maximum value, which would speed up the program).

      For each group, this Python program considers the scores for teams A (1st), B (2nd), C (3rd), D (4th), such that each team has played 2 matches, and two of the teams are tied on points, but have different “goals for” values.

      It then chooses 4 different points distributions (one for each of the groups), and from the previously examined scores it chooses 4 sets of scores that have 15 goals scored in total, and ensures there are possible teams for both Milliner and Orlando.

      The program runs in 361ms.

      Run: [ @replit ]

      from collections import defaultdict
      from enigma import (
        Football, irange, subsets, tuples, cproduct, peek, delete,
        update, find, unzip, reverse, map2str, join, printf
      )
      
      # scoring regime (2 or 3 points for a win)
      football = Football(games='wdlx', points=dict(w=2, d=1))
      
      # labels for the teams
      teams = (A, B, C, D) = tuple("ABCD")
      
      # keys for the matches
      ks = list(x + y for (x, y) in subsets(teams, size=2))
      
      # allocate <t> goals among the matches <ms>, return scores <ss>
      def allocate(t, ms, ss=dict()):
        # are we done?
        if not ms:
          if t == 0:
            yield ss
        else:
          # calculate the number of surplus goals
          n = t - sum(v == 'w' for v in ms.values())
          if n < 0: return
          # choose the next match to allocate goals to
          (k, v) = peek(ms.items())
          if v == 'x':
            # not played
            yield from allocate(t, delete(ms, [k]), update(ss, [(k, None)]))
          elif v == 'w' or v == 'l':
            # a win (or loss), calculate scores (x, y)
            for x in irange(1, n + 1):
              for y in irange(0, min(x - 1, n - x + 1)):
                s = ((x, y) if v == 'w' else (y, x))
                yield from allocate(t - x - y, delete(ms, [k]), update(ss, [(k, s)]))
          elif v == 'd':
            # a draw, calculate scores (x, x)
            for x in irange(0, n // 2):
              yield from allocate(t - x - x, delete(ms, [k]), update(ss, [(k, (x, x))]))
      
      # check goals scored by team <t> in a match from scores <ss> is <n> or more
      def scored(t, ss, n):
        for (k, v) in ss.items():
          if v is not None:
            i = find(k, t)
            if i != -1 and v[i] >= n:
              return True
      
      # map: <pts> -> <total goals> -> (<match scores>, <milliner>, <orlando>) values
      d = defaultdict(lambda: defaultdict(list))
      
      # consider possible match outcomes
      for ms in football.games(repeat=len(ks)):
        ms = dict(zip(ks, ms))
        # compute the table for each team
        table = dict((t, football.extract_table(ms, t)) for t in teams)
        # each team has played twice
        if not all(table[t].played == 2 for t in teams): continue
        # points are increasing, with exactly 2 teams having the same points
        pts = tuple(table[t].points for t in teams)
        if len(set(pts)) != 3: continue
        if not all(x >= y for (x, y) in tuples(pts, 2)): continue
        # allocate goals to the matches
        for t in irange(2, 9):
          for ss in allocate(t, ms):
            # extract the goals (for, against) for each team
            goals = dict((t, football.extract_goals(ss, t)) for t in teams)
            # check teams with same points have different "goals for" values
            if any(p1 == p2 and not(goals[t1][0] > goals[t2][0])
              for ((t1, p1), (t2, p2)) in tuples(zip(teams, pts), 2)
            ): continue
            # find teams for Milliner: team must have a match with >= 3 goals scored
            # and have >= 4 goals scored in total
            tM = list(t for (t, (f, _)) in goals.items() if f > 3 and scored(t, ss, 3))
            # find teams for Orlando: must have >= 2 goals, and not be top
            tO = list(t for (t, (f, _)) in goals.items() if t != 'A' and f > 1)
            # record this set of scores
            d[pts][t].append((ss, tM, tO))
      
      # collect scores from <ss> for teams in <ts> (from the team's perspective)
      def collect(ss, ts):
        for t in ts:
          rs = list()
          for (s, f) in unzip(football.extract(ss, t)):
            if s is None: continue
            rs.append(reverse(s) if f else s)
          yield tuple(sorted(rs, reverse=1))
      
      # choose 4 different points distributions
      for ps in subsets(d.keys(), size=4):
        # choose the number of goals scored in each group
        for ts in cproduct(d[p].keys() for p in ps):
          # there should be 15 goals in total
          if sum(ts) != 15: continue
          # choose the actual scores in each match
          for ss in cproduct(d[p][t] for (p, t) in zip(ps, ts)):
            # check for possibilities for Milliner and Orlando
            if not any(tM for (_, tM, _) in ss): continue
            if not any(tO for (_, _, tO) in ss): continue
            # output a solution (groups = scores, pts, M, O; M's team; O's team)
            (Ms, Os) = (set(), set())
            for (i, ((s, tM, tO), p)) in enumerate(zip(ss, ps), start=1):
              printf("Group {i}: {s} {p} {tM} {tO}", s=map2str(s, enc=""), tM=join(tM, enc="[]"), tO=join(tO, enc="[]"))
              Ms.update(collect(s, tM))
              Os.update(collect(s, tO))
            for M in sorted(Ms): printf("M's team: {M}", M=join(M, sep=", "))
            for O in sorted(Os): printf("O's team: {O}", O=join(O, sep=", "))
            printf()
      

      Solution: The results for Milliner’s team are: a 3-1 win, a 1-0 win. The results for Orlando’s team are: a 2-0 win, a 0-1 loss.

      M’s team is a group leader. O’s team is second in their group.

      With “2 points for a win” (and 1 for a draw) there are three possible sets of scores:

      Group 1: A v B = 1-0; A v C = 1-0; B v D = 2-0; C v D = 1-0; points = [4, 2, 2, 0], Orlando is team B
      Group 2: A v C = 3-1; A v D = 1-0; B v C = 0-0; B v D = 0-0; points = [4, 2, 1, 1], Milliner is team A
      Group 3: A v B = 1-0; A v C = 0-0; B v D = 1-0; C v D = 0-0; points = [3, 2, 2, 1]
      Group 4: A v C = 0-0; A v D = 2-0; B v C = 0-0; B v D = 1-0; points = [3, 3, 2, 0]

      Group 1: A v B = 1-0; A v D = 1-0; B v C = 2-0; C v D = 1-0; points = [4, 2, 2, 0], Orlando is team B
      Group 2: A v C = 3-1; A v D = 1-0; B v C = 0-0; B v D = 0-0; points = [4, 2, 1, 1], Milliner is team A
      Group 3: A v B = 1-0; A v C = 0-0; B v D = 1-0; C v D = 0-0; points = [3, 2, 2, 1]
      Group 4: A v C = 0-0; A v D = 2-0; B v C = 0-0; B v D = 1-0; points = [3, 3, 2, 0]

      Group 1: A v C = 1-0; A v D = 1-0; B v C = 0-1; B v D = 2-0; points = [4, 2, 2, 0], Orlando is team B
      Group 2: A v C = 3-1; A v D = 1-0; B v C = 0-0; B v D = 0-0; points = [4, 2, 1, 1], Milliner is team A
      Group 3: A v B = 1-0; A v C = 0-0; B v D = 1-0; C v D = 0-0; points = [3, 2, 2, 1]
      Group 4: A v C = 0-0; A v D = 2-0; B v C = 0-0; B v D = 1-0; points = [3, 3, 2, 0]

      We can examine what happens with “3 points for a win” by changing the initialisation at line 8. And we find in this case there are four possible sets of scores:

      Group 1: A v B = 1-0; A v D = 0-0; B v C = 2-0; C v D = 1-0; points = [4, 3, 3, 1], Orlando is team B
      Group 2: A v B = 1-1; A v D = 1-0; B v C = 0-0; C v D = 0-0; points = [4, 2, 2, 1]
      Group 3: A v C = 3-1; A v D = 1-0; B v C = 0-0; B v D = 0-0; points = [6, 2, 1, 1], Milliner is team A
      Group 4: A v C = 0-0; A v D = 2-0; B v C = 0-0; B v D = 1-0; points = [4, 4, 2, 0]

      Group 1: A v B = 1-0; A v D = 0-0; B v C = 2-0; C v D = 1-0; points = [4, 3, 3, 1], Orlando is team B
      Group 2: A v C = 0-0; A v D = 1-0; B v C = 0-0; B v D = 1-1; points = [4, 2, 2, 1]
      Group 3: A v C = 3-1; A v D = 1-0; B v C = 0-0; B v D = 0-0; points = [6, 2, 1, 1], Milliner is team A
      Group 4: A v C = 0-0; A v D = 2-0; B v C = 0-0; B v D = 1-0; points = [4, 4, 2, 0]

      Group 1: A v C = 1-0; A v D = 0-0; B v C = 0-1; B v D = 2-0; points = [4, 3, 3, 1], Orlando is team B
      Group 2: A v B = 1-1; A v D = 1-0; B v C = 0-0; C v D = 0-0; points = [4, 2, 2, 1]
      Group 3: A v C = 3-1; A v D = 1-0; B v C = 0-0; B v D = 0-0; points = [6, 2, 1, 1], Milliner is team A
      Group 4: A v C = 0-0; A v D = 2-0; B v C = 0-0; B v D = 1-0; points = [4, 4, 2, 0]

      Group 1: A v C = 1-0; A v D = 0-0; B v C = 0-1; B v D = 2-0; points = [4, 3, 3, 1], Orlando is team B
      Group 2: A v C = 0-0; A v D = 1-0; B v C = 0-0; B v D = 1-1; points = [4, 2, 2, 1]
      Group 3: A v C = 3-1; A v D = 1-0; B v C = 0-0; B v D = 0-0; points = [6, 2, 1, 1], Milliner is team A
      Group 4: A v C = 0-0; A v D = 2-0; B v C = 0-0; B v D = 1-0; points = [4, 4, 2, 0]

      Like

  • Jim Randell 12:33 pm on 17 July 2022 Permalink | Reply
    Tags:   

    Teaser 2531 

    From The Sunday Times, 27th March 2011 [link] [link]

    A Harshad number (or H-number) is any number that is divisible by the sum of its digits. Using each non-zero digit just the once, I have written down a 9-figure H-number. Reading from left to right, it also consists of three 2-figure H-numbers followed by a 3-figure H-number. Again working from left to right through the 9-figure number, the last five digits form a 5-figure H-number. Reversing the order of the first five digits of the 9-figure number also gives a 5-figure H-number.

    What is the 9-figure number?

    [teaser2531]

     
    • Jim Randell 12:34 pm on 17 July 2022 Permalink | Reply

      See: [@wikipedia].

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

      The following run file executes in 72ms. The internal runtime of the generated program is 3.1ms).

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      SubstitutedExpression
      
      --digits="1-9"
      
      # is <n> an H-number?
      --code="H = lambda n: n % dsum(n) == 0"
      
      # the 9-digit number is: abcdefghi
      "H({abcdefghi})"
      
      # three 2-digit H-numbers and a 3-digit H-number
      "H({ab})"
      "H({cd})"
      "H({ef})"
      "H({ghi})"
      
      # 5-digit H-numbers
      "H({efghi})"
      "H({edcba})"
      
      --answer="{abcdefghi}"
      

      Solution: The 9-digit number is: 273684915.

      Like

    • GeoffR 2:16 pm on 17 July 2022 Permalink | Reply

      
      % A Solution in MiniZinc 
      include "globals.mzn";
      
      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]);
      
      % 2-digit Harshad numbers
      constraint (10*a + b) mod (a + b) == 0
      /\ (10*c + d) mod (c + d) == 0
      /\ (10*e + f) mod (e + f) == 0;
      
      % 3-digit Harshad number
      constraint (100*g + 10*h + i) mod (g + h + i) == 0;
      
      % 5-digit Harshad numbers
      constraint (10000*e + 1000*f + 100*g + 10*h + i) mod(e + f + g + h + i) == 0;
      constraint (10000*e + 1000*d + 100*c + 10*b + a) mod(e + d + c + b + a) == 0;
      
      % 9-digit Harshad number
      constraint (a * pow(10,8) + b * pow(10,7) + c * pow(10,6)
      + d * pow(10,5) + e * pow(10,4) + f * pow(10,3)
      + g * pow(10,2) + h * 10 + i) mod (a+b+c+d+e+f+g+h+i) == 0;
      
      solve satisfy;
      
      output ["9-figure number = " ++ " \(a)\(b)\(c)\(d)\(e)\(f)\(g)\(h)\(i)" ];
      
      % 9-figure number = 273684915
      % ----------
      % ==========
      
      

      Like

    • Frits 3:40 pm on 17 July 2022 Permalink | Reply

         
      from itertools import permutations
      from functools import reduce
      
      # convert digits sequence to number
      d2n = lambda s: reduce(lambda x, y: 10 * x + y, s)
      
      # calculate H-number
      H = lambda s: d2n(s) % sum(s) == 0
      
      i = 5  # as abcdefghi is divisible by 45
      
      # ghi:   sum(g,h) must be even as sum(g,h,i) must be odd
      # efghi: sum(e,f) must be even as sum(e,f,g,h,i) must be odd
      # ef:    e and f not both odd otherwise 10*d + e is not divisible by e + f
      #        so e and f are both even
      # ab:    a and b not both odd
      # cd:    c and d not both odd
      # g an h must be both odd otherwise a, b, c and d must all be odd
      
      # ....eeoo5
      # edcba : a must be even as sum(e,d,c,b,a) is even
      # e...eeoo5
      # as c and d are not both odd b must be odd
      # eo..eeoo5
      
      for (b, g, h) in permutations([1, 3, 7, 9], 3):
        if not H((g, h, i)): continue
        for (a, e, f) in permutations([2, 4, 6, 8], 3):
          if not H((a, b)): continue
          if not H((e, f)): continue
          if not H((e, f, g, h, i)): continue
          rest = set(range(1, 10)).difference({a, b, e, f, g, h, i})
          for (c, d) in permutations(rest):
            if not H((c, d)): continue
            if not H((e, d, c, b, a)): continue
            if not H((a, b, c, d, e, f, g, h, i)): continue
            print("the 9-figure number:", d2n((a, b, c, d, e, f, g, h, i)))
      

      Like

    • GeoffR 6:43 pm on 17 July 2022 Permalink | Reply

      I carried out some further analysis to see how the number of Harshad numbers reduced with different arrangements of numbers.

      1) For numbers ab, cd, ef, ghi and abcdefghi, this gave 96 possible 9-digit Harshad numbers.

      2) Adding abcde to (1) above, I found 16 possible Harshad numbers for abcdefghi:

       a b c d e f g h i    a b c d e f g h i    a b c d e f g h i
      ------------------------------------------------------------
       2 7 3 6 4 8 1 9 5,   2 7 3 6 8 4 9 1 5,   2 7 6 3 4 8 1 9 5,   
       2 7 6 3 8 4 9 1 5,   3 6 2 7 4 8 1 9 5,   3 6 2 7 8 4 9 1 5,   
       3 6 7 2 4 8 1 9 5,   3 6 7 2 8 4 9 1 5,   6 3 2 7 4 8 1 9 5,   
       6 3 2 7 8 4 9 1 5,   6 3 7 2 4 8 1 9 5,   6 3 7 2 8 4 9 1 5,   
       7 2 3 6 4 8 1 9 5,   7 2 3 6 8 4 9 1 5,   7 2 6 3 4 8 1 9 5,   
       7 2 6 3 8 4 9 1 5.
      

      3) Finally, adding number edcba to (2) above, this gave the single 9-digit answer of 273684915.
      (top row, middle value)

      Interesting to note how the 16 solutions illustrate aspects of analysis in Frits code.

      Like

  • Jim Randell 4:03 pm on 15 July 2022 Permalink | Reply
    Tags:   

    Teaser 3121: Top marks 

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

    A teacher is preparing her end of term class test. After the test she will arrive at each pupil’s score by giving a fixed number of marks for each correct answer, no marks for a question that is not attempted, and deducting a mark for each incorrect answer. The computer program she uses to prepare parents’ reports can only accept tests with the number of possible test scores (including negative scores) equal to 100.

    She has worked out all possible combinations of the number of questions asked and marks awarded for a correct answer that satisfy this requirement, and has chosen the one that allows the highest possible score for a pupil.

    What is that highest possible score?

    [teaser3121]

     
    • Jim Randell 4:25 pm on 15 July 2022 Permalink | Reply

      If there are n questions asked, and there are a marks for a correct answer, then the possible scores are:

      score = ax − z; where x + z ≤ n

      And we need there to be exactly 100 possible scores.

      There are tri(n + 1) different (correct, unanswered, incorrect) ways the n questions can be answered.

      So we need n ≥ 13 in order for there to be 100 or more different combinations (some may have the same score).

      Here’s a quick program to solve the puzzle.

      It runs in 66ms.

      Run: [ @replit ]

      from enigma import (irange, inf, Accumulator, printf)
      
      # find the highest possible score (all answers correct)
      r = Accumulator(fn=max, collect=1)
      
      # consider possible marks for a correct answer
      for a in irange(1, 10):
        # consider possible numbers of questions
        for n in irange(13, inf):
          # calculate possible scores
          ss = set(a * x - z for x in irange(0, n) for z in irange(0, n - x))
          k = len(ss)
          if k > 100: break
          if k == 100:
            m = max(ss) # = a * n
            r.accumulate_data(m, (a, n))
            printf("[a={a} n={n} m={m}]")
      
      # output solutions
      printf("max score = {m}")
      for (a, n) in r.data:
        printf("-> {n} questions; {a} marks for a correct answer")
      

      Solution: The maximum possible score is 105.

      There are 15 questions, and 7 marks for each correct answer. The maximum is therefore 15×7 = 105.

      It is also possible to have 100 potential scores with 21 questions, and 4 marks for each correct answer. In this case the maximum is 21×4 = 84.

      Like

    • Frits 7:28 pm on 15 July 2022 Permalink | Reply

         
      m = 0 
      # consider possible marks for a correct answer
      for a in range(1, 11):
        # range [-n, -n+1, ..., -1, 0, 1, ..., a*n]
        # max scores            = (a + 1) * n + 1    
        # nr impossible to make = a * (a - 1) / 2
      
        # n.a + n + 1 - 1/2 a.a + 1/2 a = 100
        # (2a + 2)n = a.a - a + 198
        n, r = divmod(a * a - a + 198, 2 * a + 2)
        if r: continue
        
        m = max(m, a * n)
      
      print("answer:", m)  
      

      Like

      • Jim Randell 8:59 am on 16 July 2022 Permalink | Reply

        I wondered how you arrived at your formula for the unreachable marks.

        I came up with this:

        If we get all the questions right the (maximum possible) score is: a.n

        If we get all but one of the questions right (and don’t attempt the remaining question) the next lowest score is: a(n − 1).

        So there are (a − 1) unreachable scores between these.

        If, however, we get the remaining question wrong, we get a score of: a(n − 1) − 1.

        The there are only (a − 2) unreachable scores in the next gap.

        If we get all but two of the questions right the possible scores are: a(n − 2), a(n − 2) − 1, a(n − 2) − 2.

        And there are (a − 3) unreachable scores in the following gap.

        So, in each gap the number of unreachable scores decreases by 1.

        Hence the total number of unreachable scores is: tri(a − 1), providing na. (All possible negative scores are reachable).

        And using this we can determine the number of possible scores without having to construct them.

        And we can proceed manually (there are only 10 values to check), or programatically:

        Run: [ @replit ]

        from enigma import (irange, inf, tri, Accumulator, printf)
        
        # find the highest possible score (all answers correct)
        r = Accumulator(fn=max, collect=1)
        
        # consider possible marks for a correct answer
        for a in irange(1, inf):
          # "unreachable" scores
          u = tri(a - 1)
          # find number of questions (100 = m + n + 1 - u)
          (n, q) = divmod(99 + u, a + 1)
          if n < 13: break
          if q != 0: continue
          assert n >= a
          # max possible score
          m = a * n
          r.accumulate_data(m, (a, n))
          printf("[a={a} n={n} m={m}]")
        
        # output solutions
        printf("max score = {m}")
        for (a, n) in r.data:
          printf("-> {n} questions; {a} marks for a correct answer")
        

        Manually, we can consider increasing a values, calculate u values (by just adding the preceding a value), and compute n = (99 + u) / (a + 1). We need n to be an integer ≥ 13. The calculations proceed as follows:

        a = 1; u = 0; n = 99/2 = 49r1
        a = 2; u = 1; n = 100/3 = 33r1
        a = 3; u = 3; n = 102/4 = 25r2
        a = 4; u = 6; n = 105/5 = 21 [candidate solution]
        a = 5; u = 10; n = 109/6 = 18r1
        a = 6; u = 16; n = 115/7 = 16r2
        a = 7; u = 21; n = 120/8 = 15 [candidate solution]
        a = 8; u = 28; n = 127/9 = 14r1
        a = 9; u = 36; n = 135/10 = 13r5
        a = 10; u = 45; n = 144/11 = 13r1
        a = 11; u = 55; n = 154/12 = 12r10 [n < 13]

        There are two candidate solutions a=4, n=21 ⇒ max=84 and a=7, n=15 ⇒ max=105, so we want the second one.

        Liked by 1 person

        • Frits 12:48 pm on 16 July 2022 Permalink | Reply

          I printed and analyzed the sorted ss lists of your program and noticed that
          the first unreachable number always is F = (n – (a – 2)) * a – (a – 1).
          This happens if the number of correct answers is equal to n – (a – 2).

          the next two unreachable numbers always are:
          (F + a, F + a + 1)
          the next three unreachable numbers always are:
          (F + 2*a, F + 2*a + 1, F + 2*a + 2)
          etc…

          Like

      • Frits 12:27 am on 17 July 2022 Permalink | Reply

        If a >= n then the number of possible test scores is independent of a.
        The number of unreachable scores is then tri(a – 1) – tri(a – n – 1).

        The number of possible test scores is equal to (n + 1) * (n + 2) / 2.
        The number of possible test scores equal to 100 leads to the formula
        (n + 1) * (n + 2) = 200

        A positive solution for n is (3 * sqrt(89) – 3) / 2 = 12.65 so
        not an integer solution.

        Like

    • Frits 6:09 pm on 21 July 2022 Permalink | Reply

      Formula (2a + 2).n = a.a – a + 198 is valid if marks for a correct answer (a) is not higher than the number of questions (n). If a is higher or equal to n then n must be a non-integer solution (approx 12.65).

      Another option would have been to use divisor_pairs().

         
      #! python3 -m enigma -r
      
      # rearrangement idea from John Crabtree:
      
      # formula (2a + 2).n = a.a - a + 198
      # can be rearranged to 2.n + 3 = 200 / (a + 1) + (a + 1) 
      # so both terms of RHS are divisors of 200
       
      SubstitutedExpression
      
      # find divisors of 200
      "div(200, AB) = DEF"
      "1 < AB <= DEF"
      
      # make sure exactly one of them is odd
      "(AB + DEF) % 2"
      
      # marks for a correct answer: AB - 1
      # number of question: (AB + DEF - 3) / 2
      --answer="(AB - 1) * (AB + DEF - 3) // 2"
      --distinct=""
      --accumulate=max
      --invalid="2-9,A"
      --verbose=16
      

      Like

      • Jim Randell 3:04 pm on 22 July 2022 Permalink | Reply

        I also did a solution based on John Crabtree’s analysis:

        from enigma import (Accumulator, divisors_pairs, div, printf)
        
        # based on John Crabtree's derivation: 2n + 3 = 200/(a + 1) + (a + 1)
        
        # find the highest possible score (all answers correct)
        r = Accumulator(fn=max, collect=1)
        
        # look for divisors of 200
        for (p, q) in divisors_pairs(200, every=1):
          a = p - 1
          if a < 1: continue
          # calculate n
          n = div(p + q - 3, 2)
          if n is None or n < a: continue
          m = a * n
          r.accumulate_data(m, (a, n))
          printf("[a={a}: n={n} m={m}]")
        
        # output solutions
        printf("max score = {m}")
        for (a, n) in r.data:
          printf("-> {n} questions; {a} marks for a correct answer")
        

        It is neat because we sum the divisor pairs.

        But it is more straightforward (and slightly faster) just to consider increasing a values (as in my second program).

        Like

  • Jim Randell 9:01 am on 14 July 2022 Permalink | Reply
    Tags:   

    Teaser 2532: In hot pursuit 

    From The Sunday Times, 3rd April 2011 [link] [link]

    George and Martha are jogging around a circular track. Martha starts at the most westerly point, George starts at the most southerly point, and they both jog clockwise at their own steady speeds. After a short while Martha is due north of George for the first time. Five minutes later she is due south of him for the first time. Then George catches up with her during their second laps at the most northeasterly point of the track.

    What is Martha’s speed (in degrees turned per minute)?

    [teaser2532]

     
    • Jim Randell 9:02 am on 14 July 2022 Permalink | Reply

      If George starts at 0° and goes at g degrees per minute, and Martha starts at 90° and goes at m degrees per minute.

      Then at time x (shortly after they set off) M is due north of G. So the angle G has gone is the same angular distance that M has to go to reach the north (180°) marker.

      So we have:

      xg = 90° − xm
      x(g + m) = 90°

      And 5 minutes later M is due south of G for the first time. The distance G has gone beyond the north (180°) marker is the same as the distance that M has to go to reach the south (360°/0°) marker.

      (x + 5)g − 180° = 270° − (x + 5)m
      (x + 5)(g + m) = 450°

      5x = x + 5
      4x = 5
      x = 5/4
      g + m = 72°/min

      Later, at some time t during lap 2, G catches up with M at the north-east (225°) marker. So G has gone 585° and M has gone 495°.

      Hence:

      585 = tg
      495 = tm

      t(g + m) = 1080
      t = 1080 / 72 = 15 min
      g = 39°/min
      m = 33°/min

      Solution: Martha’s speed is 33°/min.

      Like

  • Jim Randell 7:29 am on 12 July 2022 Permalink | Reply
    Tags:   

    Teaser 2724: Headcount 

    From The Sunday Times, 7th December 2014 [link] [link]

    My grandson and I play a coin game. First we toss seven coins and I have to predict in advance the number of heads whilst he has to predict the number of tails. I then get a number of points equal to the number of heads, he gets a number of points equal to the number of tails, and anyone whose prediction was correct gets a fixed bonus number of points (less than 40). We repeat this with six coins in the second round, then five, and so on down to two. In a recent game we noticed that, after each round, the total of all the points so far awarded was equal to a prime number.

    What is the “fixed bonus” number of points? And what was the total of all the points at the end of the game?

    [teaser2724]

     
    • Jim Randell 7:30 am on 12 July 2022 Permalink | Reply

      (See also: Teaser 3009).

      In a round with n coins the points awarded are, the number of heads (+ bonus if guessed correctly) and the number of tails (+ bonus if guessed correctly). So n points are always awarded, along with 0, 1, or 2 bonuses.

      We don’t need to worry about the points won by each player, just the total number of points gained in each round.

      This Python program keeps a set of (total, bonus) pairs, and then progresses through the rounds keeping viable values.

      It runs in 57ms. (Internal runtime is 664µs).

      Run: [ @replit ]

      from enigma import (irange, is_prime, printf)
      
      # start with a total of 0, and all possible bonus values
      ss = set((0, x) for x in irange(0, 40))
      
      # start with <k> coins
      k = 7
      
      # consider subsequent rounds
      while k > 1:
        ss_ = set()
        # consider (total, bonus) in the previous round
        for (t, b) in ss:
          # consider number of bonuses awarded in this round
          for n in (0, 1, 2):
            t_ = t + k + n * b
            if is_prime(t_):
              ss_.add((t_, b))
        # move on to the next round
        (ss, k) = (ss_, k - 1)
      
      # output solutions
      for (t, b) in ss:
        printf("total = {t}, bonus={b}")
      

      Solution: The number of bonus points is 19. The total number of points at the end of the game is 103.

      The progression of the game is:

      7 coins: total = 7 (0 bonus points)
      6 coins: total = 13 (0 bonus points)
      5 coins: total = 37 (19 bonus points)
      4 coins: total = 79 (38 bonus points)
      3 coins: total = 101 (19 bonus points)
      2 coins: total = 103 (0 bonus points)

      Like

  • Jim Randell 8:02 am on 10 July 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 150: Paving the way 

    From The Sunday Times, 23rd February 1964 [link]

    I have eight paving stones whose dimensions are an exact number of inches. Their areas are 504, 420, 324, 306, 270, 130, 117 and 112 square inches. Four of these are red and four green. There should be a ninth stone coloured yellow and square so that all nine stones can be fitted together to form a square in such a way that the red stones completely enclose the other five and the green stones completely enclose the yellow one.

    What are the dimensions of the red stones?

    [teaser150]

     
    • Jim Randell 8:03 am on 10 July 2022 Permalink | Reply

      The tiles that are mentioned have a total area of 2183.

      If the missing central tile has an area of x², and the entire collection has an area of y² then we have:

      y² = x² + 2183
      y² − x² = 2183
      (y − x)(y + x) = 2183

      So we can calculate possible values for x and y by examining the divisors of 2183.

      The Python program find values for x and y, and then chooses 4 green tiles, along with the x by x yellow square, which can fit together to form a square. And then checks that this square, along with the the remaining (green) tiles can fit together to form a y by y square.

      We use the rectpack.py module to fit the tiles into squares.

      The program runs in 169ms.

      Run: [ @replit ]

      from enigma import (divisors_pairs, div, subsets, is_square, cproduct, printf)
      import rectpack
      
      # areas of tiles we are given
      areas = {504, 420, 324, 306, 270, 130, 117, 112}
      
      # record possible tiles
      dps = dict((x, list(divisors_pairs(x))) for x in areas)
      
      # select tiles by area <x>, with max dimension not exceeding <m>
      tiles = lambda x, m: ((a, b) for (a, b) in dps[x] if not(b > m))
      
      # pack rectangles <rs> and an <s> by <s> square into a <t> by <t> square
      def pack(rs, s, t):
        # make the list of rectangles
        rs_ = [(s, s)]
        rs_.extend(rs)
        # pack them into a t by t square
        for ps in rectpack.pack(t, t, rs_):
          # check the square is not on the edge
          if not any(
            w == h == s and x > 0 and y > 0 and x + w < t and y + h < t
            for (x, y, w, h) in ps
          ): continue
          return ps  # we only need one packing
      
      # consider divisors of the total area
      for (a, b) in divisors_pairs(sum(areas)):
        # calculate x and y
        (x, y) = (div(b - a, 2), div(a + b, 2))
        if x is None or y is None or y < x + 4: continue
        # choose 4 green tiles to go around a central x by x square
        for green in subsets(areas, size=4):
          z = is_square(x * x + sum(green))
          if z is None: continue
          # consider dimensions of green tiles
          for gs in cproduct(tiles(x, z) for x in green):
            # pack them into a z by z square
            ps1 = pack(gs, x, z)
            if ps1 is None: continue
            # consider dimensions of red tiles
            red = areas.difference(green)
            for rs in cproduct(tiles(x, y) for x in red):
              # pack them into a y by y square
              ps2 = pack(rs, z, y)
              if ps2 is None: continue
              # output packings
              printf("red {red} around {z} x {z} green in {y} x {y}\n-> {ps2}")
              printf("green {green} around {x} x {x} yellow in {z} x {z}\n-> {ps1}")
              printf()
      

      Solution: The dimensions of the red stones (in inches) are: 3×39, 6×45, 9×36, 12×42.

      Here is a diagram of one possible layout:

      Like

      • Frits 1:01 pm on 10 July 2022 Permalink | Reply

        @Jim, it is not stated that the yellow and green tiles form a square.

        Like

        • Jim Randell 1:11 pm on 10 July 2022 Permalink | Reply

          @Frits: Is there a way the red stones can enclose the green ones without forming a square?

          Like

        • Jim Randell 1:14 pm on 10 July 2022 Permalink | Reply

          I suppose it could be a non-square rectangle. But luckily it is possible to do it with a square.

          Like

          • Frits 1:18 pm on 10 July 2022 Permalink | Reply

            So there might be another solution…

            Like

          • Jim Randell 1:26 pm on 10 July 2022 Permalink | Reply

            I made some tweaks to my program, and it didn’t find any solutions with a non-square rectangle. But I’ll have a closer look.

            Like

          • Jim Randell 2:53 pm on 10 July 2022 Permalink | Reply

            This is my program adapted to consider packing the green and yellow tiles into a (possibly non-square) rectangle.

            It doesn’t find any additional solutions.

            from enigma import (divisors_pairs, div, subsets, cproduct, printf)
            import rectpack
            
            # areas of tiles we are given
            areas = {504, 420, 324, 306, 270, 130, 117, 112}
            
            # record possible tiles
            dps = dict((x, list(divisors_pairs(x))) for x in areas)
            
            # select tiles by area <x>, with max dimension not exceeding <m>
            tiles = lambda x, m: ((a, b) for (a, b) in dps[x] if not(b > m))
            
            # pack rectangles <rs> and rectangle <s> into a bounding rectangle <t>
            def pack(rs, s, t):
              (a, b) = t
              # make the list of rectangles
              rs_ = [s]
              rs_.extend(rs)
              # pack them into a the rectangle
              for ps in rectpack.pack(t[0], t[1], rs_):
                # check that s is not on the edge
                if not any(
                  x > 0 and y > 0 and x + w < a and y + h < b and {w, h} == set(s)
                  for (x, y, w, h) in ps
                ): continue
                return ps  # we only need one packing
            
            # consider divisors of the total area
            for (a, b) in divisors_pairs(sum(areas)):
              # calculate x and y
              (x, y) = (div(b - a, 2), div(a + b, 2))
              if x is None or y is None or y < x + 4: continue
              # choose 4 green tiles to go around the central x by x square
              for green in subsets(areas, size=4):
                for (a, b) in divisors_pairs(x * x + sum(green)):
                  if a < x + 2 or y < b + 2: continue
                  # consider dimensions of green tiles
                  for gs in cproduct(tiles(x, b) for x in green):
                    # pack them into an a by b rectangle
                    ps1 = pack(gs, (x, x), (a, b))
                    if ps1 is None: continue
                    # consider dimensions of red tiles
                    red = areas.difference(green)
                    for rs in cproduct(tiles(x, y) for x in red):
                      # pack them into a y by y square
                      ps2 = pack(rs, (a, b), (y, y))
                      if ps2:
                        # output packings
                        printf("red {red} around {a} x {b} green in {y} x {y}\n-> {ps2}")
                        printf("green {green} around {x} x {x} yellow in {a} x {b}\n-> {ps1}")
                        printf()
            

            Like

    • Frits 5:02 pm on 10 July 2022 Permalink | Reply

      One piece of logic is not coded, it turns out it is not needed.

         
      from enigma import divisors_pairs
      from itertools import product
       
      # find three other red pieces which can form the outer ring
      def check(a, b, d):
        # combinations of length and width of fourth red piece
        lst = [[[big_square_side - x, (big_square_side - y) * x] 
                for x in d[big_square_side - y] if (big_square_side - x) in d] 
               for y in [a, b]]
        
        # check every combination of possible length and width
        for c, d in product(lst[0], lst[1]):
          # has the fourth piece a known area
          if c[0] * d[0] not in d_red: continue
      
          # do all four pieces have a different area
          if len(set([c[0] * d[0], a * b, c[1], d[1]])) != 4: continue
          # return all four pieces
          return tuple(sorted([tuple(sorted([a, b])), 
                 tuple(sorted([big_square_side - a, big_square_side - c[0]])), 
                 tuple(sorted([big_square_side - b, big_square_side - d[0]])), 
                 tuple(sorted([c[0], d[0]]))]))
         
        return tuple()          
            
      # areas of tiles we are given
      areas = sorted([504, 420, 324, 306, 270, 130, 117, 112])
       
      # record possible tiles
      d_tiles = dict((x, list(divisors_pairs(x))) for x in areas)
      
      # possible areas for the big square
      sqs = {n * n for n in range(1, areas[-4] + 1)}
      
      area_greenred = sum(areas)
      
      # candidates for yellow area
      area_yellow_cands = [sq for sq in sqs if (sq + area_greenred) in sqs]
      
      # check all candidates for yellow areas 
      for area in area_yellow_cands:
        big_square_side = int((area + area_greenred)**.5)
        yellow = int(area**.5)
        area_yellow = area
        
        # adjust possible red tiles to drop tiles with a big length
        d_red = {k: [x for x in vs if x[0] <= big_square_side and 
                                      x[1] <= big_square_side] 
                    for k, vs in d_tiles.items()}
        
        d_side = dict()     # dictionary per side
        for k, vs in d_red.items():
          for x in vs:
            d_side[x[0]] = d_side.get(x[0], set()) | {x[1]}
            d_side[x[1]] = d_side.get(x[1], set()) | {x[0]}
      
        if big_square_side in d_side:
          # valid situation but not coded!
          continue
        
        # as each piece now is shorter than the side of the big square
        # we need to have a form so that 2 sides of different pieces are equal to
        # the side of the big square, forms should be similar to this one:
        #
        #   +----------+--+
        #   |          |  |
        #   +----+-----+  |
        #   |    |     |  |
        #   |    +-----+--+
        #   |    |        |
        #   +----+--------+
        
        # adjust dictionary to keep only sides <x> for which complementary side 
        # <big_square_side> - <k> also exists
        d_side = {k: vs for k, vs in d_side.items() 
                        if big_square_side - k in d_side}
        # also adjust possible red tiles 
        d_red = {k: [x for x in vs if big_square_side - x[0] in d_side and 
                                      big_square_side - x[1] in d_side] 
                    for k, vs in d_red.items()}
       
        sol = set()
        for k, vs in d_red.items():
          # pick a first red piece
          for (le, wi) in vs:
            # find three other red pieces which can form the outer ring
            chk = check(le, wi, d_side)
            if chk:
              if chk not in sol:
                print("answer:", *chk)
              sol.add(chk)
      

      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
Create your website with WordPress.com
Get started
%d bloggers like this: