Design a site like this with WordPress.com
Get started

Tagged: by: Stephen Hogg Toggle Comment Threads | Keyboard Shortcuts

  • Jim Randell 4:34 pm on 23 December 2022 Permalink | Reply
    Tags: by: Stephen Hogg   

    Teaser 3144: Beware the jabbers’ clock, my son! 

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

    On the NHS vaccine booking website, my queue position updated every minute. My initial position was an odd value in the 9000s. This value had four different digits, and its leftmost digit and just two others in it were factors of it. Curiously, these properties applied to each of the decreasing four-figure values after the next eight updates. I also noticed that no value had a digit in common with its predecessor, no zeroes occurred before the fourth update and no nines after this.

    My son, told just the above, found all the possible values from which a complete set could be selected. From these he was certain of more than one of the nine queue positions.

    Give these certain positions in displayed order.

    This completes the archive of puzzles from 2022.

    [teaser3144]

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

      I took “no zeroes occurred before the fourth update …” to mean there are no zeros in the first 4 numbers in the sequence (but it doesn’t imply that there necessarily is a zero digit in the 5th number in the sequence). And “… no nines after this” to mean that there are no nines in last 5 numbers of the sequence (and again, not implying that there is a 9 digit in 4th number in the sequence). Although I think that you can use a slightly different interpretation of these conditions and still come up with the same answer.

      This Python program runs in 307ms.

      Run: [ @replit ]

      from enigma import (irange, subsets, nconcat, intersect, printf)
      
      # does <x> divide <n>?
      divides = lambda n, x: x != 0 and n % x == 0
      
      # generate candidate numbers
      def generate():
        for (A, B, C, D) in subsets(irange(0, 9), size=4, select="P"):
          if A == 0: continue
          n = nconcat(A, B, C, D)
          # n is divisible by A and exactly 2 of B, C, D
          if divides(n, A) and sum(divides(n, d) for d in (B, C, D)) == 2:
            yield (A, B, C, D)
      
      # find viable sequences from <ns>
      def solve(ns, ss=[]):
        k = len(ss)
        # are we done?
        if k == 9:
          yield ss
        else:
          # choose the next number
          for (i, n) in enumerate(ns, start=1):
            # there are no 0s before the 4th update
            if k < 4 and 0 in n: continue
            # there are no 9s after the 3rd update
            if k > 3 and 9 in n: continue
            if k == 0:
              # the first number is odd, and starts with 9
              if n[0] < 9: break
              if n[-1] % 2 != 1: continue
            else:
              # subsequent numbers
              # have no digits in common with the previous number
              if len(set(n + ss[-1])) != 8: continue
            # looks good
            yield from solve(ns[i:], ss + [n])
      
      # collect candidate numbers in decreasing order
      ns = list(generate())
      ns.reverse()
      
      # what numbers occur in all possible sequences?
      ss = list(nconcat(x) for x in intersect(solve(ns)))
      
      # output solution
      printf("{ss}", ss=sorted(ss, reverse=1))
      

      Solution: The positions that are certain are: 7315 and 4728.

      7315 must occur as the 3rd value in the sequence, and 4728 must occur as the 6th value in the sequence.


      There are 5 positions where only one set of digits can occur. But for some of these it is possible to construct more than one valid number from the digits:

      9 + {1, 3, 5} → 9153, 9351, 9513, 9531
      8 + {2, 4, 6} → 8264, 8624
      7 + {1, 3, 5} → 7315
      5 + {0, 1, 3} → 5130, 5310
      4 + {2, 7, 8} → 4728

      Only 7315 and 4728 are unique in their respective positions.

      In total there are 8832 possible sequences of 9 numbers.

      Like

      • Jim Randell 7:38 am on 24 December 2022 Permalink | Reply

        With a little analysis we can get a much faster run time (and the program is only a little longer).

        First we note that the numbers must be of the form:

        9xxx, 8xxx, 7xxx, 6xxx, 5xxx, 4xxx, 3xxx, 2xxx, 1xxx

        And as long as there is valid number that can be constructed using the non-leading digits we don’t really care what order they appear in when we look for the next number. So we can just consider the collection of digits.

        Also, as successive numbers share no digits, as we construct numbers we can exclude the leading digit of the next number (as we already know what it will be).

        Then at the end we take the collections of digits we have found that we know must appear in each position, we can look for those that give just one valid number, and we have found an answer.

        This Python program runs in 56ms. (Internal run time is 963µs).

        Run: [ @replit ]

        from enigma import (irange, subsets, nconcat, diff, intersect, singleton, printf)
        
        # does <x> divide <n>?
        divides = lambda n, x: x != 0 and n % x == 0
        
        digits = list(irange(0, 9))
        
        # is the number formed from (A, B, C, D) valid?
        def valid(A, B, C, D):
          n = nconcat(A, B, C, D)
          if A == 9 and n % 2 != 1:
            return
          if divides(n, A) and sum(divides(n, x) for x in (B, C, D)) == 2:
            return n
        
        # generate candidate digit sets
        # return digits (A, B, C, D) - A is leading digit; B, C, D are ordered
        def candidates(A, ds):
          # choose the three final digits
          for xs in subsets(ds, size=3):
            # can we find a valid number?
            if any(valid(A, B, C, D) for (B, C, D) in subsets(xs, size=len, select="P")):
              yield (A,) + xs
        
        # k = leading digit
        def solve(k, ss=[]):
          # are we done?
          if k == 0:
            yield ss
          else:
            if k == 9:
              # the first number is odd, and has no 0 digit
              cs = candidates(9, diff(digits, {0, 8, 9}))
            elif k > 5:
              # subsequent number with no 0 digit
              cs = candidates(k, diff(digits, ss[-1], {0, k - 1, k}))
            else:
              # subsequent number with no 9 digit
              xs = {k, 9}
              if k > 1: xs.add(k - 1)
              cs = candidates(k, diff(digits, ss[-1], xs))
            for s in cs:
              yield from solve(k - 1, ss + [s])
        
        # look for positions that must occur in all solutions
        for ss in sorted(intersect(solve(9)), reverse=1):
          # look for candidates with only a single valid number
          ns = (valid(ss[0], B, C, D) for (B, C, D) in subsets(ss[1:], size=len, select="P"))
          n = singleton(filter(None, ns))
          if n:
            printf("{n}")
        

        Like

    • Frits 12:48 am on 24 December 2022 Permalink | Reply

      A different approach. At the end only 39 candidate numbers remain.

         
      from itertools import permutations
      from functools import reduce
      
      # convert digit sequences to number
      d2n = lambda s: reduce(lambda x,  y: 10 * x + y, s)
      
      # return entry and column value where column <col> is unique
      def unique_col(seq, col=0):
        d = dict()
        for s in seq:
          d[s[col]] = s[col] in d
      
        return [(s[col], s) for s in seq if not d[s[col]]]
       
      # generate candidate numbers
      def generate():
        for A, B, C, D in permutations(range(9, -1, -1), 4):
          if A == 0: break
          if (A == 9 and D % 2 == 0): continue
          
          n = d2n([A, B, C, D])
          # n is divisible by A and exactly 2 of B, C, D
          if n % A or sum(n % d == 0 for d in (B, C, D) if d) != 2:
            continue
          # A has to connect with A - 1 and A + 1 so B, C and D 
          # may not be equal to A - 1 or A + 1
          if (A < 9 and (A + 1) in {B, C, D}) or \
             (A > 1 and (A - 1) in {B, C, D}): continue
          # no zeroes occurred before the fourth update and no nines after this  
          if (A < 6 or 0 not in {B, C, D}) and \
             (A > 4 or 9 not in {B, C, D}):
            yield (A, B, C, D)
       
      # collect candidate numbers in decreasing order
      ns = list(generate())
      
      # keep maintaining the list of candidate numbers
      while True:
        # determine which numbers always exist for a specific leftmost digit ...
        d = dict()
        for A, B, C, D in ns:
          if A not in d:
            d[A] = {B, C, D}
          else:
            d[A] &= {B, C, D}
       
        # we need nine queue positions (each with a unique leftmost digit)
        if len(d) != 9: 
          print("no solution")
          exit(0)
      
        # ... and delete specific candidate numbers
        for k, vs in d.items():
          for v in vs:
            if k < 9:
              ns = [n for n in ns if n[0] != (k + 1) or v not in n[1:]]
            if k > 1:
              ns = [n for n in ns if n[0] != (k - 1) or v not in n[1:]]  
        
        
        delete = set()  
        # for each candidate number check if valid adjacent queue positions exist
        for A, B, C, D in ns:
          bef, aft = 0, 0
          for A2, B2, C2, D2 in ns:
            # skip if invalid 
            if len(set([A, B, C, D, A2, B2, C2, D2])) != 8: continue
            if A == 1 or A2 == A - 1:
              bef = 1  
            if A == 9 or A2 == A + 1:
              aft = 1
            # break if we find valid adjacent queue positions 
            if bef == aft == 1: break
          else:  
            # A, B, C, D has no (two) valid adjacent queue positions
            delete.add((A, B, C, D))
          
        if not delete: break
       
        # delete specific candidate numbers
        ns = [n for n in ns if n not in delete]
      
      print("certain positions:", [d2n(x[1]) for x in unique_col(ns)])
      

      Like

    • Frits 5:47 pm on 24 December 2022 Permalink | Reply

      Borrowing Jim’s “intersect” call.

       
      from enigma import SubstitutedExpression, intersect
      from functools import reduce
      
      # we have nine 4-digit numbers = 36 variables
      # as the leftmost digits are known and the middle entry has to end on zero
      # we are left with 26 variables, so A-Z
      
      # 9ABC, 8DEF, 7GHI, 6JKL, 5MN0, 4OPQ, 3RST, 2UVW, 1XYZ
      nums = ['ABC', 'DEF', 'GHI', 'JKL', 'MN', 'OPQ', 'RST', 'UVW', 'XYZ']
      
      # convert digit sequences to number
      d2n = lambda s: reduce(lambda x,  y: 10 * x + y, s)
      
      # check validity 2nd argument and possible connection with 1st argument
      def check(s1, s2):
        n = d2n(s2)
        # it's leftmost digit and just two others in it were factors of it
        if n % s2[0] or sum(n % d == 0 for d in s2[1:] if d) != 2:
          return False
      
        if s1 and len(set(s1 + s2)) != 8: return False
        
        return True
      
      # invalid digit / symbol assignments
      d2i = dict()
      for d in range(0, 10):
        vs = set()
        if d:
          vs.update(nums[9 - d])
          if d < 9:
            vs.update(nums[8 - d])
          if d > 1:
            vs.update(nums[10 - d])  
        # no zeroes occurred before the fourth update and no nines after this     
        if d == 0:
          vs.update('ABCDEFGHIJKLMN') 
          # as 5MN0 also delete 0 from 4OPQ entries
          vs.update('OPQ') 
        if d == 9:
          vs.update('OPQRSTUVWXYZ')  
        if d % 2 == 0:
          vs.update('C')  
        d2i[d] = vs
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
          # only check validity of 9ABC
          "check([], [9, A, B, C])",
          
          # check validity 2nd argument and connection with 1st argument
          "check([9, A, B, C], [8, D, E, F])",
          "check([8, D, E, F], [7, G, H, I])",
          "check([7, G, H, I], [6, J, K, L])",
          "check([6, J, K, L], [5, M, N, 0])",
          "check([5, M, N, 0], [4, O, P, Q])",
          "check([4, O, P, Q], [3, R, S, T])",
          "check([3, R, S, T], [2, U, V, W])",
          "check([2, U, V, W], [1, X, Y, Z])",
        ],
        answer="(9000+ABC, 8000+DEF, 7000+GHI, 6000+JKL, 5000+10*MN, 4000+OPQ, \
                 3000+RST, 2000+UVW, 1000+XYZ)",
        d2i=d2i,
        distinct=('ABC', 'DEF', 'GHI', 'JKL', 'MN', 'OPQ', 'RST', 'UVW', 'XYZ'),
        env=dict(check=check),
        denest=32,      # [CPython] work around statically nested block limit
        verbose=0,    # use 256 to see the generated code
      )
      
      answs = [y for _, y in p.solve()]
        
      print("certain positions:", list(d2n([x]) for x in intersect(answs)))
      

      Like

      • Jim Randell 4:41 pm on 26 December 2022 Permalink | Reply

        @Frits: That’s neat. I hadn’t thought of using the [[ SubstitutedExpression ]] solver.

        Here’s a run file that solves the puzzle (it does generate all possible sequences though, so it is not as fast as my second program).

        This run file executes in 98ms.

        Run: [ @replit ]

        #! python3 -m enigma -r
        
        SubstitutedExpression
        
        # the positions are:
        # 9xxx = ABCD
        # 8xxx = EFGH
        # 7xxx = IJKL
        # 6xxx = MNPQ
        # 5xxx = RSTU
        # 4xxx = VWXY
        # 3xxx = Zabc
        # 2xxx = defg
        # 1xxx = hijk
        
        # leading digits are known
        --assign="A,9"
        --assign="E,8"
        --assign="I,7"
        --assign="M,6"
        --assign="R,5"
        --assign="V,4"
        --assign="Z,3"
        --assign="d,2"
        --assign="h,1"
        
        # no number shares digits with its neighbour
        --distinct="ABCDEFGH,EFGHIJKL,IJKLMNPQ,MNPQRSTU,RSTUVWXY,VWXYZabc,Zabcdefg,defghijk"
        
        # each number is divisible by its leading digit and exactly 2 of the others
        --code="divides = lambda n, d: d > 0 and n % d == 0"
        --code="check = lambda n, A, B, C, D: divides(n, A) and sum(divides(n, x) for x in (B, C, D)) == 2"
        
        "check({ABCD}, {A}, {B}, {C}, {D})"
        "check({EFGH}, {E}, {F}, {G}, {H})"
        "check({IJKL}, {I}, {J}, {K}, {L})"
        "check({MNPQ}, {M}, {N}, {P}, {Q})"
        "check({RSTU}, {R}, {S}, {T}, {U})"
        "check({VWXY}, {V}, {W}, {X}, {Y})"
        "check({Zabc}, {Z}, {a}, {b}, {c})"
        "check({defg}, {d}, {e}, {f}, {g})"
        "check({hijk}, {h}, {i}, {j}, {k})"
        
        # 9xxx is odd
        "{D} % 2 == 1"
        
        # no 0's in 9xxx, 8xxx, 7xxx, 6xxx
        --invalid="0,ABCDEFGHIJKLMNPQ"
        # no 9's in 5xxx, 4xxx, 3xxx, 2xxx, 1xxx
        --invalid="9,RSTUVWXYZabcdefghijk"
        
        # collect numbers that occur in all sequences
        --answer="({ABCD}, {EFGH}, {IJKL}, {MNPQ}, {RSTU}, {VWXY}, {Zabc}, {defg}, {hijk})"
        --code="fn = lambda xs: sorted(intersect(xs), reverse=1)"
        --accumulate="fn"
        
        --template="({ABCD} {EFGH} {IJKL} {MNPQ} {RSTU} {VWXY} {Zabc} {defg} {hijk})"
        --solution=""
        
        --denest=1  # CPython workaround
        

        Like

    • Hugh Casement 11:49 am on 1 January 2023 Permalink | Reply

      I found, in addition to those mentioned by Jim,
      6492, 6924, 6948
      eight possible numbers starting with 3 and also containing 015 or 156 in some order
      seven possible numbers starting with 2 and all containing 4 and 8
      twelve possible numbers starting with 1 and all containing 5.

      Like

  • Jim Randell 4:32 pm on 28 October 2022 Permalink | Reply
    Tags: by: Stephen Hogg   

    Teaser 3136: Fill cells mentally, my dear Watson 

    From The Sunday Times, 30th October 2022 [link] [link]

    Moriarty’s papers were alight. Holmes memorised a 3×3 grid of different 4-digit values in ascending order as illustrated, from A (lowest) to I (highest), noticing that one numeral wasn’t used. Three cells, isolated from one another (no corner or edge contact), held squares of squares. Three others, similarly isolated, held cubes of non-squares. The other three held squares of non-squares. Holmes told Watson these features, specifying only the lowest value. “Not square”, remarked Watson.

    “True, and many grids match these facts. However, if I told you the positions of the squares of squares in the grid, you could deduce a majority of the other eight values (apart from the lowest one)”, replied Holmes.

    In ascending order, which values did Watson know certainly?

    [teaser3136]

     
    • Jim Randell 5:50 pm on 28 October 2022 Permalink | Reply

      I found 2 scenarios where Watson (when told the smallest number and the positions of the “squares of squares” in the grid) could work out 5 of the other numbers that must be in the grid.

      Since Watson says “Not square” I am assuming we want the scenario where the lowest number in the grid (A) is not a square (i.e. it is a cube of a non-square).

      The following Python program runs in 81ms. (Internal runtime is 29ms).

      Run: [ @replit ]

      from enigma import (
        defaultdict, irange, sq, cb, is_square, cproduct, union, diff,
        subsets, update, peek, intersect, join, printf
      )
      
      # we have 3 disjoint categories of 4-digit numbers:
      # cat1 = "square of a square" (i.e. a power of 4)
      cat1 = list(str(sq(sq(i))) for i in irange(6, 9))
      # cat2 = "cube of a non-square"
      cat2 = list(str(cb(i)) for i in irange(10, 21) if not is_square(i))
      # cat3 = "square of a non-square"
      cat3 = list(str(sq(i)) for i in irange(32, 99) if not is_square(i))
      
      # sets of isolated cells
      iso0 = [(0, 2, 6), (0, 2, 7), (0, 2, 8), (0, 5, 6), (0, 6, 8)] # with cell 0
      isox = [(1, 6, 8), (2, 3, 8), (2, 6, 8)] # without cell 0
      
      # collect candidate grids
      g = defaultdict(list)
      
      # fill out cells <cs> in grid <ns> with values from <cat>
      # making sure digit content (including <ds>) does not exceed 9
      def fill(ns, cs, cat, ds):
        # are we done?
        if not cs:
          yield (ns, ds)
        else:
          # fill out the next cell
          i = cs[0]
          lo = peek((ns[j] for j in irange(i - 1, 0, step=-1) if ns[j]), default='0000')
          hi = peek((ns[j] for j in irange(i + 1, 8) if ns[j]), default='AAAA')
          for n in cat:
            if not (n > lo): continue
            if not (n < hi): break
            ds_ = ds.union(n)
            if not (len(ds_) > 9):
              yield from fill(update(ns, [i], [n]), cs[1:], cat, ds_)
      
      # choose cat1, cat2 cells; cell 0 (A) is not a square
      for (cs1, cs2) in cproduct([isox, iso0]):
        # remaining cells are cat3
        cs = union([cs1, cs2])
        if len(cs) != 6: continue
        cs3 = diff(irange(0, 8), cs)
      
        # fill out the cells
        ns0 = [None] * 9
        # choose cat1 values
        for vs1 in subsets(cat1, size=3):
          ds1 = union(vs1)
          if len(ds1) > 9: continue
          ns1 = update(ns0, cs1, vs1)
      
          # fill out cat2 and cat3 values
          for (ns2, ds2) in fill(ns1, cs2, cat2, ds1):
            for (ns3, ds3) in fill(ns2, cs3, cat3, ds2):
              if len(ds3) == 9:
                # group grids by (<cell 0>, <cat1 positions>)
                g[(ns3[0], cs1)].append(ns3)
      
      # consider the groups
      for (k, vs) in g.items():
        # can we determine at least 5 additional values?
        xs = intersect(vs)
        if len(xs) < 6: continue
      
        # output solution
        (A, cs1) = (k[0], join("ABCDEFGHI"[x] for x in k[1]))
        printf("(A={A}, cat1={cs1}) -> {xs}", xs=join(sorted(xs), sep=", ", enc="()"))
      

      Solution: Watson knew for certain the grid contained: 1331, 2401, 4096, 4913, 5832, 6561.

      Watson was told that the lowest number was 1331, and the “squares of squares” were in positions: C, D, I.

      As 1331 = 11³, Watson can deduce that the cubes are in positions: A, F, G. And the squares of non-squares are in positions: B, E, H.

      And so he can deduce the cubes are: A=1331, F=4913, G=5832. And the powers of 4 are: C=2401, D=4096, I=6561.

      Together these 6 values use all the digits except 7.

      So the grid can be completed with any squares of non-squares that don’t use the digit 7, and fit in the appropriate position.

      The candidates are:

      B = 1369, 1444, 1521, 1600, 1681, 1849, 1936, 2025, 2116, 2209, 2304
      E = 4225, 4356, 4489, 4624, 4900
      H = 5929, 6084, 6241, 6400

      So there are 220 possible grids.

      Here is one possibility:

      red = squares of squares
      blue = cubes of non-squares
      yellow = squares of non-squares

      Like

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

    Teaser 3125: The bearings’ trait 

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

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

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

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

    Give the three bearings, in ascending order.

    [teaser3125]

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

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

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

      It runs in 86ms.

      Run: [ @replit ]

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

      Solution: The three bearings are: 159°, 267°, 348°.


      There are 8 ways to distribute the digits to make a valid set of bearings:

      159, 267, 348
      168, 249, 357
      169, 247, 358
      169, 248, 357
      176, 249, 358
      176, 259, 348
      178, 249, 356
      178, 259, 346

      The bearings in bold only occur in one of the sets, so each of them uniquely identifies the set to which it belongs.

      The first set is the only one that contains more than one unique bearing, and if we were to randomly choose a bearing from this set there is a 2/3 chance that we would get a unique bearing (and so be able to identify the entire set), and a 1/3 chance we will get a bearing that appears in more than one set. So this set gives the answer to the puzzle.

      Like

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

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

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

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

        Run: [ @replit ]

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

        Like

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

      Similar method to Jim’s first solution.

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

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

      Like

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

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

      Like

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

        Inspired by Nigel.

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

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

        Like

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

          @Frits: You don’t need to call sorted():

          def bearings(mx, bs=[[]]):
            return [[new] + b for b in bs
              ...
          

          Like

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

      Too hot to go outside.

      Bringing down the number of viable bearings down to 15.

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

      Like

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

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

      Like

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

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

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

      Like

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

        Well done.

        Using

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

        it is even more efficient.

        Like

        • NigelR 12:34 am on 17 August 2022 Permalink | Reply

          Thanks Frits. I’m still at the very rewarding end of the Python learning curve (and likely to remain so for some considerable time)!

          Like

  • Jim Randell 6:14 pm on 1 June 2022 Permalink | Reply
    Tags: by: Stephen Hogg   

    Teaser 3115: Germometric mean 

    From The Sunday Times, 5th June 2022 [link] [link]

    On Whit Monday, Zak began self-isolating upstairs. At lunchtime Kaz shouted up: “What’s a Geometric Mean?”

    “It’s the Nth root of the product of N values”, Zak replied.

    On TV, Teaseside hospital’s “geovid” admissions for the seven days prior were listed alongside their Geometric Mean. Kaz stated that chronologically the numbers comprised a decreasing set of two-figure values, Friday’s value equalling the Geometric Mean. She added that, curiously, there was a value double the Geometric Mean, but not triple, whereas the Geometric Mean was triple a data value, but not double a data value. She then told Zak just the Geometric Mean.

    Zak worked out the unique data set.

    Give the seven numbers in chronological order.

    [teaser3115]

     
    • Jim Randell 6:41 pm on 1 June 2022 Permalink | Reply

      The following Python program runs in 70ms. (Internal run time is 9.7ms).

      Run: [ @replit ]

      from enigma import (irange, divisors, filter2, div, reverse, singleton, printf)
      
      # generate <k> increasing values from <vs> with product <v>
      def decompose(v, k, ds, ss=[]):
        if k == 1:
          if v in ds:
            yield ss + [v]
        elif not (len(ds) < k):
          for (i, d) in enumerate(ds):
            v_ = div(v, d)
            if v_ is not None:
              yield from decompose(v_, k - 1, ds[i + 1:], ss + [d])
      
      # generate candidate values for geometric mean <gm>
      def generate(gm):
        # find the remaining values
        ds = list(d for d in divisors(gm, 6) if 9 < d < 100 and d != gm)
        for vs in decompose(gm ** 6, 6, ds):
          # there are 2 values less than gm (and 4 values greater)
          (lt, gt) = filter2((lambda x: x < gm), vs)
          if len(lt) != 2: continue
          # there is a gm/3 value, but not a gm/2 value
          if (gm // 3 not in lt) or (div(gm, 2) in lt): continue
          # there is a gm*2 value, but not a gm*3 value
          if (gm * 2 not in gt) or (gm * 3 in gt): continue
          # return the sequence, Mo - Su
          yield reverse(gt) + [gm] + reverse(lt)
      
      # consider values for the geometric mean: gm/3 and gm*2 are 2-digit values
      for gm in irange(30, 49, step=3):
        # is there only a single candidate solution?
        ns = singleton(generate(gm))
        if ns:
          # output solutions
          printf("{ns}")
      

      Solution: The numbers are (Mon – Sun): 96, 72, 64, 54, 48, 32, 16.

      The geometric mean is 48, and there is a value twice the geometric mean (98), but not three times (144). There is also a value one third of the geometric mean (16), but not one half (24).


      This is the only possible sequence with a geometric mean of 48.

      However there are other possible sequences with a geometric mean of 42:

      (98, 84, 81, 49, 42, 14, 12)
      (98, 84, 54, 49, 42, 18, 14)
      (84, 63, 56, 49, 42, 27, 14)
      (84, 63, 54, 49, 42, 28, 14)

      Like

      • Jim Randell 6:49 am on 2 June 2022 Permalink | Reply

        And here is an even faster version:

        If g is the geometric mean we have a decreasing sequence of values (Mon – Sun):

        (a, b, c, d, g, e, f)

        Such that:

        g^7 = a × b × c × d × g × e × f

        And we know one of the values greater than g (i.e. one of (a, b, c, d)) has a value of 2g, and one of the values less than g (i.e. one of (e, f)) has a value of (g / 3) (which tells us g is a multiple of 3).

        Hence:

        (3/2)(g^4) = [3 of (a, b, c, d)] × [1 of (e, f)]

        Which tells us g is also a multiple of 2.

        Furthermore (g / 3) is a 2-digit value, so g ≥ 30, and 2g is also a 2-digit value, so g < 50.

        This Python program considers possible values for the geometric mean, and finds the three remaining values higher than the mean, and the value lower than the mean. If a mean leads to a single possible set of values, then we have found the solution.

        It runs in 54ms. (Internal runtime is 167µs).

        from enigma import (irange, div, diff, singleton, printf)
        
        # reversed sort
        rsort = lambda x: sorted(x, reverse=1)
        
        # find <k> increasing values from <ds> whose product divide into <v>
        # return: (<ns>, <r>) where <r> is the remainder
        def decompose(v, k, ds, ns=[]):
          if k == 0:
            yield (ns, v)
          elif not (len(ds) < k):
            for (i, d) in enumerate(ds):
              v_ = div(v, d)
              if v_ is not None:
                yield from decompose(v_, k - 1, ds[i + 1:], ns + [d])
        
        # generate candidate sequences for geometric mean <gm>
        def generate(gm):
          # find 2-digit divisors of (3/2)gm^4 greater than gm
          v = 3 * div(gm ** 4, 2)
          ds = diff((d for d in irange(gm + 1, 99) if v % d == 0), {2 * gm, 3 * gm})
          for (gt, r) in decompose(v, 3, ds):
            # there is no gm/2 value
            if (not 9 < r < gm) or 2 * r == gm or 3 * r == gm: continue
            # return the sequence (in decreasing order)
            yield rsort(gt + [2 * gm]) + [gm] + rsort([r, gm // 3])
        
        # consider values for the geometric mean, gm is a multiple of 6
        for gm in irange(30, 49, step=6):
          # is there only a single candidate solution?
          ns = singleton(generate(gm))
          if ns:
            # output solutions
            printf("[Mon - Sun] = {ns}")
        

        Like

        • Frits 1:30 pm on 2 June 2022 Permalink | Reply

          Using divisors_tuples() is slower than the decompose() method.

             
          from enigma import divisors_tuples
          
          # return entry where column <col> is unique
          def unique_col(seq, col=0):
            d = dict()
            for s in seq:
                 d[s[col]] = s[col] in d
             
            return [s for s in seq if not d[s[col]]]
          
          # there is a gm/3 value and there is a 2*gm value
          # gm must also be even as gm^7 is even 
          
          sol = []
          # consider values for the geometric mean: gm/3 and gm*2 are 2-digit values
          for gm in range(30, 50, 6):
            # generate seven 2-digit numbers that multiply to gm^7
            nums = [sorted(x + (gm // 3, gm, 2 * gm), reverse = True) 
                   for x in divisors_tuples(3 * (gm**4 // 2), 4) 
                   if all(9 < y < 100 for y in x) 
                      and gm // 2 not in x 
                      and 3 * gm not in x]
           
            # store valid solutions
            sol += [x for x in nums if len(set(x)) == 7 and x[4] == gm]
          
          print("answer =", *unique_col(sol, 4))
          

          A basic SubstitutedExpression program takes about 5 seconds (with PyPy).

          Like

    • Frits 2:58 pm on 2 June 2022 Permalink | Reply

      Program runs in 75ms (with PyPy).

         
      from enigma import SubstitutedExpression
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
         # there is a gm/3 value and there is a gm*2 value
         # gm must also be even as gm^7 is even so E is even
         "(G + M) % 3 == 0",
         
         # 1.5 * GM**4 is the product 4 unknown sorted numbers AB, CD, EF and PQ
        
         "AB < GM",
         "CD > GM",
         "EF > GM",
         "CD < EF",
         
         "div(3 * GM**4 // 2, AB * CD * EF) = PQ",
         "PQ > EF",
         
         # seven different numbers
         "len(set([AB, CD, EF, PQ, GM, 2 * GM, GM // 3])) == 7",
         # friday's value equalling the geometric mean
         "sorted([AB, CD, EF, PQ, GM, 2 * GM, GM // 3])[2] == GM",
         
         # there is no 3*gm or gm/2 value
         "3 * GM not in {AB, CD, EF, PQ, GM, 2 * GM, GM // 3}",
         "GM // 2 not in {AB, CD, EF, PQ, GM, 2 * GM, GM // 3}",
         
        ],
        answer="sorted([AB, CD, EF, PQ, GM, 2 * GM, GM // 3], reverse=1)",
        d2i=dict([(0, "GACEP")] + 
                 [(1, "GCEM")] +                       
                 [(2, "GCE")] +
                 [(3, "M")] +
                 [(5, "AGM")] +
                 [(6, "AG")] +
                 [(7, "AGM")] +
                 [(8, "AG")] +
                 [(9, "AGM")]),
        distinct="",
        reorder=0,
        verbose=0,    # use 256 to see the generated code
      )
      
      # store answers
      d = dict()
      for (_, ans) in p.solve():
        d[ans[4]] = d.get(ans[4], []) + [ans]
        
      for v in d.values():
        if len(v) == 1:
          print(*v) 
      

      Like

  • Jim Randell 9:53 am on 5 May 2022 Permalink | Reply
    Tags: by: Stephen Hogg   

    Teaser 2856: Solid jellometry 

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

    As a wedding gift, Granny Lucci gave us a set of five jelly moulds, which was odd in many ways. The base of each mould was a different regular polygon (including a triangle) with each side an odd number of centimetres in length. Each polygon had the same length perimeter, an odd two figure number of centimetres.

    The sides of the moulds were vertical and the heights of the moulds were all the same odd number of centimetres. The volumes of the moulds were all between one and two litres.

    What was the height of the moulds?

    [teaser2856]

     
    • Jim Randell 9:55 am on 5 May 2022 Permalink | Reply

      This Python program run in 56ms (internal run time is 476µs).

      Run: [ @replit ]

      from math import pi, tan
      from enigma import fdiv, irange, divisors, divf, divc, subsets, diff, intersect, printf
      
      # area of a regular polygon with <n> sides and perimeter <p>
      def area(n, p):
        a = fdiv(pi, n)
        return fdiv(p * p, 4 * n * tan(a))
      
      # consider odd values for p = perimeter
      for p in irange(11, 99, step=2):
      
        # look for divisors of p (excluding 1)
        ds = list(d for d in divisors(p) if d > 1)
      
        # it must have at least 5 divisors, one of which is 3
        if not(len(ds) > 4 and 3 in ds): continue
      
        # consider possible odd heights for each divisor
        ps = dict()
        for n in ds:
          a = area(n, p)
          hs = list(h for h in irange(divc(1000, a), divf(2000, a)) if h % 2 == 1)
          if hs:
            ps[n] = hs
        # the smallest prism is triangular
        if 3 not in ps: continue
      
        # choose the 4 prisms with more than 3 sides
        for ns in subsets(diff(sorted(ps.keys()), [3]), size=4, fn=list):
          # add in the triangular prism
          ns.insert(0, 3)
          # find common heights
          for h in intersect(ps[n] for n in ns):
            # output solution
            printf("perimeter = {p}, height = {h}")
            for n in ns:
              printf("  {n} sides -> side = {x}; vol = {v:.2f}", x=(p // n), v=area(n, p) * h)
            printf()
      

      Solution: The moulds are 11 cm high.

      Each of the five moulds has a base with a perimeter of 45 cm.

      3 sides of 15 cm each; volume = 1071.71 cm³
      5 sides of 9 cm each; volume = 1532.95 cm³
      9 sides of 5 cm each; volume = 1700.00 cm³
      15 sides of 3 cm each; volume = 1746.59 cm³
      45 sides of 1 cm each; volume = 1769.71 cm³

      Like

    • Hugh+Casement 3:28 pm on 5 May 2022 Permalink | Reply

      There are only four values for the perimeter with enough divisors to give five different polygons.
      Of those, only 45 cm (and height 11 cm) results in all the volumes being between 1 and 2 litres.
      The polygons have sides 3, 5, 9, 15, and 45 sides.

      Like

  • Jim Randell 4:15 pm on 1 April 2022 Permalink | Reply
    Tags: by: Stephen Hogg   

    Teaser 3106: Underground umbra conundrum 

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

    An underground car park has rectangular walls, each covered with 300 abutting square tiles arranged in three repeats of red, orange, yellow, green and blue columns twenty tiles high. A sharp tapering shadow from a duct played across one wall from top to bottom (with straight lines similar to that shown).

    Each shadow edge crossed every colour and, curiously, hit just two points where four tile corners met. The upper and lower pairs of these were on levels the same distance up and down from the mid-level line. I also noticed that no column was completely free of shadow, but just one column was completely in shadow.

    Give the shadow’s area relative to the wall area as a fraction in simplest form.

    [teaser3106]

     
    • Jim Randell 11:01 pm on 1 April 2022 Permalink | Reply

      For the “shadow edge” (or terminator) to “cross” a coloured column I required that a non-zero length of it intersected with the column. I assumed that the points at which the terminator hits the intersections of the four tile corners are all the same vertical distance from the horizontal centre line of the wall. And that the shadow tapers towards the top and slants towards the right (as in the diagram).

      After drawing a diagram on graph paper to solve the puzzle, I wrote the following Python program to check the solution was unique. And I found there were in fact two ways to reach the answer.

      The Python program considers the possible heights at which the terminator line hits the intersections of four tile corners, and then possible horizontal positions. The areas of the resulting lit regions are grouped by the width in tiles of the bounding box of the area.

      We then look for two lit areas that have exactly 1 column between them (that is in shadow), and the total area of shadow is calculated.

      It runs in 59ms.

      Run: [ @replit ]

      from enigma import (defaultdict, irange, subsets, is_coprime, Polynomial, intc, product, printf)
      
      # consider possible levels for the corner intersection (from the floor/ceiling)
      for y in irange(1, 9):
      
        # record possible lit areas by bounding width
        d = defaultdict(set)
        
        # possible x co-ordinates for upper/lower intersections
        for (x, x_) in subsets(irange(1, 8), size=2):
          if not is_coprime(20 - 2 * y, x_ - x): continue
          
          # interpolate the terminator line
          f = Polynomial.interpolate([(y, x), (20 - y, x_)])
          # calculate intercepts of y=0, y=20 (floor/ceiling)
          (x0, x20) = map(f, [0, 20])
          # must start in first column, and include at least 5 columns
          if x0 < 0 or (not x0 < 1) or (not x20 > 4): continue
          
          # width of bounding region
          w = intc(x20)
          if w < 5 or w > 9: continue
          # lit area
          L = 10 * (x0 + x20)
          d[w].add(L)
          
          printf("[y={y}: x=({x}, {x_}) -> ({x0}, {x20}) w={w} L={L}]")
      
        # look for 2 bounding widths that sum to 14
        for w1 in sorted(d.keys()):
          w2 = 14 - w1
          if not w1 < w2: break
      
          # calculate area in shadow
          for (L1, L2) in product(d[w1], d[w2]):
            T = 300
            S = T - L1 - L2
            q = S / T
            printf("q = {S}/{T} = {q} [w1={w1} L1={L1}; w2={w2} L2={L2}]")
      

      Solution: The shadow covers 8/15 of the wall.


      We note that in the determination of any lit region we have:

      x0 + x20 = w

      And the area of the lit region is therefore:

      L = 20 (x0 + x20) / 2
      L = 10w

      And for a solution we require widths that sum to 14 (to leave exactly one column completely in shadow).

      Hence the area in shadow is:

      S = 300 − L1 − L2
      S = 300 − 10w1 − 10w2
      S = 300 − 10(w1 + w2)
      S = 300 − 140
      S = 160

      So we can see, if there are any solutions, the answer will be:

      q = 160 / 300
      q = 8 / 15

      And the program above shows there are two scenarios which lead to a solution (shown below):

      In the second scenario the leftmost red column is only just in shadow (at its bottom right hand corner), and similarly the second green column is only just lit (at its top left hand corner), so the first scenario is probably a better solution (although the second scenario looks more similar to the diagram in the puzzle statement).


      Another way of looking at the puzzle is that there is exactly one column entirely in shadow = 1/15 of the wall.

      And the remaining area of the wall (totalling 14/15) consists of 2 rectangles, each of which is split exactly half in shadow.

      The total area in shadow is therefore: 1/15 + 7/15 = 8/15 of the wall.

      All that remains is to show that there is a construction that meets the remaining conditions (and, as noted above, there are 2).

      Like

  • Jim Randell 4:05 pm on 14 January 2022 Permalink | Reply
    Tags: by: Stephen Hogg   

    Teaser 3095: Diddums! 

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

    “Diddums” was Didi’s dada’s name for numbers where the number of positive DIvisors (including 1 and the number), the number of Digits, and the Digit sUM are equal.

    Didi enjoyed mental arithmetic, doing it speedily and accurately. For numbers of digits from 1 to 9 she listed in ascending order all possible numbers whose digit sum equalled the number of digits. Working through her list in order, she quickly found the first two diddums (1 and 11) and the next three diddums. After many further calculations, Didi confirmed that the sixth diddum (which is even) was listed.

    “Now I’m bored”, she moaned.

    “Diddums!”, said Didi’s dada.

    What is the sixth diddum’s digit sum?

    [teaser3095]

     
    • Jim Randell 4:49 pm on 14 January 2022 Permalink | Reply

      This Python program generates the numbers in order.

      To find the first 6 numbers takes 74ms.

      Run: [ @replit ]

      from enigma import tau, irange, inf, arg, printf
      
      # generate numbers with a digit sum of t and k digits
      def generate(t, k, n=0):
        if k == 1:
          if t < 10:
            yield 10 * n + t
        else:
          for d in irange((0 if n else 1), min(9, t)):
            yield from generate(t - d, k - 1, 10 * n + d)
      
      # generate "diddums" numbers in order
      def solve():
        for k in irange(1, inf):
          for n in generate(k, k):
            if tau(n) == k:
              yield (k, n)
      
      N = arg(6, 0, int)
      
      # find the first N numbers
      for (i, (k, n)) in enumerate(solve(), start=1):
        printf("[{i}] {k} -> {n}")
        if i == N: break
      

      Solution: The sixth number on the list has a digit sum of 8.

      The list of numbers looks like this:

      1 → 1
      2 → 11
      4 → 1003, 1111, 2101
      8 → 10000034, …, 70000001 (630 numbers)
      10 → 1000003024, …, 5100000112 (70 numbers)
      12 → 100000001028, …, 900000101001 (6320 numbers)
      14 → 10000000260032, …, 70001000100032 (2149 numbers)
      16 → 1000000000000186, …

      For the larger numbers it is more efficient to use Pollard’s Rho method [[ prime_factor_rho() ]] to find prime factors, which we can do by calling [[ tau() ]] like this:

      tau(n, prime_factor_rho)
      

      Like

    • GeoffR 8:41 pm on 14 January 2022 Permalink | Reply

      A brute force solution ran in about 20 sec. After the first sixth number, there were many similar solutions to the sixth number.

      from enigma import nsplit, tau, divisors
      
      cnt = 0  #counter for number of diddum numbers.
      
      for k in range(1, 100000000):
        n = nsplit(k) #split number into digits
        sn = sum(n)   #find sum of digits
        nd = len(n)   #find number of digits
        # check sum of digits = number of digits
        if sn == nd:
          tk = tau(k)
          # check sum of digits = no. of divisors
          if sn == tk:
            print(f"{cnt+1}: num={k}, no. divisors={tau(k)}")
            print(f"Divisors are {divisors(k)}")
            print()
            cnt += 1
            # stop after the 6th number
            if cnt == 6:
              break
      
      
      

      Like

    • NigelR 9:55 am on 15 January 2022 Permalink | Reply

      I used a very similar approach to GeoffR (a sledgehammer once again!) but without the enigma functions. I also added a fudge to exploit the ‘(which is even)’ advice for the 6th number by using an increment of 2 once the 5th number had been found. This reduced the run time by a couple of days.

      import math
      #function to return list of digits in n
      def digs(n):    
          cont = []
          while n:
              n,a = divmod(n,10)
              cont.append(a)
          return cont        
      #function to return list of divisors of n
      def divisg(n):
          divs = [1]
          for i in range(2,int(math.sqrt(n))+1):
              if n%i == 0:
                  divs.extend([i,int(n/i)])
          divs.extend([n])
          return list(set(divs))
      #main
      i = 0
      inc = 1 
      count = 0
      while count < 6:
          i += inc
          num = digs(i)      
          if sum(num) != len(num): continue
          div = list(divisg(i))
          if len(div) != len(num):continue
          print(i,num,div)
          count += 1
          if count==5:
              if i%2 != 0: i+=1
              inc=2
      

      Like

    • Hugh+Casement 8:52 am on 16 January 2022 Permalink | Reply

      That was a giant sledgehammer, Nigel! There are faster ways. For example, the square of a prime has three integer divisors: none fits here. The cube of a prime has four divisors: again none found. The product of two different primes also has four divisors: that provides the next three (mentioned in the puzzle). The product of one prime and the square of another has six divisors; one of those primes obviously has to be 2 to give an even product.

      I’ll spare you my program in Basic, but after rejecting a few numbers of factors & digits it quickly found the sixth diddums and a further five.

      Like

    • GeoffR 3:42 pm on 23 January 2022 Permalink | Reply

      This programme considers ‘Diddums’ numbers for separate three, four, five, six, seven and eight digit groups. This method produced the six-number solution with a much faster run-time than my previous posting. It ran in 28 msec.

      
      from enigma import Primes, tau, divisors, nsplit
      
      from enigma import Timer
      timer = Timer('ST3095', timer='E')
      timer.start()
      
      # primes for 4-digit 'Diddums' numbers
      primes = list(Primes(200))
      
      # Check 3,4,5,6,7,8 digit 'Diddums' numbers
      DD_nums = []
      
      DD_nums.append(1) # two given 'Diddums' numbers
      DD_nums.append(11)
      
      # 3-digit 'Diddums' numbers
      D3 = [x * x for x in range(10, 20) if x * x in range(100, 301)]
      for n in D3:
        if tau(n) == 3 and sum(nsplit(n)) == 3:
          DD_nums.append(n)
      
      # 4-digit 'Diddums' numbers - use a  and b as primes,
      # where four divisors are 1, a, b, a * b
      for a in primes:
        for b in primes:
          if a == b:
            continue
          if a * b in range(1000, 4001):
            if a * b in DD_nums:
              continue
            if tau(a * b) == 4 and sum(nsplit(a * b)) == 4:
              DD_nums.append(a * b)
      
      # 5-digit 'Diddums' numbers for powers p ^ 4,
      # five divisors are 1, p, p^2, p^3, p^4
      for p in (11, 13, 17):
        num = p ** 4
        if num in range(10000, 50001):
          if tau(num) == 5 and sum(nsplit(num)) == 5:
            DD_nums.append(num)
      
      # 6-digit 'Diddums' numbers 
      # product of 2 primes in a^2 * b format gives six divisors
      for a in primes:
        for b in primes:
          if a == b:
            continue
          if a * a * b in range(100000, 600001):
            if a * a * b in DD_nums:
              continue
            if tau(a * a * b) == 6 and sum(nsplit((a * a * b))) == 6:
              DD_nums.append(a * a * b)
      
      # 7-digit 'Diddums' numbers for powers p^6,
      # seven divisors are 1, p, p^2, p^3, p^4, p^5, p^6
      for p in (11, 13):   
        num = p ** 6
        if num in range(1000000, 7000001):
          if tau(num) == 7 and sum(nsplit(num)) == 7:
            DD_nums.append(num)
      
      # check first 10,000 8-digit  numbers (initially) for
      # potential 8-digit numbers summing to eight
      D8 = []
      
      for n in range(10000000, 10010000):
        ns = nsplit(n)
        if sum(ns) == 8:
          D8.append(n)
      
      for n in D8:
        if tau(n) == 8:
          DD_nums.append(n)
          break
      
      print('Diddums Numbers are ', sorted(DD_nums))
      timer.stop()      
      timer.report()
      
      # Numbers are  [1, 11, 1003, 1111, 2101, 10000034]
      # [ST3095] total time: 0.0276404s (27.64ms)
      
      

      Like

  • Jim Randell 9:59 am on 21 December 2021 Permalink | Reply
    Tags: by: Stephen Hogg   

    Teaser 2849: Swift tailor 

    From The Sunday Times, 30th April 2017 [link]

    When measuring gentlemen’s chest sizes in inches, the tailors five foot long tape overlapped so that the set of numbers 1 to 9 was aligned with a consecutive set of higher numbers.

    Taking each pair of these nine aligned lower and higher numbers as a fraction the tailor saw that just two of the nine “fractions” were in their simplest form and did not cancel down (i.e. the pair of numbers had no common factor greater than one).

    All of this was also true when he measured the smaller waist size.

    What (in inches) were the gentleman’s chest and waist sizes?

    [teaser2849]

     
    • Jim Randell 10:00 am on 21 December 2021 Permalink | Reply

      Assuming the tape measure is graduated 1″ … 60″.

      The smallest possible measurement is: 1/10 … 9/18 corresponding to a measurement of 9″ (although that is ludicrously small). And the largest is: 1/52 … 9/60 (corresponding to 51″).

      This Python program runs in 46ms.

      Run: [ @replit ]

      from enigma import irange, is_coprime, printf
      
      # consider possible measurements
      for m in irange(9, 51):
        # count how many pairs are co-prime
        pairs = ((i, m + i) for i in irange(1, 9))
        ps = list(p for p in pairs if is_coprime(*p))
        # we are looking for measurements with 2 co-prime pairs
        if len(ps) == 2:
          printf("m={m} {ps}")
      

      Solution: The measurements are: chest = 42″; waist = 30″.

      When the measurement is 30″ we get the following lowest term fractions: 1/31, 7/37.

      When the measurement is 42″ we get the following lowest term fractions: 1/43, 5/47.

      Like

    • Hugh+Casement 1:12 pm on 21 December 2021 Permalink | Reply

      That works out at 76 and 107 cm: a fine figure of a man!
      Somehow I find 84 and 90 cm more realistic.

      Like

  • Jim Randell 8:42 am on 2 December 2021 Permalink | Reply
    Tags: by: Stephen Hogg   

    Teaser 2841: Crenellation aggregation 

    From The Sunday Times, 5th March 2017 [link]

    The castle’s crenellated outer walls formed a pentagon, and on a family visit we decided to count the crenels. My son counted the number on each side and found that these totals on each side were five consecutive two figure numbers. My daughter and wife started together and then one of them walked clockwise around the walls and the other walked anticlockwise. They each counted the crenels they passed until they met. Their totals were two different prime numbers (with no prime number between the two). I consulted the tourist leaflet and found that the total number of crenels was in fact the product of three prime numbers.

    How many crenels were there in total?

    [teaser2841]

     
    • Jim Randell 8:43 am on 2 December 2021 Permalink | Reply

      We can express the the total number of crenels in three different ways (assuming no mistakes were made in the counting):

      t = 5n + 10 (where 10 ≤ n ≤ 95, so 60 ≤ t ≤ 485)
      t = p1 + p2 (where p1 and p2 are consecutive primes)
      t = q1 × q2 × q3 (where q1, q2, q3 are primes)

      This Python program looks at consecutive primes, until it finds a total that satisfies the remaining two expressions.

      It runs in 47ms.

      Run: [ @replit ]

      from enigma import Primes, tuples, div, printf
      
      # consider primes less than 485 (primes less than 252 would work)
      primes = Primes(485)
      
      # consider consecutive pairs of primes (primes.range(29, 242) is sufficient)
      for (p1, p2) in tuples(primes, 2):
        # form the total
        t = p1 + p2
        if t < 60: continue
        if t > 485: break
      
        # check it can be expressed as 5n + 10
        n = div(t - 10, 5)
        if n is None: continue
      
        # check it is the product of three prime numbers
        qs = primes.factor(t)
        if len(qs) != 3: continue
      
        # output solution
        printf("{t} = +({n}..{n4}) = {p1} + {p2} = *{qs}", n4=n + 4)
      

      Solution: There were 410 crenels in total.

      So we have:

      410 = 80 + 81 + 82 + 83 + 84
      410 = 199 + 211
      410 = 2 × 5 × 41

      Like

    • Frits 10:59 pm on 2 December 2021 Permalink | Reply

      More analysis and using the 6n + 1 or 6n – 1 rule (just for fun).

      Other than 2 and 3, prime numbers must be of the form 6n + 1 or 6n – 1.

      Enigma function is_prime() is called only once.
      Function islice() is borrowed from enigma function first().

        
      from itertools import islice
      from enigma import is_prime
      
      # t = 5n + 10 (where 10 <= n <= 95, so 60 <= t <= 485)
      # t = p1 + p2 (where p1 and p2 are consecutive primes) ==> t is even
      # t = q1 × q2 × q3 (where q1, q2, q3 are primes and q1 <= q2 <= q3) 
      # t is even ==> q1 = 2, n is even and 30 <= q2 x q3 <= 242
      
      # n is even ==> n = 2 * m and 5 <= m <= 47
      # t = p1 + p2 = 2 * (q2 * q3) = 10m + 10 = (m + 1) * 10
      
      # t must end on a zero ==> q2 must be 5 and 6 <= q3 <= 48
      # t = 10 * q3 ==> q3 = m + 1
      
      # list of prime numbers from 6 up to 48 (used for q3)
      P = {3, 5, 7}
      P |= {x for x in range(11, 49, 2) if all(x % p for p in P)}
      P = {x for x in P if x > 5}
      
      # try to express next prime as 6k - 1 or 6k + 1
      def nextprime(n):
        # in this puzzle n always ends on a 5
        return list(islice([p for x in range(n // 6 + 1, 81) for i in [-1, 1] 
                    if is_prime(p := 6 * x + i) and p > n], 0, 1))[0]
      
      # list of prime numbers from 31 (prime before 5 x 7) up to 235 (5 x 47)
      P2 = {3, 5, 7, 11, 13, 17}
      P2 |= {x for x in range(19, 236, 2) if all(x % p for p in P2)}
      
      # try to express previous prime as 6k - 1 or 6k + 1
      def prevprime(n):
        # in this puzzle n always ends on a 5
        return list(islice([p for x in range(n // 6, 0, -1) for i in [1, -1] 
                    if (p := 6 * x + i) in P2 and p < n], 0, 1))[0]
      
      bef35 = prevprime(35) # prime number before 5 x lowest q3 prime
      P2 = {x for x in P2 if x >= bef35}
      
      # add one more prime (to be found by nextprime_P2() )
      np = nextprime(max(P2))
      P2.add(np)
      P2limit = np // 6 + 1  # variable to be used in nextprime_P2()
      
      # try to express next prime as 6k - 1 or 6k + 1
      def nextprime_P2(n):
        # in this puzzle n always ends on a 5
        return list(islice([p for x in range(n // 6 + 1, P2limit) for i in [-1, 1]
                    if (p := 6 * x + i) in P2 and p > n], 0, 1))[0]   
      
      # t = q1 x q2 x q3 = 2 x 5 x q3
      for q3 in P:
        t = 10 * q3  
        # find prime before half of t
        p1 = prevprime(5 * q3) 
        
        # t = p1 + p2 (where p1 and p2 are consecutive primes)
        if t - p1 not in P2: continue
        
        if nextprime_P2(5 * q3) != t - p1: continue
        
        print(t, "crenels in total")
      

      Like

      • Jim Randell 4:30 pm on 3 December 2021 Permalink | Reply

        I’m considering adding [[ Primes.before(n) ]] and [[ Primes.after() ]] to the prime sieve class, which would give you the largest prime less than n and the smallest prime greater than n.

        The puzzle could then be solved with:

        from enigma import Primes, printf
        
        primes = Primes(252)
        
        for q in primes.irange(6, 48):
          m = 5 * q
          p1 = primes.before(m)
          p2 = primes.after(m)
          t = 2 * m
          if p1 + p2 == t:
            n = 2 * q - 2
            printf("t={t} = +({p1}, {p2}) = *(2, 5, {q}) = +({n}..{n4})", n4=n + 4)
        

        Like

  • Jim Randell 2:29 pm on 26 November 2021 Permalink | Reply
    Tags: by: Stephen Hogg   

    Teaser 3088: Bog standard deviation 

    From The Sunday Times, 28th November 2021 [link] [link]

     

    My four toilet rolls had zigzag-cut remnants (not unlike that shown). Curiously, each polygonal remnant had a different two-figure prime number of sides, each with a digit sum itself prime.

    Calculating the average number of sides for the four remnants and the average of their squares, I found that the average of the squares minus the square of the average had a value whose square root (the “standard deviation”) was a whole number.

    I also noticed that a regular convex polygon with a number of sides equal to the average number of sides would have an odd whole-number internal angle (in degrees).

    Give the “standard deviation”.

    [teaser3088]

     
    • Jim Randell 2:45 pm on 26 November 2021 Permalink | Reply

      A bit of a convoluted scenario, but the calculations are fairly straightforward.

      The average number of sides must be an integer to construct the polygon, and so the average of the squares must also be an integer, and so must the internal angle. So we can keep everything in the integers.

      This Python program runs in 46ms.

      Run: [ @replit ]

      from enigma import Primes, dsum, subsets, div, sq, is_square, printf
      
      primes = Primes(100)
      
      # candidate primes
      ps = list(p for p in primes.irange(10, 99) if dsum(p) in primes)
      
      # choose 4 of them
      for ns in subsets(ps, size=4):
        # calculate the mean, and mean square
        m = div(sum(ns), 4)
        m2 = div(sum(sq(n) for n in ns), 4)
        if m is None or m2 is None: continue
        # standard deviation
        sd = is_square(m2 - sq(m))
        if sd is None: continue
        # internal angle
        a = div(360, m)
        if a is None or a % 2 == 0: continue
      
        # output solution
        printf("{ns}; m={m} m2={m2} sd={sd} a={a}", a=180 - a)
      

      Solution: The “standard deviation” is 15.

      The prime numbers are: 23, 29, 47, 61.

      Which give a mean of 40, and a mean square of 1825. And a regular 40-sided polygon has internal angles of 171°.

      Without the regular polygon condition there are three potential integer solutions:

      (11, 29, 61, 67); m=42 sd=23
      (23, 29, 47, 61); m=40 sd=15
      (29, 43, 61, 67); m=50 sd=15

      A 42-gon and 50-gon don’t have whole number internal angles, so the requirement for the angle to be odd isn’t necessary (although it may help in a manual solution).

      Like

    • Frits 5:44 pm on 26 November 2021 Permalink | Reply

      Starting from the (odd, even) divisor pairs of number 360.

        
      from enigma import divisor_pairs, dsum, is_square
       
      P = {3, 5, 7}
      P |= {2} | {x for x in range(11, 100, 2) if all(x % p for p in P)}
       
      # candidate primes
      P = sorted(p for p in P if p > 9 and dsum(p) in P)
      
      # get_standard_deviation by decomposing number <t> into <k> increasing 
      # numbers from <ns> so that sum(<k> numbers) equals <t>
      def get_standard_deviation(t, k, ns, sq_avg, s=[]):
        if k == 1:
          if t in ns and t > s[-1]:
            # average of the squares minus the square of the average is square
            sd = is_square(sum(x**2 for x in s + [t]) // 4 - sq_avg)
            if sd is not None:
              yield sd
        else:
          for n in ns:
            if s and n <= s[-1]: continue
            yield from get_standard_deviation(t - n, k - 1, ns, sq_avg, s + [n])
      
      min_avg = sum(P[:4]) / 4
      max_avg = sum(P[-4:]) / 4
      penmax_avg = sum([P[-5]] + P[-3:]) / 4   # penultimate maximum
      
      # determine number of sides for all possible angles
      lst_nsides = [nsides for a, nsides in divisor_pairs(360) 
                    if a % 2 and min_avg <= nsides <= max_avg]
      
      # skip smallest angle if number of sides is too close to max_avg
      if penmax_avg < lst_nsides[0] < max_avg: 
        lst_nsides = lst_nsides[1:]
      
      # solve for all possible angles
      for avg in lst_nsides:
        for sd in get_standard_deviation(4 * avg, 4, P, avg**2):
          print("answer:", sd)
      

      Like

  • Jim Randell 4:40 pm on 19 March 2021 Permalink | Reply
    Tags: by: Stephen Hogg   

    Teaser 3052: Porcus facit griphus 

    From The Sunday Times, 21st March 2021 [link]

    “Argent bend sinister abased sable in dexter chief a hog enraged proper” blazons our shield (shaped as a square atop a semi-circle, with a 45° diagonal black band meeting the top corner). We’ve three shields. For the first, in centimetres, the top width (L) is an odd perfect cube and the vertical edge height of the band (V) is an odd two-figure product of two different primes. The others have, in inches, whole-number L (under two feet) and V values (all different). For each shield, the two white zones have almost identical areas. All three V/L values, in percent, round to the same prime number.

    Give the shortest top width, in inches.

    [teaser3052]

     
    • Jim Randell 6:00 pm on 19 March 2021 Permalink | Reply

      The puzzle is set by Stephen Hogg.

      This Python routine calculates the V/L ratio where the areas are equal numerically, and then looks for permissible L values for the shield measured in centimetres.

      We then look for integer V values within 10% of the “ideal” value, that have 2 different prime factors, and give a rounded percentage that is a prime.

      We then look for multiple shields that have an L value less than 24 inches, and a corresponding V value that give the same rounded percentage.

      This Python program runs in 50ms.

      Run: [ @replit ]

      from math import (pi, sqrt, atan2)
      from enigma import (find_value, intf, intc, Accumulator, irange, divf, divc, fdiv, group, item_from, is_prime, factor, iroot, powers, printf)
      
      # calculate the difference between the upper and lower areas
      def areas(V, L):
        # lower area: triangular bit
        t = L - V
        T = 0.5 * t * t
        # lower area: semi-circular bit
        a = 0.5 * L
        b = a - V
        a2 = a * a
        b2 = b * b
        # solve: x^2 + y^2 = a^2, y = x - b for x, y
        r = sqrt(2 * a2 - b2)
        x = 0.5 * (r + b)
        y = 0.5 * (r - b)
        theta = pi - atan2(y, x)
        # calculate the areas
        upper = a * L
        lower = T + 0.5 * (a2 * theta + b * y)
        # return the difference in areas
        return fdiv(2 * abs(upper - lower), upper + lower)
      
      # find the V/L ratio when the white areas are equal
      r0 = find_value((lambda v: areas(v, 1)), 0, 0.25, 0.50).v
      printf("[r0 = {r0}]")
      
      # generate (V, L, rounded V/L percentage) values
      def generate(Ls):
        for L in Ls:
          # calculate exact V
          v = r0 * L
          # allow a tolerance of 10%
          for V in irange(intc(0.9 * v), intf(1.1 * v)):
            # calculate the rounded V/L percentage
            p = divf(200 * V + L, 2 * L)
            if not is_prime(p): continue
            # return values
            yield (V, L, p)
      
      # group (V, L, p) values by the percentage, for the shields measured in inches
      d = group(generate(irange(2, 23)), by=item_from("p", "V, L, p"))
      
      # find the shield measured in centimetres
      M = iroot(divc(100, 0.9 * r0), 3)
      for (V, L, p) in generate(powers(3, M, 3, step=2)):
        # V is an odd, 2-digit number
        if V % 2 == 0 or V < 10 or V > 99: continue
        # V should have 2 prime factors
        fs = factor(V)
        if not (len(fs) == 2 and len(set(fs)) == 2): continue
      
        # look for shields measured in inches
        vs = d.get(p)
        if (not vs) or len(vs) < 2: continue
      
        # output solution
        r = Accumulator(fn=min)
        inch = lambda x: fdiv(x, 2.54)
        printf("V/L ~ {p}%")
        printf("-> 1: L = {L}cm ({Li:.2f}in), V = {V}cm ({Vi:.2f}in) [error = {r:.6f}]", Li=inch(L), Vi=inch(V), r=areas(V, L))
        r.accumulate(inch(L))
        for (Vi, Li, _) in vs:
          printf("-> 2: L = {Li}in, V = {Vi}in [error = {r:.6f}]", r=areas(Vi, Li))
          r.accumulate(Li)
        printf("=> min L = {r:.2g}in", r=r.value)
        printf()
      

      Solution: The shortest L value is: 17 inches.

      The measurements for each of the three shields are:

      L = 125cm (49.2in), V = 51cm (20.1in)
      L = 17in, V = 7in
      L = 22in, V = 9in
      V/L ≈ 41%

      The program calculates a more precise ratio for equal areas: V/L = 0.408083900721218.


      In order to calculate the area of the lower white area on the shield, I started with a polynomial approximation based on the three values at V=0, V=L/2, V=L.

      This is sufficient to find the answer (as, I suspect, are many other rough estimates).

      But for the program above I came up with a a way of calculating the area exactly, based on the following diagram:

      The shield is turned upside down and we place x,y axes through the centre of the semicircle.

      Then using: a = L/2, b = L/2 − V

      The semicircle is part of the circle: x² + y² = a²

      The (now) upper line of the stripe is the line: y = x − b

      And these meet at: (x, y) = ((r + b)/2, (r − b)/2), where: r = √(2a² − b²)

      So we can calculate the angle θ = arctan(y, x)

      And the area of the yellow triangle = (1/2)ab sin(θ) = by/2

      The orange region is then the area of the sector of the circle that subtends the angle θ, less the area of the yellow triangle.

      And once we know the area of the orange region the area of the (formerly) lower region of the shield can be easily determined.

      Like

      • Tony Brooke-Taylor 10:13 am on 22 March 2021 Permalink | Reply

        I found you can get away with approximating away the arctan term and I eliminated the need to set a tolerance by finding the valid V/L ratios closest to the target prime. However, my code takes 40 times longer to run than yours Jim so I have some other work to do!

        Like

        • Tony Brooke-Taylor 10:56 am on 22 March 2021 Permalink | Reply

          … so it takes 1/4s to import numpy and 5ms for the rest of my program to run. Now I know why people bother with the math library.

          Like

    • Robert Brown 8:25 pm on 20 March 2021 Permalink | Reply

      The information about equal white zones is redundant. There is only one solution to the metric shield, which defines the prime. Then there are only two possible imperial solutions where v/a rounds to give the same prime. That solves the teaser. It’s good of him to tell us that all 3 solutions have white zones with ‘almost’ identical areas, but it adds nothing to the teaser solution.

      Like

      • Jim Randell 9:04 pm on 20 March 2021 Permalink | Reply

        @Robert: If we didn’t have the “equal area” constraint what would stop a solution like this:

        V/L ≈ 31%
        L = 125cm, V = 39cm
        L = 13in, V = 4in
        L = 16in, V = 5in

        I think we need the additional constraint to eliminate such solutions (in this one the areas differ by about 16%).

        But you don’t need to be completely accurate. A rough estimate will get you to the answer.

        Like

    • Hugh Casement 7:04 am on 21 March 2021 Permalink | Reply

      I thought I knew a bit about heraldry, but had never come across the term ‘abased’. However, it’s clear that the bend has slipped down so that its upper edge, rather than its centre line, meets the corner of the shield. ‘Enraged’ is surely an invention, n’est-ce pas?

      The area of white space must mean before the piglet has flown in. Then it’s a quick back-of-the-envelope calculation — no computer needed. Teasers are seldom so easy.

      Like

    • Hugh Casement 11:17 am on 21 March 2021 Permalink | Reply

      Whatever S. Hogg’s ability to blazon may be, his Latin is shocking!
      As every schoolboy knows, a direct object goes in the accusative: porcus imitat gryphem (for example).
      Better might be porci volent, though I’m not sure how far we can trust the googly translator.

      Like

  • Jim Randell 4:51 pm on 19 February 2021 Permalink | Reply
    Tags: by: Stephen Hogg   

    Teaser 3048: Nero Scrag from Carregnos 

    From The Sunday Times, 21st February 2021 [link]

    Our holiday rep, Nero, explained that in Carregnos an eight-digit total of car registrations results from combinations of three Greek capital letters after four numerals (e.g. 1234 ΩΘΦ), because some letters of the 24-letter alphabet and some numerals (including zero) are not permitted.

    For his own “cherished” registration the number tetrad is the rank order of the letter triad within a list of all permitted letter triads ordered alphabetically. Furthermore, all permitted numeral tetrads can form such “cherished” registrations, but fewer than half of the permitted letter triads can.

    Nero asked me to guess the numbers of permitted letters and numerals. He told me that I was right and wrong respectively, but then I deduced the permitted numerals.

    List the permitted numerals in ascending order.

    [teaser3048]

     
    • Jim Randell 5:29 pm on 19 February 2021 Permalink | Reply

      Nero Scrag is an anagram of Carregnos, which itself may be written as “car reg nos” = “car registration numbers”.

      The wording of the puzzle is a bit convoluted, but I think there is a unique solution.

      This Python program runs in 56ms.

      Run: [ @repl.it ]

      from enigma import irange, ndigits, group, unpack, printf
      
      # generate candidate solutions
      # return (number-of-digits, number-of-letters, total-number-of-digit-tetrads, total-number-of-letter-triads)
      def generate():
        # consider number of digits available (< 9)
        for nd in irange(1, 8):
          # number of digit tetrads
          td = nd ** 4
      
          # consider number of letters available (< 23)
          for ns in irange(1, 22):
            # number of letter triads
            ts = ns ** 3
      
            # total number of possible registrations
            t = td * ts
            # is 8 digits
            if not(ndigits(t) == 8): continue
      
            # all digit tetrads correspond to a letter triad
            # so remove impossible situations
            if 1111 * nd > ts: continue
      
            # fewer than half the letter triads correspond to number tetrads
            if not(ts > 2 * td): continue
      
            printf("[nd={nd} -> td={td}; ns={ns} -> ts={ts}; t={t}]")
            yield (nd, ns, td, ts)
      
      # group candidate solutions by the number of letters (which the setter guessed right)
      d = group(generate(), unpack(lambda nd, ns, td, ts: ns))
      
      # look for a group with only two candidates
      for (k, vs) in d.items():
        if len(vs) != 2: continue
        # look for candidates with only one set of digits
        for (nd, ns, td, ts) in vs:
          # are the digits forced to be 1..nd?
          if 1111 * (nd + 1) > ts:
            # output solution
            printf("digits = 1..{nd} [nd={nd} ns={ns}]")
      

      Solution: The digits are: 1, 2, 3, 4, 5, 6, 7.

      The setter guessed there were 20 letters and 6 digits.

      He was right about the number of letters, but wrong about the number of digits.

      The only other possibility with 20 letters is 7 digits, so that must be the correct number of digits.

      With 20 digits there are 20^3 = 8000 possible letter triads (which can be enumerated from 1 to 8000).

      The lowest valued set of 7 digits is 1..7, and the highest numeric tetrad in this case is 7777, which corresponds to an entry in the enumeration of letter triads.

      If not all of the digits from 1..7 are permissible, then the highest digit would be 8 or 9, and the highest numeric tetrad would be 8888 or 9999, but neither of these correspond to entries in the enumeration of letter triads. So these situations are not possible.

      So we know that the set of permissible digits must be 1..7.

      This means there are 2401 digit tetrads and 8000 letter triads.

      Every digit tetrad (from 1111 to 7777) corresponds to one of the letter triads, but any letter triad that has an index containing a 0, 8, or 9 does not have a corresponding digit tetrad. (Where we represent the indices with leading zeros to pad them to 4 digits, if necessary). There are 5599 of these, so less than half of the letter triads have a corresponding digit tetrad, as required.

      Like

      • Frits 9:10 pm on 19 February 2021 Permalink | Reply

        Ah, I see you now have a different answer. I couldn’t understand your previous solution.
        This is a puzzle where I needed your code to understand the puzzle.

        Like

        • Jim Randell 7:24 am on 20 February 2021 Permalink | Reply

          @Frits: The wording of the puzzle is a bit complicated, but I think it makes sense.

          In my original program I got the final check the wrong way round, but I have corrected that now.

          Like

      • Jim Randell 8:14 am on 28 February 2021 Permalink | Reply

        Here is a more detailed explanation of the logic used in the program:

        Some digits (including 0) are not permitted, so there are fewer than 9 digits available.

        And some letters are not permitted, so there are fewer than 23 letters available.

        If there are nd digits available, then we can make nd^4 possible digit tetrads.

        And if there are ns letters (symbols) available, then we can make ns^3 possible letter triads.

        The total number of registrations that can be made is therefore: (nd^4) × (ns^3), and this must be an 8-digit number.

        Also the letter triads can be enumerated (in lexicographical order) from 1 to ns^3.

        And each digit tetrad provides a valid index into the list of enumerated letter triads.

        So if d is a permitted digit then the digit tetrad dddd must be an index into the list of letter triads.

        So: 1111 × d ≤ ns^3.

        And with nd possible digits, that exclude the digit 0, the maximum permitted digit must be at least nd.

        So we can skip situations where: 1111 × nd > ns^3, as there are no viable digit sets.

        We are also told that fewer than half the letter triads correspond to digit triads.

        So: (ns^3) > 2 × (nd^4)

        These restrictions limit the possible values of nd and ns.

        The setter makes guesses for these values, and gets ns right and nd wrong.

        But from this information he is able to deduce, not just the value of nd, but the actual set of permitted digits.

        So from his guess for ns, we know there must be 2 possibilities for nd. On being told the candidate he chose was wrong, the setter can deduce that the other candidate must be the correct one.

        So now he knows the values of both ns and nd. But he can go further and deduce the actual set of permitted digits.

        This means that there can only be one possible set of digits for the values of ns and nd.

        The set with the smallest valued digit tetrads will be {1..nd}, and we already know that the value (1111 × nd) indexes into the list of letter triads.

        And we want to exclude all other possible sets. A set that excludes just one of the digits 1..nd would have a maximum digit of (nd + 1), and in order for this to be excluded the maximum digit tetrad of (1111 × (nd + 1)) must be larger than the maximum index into the list of letter triads.

        i.e.: (1111 × (nd + 1)) > ns^3

        In that case only the set of digits {1..nd} forms a viable set, so this provides the answer.

        Like

    • Brian Gladman 10:44 pm on 19 February 2021 Permalink | Reply

      @Jim I have the same logic up to line 30 but I don’t see the rationale for only considering solutions with two candidates (line 36). But it does seem necessary to obtain a unique solution.

      Like

      • Jim Randell 10:54 pm on 19 February 2021 Permalink | Reply

        @Brian: My reasoning was that when the setter guesses the number of permissible letters and digits, and gets the number of letters right, but the number of digits wrong, he is then able to deduce the correct number of digits. So for the number of letters guessed, there must be only two options for the number of digits. The setter went for the wrong one to begin with, but on being told he was wrong he was able to deduce the correct number, so there was only one other option remaining.

        Like

        • Brian Gladman 11:37 pm on 19 February 2021 Permalink | Reply

          Thanks Jim. But it is logical for the setter to apply your line 40 logic before he is asked to guess and if he does this he only needs the first of the two answers to deduce the solution. So we have to assume he is acting illogically in order to deduce a unique solution, which seems a bit odd to me.

          Like

          • Jim Randell 7:17 am on 20 February 2021 Permalink | Reply

            @Brian: But the setter doesn’t know he is going to be able to deduce the set of digits before he makes his guesses. Once he gets the answers however he knows how many letters there are (as he guessed that correctly), and as explained above there is only one candidate remaining for the number of digits, so he knows that too.

            He then realises that given those values for the number of digits and number of letters, there is only one possible set of digits that can work, so he can deduce what the digits are (not just how many of them there are).

            We aren’t told what guesses the setter made, but the fact that the scenario unrolled as described lets us work out what the setters guesses must have been, and so we can also determine what the set of digits must be, and hence answer the puzzle.

            Like

            • Brian Gladman 12:54 pm on 20 February 2021 Permalink | Reply

              Thanks Jim. My logic was originally the same as yours (up to your line 30) but I have now changed it to avoid the assumption (on your line 23) that the number of digits in use and the maximum digit in use are the same. We now arrive at the same answer in different ways.

              Like

              • Jim Randell 1:45 pm on 20 February 2021 Permalink | Reply

                @Brian: I don’t assume the maximum digit is the same as the number of digits, only it is at least this value (which it must be, as 0 is excluded).

                But I think in your method you also need to consider that the maximum digit could be 9.

                Liked by 1 person

                • Brian Gladman 5:09 pm on 20 February 2021 Permalink | Reply

                  @Jim. Good point, changed now.

                  Like

                • Tony Brooke-Taylor 9:39 am on 21 February 2021 Permalink | Reply

                  Jim, doesn’t your line 40 forbid cases where the maximum digit (int(ts/1111)) is greater than the number of digits (ns)? I am sure we must apply that condition somewhere to get a unique answer, and it is the only way our subject could have inferred all the digits.

                  I applied almost exactly the same logic as you but I did a bit of analysis first to reduce the ranges for the two main loops. We only need to explore the space defined by 10^7 <=T<10^8, where T=nd^4*ns^3. Reduces run-time by about half.

                  Like

                  • Jim Randell 9:54 am on 21 February 2021 Permalink | Reply

                    @Tony: Yes. That line is there to ensure there is only one possible set of digits at that stage, because if there were more than one the setter would not have been able to deduce what the permissible digits are.

                    And there is only one set of digits if the maximum digit is constrained to be the same as the number of digits (as 0 is excluded). So the set of digits is {1..nd}.

                    Like

    • Frits 12:58 am on 21 February 2021 Permalink | Reply

      Under the assumption that “some letters” means “at least 2 letters”

      from collections import defaultdict
      from enigma import SubstitutedExpression, divc
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
        #  N = number of permitted numerals
        # LE = number of permitted letters
        
        # the maximum possible car registration has at least 8 characters:
        # formula: no_numerals ** 4  *  no_letters ** 3 >= 10 ** 7 
        #
        # choose the highest number of permitted letters (twenty two)  
        # to calculate the lowest number of permitted numbers
        "N >= (divc(10 ** 7, 22 ** 3) ** 0.25)",
        "N < 9",
        
        "LE >= (divc(10 ** 7, N ** 4) ** (1 / 3))",
        "LE < 23",
        
        # consider the maximum 4-digits numbers (1111 * highest digit)
        # the smallest must not be greater than the number of letter triads
        "1111 * N <= LE ** 3",
        
        # fewer than half the letter triads correspond to number tetrads
        "LE ** 3 > 2 *( N ** 4)",
        ],
        answer="LE, N, LE ** 3",
        d2i=dict([(0, "N")] + [(k, "L") for k in range(3, 10)]),
        distinct="",
        verbose=0)   
      
      # collect and sort solutions
      sols = sorted(y for _, y in p.solve())
      
      # group solutions by number of permitted letters
      d = defaultdict(list)
      for le, n, ntriads in sols:
        d[le].append([n, ntriads])
        
      for k, v in d.items():
        # only with 2 options for the number of permitted numerals 
        # you can still make deductions
        if len(v) != 2: continue
        
        # "I deduced the permitted numerals"
        
        # you can only know the permitted numerals if they are 1...N
        # this must be the last entry in <v>
        
        # check that N+1 is not permitted as a numeral
        if 1111 * (v[1][0] + 1) > v[1][1]:  
          print(f"answer 1...{v[1][0]}")
      

      Like

      • Tony Brooke-Taylor 9:43 am on 21 February 2021 Permalink | Reply

        Frits, your lines 15-19 are equivalent to the analysis I referred to in my comment to Jim. I also relaxed the assumption that ‘some’ meant ‘at least two’, and the solution still works.

        Like

  • Jim Randell 5:01 pm on 29 January 2021 Permalink | Reply
    Tags: by: Stephen Hogg   

    Teaser 3045: Let Tel play BEDMAS hold ’em! 

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

    Awaiting guests on poker night, Tel placed (using only clubs, face-up, in order left-to-right) the Ace (=1) to 9 (representing numerals), then interspersed the Ten, Jack, Queen and King (representing –, +, × and ÷ respectively) in some order, but none together, among these.

    This “arithmetic expression” included a value over 1000 and more even than odd numbers. Applying BEDMAS rules, as follows, gave a whole-number answer. “No Brackets or powErs, so traverse the expression, left-to-right, doing each Division or Multiplication, as encountered, then, again left-to-right, doing each Addition or Subtraction, as encountered.”

    Tel’s auntie switched the King and Queen. A higher whole-number answer arose. Tel displayed the higher answer as a five-card “flush” in spades (the Jack for + followed by four numeral cards).

    Give each answer.

    [teaser3045]

     
    • Jim Randell 5:51 pm on 29 January 2021 Permalink | Reply

      I took “whole number” to be any integer, although you get the same answer if you just use positive integers.

      It was fun writing the [[ evaluate() ]] routine to perform the calculations in the described fashion (although it is just standard arithmetic precedence rules).

      The following Python program runs in 59ms.

      Run: [ @repl.it ]

      from enigma import Rational, irange, subsets, tuples, peek, as_int, catch, update, multiset, join, printf
      
      # implementation of rationals
      F = Rational()
      
      # map operators to implementation
      fn = {
        '+': (lambda a, b: a + b),
        '-': (lambda a, b: a - b),
        '*': (lambda a, b: a * b),
        '/': (lambda a, b: F(a, b)),
      }
      
      # evaluate the expression <ss>
      def evaluate(ss):
        ss = list(ss)
        # precedence order
        for ops in [set('*/'), set('+-')]:
          while True:
            # find the leftmost occurrence of an operator
            i = peek((i for (i, op) in enumerate(ss) if op in ops), default=-1)
            if i == -1: break
            # apply the operation
            assert 0 < i < len(ss) - 1
            n = fn[ss[i]](ss[i - 1], ss[i + 1])
            ss[i - 1:i + 2] = [n]
        assert len(ss) == 1
        return ss[0]
      
      # interleave 2 sequences (until one runs out)
      def interleave(s1, s2):
        (i1, i2) = (iter(s1), iter(s2))
        while True:
          try:
            yield next(i1)
            yield next(i2)
          except StopIteration:
            break
      
      # the string of digits
      digits = "123456789"
      ds = multiset.from_seq(digits)
      
      # slice up the string of digits
      n = len(digits)
      for ps in subsets(irange(1, n - 1), size=4, fn=list):
        ns = tuple(int(digits[i:j]) for (i, j) in tuples([0] + ps + [n]))
        # at least one number is greater than 1000
        if not any(n > 1000 for n in ns): continue
        # there are more even numbers than odd numbers
        if not(len(ns) > 2 * sum(n % 2 for n in ns)): continue
      
        # insert the operators
        for ops in subsets("+-*/", size=4, select="P"):
          # make the first expression
          ss1 = list(interleave(ns, ops))
          # evaluate it
          r1 = catch(as_int, evaluate(ss1))
          if r1 is None: continue
      
          # swap * and /
          ss2 = update(ss1, [(ss1.index('*'), '/'), (ss1.index('/'), '*')])
          r2 = catch(as_int, evaluate(ss2))
          if r2 is None or not(r1 < r2): continue    
      
          # the result is a positive 4-digit number
          if r2 < 1000 or r2 > 9999: continue
          # that can be represented using the available digits
          if not ds.issuperset(str(r2)): continue
      
          # output solution
          printf("{ss1} = {r1}; {ss2} = {r2}", ss1=join(ss1, sep=" "), ss2=join(ss2, sep=" "))
      

      Solution: Tel’s answer was 1274. Auntie’s answer was 1289.

      The expressions are:

      Tel: 1234 + 56 × 7 ÷ 8 − 9 = 1274
      Auntie: 1234 + 56 ÷ 7 × 8 − 9 = 1289

      There are only 6 ways to split up the digits in the required fashion:

      1 | 2 | 34 | 5678 | 9
      1 | 2 | 3456 | 78 | 9
      12 | 3 | 4 | 5678 | 9
      12 | 3456 | 7 | 8 | 9
      1234 | 5 | 6 | 78 | 9
      1234 | 56 | 7 | 8 | 9

      Which lead to 22 expressions that evaluate to a positive integer.

      There are 2 further candidate solutions resulting in 4-digit positive numbers, but Tel would not be able to display the result as described:

      Tel: 12 × 3 ÷ 4 + 5678 − 9 = 5678
      Auntie: 12 ÷ 3 × 4 + 5678 − 9 = 5685

      Tel: 1234 − 56 ÷ 7 × 8 + 9 = 1179
      Auntie: 1234 − 56 × 7 ÷ 8 + 9 = 1194

      Like

      • Tony Brooke-Taylor 11:02 am on 31 January 2021 Permalink | Reply

        I was going mad trying to find my error but when I compared my solution to yours I get the same. I guess the puzzle allows for an Ace in the flush.

        Like

        • Jim Randell 2:05 pm on 31 January 2021 Permalink | Reply

          @Tony: There is only one candidate solution that is positive, and is composed of 4 distinct positive digits. And I was happy enough that this could be represented using the described cards.

          Fortunately I don’t know enough about poker to know if this counts as a “5 card flush” or not.

          Like

    • Frits 9:23 pm on 30 January 2021 Permalink | Reply

      from enigma import SubstitutedExpression
      from itertools import  permutations
      
      def check(li):
        # credit: B. Gladman
        # there must be more even than odd numbers
        if sum([x & 1 for x in li]) > 2:
          return ""
          
        li2 = [str(x) for x in li]  
        for p in permutations("*/+-", 4):
          exp = ''.join(a + b for a, b in zip(li2, p + ('',)))
          ev = eval(exp) 
          if ev % 1 == 0 and ev >= 0:
            exp2 = ''.join(chr(ord(c) ^ 5) if c in '/*' else c for c in exp)
            ev2 = eval(exp2) 
            if ev2 > ev and ev2 % 1 == 0:
              ev2 = int(ev2)
              # larger answer has distinct non-zero digits
              if "0" not in str(ev2) and len(set(str(ev2))) == len(str(ev2)):
                return exp + " ; " + exp2
            
        return ""
      
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
        "T + 1 == U or T == 0",
        "S + 1 == T or S == 0",
        "R + 1 == S or R == 0",
        "[x for x in [R, S, T, U] if x > 0][0] == Q + 1",
      
        "P + 1 == Q or P == 0",
        "O + 1 == P or O == 0",
        "N + 1 == O or N == 0",
        "[x for x in [N, O, P, Q] if x > 0][0] == M + 1",
      
        "L + 1 == M or L == 0",
        "K + 1 == L or K == 0",
        "J + 1 == K or J == 0",
        "[x for x in [J, K, L, M] if x > 0][0] == H + 1",
      
        "G + 1 == H or G == 0",
        "F + 1 == G or F == 0",
        "E + 1 == F or E == 0",
        "[x for x in [E, F, G, H] if x > 0][0] == D + 1",
      
        "C + 1 == D or C == 0",
        "B + 1 == C or B == 0",
        "A + 1 == B or A == 0",
        "[x for x in [A, B, C, D] if x > 0][0] == 1",
        
        # included a value over 1000
        "sum([A > 0, E > 0, J > 0, N > 0, R > 0]) = 1",
        
        "len(check([ABCD, EFGH, JKLM, NOPQ, RSTU])) > 0",
        
        ],
        answer="check([ABCD, EFGH, JKLM, NOPQ, RSTU])", 
        distinct="",
        env=dict(check=check),
        d2i=dict([(0, "DHMQU")] + 
                 [(1, "EFGHJKLMNOPQRSTU")] + 
                 [(2, "JKLMNOPQRSTU")] + 
                 [(3, "NOPQRSTU")] +
                 [(4, "RSTU")] +
                 [(5, "RSTU")] +
                 [(k, "U") for k in range(6, 9)]
                 ),
      
        #reorder=0,
        verbose=0
        )   
        
      # Print answer
      for (_, ans) in p.solve():
        print(f"{ans}")
      

      Like

  • Jim Randell 8:27 pm on 31 December 2020 Permalink | Reply
    Tags: by: Stephen Hogg   

    Teaser 3041: The best game played in 1966 

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

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

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

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

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

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

    [teaser3041]

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

      This Python program runs in 45ms.

      Run: [ @repl.it ]

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

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

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

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

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

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

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

      Like

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

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

      Like

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

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

        Like

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

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

      Liked by 1 person

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

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

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

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

      Like

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

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

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

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

        Like

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

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

        Like

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

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

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

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

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

      Like

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

        @Tony,

        Interesting idea.

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

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

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

        Like

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

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

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

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

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

      Like

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

        Adding this will only print the 2 solutions

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

        Like

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

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

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

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

        Like

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

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

      Like

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

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

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

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

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

        And so on, until all 7 shots are taken.

        Like

  • Jim Randell 4:25 pm on 20 November 2020 Permalink | Reply
    Tags: by: Stephen Hogg   

    Teaser 3035: Friend of the Devil 

    From The Sunday Times, 22nd November 2020 [link]

    My friend, “Skeleton” Rose, rambled on with me and my uncle (“The Devil” and “Candyman”) about Mr Charlie, who gave, between us, three identical boxes of rainbow drops.

    Each identical box’s card template had a white, regular convex polygonal base section with under ten sides, from each of which a similar black triangular star point extended. All these dark star points folded up to an apex, making an enclosed box.

    The number of sweets per box equalled the single-figure sum of its own digits times the sum of the star points and the box’s faces and edges. If I told you how many of the “star point”, “face” and “edge” numbers were exactly divisible by the digit sum, you would know this number of sweets.

    How many sweets were there in total?

    [teaser3035]

     
    • Jim Randell 4:52 pm on 20 November 2020 Permalink | Reply

      If the base of the box is a k-gon (so 3 ≤ k < 10), then there are k “star points” and the closed box forms a polyhedron with (k + 1) faces and 2k edges.

      So if there are n sweets in the box, we have:

      n = dsum(n) × (k + (k + 1) + 2k)
      ⇒ k = ((n / dsum(n)) − 1) / 4

      The largest possible digit sum is 9, and the largest possible value for k is also 9, so the maximum value for n is 9×(4×9 + 1) = 333.

      This Python program considers sweet numbers (up to 333) and finds numbers unique by the given measure. It runs in 45ms.

      Run: [ @repl.it ]

      from enigma import irange, nsplit, div, unpack, filter_unique, printf
      
      # generate possible numbers of sweets
      def sweets(N=333):
        # consider numbers of sweets (n)
        for n in irange(1, N):
          # calculate the digit sum of n
          d = sum(nsplit(n))
          if d > 9: continue
          # calculate the number of sides of the polygon
          k = div(n - d, 4 * d)
          if k is None or k < 3 or k > 9: continue
          # measure = how many of (k, k + 1, 2k) are divisible by d
          m = sum(x % d == 0 for x in (k, k + 1, 2 * k))
          yield (n, m)
      
      # find values for n, unique by measure m
      r = filter_unique(sweets(), unpack(lambda n, m: m), unpack(lambda n, m: n))
      
      # output solution
      for (n, m) in r.unique:
        printf("n={n} [m={m}]")
      

      Solution: There were 666 sweets in total.

      There are 222 sweets in each of the three boxes.

      The digit sum of 222 is 6.

      The base of each box is a regular nonagon (9 sides), so the number of star points is 9, the number of faces of the shape formed by the (closed) box is 10, and the number of edges is 18.

      The digit sum (6), multiplied by the sum of the star points (9), faces (10), and edges (18) = 6×(9 + 10 + 18) = 6×37 = 222, the same as the number of sweets in the box.

      And this is the only case where just one the three summands (edges = 18) is divisible by the digit sum (6).

      There are 8 candidate numbers of sweets, grouped by the shape of the boxes:

      k=3: n=117
      k=4: n=153
      k=6: n=150, 225
      k=7: n=261
      k=9: n=111, 222, 333

      Like

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

        Here is a more efficient version, that also does not need the upper bound on the number of sweets.

        Run: [ @repl.it ]

        from enigma import irange, nsplit, unpack, filter_unique, printf
        
        # generate possible numbers of sweets
        def sweets():
          # consider number of sides of the polygon (k)
          for k in irange(3, 9):
            # consider possible digit sums (d)
            for d in irange(1, 9):
              # calculate number of sweets (n)
              n = d * (4 * k + 1)
              # check the digit sum of n
              if sum(nsplit(n)) != d: continue
              # measure = how many of (k, k + 1, 2k) are divisible by d
              m = sum(x % d == 0 for x in (k, k + 1, 2 * k))
              yield (n, m)
        
        # find values for n, unique by measure m
        r = filter_unique(sweets(), unpack(lambda n, m: m), unpack(lambda n, m: n))
        
        # output solution
        for (n, m) in r.unique:
          printf("n={n} [m={m}]")
        

        Like

  • Jim Randell 4:49 pm on 2 October 2020 Permalink | Reply
    Tags: by: Stephen Hogg   

    Teaser 3028: Rainbow numeration 

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

    Dai had seven standard dice, one in each colour of the rainbow (ROYGBIV). Throwing them simultaneously, flukily, each possible score (1 to 6) showed uppermost. Lining up the dice three ways, Dai made three different seven-digit numbers: the smallest possible, the largest possible, and the “rainbow” (ROYGBIV) value. He noticed that, comparing any two numbers, only the central digit was the same, and also that each number had just one single-digit prime factor (a different prime for each of the three numbers).

    Hiding the dice from his sister Di’s view, he told her what he’d done and what he’d noticed, and asked her to guess the “rainbow” number digits in ROYGBIV order. Luckily guessing the red and orange dice scores correctly, she then calculated the others unambiguously.

    What score was on the indigo die?

    I’ve changed the wording of the puzzle slightly to make it clearer.

    [teaser3028]

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

      (Note: I’ve updated my program (and the puzzle text) in light of the comment by Frits below).

      This Python program runs in 49ms.

      Run: [ @repl.it ]

      from enigma import irange, subsets, nconcat, filter_unique, printf
      
      # single digit prime divisor
      def sdpd(n):
        ps = list(p for p in (2, 3, 5, 7) if n % p == 0)
        return (ps[0] if len(ps) == 1 else None)
      
      # if flag = 0, check all values are the same
      # if flag = 1, check all values are different
      check = lambda flag, vs: len(set(vs)) == (len(vs) if flag else 1)
      
      # all 6 digits are represented
      digits = list(irange(1, 6))
      
      # but one of them is repeated
      ans = set()
      for (i, d) in enumerate(digits):
        ds = list(digits)
        ds.insert(i, d)
        # make the smallest and largest numbers
        smallest = nconcat(ds)
        p1 = sdpd(smallest)
        if p1 is None: continue
        largest = nconcat(ds[::-1])
        p2 = sdpd(largest)
        if p2 is None or p2 == p1: continue
        printf("smallest = {smallest} ({p1}); largest = {largest} ({p2})")
      
        # find possible "rainbow" numbers
        rs = list()
        for s in subsets(ds[:3] + ds[4:], size=len, select="P", fn=list):
          s.insert(3, ds[3])
          # rainbow has only the central digit in common with smallest and largest
          if not all(check(i != 3, vs) for (i, vs) in enumerate(zip(s, ds, ds[::-1]))): continue
          rainbow = nconcat(s)
          p3 = sdpd(rainbow)
          if p3 is None or not check(1, (p1, p2, p3)): continue
      
          rs.append(tuple(s))
      
        # find rainbow numbers unique by first 2 digits
        for rainbow in filter_unique(rs, (lambda s: s[:2])).unique:
          n = nconcat(rainbow)
          printf("-> rainbow = {n} ({p3})", p3=sdpd(n))
          # record the indigo value
          ans.add(rainbow[5])
      
      # output solution
      printf("indigo = {ans}")
      

      Solution: The score on the indigo die is 4.

      Each of the digits 1-6 is used once, and there is an extra copy of one of them. So there is only one possible set of 7 digits used.

      The smallest number is: 1234456 (divisible by 2).

      And the largest number is: 6544321 (divisibly by 7).

      There are 17 possible values for the “rainbow” number, but only 3 of them are uniquely identified by the first 2 digits: 2314645, 3124645, 3614245 (and each is divisible by 5).

      The scores on the green, indigo and violet dice are the same for all three possible “rainbow” numbers: 4, 4, 5. So this gives us our answer.

      Like

    • Frits 11:02 pm on 2 October 2020 Permalink | Reply

      “each number had just one prime factor under 10 (different for each number)”.

      The three numbers you report seem to have same prime factors under 10, maybe I have misunderstood.

      Like

      • Jim Randell 11:10 pm on 2 October 2020 Permalink | Reply

        @Frits: I think you could be right. I took it to mean that it wasn’t the same prime in each case (two of the numbers I originally found share a prime). But requiring there to be three different primes does also give a unique answer to the puzzle (different from my original solution). So it could well be the correct interpretation (and it would explain why we weren’t asked to give the rainbow number). Thanks.

        Like

    • Frits 11:35 pm on 2 October 2020 Permalink | Reply

      @Jim: I hope to publish my program tomorrow (for three different prime numbers). I don’t have a clean program yet.

      Your solution also seems to be independent of the indigo question (it could have been asked for another colour). In my solution this specific colour is vital for the solution.

      Like

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

      Next time I try to use the insert function (list).

       
      from enigma import factor, irange, concat, peek 
      from itertools import permutations as perm
      from collections import defaultdict
      
      P = {2, 3, 5, 7}
      
      # number of same characters at same positions
      nr_common = lambda x, y: sum(1 for i, a in enumerate(x) if a == y[i])
      
      # prime factors under 10
      factund10 = lambda x: [p for p in P if int(x) % p == 0]
      
      # if list contains one entry then return possible values at position i
      charvals = lambda s, i: {x[0][i] for x in s if len(x) == 1}
      
      n = 6
      digits = concat([x for x in irange(1, n)])
      
      # for each digit i occuring twice in lowest and highest number
      for i in irange(1, n):
        str_i = str(i)
        # build lowest and highest number
        low = digits[:i] + str_i + digits[i:]
        hgh = low[::-1]
       
        # get prime factors under 10 
        u10low = factund10(low) 
        u10hgh = factund10(hgh) 
        
        # each number with one prime factor under 10 (different for each number)
        if len(u10low) != 1 or len(u10hgh) != 1 or u10low[0] == u10hgh[0]:
           continue
       
        rainbow = defaultdict(list)
       
        # for this combination of lowest and highest check the rainbow possibilities
        for pe in perm(low[:n//2] + low[n//2 + 1:]):
          # weave central digit into permutation pe at center position
          rb = concat(pe[:n//2] + tuple(low[n//2]) + pe[n//2:])
          
          # check rainbow number on only the central digit being the same
          if nr_common(rb, low) != 1 or nr_common(rb, hgh) != 1: 
            continue
      
          u10rb = factund10(int(rb)) 
          # all three prime factors under 10 are different
          if len(u10rb) == 1 and u10rb[0] != u10low[0] and u10rb[0] != u10hgh[0]:
            # store rainbow number with as key first 2 digits
            rainbow[rb[:2]].append(rb)
            
        # if first 2 digits rainbow number is unique then list indigo values
        indigo = charvals(rainbow.values(), 5)  
        if len(indigo) == 1:
          print(f"The score on the indigo die: {peek(indigo)}")
      

      Like

    • Frits 2:58 pm on 4 October 2020 Permalink | Reply

      A more efficient program (without explaining the choices as this is a new puzzle).

       
      from enigma import factor, irange, concat, diff 
      from itertools import permutations as perm
      from collections import defaultdict
      
      # number of same characters at same positions
      nr_common = lambda x, y: sum(1 for i, a in enumerate(x) if a == y[i])
      
      # prime factors under 10
      factund10 = lambda x: [p for p in {2, 5, 7} if int(x) % p == 0]
      
      # if list contains one entry then return possible values at position i
      charvals = lambda s, i: {x[0][i] for x in s if len(x) == 1}
      
      n = 6
      digits = concat([x for x in irange(1, n)])
      
      # for each digit i occuring twice in lowest and highest number
      for i in irange(1, n):
        if i % 3 == 0: continue
        
        # build lowest and highest number
        low = digits[:i] + str(i) + digits[i:]
        hgh = low[::-1]
       
        # get prime factors under 10 
        u10low = factund10(low)       
        u10hgh = factund10(hgh)       
       
        if len(u10hgh) != 1 or u10hgh[0] != 7: continue
        
        # each number with one prime factor under 10 (different for each number)
        if len(u10low) != 1: continue
        
        rainbow = defaultdict(list)
         
        # for this combination of lowest and highest check the rainbow possibilities
        center = str(i)
        remaining = diff(low[:n//2] + low[n//2 + 1:], "5")
        # try possibilities for first digit  
        for d1 in diff(remaining, "1" + str(n)):
          # find values for positions without the edges and the center
          for pe2 in perm(diff(remaining, d1) , n - 2):
            # build rainbow number
            rb = d1 + concat(pe2[:(n-1)//2]) + center + \
                 concat(pe2[(n-1)//2:]) + "5"
            
            if int(rb) % u10hgh[0] == 0:      
              continue
           
            # check rainbow number on only the central digit being the same
            if nr_common(rb, low) != 1 or nr_common(rb, hgh) != 1: 
              continue
            
            # store rainbow number with as key first 2 digits
            rainbow[rb[:2]].append(rb)
        
        # if first 2 digits rainbow number is unique then list indigo values
        indigo = charvals(rainbow.values(), 5)  
        if len(indigo) == 1:
          print(f"The score on the indigo die: {indigo.pop()}")  
      

      Like

  • Jim Randell 4:35 pm on 7 August 2020 Permalink | Reply
    Tags: by: Stephen Hogg   

    Teaser 3020: Baz’s bizarre arrers 

    From The Sunday Times, 9th August 2020 [link]

    “Bizarrers” dartboards have double and treble rings and twenty sectors ordered as on this normal dartboard [shown above]. However, a sector’s central angle (in degrees) is given by (100 divided by its basic score). The 20 sector incorporates the residual angle to complete 360º.

    Each player starts on 501 and reduces this, eventually to 0 to win. After six three-dart throws, Baz’s seventh could win. His six totals were consecutive numbers. Each three-dart effort lodged a dart in each of three clockwise-adjacent sectors (hitting, in some order, a single zone, a double zone and a treble zone). [Each] three-sector angle sum (in degrees) exceeded that total.

    The sectors scored in are calculable with certainty, but not how many times hit with certainty, except for one sector.

    Which sector?

    This puzzle uses a different spelling for “arraz” from the previous puzzle involving Baz (Teaser 2934).

    [teaser3020]

     
    • Jim Randell 5:21 pm on 7 August 2020 Permalink | Reply

      This Python program runs in 52ms.

      Run: [ @replit ]

      from fractions import Fraction as F
      from collections import defaultdict
      from itertools import product
      from enigma import tuples, subsets, multiset, seq_all_same, intersect, join, printf
       
      # sectors of the dartboard
      board = [ 20, 1, 18, 4, 13, 6, 10, 15, 2, 17, 3, 19, 7, 16, 8, 11, 14, 9, 12, 5 ]
      
      # map scores from 1 to 19 to sector angles (in degrees)
      angle = dict((n, F(100, n)) for n in board if n != 20)
      # the 20 sector completes the board
      angle[20] = 360 - sum(angle.values())
       
      # consider 3 adjacent sectors
      d = defaultdict(list) # store the results by the score (single, double, treble)
      for ss in tuples(board + board[:2], 3):
        # calculate the sector angle sum
        a = sum(angle[s] for s in ss)
        # choose multipliers for the scores
        for ms in subsets(ss, size=len, select="P"):
          # calculate the total
          t = sum(s * m for (m, s) in enumerate(ms, start=1))
          # which is less than the angle sum
          if not (t < a): continue
          d[t].append(ms)
      
      # look for 6 consecutive scores
      for ts in tuples(sorted(d.keys()), 6):
        if not (ts[0] + 5 == ts[-1]): continue
        # produce possible sets of scoring sectors
        mss = list(multiset.from_seq(*ss) for ss in product(*(d[t] for t in ts)))
        # each set of sectors should be the same
        if not seq_all_same(set(m.keys()) for m in mss): continue
        # look for common (sector, count) pairs for all possible scores
        ps = intersect(m.items() for m in mss)
        if len(ps) == 1:
          # output solution
          for (s, n) in ps:
            printf("sector = {s} [count = {n}]")
          printf("  scores = {ts}")
          for t in ts:
            printf("    {t}: {ss}", ss=join(d[t], sep=" "))
      

      Solution: We can say for certain that the 4 sector was hit twice.

      Baz’s 6 scores were (in consecutive order): 58, 59, 60, 61, 62, 63.

      So he has 138 left to score. (Which is achievable in many ways with 3 darts (assuming standard rules of darts apply), for example: treble 20, treble 20, double 9).

      Possible ways to make the first 6 scores with consecutive sectors are:

      58 = (single 3, double 2, treble 17)
      59 = (single 20, double 18, treble 1); (single 10, double 2, treble 15); (single 2, double 3, treble 17)
      60 = (single 4, double 1, treble 18)
      61 = (single 18, double 20, treble 1)
      62 = (single 2, double 15, treble 10)
      63 = (single 1, double 4, treble 18)

      We don’t know which of the alternatives makes up the 59, but whichever is chosen the 4 sector is used twice (in scoring 60 and 63), and the full list of sectors used is: 1, 2, 3, 4, 10, 15, 17, 18, 20.

      There is only one other possible consecutive set of consecutive scores: (41, 42, 43, 44, 45, 46), but this leaves a 240 finish which is not possible with 3 darts (at least not using the standard rules of darts, but maybe there is a way to score at least 80 with one dart on this strange dartboard, or another rule that would allow Baz to win that we don’t know about). But it also turns out that with this set of scores we cannot be certain which sectors were definitely used to make the scores either, so this possibility is excluded without us needing to know the exact rules for the variation of darts being used in the puzzle.

      Like

      • Frits 12:17 pm on 9 August 2020 Permalink | Reply

        It wasn’t easy for me to understand this puzzle. Only after seeing the code it became clear.

        “After six three-dart throws, Baz’s seventh could win”.

        You don’t seem to check that after six three-dart throws Baz has scored at least 331 points.

        With this extra check the 41-46 range can be eliminated earlier (ts[0] ≥ 52).

        Like

        • Jim Randell 12:24 pm on 9 August 2020 Permalink | Reply

          @Frits: There are two possible sets of six consecutive scores, but one is eliminated by the requirement that we can be certain of the sectors that were definitely used to make the scores. It also turns out that it would not be possible to win with three darts from this position (at least on a normal dart board), and it is possible for the other set of six consecutive scores (in many ways, which can easily be seen), so I didn’t incorporate that test into my code, as it seemed to be superfluous (although probably useful in a manual solution).

          Like

          • Frits 5:17 pm on 9 August 2020 Permalink | Reply

            Agree.

            If the six totals had come out as f.i. 54-59 the score after six three-dart throws would have been 339 leaving 162 which is not a finish at darts.

            If the program is intended to find a quick solution which has to be checked manually that’s OK with me.

            Like

            • Jim Randell 8:30 am on 12 August 2020 Permalink | Reply

              Here is a modified version of my program that ensures that Baz can finish on his 7th throw [ @replit ].

              Although as previously noted, this doesn’t change the solutions found.

              The puzzle text only states that the remaining total should be reduced to 0, so that’s what I’ve implemented. No requirement for the final dart to be a double, and as no inner or outer bull is mentioned I have not included them either.

              New Scientist Puzzle #06 explores scores achievable with n darts (on a standard dartboard).

              Like

    • Robert Brown 1:07 am on 10 August 2020 Permalink | Reply

      That total doesn’t work. You need 58-63, which can be made 3 different ways. Total is 363 leaving 138 which can be finished with any 3 darts that sum to 46, all of which are trebles. It’s quite quick to manually check the 3 different sequences: there’s one sector that appears the same number of times in each sequence, which is the required answer.

      Like

      • Jim Randell 8:55 am on 10 August 2020 Permalink | Reply

        @Robert: I’m not sure what total you are objecting to. Also I understood that in standard rules of darts you have to finish on a double. (Although in the version of the game used in the puzzle we are not told what the rules for finishing are. Fortunately though, of the two possible consecutive sequences of scores one of them is ruled out for reasons that are explained in the puzzle, so we don’t need to know the rules for finishing. We are just told that Baz could finish on his next throw, which is nice for him, but inconsequential for us).

        Like

    • Robert Brown 8:22 pm on 10 August 2020 Permalink | Reply

      I don’t know the rules of darts! The total that I found (58,59,60,61,62,63) needs 138 to finish, so I assumed finishing on trebles was ok. But they tell me that a bull’s eye counts as 50, so you can finish with 2 bull’s eyes & a double 19.
      I was objecting to Frits’s 6 totals (54-59) which I don’t see as a possibility. The important thing about my sequence is that there are 3 way to make 59, which changes the number of times that each sector is called, except for one which is the answer.

      Like

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

        @Robert: Right. I believe Frits only gave those numbers as a hypothetical example to illustrate his point.

        You have found the right set of scores that leads to the answer. And fortunately (as I said above) you don’t need to know the rules of darts to eliminate the only other possible consecutive sequence of scores.

        Like

    • GeoffR 8:40 am on 12 August 2020 Permalink | Reply

      I had the idea of defining a valid function for three adjacent sectors – i.e.valid if the six totals were less than the sum of the three angles. This enabled the code below to find the unique six consecutive totals, but not the single requested sector.

      
      from itertools import permutations
      from collections import defaultdict
      D = defaultdict(set)
      
      L, L2 = [], []
      
      # function to check if a three-sector is valid
      # a, b, c are adjacent sector numbers
      def is_valid(a, b, c):
        asum = sum(100 / x for x in (a, b, c))
        ps = []
        for p3 in permutations((a, b, c)):
          score = sum(m * x for m, x in zip((1, 2, 3), p3))
          if score < asum:
            ps.append(score)
        return ps
      
      # the scores starting at north and running clockwise
      db = (20, 1, 18, 4, 13, 6, 10, 15,  2, 17,
            3, 19, 7, 16, 8, 11, 14, 9, 12, 5)
      
      for p in range(20):
        p3 = tuple((p + i) % 20 for i in (0, 1, 2))
        sc = tuple(db[i] for i in p3)
        L.append(sc)
      
      for x in range(20):
        a, b, c = L[x]
        s6 = is_valid(a, b, c)
        if s6:
          L2.append(s6)
      
      for p in permutations(L2,6):
        L1, L2, L3, L4, L5, L6 = p
        
        L22 = sorted(L1 + L2 + L3 + L4 + L5 + L6)
        L22 = sorted(list(set(L22)))
        
        for b in range(0, len(L22)-6):
          b1  = L22[b:b+6]
          # split slice into six totals
          a0, b0, c0, d0, e0, f0 = b1
          # total of six scores
          s = a0 + b0 + c0 + d0 + e0 + f0
          # total must be less than 180 to close with the 7th set of 3 darts
          # else there is another set of 6 consecutive numbers in the forties
          if 501 - s > 180:
            continue
          # check six numbers are consecutive
          if b0-a0 == c0-b0 == d0-c0 == e0-d0 == f0-e0 == 1:
            D[s].add ((a0,b0,c0,d0,e0,f0))
      
      for k,v in D.items():
        print(f"Sum of six 3 dart totals = {k}")
        print(f"Unique six totals are {v}")
        sc_left = 501 - k
        print(f"Seventh group of three darts score = {sc_left}")
        print(f"7th 3 darts group could be 3*18 + 3*20 + 2*12 = 138")
        print(f"Finishing on a double!")
      
      # Sum of six 3 dart totals = 363
      # Unique six totals are {(58, 59, 60, 61, 62, 63)}
      # Seventh group of three darts score = 138
      # 7th 3 darts group could be 3*18 + 3*20 + 2*12 = 138
      # Finishing on a double!
      
      
      

      I looked at a print out of Jim’s dictionary which gives the same six consecutive totals and the triples used in each of the numbers 58,59,60,61, 62 and 63.

      scores = (58, 59, 60, 61, 62, 63)
      58: (3, 2, 17)
      59: (20, 18, 1) (10, 2, 15) (2, 3, 17)
      60: (4, 1, 18)
      61: (18, 20, 1)
      62: (2, 15, 10)
      63: (1, 4, 18)

      The number 59 has three triples and all these digits appear in the numbers 58,60,61,62 and 63. The total of 363 can therefore be made up three ways. All three ways require the numbers 60 and 63, which also contain the digit ‘4’, so we can say thet the digit ‘4’ definitely occurs twice.

      A minor variation to my programme found the only eight valid sectors were:
      (20, 1, 18), (1, 18, 4), (4, 13, 6), (10, 15, 2),
      (15, 2, 17), (2, 17, 3), (3, 19, 7), (5, 20, 1)

      Jim’s dictionary above show that only four of these eight triples were needed for the final solution;
      i.e (2,3,17), (20,18,1), (10,2,15), (4,1,18)

      Like

  • Jim Randell 4:30 pm on 17 July 2020 Permalink | Reply
    Tags: by: Stephen Hogg   

    Teaser 3017: Mr. Green’s scalene mean machine 

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

    My maths teacher, Mr. Green, stated that the average of the squares of any two different odd numbers gives the hypotenuse of a right-angled triangle that can have whole-number unequal sides, and he told us how to work out those sides.

    I used my two sisters’ ages (different odd prime numbers) to work out such a triangle, then did the same with my two brothers’ ages (also different odd prime numbers). Curiously, both triangles had the same three-figure palindromic hypotenuse. However, just one of the triangles was very nearly a 45° right-angled triangle (having a relative difference between the adjacent side lengths of less than 2%).

    In ascending order, what were my siblings’ ages?

    [teaser3017]

     
    • Jim Randell 5:34 pm on 17 July 2020 Permalink | Reply

      We don’t need to work out how to calculate the non-hypotenuse sides of the triangle (although I have worked out a rule which works).

      This Python program groups together Pythagorean triples by the hypotenuse, then looks for groups that have a palindromic hypotenuse, and more than one corresponding triangle. It then works out pairs of odd squares that average to the hypotenuse, and looks for two of these pairs where each number in the pair is prime. Then we need to look for a corresponding triangle where the non-hypotenuse sides are almost equal. And that gives us our solution.

      This Python program runs in 55ms.

      Run: [ @repl.it ]

      from enigma import pythagorean_triples, is_palindrome, nsplit, group, unpack, isqrt, compare, subsets, flatten, is_prime, printf
      
      # generate decompositions of n into the sum of two squares
      def sum_of_squares(n):
        (i, j) = (isqrt(n), 0)
        while not(i < j):
          r = compare(i * i + j * j, n)
          if r == 0: yield (j, i)
          if r != -1: i -= 1
          if r != 1: j += 1
      
      # collect pythagorean triples grouped by hypotenuse
      tris = group(
        pythagorean_triples(999),
        st=unpack(lambda x, y, z: z > 99 and is_palindrome(nsplit(z))),
        by=unpack(lambda x, y, z: z)
      )
      
      # look for multiple triangles that share a palindromic hypotenuse
      for (z, xyzs) in tris.items():
        if not(len(xyzs) > 1): continue
        # and look for multiple pairs of squares that average to the hypotenuse
        avgs = list((x, y) for (x, y) in sum_of_squares(2 * z) if x < y)
        if not(len(avgs) > 1): continue
        printf("[{z} -> {xyzs} -> {avgs}]")
        # look for triangles with x, y within 2% of each other
        t45ish = list((x, y, z) for (x, y, z) in xyzs if 100 * y < 102 * x)
        if not(0 < len(t45ish) < len(xyzs)): continue
        # collect two of the pairs for the ages
        for ages in subsets(avgs, size=2):
          ages = sorted(flatten(ages))
          # and check they are odd primes
          if not all(x % 2 == 1 and is_prime(x) for x in ages): continue
          # output solution
          printf("z={z} -> t45ish = {t45ish} -> ages = {ages}")
      

      Solution: The ages are: 13, 17, 29, 31.

      Removing the test for the ages being odd and prime does not give any additional solutions.

      If the two odd numbers are a and b (where a < b), then the following is a Pythagorean triple:

      x = (b² − a²) / 2
      y = ab
      z = (a² + b²) / 2

      where z is the hypotenuse. (All we actually require is that a and b have the same parity).

      Applying this rule to the two pairs (13, 31) and (17, 29) we get the following triangles:

      (13, 31) → sides = (396, 403, 565); angles = (44.5°, 45.5°, 90.0°)
      (17, 29) → sides = (276, 493, 565); angles = (29.2°, 60.8°, 90.0°)

      The first of these triangles is close to being a (45°, 45°, 90°) triangle, and the other one is quite close to being a (30°, 60°, 90°) triangle – the standard shapes for set squares.

      Like

    • GeoffR 8:15 am on 21 July 2020 Permalink | Reply

      
      % A Solution in MiniZinc 
      include "globals.mzn";
      
      predicate is_prime(var int: x) = 
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
      ((i < x) -> (x mod i > 0));
      
      % Siblings ages in teaser
      var 2..97:S1; var 2..97:S2; var 2..97:B1; var 2..97:B2;
      constraint all_different ([S1, S2, B1, B2]);
      
      constraint S1 < S2 /\ B1 < B2;
      
      constraint is_prime(S1) /\ is_prime(S2)
      /\ is_prime(B1) /\ is_prime(B2);
      
      % Palindromic hypotenuse
      var 100..999: HYP;
      
      constraint HYP div 100 == HYP mod 10 
      /\ HYP div 10 mod 10 != HYP mod 10;
      
      % Two other sides with a palindromic hypotenuse
      var 100..999: side1; var 100..999: side2;
      
      constraint side1 > side2
      /\ all_different([HYP, side1, side2]);
      
      % Mr Green's triangle formula
      constraint B1*B1 + B2*B2 = 2 * HYP
      /\ S1*S1 + S2*S2 = 2 * HYP;
      
      % The triangle sides are less than 2% different in size
      constraint side1 * side1 + side2 * side2 == HYP * HYP
      /\ 100 * (side1 - side2) < 2 * side1;
      
      solve satisfy;
      
      output [ "Sisters' ages are " ++ show(S1) ++ ", " ++ show(S2)]
      ++ [ "\nBrothers' ages are " ++ show(B1) ++ ", " ++ show(B2)]
      ++ [ "\nTriangle solution sides are " ++ show(HYP) ++ ", " ++ show(side1)]
      ++ [", " ++ show(side2) ];
      
      % Ascending siblings ages are 13,17,29,31
      
      % Sisters' ages are 17, 29
      % Brothers' ages are 13, 31
      % Triangle solution sides are 565, 403, 396
      % time elapsed: 0.05 s
      % ----------
      % Sisters' ages are 13, 31
      % Brothers' ages are 17, 29
      % Triangle solution sides are 565, 403, 396
      % time elapsed: 0.05 s
      % ----------
      % ==========
      
      

      I found the prime age constraint of the siblings was not essential for this solution.

      Like

  • Jim Randell 4:48 pm on 12 June 2020 Permalink | Reply
    Tags: by: Stephen Hogg   

    Teaser 3012: Number blind rage 

    From The Sunday Times, 14th June 2020 [link]

    After school, angry at getting “50 lines”, I kicked my satchel around. Impacts made my 11-digit calculator switch on. An 11-digit number was also entered and the display was damaged. Strangely, I found “dYSCALCULIA” displayed and saved this to memory (as shown).

    After various tests I confirmed that all arithmetic operations were correct and the decimal point would appear correctly if needed. No segments were permanently “on”, two digits were undamaged, and for the other digits, overall, several segments were permanently “off”.

    Retrieving “dYSCALCULIA”, I divided it by 9, then the result by 8, then that result by 7, then that result by 6. No decimal point appeared and the last result (at the right-hand side of the display) had three digits appearing as numerals.

    What number was “dYSCALCULIA”?

    [teaser3012]

     
    • Jim Randell 9:07 pm on 12 June 2020 Permalink | Reply

      I used the standard set of digits (as illustrated in Enigma 1701).

      This Python program runs in 90ms.

      from itertools import product
      from enigma import join, div, printf
      
      # normal digits
      normal = "0123456789"
      
      # map digits to illuminated segments, arranged as:
      #
      #   0
      # 1   2
      #   3
      # 4   5
      #   6
      #
      # map digits to segments
      f = lambda *ss: frozenset(ss)
      seg = {
        # normal digits
        '0': f(0, 1, 2, 4, 5, 6),
        '1': f(2, 5),
        '2': f(0, 2, 3, 4, 6),
        '3': f(0, 2, 3, 5, 6),
        '4': f(1, 2, 3, 5),
        '5': f(0, 1, 3, 5, 6),
        '6': f(0, 1, 3, 4, 5, 6), # or could be (1, 3, 4, 5, 6)
        '7': f(0, 2, 5), # or could be (0, 1, 2, 5)
        '8': f(0, 1, 2, 3, 4, 5, 6),
        '9': f(0, 1, 2, 3, 5, 6), # or could be (0, 1, 2, 3, 5)
        # malformed digits
        'a': f(0, 1, 2, 3, 4, 5),
        'c': f(0, 1, 4, 6),
        'd': f(2, 3, 4, 5, 6),
        'l': f(1, 4, 6),
        'u': f(1, 2, 4, 5, 6),
      }
      # map segments to normal digits
      norm = dict((seg[k], k) for k in normal)
      
      # the display
      display = "d45calcul1a"
      
      # compute possible replacement (superset) digits for the symbols
      r = dict((k, list(d for d in normal if seg[d].issuperset(seg[k]))) for k in set(display))
      
      # choose possible replacement digits for the symbols
      for ds in product(*(r[x] for x in display)):
        if ds[0] == '0': continue
        # two of the digits are unaffected
        if sum(x == y and x in normal for (x, y) in zip(display, ds)) < 2: continue
        # make the number
        n = int(join(ds))
        # and the result
        s = div(n, 9 * 8 * 7 * 6)
        if s is None: continue
        # remove broken segments from the result
        # x = original display, y = original digit, z = result digit
        rs = list(
          norm.get(seg[z].difference(seg[y].difference(seg[x])), '?')
            for (x, y, z) in zip(display[::-1], ds[::-1], str(s)[::-1])
        )
        # there should be 3 normal digits
        if len(rs) - rs.count('?') != 3: continue
        # output solution
        printf("{n} -> {s} -> {rs}", rs=join(rs[::-1]))
      

      Solution: dYSCALCULIA = 84588800688.

      The digits displaying 4 and 5 must be the undamaged ones.

      So the segments that are definitely broken are as shown below:

      There are 22 segments that are definitely broken, and a further 3 that we cannot determine if they are broken or not.

      The result of dividing the number by 9×8×7×6 = 3024 is 27972487, which would look something like this:

      (Only showing the segments that we definitely know to be broken, there are two segments shown lit that may be broken).

      The 2nd digit (7) displays as a 7. The 7th digit (8) displays as a 1. The 8th digit (7) displays as a 7.

      Like

  • Jim Randell 5:13 pm on 15 May 2020 Permalink | Reply
    Tags: by: Stephen Hogg   

    Teaser 3008: Three-fruit fractions 

    From The Sunday Times, 17th May 2020 [link]

    The owner of the old curiosity shop repaired an antique mechanical fruit machine having three wheels of identical size and format. Afterwards each wheel was independently fair, just as when new. Each wheel’s rim had several equal-sized zones, each making a two-figure whole number of degrees angle around the rim. Each wheel had just one zone showing a cherry, with other fruits displayed having each a different single-figure number (other than one) of zone repetitions.

    Inside the machine were printed all the fair chances (as fractions) of getting three of the same fruit symbol in one go. Each of these fractions had a top number equal to 1 and, of their bottom numbers, more than one was odd.

    What was the bottom number of the chance for three cherries?

    [teaser3008]

     
    • Jim Randell 7:26 am on 16 May 2020 Permalink | Reply

      I assumed the wheels are identical duplicates of each other, which gives a unique solution.

      This Python 3 program runs in 49ms.

      Run: [ @repl.it ]

      from enigma import Rational, divisors, div, irange, join, printf
      
      F = Rational()
      
      # decompose t into numbers between 2 and 9
      def decompose(t, m=2, M=9, s=[]):
        if not(t < m or t > M):
          yield s + [t]
        for x in irange(m, min(t - m, M)):
          yield from decompose(t - x, x + 1, M, s + [x])
      
      # each wheel is divided into n equal sized divisions
      # each spanning d degrees
      for n in divisors(360):
        d = div(360, n)
        if d < 10: break
        if d > 99: continue
      
        # probability of 3 cherries
        p = F(1, n) ** 3
      
        # consider the number of other fruits (all different and between 2 and 9)
        for ns in decompose(n - 1):
          # calculate the probabilities of getting 3 of each of the other fruits
          ps = list(F(x, n) ** 3 for x in ns)
          # probabilities are all 1/N
          if not all(x.numerator == 1 for x in ps): continue
          # and more than one N is odd
          if sum(x.denominator % 2 == 1 for x in ps) < 2: continue
      
          # output solution
          printf("{n} divisions, {d} degrees -> 1 + {ns}; p={p}, ps=[{ps}]", ps=join(ps, sep=", "))
      

      Solution: There is a 1 / 5832 chance of getting 3 cherries.

      Each wheel is divided into 18 sectors. Each sector subtends 20°.

      There are 4 fruits, each is allocated 1, 2, 6, 9 sectors on each wheel.

      The probabilities for each of the 4 fruits are: 1/5832 (= 1/18³), 1/729 (= 1/9³), 1/27 (= 1/3³), 1/8 (= 1/2³).

      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
%d bloggers like this: