Tagged: by: Victor Bryant Toggle Comment Threads | Keyboard Shortcuts

  • Jim Randell 8:14 am on 16 March 2021 Permalink | Reply
    Tags: by: Victor Bryant,   

    Teaser 2529 

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

    A letter to The Times concerning the inflated costs of projects read:

    When I was a financial controller, I found that multiplying original cost estimates by π used to give an excellent indication of the final outcome.

    Interestingly, I used the same process (using 22/7 as a good approximation for π). On one occasion, the original estimate was a whole number of pounds (less than £100,000), and this method for the probable final outcome gave a number of pounds consisting of exactly the same digits, but in the reverse order.

    What was the original estimate?

    When originally published the amount was given as “less than £10,000”, which was raised to “less than £100,000” in the following issue. But even with this change the puzzle is still open to interpretation.

    [teaser2529]

     
    • Jim Randell 8:15 am on 16 March 2021 Permalink | Reply

      What the puzzle isn’t clear on is what happens to any fractional part of the new estimate. (Which there would always be if you were to multiply by π).

      If we round down (simply ignoring any fractional part) in the result, then we can get a solution to the original puzzle:

      £185 × 22/7 = £581.43 ≈ £581

      And we get the same result if we round to the nearest pound.

      If we round up:

      £29 × 22/7 = £91.14 ≈ £92

      Raising the limit to £100,000 then we get the following additional solutions:

      £22407 × 22/7 = £70422

      Rounding to nearest:

      £30769 × 22/7 = £96702.57 ≈ £96703

      Which we also get if we round up, along with:

      £29429 × 22/7 = £92491.14 ≈ £92492

      So the only way we can get a unique solution with the revised upper limit is to assume that, before rounding, the new estimate was a whole number of pounds, and so no rounding was necessary. In this case only the pair £22407 → £70422 remain as a candidate solution, and this was the required answer.

      This makes a manual solution easier (and a programmed solution a little faster), as we know the original estimate must be a multiple of 7.

      The following Python program lets you play with various rounding methods.

      Run: [ @replit ]

      from enigma import irange, divf, divc, div, nreverse, printf
      
      # the new estimate is the original estimate multiplied by 22/7
      # choose an appropriate function from the following
      #estimate = lambda x: divf(x * 22, 7) # rounded down
      #estimate = lambda x: divc(x * 22, 7) # rounded up
      #estimate = lambda x: divf(x * 44 + 7, 14) # rounded to nearest integer
      estimate = lambda x: div(x * 22, 7) # exact division
      
      # consider the original estimate x
      for x in irange(1, 99999):
        # multiply by 22/7 for new estimate n
        n = estimate(x)
        if n is None or n % 10 == 0: continue
        # new estimate is reverse of the original
        if nreverse(n) == x:
          printf("original {x} -> {n}")
      

      Solution: The original estimate was: £22,407.


      If the estimates had been constrained to be between £100,000 and £1,000,000 then there is a single solution whichever rounding method is chosen:

      £246,477 × 22/7 = £774,642

      Like

    • Frits 1:04 pm on 17 March 2021 Permalink | Reply

      # consider original cost abcde w    
      # 22 * abcde = 7 * edcba 
      
      # 0 < a < 4 as a * 22 / 7 < 10
      # a must be also be even as 22 * abcde is even
      # so a = 2 and 5 < e < 10
      # 22 * 2bcde = 7 * edcb2 --> e is 7 or 2 --> e is 7 
      
      # equation 22 * 2bcd7 = 7 * 7dcb2
      
      # cost 2-digit number: 
      # -- 27 is not divisible by 7
      # cost 3-digit number: 4914 <= 22 * 2b7 <= 5544 so 2 < b < 5 
      # -- no 2b7 is divisible by 7 for 2 < b < 5 
      # cost 4-digit number: 49014 <= 22 * 2bc7 <= 55944 so 1 < b < 6 
      # cost 5-digit number: 490014 <= 22 * 2bcd7 <= 559944 so 1 < b < 6 
      
      # ...d7 * 22 ends on 54 + d * 20 --> ends on o4 where o is an odd digit
      # b = 2 --> ...22 * 7 = ...54, 54 + d * 20 ends on 54 so d = 0 or 5
      # b = 3 --> ...32 * 7 = ...24, wrong
      # b = 4 --> ...42 * 7 = ...94, 54 + d * 20 ends on 94 so d = 2 or 7
      # b = 5 --> ...52 * 7 = ...64, wrong
      
      # b = 2 --> d = 0 or 5,
      # b = 4 --> d = 2 or 7
      
      # 4-digit numbers 2207, 2257, 2427 and 2477 are not not divisible by 7
      
      # divisibility by 11 requires that the difference between 
      # the sum of the the digits in odd positions and 
      # the sum of all the digits in even positions is 0 or divisible by 11
      
      # 22x07, sum even positions = 2  --> (9 + x - 2) % 11 = 0 -- > x = 4
      # 22407 is divisible by 7
      
      # 22x57, sum even positions = 7  --> (9 + x - 7) % 11 = 0 -- > x = 9
      # 22957 is not divisible by 7
      
      # 24x27, sum even positions = 6  --> (9 + x - 6) % 11 = 0 -- > x = 8
      # 24827 is not divisible by 7
      
      # 24x77, sum even positions = 11 --> (9 + x - 11) % 11 = 0 -- > x = 2
      # 24277 is not divisible by 7
           
      # so 22407 * 22/7 = 70422  
      

      Like

    • John Crabtree 1:40 pm on 18 March 2021 Permalink | Reply

      X = abcde, Y = edcba where X * 22 = Y * 7
      and so 2e = 7a mod 10, and so a = 2 and e = 7

      By digital roots, the sum of the digits in X = 0 mod 3. X = Y = 0 mod 3
      X = 0 mod 7. Y = 0 mod 11, and so X = 0 mod 11
      And so X = 231*M, Y = 726*M, and M = 7 mod 10
      Or X = 1617 + 2310*N and Y = 5082 + 7260*N

      By inspection X cannot have 2, 3 or 4 digits
      70,000 < Y < 80,000 and so N = 9 or 10, which is invalid by inspection.
      N = 9 gives X = 22407 and Y = 70422, which is valid.

      If X 6 digits, there are only 14 possible values of N, ie 96 to 109, to check.

      Like

      • Frits 12:12 pm on 19 March 2021 Permalink | Reply

        @John,

        Maybe you used the congruent sign in your analysis and it was replaced by equal signs.
        If so you might try the enclosure of text as mentioned in Teaser 2756.
        If not the analysis is wrong as 0 mod 11 equals 0.

        Please elaborate as I am not an expert in modular arithmetic (I gather X must be a multiple of 3, 7 and 11?).

        Like

        • John Crabtree 4:16 pm on 19 March 2021 Permalink | Reply

          @Frits
          I do not recall the congruence sign from when I was first introduced to modulo arithmetic nearly 50 years ago. I have always used the equals sign (perhaps incorrectly) followed by mod n.
          X = 0 mod 3 means that X is divisible by 3. And so, yes, X is divisible by 3, 7 and 11. As it also ends in 7 the solution space becomes very small. HTH

          Like

    • Hugh Casement 12:25 pm on 19 March 2021 Permalink | Reply

      I meant to post this on St Patrick’s day, before most of the other comments appeared.

      I’m sure that an integer solution is intended, so no rounding is necessary.
      The original estimate must therefore be an integer multiple of 7.
      The result is even, so the original estimate (with its digits in reverse order) must start with 2: any larger value would yield a result with more digits.
      The result is a multiple of 11, so the original estimate (using the same digits) must be too.
      Admittedly, that still means a lot of trial & error if we don’t use a computer.

      22/7 is a lousy approximation to pi! Much better is 355/113, but I think that can work only if the original estimate is allowed to have a leading zero.

      Like

  • Jim Randell 8:35 am on 11 March 2021 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2780: Calendar dice 

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

    I have tried to make a calendar using some dice. To display the month I want to use three dice, with a capital letter on each of the faces to display:

    [J A N] or [F E B] or [M A R] etc.

    I chose the capital letters on the dice to enable me to go as far as possible through the year. Furthermore, it turned out that one particular die contained four vowels.

    (a) What was the last month that I was able to display?
    (b) What were the two other letters on that particular die?

    [teaser2780]

     
    • Jim Randell 8:36 am on 11 March 2021 Permalink | Reply

      In upper case the only symbol that can be used for more than one letter is M/W, but W does not appear in the words we are interested in, so we can consider all the symbols to be unique. (In a standard font anyway).

      This Python program finds sets of dice that can make the maximum number of months, and then looks for sets that have a die with 4 vowels on. It runs in 1.18s.

      Run: [ @repl.it ]

      from enigma import subsets, Accumulator, first, diff, join, printf
      
      vowels = set('AEIOU')
      months = ['JAN', 'FEB', 'MAR', 'APR', 'MAY', 'JUN', 'JUL', 'AUG', 'SEP', 'OCT', 'NOV', 'DEC']
      
      # merge the symbols <ss> to the dice <ds>
      def merge(ds, ss):
        rs = list()
        for (d, s) in zip(ds, ss):
          if s in d:
            rs.append(d)
          elif len(d) == 6:
            return
          else:
            rs.append(d + [s])
        return rs
      
      # add words from <ws> to dice in <ds>
      # return (<dice>, <number-of-words-remaining>)
      def solve(ds, ws):
        # result so far
        yield (ds, len(ws))
        if ws:
          # put letters for the next word on the dice
          for ss in subsets(ws[0], size=len, select="mP"):
            ds_ = merge(ds, ss)
            if ds_:
              yield from solve(ds_, ws[1:])
      
      # start with the first month
      ds0 = list([x] for x in months[0])
      
      # find dice with the fewest remaining words
      r = Accumulator(fn=min, collect=1)
      for (ds, n) in solve(ds0, months[1:]):
        r.accumulate_data(n, ds)
      
      # output result
      printf("months = {ms} [{n} sets of dice]",
        ms=join(first(months, len(months) - r.value), sep=" ", enc="[]"),
        n=len(r.data),
      )
      
      # look for solutions with 4 vowels on one die
      fmt = lambda d: join(d, sep=" ", enc="[]") # format a die
      for ds in r.data:
        ds = sorted(sorted(d) for d in ds)
        # find dice with (exactly) 4 vowels
        vs = list(d for d in ds if len(vowels.intersection(d)) == 4)
        if not vs: continue
        printf("dice = {ds}", ds=join((fmt(d) for d in ds), sep=" "))
        for d in vs:
          printf("-> {d} has 4 vowels; consonants = {c}", d=fmt(d), c=fmt(diff(d, vowels)))
      

      Solution: (a) The last month you would be able to display is OCT. (b) The consonants on the die with 4 vowels are R and Y.

      There are 108 sets of dice that can make JAN .. OCT, but only 4 of them have a die with 4 vowels on:

      [A B L N S T] [A E O R U Y] [C F G J M P]
      [A B C L N S] [A E O R U Y] [F G J M P T]
      [A E O R U Y] [A F L N S T] [B C G J M P]
      [A C F L N S] [A E O R U Y] [B G J M P T]

      In each case the die with 4 vowels is: [A E O U] + [R Y]

      We can see that the vowel I does not occur in any of the words, so the four vowels must be [A E O U], and setting the middle die in our initial set of dice (line 31) to have these 4 symbols on to start with finds just the four sets of dice given above, and runs in 401ms.


      However, if we were to use lower case letters, then there are useful symbols that can be used for more than one letter:

      b / q
      d / p
      n / u

      And by replacing lines 3-4 with:

      vowels = set('aeion')
      months = ['jan', 'feb', 'mar', 'adr', 'may', 'jnn', 'jnl', 'ang', 'sed', 'oct', 'nov', 'dec']
      

      We find there are 10 sets of dice that can make all twelve months. (But none of them have a die containing 4 vowel symbols, so remove line 50 if you want to see them).

      Like

    • Hugh Casement 1:38 pm on 11 March 2021 Permalink | Reply

      If we cheat by using upper-case U turned sideways to make C, will that allow us to make DEC?

      Like

      • Jim Randell 1:51 pm on 11 March 2021 Permalink | Reply

        @Hugh: It doesn’t let us get to DEC (we can’t fit a D in), but it means we don’t need a C to make OCT, so we free up a letter, which can be V, so we can get as far as NOV.

        If we can also use an upside down A to make a V, then we can fit the D in and get to DEC.

        I think there is scope for using specialised fonts that would allow some symbols to serve as multiple letters.

        Like

    • Hugh Casement 5:40 pm on 11 March 2021 Permalink | Reply

      Thanks, Jim. I was going to suggest turning the A upside down, though it’s possibly a worse cheat!

      I’m sure I’ve come across a variant of this puzzle, possibly by Martin Gardner. I have a vague recollection that all the months could be done except AUG which wasn’t needed because it was during the university long vacation.

      Like

      • Jim Randell 8:45 pm on 14 March 2021 Permalink | Reply

        @Hugh: Removing “AUG” from the list in my program finds 6 sets of dice that can make the remaining 11 months.

        Also removing “FEB” has 30 sets of dice that can make the remaining 11 months, and 2 of the sets also have 4 vowels on one die.

        Like

    • Frits 1:54 pm on 12 March 2021 Permalink | Reply

      # place the 4 vowels A, E, O and U on die number 2
      #
      # As either A or U also has to be on die 1 or 3 (in order to form AUG)
      # there are only 18 -5 = 13 spots left for consonants
      
      months = ['JAN', 'FEB', 'MAR', 'APR', 'MAY', 'JUN', 
                'JUL', 'AUG', 'SEP', 'OCT', 'NOV', 'DEC']
      
      s = set()
      for j in range(12):
        lets = "".join([x for x in months[j] if x not in "AEOU"])
        s = s | set(lets)
        print (f"{months[j]}: {len(list(s))} consonants {''.join(s)} ")
      
      # JAN: 2 consonants JN
      # FEB: 4 consonants JNFB
      # MAR: 6 consonants JNFBMR
      # APR: 7 consonants JNFBMRP
      # MAY: 8 consonants JNFBMRPY
      # JUN: 8 consonants JNFBMRPY
      # JUL: 9 consonants JNFBMRPYL
      # AUG: 10 consonants JNFBMRPYLG
      # SEP: 11 consonants JNFBMRPYLGS
      # OCT: 13 consonants JNFBMRPYLGSCT
      # NOV: 14 consonants JNFBMRPYLGSCTV
      # DEC: 15 consonants JNFBMRPYLGSCTVD
      #
      # so NOV and DEC can't be the last month to be displayed
      #
      # Assume last month to be displayed is OCT
      #
      # letter pairs on dice 1 and 3 but not on the same die (no order):
      # v,G + F,B + C,T + S,P (E only on die 2) + J,N (because JUN and JAN)
      # where v is A or U (extra vowel)
      #
      # suppose v = U -> in same group: P and M (APR and MAR), R and Y (MAR and MAY)
      # this is impossible as group 1 and 3 already have 5 candidates
      #
      # suppose v = A 
      # candidates for 2 empty spots on die 2: 
      # NOT: F,B + C,T + S,P + J,N + G + L (as U only on die 2)
      # leaving R, M, Y
      #  -- suppose M and R on die 2: --> we can't form MAR anymore
      #  -- suppose M and Y on die 2: --> we can't form MAY anymore
      #  -- suppose R and Y on die 2: --> no inconsistency
      
      # place A on die 1
      
      # die 1: A  .  .  .  .  .
      # die 2: A  E  O  U  R  Y
      # die 3: .  .  .  .  .  .
      
      # P must be on die 3 (APR) --> S on die 1
      # M must be on die 3 (MAR)
      # G must be on die 3 (AUG)
      # L must be on die 1 (as F,B + C,T + J,N are pairs)
      # J must be on die 3 (as L is on die 1) --> N on die 1
      
      # die 1: A  S  L  N  .  .
      # die 2: A  E  O  U  R  Y
      # die 3: P  M  G  J  .  .
      
      # this leaves 4 ways to place B, F, C and T
      
      for x in ("BF", "FB"):
        for y in ("CT", "TC"):
          print("A S L N", x[0], y[0], end="  -  ")
          print("A  E  O  U  R  Y", end="  -  ")
          print("P  M  G  J", x[1], y[1])
      
      # A S L N B C  -  A  E  O  U  R  Y  -  P  M  G  J F T
      # A S L N B T  -  A  E  O  U  R  Y  -  P  M  G  J F C
      # A S L N F C  -  A  E  O  U  R  Y  -  P  M  G  J B T
      # A S L N F T  -  A  E  O  U  R  Y  -  P  M  G  J B C
      

      Like

    • Hugh Casement 5:45 pm on 12 March 2021 Permalink | Reply

      I still don’t know who published the no-August variant, or where, but I’ve found the solution scribbled in the margin of a book. It’s a wee bit shorter than the proof of Fermat’s last theorem: the three cubes bear the letters
      A B C S U V, D F J M O P, E L N R T Y
      With two further cubes we can make the numbers 01 to 31:
      0 1 2 3 4 5, 0 1 2 6 (which also serves as 9), 7, 8.

      Like

  • Jim Randell 4:34 pm on 5 March 2021 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 3050: Power struggle 

    From The Sunday Times, 7th March 2021 [link]

    Given any number, one can calculate how close it is to a perfect square or how close it is to a power of 2. For example, the number 7 is twice as far from its nearest perfect square as it is from its nearest power of 2. On the other hand, the number 40 is twice as far from its nearest power of 2 as it is from its nearest square.

    I have quite easily found a larger number (odd and less than a million!) for which one of these distances is twice the other.

    What is my number?

    [teaser3050]

     
    • Jim Randell 4:45 pm on 5 March 2021 Permalink | Reply

      A brute force approach in Python can search the solution space in 215ms. If we stop after the first candidate solution is found, then it only takes 72ms.

      Run: [ @repl.it ]

      from enigma import isqrt, irange, printf
      
      # distance to nearest square
      def dist_sq(n):
        x = isqrt(n)
        return min(n - x ** 2, (x + 1) ** 2 - n)
      
      # distance to nearest power of 2
      def dist_p2(n):
        x = n.bit_length()
        return min(2 ** x - n, n - 2 ** (x - 1))
      
      # find solutions
      for n in irange(41, 1000000, step=2):
        d1 = dist_sq(n)
        d2 = dist_p2(n)
        if d1 == 2 * d2 or d2 == 2 * d1:
          printf("{n} -> dist_sq = {d1}, dist_p2 = {d2}")
          break # we only need the first solution
      

      Solution: Your number is 32775.

      There aren’t many odd numbers with this property.

      The first 5 are:

      7
      32775
      134223231
      2147479015
      549756110751

      Like

      • Jim Randell 12:18 pm on 6 March 2021 Permalink | Reply

        Here’s an alternative approach that considers numbers at increasing distances from the sets of “markers”.

        Also we can see that powers of 2 (greater than 1) are all even, and we are looking for an odd number n > 40, so its distance d to a power of 2 must be odd, and its distance to a square must be 2d. This reduces the number of checks we need to make.

        The following Python program runs in 50ms.

        Run: [ @repl.it ]

        # markers less than 1 million
        M = 1000000
        squares = first(powers(0, inf, 2), count=(lambda x: x < M))
        pow2s = first((2 ** i for i in irange(0, inf)), count=(lambda x: x < M))
        
        # generate numbers at a distance <d> from the nearest marker in <ms>
        def dist(ms, d):
          for (ml, m, mr) in tuples(ms, 3):
            n = m - d
            if n - ml > d: yield n
            n = m + d
            if mr - n > d: yield n
        
        # generate odd numbers at twice the distance from
        # a square than from a power of 2
        def solve():
          # consider increasing odd distances to a power of 2
          for d in irange(1, inf, step=2):
            d2 = 2 * d
            # distance d from pow2s, 2d from squares
            for n in intersect([dist(pow2s, d), dist(squares, d2)]):
              printf("[{n} -> dist_p2 = {d}, dist_sq = {d2}]")
              yield n
        
        # find the first odd solution, greater than 40, less than M
        for n in solve():
          if 40 < n < M:
            printf("answer = {n}")
            break
        

        Like

      • Jim Randell 9:30 am on 14 March 2021 Permalink | Reply

        This program finds the 5 odd solutions given above, and larger ones (by default it outputs the first 10 it finds), by examining the two squares surrounding each odd power of 2:

        from enigma import irange, inf, isqrt, div, first, arg, printf
        
        # generate candidate solutions
        def generate():
          # consider increasing odd powers of 2
          for i in irange(3, inf, step=2):
            p = 2 ** i
            # and the square below
            n = isqrt(p)
            # look for candidate solutions
            n2 = n * n
            n21 = n2 + 2 * n + 1
            p2 = 2 * p
            # and check viability
            for x in [div(p2 + n2, 3), p2 - n2]:
              if x and x % 2 == 1 and x - n2 < n21 - x:
                printf("[{x} -> dist_p2 = {dp2}, dist_sq = {dsq}]", dp2=abs(p - x), dsq=x - n2)
                yield x
            for x in [div(p2 + n21, 3), p2 - n21]:
              if x and x % 2 == 1 and n21 - x < x - n2:
                printf("[{x} -> dist_p2 = {dp2}, dist_sq = {dsq}]", dp2=abs(p - x), dsq=n21 - x)
                yield x
        
        # find the first N solutions
        N = arg(10, 0, int)
        first(generate(), N)
        
        % time python3.9 teaser/teaser3050d.py 10
        [7 -> dist_p2 = 1, dist_sq = 2]
        [32775 -> dist_p2 = 7, dist_sq = 14]
        [134223231 -> dist_p2 = 5503, dist_sq = 11006]
        [2147479015 -> dist_p2 = 4633, dist_sq = 9266]
        [549756110751 -> dist_p2 = 296863, dist_sq = 593726]
        [8796091840375 -> dist_p2 = 1181833, dist_sq = 2363666]
        [140737493172567 -> dist_p2 = 4817239, dist_sq = 9634478]
        [2251799795854807 -> dist_p2 = 17830441, dist_sq = 35660882]
        [36028797113301975 -> dist_p2 = 94338007, dist_sq = 188676014]
        [576460752294331351 -> dist_p2 = 9092137, dist_sq = 18184274]
        python3.9 teaser/teaser3050d.py 10  0.03s user 0.01s system 92% cpu 0.048 total
        

        Like

    • Hugh Casement 2:07 pm on 6 March 2021 Permalink | Reply

      I assume that “number” means integer: the setters of these puzzles have never been able to tell the difference.

      The logarithm of n to base 2, q = ln(n) / ln(2). We round to the nearest integer and take 2^q.

      Having written and run a Basic program in about one minute, I decided to look for even numbers.
      There are dozens, starting with 54, 114, 278, 546, 982, 2002, 4182, 8370, …
      The program was ten lines: I never expected Basic to be more compact than Python.

      Like

    • Frits 1:06 pm on 7 March 2021 Permalink | Reply

      A variation of Jim’s second program (more efficient).

      from enigma import first, powers, irange, inf, tuples, intersect, printf, \
                         isqrt
      # markers less than 1 million
      M = 1000000
      squares = first(powers(0, inf, 2), count=(lambda x: x < M))
      pow2s = first((2 ** i for i in irange(0, inf)), count=(lambda x: x < M))
       
      # generate numbers at a distance <d> from the nearest marker in <ms>
      def dist(ms, d):
        for (ml, m, mr) in tuples(ms, 3):
          n = m - d
          if n - ml > d: yield n
          n = m + d
          if mr - n > d: yield n
       
      # generate odd numbers at twice the distance from
      # a square than from a power of 2
      def solve():
        # consider increasing odd distances to a power of 2
        for d in irange(1, inf, step=2):
          d2 = 2 * d
          for n in dist(pow2s, d): 
            # is there a square at distance 2d from n?
            if n - d2 in squares or n + d2 in squares:
              # is it the nearest square?
              x = isqrt(n)
              x2 = x * x
              x2n = x2 + 2 * x + 1
              nearest = x2 if n - x2 < x2n - n else x2n
              if nearest in {n - d2, n + d2}:
                printf("[{n} -> dist_p2 = {d}, dist_sq = {d2}]")
                yield n
      
      # find the first odd solution, greater than 40, less than M
      for n in solve():
        if 40 < n < M:
          printf("answer = {n}")
          break
      

      Like

      • Jim Randell 2:53 pm on 7 March 2021 Permalink | Reply

        @Frits: I thought that a “hybrid” approach of my two programs would probably be faster. Although my second program has an internal runtime of 2.74ms, so I didn’t think it was worth the extra code.

        Interestingly when I timed the code you posted it ran slightly slower than my version (3.03ms). It might be faster the other way around (generating distances from squares and then calculating distances from powers of two), as I would assume that [[ int.bit_length() ]] is probably faster than [[ math.isqrt() ]] (certainly the code in enigma.py for [[ isqrt() ]] starts by calling [[ int.bit_length() ]], and then does more stuff. (Although if [[ math.isqrt() ]] is available it just uses that, which should be implemented by native code).

        Like

        • Frits 5:01 pm on 7 March 2021 Permalink | Reply

          @Jim, I have tested with the Brian Gladman’s Timer function (which uses perf_counter_ns ) doing 200 runs (jra3 is my variation on your jra2 and jra4 a variation on jra2 the other way around (looking at distances from squares and then checking distances from powers of two)).

           
          PyPy:
          
          jra1 1.579 ms
          jra2 2.629 ms
          jra3 146.700 us
          jra4 539.500 us
          
          Python 3.9.0:
          
          jra1 23.978 ms
          jra2 5.238 ms
          jra3 2.547 ms
          jra4 4.525 ms
          

          I would have been surprised in jra4 was faster than jra3 as the distances from squares generates many elements (like 1900).

          Like

          • Jim Randell 12:06 pm on 8 March 2021 Permalink | Reply

            @Frits: I suppose it goes to show that different timing strategies produce different results.

            For a piece of Python code that is only going to be executed once I think that a 3ms internal runtime is perfectly fine. This run time is dwarfed by the amount of additional time the Python interpreter takes getting ready to run it, so in my preferred measure of execution time both the programs give an external runtime of 50ms.

            For code that is going to be executed thousands of times it may be worth shaving a few milliseconds off it, but code that is only executed once I’m not so sure.

            I wanted my programs to show two different approaches. My first program defines functions that calculate the two distances and then compares them. But there are nearly 500,000 candidate numbers, so this could involve a lot of calculation.

            The second program makes a set of markers, and then looks at numbers that are fixed distances from the markers, so it is essentially a searching strategy. In this case the distances involved in the solution aren’t very large, so the searching strategy wins.

            Like

        • Frits 3:05 pm on 8 March 2021 Permalink | Reply

          @Jim,

          Talking about isqrt:

          have you considered using math.sqrt in enigma.py’s isqrt() if math.isqrt is not available (like in an up-to-date PyPy) for numbers under a certain limit? See Brian Gladman’s number_theory.py.

          Like

          • Jim Randell 6:46 pm on 8 March 2021 Permalink | Reply

            My original version of isqrt() used a float square root to provide an initial guess, and then applied Newton’s method until the result settled down to an integer. (See this comment on Enigma 1759).

            But I switched that to a binary technique I found on Wikipedia [ @wikipedia ] which performed better for numbers that overflowed floats.

            But looking at it again it turns out that that was because I was choosing a poor initial guess in the overflow case. It turns out you can do a much better guess using the fact that int.bit_length() behaves roughly like log2().

            So I think I’ll switch back to using Newton’s method for cases where math.isqrt() is not available.

            BTW: For a very fast implementation of isqrt() check out gmpy2.isqrt().

            Like

    • Hugh Casement 1:20 pm on 7 March 2021 Permalink | Reply

      Isn’t this simpler?

      defdbl a - z
      for n = 41.0 to 999999.0 step 2.0
            p = int(log(n)/log(2.0) + 0.5)
            pp = 2.0^p
            dp = abs(pp - n)
            s = int(sqr(n) + 0.5)
            ss = s*s
            ds = abs(ss - n)
            if dp = 2.0*ds or ds = 2.0*dp then print n pp ss
      next n
      

      Turbo Basic has a log2 function, which would have made the third line a bit more compact.
      Of course some expressions could be combined, but at a slight loss of transparency.
      The .0 are not strictly necessary but make sure the numbers are interpreted as floating-point (single-length integers go only to 32767).

      Like

      • Frits 2:00 pm on 7 March 2021 Permalink | Reply

        Hi Hugh,

        Your program suffers from the same problem Erling Torkildsen had at PuzzlingInPython (dp should be 107 iso 149 for n = 363).

        from math import log2
        
        for n in range(41, 1000000, 2):
          #p = int(log2(n) + 0.5)
          p = round(log2(n))
          pp = 2 ** p
          dp = abs(pp - n)
          #s = int(n ** 0.5 + 0.5)
          s = round(n ** 0.5)
          ss = s * s
          ds = abs(ss - n)
          if n == 363:
            print("n =", n, "p =", p, "pp =", pp, "dp =", dp, "ds =", 
                  ds, "s =", s, "ss =", ss)
          if dp == 2 * ds or ds == 2 * dp:
            print(n, pp, ss)
            break
        
        # n = 363 p = 9 pp = 512 dp = 149 ds = 2 s = 19 ss = 361
        

        Like

      • Jim Randell 2:08 pm on 7 March 2021 Permalink | Reply

        @Hugh: (I put your code into [code] ... [/code] tags so it should look better now).

        It is simpler, but it doesn’t calculate accurate values:

        e.g. The nearest power of 2 to 46 is 32, which gives a distance of 14:

        >>> dist_p2(46)
        14
        >>> f = lambda n: abs(2 ** int(log2(n) + 0.5) - n)
        >>> f(46)
        18
        

        You have to go much higher before the calculation of the nearest square breaks down (much more than a million), probably due to exceeding the precision of floating point numbers. (e.g. It fails at 10^37).

        Like

    • Frits 4:52 pm on 9 March 2021 Permalink | Reply

      Looping over the power of 2 entries.

      # suppose p2 (2 ** p) is the power of 2 is the nearest power 
      # let s^2 be the nearest square smaller equal to p2 
      # so that s^2 <= p2 <= (s + 1)^2 
      # example:  484 <= 512 <= 529 with s = 22 and p2 = 2 ** 9       
      
      #          +--- 2s-1 ---+----- 2s + 1 ----+--- 2s + 3 --+  
      #          |            |                 |             |
      #  ---- (s - 1)^2 ---- s^2 --- p2 ---- (s + 1)^2 --- (s + 2)^2 ---
      #
      
      # even power exponents are also squares so ignore them
      for p in range(5, 21, 2):
        p2 = 2 ** p
        s = int(sqrt(p2))
        s2 = s ** 2
       
        # can x be between (s - 1)^2 and s^2 ?
        # then ds is maximal s - 1 and d2 is maximal (s - 1) / 2
        minx = min(p2 - ((s - 1) // 2), s2)
      
        # make sure minx is odd and ... 
        minx = minx + (minx % 2 == 0) 
      
        # ... ds is not a multiple of 4 and 
        minx = minx +  2 * (minx % 4 == 1) 
        
        # if s2 is even then first entries have an odd ds
        if s2 % 2 == 0:
          minx += s - 2
          
        # can x be between (s + 1)^2 and (s + 2)^2 ?
        # then ds is maximal s + 1 and d2 is maximal (s + 1) / 2
        maxx = max(p2 + ((s + 1) // 2), s2 + 2 * s + 1)
        
        # if s2 is odd then last entries have an odd ds
        if s2 % 2 :
          maxx -= s + 1
        
        # consider odd x's so that ds is not a multiple of 4
        for x in range(minx, maxx + 1, 4):
          # determine nearest square             
          y = int(sqrt(x))
          y2 = y ** 2
          ds = min(x - y2, y2 + 2 * y + 1 - x)  
          
          # determine nearest power of 2              
          y2min1 = 2 ** (x.bit_length() - 1)   
          d2 = min(2 * y2min1 - x, x - y2min1)
          
          # distance from x to power of 2 is always odd 
          # so ds = 2 * d2 (and not d2 = 2 * ds)
          if ds == 2 * d2:        
            print(f"number is {x}; distance to power of 2: {d2}; to square: {ds}")
            exit() # we only need the first
      

      Like

  • Jim Randell 8:16 am on 26 January 2021 Permalink | Reply
    Tags: by: Victor Bryant,   

    Teaser 2772: Madam I’m Adam 

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

    Adam noticed that today’s Teaser number was a four-figure palindrome. He told me that he had written down [a] four-figure palindrome and he asked me to guess what it was. I asked for some clues regarding its prime factors and so he told me, in turn, whether his number was divisible by 2, 3, 5, 7, 11, 13, … Only after he had told me whether it was divisible by 13 was it possible to work out his number.

    What was his number?

    When this was originally published “another” was used where I have placed “[a]”, but this makes the puzzle unsolvable. However, as presented above, there is a unique solution.

    [teaser2772]

     
    • Jim Randell 8:17 am on 26 January 2021 Permalink | Reply

      The use of “another” in the puzzle text implies that the palindrome 2772 is excluded from the set of possibilities, but if this is the case the puzzle is not solvable. So instead we just consider that Adam has told the setter that he has written down some 4-digit palindrome (which may be 2772), and the setter has to guess it.

      This Python program considers increasing prime numbers p, and looks for palindromes that can be uniquely identified by knowing if it is divisible by primes up to (and including) p.

      To solve this puzzle we look up to p = 13, but the maximum prime can be specified on the command line. (We have to go to 859 to be sure of determining the palindrome).

      The program runs in 45ms.

      Run: [ @repl.it ]

      from enigma import Primes, irange, filter_unique, diff, join, arg, printf
      
      # max prime
      N = arg(13, 0, int)
      
      # 4-digit palindromes
      palindromes = sorted(1001 * a + 110 * b for a in irange(1, 9) for b in irange(0, 9))
      #palindromes.remove(2772) # puzzle text says 2772 is excluded, but that makes it impossible
      
      # palindromes unique by divisibility of primes, but not unique by shorter sequences
      r = set()
      # consider sequences of primes by increasing length
      ps = list()
      for p in Primes(N + 1):
        ps.append(p)
        # find unique palindromes by this sequence of primes
        s = filter_unique(palindromes, lambda x: tuple(x % p == 0 for p in ps)).unique
        # unique palindromes we haven't seen before
        s = diff(s, r)
        if s:
          printf("{p} -> {s}", s=join(s, sep=", ", enc="()"))
        # update the list of unique palindromes
        r.update(s)
      

      Solution: The number was 6006.


      If 2772 is removed from the set of possible palindromes (by removing the comment from line 8), we see that 8778 would also be uniquely identified by the divisibility values for primes up to 13.

      So although the setter would know the answer (because he knows if the number is divisible by 13 or not), we can’t work it out:

      6006 → 2=Y, 3=Y, 5=N, 7=Y, 11=Y, 13=Y
      8778 → 2=Y, 3=Y, 5=N, 7=Y, 11=Y, 13=N, [17=N, 19=Y]
      2772 → 2=Y, 3=Y, 5=N, 7=Y, 11=Y, 13=N, [17=N, 19=N]

      But, if 2772 is included in the set of possible palindromes, then 8778 and 2772 cannot be distinguished until we are told the answer for divisibility by 19, so the fact that the setter can work out the number at p = 13 means that it must be 6006.

      There are two palindromes that can be distinguished with a shorter sequence of answers:

      5005 → 2=N, 3=N, 5=Y, 7=Y
      5775 → 2=N, 3=Y, 5=Y, 7=Y

      Note that all palindromes are divisible by 11.

      Like

    • Frits 8:08 pm on 26 January 2021 Permalink | Reply

      With fewer modulo calculations.

      from collections import Counter
       
      # max prime
      N = 13
      
      # list of prime numbers
      P = [2, 3, 5, 7, 11, 13]
       
      # 4-digit palindromes
      palindromes = sorted(1001 * a + 110 * b for a in range(1, 10) 
                                              for b in range(0, 10))
      
      # initialize dictionary (divisibility by prime)                                    
      d = {key: [] for key in palindromes}
       
      singles = []
      # consider sequences of primes by increasing length
      for p in P:
        # maintain dictionary (divisibility by prime)   
        for x in palindromes:
          d[x].append(x % p == 0)
         
        c = Counter(map(tuple, d.values()))
        # get combinations unique by divisibility of primes
        # but not unique by shorter sequences
        c2 = [k for k, v in c.items() if v == 1 and 
              all(k[:-i] not in singles for i in range(1, len(k)))]
        
        if len(c2) == 1:
          for x in palindromes:
            if d[x] == list(c2[0]):
              print(f"{p} -> {x}")
              if p != N:
                print("Error: palindrome already known before prime", N)
              exit()  
              
        # add "unique by shorter sequences" to singles
        for x in [k for k, v in c.items() if v == 1]:
          singles.append(x)
      

      Like

  • Jim Randell 4:31 pm on 15 January 2021 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 3043: An odd selection 

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

    I wrote an odd digit in each of the sixteen cells of a four-by-four grid, with no repeated digit in any row or column, and with each odd digit appearing three or more times overall. Then I could read four four-figure numbers across the grid and four four-figure numbers down. I calculated the average of the four across numbers and the larger average of the four down numbers. Each was a whole number consisting entirely of odd digits, and each used an odd number of different odd digits.

    What were those two averages?

    [teaser3043]

     
    • Jim Randell 4:54 pm on 15 January 2021 Permalink | Reply

      Here’s a quick (to write) constructive solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      It runs in 687ms.

      Run: [ @repl.it ]

      # suppose the layout is:
      #
      #  A B C D
      #  E F G H
      #  J K L M
      #  N P Q R
      
      SubstitutedExpression
      
      --digits="1,3,5,7,9"
      
      # no repeated digit in any row or column
      --distinct="ABCD,EFGH,JKLM,NPQR,AEJN,BFKP,CGLQ,DHMR"
      
      # don't reorder the expressions (they all use all 16 symbols)
      --reorder=0
      
      # each average uses an odd number of different odd digits
      --code="avg = lambda *ns: ediv(sum(ns), len(ns))"
      --code="odds = {1, 3, 5, 7, 9}"
      --code="check = lambda s: len(s) in odds and odds.issuperset(s)"
      
      # row average = WXYZ
      "avg(ABCD, EFGH, JKLM, NPQR) = WXYZ"
      "check({W, X, Y, Z})"
      
      # col average = STUV, is greater than row average
      "avg(AEJN, BFKP, CGLQ, DHMR) = STUV"
      "STUV > WXYZ"
      "check({S, T, U, V})"
      
      # each digit appears at least 3 times
      --code="count = lambda s: all(s.count(d) > 2 for d in odds)"
      "count([A, B, C, D, E, F, G, H, J, K, L, M, N, P, Q, R])"
      
      # required answer (row avg, col avg)
      --answer="(WXYZ, STUV)"
      
      # [optional] less verbose output
      --template="({ABCD}, {EFGH}, {JKLM}, {NPQR}) -> {WXYZ}, {STUV}"
      --solution=""
      

      Solution: The row average is 5159. The column average is 5951.

      There are 56 possible arrangements of digits in the grid. Here is one:

      1 9 7 5
      3 5 1 7
      5 3 9 1
      9 7 5 3

      Row average = (1975 + 3517 + 5391 + 9753) / 4 = 5159.

      Column average = (1359 + 9537 + 7195 + 5713) / 4 = 5951.

      Like

    • Frits 12:31 pm on 16 January 2021 Permalink | Reply

      @Jim,

      First time I see a nested lambda.

      I would have used

      “check({W, X, Y, Z})” etc

      and

      –code=”check = lambda s: len(s) in odds and odds.issuperset(s)”

      Like

      • Jim Randell 1:48 pm on 16 January 2021 Permalink | Reply

        @Frits: Yes, that would probably be clearer. I’ll change it.

        I wrote that bit of code before I was using STUV and WXYZ for the averages, so I didn’t already have them broken out into separate digits.


        You can use a lambda expression to implement a sort of where clause in Python:

        <expr1> where (x=<expr2>, y=<expr3>)
        

        can be implemented as:

        (lambda x, y: <expr1>)(<expr2>, <expr3>)
        

        or:

        (lambda x=<expr2>, y=<expr3>: <expr1>)()
        

        Like

    • Jim Randell 8:18 am on 17 January 2021 Permalink | Reply

      And here is a much faster solution that uses some analysis:

      If we start with the four 4-digit numbers that form the rows, we can construct a fifth 4-digit number using the missing digit from each column.

      When these five numbers are added together, each possible digit now appears in each position, so we get:

      T = 1111 × (1 + 3 + 5 + 7 + 9) = 27775

      We can then make possible actual totals by subtracting a 4-digit number composed of different odd digits from T.

      (Each possible digit appears 4 times in our collection of five 4-digit numbers, and in the actual grid we want each digit to appear at least 3 times, so we can only remove at most 1 copy of each digit).

      A viable total must be divisible by 4 to give the average, which itself must consist of an odd number of different odd digits.

      And for any pair of averages the row average must be less than the column average.

      The following program uses this technique to find possible viable pairs of averages. It turns out there is only one viable pair, so this gives us our solution.

      It runs in 44ms.

      Run: [ @repl.it ]

      from enigma import subsets, nconcat, div, nsplit, printf
      
      # allowable digits
      digits = {1, 3, 5, 7, 9}
      
      # generate possible averages for 4x 4-digit numbers
      # with no digit repeated in the same position
      def avgs():
        # if all digits appeared in each position then 4 copies
        # of each digit would be used, and the sum would be ...
        T = 1111 * sum(digits)
      
        # now delete a digit from each position
        # at least 3 copies of each digit must remain, so we can only
        # delete at most one instance of any digit
        for xs in subsets(digits, size=4, select="P"):
          # calculate the average
          avg = div(T - nconcat(xs), 4)
          if avg is None: continue
          # check it uses an odd number of different odd digits
          s = nsplit(avg, fn=set)
          if not(len(s) in digits and digits.issuperset(s)): continue
          # return the average
          yield avg
      
      # choose possible row and column averages
      for (ravg, cavg) in subsets(sorted(avgs()), size=2):
        printf("row avg = {ravg}, col avg = {cavg}")
      

      All that remains is to show that a grid can be constructed using the required averages. Fortunately my first program (above) finds many possible ways to do this.

      Like

      • Frits 3:39 pm on 17 January 2021 Permalink | Reply

        @Jim, Very clever. I also was thinking to start with the missing digits but would probably not have come up with this solution.

        nconcat(xs) modulo 4 must be 3 but this will not help an already very fast program.

        Like

    • GeoffR 12:36 pm on 17 January 2021 Permalink | Reply

      This programme is a bit verbose and an array type solution might well be shorter.
      Hovever, it gets the same answer as Jim’s first solution and runs in about the same time as that solution – about 0.7 sec.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % four-by-four grid
      %  A B C D
      %  E F G H
      %  J K L M
      %  N P Q R
      
      set of int: odds = {1,3,5,7,9};
      
      var 1..9: A; var 1..9: B; var 1..9: C; var 1..9: D; 
      var 1..9: E; var 1..9: F; var 1..9: G; var 1..9: H; 
      var 1..9: J; var 1..9: K; var 1..9: L; var 1..9: M; 
      var 1..9: N; var 1..9: P; var 1..9: Q; var 1..9: R; 
      
      % Row 1 digits
      constraint A in odds /\ B in odds /\ C in odds /\ D in odds;
      constraint all_different ([A,B,C,D]);
      % Row 2 digits
      constraint E in odds /\ F in odds /\ G in odds /\ H in odds;
      constraint all_different ([E,F,G,H]);
      % Row 3 digits
      constraint J in odds /\ K in odds /\ L in odds /\ M in odds;
      constraint all_different ([J,K,L,M]);
      % Row 4 digits
      constraint N in odds /\ P in odds /\ Q in odds /\ R in odds;
      constraint all_different ([N,P,Q,R]);
      
      % Each odd digit appears three or four times in the grid
      % Row 1 digit counts
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], A, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], A, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], B, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], B, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], C, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], C, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], D, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], D, 4) ;
      
      % Row 2 digit counts
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], E, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], E, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], F, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], F, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], G, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], G, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], H, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], H, 4) ;
      
      % Row 3 digit counts
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], J, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], J, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], K, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], K, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], L, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], L, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], M, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], M, 4) ;
      
      % Row 4 digit counts
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], N, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], N, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], P, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], P, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], Q, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], Q, 4) ;
      
      constraint count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], R, 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
      N,P,Q,R], R, 4) ;
      
      % Down column digits are all different
      constraint all_different([A,E,J,N]);
      constraint all_different([B,F,K,P]);
      constraint all_different([C,G,L,Q]);
      constraint all_different([D,H,M,R]);
      
      % Across numbers in grid
      var 1000..9999:ABCD = 1000*A + 100*B + 10*C + D;
      var 1000..9999:EFGH = 1000*E + 100*F + 10*G + H;
      var 1000..9999:JKLM = 1000*J + 100*K + 10*L + M;
      var 1000..9999:NPQR = 1000*N + 100*P + 10*Q + R;
      
      % Down numbers in grid
      var 1000..9999:AEJN = 1000*A + 100*E + 10*J + N;
      var 1000..9999:BFKP = 1000*B + 100*F + 10*K + P;
      var 1000..9999:CGLQ = 1000*C + 100*G + 10*L + Q;
      var 1000..9999:DHMR = 1000*D + 100*H + 10*M + R;
      
      % Each average (across and down) is a whole number(see description)
      % Average of across numbers 
      var 1000..9999: Av_Across;
      Av_Across = (ABCD + EFGH + JKLM + NPQR) div 4;
      
      % Across average digits (A1, A2, A3, A4)
      var 1..9:A1; var 1..9:A2; var 1..9:A3; var 1..9:A4;
      
      constraint A1 == Av_Across div 1000 /\ A1 mod 2 == 1;
      
      constraint A2 = Av_Across div 100 mod 10 /\ A2 mod 2 == 1;
      
      constraint A3 = Av_Across div 10 mod 10 /\ A3 mod 2 == 1;
      
      constraint A4 = Av_Across mod 10 /\ A4 mod 2 == 1;
      
      % Average of down numbers
      var 1000..9999: Av_Down;
      Av_Down = (AEJN + BFKP + CGLQ + DHMR) div 4;
      
      % Down average digits (D1, D2, D3, D4)
      var 1..9:D1; var 1..9:D2; var 1..9:D3; var 1..9:D4;
      
      constraint D1 == Av_Down div 1000 /\ D1 mod 2 == 1;
      
      constraint D2 = Av_Down div 100 mod 10 /\ D2 mod 2 == 1;
      
      constraint D3 = Av_Down div 10 mod 10 /\ D3 mod 2 == 1;
      
      constraint D4 = Av_Down mod 10 /\ D4 mod 2 == 1;
      
      % Larger average is down average
      constraint Av_Down > Av_Across;
      
      % Each average used an odd number of digits
      constraint card({A1,A2,A3,A4}) mod 2 == 1 
      /\ card({D1,D2,D3,D4}) mod 2 == 1;
      
      solve satisfy;
      
      output ["Average across = " ++ show(Av_Across)
      ++ "\nAverage down = " ++ show(Av_Down) 
      ++ "\nTypical grid:"
      ++ "\n" ++ show(ABCD) ++ "\n" ++ show(EFGH)
      ++ "\n" ++ show(JKLM) ++ "\n" ++ show(NPQR)];
      
      
      

      Like

      • Frits 1:54 pm on 17 January 2021 Permalink | Reply

        @GeoffR,

        You don’t have to the count for each variable A-R, only for 1,3,5,7,9.
        However, the program doesn’t seem to run faster.

        % Each odd digit appears three or four times in the grid
        array[1..5] of int: nbrs = [1,3,5,7,9];
        constraint forall (i in 1..5) (count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
        N,P,Q,R], nbrs[i], 3) \/ count_eq ( [A,B,C,D,E,F,G,H,J,K,L,M,
        N,P,Q,R], nbrs[i], 4));
        

        Like

    • GeoffR 3:26 pm on 17 January 2021 Permalink | Reply

      @Frits: Good point. That will shorten the code.
      The original code took 240 ms to print the answer, and 667 msec to complete the search on my I7 laptop.

      Like

  • Jim Randell 9:04 am on 20 December 2020 Permalink | Reply
    Tags: by: Victor Bryant   

    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 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: [ @repl.it ]

      #!/usr/bin/env python -m enigma -r
      
      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 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 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 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 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 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 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 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

  • Jim Randell 9:59 am on 19 November 2020 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2764: Three little lists 

    From The Sunday Times, 13th September 2015 [link]

    I have chosen five different numbers, each less than 20, and I have listed these numbers in three ways. In the first list the numbers are in increasing numerical order. In the second list the numbers are written in words and are in alphabetical order. In the third list they are again in words and as you work down the list each word uses more letters than its predecessor. Each number is in a different position in each of the lists.

    What are my five numbers?

    [teaser2764]

     
    • Jim Randell 9:59 am on 19 November 2020 Permalink | Reply

      This Python program runs in 68ms.

      Run: [ @repl.it ]

      from enigma import irange, subsets, int2words, join, printf
      
      # the numbers (in numerical order)
      nums = list(irange(1, 19))
      
      # map numbers to words
      word = dict((n, int2words(n)) for n in nums)
      
      # map number to word length
      length = dict((n, len(word[n])) for n in nums)
      
      # choose 5 numbers for the first list
      for s1 in subsets(nums, size=5):
      
        # make the third list by ordering the numbers by word length
        k3 = lambda n: length[n]
        # check all word lengths are distinct
        if len(set(k3(n) for n in s1)) < 5: continue
        s3 = sorted(s1, key=k3)
      
        # make the second list by ordering the numbers alphabetically
        k2 = lambda n: word[n]
        s2 = sorted(s1, key=k2)
      
        # no number is the same place in 2 or more lists
        if any(len(set(x)) < 3 for x in zip(s1, s2, s3)): continue
      
        # output solution (lists 2 and 3 formatted as words)
        fmt = lambda ns: join((word[n] for n in ns), sep=", ", enc="()")
        printf("1: {s1}")
        printf("2: {s2}", s2=fmt(s2))
        printf("3: {s3}", s3=fmt(s3))
        printf()
      

      Solution: The 5 numbers are: 3, 6, 9, 17, 19.

      Like

  • Jim Randell 9:26 am on 15 November 2020 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 1946: Not the millennium bug 

    From The Sunday Times, 2nd January 2000 [link]

    Do you remember all that fuss over the “Millennium bug”?

    On that New Year’s Day I typed a Teaser on my word processor. When I typed in 2000 it actually displayed and printed 1900. This is because whenever I type a whole number in figures the machine actually displays and prints only a percentage of it, choosing a random different whole number percentage each time.

    The first example was bad enough but the worrying this is that is has chosen even lower percentages since then, upsetting everything that I prepare with numbers in it. Luckily the percentage reductions have not cut any number by half or more yet.

    What percentage did the machine print on New Year’s Day?

    This puzzle was included in the book Brainteasers (2002, edited by Victor Bryant). The puzzle text above is taken from the book.

    [teaser1946]

     
    • Jim Randell 9:26 am on 15 November 2020 Permalink | Reply

      See also: Enigma 1419.

      We assume that both the original (prepared on 2000-01-01) puzzle, and the puzzle text presented above were created using the faulty program.

      So, on 2000-01-01 the setter typed a whole number, X, which was replaced by the value aX, where a is some whole number percentage less than 100% and greater than 50%.

      In relating the story for this puzzle, the setter has typed the values X and aX, and these have been replaced by values multiplied by b and c respectively, where b and c are different whole number percentages, less than a and greater than 50%.

      So, we have:

      bX = 2000
      c.aX = 1900

      This Python program runs in 44ms.

      Run: [ @repl.it ]

      from enigma import irange, div, printf
      
      # choose a percentage for b
      for b in irange(51, 98):
        X = div(2000 * 100, b)
        if X is None: continue
      
        # a > b
        for a in irange(b + 1, 99):
          aX = div(a * X, 100)
          if aX is None: continue
          c = div(1900 * 100, aX)
          if c is None or c == b or not(a > c > 50): continue
      
          # output solution
          printf("a={a} b={b} c={c} -> X={X} aX={aX}")
      

      Solution: On 2000-01-01 the machine used a value of 80%.

      So the setter was attempting to enter 3125, but instead the program printed 80% of this = 2500.

      In relating the story, the setter typed: “When I typed in 3125 it actually printed 2500”, but these values were replaced using percentages of 64% and 76%, to appear as: “When I typed in 2000 it actually printed 1900”, as in the puzzle text.

      Like

  • Jim Randell 12:17 pm on 29 October 2020 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 1928: Prime of life 

    From The Sunday Times, 29th August 1999 [link]

    Today my daughter was looking through her old scrapbook and came across a rhyme I had written about her when she was a little girl:

    Here’s a mathematical rhyme:
    Your age in years is a prime;
    Mine is too,
    And if you add the two
    The answer’s a square — how sublime!

    She was surprised to find that this is also all true today. Furthermore is will all be true again some years hence.

    How old are my daughter and I?

    This puzzle was included in the book Brainteasers (2002, edited by Victor Bryant). The puzzle text above is taken from the book.

    [teaser1928]

     
    • Jim Randell 12:18 pm on 29 October 2020 Permalink | Reply

      When rhyme was written the daughter’s age was some prime d, the father’s age some prime f, and (d + f) is a square number.

      Unless they were born on the same day at the same time one of them have their next birthday before the other.

      If it is the daughter, the ages progress like this:

      (d, f) → (d + 1, f) → (d + 1, f + 1) → (d + 2, f + 1) → (d + 2, f + 2) …

      And if the father has the next birthday, the ages progress like this:

      (d, f) → (d, f + 1) → (d + 1, f + 1) → (d + 1, f + 2) → (d + 2, f + 2) …

      So we just need to examine these sequences to look for two more occurrences of the ages being prime, and their sum being a square.

      This Python program runs in 44ms.

      Run: [ @repl.it ]

      from enigma import Primes, is_square, printf
      
      # primes for ages
      primes = Primes(150)
      
      # check for viable ages
      check = lambda a, b: a in primes and b in primes and is_square(a + b)
      
      # extend the list to length k, with birthdays a then b
      def extend(a, b, k=3):
        rs = [(a, b)]
        while a < 150 and b < 150:
          a += 1
          if check(a, b): rs.append((a, b))
          b += 1
          if check(a, b): rs.append((a, b))
          if not(len(rs) < k): return rs
      
      # consider the daughters age at the time of the rhyme
      for d in primes.irange(2, 16):
      
        # now consider possible ages for the father
        for f in primes.irange(d + 16, 50):
          # together they make a square
          if not is_square(d + f): continue
      
          # find solutions where daughters birthday is next
          rs = extend(d, f)
          if rs: printf("d -> f: {rs}")
      
          # find solutions where fathers birthday is next
          rs = extend(f, d)
          if rs: printf("f -> d: {rs}")
      

      Solution: Today the daughter is 7 and the father is 29.

      The three pairs of ages are:

      d = 2, f = 23: d + f = 25 = 5²
      d = 7, f = 29: d + f = 36 = 6²
      d = 61, f = 83: d + f = 144 = 12²

      So father’s birthday came first after the rhyme was written.

      Like

    • Frits 1:44 pm on 29 October 2020 Permalink | Reply

      from enigma import SubstitutedExpression, is_prime, is_square
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [# father (age CDE) is a lot older than daughter (age AB)
         "AB + 15 < CDE",
         "PQ > 0",
         "RS > 0",
         # daughter must have already been born PQ years ago (and prime)
         # "when she was a little girl"
         "0 < AB - PQ < 10",
         # maximum age father
         "CDE < 125",
         "CDE + RS < 125",
         
         # PQ years ago
         "is_prime(AB - PQ - w)",
         "is_prime(CDE - PQ - x)",
         "is_square(AB + CDE - 2 * PQ - w - x)",
         # now
         "is_prime(AB)",
         "is_prime(CDE)",
         "is_square(AB + CDE)",
         # RS years later
         "is_prime(AB + RS + y)",
         "is_prime(CDE + RS + z)",
         "is_square(AB + CDE + 2 * RS + y + z)",
         
         # uncertainty bits, not both of them may be true
         "x + w < 2",
         "y + z < 2",
        ],
        answer="AB, CDE, PQ, RS, w, x, y, z",
        symbols="ABCDEPQRSwxyz",
        verbose=0,
        d2i=dict([(k, "wxyz") for k in {2,3,4,5,6,7,8,9}]),
        distinct="",   # allow variables with same values
        #reorder=0,
      )
      
      # Print answer
      for (_, ans) in p.solve():
        print(f"ages daughter {ans[0] - ans[2] - ans[4]} {ans[0]} "
              f"{ans[0] + ans[3] + ans[6]}")
        print(f"ages father   {ans[1] - ans[2]  - ans[5]} "
              f"{ans[1]} {ans[1] + ans[3]  + ans[7]}")
        print(f"squares       {ans[0] + ans[1] - 2*ans[2]  - ans[4] - ans[5]} "
              f"{ans[0] + ans[1]} {ans[0] + ans[1] + 2*ans[3] + ans[6] + ans[7]}")
        
        
      # ages daughter 2 7 61
      # ages father   23 29 83
      # squares       25 36 144
      

      Like

    • Frits 4:16 pm on 29 October 2020 Permalink | Reply

      from enigma import printf
      
      # Prime numbers up to 124
      P =  [2, 3, 5, 7]
      P += [x for x in range(11, 100, 2) if all(x % p for p in P)]
      P += [x for x in range(101, 125, 2) if all(x % p for p in P)]
      
      # report two prime numbers (ascending) which sum to <n>
      def twoprimes(n, dif=0): 
        li = []
        i = 1
        p1 = 2 
        while(p1 < n - p1): 
          if n - p1 in P:
            # difference between primes is not exact
            if dif == 0 or (dif - 1 <= abs(n - 2 * p1) <= dif + 1): 
              li.append([p1, n - p1])
          p1 = P[i]
          i += 1
        return li  
      
      # square candidates for when daughter was a little girl   
      for i in range(4, 11):  # also allowing for people like B. Ecclestone
        for t1 in twoprimes(i * i): 
          # "when she was a little girl"
          if t1[0] > 9: continue
          dif1 = int(t1[1]) - int(t1[0])
          # square candidates for now
          for j in range(i + 1, 15):
            for t2 in twoprimes(j * j, dif1): 
              # square candidates for in te future
              for k in range(j + 1, 16):
                for t3 in twoprimes(k * k, dif1): 
                  printf("{t1[0]} + {t1[1]} = {su}", su = int(t1[0]) + int(t1[1]))
                  printf("{t2[0]} + {t2[1]} = {su}", su = int(t2[0]) + int(t2[1]))
                  printf("{t3[0]} + {t3[1]} = {su}", su = int(t3[0]) + int(t3[1]))
      

      Like

    • GeoffR 9:23 pm on 29 October 2020 Permalink | Reply

      % A Solution in MiniZinc     
      include "globals.mzn";
      
      % Three Daughters' ages
      % D1 = young girl, D2 = age now, D3 = future age
      var 1..10:D1; var 1..50:D2; var 1..80:D3;
      
      % Three corresponding Fathers ages
      var 13..40:F1; var 13..70:F2; var 13..105:F3;
      
      % All Fathers and Daughters ages are different
      constraint all_different ([F1, F2, F3, D1, D2, D3]);
      
      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};
      
      set of int : squares = {16, 25, 36, 49, 64, 81,
       100, 121, 144, 169};
      
      % Age group constraints
      constraint F1 - D1 > 12 /\ D1 < 10 ;
      constraint D2 > D1 /\ D3 > D2;
      constraint F2 > F1 /\ F3 > F2;
      constraint F1 > D1 /\ F2 > D2 /\ F3 > D3;
      
      % 1st age differences between Father and Daughter
      constraint D2 - D1 = F2 - F1 + 1
      \/ D2 - D1 = F2 - F1 - 1;
      
      % Age difference is the same between the 2nd and 3rd age groups
      constraint F2 - D2 == F3 - D3;
      constraint F3 - F2 == D3 - D2;
      
      % All ages are prime numbers
      constraint F1 in primes /\ F2 in primes /\ F3 in primes;
      constraint D1 in primes /\ D2 in primes /\ D3 in primes;
      
      % All father and daughter group sums are squares
      constraint (F1 + D1) in squares /\ (F2 + D2) in squares 
      /\ (F3 + D3) in squares;
      
      solve satisfy;
      
      output[ "Father's ages in sequence are " ++ show(F1) ++
       ", " ++ show(F2) ++ ", " ++ show(F3)  
      ++"\nDaughters ages in sequence are " ++ show(D1) ++
       ", " ++ show(D2) ++  ", " ++ show(D3) ];
      
      % Father's ages in sequence are 23, 29, 83
      % Daughters ages in sequence are 2, 7, 61
      % ----------
      % ==========
      
      
      

      Like

      • Frits 10:25 am on 30 October 2020 Permalink | Reply

        I feel lines 11 and 12 are too restrictive. However, removing them gives the same result.

        Like

    • GeoffR 5:16 pm on 30 October 2020 Permalink | Reply

      @Frits:
      The constraint programming approach is to search for a state of the world in which a large number of constraints are satisfied at the same time. But we cannnot predict in advance which constraints are required for a solution. It is, of course, a different approach to imperative programming e.g. Python.

      It is therefore possible to cancel one or two constraints and still get a solution.
      We soon know if we have not got sufficient constraints when we don’t get a solution.

      Lines 11 and 12 are logical in that we know over several time scales that all the fathers and daughters ages will be different, so it is quite OK to make this a constraint, in my view.

      As an experiment, I remmed out Lines 22, 23 and 24, leaving Line 12 functional. This still gave the correct solution. I then remmed out Line 12 and I got three solutions – one correct and two wrong.
      This shows that Line 12 constraint is related to the constraints on Lines 22,23 and 24 in functionality.

      So we could equally say that Lines 22,23 and 24 could be removed, providing Line 12 was not removed.

      I think all the constraints I used have a reasonable basis, so it is probably best not to tinker with individual constraints and let constraint programming use its own internal procedures to find a solution.

      Like

    • Frits 11:26 am on 31 October 2020 Permalink | Reply

      @GeoffR,

      My only point is that this particular constraint is not part of the requirements and can potentially give cause to miss certain solutions.

      You say that “we know over several time scales that all the fathers and daughters ages will be different”. I think it is possible the daughter “today” can have the same age as her father at the time she was a little girl (same for later on).

      Example (if we forget about primes):

      Father’s ages in sequence are 23, 44, 83
      Daughters ages in sequence are 2, 23, 62

      You may be right if the line 11/12 constraint emerges from all the requirements but that is not immediately clear to me.

      Like

  • Jim Randell 9:58 am on 13 October 2020 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 1915: Rabbit, rabbit, rabbit, … 

    From The Sunday Times, 30th May 1999 [link]

    In each of the four houses in a small terrace lives a family with a boy, a girl and a pet rabbit. One of the children has just mastered alphabetical order and has listed them thus:

    I happen to know that this listing gave exactly one girl, one boy and one rabbit at her, his or its correct address. I also have the following correct information: neither Harry nor Brian lives at number 3, and neither Donna nor Jumper lives at number 1. Gail’s house number is one less than Mopsy’s house number, and Brian’s house number is one less than Cottontail’s.

    Who lives where?

    This puzzle was included in the book Brainteasers (2002, edited by Victor Bryant). The puzzle text above is taken from the book.

    [teaser1915]

     
    • Jim Randell 9:58 am on 13 October 2020 Permalink | Reply

      See also: Teaser 2944.

      This Python program runs in 44ms.

      Run: [ @repl.it ]

      from enigma import subsets, printf
      
      # the names
      girls = "ADGK"
      boys = "BEHL"
      rabbits = "CFJM"
      
      # choose an ordering where exactly k of the original ordering is correct
      def choose(xs, k=1):
        for ys in subsets(xs, size=len, select="P"):
          if sum(x == y for (x, y) in zip(xs, ys)) == k:
            yield ys
      
      # choose an ordering for the boys
      for boy in choose(boys):
        # "neither H nor B live at number 3 [= index 2]"
        if boy[2] == 'H' or boy[2] == 'B': continue
      
        # choose an ordering for the rabbits
        for rabbit in choose(rabbits):
          # "J does not live at number 1 [=index 0]"
          if rabbit[0] == 'J': continue
          # "B's number is one less than C's"
          if boy.index('B') + 1 != rabbit.index('C'): continue
      
          # choose an ordering for the girls
          for girl in choose(girls):
            # "D does not live at number 1 [= index 0]"
            if girl[0] == 'D': continue
            # "G's number is one less than M's"
            if girl.index('G') + 1 != rabbit.index('M'): continue
      
            # output solution
            for (n, (g, b, r)) in enumerate(zip(girl, boy, rabbit), start=1):
              printf("{n}: {g} {b} {r}")
            printf()
      

      Solution: The occupants of each house are:

      1: Kelly, Harry, Flopsy
      2: Alice, Brian, Jumper
      3: Gail, Eric, Cottontail
      4: Donna, Laurie, Mopsy

      Like

    • Frits 4:56 pm on 13 October 2020 Permalink | Reply

      from enigma import SubstitutedExpression
      
      girls   = ("", "Alice", "Donna", "Gail", "Kelly")
      boys    = ("", "Brian", "Eric", "Harry", "Laurie")
      rabbits = ("", "Cottontail", "Flopsy", "Jumper", "Mopsy")
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
         # "B's number is one less than C's"
         "B + 1 = C",
         # "G's number is one less than M's" 
         "G + 1 = M",
         # listing gave exactly one girl, one boy and one rabbit at
         # her, his or its correct address
         "sum((A == 1, D == 2, G == 3, K == 4)) == 1",
         "sum((B == 1, E == 2, H == 3, L == 4)) == 1",
         "sum((C == 1, F == 2, J == 3, M == 4)) == 1",
        ],
        answer="ADGK, BEHL, CFJM",   
        digits=range(1,5),
        distinct=('ADGK', 'BEHL', 'CFJM'),
        # "D does not live at number 1"
        # "J does not live at number 1"
        # "neither H nor B live at number 3"
        d2i={1 : "CMDJ", 3 : "BH", 4 : "BG"}, 
        verbose=0,
        #reorder=0,
      )
      
      # Print answers
      for (_, ans) in p.solve(): 
        for k in "1234":
          x = [j+1 for x in ans for j, y in enumerate(str(x)) if y == k]
          print(f"house {k}: {girls[x[0]]:<6} {boys[x[1]]:<7} {rabbits[x[2]]}")
        
      # house 1: Kelly  Harry   Flopsy
      # house 2: Alice  Brian   Jumper
      # house 3: Gail   Eric    Cottontail
      # house 4: Donna  Laurie  Mopsy
      

      Like

    • John Crabtree 6:34 pm on 13 October 2020 Permalink | Reply

      Flopsy must be at #1.
      Brian cannot be at #2, otherwise Jumper and Mopsy are both correct or both incorrect.
      And so Brian is at #1, Cottontail at #3, Jumper at #1, Mopsy at #4, and Gail at #3, etc

      Like

  • Jim Randell 4:38 pm on 9 October 2020 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 3029: Square jigsaws 

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

    I chose a whole number and asked my grandson to cut out all possible rectangles with sides a whole number of centimetres whose area, in square centimetres, did not exceed my number. (So, for example, had my number been 6 he would have cut out rectangles of sizes 1×1, 1×2, 1×3, 1×4, 1×5, 1×6, 2×2 and 2×3). The total area of all the pieces was a three-figure number of square centimetres.

    He then used all the pieces to make, in jigsaw fashion, a set of squares. There were more than two squares and at least two pieces in each square.

    What number did I originally choose?

    [teaser3029]

     
    • Jim Randell 5:17 pm on 9 October 2020 Permalink | Reply

      (See also: Enigma 1251, Enigma 1491).

      If the squares are composed of at least two pieces, they must be at least 3×3.

      This Python program works out the only possible original number that can work, but it doesn’t demonstrate the the rectangles can be assembled into the required squares.

      It runs in 44ms.

      Run: [ @repl.it ]

      from enigma import irange, inf, printf
      
      # generate rectangles with area less than n
      def rectangles(n):
        for i in irange(1, n):
          if i * i > n: break
          for j in irange(i, n // i):
            yield (i, j)
      
      # decompose t into squares
      def decompose(t, m=1, ss=[]):
        if t == 0:
          yield ss
        else:
          for k in irange(m, t):
            s = k * k
            if s > t: break
            yield from decompose(t - s, k, ss + [k])
      
      # make squares from the rectangular pieces, with total area A
      def fit(rs, A):
        # determine the maximum dimension of the rectangles
        m = max(j for (i, j) in rs)
        for n in irange(m, A):
          if n * n > A: break
          # decompose the remaining area into squares
          for ss in decompose(A - n * n, 3):
            if len(ss) < 2: continue
            yield ss + [n]
      
      # consider the chosen number
      for n in irange(2, inf):
        # collect the rectangles and total area
        rs = list(rectangles(n))
        A = sum(i * j for (i, j) in rs)
        if A < 100: continue
        if A > 999: break
      
        # fit the rectangles in a set of squares
        for ss in fit(rs, A):
          printf("n={n}, A={A} -> ss={ss}")
      

      Solution: The original number was 29.

      The rectangles cut out are:

      1, 2, 3, …, 29
      2, 3, …, 14
      3, …, 9
      4, 5, 6, 7
      5

      With a total area of 882 cm².

      The 1×29 piece must fit into a square of size 29×29 or larger, but this is the largest square we can make, so there must be a 29×29 square, which leaves an area of 41 cm². This can be split into squares as follows:

      41 = 3² + 4² + 4²
      41 = 4² + 5²

      It turns out that it only possible to construct a packing using the second of these.

      I used the polyominoes.py library that I wrote for Teaser 2996 to assemble the rectangles into a viable arrangement of squares. It runs in 19 minutes. (The adapted program is here).

      Here is a diagram showing one way to pack the rectangles into a 4×4, 5×5 and a 29×29 square:

      Like

      • Frits 2:27 pm on 10 October 2020 Permalink | Reply

        @Jim,

        Wouldn’t it be easier to use the chosen number n as maximum dimension (line 23)?

        Like

        • Jim Randell 11:51 am on 11 October 2020 Permalink | Reply

          @Frits: Probably. When I started writing the program I was thinking about a constructive solution, that would produce a packing of the rectangles into the required squares. This is a cut-down version of the program which finds possible sets of squares to investigate – fortunately the solutions found all correspond to the same original number, so if there is an answer we know what it must be.

          And it turns out that we don’t need to examine the set of rectangles to determine the maximum dimension, so we could just pass it in. In fact we don’t need to collect the rectangles at all. Here’s a better version of the cut-down program:

          from enigma import irange, inf, divisors_pairs, printf
          
          # decompose t into squares
          def decompose(t, m=1, ss=[]):
            if t == 0:
              yield ss
            else:
              for k in irange(m, t):
                s = k * k
                if s > t: break
                yield from decompose(t - s, k, ss + [k])
          
          # find at least 3 potential squares with total area A
          # that can accomodate a rectangle with max dimension m
          def fit(A, m):
            for n in irange(m, A):
              a = A - n * n
              if a < 18: break
              # decompose the remaining area into at least 2 squares
              # with minimum dimension 3
              for ss in decompose(a, 3):
                if len(ss) > 1:
                  yield ss + [n]
          
          # collect rectangles with increasing area
          A = 0
          for n in irange(1, inf):
            # add in rectangles of area n
            A += sum(i * j for (i, j) in divisors_pairs(n))
          
            # look for 3-digit total area
            if A < 100: continue
            if A > 999: break
          
            # find a set of squares with the same area
            for ss in fit(A, n):
              printf("n={n} A={A} -> ss={ss}")
          

          I did complete a program that finds a viable packing, but it takes a while to run (19 minutes).

          I’ll post the diagram with the answer later.

          Like

          • Frits 5:59 pm on 11 October 2020 Permalink | Reply

            @Jim, a nice solution with the divisor pairs.
            I think we can only form one 3×3 square at most (out of 3 possibilities).

            Like

    • Frits 1:29 pm on 10 October 2020 Permalink | Reply

      I did a manual check to see if the reported squares can be formed in 2-D with the rectangular pieces.

       
      # select numbers from list <li> so that sum of numbers equals <n>
      def decompose(n, li, sel=[]):
        if n == 0:
          yield sel
        else:
          for i in {j for j in range(len(li)) if li[j] <= n}:
            yield from decompose(n - li[i], li[i:], sel + [li[i]])     
              
      # squares under 1000, square 2x2 can't be formed from rectangles                 
      squares = [n*n for n in range(3, 32)]
      
      rectangles = lambda n: [(i, j) for i in range(1, n + 1) 
                              for j in range(i, n + 1) if i * j <= n]
      
      area = lambda li: sum(i * j for (i, j) in li)
      
      # candidates with three-figure number area; area must be
      # at least largest square (i*i) plus the 2 smallest squares 9 and 16
      cands = lambda: {i: area(rectangles(i)) for i in range(7, 32) 
                       if area(rectangles(i)) in range(100, 1000) and
                          area(rectangles(i)) >= i * i + 25}
      
      # check if solution exist for candidates
      for (n, a) in cands().items(): 
        # biggest square should be at least n x n due to 1 x n piece
        for big in range(n, 32):
          # list of squares to consider (excluding the biggest square)
          sq = [x for x in squares if x <= a - (big * big) - 9]
          # select squares which together with biggest square will sum to area <a>
          for s in decompose(a - (big * big), sq):
            if len(s) > 1:
              print(f"number chosen = {n}, area={a}, squares={s + [big * big]}")
      

      Like

  • Jim Randell 10:36 am on 8 October 2020 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 1908: Dunroamin 

    From The Sunday Times, 11th April 1999 [link]

    At our DIY store you can buy plastic letters of the alphabet in order to spell out your house name. Although all the A’s cost the same as each other, and all the B’s cost the same as each other, etc., different letters sometimes cost different amounts with a surprisingly wide range of prices.

    I wanted to spell out my house number:

    FOUR

    and the letters cost me a total of £4. Surprised by this coincidence I worked out the cost of spelling out each of the numbers from ONE to TWELVE. In ten out of the twelve cases the cost in pounds equalled the number being spelt out.

    For which house numbers was the cost different from the number?

    This puzzle was included in the book Brainteasers (2002, edited by Victor Bryant). The puzzle text above is taken from the book.

    [teaser1908]

     
    • Jim Randell 10:37 am on 8 October 2020 Permalink | Reply

      (See also: Teaser 2756, Enigma 1602).

      This Python program checks to see if each symbol can be assigned a value that is a multiple of 25p to make the required 10 words correct (and also checks that the remaining two words are wrong).

      Instead of treating the letters G, H, R, U separately, we treat them as GH, HR, UR, which reduces the number of symbols to consider by 1.

      The program runs in 413ms.

      Run: [ @repl.it ]

      from enigma import irange, subsets, update, unpack, diff, join, map2str, printf
      
      # <value> -> <symbol> mapping
      words = {
        100: ("O", "N", "E"),
        200: ("T", "W", "O"),
        300: ("T", "HR", "E", "E"),
        400: ("F", "O", "UR"),
        500: ("F", "I", "V", "E"),
        600: ("S", "I", "X"),
        700: ("S", "E", "V", "E", "N"),
        800: ("E", "I", "GH", "T"),
        900: ("N", "I", "N", "E"),
        1000: ("T", "E", "N"),
        1100: ("E", "L", "E", "V", "E" ,"N"),
        1200: ("T" ,"W", "E", "L", "V", "E"),
      }
      
      # decompose t into k numbers, in increments of step
      def decompose(t, k, step, ns=[]):
        if k == 1:
          yield ns + [t]
        elif k > 1:
          k_ = k - 1
          for n in irange(step, t - k_ * step, step=step):
            yield from decompose(t - n, k_, step, ns + [n])
      
      # find undefined symbols and remaining cost
      def remaining(v, d):
        (us, t) = (set(), v)
        for x in words[v]:
          try:
            t -= d[x]
          except KeyError:
            us.add(x)
        return (us, t)
      
      # find values for vs, with increments of step
      def solve(vs, step, d=dict()):
        # for each value find remaining cost and undefined symbols
        rs = list()
        for v in vs:
          (us, t) = remaining(v, d)
          if t < 0 or bool(us) == (t == 0): return
          if t > 0: rs.append((us, t, v))
        # are we done?
        if not rs:
          yield d
        else:
          # find the value with the fewest remaining symbols (and lowest remaining value)
          (us, t, v) = min(rs, key=unpack(lambda us, t, v: (len(us), t)))
          # the remaining values
          vs = list(x for (_, _, x) in rs if x != v)
          # allocate the unused symbols
          us = list(us)
          for ns in decompose(t, len(us), step):
            # solve for the remaining values
            yield from solve(vs, step, update(d, us, ns))
      
      # choose the 2 equations that are wrong
      for xs in subsets(sorted(words.keys()), size=2):
        # can't include FOUR
        if 400 in xs: continue
        # find an allocation of values
        for d in solve(diff(words.keys(), xs), 25):
          xvs = list(sum(d[s] for s in words[x]) for x in xs)
          if all(x != v for (x, v) in zip(xs, xvs)):
            # output solution
            wxs = list(join(words[x]) for x in xs)
            printf("wrong = {wxs}", wxs=join(wxs, sep=", ", enc="[]"))
            printf("-> {d}", d=map2str(d, sep=" ", enc=""))
            for (x, xv) in zip(wxs, xvs):
              printf("  {x} = {xv}p")
            printf()
            break
      

      Solution: NINE and TEN do not cost an amount equal to their number.

      One way to allocate the letters, so that ONEEIGHT, ELEVEN, TWELVE work is:

      25p = F, H, N, O, T
      50p = E, X
      150p = W, R
      200p = I, U
      225p = V
      350p = S
      500p = G
      700p = L

      (In this scheme: NINE costs £3 and TEN costs £1).

      But there are many other possible assignments.

      You can specify smaller divisions of £1 for the values of the individual symbols, but the program takes longer to run.

      It makes sense that NINE and TEN don’t cost their value, as they are short words composed entirely of letters that are available in words that cost a lot less.


      Here’s a manual solution:

      We note that ONE + TWELVE use the same letters as TWO + ELEVEN, so if any three of them are correct so is the fourth. So there must be 0 or 2 of the incorrect numbers among these four.

      Now, if ONE and TEN are both correct, then any number with value 9 or less with a T in it must be wrong. i.e. TWO, THREE, EIGHT. Otherwise we could make TEN for £10 or less, and have some letters left over. And this is not possible.

      If ONE is incorrect, then the other incorrect number must be one of TWO, ELEVEN, TWELVE, and all the remaining numbers must be correct. So we could buy THREE and SEVEN for £10, and have the letters to make TEN, with EEEHRSV left over. This is not possible.

      So ONE must be correct, and TEN must be one of the incorrect numbers.

      Now, if NINE is correct, then any number with value 7 or less with an I in it must be incorrect. Which would mean FIVE and SIX are incorrect. This is not possible.

      Hence, the incorrect numbers must be NINE and TEN.

      All that remains is to demonstrate one possible assignment of letters to values where NINE and TEN are incorrect and the rest are correct. And the one found by the program above will do.

      Like

    • GeoffR 6:36 pm on 8 October 2020 Permalink | Reply

      I used a wide range of upper .. lower bound values for letter variables.

      The programme would not run satisfactorily under the Geocode Solver, but produced a reasonable run time under the Chuffed Solver. It confirmed the incorrect numbers were NINE and TEN.

      % A Solution in MiniZinc
      include "globals.mzn";
       
      var 10..900:O; var 10..900:N; var 10..900:E; var 10..900:T;
      var 10..900:W; var 10..900:H; var 10..900:R; var 10..900:F;
      var 10..900:U; var 10..900:V; var 10..900:I; var 10..900:L;
      var 10..900:G; var 10..900:S; var 10..900:X;
      
      constraint sum([
      O+N+E == 100, T+W+O == 200, T+H+R+E+E == 300, F+O+U+R == 400,
      F+I+V+E == 500, S+I+X == 600, S+E+V+E+N == 700,
      E+I+G+H+T == 800, N+I+N+E == 900, T+E+N == 1000,
      E+L+E+V+E+N == 1100, T+W+E+L+V+E == 1200]) == 10;
      
      solve satisfy;
      
      output [" ONE = " ++ show (O + N + E) ++
      "\n TWO = " ++ show (T + W + O ) ++
      "\n THREE = " ++ show (T + H + R + E + E) ++
      "\n FOUR = " ++ show (F + O + U + R) ++
      "\n FIVE = " ++ show (F + I + V + E) ++
      "\n SIX = " ++ show (S + I + X) ++
      "\n SEVEN = " ++  show (S + E + V + E + N) ++
      "\n EIGHT = " ++ show (E + I + G + H + T) ++
      "\n NINE = " ++ show (N + I + N + E) ++
      "\n TEN = " ++ show (T + E + N) ++
      "\n ELEVEN = " ++ show (E + L + E + V + E + N) ++
      "\n TWELVE = " ++ show (T + W + E + L + V + E) ++
      "\n\n [O N E T W H R F U V I L G S X = ]" ++ 
      show([O, N, E, T, W, H, R, F, U, V, I, L, G, S, X]) ];
      
      %  ONE = 100
      %  TWO = 200
      %  THREE = 300
      %  FOUR = 400
      %  FIVE = 500
      %  SIX = 600
      %  SEVEN = 700
      %  EIGHT = 800
      %  NINE = 171   << INCORRECT
      %  TEN = 101    << INCORRECT
      %  ELEVEN = 1100
      %  TWELVE = 1200
      %  Letter Values (One of many solutions)
      %  [O    N   E   T   W    H   R    F   U    V    I   L    G    S    X = ]
      %  [10, 71, 19, 11, 179, 13, 238, 10, 142, 461, 10, 511, 747, 130, 460]
      %  time elapsed: 0.04 s
      % ----------
      
      
      
      

      Like

      • Frits 7:47 pm on 11 October 2020 Permalink | Reply

        @GeoffR, As Jim pointed out to me (thanks) that FOUR can not be an incorrect number your MiniZinc program can be adapted accordingly. Now both run modes have similar performance.

        Like

    • Frits 4:56 pm on 11 October 2020 Permalink | Reply

      Pretty slow (especially for high maximum prizes).

      I combined multiple “for loops” into one loop with the itertools product function so it runs both under Python and PyPy.

      @ Jim, your code has some unexplained “# can’t include FOUR” code (line 62, 63).
      It is not needed for performance.

       
      from enigma import SubstitutedExpression
      from itertools import product
      
      mi = 25      # minimum prize
      step = 25    # prizes differ at least <step> pennies 
      ma = 551     # maximum prize + 1
      bits = set() # x1...x12 are bits, 10 of them must be 1, two them must be 0
      
      # return numbers in range and bit value 
      # (not more than 2 bits in (<li> plus new bit) may be 0)
      rng = lambda m, li: product(range(mi, m, step), 
                                 (z for z in {0, 1} if sum(li + [z]) > len(li) - 2))
      
      def report():
        print(f"ONE TWO THREE FOUR FIVE SIX "
        f"SEVEN EIGHT NINE TEN ELEVEN TWELVE"
        f"\n{O+N+E} {T+W+O}   {T+HR+E+E}  {F+O+UR}  {F+I+V+E} {S+I+X} "
        f"  {S+E+V+E+N}   {E+I+GH+T}  {N+I+N+E} {T+E+N}   {E+L+E+V+E+N}"
        f"   {T+W+E+L+V+E}"
        f"\n   O   N   E   T   W   L  HR   F  UR   I   V   S   X  GH"
        f"\n{O:>4}{N:>4}{E:>4}{T:>4}{L:>4}{W:>4}{HR:>4}{F:>4}{UR:>4}"
        f"{I:>4}{V:>4}{S:>4}{X:>4}{GH:>4}")
      
      for (O, N, E) in product(range(mi, ma, step), repeat=3):
        for x1 in {0, 1}:
          if x1 != 0 and O+N+E != 100: continue
          li1 = [x1]
          for (T, x10) in rng(ma, li1):
            if x10 != 0 and T+E+N != 1000: continue
            li2 = li1 + [x10]
            maxW = 201 - 2*mi if sum(li2) == 0 else ma
            for (W, x2) in rng(maxW, li2):
              if x2 != 0 and T+W+O != 200: continue
              li3 = li2 + [x2]
              for (I, x9) in rng(ma, li3):
                if x9 != 0 and N+I+N+E != 900: continue
                li4 = li3 + [x9]
                for L in range(mi, ma, step):
                  for (V, x12) in rng(ma, li4):
                    if x12 != 0 and T+W+E+L+V+E != 1200: continue
                    li5 = li4 + [x12]
                    for x11 in {0, 1}:
                      li6 = li5 + [x11]
                      if sum(li6) < 4 : continue
                      if x11 != 0 and E+L+E+V+E+N != 1100: continue
                      maxF = 501 - 3*mi if sum(li6) == 4 else ma
                      for (F, x5) in rng(maxF, li6):
                        if x5 != 0 and F+I+V+E != 500: continue
                        li7 = li6 + [x5]
                        maxSX = 601 - 2*mi if sum(li7) == 5 else ma
                        for (S, x7) in rng(maxSX, li7):
                          if x7 != 0 and S+E+V+E+N != 700: continue
                          li8 = li7 + [x7]
                          for (X, x6) in rng(maxSX, li8):
                            if x6 != 0 and S+I+X != 600: continue
                            li9 = li8 + [x6]
                            maxGH = 801 - 3*mi if sum(li9) == 7 else ma
                            for (GH, x8) in rng(maxGH, li9):
                              if x8 != 0 and E+I+GH+T != 800: continue
                              li10 = li9 + [x8]
                              maxHR = 301 - 4*mi if sum(li10) == 8 else ma
                              for (HR, x3) in rng(maxHR, li10):
                                if x3 != 0 and T+HR+E+E != 300: continue
                                li11 = li10 + [x3]
                                maxUR = 401 - 3*mi if sum(li11) == 9 else ma
                                for (UR, x4) in rng(maxUR, li11):
                                  if x4 != 0 and F+O+UR != 400: continue
      
                                  r = tuple(li11 + [x4])
                                  if sum(r) != 10: continue  
                                  # only report unique bits
                                  if r not in bits:
                                    report()
                                    bits.add(r)
                                    
      # ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE TEN ELEVEN TWELVE
      # 100 200   300  400  500 600   700   800  125 100   1100   1200
      #    O   N   E   T   W   L  HR   F  UR   I   V   S   X  GH
      #   25  25  50  25 550 150 175  50 325  25 375 200 375 700 
      

      Like

      • Jim Randell 5:17 pm on 11 October 2020 Permalink | Reply

        @Frits: The fact the FOUR cannot be one of the incorrect numbers is one of the conditions mentioned in the puzzle text.

        Like

    • GeoffR 8:56 am on 12 October 2020 Permalink | Reply

      @Frits: I never used the fact that FOUR cannot be one of the incorrect numbers.
      I only spelt out a condition in the teaser as part of the programme ie F+O+U+R = 400.
      I do not think my programme needs adapting – is OK as the original posting.

      Like

  • Jim Randell 12:59 pm on 24 September 2020 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2756: Terrible teens 

    From The Sunday Times, 19th July 2015 [link]

    I have allocated a numerical value (possibly negative) to each letter of the alphabet, where some different letters may have the same value. I can now work out the value of any word by adding up the values of its individual letters. In this way NONE has value 0, ONE has value 1, TWO has value 2, and so on up to ELEVEN having value 11. Unfortunately, looking at the words for the numbers TWELVE to NINETEEN, I find that only two have values equal to the number itself.

    Which two?

    [teaser2756]

     
    • Jim Randell 1:01 pm on 24 September 2020 Permalink | Reply

      (See also: Enigma 1602).

      A manual solution:

      From:

      NONE = 0
      ONE = 1

      we see:

      N = –1

      We can write the unknown words in terms of the known words:

      TWELVE = TWO + ELEVENONE = 12
      THIRTEEN = THREE + TEN + IE = 13 + IE
      FOURTEEN = FOUR + TEN + E = 14 + E
      FIFTEEN = FIVE + TEN + FV = 15 + FV
      SIXTEEN = SIX + TEN + E = 16 + E
      SEVENTEEN = SEVEN + TEN + E = 17 + E
      EIGHTEEN = EIGHT + TEN + ET = 18 + ET
      NINETEEN = NINE + TEN + E = 19 + E

      We see the value of TWELVE is fixed as 12, so this is one of the correct unknown words. So there is only one left to find.

      Note if E = 0, then FOURTEEN, SIXTEEN, SEVENTEEN, NINETEEN are all correct, which is not possible, so E ≠ 0 (and they are all incorrect).

      So the possibilities for the other correct word are:

      THIRTEENI = E
      FIFTEENF = V
      EIGHTEENT = E

      In the first case, when THIRTEEN = 13, we have I = E, so we can substitute I with E.

      So, for NINE and EIGHTEEN:

      N = –1
      NENE = 9 ⇒ EE = 11
      EEGHTEEN = EEGHT + EE + N = 8 + 11 – 1 = 18

      So if THIRTEEN is correct, so is EIGHTEEN.

      And if EIGHTEEN = 18, we have T = E, so for THIRTEEN:

      N = –1
      NINE = 9 ⇒ NINEN = 9 – (–1) = 10
      EHIREEEN = EHREE + NINEN = 3 + 10 = 13

      So THIRTEEN and EIGHTEEN are either both correct (impossible) or both incorrect.

      Which means the only remaining viable solution is FIFTEEN = 15, and so F = V.

      Putting together what we already have and solving the equations gives the following values:

      F = –3
      N = –1
      V = –3

      I = 11 – E
      L = 15 – 3E
      O = 2 – E
      S = 11 – 2E
      T = 11 – E
      W = 2E – 11
      X = 3E – 16
      GH = E – 14
      HR = –E – 8
      UR = E + 5

      TWELVE = 12 [CORRECT]
      THIRTEEN = 24 – 2E
      FOURTEEN = 14 + E
      FIFTEEN = 15 [CORRECT]
      SIXTEEN = 16 + E
      SEVENTEEN = 17 + E
      EIGHTEEN = 7 + 2E
      NINETEEN = 19 + E

      Which makes TWELVE and FIFTEEN the other correct words, providing: E ≠ 0, E ≠ 11/2.

      Solution: TWELVE and FIFTEEN are correct.

      Like

    • Frits 4:55 pm on 24 September 2020 Permalink | Reply

      @Jim,

      I like your equation

      TWELVE = TWO + ELEVEN – ONE = 12

       
      # N+O+N+E = 0 and O+N+E = 1 so N = - 1
      #
      # F+O+U+R+T+E+E+N, S+I+X+T+E+E+N, S+E+V+E+N+T+E+E+N and N+I+N+E+T+E+E+N
      # are all incorrect, they are of the form ...+T+E+E+N 
      # where ... already is an equation. T+E+E+N can't be 10 as not all of
      # the 4 numbers can be correct.
      #
      # Remaining correct candidates are:
      # T+W+E+L+V+E, T+H+I+R+T+E+E+N, F+I+F+T+E+E+N and E+I+G+H+T+E+E+N 
      #
      # E+I+G+H+T+E+E+N = 8+E+E+N = 7+E+E, this can never be 18 
      #
      # T+E+N = T+E-1 = 10, so T = 11 - E
      # N+I+N+E = I+E-2 = 9, so I = 11 - E
      # T+H+I+R+T+E+E+N = 3+I+T+N = 2+I+T = 24 - 2E, this can never be 13 
      # so answer must be T+W+E+L+V+E and F+I+F+T+E+E+N
      

      Like

      • Jim Randell 5:15 pm on 24 September 2020 Permalink | Reply

        @Frits: I take it you are assuming the values are integers. It’s a reasonable assumption, although not explicitly stated (and not actually necessary to solve the puzzle).

        Although if we allow fractions in both cases we get E = 11/2, so in this scenario both THIRTEEN = 13 and EIGHTEEN = 18 would be true, and we would have too many correct values.

        The TWO + ELEVEN = TWELVE + ONE equality also cropped up in Enigma 1278 (where fractions were explicitly allowed).

        Also I changed your enclosure to use:

        [code language="text" gutter="false"]
        ...
        [/code]
        

        Which turns off syntax highlighting and line numbers.

        Like

    • John Crabtree 5:30 am on 25 September 2020 Permalink | Reply

      TEN + NONE = NINE + ONE, and so I = T
      and so THIRTEEN + EIGHTEEN = THREE + TEN + (I – E) + EIGHT + TEN +(E – T) = 31
      And so THIRTEEN and EIGHTEEN are both correct, or both incorrect.

      Like

    • GeoffR 8:11 am on 25 September 2020 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
       
      var -25..25: O; var -25..25: N; var -25..25: E;
      var -25..25: T; var -25..25: W; var -25..25: H;
      var -25..25: R; var -25..25: F; var -25..25: U;
      var -25..25: I; var -25..25: V; var -25..25: S;
      var -25..25: X; var -25..25: G; var -25..25: L;
       
      % Numbers NONE .. ELEVEN are all correct 
      constraint N+O+N+E = 0 /\ O+N+E = 1 /\ T+W+O = 2 
      /\ T+H+R+E+E = 3 /\ F+O+U+R = 4 /\ F+I+V+E = 5
      /\ S+I+X = 6 /\ S+E+V+E+N = 7 /\ E+I+G+H+T = 8 
      /\ N+I+N+E = 9 /\ T+E+N = 10 /\ E+L+E+V+E+N = 11;
                
      % Exactly two of TWELVE .. NINETEEN are correct
      constraint sum ( [
      T+W+E+L+V+E == 12, T+H+I+R+T+E+E+N == 13, 
      F+O+U+R+T+E+E+N == 14, F+I+F+T+E+E+N == 15,
      S+I+X+T+E+E+N == 16, S+E+V+E+N+T+E+E+N == 17, 
      E+I+G+H+T+E+E+N == 18, N+I+N+E+T+E+E+N == 19] ) == 2;
      
      solve satisfy;
       
      output [ "TWELVE = ", show (T+W+E+L+V+E), 
               ", THIRTEEN = ", show(T+H+I+R+T+E+E+N),
               ", FOURTEEN = ", show(F+O+U+R+T+E+E+N), 
               ", FIFTEEN = ", show(F+I+F+T+E+E+N),
               ",\nSIXTEEN = ", show(S+I+X+T+E+E+N), 
               ", SEVENTEEN = ", show(S+E+V+E+N+T+E+E+N),
               ", EIGHTEEN = ", show(E+I+G+H+T+E+E+N), 
               ", NINETEEN = ", show(N+I+N+E+T+E+E+N)  ];
      
      % TWELVE = 12, THIRTEEN = 30, FOURTEEN = 11, FIFTEEN = 15,
      % SIXTEEN = 13, SEVENTEEN = 14, EIGHTEEN = 1, NINETEEN = 16
      
      % Answer: Only numbers TWELVE and FIFTEEN are correct
      
      
      

      Like

  • Jim Randell 9:10 am on 27 August 2020 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2681: Inconsequential 

    From The Sunday Times, 9th February 2014 [link]

    An “arithmetic” sequence is one in which each number is a fixed amount more than the previous one. So, for example, 10, 29, 48, … is an arithmetic sequence. In this case its ninth number is 162, which happens to be divisible by 9. I have in mind another arithmetic sequence whose ninth number is divisible by 9. This time it starts with two three-figure numbers, but in this case I have consistently replaced digits by letters, with different letters used for different digits.

    The arithmetic sequence then begins ONE, TWO, …, and its ninth number is NINE.

    To win, find the number to WIN.

    [teaser2681]

     
    • Jim Randell 9:10 am on 27 August 2020 Permalink | Reply

      The common difference is (TWOONE), and there are 8 instances of the common difference between ONE and NINE.

      So, we can solve this puzzle straightforwardly using the [[ SubstitutedExpression() ]] solver from the enigma.py library.

      The following run file executes in 110ms.

      Run: [ @repl.it ]

      #!/usr/bin/env python -m enigma -r
      
      SubstitutedExpression
      
      "div(NINE - ONE, TWO - ONE) = 8"
      "div(NINE, 9) > 0"
      
      --answer="WIN"
      

      Solution: WIN = 523.

      The progression is: ONE = 631, TWO = 956, …, NINE = 3231.

      The common difference is: TWOONE = 325.

      Like

    • GeoffR 10:39 am on 27 August 2020 Permalink | Reply

      % A Solution in MiniZinc 
      include "globals.mzn";
      
      var 1..9: O; var 1..9: N; var 1..9: E;
      var 1..9: T; var 1..9: W; var 1..9: I;
      
      constraint all_different ([O, N, E, T ,W, I]);
      
      var 100..999: ONE = 100*O + 10*N + E;
      var 100..999: TWO = 100*T + 10*W + O;
      var 100..999: WIN = 100*W + 10*I + N;
      var 1000..9999: NINE = 1000*N + 100*I + 10*N + E;
      
      % Define 9th term of series
      constraint NINE = ONE + 8 * (TWO - ONE)
       /\ NINE mod 9 == 0;
      
      solve satisfy;
      
      output [ "Series is " ++ show(ONE) ++ "," ++ show(TWO) ++ 
      "..." ++ show(NINE) ++ "\n" ++ "WIN = " ++ show(WIN)]
      
      % Series is 631,956...3231
      % WIN = 523
      % ----------
      % ==========
      
      
      

      Like

    • GeoffR 11:02 am on 27 August 2020 Permalink | Reply

      
      from itertools import permutations
      
      for Q in permutations(range(1,10), 6):
        O, N, E, T, W, I = Q
        ONE, TWO = 100*O + 10*N + E, 100*T + 10*W + O
        WIN = 100*W + 10*I + N
        NINE = 1010*N + 100*I + E
        if NINE == ONE + (TWO - ONE) * 8 and NINE % 9 == 0:
          print(f"ONE = {ONE}, TWO = {TWO}, NINE = {NINE}, WIN = {WIN}")
      
      # ONE = 631, TWO = 956, NINE = 3231, WIN = 523
      
      

      Like

      • Frits 1:26 pm on 27 August 2020 Permalink | Reply

        @GeoffR, shouldn’t you allow for E, I and W to be zero as well?

        Like

    • Frits 1:20 pm on 27 August 2020 Permalink | Reply

       
      # elements in range <r> unequal to values of D[i]
      def domain(i, r):
        vals = set()
        for s in D[i]:
          # use globals() iso eval()
          vals.add(globals()[s])
        return [x for x in r if x not in vals]
      
      # set up dictionary of for-loop iterator names
      def init(li):
        for i in range(1,len(li)):
          D[li[i]] = li[0:i]
          
      # concatenate list of integers 
      to_num = lambda *args: int("".join(map(str, args)))    
      
      
      D = {}
      init(['O','N','E','T','W'])
      
      
      for O in range(1,10):
        for N in domain('N', range(1,10)):
          for E in domain('E', range(0,10)):
            ONE = to_num(O,N,E)
            for T in domain('T', range(1,10)):
              if T > O:  
                for W in domain('W', range(0,10)):
                  TWO = to_num(T,W,O)
                  unit = TWO - ONE
                  units8 = 8*unit + ONE
                  if units8 % 9 != 0 or units8 < 1000: continue
                  
                  s = str(units8)
                  if s[3] != str(E): continue 
                  if s[0] != str(N) or s[2] != str(N): continue 
                  # check letter I
                  if int(s[1]) in {O,N,E,T,W}: continue
            
                  WIN = str(W)+s[1]+str(N)
                  print("WIN ONE TWO NINE")
                  print(WIN, ONE, TWO, units8)
      
      # WIN ONE TWO NINE
      # 523 631 956 3231
      

      Like

    • GeoffR 1:47 pm on 27 August 2020 Permalink | Reply

      @Frits: In theory maybe, but it would not have made any difference in practice.
      As the title of the teaser says – “Inconsequential” ?

      Like

  • Jim Randell 4:38 pm on 21 August 2020 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 3022: Sporty set 

    From The Sunday Times, 23rd August 2020 [link]

    There are 100 members of my sports club where we can play tennis, badminton, squash and table tennis (with table tennis being the least popular). Last week I reported to the secretary the numbers who participate in each of the four sports. The digits used overall in the four numbers were different and not zero.

    The secretary wondered how many of the members were keen enough to play all four sports, but of course he was unable to work out that number from the four numbers I had given him. However, he used the four numbers to work out the minimum and the maximum possible numbers playing all four sports. His two answers were two-figure numbers, one being a multiple of the other.

    How many played table tennis?

    [teaser3022]

     
    • Jim Randell 11:26 pm on 21 August 2020 Permalink | Reply

      If the numbers that participate in each sport are A, B, C, D (in increasing order), and the sum of these values is T.

      Then the maximum size of their intersection is easily determined – it is the size of the smallest set, in this case A; (or as John points out below, if all 100 members participate in at least one of the available sports, the maximum is: floor((T – 100) / 3), if this is smaller than A).

      So our maximum is: min(A, floor((T – 100) / 3).

      The minimum size of the intersection is trickier to determine. But if we have a family of subsets S[i] of some universal set U, then the minimum size of the intersection is given by:

      X = \left|\bigcap_{i=1}^{n}S_i\right| \medskip \newline N = |U| \medskip \newline T = \sum_{i=1}^{n}|S_i| \medskip \newline \newline X \geq 0 \medskip \newline X \geq T - (n - 1)N

      So in this case the minimum size is: max(0, T – 300).

      The following Python program runs in 138ms.

      Run: [ @repl.it ]

      from enigma import subsets, irange, diff, nconcat, divf, div, multiset, printf
      
      # generate k increasing 2-digit numbers from the supplied (increasing) digits
      def generate(k, ds, ns=[]):
        # choose the tens digits
        for d10s in subsets(ds, size=k, select="C"):
          # choose the units digits
          for d1s in subsets(diff(ds, d10s), size=k, select="P"):
            # construct the numbers
            yield tuple(nconcat(z) for z in zip(d10s, d1s))
      
      # collect solutions (size of the smallest set)
      ss = multiset()
      
      # choose increasing numbers of participants for each of the 4 sports
      for ns in generate(4, irange(1, 9)):
        T =sum(ns)
        # maximum size of intersection
        M = min(ns[0], divf(T - 100, 3))
        # minimum size of intersection
        m = max(0, T - 300)
      
        # min is a 2-digit numbers
        if m < 10: continue
        # M is a multiple of m
        k = div(M, m)
        if k is None or not(k > 1): continue
      
        printf("[ns={ns}; min={m} max={M} k={k}]")
        ss.add(ns[0])
      
      # output solutions
      for (k, v) in ss.most_common():
        printf("min(ns) = {k} [{v} solutions]")
      

      Solution: 65 played table tennis.

      The other three sports are represented by the numbers (70, 80, 90) + (1, 3, 4) assembled in some order.

      The minimum size of the intersection is 13, and the maximum size is 65 (= 5×13).

      Like

      • Jim Randell 8:54 am on 23 August 2020 Permalink | Reply

        We don’t need to work out the actual sizes of the 3 larger sets, to calculate the sum of their sizes. We only need to know what the tens and units digits are.

        So here is a faster version of my program. You can also pass a command line argument to specify if members playing zero sports are allowed (1) or not (0). It runs in 54ms.

        Run: [ @repl.it ]

        from enigma import irange, subsets, diff, divf, div, arg, printf
        
        # set z to:
        # 0 - if members playing 0 sports are not allowed
        # 1 - if members playing 0 sports are allowed
        z = arg(0, 0, int)
        
        # allowable digits
        digits = irange(1, 9)
        
        # choose the 10s digits for the sets
        for d10s in subsets(digits, size=4):
          t10 = sum(d10s) * 10
          if t10 < 280: continue
        
          # choose the units digits
          for d1s in subsets(diff(digits, d10s), size=4):
            # size of the union of the sets
            T = t10 + sum(d1s)
            # minimum size of intersection
            m = T - 300
            # is a 2 digit number
            if not(9 < m < 100): continue
        
            # choose a units digit for the smallest set
            for d1 in d1s:
              # maximum size of intersection
              A = 10 * d10s[0] + d1
              M = (A if z else min(A, divf(T - 100, 3)))
              # is a multiple of m
              k = div(M, m)
              if k is None or not(k > 1): continue
        
              # output solution
              printf("min(ns) = {A} [min={m} max={M} k={k}; ns = {d10s} x {d1s}] [z={z}]")
        

        Like

        • Frits 10:11 pm on 24 August 2020 Permalink | Reply

          Very nice solution.

          “if t10 Don’t we already know d10s must always be equal to (6, 7, 8, 9)?

          if it is (5, 7, 8, 9) then t10 = 290 and sum(d1s) <= 15 (fi 2,3,4,6)
          So T <= 305 which is not acceptable.

          Like

          • Frits 12:12 pm on 25 August 2020 Permalink | Reply

             
            from enigma import irange, diff, div, printf
            
            # minimum A + B + C + D - 300 > 9 
            # so 10s digits must be (6,7,8,9)
            
            # (A + B + C + D - 100) / 3 >= 70
            # which is bigger than A, so maximum M equals A
            
            # allowable digits for units
            digits = irange(1, 5)
            
            # d is the units digit which is not used in A, B, C and D
            for d in digits:
              # sum of A, B, C and D
              T = 315 - d
              # minimum size of intersection
              m = T - 300
              # choose a units digit for the smallest set
              d1s = diff(digits, (d,))
              for d1 in d1s:
                # maximum size of intersection (is A)
                M = 60 + d1    
                # is a multiple of m
                k = div(M, m)
                if k is None or not(k > 1): continue
            
                # output solution
                printf("min(ns) = {M} [min={m} max={M} k={k}; ns = (6,7,8,9) x {d1s}]")
            

            Like

          • Jim Randell 12:51 pm on 25 August 2020 Permalink | Reply

            @Frits: It looks like your comment didn’t make it through WordPress unscathed. Usually this happens when you use < and > in a comment. WordPress sees everything in between as an HTML tag, and then doesn’t recognise it, so it throws it away. You can use &lt; and &gt; to make < and > appear correctly. (If you want to send me a corrected version, I’ll fix it up).

            It looks like you are asking about line 9 of my code. It’s really just a quick bit of early rejection so the code doesn’t go on to evaluate cases that can’t possibly work, and the program works just as well (and not much slower) without it.

            I reasoned that if (T – 300) is to be a 2-digit number, then (T – 300) > 9, so: T > 309. The maximum possible value of the units digits of the four numbers that make up T is 6+7+8+9 = 30, so the sum of the tens parts of the numbers must be more than 309 – 30 = 279, which is what that test does, and it cuts the number of cases considered drastically.

            With a bit more work we can see that there is only one possible set of values for the tens digits, and we are half way towards a manual solution.

            When programming a solution there is always an amount of choice on how much analysis is necessary to get a program that runs in a reasonable time. But normally if it doesn’t make much difference to the run time I let the computer do the checks.

            Like

            • Frits 6:26 pm on 25 August 2020 Permalink | Reply

              @Jim, Thanks.

              I like to make use of –> which WordPress doesn’t like.

              Yes, I was trying to understand line 9 of your code and wondered why you had chosen this (for me suboptimal) limit.

              I still need to verify for myself that the minimum and maximum formula are indeed correct.

              Is there not an easy way of allowing us to edit our own posts (as it is linked to an email address)?
              Many times directly after posting I see errors/improvements.

              Like

              • Jim Randell 10:37 am on 26 August 2020 Permalink | Reply

                @Frits: Sadly WordPress doesn’t treat comments at the same level as posts. Even for logged-in users. So the only way they can be edited is by a site administrator (who can make changes to any aspect of the site).

                It is the main reason I sometimes think about moving away from WordPress, but I have not yet found a suitable alternative.

                At one point I had hoped that WordPress would implement some level of editing (or even just the basic courtesy of previewing a comment before it is posted), but it has become clear that they really have no interest in this.

                On the upside the system does make it relatively easy to manage a site, and has remained (mostly) problem free for the last 8 years.

                In the meantime, the best I can offer as site administrator is to make amendments to comments if you send me any revisions.

                Like

    • Frits 2:38 pm on 22 August 2020 Permalink | Reply

      Making use of Jim’s analysis (and Brian’s at https://brg.a2hosted.com/?page_id=7024#comment-2431) .

       
      from enigma import  SubstitutedExpression, irange 
      
      # AB = table tennis
      # minimum played is AB + CD + EF + GH - 300
      # maximum played is AB
      # maximum = X * minimum
      
      p = SubstitutedExpression([
          "GH > EF", 
          "EF > CD", 
          "CD > AB", 
          "AB % (AB + CD + EF + GH - 300) == 0", 
          "(AB + CD + EF + GH - 300) > 10",
         ], 
          verbose=0, 
          answer="AB,CD,EF,GH",
          digits=irange(1, 9))
        
      # Print answers
      for (_, ans) in p.solve(verbose=0):
        print(f"{ans} minimum={sum(ans)-300} maximum={ans[0]}")
      
      # Output:
      #
      # (65, 74, 83, 91) minimum=13 maximum=65
      # (65, 73, 84, 91) minimum=13 maximum=65
      # (65, 74, 81, 93) minimum=13 maximum=65
      # (65, 71, 84, 93) minimum=13 maximum=65
      # (65, 73, 81, 94) minimum=13 maximum=65
      # (65, 71, 83, 94) minimum=13 maximum=65
      

      Like

    • GeoffR 3:25 pm on 22 August 2020 Permalink | Reply

      @Frits: You probably don’t know, but there is a sort of convention in Brian/Jim’s groups for programmed solutions with the answer not to be published early. This helps to minimise people entering the Sunday Times Prize Draw competition if they are just looking for the answer to take part in the draw, without attempting the puzzle.

      Like

      • Frits 4:46 pm on 22 August 2020 Permalink | Reply

        @GeoffR.
        Thanks. I keep that in mind.

        Like

    • John Crabtree 6:22 pm on 23 August 2020 Permalink | Reply

      The maximum is not A, but min(A, (A + B + C + D – 100) / 3)

      Like

      • Jim Randell 8:45 pm on 23 August 2020 Permalink | Reply

        @John: You are, of course, quite right. Thanks.

        I originally came up with the maximum without making the assumption that every member participated in at least one sport. But then I used that assumption to determine the minimum, and I neglected to revisit the maximum.

        I have provided code above that allows you to select whether participation in zero sports is allowed or not.

        Like

        • Jim Randell 10:08 pm on 26 August 2020 Permalink | Reply

          Actually, it looks like it doesn’t matter if we allow members who participate in 0 sports or not. The possible numbers presented to the secretary are the same in both cases, and so is the answer to the puzzle.


          The minimum intersection size is given by: max(0, T – 300).

          And we require this to be a 2 digit number.

          So we must have:

          T – 300 ≥ 10
          T ≥ 310

          And T is the sum of four 2-digit numbers, all with different non-zero digits.

          The largest we can make the units digits of our four numbers is 6 + 7 + 8 + 9 = 30.

          So the tens digits have to sum to at least 28, so the numbers are of the form:

          4a + 7b + 8c + 9d = 280 + (a + b + c + d)
          5a + 6b + 8c + 9d = 280 + (a + b + c + d)
          5a + 7b + 8c + 9d = 290 + (a + b + c + d)
          6a + 7b + 8c + 9d = 300 + (a + b + c + d)

          In the first case the maximum value of (a + b + c + d) is (6 + 5 + 3 + 2) = 16, giving a maximum possible total of 296, so this is not feasible.

          In the second case the maximum value of(a + b + c + d) is (7 + 4 + 3 + 2) = 16, giving a maximum possible total of 296, so this is not feasible.

          In the third case the maximum value of(a + b + c + d) is (6 + 4 + 3 + 2) = 15, giving a maximum possible total of 305, so this is not feasible.

          In the fourth case the maximum value of (a + b + c + d) is (5 + 4 + 3 + 2) = 14, giving a maximum possible total of 314, so this is feasible.

          So the four numbers must be of the form: 6a, 7b, 8c, 9d

          The size of the smallest set is thus: 61, 62, 63, 64, or 65.

          And the smallest possible value of floor((T – 100) / 3) = floor((310 – 100) / 3) = 70.

          So, in this case, the maximum intersection size is always the same as the size of the smallest set, whether we allow participants of zero sports or not.

          Like

  • Jim Randell 12:05 pm on 20 August 2020 Permalink | Reply
    Tags: by: Victor Bryant,   

    Teaser 2551: Take nothing for granted 

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

    In arithmetic, the zero has some delightful properties. For example:

    ANY + NONE = SAME
    X . ZERO = NONE

    In that sum and product, digits have been replaced with letters, different letters being used for different digits. But nothing should be taken for granted: here the equal signs are only approximations as, in each case, the two sides may be equal or differ by one.

    What is your NAME?

    [teaser2551]

     
    • Jim Randell 12:06 pm on 20 August 2020 Permalink | Reply

      We can use the [[ SubstitutedExpression() ]] solver from the enigma.py library to tackle this puzzle. Unfortunately there are two possible solutions.

      The following run file executes in 159ms.

      Run: [ @repl.it ]

      #!/usr/bin/env python -m enigma -r
      
      SubstitutedExpression
      
      "abs(ANY + NONE - SAME) < 2"
      "abs(X * ZERO - NONE) < 2"
      
      --answer="NAME"
      #--answer="SYNONYM" # for a unique answer
      

      Solution: The two possible values for NAME are: 7146 and 7543.

      The possible sums are:

      170 + 7976 = 8146; 6 × 1329 ≈ 7973
      570 + 7973 = 8543; 3 × 2659 ≈ 7976

      In both cases the addition is exact, but the multiplication sums are off by 1.

      If instead, the puzzle had asked the value of SYNONYM the answer would have been unique (= 8079704).

      Like

    • GeoffR 3:07 pm on 20 August 2020 Permalink | Reply

      % A Solution in MiniZinc 
      include "globals.mzn";
      
      var 1..9:A; var 1..9:N; var 0..9:Y; 
      var 0..9:O; var 0..9:E; var 1..9:X;
      var 1..9:Z; var 0..9:R; var 1..9:S;  
      var 0..9:M;
      
      constraint all_different([A,N,Y,O,E,X,Z,R,S,M]);
      
      var 100..999: ANY = 100*A + 10*N + Y;
      var 1000..9999: NONE = 1010*N + 100*O + E;
      var 1000..9999: SAME = 1000*S + 100*A + 10*M + E;
      var 1000..9999: ZERO = 1000*Z + 100*E + 10*R + O;
      var 1000..9999: NAME = 1000*N + 100*A + 10*M + E;
      
      constraint ANY + NONE == SAME \/ANY + NONE == SAME + 1
      \/ ANY + NONE == SAME - 1;
      
      constraint X * ZERO == NONE \/  X * ZERO == NONE + 1
      \/  X * ZERO == NONE - 1;
      
      solve satisfy;
      
      output ["NAME = " ++ show(NAME)
      ++ "\n Sum is " ++ show(ANY) ++ " + " ++ show(NONE) 
      ++ " = " ++ show(SAME)
      ++ "\n Product is " ++ show(X) ++ " * " ++ show(ZERO)
      ++ " = " ++ show(NONE)
      ++ "\n SYNONYM = " ++ show(S),show(Y),show(N),show(O),
      show(N),show(Y),show(M)];
      
      % NAME = 7543
      %  Sum is 570 + 7973 = 8543
      %  Product is 6 * 1329 = 7973
      %  SYNONYM = 8079704
      % ----------
      % NAME = 7146
      %  Sum is 170 + 7976 = 8146
      %  Product is 3 * 2659 = 7976
      %  SYNONYM = 8079704
      % ----------
      % ==========
      
      
      
      

      Like

  • Jim Randell 5:12 pm on 4 August 2020 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2700: Spell check 

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

    This is Teaser 2700. The number 2700 is not particularly auspicious,  but it does have one unusual property. Notice that if you write the number in words and you also express the number as a product of primes you get:

    TWO THOUSAND SEVEN HUNDRED = 2 2 3 3 3 5 5

    The number of letters on the left equals the sum of the factors on the right! This does happen occasionally. In particular it has happened for one odd-numbered Teaser in the past decade.

    What is the number of that Teaser?

    [teaser2700]

     
    • Jim Randell 5:13 pm on 4 August 2020 Permalink | Reply

      There is a handy utility function [[ int2words() ]] in the enigma.py library, that converts a number to it’s “standard” English equivalent.

      This Python program runs in 53ms.

      Run: [ @repl.it ]

      from enigma import irange, int2words, factor, printf
      
      # check odd numbers
      for n in irange(2699, 1, step=-2):
        # count the letters
        s = int2words(n)
        c = sum(x.isalpha() for x in s)
        # sum the factors
        fs = factor(n)
        t = sum(fs)
        if c == t:
          printf("{n} = \"{s}\", {c} letters; factors = {fs}, sum = {t}")
          break
      

      Solution: Teaser 2401.

      2401 = “two thousand four hundred and one”, which has 28 letters, and:

      2401 factorises as (7, 7, 7, 7), which sums to 28.

      Earlier odd numbers with the same property: 1725, 1029, 693, 585, 363, 153, 121, 25.

      The next time it will occur is at 3087.

      Teaser 3087 should be published in November 2021.

      Like

  • Jim Randell 6:00 pm on 27 July 2020 Permalink | Reply
    Tags: by: Victor Bryant   

    Brainteaser 1312: A Times Teaser is … 

    From The Sunday Times, 25th October 1987 [link]

    The five teams in our local league each play each other once in the course of the season. After seven of the games this season a league table was calculated, and part of it is shown below (with the teams in alphabetical order). Three points are awarded for a win and point [to each side] for a draw. In our table the digits 0 to 6 have been consistently replaced by letters.

    Over half the matches so far have had a score of 1-1.

    List all the results of the games (teams and scores).

    [teaser1312]

     
    • Jim Randell 6:01 pm on 27 July 2020 Permalink | Reply

      This Python program uses the [[ Football() ]] helper class from the enigma.py library. It runs in 84ms.

      Run: [ @repl.it ]

      from enigma import Football, irange, update
      
      # scoring system
      football = Football(points=dict(w=3, d=1))
      
      # available digits
      digits = set(irange(0, 6))
      
      # the columns of the table
      (table, gf, ga) = (dict(w="??T??", d="?TE??", l="AIA??", points="?SR?S"), "?MS?I", "?EE??")
      
      # allocate match outcomes
      for (ms, d) in football.substituted_table(table, vs=digits):
      
        # 7 of the (10) games have been played
        if not(sum(m != 'x' for m in ms.values()) == 7): continue
      
        # choose a value for M
        for M in digits.difference(d.values()):
          d_ = update(d, [('M', M)])
      
          # allocate scorelines
          for ss in football.substituted_table_goals(gf, ga, ms, d=d_, teams=[1, 2]):
      
            # over half (4 or more) of the matches were 1-1
            if not(sum(s == (1, 1) for s in ss.values()) > 3): continue
      
            # output solution
            football.output_matches(ms, ss, teams="CFRTU", d=d_)
      

      Solution: The results in the 7 played matches are: C vs F = 1-1; C vs R = 1-1; F vs R = 0-1; F vs T = 4-0; F vs U = 0-1; R vs T = 1-1; R vs U = 1-1.

      The C vs T, C vs U, T vs U matches are yet to be played.

      Like

    • Frits 2:01 pm on 29 July 2020 Permalink | Reply

      I tried to solve the problem with a SubstitutedExpression.
      I succeeded but had to solve all major logic myself.

      #          WON  DRAWN LOST FOR AGAINST POINTS
      # CITY      C*    G*   A    N*    P*     V*
      # FOREST    B*    T    I    M     E      S 
      # ROVERS    T     E    A    S     E      R
      # TOWN      D*    H*   K*   O*    Q*     W*
      # UNITED    F*    J*   L*   I     U*     S
      #
      # TEASRCBDFGHIJKLMNOPQUVW
      # 13046010121211052125121
      #
      
      # T * 3 + E = R and E != R ---> T > 0 
      # A+I+A < 4 --> A = 0 or I = 0 --> E > 0
      # E > 0 and R < 7 and A < 2 
      # --> T = 1 and A = 0 --> sorted(I,E) = (2,3)
      # --> sorted(S,R,M) = (4,5,6)
      # sorted(I,E) = (2,3) but also E >= I --> I = 2, E = 3
      # B * 3 + T = S --> B = 1, S = 4 --> sorted(R,M) = (5,6) 
      # Forest: 1 won, 1 drawn, 2 lost, against 3 
      # --> they lost twice with 0-1 and drew 1-1 --> they won (M-1)-0
      # --> 1 won, 2 lost thus in total we have 4 draws and 3 wins/losses
      # Rovers: 1 won, 3 drawn, 0 lost, goals made 4, points R 
      # --> R = 6, M = 5
      # Rovers - Forest: no draw (otherwise there are 4 win/loss games)
      # --> Rovers - Forest: 1-0 
      # --> Rovers - City: 1-1
      # --> Rovers - Town: 1-1
      # --> Rovers - United: 1-1
      # United drew 1-1 against Rovers, made 2 goals and has 4 points 
      # --> they also had a win
      # --> United - Forest: 1-0, F = 1, J = 1, L = 0, U = 1
      # Forest and Rovers both played 4 times (total 7 games)
      # --> City, Town and United didn't play each other but played twice
      # --> City didn't lose (A = 0) 
      # --> City - Forest 1-1 --> N = 2, P = 2
      # Town played 2 games, one draw only 
      # --> Town - Forest: 0-4
      

      I wonder if in MiniZinc core van be achieved.

      Like

  • Jim Randell 12:11 pm on 14 July 2020 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 2672: 11, 12, 13 … 

    From The Sunday Times, 6th December 2013 [link]

    On Wednesday the date will be 11.12.13. To celebrate this fact I have found three numbers with the lowest divisible by 11, another divisible by 12, and the remaining number divisible by 13. Furthermore, appropriately, the sum of the three numbers is 2013. Overall the three numbers use nine digits with no digit used more than once.

    What (in increasing order) are my three numbers?

    [teaser2672]

     
    • Jim Randell 12:13 pm on 14 July 2020 Permalink | Reply

      The following Python program runs in 61ms.

      Run: [ @repl.it ]

      from enigma import irange, is_duplicate, printf
      
      # choose the first number (a multiple of 11)
      for n1 in irange(11, 2013, step=11):
        # it has no repeated digits
        s1 = str(n1)
        if is_duplicate(s1): continue
        # and choose a larger second number (a multiple of 12)
        for n2 in irange(n1 + 12 - (n1 % 12), 2013 - n1, step=12):
          # n1 and n2 don't share digits
          s2 = str(n2)
          if is_duplicate(s1, s2): continue
          # and determine n3
          n3 = 2013 - (n1 + n2)
          # n3 is larger than n1, 
          if not(n1 < n3): continue
          # and a multiple of 13
          if n3 % 13: continue
          # and between them the numbers have 9 digits, all different
          s = s1 + s2 + str(n3)
          if len(s) != 9 or is_duplicate(s): continue
          # output solution
          printf("{ns}", ns=sorted([n1, n2, n3]))
      

      Solution: The three numbers are: 495, 702, 816.

      Like

    • GeoffR 5:44 pm on 14 July 2020 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
       
      var 0..9:A; var 0..9:B; var 0..9:C; 
      var 0..9:D; var 0..9:E; var 0..9:F; 
      var 0..9:G; var 0..9:H; var 0..9:I; 
      
      % Three numbers are ABC, DEF and GHI
      var 100..999: ABC = 100*A + 10*B + C;
      var 100..999: DEF = 100*D + 10*E + F;
      var 100..999: GHI = 100*G + 10*H + I;
      
      constraint A != 0 /\ D != 0 /\ G != 0;
      constraint all_different ([A,B,C,D,E,F,G,H,I]);
      
      constraint ABC mod 11 == 0 /\ DEF mod 12 == 0  
      /\ GHI mod 13 == 0;
      
      constraint ABC + DEF + GHI == 2013;
      
      solve minimize (ABC);
      
      output ["ABC = " ++ show (ABC) ++ ", DEF = " ++ show(DEF) 
      ++ ", GHI = " ++ show(GHI)];
      
      % ABC = 495, DEF = 816, GHI = 702  
      % or 495, 702, 816 in increasing order
      % ----------
      % ==========
      
      
      

      Like

      • Jim Randell 5:12 pm on 15 July 2020 Permalink | Reply

        Providing we know the numbers all have 3 digits.

        But the smallest number is a multiple of 11, with no repeated digits, so must be at least 132 (unless it is 0). So the other two numbers must both be at least 3 digits, but between them they have only 9 digits, so they must indeed be all 3-digit numbers.

        (If the first number is 0, the other two must both be 4-digit numbers, but to add up to 2013, they would both have to start with 1, so this is disallowed).

        #!/usr/bin/env python -m enigma -r
        
        SubstitutedExpression
        
        "ABC % 11 = 0"
        "DEF % 12 = 0"
        "GHI % 13 = 0"
        
        "ABC < DEF"
        "ABC < GHI"
        
        "ABC + DEF + GHI = 2013"
        
        --answer="ordered(ABC, DEF, GHI)"
        

        Like

  • Jim Randell 5:14 pm on 3 July 2020 Permalink | Reply
    Tags: by: Victor Bryant   

    Teaser 3015: Quid pro quo 

    From The Sunday Times, 5th July 2020 [link]

    In Readiland the unit of currency is the quid. Notes are available in two denominations and with these notes it is possible to make any three-figure number of quid. However, you need a mixture of the denominations to make exactly 100 quid. Furthermore, there is only one combination of denominations that will give a total of 230 quid.

    What are the two denominations?

    [teaser3015]

     
    • Jim Randell 5:32 pm on 3 July 2020 Permalink | Reply

      See also: Enigma 228, Enigma 1194, Enigma 1154.

      If we suppose the denominations are x and y (where gcd(x, y) = 1). Then the largest amount that cannot be made using the denominations is given by F(x, y) = xy – x – y.

      Both denominations are needed to make 100, so they must both be less than 100, and neither can be a divisor of 100.

      The following Python 3 program runs in 67ms.

      Run: [ @repl.it ]

      from enigma import coprime_pairs, express, printf
      
      # consider denominations x, y
      for (x, y) in coprime_pairs(97):
        if 100 % x == 0 or 100 % y == 0: continue
      
        # largest inexpressible amount is < 100
        if not(x * y - x - y < 100): continue
      
        # there is exactly 1 way to express 230
        e230s = list(express(230, (x, y)))
        if len(e230s) != 1: continue
      
        # output solution
        printf("x={x} y={y}; 100 -> {e100s}, 230 -> {e230s}", e100s=list(express(100, (x, y))))
      

      Solution: The two denominations are 3 quid and 49 quid.

      The largest amount that cannot be made using these denominations is 95 quid. All larger amounts are possible.

      The only way to make 100 quid is 17× 3 quid + 1× 49 quid.

      The only way to make 230 quid is 44× 3 quid + 2× 49 quid.


      Manually:

      The largest integer that is not expressible in k different ways using denominations x, y is given by:

      F[k](x, y) = kxy − x – y

      So we need to find co-prime values for x, y, less than 100 that are not divisors of 100, and the following hold:

      F[1](x, y) < 100
      F[2](x, y) ≥ 230

      This will ensure that all 3-digit amounts are expressible, and that to make 100 requires both denominations. All that remains for each pair of candidate denominations is to determine if there is a unique expression for 230.

      Given a value for x we can use the inequalities to find a range of viable values for y.

      Starting with x = 3, gives y = 47 .. 51 and only y = 47, 49 are co-prime with x.

      230 can be expressed in two ways using (3, 47): 230 = 14× 3 + 4× 47 = 61× 3 + 1× 47.

      230 can be expressed in only one way using (3, 49): 230 = 44× 3 + 2× 49.

      So (3, 49) is a viable solution.

      For x = 4, we get only y = 34, but x divides 100, so this is not a candidate solution.

      And for larger values of x there are no possibilities for y, so we are done.

      Like

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