Updates from Jim Randell Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 10:25 am on 10 January 2021 Permalink | Reply
    Tags: by: P. R. Scott   

    Brain-Teaser 18: [Postal deliveries] 

    From The Sunday Times, 2nd July 1961 [link]

    Mr Simpson, who lives at No. 1453 Long Street, is a keen mathematician, and so he was most interested when, [while delivering a letter], his postman mentioned a strange coincidence. If the numbers of [any] two houses to which he made consecutive deliveries were added together, the result came to the number of the next house to which he delivered a letter.

    Mr Simpson asked him which houses he had visited, but the postman could only remember that some of them had single digits.

    To which house did the postman deliver a letter immediately before delivering Mr Simpson’s letter?

    I have changed the wording of this puzzle slightly for clarity.

    This puzzle was originally published with no title.

    [teaser18]

     
    • Jim Randell's avatar

      Jim Randell 10:26 am on 10 January 2021 Permalink | Reply

      I think the wording in this puzzle could have been made a bit clearer. (I have attempted to clarify the wording from the originally published text).

      Evidently, if we write down the numbers of the houses that the postman delivered to, in the order he delivered, we are told that for every house he visited (after the first two houses), the number of that house is the sum of the numbers of the previous two houses delivered to.

      So the numbers of the houses visited form a Fibonacci sequence. And we are told the sequence starts with two single digit numbers, and the number 1453 is in the sequence.

      This Python program runs in 45ms.

      from enigma import (irange, subsets, fib, printf)
      
      # collect solutions
      r = set()
      
      # choose a single digit number to start the sequence
      for (a, b) in subsets(irange(1, 9), size=2, select="P"):
        ns = list()
        for n in fib(a, b):
          if n > 1453: break
          ns.append(n)
          if n == 1453:
            r.add(ns[-2])
            printf("[({a}, {b}) -> {ns}]")
      
      printf("answer = {r}")
      

      Solution: The postman had just come from house number 898.

      There are in fact three possible starting pairs of house numbers:

      (2, 5) → (7, 12, 19, 31, 50, …)
      (3, 2) → (5, 7, 12, 19, 31, 50, …)
      (5, 7) → (12, 19, 31, 50, …)

      but they all end up settling down to generating the same sequence of higher valued house numbers, which does eventually reach 1453:

      …, 5, 7, 12, 19, 31, 50, 81, 131, 212, 343, 555, 898, 1453, …

      And the number immediately preceding 1453 is 898.

      As the ratio of consecutive terms in a Fibonacci sequence approaches the value of the Golden Ratio (𝛗 = (1 + √5) / 2), we can immediately calculate a good guess to the answer:

      % python
      >>> phi = 0.5 + sqrt(5, 4)
      >>> 1453 / phi
      898.0033856535972
      

      Like

    • Hugh Casement's avatar

      Hugh Casement 2:02 pm on 11 January 2021 Permalink | Reply

      So for every third house visited, the postman crossed the road and back again.
      That’s not the way our posties (male or female) work.
      I think a better puzzle could have put Simpson in an even-numbered house,
      all houses receiving post that day being on the one side of the street.

      That was a good idea to divide by phi. Repeated division, each time rounding to the nearest integer, would get us most of the way to the start of the sequence, though it would be safer after a while to take S(n) = S(n+2) – S(n+1) .
      Did we need to know that it starts with two single-digit terms? 1453/phi has a unique value!

      Like

    • John Crabtree's avatar

      John Crabtree 4:26 pm on 11 January 2021 Permalink | Reply

      Good question, but I think that the answer is yes. Otherwise you can get shorter sequences which reach 1453, ie:
      1453, 897, 556, 341, 215, 126, 89, 37, 52
      1453, 899, 554, 345, 209, 136, 73, 63, 10
      The ratio of successive terms oscillates about phi, and converges quite slowly.

      Like

    • Hugh Casement's avatar

      Hugh Casement 10:24 am on 12 January 2021 Permalink | Reply

      Thanks, John. The best approximations to phi are given by the original Fibonacci sequence.
      So if we double each term we get numbers all on the same side of the street.
      But perhaps the puzzle would then be too easy!

      Like

  • Unknown's avatar

    Jim Randell 4:56 pm on 8 January 2021 Permalink | Reply
    Tags:   

    Teaser 3042: A question of scale 

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

    The modernist music of Skaredahora eschewed traditional scales; instead he built scales up from strict mathematical rules.

    The familiar major scale uses 7 notes chosen from the 12 pitches forming an octave. The notes are in (1) or out of (0) the scale in the pattern 101011010101, which then repeats. Six of these notes have another note exactly 7 steps above (maybe in the next repeat).

    He wanted a different scale using 6 notes from the 12 pitches, with exactly two notes having another note 1 above, and one having another 5 above. Some notes could be involved in these pairings more than once.

    His favourite scale was the one satisfying these rules that came first numerically when written out with 0s & 1s, starting with a 1.

    What was Skaredahora’s favourite scale?

    [teaser3042]

     
    • Jim Randell's avatar

      Jim Randell 5:14 pm on 8 January 2021 Permalink | Reply

      By choosing the excluded pitches we ensure that the scales are generated in the required order, so we only need to find the first scale that satisfies the specified condition.

      This Python program runs in 45ms.

      Run: [ @repl.it ]

      from enigma import (subsets, irange, join, printf)
      
      # count notes with an interval of k
      interval = lambda ps, k: sum((p + k) % 12 in ps for p in ps)
      
      # choose six notes to exclude
      for xs in subsets(irange(1, 11), size=6):
        ps = tuple(p for p in irange(0, 11) if p not in xs)
      
        # count notes with an interval of 1 and 5
        if not (interval(ps, 1) == 2 and interval(ps, 5) == 1): continue
      
        # the solution is the first value we find
        printf("{s}", s=join("01"[i in ps] for i in irange(0, 11)))
        break
      

      Solution: Skaredahora’s favourite scale is 100010101110.

      We can consider this as a binary representation of the number 2222.

      There are 12 possible scales starting with 1 that have exactly 2 notes with another note 1 above, and exactly one having another note 5 above.

      There are also 12 possible scales starting with 0.

      Like

      • Jim Randell's avatar

        Jim Randell 11:04 am on 9 January 2021 Permalink | Reply

        Here is another solution that treats the scales as numbers represented in binary.

        We can use the [[ bit_permutations() ]] function from the enigma.py library (described here [link]) to generate patterns with 6 bits set in lexicographic order.

        It runs in 45ms overall, and has an internal runtime of 55µs.

        Run: [ @repl.it ]

        from enigma import (bit_permutations, dsum2, printf)
        
        # count notes with an interval of k
        def interval(n, k):
          m = n << (12 - k) # notes shifted up an interval of k
          v = n | (n << 12) # wrapped values
          return dsum2(v & m) # count the set bits
          
        # choose a bit pattern with 6 of the 12 digits set
        for n in bit_permutations(0b100000011111, 0b111111111111):
          # count notes with an interval of 1 and 5
          if interval(n, 1) == 2 and interval(n, 5) == 1:
            printf("{n} -> {n:012b}")
            # we only need the first value
            break
        

        And here is an “unrolled” version that has an internal runtime of only 24µs [ link ].

        Like

        • Tony Brooke-Taylor's avatar

          Tony Brooke-Taylor 12:54 pm on 9 January 2021 Permalink | Reply

          I tried the binary approach first and was annoyed that this took more than twice as long as your first solution Jim. Having swapped other bits of my algorithm for yours I think the biggest time difference comes from this: your first approach generates trials with only the 6 notes in; my binary approach generates trials with all 12 positions included, and then I have to use an if statement or similar to test only the 6.

          Like

    • Brian Gladman's avatar

      Brian Gladman 10:24 am on 9 January 2021 Permalink | Reply

      You get the speed record this week Jim. And you can gain a few percent more by using a set for in place of a tuple. Maybe I am being stupid but it was not immediately obvious to me why lexically sorted zero digit positions produced numerically sorted values.

      Like

      • Jim Randell's avatar

        Jim Randell 11:02 am on 9 January 2021 Permalink | Reply

        @Brian: The lowest number will have the largest leftmost grouping of 0’s. And fortunately combinations are generated in lexicographic order, so that gives us what we want.

        Like

    • Frits's avatar

      Frits 12:22 pm on 9 January 2021 Permalink | Reply

      As the puzzle is not yet fully clear to me I publish a solution which does the same as Jim’s code.
      I tried to use different and probably less efficient code.

      check1 = lambda s: sum(y == (x + 1) % 12 \
                             for (x, y) in list(zip(s, s[1:] + s[:1])))
      
      check5 = lambda s: sum(y - x == 5 or 12 + x - y == 5 
                             for x in s for y in s if y > x)    
      
      # loop backwards as first found solution will have maximal value
      # and thus the 2nd 1 bit will be as far to the right as possible
      for A in range(7, 0, -1):
        for B in range(8, A, -1):
          for C in range(9, B, -1):
            for D in range(10, C, -1):
               for E in range(11, D, -1):
                 if check1([0, A, B, C, D, E]) != 2: continue
                 if check5([0, A, B, C, D, E]) != 1: continue
                 
                 # print solution
                 for k in range(12):
                   print("1", end="") if k in {0, A, B, C, D, E} \
                                      else print("0", end="")
                 print()  
                 exit()
      

      Like

      • Frits's avatar

        Frits 1:00 pm on 9 January 2021 Permalink | Reply

        check5 can also be written as:

        check5 = lambda s: sum(y - x in {5, 7} for x in s for y in s if y > x)
        

        Like

    • Hugh Casement's avatar

      Hugh Casement 1:24 pm on 17 January 2021 Permalink | Reply

      Using Basic (oh horror!) I found the same solution as Jim.
      Five other scales can be found by transposing the scale up or down by appropriate numbers of semitones, always with 1 in first position. Each can be reversed to give the other six.

      I think the solution corresponds to C E F# G# A A#.
      Some of those sharps may be better designated as flats of the note above
      (though in an equitempered scale it makes no difference).

      Five semitones apart is the interval known as a fourth; that leaves seven semitones, known as a fifth, to the octave note. Those are generally considered the most harmonious intervals, so a person with normal hearing would want as many as possible in the scale. I bet S’s so-called music sounds even worse than the stuff they play in the supermarket so that we don’t linger over our shopping a moment longer than necessary. But then I’ve always said that the only good composer is a dead composer — preferably one who’s been dead for a couple of centuries.

      Like

  • Unknown's avatar

    Jim Randell 8:47 am on 7 January 2021 Permalink | Reply
    Tags:   

    Teaser 2768: In the bag 

    From The Sunday Times, 11th October 2015 [link] [link]

    A set of snooker balls consists of fifteen reds and seven others. From my set I put some [of the balls] into a bag. I calculated that if I picked three balls out of the bag simultaneously at random, then there was a one in a whole-number chance that they would all be red. It was more likely that none of the three would be red – in fact there was also a one in a whole-number chance of this happening.

    How many balls did I put in the bag, and how many of those were red?

    [teaser2768]

     
    • Jim Randell's avatar

      Jim Randell 8:48 am on 7 January 2021 Permalink | Reply

      (See also: Enigma 1551).

      This Python program runs in 47ms.

      Run: [ @repl.it ]

      from itertools import product
      from enigma import Rational, irange, multiply, printf
      
      F = Rational()
      
      # probability of choosing n balls with the same quality from t
      # where q of the t balls have the quality
      def P(n, t, q):
        return multiply(F(q - i, t - i) for i in irange(0, n - 1))
      
      # choose the number of non-red and red balls
      for (n, r) in product(irange(3, 7), irange(3, 15)):
        # there are r red and n non-red balls
        t = r + n
      
        # probability of 3 being red
        p1 = P(3, t, r)
      
        # probability of 3 being non-red
        p2 = P(3, t, n)
      
        # check the conditions
        if p1.numerator == 1 and p2.numerator == 1 and p1 < p2:
          printf("n={n} r={r}, t={t}, p1={p1} p2={p2}")
      

      Solution: There were 10 balls in the bag, 4 of them were red.

      So, the bag contained 6 red balls, and 4 non-red balls.

      When picking three balls, there is a 1/30 chance that they are all red, and a 1/6 chance of them all being non-red.

      Like

    • Frits's avatar

      Frits 6:37 pm on 7 January 2021 Permalink | Reply

      from enigma import gcd
      
      # pick at least one red
      for R in range(1, 7):
        # pick more others than reds
        for T in range(2 * R + 1, 14):
          den = T * (T - 1) * (T - 2)
         
          num = R * (R - 1) * (R - 2) 
          if num != gcd(num, den): continue
         
          num = (T - R) * (T - R - 1) * (T - R - 2)
          if num != gcd(num, den): continue
      
          print(f"{T} balls in the bag, {R} of them were red ")
          
      # 10 balls in the bag, 4 of them were red   
      

      Like

  • Unknown's avatar

    Jim Randell 9:29 am on 5 January 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 658: Fiendish device 

    From The Sunday Times, 17th February 1974 [link] [link]

    “Moriarty speaking”, said the voice on the telephone to the Prime Minister. “As you have rejected my demands, a hidden bomb with destroy London. I’m particularly pleased with the detonating device”, he went on, chuckling fiendishly, “it’s designed to give me time to get away before the explosion. There are 60 switches (all turned OFF at the moment) arranged in a ring so that No. 60 is next to No. 1. Whenever any switch changes from ON to OFF it causes the following switch to change over virtually instantaneously (from OFF to ON or vice-versa). As soon as I put down this phone I’ll activate the device. This will automatically put switch No. 1 to ON, then one minute later to OFF, then one minute later still to ON, carrying on in this way after each minute changing switch No. 1 over. As soon as every switch has remained in the OFF position for 10 seconds simultaneously the bomb explodes. So goodbye now — for ever!”

    The Prime Minister turned anxiously to Professor D. Fuse who had been listening in. “When will the activating device set off the bomb?” he asked.

    What was the Professor’s reply?

    This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.

    [teaser658]

     
    • Jim Randell's avatar

      Jim Randell 9:29 am on 5 January 2021 Permalink | Reply

      If there were only 3 switches, this what would happen:

      1 2 3
      1 0 0 (0m)
      0 1 0 (1m)
      1 1 0 (2m)
      0 0 1 (3m)
      1 0 1 (4m)
      0 1 1 (5m)
      1 1 1 (6m)
      1 0 0 (7m)

      If we read the switches backwards we see the system of switches operates as a binary counter starting at 001 (= 1) and counting up to 111 (= 7) after 6 minutes.

      After 7 minutes the counter would reach 8 = (000 + overflow), but the switches are arranged in a circle, so the overflow bit feeds into the least significant bit of the counter, so state 8 corresponds to state 1 (= 001) and we are back where we started.

      The counter cycles through the non-zero states 1-7 every 7 minutes, so never achieves state 0 and the bomb will never go off.

      So, with 60 switches we have a 60-bit counter which cycles through the states 1 – (2^60 − 1) every 1152921504606846975 minutes (= 2.2e+12 years), without ever reaching zero.

      Solution: The Professor’s reply is: “Never”.

      Like

  • Unknown's avatar

    Jim Randell 8:39 am on 3 January 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 17: [Knight’s tour] 

    From The Sunday Times, 25th June 1961 [link]

    In “Amusements in Mathematics” (Nelson, 1917), the late Henry Ernest Dudeney published a magic knight’s tour of the chessboard. That is to say, a knight placed on the square numbered 1 could, by ordinary knight’s moves, visit every square of the board in the ordered numbered, and the numbers themselves in each row and column added up to 260. Yet it was not a fully magic square, for the diagonals did not add to the same constant. After much trying Dudeney came to the conclusion that it is not possible to devise such a square complete with magic diagonals, but, as he said, a pious opinion is not a proof.

    You are invited to try your skill in devising a magic knight’s tour of a square 7×7, with or without magic diagonals.

    Dudeney’s Amusements in Mathematics is available on Project Gutenberg [link].

    This puzzle was originally published with no title.

    [teaser17]

     
    • Jim Randell's avatar

      Jim Randell 8:39 am on 3 January 2021 Permalink | Reply

      A 7×7 chessboard has 49 squares. So if we colour the corners black there will be 25 black squares and only 24 white squares. So the knight will have to start on a black square, and end on a black square. (So it is not possible for a tour to form a closed loop).

      So, 1 is on a black square. The next square in the tour will be a white square (as a knight always moves to a square of the other colour). So, 2 will be on a white square, 3 on a black square, etc. When the tour is complete all the black squares will be odd numbers and all the white squares will be even numbers.

      The rows/columns alternate between (4 black + 3 white) and (4 white + 3 black) squares, but the total of a row/column consisting of (4 black + 3 white) numbers will be (4 odd + 3 even) = even. And the total of a row/column consisting of (4 white + 3 black) will be (4 even + 3 odd) = odd. And we require the sum of each row and column to be the same (it should be T(49) / 7 = 175),

      So it will not be possible for us to make a magic squares as the sums of the values in the rows and columns will necessarily alternate between even and odd, so they can’t all be the same.

      Hence it is not possible to construct a magic knight’s tour on a 7×7 board.

      Like

    • Hugh Casement's avatar

      Hugh Casement 1:35 pm on 3 January 2021 Permalink | Reply

      Dudeney was by no means the first: see
      https://www.mayhematics.com/t/1d.htm
      https://mathworld.wolfram.com/MagicTour.html

      It has been proved (by computer) to be impossible on an 8×8 board,
      though there are many semi-magic tours.

      Like

  • Unknown's avatar

    Jim Randell 8:27 pm on 31 December 2020 Permalink | Reply
    Tags:   

    Teaser 3041: The best game played in 1966 

    From The Sunday Times, 3rd January 2021 [link] [link]

    For Christmas 1966 I got 200 Montini building blocks; a World Cup Subbuteo set; and a Johnny Seven multi-gun. I built a battleship on the “Wembley pitch” using every block, then launched seven missiles at it from the gun. The best game ever!

    Each missile blasted a different prime number of blocks off the “pitch” (fewer than remained). After each shot, in order, the number of blocks left on the “pitch” was:

    (1) a prime;
    (2) a square;
    (3) a cube;
    (4) (a square greater than 1) times a prime;
    (5) (a cube greater than 1) times a prime;
    (6) none of the aforementioned; and
    (7) a prime.

    The above would still be valid if the numbers blasted off by the sixth and seventh shots were swapped [with each other].

    How many blocks remained on the “pitch” after the seventh shot?

    [teaser3041]

     
    • Jim Randell's avatar

      Jim Randell 10:14 pm on 31 December 2020 Permalink | Reply

      This Python program runs in 45ms.

      from enigma import (irange, inf, primes, is_square, is_cube, printf)
      
      # primes less than 200
      primes.expand(200)
      
      # test x is of the form (a^k)p where p is prime and a >= m
      def test(x, k, m=2):
        for a in irange(m, inf):
          (p, r) = divmod(x, a**k)
          if p < 2: return False
          if r == 0 and p in primes: return True
      
      # tests
      t1 = primes.is_prime  # a prime
      t2 = is_square  # a square
      t3 = is_cube  # a cube
      t4 = lambda x: test(x, 2)  # (a square) times (a prime)
      t5 = lambda x: test(x, 3)  # (a cube) times (a prime)
      t6 = lambda x: not any(f(x) for f in (t1, t2, t3, t4, t5))  # none of the above
      t7 = t1  # a prime
      tests = (t1, t2, t3, t4, t5, t6, t7)
      
      # remove different prime amounts from <t>, remaining amounts satisfying <tests>
      # return the amounts removed
      def solve(t, tests, ns=[]):
        # are we done?
        if not tests:
          yield ns
        else:
          # remove less than half of t
          for n in primes:
            t_ = t - n
            if not (n < t_): break
            if n not in ns and tests[0](t_):
              yield from solve(t_, tests[1:], ns + [n])
      
      # find solutions
      for ns in solve(200, tests):
        r = 200 - sum(ns)
        # where the tests still work with the last 2 amounts swapped
        if t6(r + ns[-2]):
          printf("remaining={r} {ns}")
      

      Solution: There were 47 blocks remaining on the pitch after the seventh shot.

      There are six possible sequences that satisfy all the conditions of the puzzle, and they can be grouped into three pairs that give the same total number of blocks remaining:

      [3, 53, 19, 13, 31, 11, 29] → 41
      [3, 53, 19, 13, 31, 23, 17] → 41

      [3, 53, 19, 13, 31, 11, 23] → 47
      [3, 53, 19, 13, 31, 23, 11] → 47

      [3, 53, 19, 13, 31, 11, 17] → 53
      [3, 53, 19, 13, 31, 23, 5] → 53

      Each sequence is the same for the first 5 shots, and only the middle pair consists of sequences where the final two amounts are swapped over, so this gives our solution.

      Like

    • Robert Brown's avatar

      Robert Brown 12:54 pm on 1 January 2021 Permalink | Reply

      Since the sixth & seventh shots can be interchanged, they both take a prime value which doesn’t affect the rest of the puzzle. So I can’t see how we can decide which is which. Surely it would have been better if he had asked for the number of bricks remaining after the fifth shot?

      Like

      • Jim Randell's avatar

        Jim Randell 1:14 pm on 1 January 2021 Permalink | Reply

        @Robert: For any set of numbers chosen for the seven shots the number of blocks remaining after they have all been taken does not depend on the order they were taken in. So there is a unique answer for the number of blocks remaining, even though we don’t know what order the last two shots were taken in.

        Like

    • Robert Brown's avatar

      Robert Brown 6:10 pm on 1 January 2021 Permalink | Reply

      Thanks for that Jim. I realised after I posted my comment that I had misunderstood what the teaser said. The 6th shot prime must be chosen so that the balance remaining isn’t a square, a cube, a square times a prime or a cube times a prime. This gives 3 options, leading to a selection of possible 7th shot values.

      Liked by 1 person

    • Frits's avatar

      Frits 6:11 pm on 2 January 2021 Permalink | Reply

      Things are not necessarily efficient (I didn’t want to copy Jim’s test function or the approach at PuzzlingInPython).

      @Jim, I consider ” (fewer than remained)” also as part of “above would still be valid”, see last 2 checks.

      from enigma import SubstitutedExpression, is_prime, is_square, is_cube, \
                         seq_all_different
      
      # is number product of a prime and a square (k=2) / cube (k=3)
      def is_primeprod(n, k):
        # primes up to (200 / 2^2)
        P = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
        if k == 3: # primes up to (200 / 2^3)
          P = P[:9]
        for p in P:
          (d, r) = divmod(n, p)
          if d < 2: return False
          if r == 0 and ((k == 2 and is_square(d)) or (k == 3 and is_cube(d))): 
            return True
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
        "is_prime(200 - AB)", 
      
        "is_square(200 - AB - CD)", 
        # fewer than remained
        "2 * CD < 200 - AB",
      
        "is_cube(200 - AB - CD - EF)", 
        # fewer than remained
        "2 * EF < 200 - AB - CD",
      
        # (a square greater than 1) times a prime
        "is_primeprod(200 - AB - CD - EF - GH, 2)", 
        # fewer than remained
        "2 * GH < 200 - AB - CD - EF",
        
        # (a cube greater than 1) times a prime
        "is_primeprod(200 - AB - CD - EF - GH - IJ, 3)", 
        # fewer than remained
        "2 * IJ <  200 - AB - CD - EF - GH",
        
        # none of the aforementioned
        "not is_prime(200 - AB - CD - EF - GH - IJ - KL)",
        "not is_cube(200 - AB - CD - EF - GH - IJ - KL)",
        "not is_square(200 - AB - CD - EF - GH - IJ - KL)",
        "not is_primeprod(200 - AB - CD - EF - GH - IJ - KL, 2)",
        "not is_primeprod(200 - AB - CD - EF - GH - IJ - KL, 3)",
        # fewer than remained
        "2 * KL < 200 - AB - CD - EF - GH - IJ", 
        
        
        "is_prime(200 - AB - CD - EF - GH - IJ - KL - MN)",
        # fewer than remained
        "2 * MN < 200 - AB - CD - EF - GH - IJ - KL",
        
        "seq_all_different([AB, CD, EF, GH, IJ, KL, MN])",
        "all(is_prime(x) for x in [AB, CD, EF, GH, IJ, KL, MN])",
      
        
        # rules are still valid if the numbers blasted off by the sixth and 
        # seventh shots were swapped 
        "not is_prime(200 - AB - CD - EF - GH - IJ - MN)",
        "not is_cube(200 - AB - CD - EF - GH - IJ - MN)",
        "not is_square(200 - AB - CD - EF - GH - IJ - MN)",
        "not is_primeprod(200 - AB - CD - EF - GH - IJ - MN, 2)",
        "not is_primeprod(200 - AB - CD - EF - GH - IJ - MN, 3)",
        
        # fewer than remained (also after swapping)
        "2 * MN < 200 - AB - CD - EF - GH - IJ", 
        "2 * KL < 200 - AB - CD - EF - GH - IJ - MN", 
        ],
        answer="(AB, CD, EF, GH, IJ, KL, MN), \
                (200 - AB, \
                 200 - AB - CD, \
                 200 - AB - CD - EF, \
                 200 - AB - CD - EF - GH, \
                 200 - AB - CD - EF - GH - IJ, \
                 200 - AB - CD - EF - GH - IJ - KL, \
                 200 - AB - CD - EF - GH - IJ - KL - MN)",
        distinct="",
        d2i={},
        env=dict(is_primeprod=is_primeprod),
        verbose=0)   
      
      for (_, ans) in p.solve():  
        print(f"{ans}")
      

      Like

      • Jim Randell's avatar

        Jim Randell 6:58 pm on 2 January 2021 Permalink | Reply

        @Frits: You’re right. Here is a more rigorous implementation of my original approach.

        We collect all possible solutions, and look for a pair that are the same except the final two values are swapped over:

        from enigma import (irange, inf, primes, is_square, is_cube, group, printf)
        
        # primes less than 200
        primes.expand(200)
        
        # test x is of the form (a^k)p where p is prime and a >= m
        def test(x, k, m=2):
          for a in irange(m, inf):
            (p, r) = divmod(x, a**k)
            if p < 2: return False
            if r == 0 and p in primes: return True
        
        # tests
        t1 = primes.is_prime  # a prime
        t2 = is_square  # a square
        t3 = is_cube  # a cube
        t4 = lambda x: test(x, 2)  # (a square) times (a prime)
        t5 = lambda x: test(x, 3)  # (a cube) times (a prime)
        t6 = lambda x: not any(f(x) for f in (t1, t2, t3, t4, t5))  # none of the above
        tests = (t1, t2, t3, t4, t5, t6, t1)
        
        # remove different prime amounts from <t>, remaining amounts satisfying <tests>
        # return the amounts removed
        def solve(t, tests, ns=[]):
          # are we done?
          if not tests:
            yield ns
          else:
            # remove less than half of t
            for n in primes:
              t_ = t - n
              if not (n < t_): break
              if n not in ns and tests[0](t_):
                yield from solve(t_, tests[1:], ns + [n])
        
        # collect solutions, with the final two values ordered
        d = group(solve(200, tests), by=(lambda x: tuple(x[:5] + sorted(x[5:]))))
        # find a pair of solution values
        for (k, vs) in d.items():
          if len(vs) > 1:
            printf("remaining={r}; {vs}", r=200 - sum(k))
        

        Like

      • Frits's avatar

        Frits 12:01 pm on 8 January 2021 Permalink | Reply

        Coding the seq_all_different and is_prime clauses for each missile separately will bring the run time down from 1 second to 47ms.

        Like

    • Tony Brooke-Taylor's avatar

      Tony Brooke-Taylor 9:52 am on 7 January 2021 Permalink | Reply

      My original solution looked very messy but I was seeking to reduce the amount of looping over primes by starting in the middle – noting that there are only 4 cubes below 200, I wanted to generate and test cubes rather than primes initially.

      Being a Python novice, I am learning a lot from reviewing solutions on here (Jim’s or others’), so once I had solved the puzzle I came to look at this thread. Then as a test I tried to implement my algorithm using as much of Jim’s code as possible. I have not researched properly the relative time cost of looping through primes and testing other properties, as opposed to engineering the other properties and then testing if prime (which involves at least a look-up which itself must require looping). However, by starting with the square/cube pairs implied by tests 2 and 3, then working back to 200 in one direction and forwards using Jim’s code in the other, I reduced the average run-time on my machine from 0.90ms to 0.38ms.

      I won’t post all my code because I am using a few long-hand functions instead of the Enigma library. However, I think the following chunk should make it clear how I adapted Jim’s code to give a list of possible solutions from which to find the pair with interchangeable d5 and d6:

      convert "power" test into powers generator
      generates (a^k) up to and including x, from a minimum root m
      
      
      
      def powers(x,k,m=2):
          for a in range(m, int(x**(1/k))+1):
              yield a**k
      
      ...
      
      #Control program
      #Store long-list of primes
      n0=200
      primes = list(Primes(n0))
      
      #Start with all possible pairs of squares and cubes separated by a prime
      nsd = {}
      for n3 in powers(n0,3,3):# N3>cube of 2 since we need at least one cube for N5
          for n2 in powers(n0,2):
              d3 = n2 - n3
              if d3>n2/2:continue
              elif is_prime(d3):
                  nsd[(n2,n3)]=d3
      
      #For each of these pairs, run back up to n0 to find possible prime steps
      ns = []
      for n2, n3 in nsd.keys():
          for d2 in primes:
              if d2 > min((n0-n2),n2):break#we don't know n1 yet, so cap d2 as if d1=0
              else:
                  n1=n2+d2
                  d1=n0-n1
                  d3=nsd[(n2,n3)]
                  if is_prime(n1) and is_prime(d1) and len(set([d1,d2,d3]))==3:
      
      #And then run downwards to apply the remaining tests (per JR approach)                 
                      for solution in solve((n0-sum([d1,d2,d3])), (t4, t5, t6, t1)
      , [d1,d2,d3]):
                          ns.append(solution)
      

      Like

      • Frits's avatar

        Frits 12:53 pm on 8 January 2021 Permalink | Reply

        @Tony,

        Interesting idea.

        I am not coding in Python for a very long time.
        I like to use list comprehensions so I would have used something like this:

        nsd1 = [(s2, c3) for s in range(2, 15) for c in range(2, 6) 
                if is_prime(d := (s2 := s*s) - (c3 := c*c*c)) and 2 * d < s2]
        

        As you can calculate d3 from n2 and n3 you don’t need to use a dictionary to store the squares and cubes.

        Like

    • GeoffR's avatar

      GeoffR 8:21 am on 8 January 2021 Permalink | Reply

      My approach was to simulate the game, finding the blocks left (B1..B7) after firing the missiles in sequence (M1..M7).

      The programme produces outputs for the number of blocks remaining as 53, 41 and 47.

      However, only an output of 47 blocks remaining , after the 7th missile, allows the 6th and 7th missiles (shots) to be interchanged, so this is the answer to the teaser.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      int:blocks = 200;
       
      % list of missiles in sequence fired
      var 2..79:M1; var 2..79:M2; var 2..79:M3; var 2..79:M4; 
      var 2..79:M5; var 2..79:M6; var 2..79:M7;
      
      % all missiles are different (and prime numbers)
      constraint all_different ([M1, M2, M3, M4, M5, M6, M7]);
      
      % list of blocks remaining after each missile (shot)
      var 2..197:B1; var 2..197:B2; var 2..197:B3; var 2..197:B4;
      var 2..197:B5; var 2..197:B6; var 2..197:B7;
      
      % set of primes less than 200
      set of int :primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
      31, 37, 41, 43,47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
      101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157,
      163, 167, 173, 179, 181, 191, 193, 197, 199};
      
      % sets of squares and cubes less than 200
      set of int: cubes = { x * x * x | x in 2..5 };
      set of int: squares = { x * x | x in 2..14 };
      
      % set of all integers between 1 and 200
      set of int: all_int = {x | x in 1..200};
      
      % set of squares times primes
      set of int: sq_x_pr = {i * j | i in squares, 
      j in primes where i * j < 200};
      
      % set of cubes times primes
      set of int: cb_x_pr = {i * j | i in cubes, 
      j in primes where i * j < 200};
      
      % set of integers, none of the aforementioned
      set of int : none_of_afore = all_int diff primes 
      diff cubes diff squares diff sq_x_pr diff cb_x_pr;
      
      % 1st Missile M1 leaves Blocks B1, displacing M1 blocks 
      constraint B1 == blocks - M1 /\  M1 < B1 /\ M1 in  primes
      /\ B1 in primes;
      
      % 2nd Missile M2 leaves Blocks B2 
      constraint B2 = blocks - (M1 + M2) /\ M2 < B2 
      /\ M2 in primes /\ B2 in squares;
      
      % 3rd Missile M3 leaves Blocks B3 
      constraint B3 = blocks - (M1 + M2 + M3) /\ 
      M3 < B3 /\ M3 in primes /\ B3 in cubes;
      
      % 4th Missile M4 leaves Blocks B4 
      constraint B4 = blocks - (M1 + M2 + M3 + M4) 
      /\ M4 < B4 /\ M4 in primes /\ B4 in sq_x_pr;
      
      % 5th Missile M5 leaves Blocks B5 
      constraint B5 = blocks - (M1 + M2 + M3 + M4 + M5)
       /\ M5 < B5 /\ M5 in primes /\ B5 in cb_x_pr;
      
      % 6th Missile M6 leaves Blocks B6 
      constraint B6 = blocks - (M1 + M2 + M3 + M4 + M5 + M6)
       /\ M6 < B6 /\ M6 in primes /\ B6 in none_of_afore;
      
      % 7th Missile M7 leaves Blocks B7 
      constraint B7 = blocks - (M1 + M2 + M3 + M4 + M5 + M6 + M7)
      /\ M7 < B7 /\ M7 in primes /\ B7 in primes;
      
      solve satisfy;
      
      output [" Missile sequence: " ++ show(M1),", ", show(M2),
      ", ", show(M3),", ", show(M4),", ", show(M5),", ", show(M6),
      ", ", show(M7) 
      ++ "\n" ++ " Blocks left: " ++ show(B1),", ", show(B2),
      ", ", show(B3),", ", show(B4),", ", show(B5),", ", show(B6),
      ", ", show(B7) ];
      
      %  Missile sequence: 3, 53, 19, 13, 31, 11, 17
      %  Blocks left: 197, 144, 125, 112, 81, 70, 53
      % ----------
      %  Missile sequence: 3, 53, 19, 13, 31, 11, 23 
      %  Blocks left: 197, 144, 125, 112, 81, 70, 47  <<< ans
      % ----------
      %  Missile sequence: 3, 53, 19, 13, 31, 11, 29
      %  Blocks left: 197, 144, 125, 112, 81, 70, 41
      % ----------
      %  Missile sequence: 3, 53, 19, 13, 31, 23, 5
      %  Blocks left: 197, 144, 125, 112, 81, 58, 53
      % ----------
      %  Missile sequence: 3, 53, 19, 13, 31, 23, 11 
      %  Blocks left: 197, 144, 125, 112, 81, 58, 47  <<< ans
      % ----------
      %  Missile sequence: 3, 53, 19, 13, 31, 23, 17
      %  Blocks left: 197, 144, 125, 112, 81, 58, 41
      % ----------
      % ==========
      
      
      
      

      Like

      • Frits's avatar

        Frits 11:13 am on 8 January 2021 Permalink | Reply

        Adding this will only print the 2 solutions

        var 2..197:B6A;
        
        % 7th Missile M7 can be swapped with 6th Missile M6
        constraint B6A = blocks - (M1 + M2 + M3 + M4 + M5 + M7)
         /\ M7 < B6A /\ B6A in none_of_afore;
        

        Like

      • Frits's avatar

        Frits 12:09 pm on 8 January 2021 Permalink | Reply

        @GeoffR, I am not sure if the limit of 79 for missiles is correct.

        The minimum for 6 missiles is 41 (2+3+5+7+11+13) –> (200 – 41) / 2 = 79.5 ???

        I don’t immediately see why the first missile can’t be 83.

        Like

    • Geoff's avatar

      Geoff 12:30 pm on 10 January 2021 Permalink | Reply

      I don’t understand. What do the words in brackets mean – (fewer than remained) – I took this to mean that each of the 7 prime numbers where smaller than the number of blocks left on the pitch. So if 53 are kicked off on the second go, don’t we need more than 53 left on the pitch? Or does it mean fewer than remained after that particular shot?

      Like

      • Jim Randell's avatar

        Jim Randell 12:40 pm on 10 January 2021 Permalink | Reply

        @Geoff: I took it to mean that at each stage the number of blocks knocked off is less than the number of blocks remaining after that shot. (So the number knocked off is less than half the number of blocks available).

        So at the beginning there are 200 blocks available, so in the first shot we can knock off between 1 and 99.

        If we knock off 3 with the first shot, there are 197 blocks remaining, so the second shot can knock off between 1 and 98.

        If we knock off 53 with the second shot, there are 144 blocks remaining, so the third shot can knock off between 1 and 71.

        And so on, until all 7 shots are taken.

        Like

  • Unknown's avatar

    Jim Randell 8:37 am on 31 December 2020 Permalink | Reply
    Tags: ,   

    Teaser 1995: Pyramid selling 

    From The Sunday Times, 10th December 2000 [link]

    At the fruit stall in our local market the trader built a stack of oranges using the contents of some complete boxes, each containing the same number of oranges.

    He first laid out one box of oranges in a rectangle to form the base of a stack. He then added more oranges layer by layer from the contents of the other boxes. Each layer was a rectangle one orange shorter and narrower than the layer beneath it.

    The top layer should have consisted of a single row of oranges but the trader was one orange short of being able to complete the stack.

    How many oranges were there in each box?

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

    This completes the 72 puzzles from the Brainteasers (2002) book.

    In the New Year I will start posting puzzles from the 1980 book The Sunday Times book of Brain Teasers: Book1 (50 hard (very hard) master problems), compiled by Victor Bryant and Ronald Postill. It is a selection of Teaser puzzles originally published in The Sunday Times between January 1974 and December 1979.

    Happy New Year from S2T2!

    [teaser1995]

     
    • Jim Randell's avatar

      Jim Randell 8:38 am on 31 December 2020 Permalink | Reply

      See: Enigma 1086.

      This Python program runs in 43ms.

      Run: [ @repl.it ]

      from enigma import (irange, inf, div, printf)
      
      # calculate stacking numbers n <= m
      stack = lambda n, m: sum((n - i) * (m - i) for i in irange(n))
      # or: n * (n + 1) * (3 * m - n + 1) // 6
      
      # generate (n, m) pairs where 1 < n < m
      def pairs():
        for t in irange(5, inf):
          for n in irange(2, (t - 1) // 2):
            yield (n, t - n)
      
      # consider n, m values
      for (n, m) in pairs():
        # number of oranges in a box
        b = n * m
        # number of stacked oranges
        s = stack(n, m) - 1
        # number of boxes required
        k = div(s, b)
        if k is not None:
          printf("n={n} m={m} b={b} s={s} k={k}")
          break
      

      Solution: There were 72 oranges in each box.

      3 boxes were used, making a total of 216 oranges.

      The base layer was 6 × 12 layer, using 72 oranges (= 1 box).

      The remaining layers:

      5 × 11 = 55
      4 × 10 = 40
      3 × 9 = 27
      2 × 8 = 16
      1 × 6 = 6 (the final layer is 1 orange short)

      use 55+40+27+16+6 = 144 oranges (= 2 boxes)


      Manually:

      To complete a structure starting with a base that is n × m where n ≤ m, the number of oranges required is:

      S(n, m) = n(n + 1)(3m − n + 1)/6

      And if we use k boxes we have:

      n(n + 1)(3m − n + 1) / 6 = kmn + 1
      n(n + 1)(3m − n + 1) = 6kmn + 6

      n divides the LHS, so n must divide the RHS, hence n divides 6.

      So: n = 1, 2, 3, 6.

      If n = 6:

      m = 12 / (7 − 2k)

      so: m = 12, k = 3.

      If n = 3:

      m = 5 / (6 − 3k)

      doesn’t work.

      If n = 2:

      m = 2 / (3 − 2k)

      doesn’t work.

      If n = 1:

      m = 1 / (1 − k)

      doesn’t work.

      So: n = 6, m = 12, k = 3 is the only viable solution.

      Like

  • Unknown's avatar

    Jim Randell 8:46 am on 29 December 2020 Permalink | Reply
    Tags:   

    Teaser 2508: [Near miss] 

    From The Sunday Times, 17th October 2010 [link] [link]

    An Austin was pootling along a country lane at 30mph; behind were a Bentley doing 40mph and a Cortina doing 50mph. The Bentley and the Cortina braked simultaneously, decelerating at constant rates, while the Austin carried on at the same speed. The Bentley just avoided hitting the rear of the Austin, [while, at the same time,] the Cortina just avoided a collision with the Bentley. The Bentley and the Cortina continued to decelerate at the same rates, and stopped with a 45 yard gap between them.

    What was the gap between the Bentley and the Cortina at the moment they started to brake?

    The wording in this puzzle has been modified from the published version for clarification.

    This puzzle was originally published with no title.

    [teaser2508]

     
    • Jim Randell's avatar

      Jim Randell 8:46 am on 29 December 2020 Permalink | Reply

      I am assuming that at the time of the “almost collision” the separation between A, B and B, C can be considered to be zero. (And so we can consider the cars to be points, that coincide at the moment of “almost collision”).

      This puzzle can be solved graphically, without the need to resort to equations of motion (although you can solve it that way too).

      If we plot the velocities of the Austin (red), the Bentley (green), and the Cortina (blue) against time we get a graph like this:

      Where red carries on at a steady 30mph, green starts at 40mph and decelerates steadily to 0mph (BB’), and blue starts at 50mph and decelerates steadily to 0mph (CC’).

      At X, all their speeds are 30mph, and this is the point at which the separations between the cars are zero (the almost collision).

      The area under the line XB’ gives the distance travelled by green after the almost collision, and the area under the line XC’ gives the distance travelled by blue after the almost collision.

      And the difference between these distances corresponds to their final separation:

      area(XUB’) − area(XUC’) = 45 yards
      (45 − 45/2) units = 45 yards
      1 unit = 2 yards

      Similarly we can calculate the difference between the areas under the lines CX and BX to get the separation of green and blue at the time they started braking:

      area(CAX) − area(BAX) = (10 − 5) units
      = 10 yards

      Solution: The Bentley and the Cortina were 10 yards apart at the time they started braking.

      Like

  • Unknown's avatar

    Jim Randell 8:27 am on 27 December 2020 Permalink | Reply
    Tags:   

    Teaser 1991: Numismathematics 

    From The Sunday Times, 12th November 2000 [link]

    I have three circular medallions that I keep in a rectangular box, as shown. The smallest (of radius 4cm) touches one side of the box, the middle-sized one (of radius 9cm) touches two sides of the blox, the largest touches three sides of the box, and each medallion touches both the others.

    What is the radius of the largest medallion?

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

    [teaser1991]

     
    • Jim Randell's avatar

      Jim Randell 8:27 am on 27 December 2020 Permalink | Reply

      Here’s a manual solution:

      Labelling the centres of the medallions (smallest to largest) are A, B, C, and the corresponding radii are 4, 9, R.

      Then the horizontal displacement between B and C, h(B, C), is given by:

      h(B, C)² = (R + 9)² − (R − 9)²
      h(B, C)² = 36R
      h(B, C) = 6r, where: r = √R

      And the horizontal displacement between A and C, h(A, C), is given by:

      h(A, C)² = (R + 4)² − (R − 4)²
      h(A, C)² = 16R
      h(A, C) = 4r

      And the difference in these displacements is the horizontal displacement between A and B, h(A, B):

      h(A, B) = h(B, C) − h(A, C)
      h(A, B) = 2r
      h(A, B)² = 4r² = 4R

      The vertical displacement between A and B, v(A, B), is given by:

      v(A, B) = 2R − 13

      Then we have:

      h(A, B)² + v(A, B)² = 13²
      4R + (2R − 13)² = 13²
      4R + 4R² − 52R = 0
      4R(R − 12) = 0

      So R = 12.

      Solution: The radius of the largest medallion is 12cm.

      Like

  • Unknown's avatar

    Jim Randell 10:31 pm on 23 December 2020 Permalink | Reply
    Tags:   

    Teaser 3040: Moving digit 

    From The Sunday Times, 27th December 2020 [link] [link]

    Jonny has opened a new bank account and has set up a telephone PIN. His sort code is comprised of the set of three two-figure numbers with the smallest sum which give his PIN as their product. He was surprised to find that the PIN was also the result of dividing his eight-figure account number by one of the three two-figure numbers in the sort code.

    The PIN has an unusual feature which Jonny describes as a moving digit. If the number is divided by its first digit then the number which results has the same digits in the same order except that first digit is now at the end.

    The account number does not contain the digit which moved.

    What is the account number?

    [teaser3040]

     
    • Jim Randell's avatar

      Jim Randell 10:54 pm on 23 December 2020 Permalink | Reply

      Using a similar analysis to Teaser 3031 we get:

      If the PIN is represented by leading digit a and remaining digits r (a k digit number), then:

      r = a(10^k − a) / (10a − 1)

      The PIN is an 8-digit number divided by a 2-digit number, so it must have 6 or 7 digits. But it is also the product of three 2-digit numbers, so it has at most 6 digits.

      This gives only a few candidates for the PIN (and only one “proper” candidate), which can then be checked against the remaining conditions.

      This Python 3 program runs in 43ms.

      Run: [ @replit ]

      from enigma import (irange, div, divisors_pairs, catch, ndigits, nsplit, printf)
      
      # decompose n into k 2-digit divisors
      def decompose(n, k, m=10, ds=[]):
        if k == 1:
          if 9 < n < 100 and not(n < m):
            yield ds + [n]
        else:
          for (d, r) in divisors_pairs(n):
            if d < m: continue
            if d > 99: break
            yield from decompose(r, k - 1, d, ds + [d])
      
      # consider k digit numbers for r
      k = 5
      m = 10**k
      # consider possible leading digits
      for a in irange(1, 9):
        r = div(a * (m - a), 10 * a - 1)
        if r is None: continue
        PIN = a * m + r
        # find the numbers in the sort code
        sc = catch(min, decompose(PIN, 3), key=sum)
        if sc is None: continue
        # find possible account numbers
        ac = list(n for n in (x * PIN for x in set(sc)) if ndigits(n) == 8 and a not in nsplit(n))
        if ac:
          # output solutions
          printf("PIN = {PIN}; sort-code = {sc}; account-number = {ac}")
      

      Solution: The account number is 31589712.

      The 2-digit numbers in the sort code are: 72, 74, 77, so the PIN is 410256.

      And we have:

      31589712 / 77 = 410256
      410256 / 4 = 102564


      If the “two-figure” numbers in the sort code, and the “eight-figure” account number are allowed to have leading zeros, then there are further solutions:

      PIN = 111; sort-code = (01, 03, 37); account-number = 00000333
      PIN = 111111; sort-code = (37, 39, 77); account-number = 08555547
      PIN = 111111; sort-code = (37, 39, 77); account-number = 04333329

      The PIN cannot have a leading zero, as we want to divide by the leading digit.

      Like

      • Frits's avatar

        Frits 1:41 pm on 24 December 2020 Permalink | Reply

        @Jim, Very concise.
        I think you can limit k to 3,4,5 as PIN cannot be a 7 digit number.

        Like

        • Jim Randell's avatar

          Jim Randell 2:50 pm on 24 December 2020 Permalink | Reply

          @Frits: Yes. I’d forgotten PIN is (k + 1) digits.

          And in fact we can see that PIN can only have 6 digits (so k = 5).

          Like

    • Frits's avatar

      Frits 9:58 pm on 24 December 2020 Permalink | Reply

      from enigma import SubstitutedExpression
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
        # smallest 8-digit number divided by biggest 2-digit number:
        # 10,000,000 // 99 = 101,010 so PIN is a 6-digit number
        #
        # PIN = AB * CD * EF = GHIJKL
        # 
        # HIJKL = G * (10^5 - G) / (10G - 1) 
        
        "AB <= CD",
        "CD <= EF",
        
        # PIN is product of three 2-digit numbers
        "AB * CD * EF = GHIJKL",
        
        # moving digit formula
        "G * (100000 - G) == HIJKL * (10 * G - 1)", 
        ],
        answer="(GHIJKL, AB + CD + EF, [GHIJKL * AB, GHIJKL * CD, GHIJKL * EF])",
        distinct="",
        d2i={0: "ACEG"},
        reorder=0,
        verbose=0)   
      
      answs = sorted([y for _, y in p.solve()])
      
      prev = ""
      for ans in answs:  
        if ans[0] != prev:      # only do once for minimal sum
          accounts = [x for x in ans[2] if str(ans[0])[0] not in str(x) 
                      and len(str(x)) == 8]
          if len(accounts) != 1: continue
          print(f"account number {accounts[0]}")
        prev = ans[0]
      

      Like

    • Frits's avatar

      Frits 11:58 am on 25 December 2020 Permalink | Reply

      Framework has been taken from the generated code of the previous program.
      It can’t be run with PyPy yet (due to the walrus operator).

      # product of three 2-digit numbers can't be a 7-digit number
      #
      # smallest 8-digit number divided by biggest 2-digit number:
      # 10,000,000 // 99 = 101,010 so PIN has to be a 6-digit number
      #
      # moving digit formula (pin1 = first digit, pin2_6 = the remaining digits):
      #
      # pin1.(100000 - pin1) / (10.pin1 - 1) = pin2_6
      
      sol = []
      
      # increasing sort codes AB, CD and EF 
      for AB in range(10, 100):
        for CD in range(AB, 100):
          mi = max(CD, round(100000 / (AB * CD) + 0.5))
          for EF in range(mi, 100):
            pin = AB * CD * EF
            pin1 = pin // 100000
            pin2_6 = pin % 100000
            # moving digit formula  
            if pin1 * (100000 - pin1) == pin2_6 * (10 * pin1 - 1):
              sol.append([pin, AB + CD + EF, AB, CD, EF])
      
      prev = -1
      for s in sorted(sol):  
        if s[0] != prev:      # only do once for a minimal sum
          # account number has eight digits, none equal to the PIN's first digit
          accounts = [a for x in s[2:] if str(s[0])[0] not in (a := str(x * s[0])) 
                      and len(a) == 8]
                      
          if len(accounts) > 0:
            print(f"account number(s): {', '.join(str(x) for x in accounts)}")
        prev = s[0]
      

      Like

      • Frits's avatar

        Frits 12:15 pm on 25 December 2020 Permalink | Reply

        AB could also have 11 as minimum.

        CD could also have as minimum:

        mi = max(AB, round(round(100000 / 99 + 0.5) / AB + 0.5))
        

        Like

    • GeoffR's avatar

      GeoffR 2:10 pm on 26 December 2020 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % 6-digit PIN number
      var 100000..999999: PIN;
      
      % 8-digit Account number 
      % Search range reduced to one million to limit run-time
      var 31000000..32000000: ACCNO;
      
      var 1..9:p; var 0..9:q; var 0..9:r;  var 0..9:s; 
      var 0..9:t; var 0..9:u; var 0..9:v;  var 0..9:w; 
      
      constraint ACCNO = 10000000*p + 1000000*q + 100000*r
      + 10000*s + 1000*t + 100*u + 10*v + w;
      
      % Using others similar analysis for the moving digit
      % d = initial digit, n = remaining number and N = power
      var 1..9: d;
      var 3..6: N;
      var 10000..99999:n;
      
      constraint d * pow(10,N) + n == d * (10*n + d);
      constraint PIN = d * pow(10,N) + n;
      
      % Three two digit numbers multiplied to give the PIN
      var 47..99: N1; var 47..99: N2; var 47..99: N3;  
      constraint N1 * N2 * N3 == PIN;
      
      % Find Account Number
      constraint  ACCNO == PIN * N1 \/ ACCNO == PIN * N2 
      \/ ACCNO == PIN * N3;
      
      constraint N3 > N2 /\ N2 > N1;
      
      % Smallest sum of three 2-digit numbers
      solve minimize(N1 + N2 + N3);
      
      % The moved digit 'dig1' is not in the account number
      var 1..9: dig1;
      constraint dig1 == PIN div 100000;
      
      % Set of digits for the account number
      var set of int: s1 = {p, q, r, s, t, u, v, w};
      constraint card(s1 intersect {dig1} ) == 0;
      
      output ["PIN = " ++ show(PIN)
      ++ "\n" ++ "ACC No. = " ++ show(ACCNO)
      ++ "\nThree 2-digit numbers are  " ++ show(N1) ++ 
      ", " ++ show(N2) ++ ", " ++ show(N3) ];
      
      
      

      Like

      • Frits's avatar

        Frits 1:57 pm on 27 December 2020 Permalink | Reply

        Based on GeoffR’s program. I didn’t reduce the account range to limit run-time, runs in half a second.

        Removing lines 56-58 gives the same result but is probably not a good idea in combination with the minimize function.

        % A Solution in MiniZinc
        include "globals.mzn";
        
        % Product of three 2-digit numbers can't be a 7-digit number
        %
        % Smallest 8-digit number divided by biggest 2-digit number:
        % 10,000,000 // 99 = 101,010 so PIN has to be a 6-digit number  
        var 101011..922082: PIN;                 % 97*97*98
        
        % Array of sort codes
        array[1..3] of var int: N;  
        
        % Array of possible accounts
        array[1..3, 1..8] of var int: t;  
        
        predicate toNum(array[int] of var int: a, var int: n,  int: base) =
                  let { int: len = length(a) }
                  in
                  n = sum(i in 1..len) (
                    ceil(pow(int2float(base), int2float(len-i))) * a[i]
                  )
                  /\ forall(i in 1..len) (a[i] >= 0 /\ a[i] < base)
        ; 
        
        predicate toNum10(array[int] of var 0..9: a, var int: n) = toNum(a, n, 10);
        
        % Using others similar analysis for the moving digit
        % d = initial digit, n = remaining number and N = power
        var 1..9: d;
        var 10000..99999:n;
        
        constraint d * 100000 + n == d * (10*n + d);
        constraint PIN = d * 100000 + n;
         
        % Three two digit numbers multiplied to give the PIN
        % N[1] <= 97 as 98^3 > 900,000 and 98^4 > 90,000,000, both containing a 9
        % N[2] >= 32 as 31*31*99 < 100,000
        % N[3] >= 47 as 46^3 < 100,000
        constraint N[1] > 10 /\ N[1] < 98;
        constraint N[2] > 31 /\ N[2] < 100;
        constraint N[3] > 46 /\ N[3] < 100;
         
        % Increasing 
        constraint N[3] > N[2] /\ N[2] > N[1];
        
        constraint N[1] * N[2] * N[3] == PIN;
        
        % Smallest sum of three 2-digit numbers
        solve minimize(sum(N));
         
        % The moved digit 'd' is not in the account number
        constraint toNum10(row(t, 1), PIN * N[1]) /\ PIN * N[1] > 9999999;
        constraint toNum10(row(t, 2), PIN * N[2]) /\ PIN * N[2] > 9999999;
        constraint toNum10(row(t, 3), PIN * N[3]) /\ PIN * N[3] > 9999999;
        
        constraint forall( [row(t, 1)[i] != d | i in 1..8] ) \/ 
                   forall( [row(t, 2)[i] != d | i in 1..8] ) \/ 
                   forall( [row(t, 3)[i] != d | i in 1..8] ); 
                   
        output ["PIN = " ++ show(PIN)];
        output ["\nACC No. = " ++ show(N[j] * PIN) ++ " " | j in 1..3 where fix(forall( [row(t, j)[i] != d | i in 1..8]))];
        output ["\nThree 2-digit numbers are  " ++ show(N)];
        output["\nSum = " ++ show(sum(N))];
        

        Like

        • Frits's avatar

          Frits 3:10 pm on 27 December 2020 Permalink | Reply

          A bit easier with div and mod.

          % A Solution in MiniZinc
          include "globals.mzn";
          
          % Product of three 2-digit numbers can't be a 7-digit number
          %
          % Smallest 8-digit number divided by biggest 2-digit number:
          % 10,000,000 // 99 = 101,010 so PIN has to be a 6-digit number  
          var 100000..999999: PIN;             
               
          % Array of sort codes
          array[1..3] of var int: N;  
          
          % Array of possible accounts
          array[1..3, 1..8] of var int: t;  
          
          % Using others similar analysis for the moving digit
          % d = initial digit, n = remaining number and N = power
          var 1..9: d;
          var 10000..99999:n;
          
          constraint d * 100000 + n == d * (10*n + d);
          constraint PIN = d * 100000 + n;
           
          % Three two digit numbers multiplied to give the PIN
          % N[1] <= 97 as 98^3 > 900,000 and 98^4 > 90,000,000, both containing a 9
          % N[2] >= 32 as 31*31*99 < 100,000
          % N[3] >= 47 as 46^3 < 100,000
          constraint N[1] > 10 /\ N[1] < 98;
          constraint N[2] > 31 /\ N[2] < 100;
          constraint N[3] > 46 /\ N[3] < 100;
           
          % Increasing 
          constraint N[3] > N[2] /\ N[2] > N[1];
          
          constraint N[1] * N[2] * N[3] == PIN;
          
          % Smallest sum of three 2-digit numbers
          solve minimize(sum(N));
           
          % The moved digit 'd' is not in the account number
          constraint forall( [(PIN * N[1] div pow(10,i-1) mod 10) != d | i in 1..8] ) \/ 
                     forall( [(PIN * N[2] div pow(10,i-1) mod 10) != d | i in 1..8] ) \/ 
                     forall( [(PIN * N[3] div pow(10,i-1) mod 10) != d | i in 1..8] ); 
          
          % Account consists of 8 digits          
          constraint forall( [PIN * N[i] > 9999999 | i in 1..3] );          
                     
          output ["PIN = " ++ show(PIN)];
          output ["\nACC No. = " ++ show(N[j] * PIN) ++ " " | j in 1..3 
                  where fix(forall( [(PIN * N[j] div pow(10,i-1) mod 10) != d 
                  | i in 1..8]))];
          output ["\nThree 2-digit numbers are  " ++ show(N)];
          output["\nSum = " ++ show(sum(N))];
          

          Like

    • GeoffR's avatar

      GeoffR 7:35 pm on 27 December 2020 Permalink | Reply

      @Frits:
      On running your latest two MiniZinc postings, I found that they both give three solutions as output.

      From my own experience in MinZinc, I also know this is possible and the correct solution can easily be found as one of the output solutions. However, for this teaser, my code produced a single solution. Maybe, with some minor amendment, this also might be possible for your code, but I am not sure why our outputs vary.

      I also try to generally try to make most of my code visible in the available posting space. However, I have not found any guidance/ recommendations on this matter and opinions vary. I did achieve this aim for my MiniZinc posting, but it gets increasingly difficult to achieve when page widths for posting decrease with replies to postings.

      I noticed there was quite a lot of your output code hidden from the available posting window on your first posting after my posting. I reformatted this last section of code to show that some simple adjustments to code can keep code readable in the window – please don’t mind me doing this as I am just making a comment.

      % Frits part teaser code only - formatting comment
        
      % The moved digit 'd' is not in the account number
      constraint toNum10(row(t, 1), PIN * N[1])
      /\ PIN * N[1] > 9999999;
      
      constraint toNum10(row(t, 2), PIN * N[2]) 
      /\ PIN * N[2] > 9999999;
      
      constraint toNum10(row(t, 3), PIN * N[3]) 
      /\ PIN * N[3] > 9999999;
       
      constraint forall( [row(t, 1)[i] != d | i in 1..8] ) 
      \/ forall( [row(t, 2)[i] != d | i in 1..8] ) 
      \/ forall( [row(t, 3)[i] != d | i in 1..8] ); 
                  
      output ["PIN = " ++ show(PIN)];
      output ["\nACC No. = " ++ show(N[j] * PIN) 
      ++ " " | j in 1..3 
      where fix(forall( [row(t, j)[i] != d | i in 1..8]))];
      output ["\nThree 2-digit numbers are  " ++ show(N)];
      output["\nSum = " ++ show(sum(N))];
      
      
      

      @Jim: Any comments about maximising available windows for posting code?

      Like

      • Jim Randell's avatar

        Jim Randell 7:24 pm on 31 December 2020 Permalink | Reply

        When running MiniZinc on a model with a maximise()/minimise() target you only expect to get one answer, but I think some solvers will output “best so far” solutions as they work if the “all solutions” parameter is selected.

        Replies on the site are indented, so there is less horizontal space. I like replies, rather than making new comment threads, but this is an issue for code. Unfortunately there doesn’t seem to be a documented option to allow code blocks to wrap long lines. (Although there is a [[ collapse="true" ]] option which means you have to click on it to view the code, which might be useful for long programs).

        Personally I’m not bothered that much by horizontal scrolling (I prefer it to lots of wrapped lines). If I really want to look at (or run) a program I will copy it into an editor.

        Like

    • GeoffR's avatar

      GeoffR 8:22 am on 28 December 2020 Permalink | Reply

      @Frits:
      Looking at the three solutions in the output, the first two solutions are not the minimum sum of the three two-digit numbers (224 and 225). The third solution is the answer and has a minimum sum of 223. Should have seen that earlier!

      Like

      • Frits's avatar

        Frits 10:36 am on 28 December 2020 Permalink | Reply

        @GeoffR, Yes, per default Minizinc will print intermediate solutions. In the configuration editor you have to use “user-defined behavior”.

        I normally try to keep code within lines of 80 bytes. I will not correct for indentations within WordPress itself.

        In your program “d” and “dig1” always seem to be the same as you have fixed PIN to 6 digits. Also N always have to be 5 in that case.

        Like

  • Unknown's avatar

    Jim Randell 10:37 am on 22 December 2020 Permalink | Reply
    Tags: by: Sgt. Tellis   

    Brain-Teaser 16: [Army number] 

    From The Sunday Times, 18th June 1961 [link]

    My army number has eight digits, the third being the same as the sixth, all the others occurring only once. The sum of the digits is 33, and the difference between the sum of the first four and the sum of last four is 3. The first four digits have irregular ascending values. When out of their correct order, three only of my last four digits have consecutive numerical value; in correct order there is a difference of at least 2 between consecutive digits. The highest digit is 7 and army numbers never start with zero.

    What is my number?

    This puzzle was originally published with no title.

    [teaser16]

     
    • Jim Randell's avatar

      Jim Randell 10:37 am on 22 December 2020 Permalink | Reply

      Alphametically, we can consider the number to be: ABCDECFG (the 3rd and 6th digits are the same).

      And we can use the [[ SubstitutedExpression ]] solver from the enigma.py library to solve the puzzle.

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

      #! python -m enigma -rr
      
      SubstitutedExpression
      
      # number is ABCDECFG (3rd and 6th digits the same)
      --answer="ABCDECFG"
      
      # use digits 0-7, no leading zero
      --digits="0-7"
      --invalid="0,A"
      
      # digit sum is 33
      "A + B + C + D + E + C + F + G == 33"
      
      # difference between sum of first 4 and last 4 is 3
      "abs((A + B + D) - (E + F + G)) == 3"
      
      # first 4 digits are ascending
      "A < B < C < D"
      # but not in arithmetic progression
      "not all_same(B - A, C - B, D - C)"
      
      # last 4 digits have no consecutive pairs
      "abs(C - E) > 1"
      "abs(F - C) > 1"
      "abs(G - F) > 1"
      
      # but exactly three of the digits are consecutive (when ordered)
      --code="check = unpack(lambda a, b, c, d: (c - a == 2) != (d - b == 2))"
      "check(sorted((E, C, F, G)))"
      
      # [optional] just display the answer
      --verbose=A
      

      Solution: The number is 23674605.

      Like

      • Frits's avatar

        Frits 2:34 pm on 22 December 2020 Permalink | Reply

        @Jim: “When out of their correct order, three only of my last four digits have consecutive numerical value”.

        You seem to have interpreted it as “at least three”.

        Like

        • Jim Randell's avatar

          Jim Randell 4:30 pm on 22 December 2020 Permalink | Reply

          @Frits: Yes, this would be a more accurate (and specific) test:

          --code="check = unpack(lambda a, b, c, d: (c - a == 2) != (d - b == 2))"
          "check(sorted((E, C, F, G)))"
          

          It doesn’t change the solutions found. But I’ll update my code.

          Like

    • Frits's avatar

      Frits 12:59 pm on 22 December 2020 Permalink | Reply

      “three of the digits are consecutive (in some order)” could (probably) also be achieved by:

      # ^ is bitwise XOR operator
      check = lambda li: li[2] == li[1] + 1 and \
                                  ((li[3] == li[2] + 1) ^ (li[1] == li[0] + 1))
      
      "check(sorted([E, C, F, G])"
      

      Like

  • Unknown's avatar

    Jim Randell 9:04 am on 20 December 2020 Permalink | Reply
    Tags:   

    Teaser 2570: Christmas Teaser 

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

    I asked my nine-year-old grandson Sam to set a Teaser for today’s special edition and the result was:

    SAM
    SET
    NICE
    CHRISTMAS
    TEASER

    Those words are the result of taking five odd multiples of nine and consistently replacing digits by letters.

    Given that THREE is divisible by 3; What is the 9-digit number CHRISTMAS?

    This was not a prize puzzle.

    [teaser2570]

     
    • Jim Randell's avatar

      Jim Randell 9:04 am on 20 December 2020 Permalink | Reply

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

      The following run file executes in 95ms.

      Run: [ @replit ]

      #! python -m enigma -rr
      
      SubstitutedExpression
      
      # all words are odd multiples of 9
      --code="f = lambda x: x % 18 == 9"
      "f(SAM)"
      "f(SET)"
      "f(NICE)"
      "f(CHRISTMAS)"
      "f(TEASER)"
      
      # and THREE is a multiple of 3
      "THREE % 3 = 0"
      
      --answer="CHRISTMAS"
      

      Solution: CHRISTMAS = 489051765.

      Like

    • GeoffR's avatar

      GeoffR 9:16 am on 20 December 2020 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..9:S; var 0..9:A; var 1..9:M; var 0..9:E;
      var 1..9:T; var 1..9:N; var 0..9:I; var 1..9:C;
      var 0..9:H; var 0..9:R;
      
      constraint all_different ([S,A,M,E,T,N,I,C,H,R]);
      
      var 100..999: SAM = 100*S + 10*A + M;
      var 100..999: SET = 100*S + 10*E + T;
      var 1000..9999: NICE = 1000*N + 100*I + 10*C + E;
      
      var 100000000..999999999: CHRISTMAS = S + 10*A
       + 100*M + 1000*T + 10000*S + 100000*I + 1000000*R
        + 10000000*H + 100000000*C;
      
      var 100000..999999: TEASER = 100000*T + 10000*E
       + 1000*A + 100*S + 10*E + R;
       
      var 10000..99999:THREE = 10000*T + 1000*H + 100*R + 11*E;
      
      constraint THREE mod 3 == 0;
      
      % five odd multiples of nine 
      constraint SAM mod 2 == 1 /\ SAM mod 9 == 0;
      constraint SET mod 2 == 1 /\ SET mod 9 == 0;
      constraint NICE mod 2 == 1 /\ NICE mod 9 == 0;
      constraint CHRISTMAS mod 2 == 1 /\  CHRISTMAS mod 9 == 0;
      constraint TEASER mod 2 == 1 /\ TEASER mod 9 == 0;
      
      solve satisfy;
      
      output["CHRISTMAS = " ++ show(CHRISTMAS)  ++
      "\nSAM = " ++ show(SAM) ++ ", SET = " ++ show(SET) ++
      "\nNICE = " ++ show(NICE) ++ ",  TEASER = " ++ show(TEASER) ];
      
      % CHRISTMAS = 489051765
      % SAM = 567, SET = 531
      % NICE = 2043,  TEASER = 136539
      % ----------
      % ==========
      
      
      

      Like

    • GeoffR's avatar

      GeoffR 10:57 am on 20 December 2020 Permalink | Reply

      Another solution using the digits only in the multiple numbers.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..9:S; var 0..9:A; var 1..9:M; var 0..9:E;
      var 1..9:T; var 1..9:N; var 0..9:I; var 1..9:C;
      var 0..9:H; var 0..9:R;
      
      constraint all_different ([S,A,M,E,T,N,I,C,H,R]);
      
      % last digits for 5 odd numbers
      constraint M==1 \/ M==3 \/ M==5 \/ M==7 \/ M==9;
      constraint T==1 \/ T==3 \/ T==5 \/ T==7 \/ T==9;
      constraint E==1 \/ E==3 \/ E==5 \/ E==7 \/ E==9;
      constraint S==1 \/ S==3 \/ S==5 \/ S==7 \/ S==9;
      constraint R==1 \/ R==3 \/ R==5 \/ R==7 \/ R==9;
      
      % THREE is divisible by 3, as are the sum of its digits
      constraint (T + H + R + E + E) mod 3 == 0;
      
      % five multiples of nine
      % sum of digits  of each nmber is also divisible by 9
      constraint (S + A + M) mod 9 == 0 ;
      constraint (S + E + T) mod 9 == 0 ;
      constraint (N + I + C + E) mod 9 == 0;
      constraint (C + H + R + I + S + T + M + A + S) mod 9 == 0;
      constraint (T + E + A + S + E + R) mod 9 == 0;
      
      solve satisfy;
      
      output ["CHRISTMAS = " ++ show(C),show(H),show(R),
      show(I),show(S),show(T),show(M),show(A),show(S) ];
      
      % CHRISTMAS = 489051765
      % ----------
      % ==========
      
      

      Like

    • Frits's avatar

      Frits 2:26 pm on 20 December 2020 Permalink | Reply

      Without using modulo and with the Walrus assignment (not possible to run with PyPy).

      from enigma import SubstitutedExpression 
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
        # all words are odd multiples of 9 (and don't start with zero)
        # digits M,E,S,T,R are odd and A,N,I,C,H are even
        
        # SAM digits: one odd, 2 even; so sum is even and multiple of 18
        # so A >= 2 (max(S+M) is 16), max(A) is 8 so M + S >= 10
        "M + S > 9",
        "S+A+M = 18",                # even
        "S+E+T = 9",                 # odd (9 or 27)
        "N+I+C+E = 9",               # odd, 27 not possible as 
                                     # max(N+I+C) = 14) and A is 6 or 8 (see below)
        
        # C+H+R+I+S+T+M+A+S equals C+H+R+I+S+T plus S+A+M
        "C+H+R+I+S+T == 27",          # odd (9, 27 or 45) 
        
        # T+E+A+S+E+R equals S+E+T plus A+E+R (so A+E+R is even)
        # max(A) is 8 so E + R >= 10
        "E+R > 9",
        "A+E+R = 18",                # even
        # E + R >= 10 and M + S >= 10 so T <= 5 
        
        # (A + E + R) mod 18 == 0 and (S + A + M) mod 18 == 0
        #  so E + R must be equal to M + S --> T is 1 or 5 and A is 6 or 8
         
        # and THREE is a multiple of 3
        # THREE contains one even digit and 4 odd digits 
        # so sum must be even and a multiple of 6
        "(tot := T+H+R+E+E) == 18 or tot == 24",   
        ],
        answer="(C,H,R,I,S,T,M,A,S), E,N",
        # A is 6 or 8, T is 1 or 5
        d2i=dict([(0, "MTESRACN")] + \
                 [(2, "MTESRA")] + \
                 [(3, "ANICHT")] + \
                 [(4, "MTESRA")] + \
                 [(7, "ANICHT")] + \
                 [(9, "ANICHT")] + \
                 [(k, "ANICH") for k in {1, 5}] + \
                 [(k, "MTESR") for k in {6, 8}]),
        distinct="CHRISTMAEN",
        reorder=0,
        verbose=0)   
      
      # print answers 
      for (_, ans) in p.solve():
        print(f"{ans}")
        
      # ((4, 8, 9, 0, 5, 1, 7, 6, 5), 3, 2)
      

      Like

      • Jim Randell's avatar

        Jim Randell 11:17 pm on 20 December 2020 Permalink | Reply

        @Frits: You could just use [[ "T+H+R+E+E in (18, 24)" ]] to eliminate the “walrus” operator.

        Like

        • Frits's avatar

          Frits 11:26 am on 21 December 2020 Permalink | Reply

          @Jim: Thanks. “T+H+R+E+E in {18, 24}” doesn’t work in combination with SubstitutedExpression. However, “T+H+R+E+E in set((18, 24))” works.

          As N+I+C+E = 9 we can also further analyze that I = 0.

          Some benchmark tests on lists, sets and tuples. In one case an in_test for sets is slower than for lists and tuples.

          import time
          from timeit import timeit
          from datetime import datetime
          
          # See https://stackoverflow.com/questions/2831212/python-sets-vs-lists
          # https://www.nuomiphp.com/eplan/en/92679.html
           
          # Determine if an object is present
          def in_test(iterable):
            for i in range(1000):
              if i in iterable:
                pass
          
          # Iterating
          def iter_test(iterable):
            for i in iterable:
              pass
          
          # Determine if an object is present
          print("# in_test")
          print("# set   ", timeit(
          "in_test(iterable)",
          setup="from __main__ import in_test; iterable = set(range(1000))",
          number=10000))
           
          print("# list  ",timeit(
          "in_test(iterable)",
          setup="from __main__ import in_test; iterable = list(range(1000))",
          number=10000))
          
          print("# tuple ", timeit(
          "in_test(iterable)",
          setup="from __main__ import in_test; iterable = tuple(range(1000))",
          number=10000))
          print()
          
          # Iterating
          print("# iter_test")
          print("# set   ", timeit(
          "iter_test(iterable)",
          setup="from __main__ import iter_test; iterable = set(range(10000))",
          number=100000))
          
          print("# list  ", timeit(
          "iter_test(iterable)",
          setup="from __main__ import iter_test; iterable = list(range(10000))",
          number=100000))
          
          print("# tuple ", timeit(
          "iter_test(iterable)",
          setup="from __main__ import iter_test; iterable = tuple(range(10000))",
          number=100000))
          print()
          
          
          
          def in_test1():
            for i in range(1000):
              if i in (314, 628):
                pass
          
          def in_test2():
            for i in range(1000):
              if i in [314, 628]:
                pass
          
          def in_test3():
            for i in range(1000):
              if i in {314, 628}:
                pass
          
          def in_test4():
            for i in range(1000):
              if i == 314 or i == 628:
                pass
          print("# Another in_test")
          print("# tuple", end=" ")
          print(timeit("in_test1()", setup="from __main__ import in_test1", 
                number=100000))
          print("# list ", end=" ")
          print(timeit("in_test2()", setup="from __main__ import in_test2", 
                number=100000))
          print("# set  ", end=" ")
          print(timeit("in_test3()", setup="from __main__ import in_test3", 
                number=100000))
          print("# or   ", end=" ")
          print(timeit("in_test4()", setup="from __main__ import in_test4", 
                number=100000))
          print()
          
          
          l = list(range(10000000))
          t = tuple(range(10000000))
          s = set(range(10000000))
          
          start = time.perf_counter()  
          -1 in l
          elapsed = time.perf_counter() 
          e = elapsed - start 
          print("# Time spent in list is: ", e)
          
          start = time.perf_counter()  
          -1 in s
          elapsed = time.perf_counter() 
          e = elapsed - start 
          print("# Time spent in set is: ", e)
          
          
          start = time.perf_counter()  
          -1 in t
          elapsed = time.perf_counter() 
          e = elapsed - start 
          print("# Time spent in tuple is: ", e)
          print()
          
          
          # Running with PyPy
          #
          # in_test
          # set    0.081273
          # list   1.5676623
          # tuple  4.0899722
          
          # iter_test
          # set    3.432239
          # list   3.486127399999999
          # tuple  2.8504029000000006
          
          # Another in_test
          # tuple 0.1158544999999993
          # list  0.11811669999999985
          # set   0.8540392000000008
          # or    0.12334350000000072
          
          # Time spent in list is:  0.0029356000000007043
          # Time spent in set is:  4.600000000465343e-06
          # Time spent in tuple is:  0.014147899999997549
          #
          # Running with Python 3.9.0
          #
          # in_test
          # set    0.4714717
          # list   51.8807992
          # tuple  48.01474160000001
          
          # iter_test
          # set    11.122311100000005
          # list   7.8272695
          # tuple  8.692177200000003
          
          # Another in_test
          # tuple 4.704576400000008
          # list  4.779769200000004
          # set   3.6342248999999924
          # or    4.508794999999992
          
          # Time spent in list is:  0.09308849999999325
          # Time spent in set is:  3.800000001774606e-06
          # Time spent in tuple is:  0.09272150000001034
          

          Like

    • GeoffR's avatar

      GeoffR 9:05 am on 22 December 2020 Permalink | Reply

      A Python 3 permutation solution.

      from itertools import permutations
      
      digits = set('0123456789')
      
      for P1 in permutations(digits, 4):
          T, H, R, E = P1
          if T == '0':
              continue
          if int(T) % 2 != 1:
              continue
          if int(E) % 2 != 1:
              continue
          THREE = int(T + H + R + E + E)
          if THREE % 3 != 0:
              continue
          Q1 = digits.difference(P1)
          # permute remaining digits
          for P2 in permutations(Q1):
              C, I, S, M, A, N = P2
              if '0' in (C, S, N):
                  continue
              if (int(M) % 2 != 1 or int(S) % 2 != 1
                      or int(R) % 2 != 1):
                  continue
              SAM, SET = int(S + A + M), int(S + E + T)
              if SAM % 9 != 0 or SET % 9 != 0:
                  continue
              NICE = int(N + I + C + E)
              TEASER = int(T + E + A + S + E + R)
              if NICE % 9 != 0 or TEASER % 9 != 0:
                  continue
              CHRISTMAS = int(C + H + R + I + S + T + M + A + S)
              if CHRISTMAS % 9 == 0:
                  print(f"CHRISTMAS = {CHRISTMAS}")
      
      
      

      Like

    • John Crabtree's avatar

      John Crabtree 3:16 am on 24 December 2020 Permalink | Reply

      E, M, R, S and T are odd, and A, C, H, I and N are even
      S+E+T is odd, = 9 = (1, 3, 5), and so M, R = (7, 9)
      N+I+C+E is odd, = 9 = (0, 2, 4, 3) or (0, 2, 6, 1)

      T+E+A+S+E+R is odd, = 27 and so A+E+R = 18
      C+H+R+I+S+T is odd, = 27, and so N+A+M+E (remaining letters) = 18 = A+E+R, and so R = M+N
      And so R = 9, M = 7, N = 2, and as C > 0, I = 0 and C + E = 7

      From N+A+M+E = 18 = S+A+M, S = E + 2, and so C + S = 9
      (C+H+R+I+S+T) – (T+H+R+E+E) = C + S – 2E = E mod 3 = 0 mod 3
      And so E = 3, A = 6; C = 4, S = 5; and T = 1, H = 8.

      CHRISTMAS = 489051765

      Like

  • Unknown's avatar

    Jim Randell 4:36 pm on 18 December 2020 Permalink | Reply
    Tags:   

    Teaser 3039: Three patterned paving 

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

    James is laying foot-square stones in a rectangular block whose short side is less than 25 feet. He divides this area into three rectangles by drawing two parallel lines between the longest sides and into each of these three areas he lays a similar pattern.

    The pattern consists of a band or bands of red stones laid concentrically around the outside of the rectangles with the centre filled with white stones. The number of red stone bands is different in each of the rectangles but in each of them the number of white stones used equals the number of outer red stones used.

    The total number of stones required for each colour is a triangular number (i.e., one of the form 1+2+3+…).

    What is the total area in square feet of the block?

    [teaser3039]

     
    • Jim Randell's avatar

      Jim Randell 5:51 pm on 18 December 2020 Permalink | Reply

      (See also: Teaser 3007).

      After some head scratching I realised that the parallel lines are parallel to the short sides of the rectangular block, not the long sides.

      Considering a section of paving that is n stones wide and h stones long.

      If we count the number of border layers on both sides of the central area, we get an even number b, such that b < n.

      And if the border area is the same as the central area we have:

      (n − b)(h − b) = nh/2
      h = 2b(n − b) / (n − 2b)

      So for any (n, b) pair we can calculate a value for h, and accept values where b < h.

      The following Python program runs in 44ms.

      Run: [ @replit ]

      from enigma import (irange, div, subsets, all_different, is_triangular, printf)
      
      # consider values for the short side of the rectangle
      for n in irange(3, 24):
        # collect sets of (<section-length>, <border-width>)
        ss = list()
        # consider possible border values
        for b in irange(2, (n - 1) // 2, step=2):
          # calculate section length
          h = div(2 * b * (n - b), n - 2 * b)
          if h is None or not (b < h): continue
          printf("[n={n} b={b} -> h={h}]")
          ss.append((h, b))
        # choose the 3 sections
        for ((h1, b1), (h2, b2), (h3, b3)) in subsets(ss, size=3):
          # the borders are all different
          if not all_different(b1, b2, b3): continue
          # total length of the sections
          h = h1 + h2 + h3
          if not (h > n): continue
          # total number of stones for each colour
          t = div(n * h, 2)
          if t is None or not is_triangular(t): continue
      
          # output solution
          printf("{n} x {h} -> A={A} (t={t}); sections = (h={h1}, b={b1}) (h={h2}, b={b2}) (h={h3}, b={b3})", A=2 * t)
      

      Solution: The total area of the block is 2352 square feet.

      The block is 24 feet wide and 98 feet long, and is split into three sections:

      24 feet × 10 feet, border 2 deep. (120 slabs of each colour).

      24 feet × 18 feet, border 3 deep. (216 slabs of each colour).

      24 feet × 70 feet, border 5 deep. (840 slabs of each colour).

      In total 1176 slabs of each colour are required, and 1176 = T(48).

      Here’s a diagram of the three sections, with the longest one in the middle:

      Like

    • Frits's avatar

      Frits 6:37 pm on 19 December 2020 Permalink | Reply

      I tried pythagorean_triples in combination with SubstitutedExpression (as n^2 + h^2 must be square) but that was too slow.

      from enigma import SubstitutedExpression, is_square
      
      # number of red stones: (n - b)(h - b)
      # number of white stones: nh/2
      # b^2 - (n + h)b + nh/2 = 0 
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [ 
        # AB = number of border layers on both sides of the central area
        # CDE = long side
        # FG = short side
        # FG is at least 15, 2+4+6 = 12, sum 3 different numbers of border layers
        #                    plus 3 whites
        "FG > 14",
        "FG < 25",
        "AB * AB - (CDE + FG) * AB + CDE * FG / 2 == 0",
        "AB > 0",
        "AB < CDE",
        "CDE > 0",
       
        # IJ = number of border layers on both sides of the central area
        # KLM = long side
        "IJ * IJ - (KLM + FG) * IJ + KLM * FG / 2 == 0",
        "IJ > 0",
        "KLM > 0",
        "IJ < KLM",
        "KLM > CDE", 
        
        # QR = number of border layers on both sides of the central area
        # STU = long side
        "QR * QR - (STU + FG) * QR + STU * FG / 2 == 0",
        "QR > 0",
        "STU > 0",
        "QR < STU",
        "STU > KLM",
        
        # the numbers of border layers are all different
        "len([AB, IJ, QR]) == len(set([AB, IJ, QR]))",
        
        # total number of stones for each colour must be triangular
        # if t is the nth triangular number, then t = n*(n+1)/2
        # and n = (sqrt(8t+1) - 1) / 2
      
        "is_square(4* FG * (CDE + KLM + STU) + 1)"
        ],
        answer="FG * (CDE + KLM + STU), FG, CDE, AB, KLM, IJ, STU, QR",
        # short side is even and < 25
        d2i=dict([(0, "F")] + \
                 [(1, "GBJR")] + \
                 [(k, "FGBJR") for k in {3, 5, 7, 9}] + \
                 [(k, "F") for k in {4, 6, 8}]),
        distinct="",
        reorder=0,
        verbose=0)   
      
      # collect and print answers 
      answs = sorted([y for _, y in p.solve()])
      print(" area,  n  h1  b1 h2  b1 h3  b3")
      for a in answs:
        print(f"{a}")
      

      Like

  • Unknown's avatar

    Jim Randell 8:07 am on 17 December 2020 Permalink | Reply
    Tags:   

    Teaser 2767: Cutting corners 

    From The Sunday Times, 4th October 2015 [link] [link]

    To make an unusual paperweight a craftsman started with a cuboidal block of marble whose sides were whole numbers of centimetres, the smallest sides being 5cm and 10cm long. From this block he cut off a corner to create a triangular face; in fact each side of this triangle was the diagonal of a face of the original block. The area of the triangle was a whole number of square centimetres.

    What was the length of the longest side of the original block?

    [teaser2767]

     
    • Jim Randell's avatar

      Jim Randell 8:08 am on 17 December 2020 Permalink | Reply

      Assuming the block is a rectangular cuboid (like a brick), lets us calculate the diagonals of the faces using Pythoagoras’ Theorem. (But this isn’t the only type of cuboid, see: [ @wikipedia ]).

      Suppose the sides of the block are (a, b, c).

      Then the lengths of the diagonals are: (x, y, z) = (√(a² + b²), √(a² + c²), √(b² + c²)).

      Using the following variant of Heron’s Formula [ @wikipedia ] for the area of a triangle with sides (x, y, z)

      4A = √(4x²y² − (x² + y² − z²)²)

      We can simplify this to calculate the area of a triangle formed by the diagonals as:

      4A = √(4(a² + b²)(a² + c²) − (2a²)²)
      2A = √(a²b² + a²c² + b²c²)

      And we are interested in when the area A is an integer, for given values of a and b.

      A = (1/2)√(a²b² + a²c² + b²c²)

      This Python program looks for the smallest solution for side c. It runs in 44ms.

      Run: [ @replit ]

      from enigma import (irange, inf, is_square, div, printf)
      
      # the smallest 2 sides are given
      (a, b) = (5, 10)
      (a2, b2) = (a * a, b * b)
      
      # consider values for the longest side
      for c in irange(b + 1, inf):
        c2 = c * c
      
        # calculate the area of the triangle
        r = is_square(a2 * b2 + a2 * c2 + b2 * c2)
        if r is None: continue
        A = div(r, 2)
        if A is None: continue
      
        # output solution
        printf("a={a} b={b} c={c}; A={A}")
        break # only need the first solution
      

      Solution: The longest side of the original block was 40 cm.


      In this case we are given a = 5, b= 10, so we have:

      4A² = 2500 + 125c²
      4A² = 125(20 + c²)
      c² = 4A²/125 − 4.5
      c = √(4A²/125 − 20)

      For c to be an integer, it follows the 4A² is divisible by 125 = 5³. So A is some multiple of 25, larger than 25.

      And we quickly find a solution, either manually, or using a program:

      from enigma import (irange, inf, is_square, div, printf)
      
      # consider values for the longest side
      for A in irange(50, inf, step=25):
        c = is_square(div(4 * A * A, 125) - 20)
        if c is not None:
          # output solution
          printf("a={a} b={b} c={c}; A={A}", a=5, b=10)
          break # only need the first solution
      

      However, this is not the only solution. If we leave the program running we find larger solutions:

      a=5 b=10 c=40; A=225
      a=5 b=10 c=720; A=4025
      a=5 b=10 c=12920; A=72225
      a=5 b=10 c=231840; A=1296025
      a=5 b=10 c=4160200; A=23256225
      a=5 b=10 c=74651760; A=417316025
      a=5 b=10 c=1339571480; A=7488432225

      These further solutions could have been eliminated by putting a limit on the size of the block (e.g. if the longest side was less than 7m long, which it probably would be for a desk paperweight).

      But we can generate these larger solutions more efficiently by noting that we have a form of Pell’s equation:

      4A² = a²b² + a²c² + b²c²
      (2A)² − (a² + b²)c² = a²b²

      writing:

      X = 2A
      D = a² + b²
      Y = c
      N = a²b²

      we get:

      X² − D.Y² = N

      And we are interested in solutions to the equation where X is even, and Y > b.

      We can use the pells.py solver from the py-enigma-plus repository to efficiently generate solutions:

      from enigma import (arg, ifirst, printf)
      import pells
      
      (a, b) = (5, 10)
      
      # given (a, b) generate solutions for (c, A) in c order
      def solve(a, b):
        (a2, b2) = (a * a, b * b)
        # solve: (a^2 + b^2).c^2 - 4.A^2 = -(a^2.b^2)
        for (c, A) in pells.diop_quad(a2 + b2, -4, -a2 * b2):
          if c > b:
            yield (c, A)
      
      # output the first N solutions
      N = arg(20, 0, int)
      for (c, A) in ifirst(solve(a, b), N):
        printf("a={a} b={b} c={c}; A={A}")
      

      Which gives the following output:

      a=5 b=10 c=40; A=225
      a=5 b=10 c=720; A=4025
      a=5 b=10 c=12920; A=72225
      a=5 b=10 c=231840; A=1296025
      a=5 b=10 c=4160200; A=23256225
      a=5 b=10 c=74651760; A=417316025
      a=5 b=10 c=1339571480; A=7488432225
      a=5 b=10 c=24037634880; A=134374464025
      a=5 b=10 c=431337856360; A=2411251920225
      a=5 b=10 c=7740043779600; A=43268160100025
      a=5 b=10 c=138889450176440; A=776415629880225
      a=5 b=10 c=2492270059396320; A=13932213177744025
      a=5 b=10 c=44721971618957320; A=250003421569512225
      a=5 b=10 c=802503219081835440; A=4486129375073476025
      a=5 b=10 c=14400335971854080600; A=80500325329753056225
      a=5 b=10 c=258403544274291615360; A=1444519726560481536025
      a=5 b=10 c=4636863460965394995880; A=25920854752758914592225
      a=5 b=10 c=83205138753102818310480; A=465130865823099981124025
      a=5 b=10 c=1493055634094885334592760; A=8346434730063040745640225
      a=5 b=10 c=26791796274954833204359200; A=149770694275311633440400025
      ...
      

      Solutions for the longest side (c) and area (A) can be calculated by the following recurrence relation:

      (c, A) → (40, 225)
      (c, A) → (9c + 8A/5, 50c + 9A)

      Like

  • Unknown's avatar

    Jim Randell 9:20 am on 15 December 2020 Permalink | Reply
    Tags:   

    Teaser 1967: Domino effect 

    From The Sunday Times, 28th May 2000 [link]

    I have placed a full set of 28 dominoes on an eight-by-seven grid, with some of the dominoes horizontal and some vertical. The array is shown above with numbers from 0 to 6 replacing the spots at each end of the dominoes.

    Fill in the outlines of the dominoes.

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

    [teaser1967]

     
    • Jim Randell's avatar

      Jim Randell 9:20 am on 15 December 2020 Permalink | Reply

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

      Run: [ @repl.it ]

      from enigma import DominoGrid
      
      DominoGrid(8, 7, [
        1, 6, 3, 3, 5, 6, 6, 0,
        2, 6, 2, 5, 4, 4, 3, 3,
        3, 6, 6, 5, 0, 4, 1, 3,
        2, 4, 5, 0, 0, 1, 1, 4,
        4, 4, 1, 1, 0, 2, 0, 6,
        0, 4, 3, 2, 0, 2, 2, 6,
        2, 1, 5, 5, 5, 5, 1, 3,
      ]).run()
      

      Solution: The completed grid is shown below:

      Like

    • Frits's avatar

      Frits 2:00 pm on 19 December 2020 Permalink | Reply

      You have to press a key each time for finding new dominoes/stones.

      import os
      from collections import defaultdict
        
      # grid dimensions (rows, columns)
      (R, C) = (7 ,8)
       
      g = [
          1, 6, 3, 3, 5, 6, 6, 0,
          2, 6, 2, 5, 4, 4, 3, 3,
          3, 6, 6, 5, 0, 4, 1, 3,
          2, 4, 5, 0, 0, 1, 1, 4,
          4, 4, 1, 1, 0, 2, 0, 6,
          0, 4, 3, 2, 0, 2, 2, 6,
          2, 1, 5, 5, 5, 5, 1, 3,
          ]
      
      # return coordinates of index number <n> in list <g>
      coord = lambda n: (n // C, n % C)
      
      # return index number in list <g>
      gnum = lambda x, y: x * C + y
      
      # return set of stone numbers in list <li>, like {'13', '15', '12'}
      domnums = lambda li: set("".join(sorted(str(li[i][1]) + str(li[i+1][1]))) 
                           for i in range(0, len(li), 2))
      
      # build dictionary of coordinates per stone
      def collect_coords_per_stone()  : 
        # empty the dictionary
        for k in coords_per_stone: coords_per_stone[k] = []
        
        for (i, d) in enumerate(g):
          if d < 0: continue           # already placed?
          # (x, y) are the coordinates in the 2 dimensional matrix
          (x, y) = divmod(i, C) 
          js = list()
          # horizontally
          if y < C - 1 and not(g[i + 1] < 0): js.append(i + 1)
          # vertically
          if x < R - 1 and not(g[i + C] < 0): js.append(i + C)
          
          # try possible placements
          for j in js:
            stone = tuple(sorted((g[i], g[j])))
            if ((coord(i), coord(j))) in ex: continue
           
            if not stone in done:
              coords_per_stone[stone] += [[coord(i), coord(j)]]
           
      # coordinate <mand> has to use stone {mandstone> so remove other possibilities
      def remove_others(mand, mandstone, reason):  
        global stop
        mandval = g[gnum(mand[0], mand[1])]
        stones = stones_per_coord[mand]
        for i in range(0, len(stones), 2):
          otherval = stones[i+1][1] if stones[i][0] == mand else stones[i][1]
          stone = sorted([mandval, otherval])
          # stone at pos <mand> unequal to <mandstone> ?
          if stone != mandstone:
            otherco = stones[i+1][0] if stones[i][0] == mand else stones[i][0]
            tup = tuple(sorted([mand, otherco]))
            if tup in ex: continue
            print(f"stone at {yellow}{str(tup)[1:-1]}{endc} "
                  f"cannot be {stone} {reason}")
            ex[tup] = stone
            stop = 0
      
      # check for unique stones and for a coordinate occurring in all entries 
      def analyze_coords_per_stone():
        global step, stop
        for k, vs in sorted(coords_per_stone.items()): 
          k_stone = tuple(sorted(k))
          if len(vs) == 1:
            pair = vs[0]
            x = gnum(pair[0][0], pair[0][1])
            y = gnum(pair[1][0], pair[1][1])
            if list(k_stone) in done: continue
      
            print(f"----  place stone {green}{k_stone}{endc} at coordinates "
                  f"{yellow}{pair[0]}, {pair[1]}{endc} (stone occurs only once)")
            done.append(k_stone)
            g[x] = g[y] = step
            step -= 1
            stop = 0
          elif len(vs) != 0:
            # look for a coordinate occurring in all entries
            common = [x for x in vs[0] if all(x in y for y in vs[1:])]
            if len(common) != 1: continue
            reason = " (coordinate " + yellow + str(common)[1:-1] + \
                     endc + " has to use stone " + str(k) + ")"
            # so remove <common> from other combinations
            remove_others(common[0], sorted(k), reason)
      
      # build dictionary of stones per coordinate
      def collect_stones_per_coord():
        stones = defaultdict(list)
        # collect stones_per_coord per cell
        for (i, d) in enumerate(g):
          if d < 0: continue      # already placed?
          # (x, y) are the coordinates in the 2 dimensional matrix
          (x, y) = divmod(i, C) 
          
          js = list()
          # horizontally
          if y < C - 1 and not(g[i + 1] < 0): js.append(i + 1)
          if y > 0     and not(g[i - 1] < 0): js.append(i - 1)
          # vertically
          if x < R - 1 and not(g[i + C] < 0): js.append(i + C)
          if x > 0     and not(g[i - C] < 0): js.append(i - C)
          # try possible placements
          for j in js:
            t = [[coord(i), g[i]], [coord(j), g[j]]]
            t2 = tuple(sorted((coord(i), coord(j))))
            if t2 not in ex:
              stones[(x, y)] += t
              
        return stones
        
      # check if only one stone is possible for a coordinate  
      def one_stone_left():
        global step, stop
        for k, vs in sorted(stones_per_coord.items()): 
          if len(vs) != 2: continue  
      
          pair = vs
          x = gnum(pair[0][0][0], pair[0][0][1])
          y = gnum(pair[1][0][0], pair[1][0][1])
          if g[x] < 0 or g[y] < 0: return
          
          stone = sorted([g[x], g[y]])  
          if stone in done: continue
      
          print(f"----  place stone {green}{tuple(stone)}{endc} at coordinates "
                f"{yellow}{str(sorted((pair[0][0], pair[1][0])))[1:-1]}{endc}, "
                f"(only one possible stone left)")
          done.append(stone)
          g[x] = g[y] = step
          step -= 1
          stop = 0
      
      
      # if n fields only allow for n stones we have a group
      def look_for_groups():
        global stop
        for n in range(2, 5):
          for group in findGroups(n, n, list(stones_per_coord.items())):
            # skip for adjacent fields 
            a1 = any(x[0] == y[0] and abs(x[1] - y[1]) == 1 
                     for x in group[1] for y in group[1])
            if a1: continue
            a2 = any(x[1] == y[1] and abs(x[0] - y[0]) == 1 
                     for x in group[1] for y in group[1])
            if a2: continue
      
            for d in group[0]:
              # get stone number
              tup = tuple(int(x) for x in d)
              for c in coords_per_stone[tup]:
                # skip coordinates in our group 
                if len(set(c) & set(group[1])) > 0: continue
                
                tup2 = tuple(c)
                if g[gnum(tup2[0][0], tup2[0][1])] < 0: continue
                if g[gnum(tup2[1][0], tup2[1][1])] < 0: continue
                if tup2 in ex: continue
                print(f"stone at {yellow}{str(tup2)[1:-1]}{endc} cannot be "
                      f"{list(tup)}, group ({', '.join(group[0])}) "
                      f"exists at coordinates {yellow}{str(group[1])[1:-1]}{endc}")
                ex[tup2] = list(tup)
                stop = 0
          if stop == 0: return    # skip the bigger groups
      
      # pick <k> elements from list <li> so that all picked elements use <n> values
      def findGroups(n, k, li, s=set(), f=[]):
        if k == 0:
          yield (list(s), f)
        else:
          for i in range(len(li)):
            # get set of stone numbers
            vals = domnums(li[i][1])
            if len(s | vals) <= n:
              yield from findGroups(n, k - 1, li[i+1:], s | vals, f + [li[i][0]])  
      
      def print_matrix(mat, orig):
        # https://en.wikipedia.org/wiki/Box-drawing_character
        global g_save
        nw = '\u250c'    #   N
        ne = '\u2510'    # W   E
        ho = '\u2500'    #   S
        ve = '\u2502' 
        sw = '\u2514' 
        se = '\u2518'
        
        numlist = "".join(["    " + str(i) for i in range(C)]) + "   "
        print("\n\x1b[6;30;42m" + numlist + "\x1b[0m")
        for i in range(R):
          top = ""
          txt = ""
          bot = ""
          prt = 0
          for j in range(C):
            v = mat[i*C + j]
            # original value
            ov = orig[i*C + j] if orig[i*C + j] > -1 else " "
            
            cb = green if v != g_save[i*C + j] else ""
            ce = endc if v != g_save[i*C + j] else ""
            
            o = orientation(mat, i*C + j, v)
            
            if o == 'N': 
              top += nw+ho+ho+ho+ne
              txt += ve+cb+ " " + str(ov) + " " + ce+ve
              bot += ve+ "   " + ve
            if o == 'S': 
              top += ve+ "   " + ve
              txt += ve+cb+ " " + str(ov) + " " + ce+ve
              bot += sw+ho+ho+ho+se  
            if o == 'W':   # already handle East as well
              top += nw+ho+ho+ho+ho+ho+ho+ho+ho+ne
              txt += ve+cb+ " " + str(ov) + "    " + str(orig[i*C + j + 1]) + " " + ce+ve
              bot += sw+ho+ho+ho+ho+ho+ho+ho+ho+se
            if o == '':  
              top += "     "
              txt += "  " + str(ov) + "  " 
              bot += "     "
          print("\x1b[6;30;42m \x1b[0m " + top + "\x1b[6;30;42m \x1b[0m")  
          print("\x1b[6;30;42m" + str(i) + "\x1b[0m " + txt + "\x1b[6;30;42m" + str(i) + "\x1b[0m")
          print("\x1b[6;30;42m \x1b[0m " + bot + "\x1b[6;30;42m \x1b[0m")  
        print("\x1b[6;30;42m" + numlist + "\x1b[0m")  
          
        g_save = list(g)
          
      def orientation(mat, n, v):
        if v > -1: return ""
        
        # (x, y) are the coordinates in the 2 dimensional matrix
        (x, y) = divmod(n, C) 
        # horizontally
        if y < C - 1 and mat[n + 1] == v: return "W"
        if y > 0     and mat[n - 1] == v: return "E"
        # vertically
        if x < R - 1 and mat[n + C] == v: return "N"
        if x > 0     and mat[n - C] == v: return "S"
        
        return ""
                     
       
      coords_per_stone = defaultdict(list)
      
      stop = 0
      step = -1
      green = "\033[92m"    
      yellow = "\033[93m"   
      endc = "\033[0m"    # end color
       
       
      done = []
      ex = defaultdict(list)
      
      os.system('cls||clear')
      
      g_orig = list(g)
      g_save = list(g)
      
      for loop in range(222):
        stop = 1
        prevstep = step
        
        stones_per_coord = collect_stones_per_coord()
        
        one_stone_left()
        
        if step == prevstep:
          collect_coords_per_stone()    
          analyze_coords_per_stone()
      
        if step < prevstep:
          print_matrix(g, g_orig) 
          if all(y < 0 for y in g):
            exit(0)
          letter = input('Press any key: ')
          os.system('cls||clear')
          print()
          continue
      
        # collect again as some possible placements may have been ruled out
        stones_per_coord = collect_stones_per_coord()
        look_for_groups()
      
        if stop: break
      
      
      print("----------------------- NOT SOLVED -----------------------------")
      
      print_matrix(g, g_orig) 
      

      Like

  • Unknown's avatar

    Jim Randell 9:45 am on 13 December 2020 Permalink | Reply
    Tags:   

    Teaser 1984: Which whatsit is which? 

    From The Sunday Times, 24th September 2000 [link]

    I have received three boxes of whatsits. They all look alike but those in one of the boxes weigh 6 grams each, those in another box all weigh 7 grams each, and all those in the remaining box weigh 8 grams each.

    I do not know which box is which but I have some scales which enable me to weigh accurately anything up to 30 grams. I with to use the scales to determine which whatsit is which.

    How can I do this with just one weighing?

    The text of this puzzle is taken from the book Brainteasers (2002), the wording differs only slightly from the puzzle originally published in the newspaper.

    The following note was added to the puzzle in the book:

    When this Teaser appeared in The Sunday Times, instead of saying “some scales” it said “a balance”. This implied to some readers that you could place whatsits on either side of the balance — which opens up all sorts of alternative approaches which you might like to think about.

    There are now 400 Teaser puzzles available on the site.

    [teaser1984]

     
    • Jim Randell's avatar

      Jim Randell 9:45 am on 13 December 2020 Permalink | Reply

      Evidently we need to find some selection from the three types of whatsit, such that from the value of their combined weight we can determine the weights of the individual types.

      If the scale did not have such a low maximum weight we could weigh 100 type A whatsits, 10 type B whatsits, and 1 type C whatsit, to get a reading of ABC, which would tell us immediately the weights of each type. (For example, if the total weight was 768g, we would know A = 7g, B = 6g, C = 8g).

      We first note that if we can determine the weights for two of the types, then the third types weight must be the remaining value. (Equivalently if the selection (a, b, c) determines the weights, so does selection (0, b − a, c − a) where a is the smallest count in the selection).

      So we need to find a pair of small numbers (as 6 or more of the lightest whatsits will give an error on the scales), that give a different outcome for each possible choice of whatsits.

      This Python program runs in 45ms.

      Run: [ @repl.it ]

      from enigma import (group, subsets, printf)
      
      # display for a weight of x
      weigh = lambda x: ("??" if x > 30 else str(x))
      
      # check the qunatities <ns> of weights <ws> are viable
      def check(ns, ws):
        # collect total weight
        d = group(subsets(ws, size=len, select="P"), by=(lambda ws: weigh(sum(n * w for (n, w) in zip(ns, ws)))))
        # is this a viable set?
        return (d if all(len(v) < 2 for v in d.values()) else None)
      
      # consider (a, b) pairs, where a + b < 6
      for (a, b) in subsets((1, 2, 3, 4), size=2):
        if a + b > 5: continue
        ns = (0, a, b)
        d = check(ns, (6, 7, 8))
        if d:
          # output solution
          printf("ns = {ns}")
          for k in sorted(d.keys()):
            printf("  {k:2s} -> {v}", v=d[k])
          printf()
      

      Solution: You should choose one whatsit from one of the boxes, and three whatsits from another box.

      The combined weight indicates what the weight of each type of whatsit is:

      25g → (0 = 8g, 1 = 7g, 3 = 6g)
      26g → (0 = 7g, 1 = 8g, 3 = 6g)
      27g → (0 = 8g, 1 = 6g, 3 = 7g)
      29g → (0 = 6g, 1 = 8g, 3 = 7g)
      30g → (0 = 7g, 1 = 6g, 3 = 8g)
      <error> → (0 = 6g, 1 = 7g, 3 = 8g) (actual weight = 31g)

      Like

    • Frits's avatar

      Frits 12:01 pm on 13 December 2020 Permalink | Reply

      from enigma import SubstitutedExpression, group
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [# pick not more than 5 whatsits from one or two boxes
         "min(X, Y, Z) == 0 and sum([X, Y, Z]) < 6",
         
         # don't allow all whatits to be picked from one box only
         "max(X, Y, Z) != sum([X, Y, Z])"
        ],
        answer="(X, Y, Z), X*6 + Y*7 + Z*8",
        d2i=dict([(k, "XYZ") for k in range(5,10)]),
        distinct="",
        verbose=0)   
      
      # collect weighing results
      res = [y for _, y in p.solve()]
      
      # group items based on X,Y,Z combinations    
      grp = group(res, by=(lambda a: "".join(str(x) for x in sorted(a[0]))))
      
      for g, vs in grp.items(): 
        # there should be 6 different weighing results in order to determine 
        # which whatsit is which 
        if (len(vs)) != 6: continue
        
        # group data by sum of weights
        grp2 = group(vs, by=(lambda a: a[1]))
        
        morethan30 = [1 for x in grp2.items() if x[0] > 30]
        if (len(morethan30) > 1): continue 
        
        ambiguous = [1 for x in grp2.items() if len(x[1]) > 1]
        if len(ambiguous) > 0: continue
        
        print("Solution", ", ".join(g), "\nweighings: ", vs)
      

      Like

      • Frits's avatar

        Frits 12:17 pm on 13 December 2020 Permalink | Reply

        I could have used “[X, Y, Z].count(0) == 1” but somehow count() is below my radar (probably because I have read that count() is/was quite expensive).

        Like

  • Unknown's avatar

    Jim Randell 4:30 pm on 11 December 2020 Permalink | Reply
    Tags:   

    Teaser 3038: Progressive raffle 

    From The Sunday Times, 13th December 2020 [link] [link]

    George and Martha were participating in the local village raffle. 1000 tickets were sold, numbered normally from 1 to 1000, and they bought five each. George noticed that the lowest-numbered of his tickets was a single digit, then each subsequent number was the same multiple of the previous number, e.g. (7, 21, 63, 189, 567). Martha’s lowest number was also a single digit, but her numbers proceeded with a constant difference, e.g. (6, 23, 40, 57, 74). Each added together all their numbers and found the same sum. Furthermore, the total of all the digits in their ten numbers was a perfect square.

    What was the highest numbered of the ten tickets?

    [teaser3038]

     
    • Jim Randell's avatar

      Jim Randell 4:52 pm on 11 December 2020 Permalink | Reply

      If the sum of the 5 terms of the geometric progression is t, and this is also the sum of the 5 term arithmetic progression (a, a + d, a + 2d, a + 3d, a + 4d), then we have:

      t = 5(a + 2d)

      So the sum must be a multiple of 5.

      The following Python program runs in 44ms.

      Run: [ @repl.it ]

      from enigma import (irange, div, union, nsplit, is_square, printf)
      
      # generate geometric progressions with k elements
      # n = max value for 1st element, N = max value for all elements
      def geom(k, n=9, N=1000):
        # first element
        for a in irange(1, n):
          # second element is larger
          for b in irange(a + 1, N):
            # calculate remaining elements
            (gs, rs, x) = ([a, b], 0, b)
            while len(gs) < k:
              (x, r) = divmod(x * b, a)
              gs.append(x)
              rs += r
            if x > N: break
            if rs == 0:
              yield tuple(gs)
      
      # digit sum of a sequence
      dsums = lambda ns: sum(nsplit(n, fn=sum) for n in ns)
      
      # consider geometric progressions for G
      for gs in geom(5):
        x = div(sum(gs), 5)
        if x is None: continue
        
        # arithmetic progressions for M, with the same sum
        # and starting with a single digit
        for a in irange(1, 9):
          d = div(x - a, 2)
          if d is None: continue
          ms = tuple(irange(a, a + 4 * d, step=d))
          ns = union([gs, ms])
          if len(ns) != 10: continue
      
          # the sum of the digits in all the numbers is a perfect square
          r = is_square(dsums(ns))
          if r is None: continue
      
          m = max(gs[-1], ms[-1])
          printf("max = {m}; gs = {gs}, ms = {ms}; sum = {t}, dsum = {r}^2", t=5 * x)
      

      Solution: The highest numbered ticket is 80.

      Note that the [[ geom() ]] function will generate all possible geometric progressions, including those that have a non-integer common ratio, (e.g. for a 4 element progression we could have (8, 28, 48, 343)), but for a 5 element progression we would need the initial term to have a factor that is some (non-unity) integer raised to the 4th power, and the smallest possible value that would allow this is 2^4 = 16, which is not possible if the initial term is a single digit. So for this puzzle the solution can be found by considering only those progressions with an integer common ratio (which is probably what the puzzle wanted, but it could have said “integer multiple” to be completely unambiguous).

      Like

    • GeoffR's avatar

      GeoffR 7:48 pm on 11 December 2020 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % terms of arithmetic series
      var 1..9: A1; var 2..100: A2;var 2..150: A3;
      var 2..250: A4; var 2..500: A5;
      
      % terms of geometric series
      var 1..9: G1; var 2..100: G2;var 2..150: G3;
      var 2..250: G4; var 2..500: G5;
      
      % geometric ratio and arithmetic difference
      var 2..9:Gratio; 
      var 2..200:Adiff;
      
      %  total sum of  geometric and arithmetic series 
      var 2..500: Gsum; 
      var 2..500: Asum;
      
      % maximum raffle ticket number
      var 2..999: max_num;  
      
      constraint A2 == A1 + Adiff;
      constraint A3 == A2 + Adiff;
      constraint A4 == A3 + Adiff;
      constraint A5 == A4 + Adiff;
      
      constraint Asum = A1 + A2 + A3 + A4 + A5;
      
      constraint G2 == G1*Gratio;
      constraint G3 == G2*Gratio;
      constraint G4 == G3*Gratio;
      constraint G5 == G4*Gratio;
      
      constraint Gsum = G1 + G2 + G3 + G4 + G5;
      
      constraint Gsum == Asum;
      
      constraint all_different ([A1,A2,A3,A4,A5,G1,G2,G3,G4,G5]);
      
      constraint max_num = max({A1,A2,A3,A4,A5,G1,G2,G3,G4,G5});
      
      solve satisfy;
      
      output[ "Geometric Series: " ++ show([G1,G2,G3,G4,G5])  
      ++ "\n" ++ "Arithmetic Series = " ++ show([A1,A2,A3,A4,A5]) 
      ++ "\n" ++ "Max ticket number = " ++ show(max_num) ];
      

      This programme produces three solutions, all with the same maximum value.
      In only one of the solutions do the digits add to a perfect square.

      Like

    • Jim Randell's avatar

      Jim Randell 8:05 pm on 11 December 2020 Permalink | Reply

      @Geoff: There’s only one copy of each ticket, so both George and Martha’s sets of numbers are fully determined. (Even though we are only asked for the highest numbered ticket).

      Like

    • Frits's avatar

      Frits 2:30 pm on 12 December 2020 Permalink | Reply

      for k in range(2, 6):
        print(sum(k**i for i in range(5)))
      

      The result of this piece of code are all numbers ending on a 1. This limits George’s lowest-numbered ticket to one number.

      Like

    • Frits's avatar

      Frits 7:57 pm on 12 December 2020 Permalink | Reply

      The generated code can be seen with option verbose=256.

      from enigma import SubstitutedExpression, is_prime, is_square, \
                         seq_all_different
      
      # Formula
      # G * (1 + K + K^2 + K^3 + K^4) == 5 * (M + 2*D) 
      
      # (1 + K + K^2 + K^3 + K^4) equals (K^5 - 1) / (K - 1) 
      # (idea Brian Gladman)
      
      # sum the digits of the numbers in a sequence
      dsums = lambda seq: sum(sum(int(x) for x in str(s)) for s in seq)
      
      # domain lists
      dlist = list(range(3))  # d < 250
      elist = list(range(10))
      flist = list(range(10))
      glist = list(range(1, 10))
      klist = []
      mlist = list(range(1, 10))
      
      lastdigit = set()           # last digit of the total of 5 tickets
      # K^4 may not be higher than 1000, so K < 6
      for k in range(2, 6):
        t = sum(k**i for i in range(5))
        klist.append(k)
        lastdigit.add(t % 10)
        
      lastdigit = list(lastdigit)  
      
      if 5 not in lastdigit:
        # George's lowest ticket must be 5 as total is a multiple of 5
        glist = [5]
        
      if len(lastdigit) == 1:
        # Martha's tickets sum to 5 * (M + 2*D) 
        if lastdigit[0] % 2 == 1:
          # Martha's lowest ticket must be odd
          mlist = [1, 3, 5, 7, 9]
        else:
          # Martha's lowest ticket must be even
          mlist =[2, 4, 6, 8]
        
      if len(glist) == 1:
        # George's highest ticket may not be higher than 1000
        klist = [x for i, x in enumerate(klist, start=2) 
                               if i**4 * glist[0] <= 1000]
        # calculate highest sum of 5 tickets                       
        t = sum(max(klist)**i for i in range(5)) * glist[0]
        
        # Martha's highest ticket may not be higher than (t/5 - M) / 2
        dlist = [x for x in dlist if x <= (t / 10) // 100]
        if dlist == [0]:
          elist = [x for x in elist if x <= (t // 10) // 10]
          
        mlist = [x for x in mlist if x != glist[0]]
        
      # build dictionary for invalid digits 
      vars = "DEFGKM"
      invalid = "dict("
      for i in range(10):
        txt = ""
        for j, li in enumerate([dlist, elist, flist, glist, klist, mlist]):
          if i not in li:
            txt += vars[j]
        invalid += "[(" + str(i) + ", '" + txt + "')] + "
      
      invalid = invalid[:-3] + ")"  
      
      
      exprs = []
      
      # George's and Martha's sum was the same
      exprs.append("G * (K ** 5 - 1) // (K - 1) == 5 * (M + 2 * DEF)")
      # all ticket numbers have to be different
      exprs.append("seq_all_different([G, G * K, G * K**2, G * K**3, G * K**4, \
                                     M, M + DEF, M + 2*DEF, M + 3*DEF, M + 4*DEF])")
      # total of all the digits in the ten numbers was a perfect square                               
      exprs.append("is_square(dsums([G, G * K, G * K**2, G * K**3, G * K**4, \
                                     M, M + DEF, M + 2*DEF, M + 3*DEF, M + 4*DEF]))")    
                                     
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        exprs,
        answer="(G, G * K, G * K**2, G * K**3, G * K**4), \
                (M, M + DEF, M + 2*DEF, M + 3*DEF, M + 4*DEF), 5 * (M + 2 * DEF)",
        d2i=eval(invalid),
        env=dict(dsums=dsums),
        distinct="GM",
        verbose=0)   
      
      # Print answers 
      for (_, ans) in p.solve():
          print(f"{ans}")
      

      Like

    • Tony Brooke-Taylor's avatar

      Tony Brooke-Taylor 9:10 am on 14 December 2020 Permalink | Reply

      My first solution generated the series explicitly and then applied the tests to each series, but then I realised we could equate the expressions for the sums of each series to reduce the sets of parameters we need to test. My second attempt was similar to below but instead of constraining the sum to a multiple of 5 I initially constrained my ‘b’ parameter to an integer, which I think is mathematically equivalent but came inside another loop so was less efficient.

      #Generator function to create possible combinations of parameters for George and Martha
      def core_parameters():
        #George's tickets form the geometric progression x.(y^0, y^1, y^2, y^3, y^4)
        #Martha's tickets form the arithmetic progression (a+b*0, a+b*1, a+b*2, a+b*3, a+b*4)
      
        for x in range(1,10): #we are told that George's first ticket has a single-digit value
          max_y = int((1000/x)**(0.25)//1)+1 #defined by the maximum possible value for George's highest-value ticket
          for y in range(2,max_y): #y=1 not possible because this would give all George's tickets the same value
      
            sum_values = x*(1-y**5)/(1-y) #sum of finite geometric progression
            #sum_values = a*5 + b*10      #sum of finite arithmetic progression
            #=> b = (sum_values - a*5)/10 = sum_values/10 - a/2
            if sum_values%5 == 0:      #equality also requires that the sum is a multiple of 5
      
              for a in range(1,10): #we are told that Martha's first ticket has a single-digit value
                if a != x:          #Martha's first ticket cannot have the same value as George's
                  b = sum_values/10 - a/2
                  yield x, y, a, b
      
      #Function to sum all digits in an integer
      def digit_sum(num):
        s = 0
        for dig in str(num):
          s = s + int(dig)
        return s  
      
      #Control program
      
      for first_george_ticket, george_multiple, first_martha_ticket, martha_multiple in core_parameters():
        george_tix = [first_george_ticket*george_multiple**n for n in range(5)]
        martha_tix = [int(first_martha_ticket+martha_multiple*m) for m in range(5)]
      
        #they can't both have the same ticket and we are told that the sum of all digits is a square
        if set(martha_tix).intersection(george_tix) == set() and \
        ((sum([digit_sum(j) for j in george_tix]) + sum([digit_sum(k) for k in martha_tix]))**(1/2))%1 == 0: 
        
          print("George:", george_tix)
          print("Martha:", martha_tix)
          print("Highest-valued ticket:",max(george_tix + martha_tix))     
          break
      

      Like

  • Unknown's avatar

    Jim Randell 9:23 am on 10 December 2020 Permalink | Reply
    Tags:   

    Teaser 1966: Square of primes 

    From The Sunday Times, 21st May 2000 [link]

    If you place a digit in each of the eight unshaded boxes, with no zeros in the corners, then you can read off various three-figure numbers along the sides of the square, four in a clockwise direction and four anticlockwise.

    Place eight different digits in those boxes with the largest of the eight in the top right-hand corner so that, of the eight resulting three-figure numbers, seven are prime and the other (an anticlockwise one) is a square.

    Fill in the grid.

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

    [teaser1966]

     
    • Jim Randell's avatar

      Jim Randell 9:24 am on 10 December 2020 Permalink | Reply

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

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

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      #  A B C
      #  D   E
      #  F G H
      
      SubstitutedExpression
      
      # no zeros in the corners
      --invalid="0,ACFH"
      
      # C is the largest number
      "C > max(A, B, D, E, F, G, H)"
      
      # all the clockwise numbers are prime
      "is_prime(ABC)"
      "is_prime(CEH)"
      "is_prime(HGF)"
      "is_prime(FDA)"
      
      # three of the anticlockwise numbers are prime
      "icount((ADF, FGH, HEC, CBA), is_prime) = 3"
      
      # and the other one is square
      "icount((ADF, FGH, HEC, CBA), is_square) = 1"
      
      # answer grid
      --answer="((A, B, C), (D, E), (F, G, H))"
      

      Solution: The completed grid looks like this:

      Like

      • Frits's avatar

        Frits 2:42 pm on 10 December 2020 Permalink | Reply

        @Jim,

        A further optimization would be to limit A, F, and H to {1, 3, 5, 7} and C to {7, 9}.

        Like

    • Frits's avatar

      Frits 10:54 am on 10 December 2020 Permalink | Reply

      A solution with miniZinc.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      %  A B C
      %  D   E
      %  F G H
      
      % no zeros in the corners 
      var 1..9:A; var 0..9:B; var 1..9:C; 
      var 0..9:D; var 0..9:E; 
      var 1..9:F; var 0..9:G; var 1..9:H;
      
      % 3-digit numbers clockwise
      var 100..999: ABC = 100*A + 10*B + C;
      var 100..999: CEH = 100*C + 10*E + H;
      var 100..999: HGF = 100*H + 10*G + F;
      var 100..999: FDA = 100*F + 10*D + A;
      
      % 3-digit numbers anticlockwise
      var 100..999: CBA = 100*C + 10*B + A;
      var 100..999: HEC = 100*H + 10*E + C;
      var 100..999: FGH = 100*F + 10*G + H;
      var 100..999: ADF = 100*A + 10*D + F;
      
      constraint all_different([A, B, C, D, E, F, G, H]);
      
      predicate is_prime(var int: x) = 
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
      ((i < x) -> (x mod i > 0));
       
      predicate is_square(var int: y) = exists(z in 1..ceil(sqrt(int2float(ub(y)))))
       (z*z = y );
       
      % C is the largest number
      constraint C > max([A, B, D, E, F, G, H]);
      
      % all the clockwise numbers are prime
      constraint is_prime(ABC) /\ is_prime(CEH)
      /\ is_prime(HGF) /\ is_prime(FDA);
      
      % three of the anticlockwise numbers are prime
      constraint (is_prime(CBA) /\ is_prime(HEC)/\ is_prime(FGH))
      \/ (is_prime(CBA) /\ is_prime(HEC)/\ is_prime(ADF)) 
      \/ (is_prime(CBA) /\ is_prime(FGH) /\ is_prime(ADF))
      \/ (is_prime(HEC) /\ is_prime(FGH) /\ is_prime(ADF));
      
      % and the other one is square
      constraint is_square(CBA) \/ is_square(HEC)
      \/ is_square(FGH) \/ is_square(ADF);
       
      solve satisfy;
       
      output [ show(ABC) ++ "\n" ++ show(D) ++ " " ++ show(E) ++ "\n" ++ show(FGH) ];
      

      Like

    • GeoffR's avatar

      GeoffR 9:44 am on 11 December 2020 Permalink | Reply

      A solution in Python. formatted to PEP8:

      
      import time
      start = time.time()
      
      from itertools import permutations
      from enigma import is_prime
      
      digits = set(range(10))
      
      def is_sq(n):
        a = 2
        while a * a < n:
          a += 1
        return a * a == n
      
      for P1 in permutations(digits, 4):
        A, F, H, C = P1
        if C not in (7, 9):
          continue
        if 0 in (A, F, H, C):
          continue
        Q1 = digits.difference(P1)
        for P2 in permutations(Q1, 4):
          B, D, E, G = P2
          if C > max(A, B, D, E, F, G, H):
      
            # Four clockwise primes
            ABC, CEH = 100 * A + 10 * B + C, 100 * C + 10 * E + H
            HGF, FDA = 100 * H + 10 * G + F, 100 * F + 10 * D + A
            if sum([is_prime(ABC), is_prime(CEH),
                    is_prime(HGF), is_prime(FDA)]) == 4:
              ADF, FGH = 100 * A + 10 * D + F, 100 * F + 10 * G + H
              HEC, CBA = 100 * H + 10 * E + C, 100 * C + 10 * B + A
      
              # Three anti-clockwise primes
              if sum([is_prime(ADF), is_prime(FGH),
                      is_prime(HEC), is_prime(CBA)]) == 3:
      
                # One anti-clockwise square
                if sum([is_sq(ADF), is_sq(FGH),
                        is_sq(HEC), is_sq(CBA)]) == 1:
                  print(f"{A}{B}{C}")
                  print(f"{D} {E}")
                  print(f"{F}{G}{H}")
                  print(time.time() - start) # 0.515 sec
      
      # 389
      # 6 0
      # 157
      
      
      

      A solution in MiniZinc, first part similar to previous MiniZinc solution, the last part using a different approach to find the seven primes and the one square number:

      
      % A Solution in MiniZinc
      include "globals.mzn";
      %  A B C
      %  D   E
      %  F G H
       
      var 0..9:A; var 0..9:B; var 0..9:C; 
      var 0..9:D; var 0..9:E; var 0..9:F; 
      var 0..9:G; var 0..9:H;
      
      constraint A > 0 /\ C > 0 /\ H > 0 /\ F > 0;
      constraint all_different([A, B, C, D, E, F, G, H]);
       
      % Four 3-digit numbers clockwise
      var 100..999: ABC = 100*A + 10*B + C;
      var 100..999: CEH = 100*C + 10*E + H;
      var 100..999: HGF = 100*H + 10*G + F;
      var 100..999: FDA = 100*F + 10*D + A;
       
      % Four 3-digit numbers anti-clockwise
      var 100..999: CBA = 100*C + 10*B + A;
      var 100..999: HEC = 100*H + 10*E + C;
      var 100..999: FGH = 100*F + 10*G + H;
      var 100..999: ADF = 100*A + 10*D + F;
       
      set of int: sq3 = {n*n | n in 10..31}; 
       
      % Hakank's prime predicate
      predicate is_prime(var int: x) =
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
      ((i < x) -> (x mod i > 0));
       
      % C is the largest number
      constraint C > max([A, B, D, E, F, G, H]);
      
      % four clockwise prime numbers
      constraint sum([is_prime(ABC), is_prime(CEH), is_prime(HGF),
       is_prime(FDA)]) == 4;
       
      % three anti-clockwise prime numbers
      constraint sum([is_prime(CBA), is_prime(HEC), is_prime(FGH),
      is_prime(ADF)]) == 3;
      
      % one anti-clockwise square
      constraint sum([CBA in sq3, HEC in sq3, FGH in sq3,
      ADF in sq3]) == 1;
      
      solve satisfy;
        
      output ["Completed Grid: " ++ "\n"  ++ 
      show(ABC) ++ "\n" ++ 
      show(D) ++ " " ++ show(E) ++ "\n" ++ show(FGH) ];
      
      % Completed Grid: 
      % 389
      % 6 0
      % 157
      % ----------
      % ==========
      
      
      
      

      Like

    • Frits's avatar

      Frits 2:05 pm on 12 December 2020 Permalink | Reply

      Further analysis leads to C = 9 and square 361.

      from enigma import SubstitutedExpression
      
      #  A B C
      #  D   E
      #  F G H
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
        # C = 9
        # All corner numbers have to be odd and can't be number 5"
        # (otherwise somewhere a number xx5 is not prime and has to be square.
        #  xx5 is either 225 or 625 but their 1st digit is not odd)
         
        # all the clockwise numbers are prime
        "is_prime(10*AB + 9)",  # ABC
        "is_prime(900 + EH)",   # CEH
        "is_prime(HGF)",
        "is_prime(FDA)",
         
        # three of the anticlockwise numbers are prime
        "icount((ADF, FGH, 10*HE + 9, 900 + BA), is_prime) = 3",
         
        # and the other one is square
        "icount((ADF, FGH, 10*HE + 9, 900 + BA), is_square) = 1",
       
        ],
        answer="((A, B, 9), (D, E), (F, G, H))",
        digits=range(0, 9),
        d2i=dict([(k, "AFH") for k in {0, 2, 4, 5, 6, 8}] +
                 [(k, "BEDG") for k in {1, 3, 7}]),
        distinct="ABDEFGH",
        verbose=0)   
      
      # Print answers 
      for (_, ans) in p.solve():
          print(f"{ans}")
      
      # ((3, 8, 9), (6, 0), (1, 5, 7))
      

      Only one square is possible:

      from enigma import is_prime
      
      alldiff = lambda seq: len(seq) == len(set(seq))
      
      sqs = []
      # check 3-digit squares
      for i in range(11, 32):
        i2 = i * i
        # digits in square must all be different 
        # and number must start/end with an odd digit
        if not(alldiff(str(i2)) and i2 % 2 == 1 and (i2 // 100) % 2 == 1):
          continue
        # reverse square has to be prime
        if not(is_prime(int(str(i2)[::-1]))): continue
        sqs.append(i2)
      
      print("possible squares:")  
      for sq in sqs: 
        print(sq)
      
      # possible squares:
      # 361
      

      Like

  • Unknown's avatar

    Jim Randell 9:31 am on 8 December 2020 Permalink | Reply
    Tags:   

    Brain-Teaser 44: The Omnibombulator 

    From The Sunday Times, 21st January 1962 [link]

    This unusual instrument is operated by selecting one of the four switch positions: A, B, C, D, and turning the power on. The effects are:

    A: The pratching valve glows and the queech obulates;
    B: The queech obulates and the urfer curls up, but the rumption does not get hot;
    C: The sneeveling rod turns clockwise, the pratching valve glows and the queech fails to obulate;
    D: The troglodyser gives off hydrogen but the urfer does not curl up.

    Whenever the pratching valve glows, the rumption gets hot. Unless the sneeveling rod turns clockwise, the queech cannot obulate, but if the sneeveling rod is turning clockwise the troglodyser will not emit hydrogen. If the urfer does not curl up, you may be sure that the rumption is not getting hot.

    In order to get milk chocolate from the machine, you must ensure:

    (a) that the sneeveling rod is turning clockwise AND;
    (b) that if the troglodyser is not emitting hydrogen, the queech is not obulating.

    1. Which switch position would you select to get milk chocolate?

    If, tiring of chocolate, you wish to receive the Third Programme, you must take care:

    (a) that the rumption does not get hot AND;
    (b) either that the urfer doesn’t curl and the queech doesn’t obulate or that the pratching valve glows and the troglodyser fails to emit hydrogen.

    2. Which switch position gives you the Third Programme?

    No setter was given for this puzzle.

    This puzzle crops up in several places on the web. (Although maybe it’s just because it’s easy to search for: “the queech obulates” doesn’t show up in many unrelated pages).

    And it is sometimes claimed it “appeared in a national newspaper in the 1930s” (although the BBC Third Programme was only broadcast from 1946 to 1967 (after which it became BBC Radio 3)), but the wording always seems to be the same as the wording in this puzzle, so it seems likely this is the original source (at least in this format).

    “Omnibombulator” is also the title of a 1995 book by Dick King-Smith.

    [teaser44]

     
    • Jim Randell's avatar

      Jim Randell 9:33 am on 8 December 2020 Permalink | Reply

      Consider the following conditions:

      P = “the pratching valve glows”
      Q = “the queech obulates”
      R = “the rumption gets hot”
      S = “the sneeveling rod turns clockwise”
      T = “the troglodyser gives off hydrogen”
      U = “the urfer curls up”

      Then the positions can be described as:

      A = P ∧ Q
      B = Q ∧ U ∧ ¬R
      C = S ∧ P ∧ ¬Q
      D = T ∧ ¬U

      And we are also given the following constraints:

      P → R
      Q → S
      S → ¬T
      ¬U → ¬R

      And the conditions that produce outcomes we are told about are:

      milk chocolate = S ∧ (¬T → ¬Q)
      third programme = ¬R ∧ ((¬U ∧ ¬Q) ∨ (P ∧ ¬T))

      The following Python program looks at all possible combinations of P, Q, R, S, T, U, and checks that the constraints are not violated, then looks for which positions are operated, and which outcomes occur.

      It runs in 49ms.

      Run: [ @replit ]

      from enigma import (subsets, implies, join, printf)
      
      # consider possible values of the statements
      for (P, Q, R, S, T, U) in subsets((True, False), size=6, select="M"):
      
        # check the constraint hold:
        # P -> R
        if not implies(P, R): continue
        # Q -> S
        if not implies(Q, S): continue
        # S -> not(T)
        if not implies(S, not T): continue
        # not(U) -> not(R) [same as: R -> U]
        if not implies(not U, not R): continue
      
        # which positions are operated?
        ps = list()
        if P and Q: ps.append('A')
        if Q and U and (not R): ps.append('B')
        if S and P and (not Q): ps.append('C')
        if T and (not U): ps.append('D')
      
        # possible outcomes
        ss = list()
        if S and implies(not T, not Q): ss.append('milk chocolate')
        if (not R) and (((not U) and (not Q)) or (P and (not T))): ss.append('third programme')
      
        # output solution
        if ps:
          if not ss: ss = [ "???" ]
          printf("{ps} -> ({ss}) {vs}", ps=join(ps, sep=","), ss=join(ss, sep=", "), vs=[P, Q, R, S, T, U])
      

      Solution: 1. Position C produces milk chocolate; 2. Position D gives you the Third Programme.

      We don’t know what A and B do, but we can describe their affects on the machine:

      A: the pratching valve glows; the queech obulates; the rumption gets hot; the sneeveling rod turns clockwise; the troglodyser does not give off hydrogen; the urfer curls up

      B: the pratching valve does not glow; the queech obulates; the rumption does not get hot; the sneeveling rod turns clockwise; the troglodyser does not give off hydrogen; the urfer curls up

      C: the pratching valve glows; the queech obulates; the rumption gets hot; the sneeveling rod turns clockwise; the troglodyser does not give off hydrogen; the urfer curls up

      D: the pratching valve does not glow; the queech does not obulate; the rumption does not get hot; the sneeveling rod turns anticlockwise; the troglodyser gives off hydrogen; the urfer does not curl up

      Like

    • John Crabtree's avatar

      John Crabtree 4:39 am on 14 December 2020 Permalink | Reply

      Let a positive action be represented by an uppercase letter, and a negative action by a lowercase letter.
      Expressed as Boolean logic where “.” means AND and “+” means OR, the conditions are:
      1. P.R + p = 1
      2. q.s + S.t = 1
      3. r.u + U = 1
      Combining 1 and 3 gives ( P.R + p).(r.u + U) = P.R.U + p.u.r + p.U = 1
      And so (P.R.U + p.r,u + p.U).(q.s + S,t) = 1

      The four switches give:
      A. P.Q = 1 and so P.R.U.Q.S.t = 1
      B. r.U.Q = 1 and so p.r.U.Q.S.t = 1
      C. P.q.S = 1, and so P.R.U.q.S.t = 1, (milk chocolate)
      D. u.T = 1 and so p.r.u.q.s.T = 1, (Third programme)

      Switch C selects milk chocolate. Switch D gets the Third programme.

      A similar technique can also be used in Brain-Teasers 506 and 520.

      Like

  • Unknown's avatar

    Jim Randell 12:28 pm on 6 December 2020 Permalink | Reply
    Tags: by: K. G. Messenger   

    Brain-Teaser 14: Cross-country 

    From The Sunday Times, 4th June 1961 [link]

    In the annual cross-country race between the Harriers and the Greyhounds each team consists of eight men, of whom the first six in each team score points. The first man home scores one point, the second two, the third three, and so on. When these are added together, the team with the lower total wins the match.

    In this year’s match, the Harriers’ captain came in first and as his team followed he totted up the score. When five more Harriers and a number of Greyhounds had arrived, he found that it would be possible still for his team either to lose or to draw or to win, depending on the placings of the two Harriers yet to come.

    The tension was relieved slightly when the seventh Harrier arrived, since now the worst that could happen was a draw. Then, in an exciting finish, the eighth Harrier just beat one of his rivals to gain a win for his site by a single point.

    What were the scores? And what were the placings of the 16 runners assuming that no two runners tied for a place?

    [teaser14]

     
    • Jim Randell's avatar

      Jim Randell 12:28 pm on 6 December 2020 Permalink | Reply

      (See also: Enigma 1073, Enigma 1322, Enigma 1418).

      This Python program runs in 79ms.

      Run: [ @repl.it ]

      from enigma import (defaultdict, subsets, irange, diff, compare, printf)
      
      # record by first 6 H, if it is a win, draw, loss for H
      d6 = defaultdict(set)
      # and by first 7 H
      d7 = defaultdict(set)
      # and if H wins by 1 point
      rs = list()
      
      # calculate the scores, by positions of H runners
      def scores(hs):
        # scores are the sum of the positions of the first 6 runners
        return (sum(hs[:6]), sum(diff(irange(1, 16), hs)[:6]))
      
      # consider the positions of the H runners
      for hs in subsets(irange(2, 16), size=7):
        hs = (1,) + hs
        (H, G) = scores(hs)
      
        # compare scores: -1 = win for H; 0 = draw; +1 = win for G
        x = compare(H, G)
        d6[hs[:6]].add(x)
        d7[hs[:7]].add(x)
        if G == H + 1: rs.append(hs)
      
      # consider possible final outcomes
      for hs in rs:
        # look for situations where after the first 6 H's w/d/l is possible
        if d6[hs[:6]] != { -1, 0, 1 }: continue
        # and after the first 7 H's only w/d is possible
        if d7[hs[:7]] != { -1, 0 }: continue
      
        # output solution
        (H, G) = scores(hs)
        printf("H={H} G={G}; hs={hs}")
      

      Solution: The scores were Harriers = 40, Greyhounds = 41. Harriers took positions (1, 5, 7, 8, 9, 10, 11, 13). Greyhounds took positions (2, 3, 4, 6, 12, 14, 15, 16).

      Like

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
Design a site like this with WordPress.com
Get started