Design a site like this with WordPress.com
Get started

Tagged: by: Colin Vout Toggle Comment Threads | Keyboard Shortcuts

  • Jim Randell 4:17 pm on 9 December 2022 Permalink | Reply
    Tags: by: Colin Vout   

    Teaser 3142: Mrs Hyde’s garden design tips 

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

    I’m planting four differently-coloured plots in a line. Mrs Hyde’s design principles classify eight colours into five categories. Adjacent plots mustn’t have the same category, or even certain pairs of categories.

    “Every scheme you’ve suggested has at least one adjacent pair of categories that breaks my rules”, said Mrs Hyde. “White, Green, Yellow, White has Honest and Social adjacent; Blue, Orange, Pink, Violet has Ardent and Social adjacent; Green, Violet, Blue, Orange has Ardent and Honest adjacent; Violet, White, Orange, Red has Droll and Honest adjacent; and White, Violet, Green, Blue has Jolly and Social adjacent. However, if you change one colour in one of your suggestions then it will work”.

    What are the four colours in order in the changed suggestion that would be allowable?

    [teaser3142]

     
    • Jim Randell 4:55 pm on 9 December 2022 Permalink | Reply

      Here is my first attempt. It is not particularly quick, but I’ll have another look at this puzzle later.

      The program maps the different colours to the categories and checks that each of the given arrangements provides (at least) the corresponding objection. One we have a viable map we change one of the colours in one of the given arrangements and look for new arrangements that do not give rise to any of the objections raised previously.

      This Python program runs in 866ms.

      Run: [ @replit ]

      from enigma import (subsets, diff, tuples, update, wrap, uniq, map2str, printf)
      
      # colours and categories
      cols = "BGOPRVWY"
      cats = "ADHJS"
      
      # invalid arrangements and objections
      inv = {
        'WGYW': 'HS',
        'BOPV': 'AS',
        'GVBO': 'AH',
        'VWOR': 'DH',
        'WVGB': 'JS',
      }
      
      # banned adjacencies
      banned = set(frozenset([x]) for x in cats)
      banned.update(map(frozenset, inv.values()))
      
      # check each of the arrangements provides the required objection
      def check(m):
        # check each of the arrangements
        for (k, v) in inv.items():
          adj = set(v)
          if not any({m[x], m[y]} == adj for (x, y) in tuples(k, 2)): return False
        # looks OK
        return True
      
      @wrap(uniq)
      # change one of the arrangements
      def change(ks):
        for k in ks:
          for (i, x) in enumerate(k):
            # make a changed arrangement
            for y in cols:
              if y != x:
                yield update(k, [(i, y)])
      
      # map colours to categories
      for ss in subsets(cats, size=len(cols), select="M"):
        m = dict(zip(cols, ss))
        # each category must be represented
        if not set(m.values()).issuperset(cats): continue
        # check the given arrangements are objectionable
        if not check(m): continue
      
        # find a changed arrangement that is not objectionable
        for s in change(inv.keys()):
          # look for banned adjacencies in the new arrangement
          if not any(frozenset([m[x], m[y]]) in banned for (x, y) in tuples(s, 2)):
            # output solution
            printf("{s} [{m}]", m=map2str(m, sep=" ", enc=""))
      

      Solution: The allowable arrangement is: White, Red, Green, Blue.

      The colour assignments are:

      Blue → Ardent
      Green → Jolly
      Orange → Honest
      Pink → Ardent
      Red → Droll
      Violet → Social
      White → Social
      Yellow → Honest

      And so the given arrangements (and their objections) are:

      White (S); Green (J); Yellow (H); White (S) → S and J adjacent; H and S adjacent
      Blue (A); Orange (H); Pink (A); Violet (S) → A and H adjacent (twice); A and S adjacent
      Green (J); Violet (S); Blue (A); Orange (H) → A and S adjacent; A and H adjacent
      Violet (S); White (S); Orange (H); Red (D) → S and S adjacent; S and H adjacent; D and H adjacent
      White (S); Violet (S); Green (J); Blue (A) → S and S adjacent; J and S adjacent;

      However, swapping Violet for Red in the final arrangement gives:

      White (S); Red (D); Green (J); Blue (A)

      Which does not give any of the objections we have discovered so far.

      Like

      • Jim Randell 6:25 pm on 9 December 2022 Permalink | Reply

        Here is a much faster version of my program (and not much longer). It uses the [[ SubstitutedExpression() ]] solver from the enigma.py library to assign the colours to the categories, such that the objections for each arrangement applies.

        It runs in 57ms. (Internal runtime is 5.6ms).

        Run: [ @replit ]

        from enigma import (SubstitutedExpression, wrap, uniq, update, tuples, map2str, printf)
        
        # colours and categories
        cols = "BGOPRVWY"
        cats = "ADHJS"
        
        # invalid arrangements and objections
        inv = {
          'WGYW': 'HS',
          'BOPV': 'AS',
          'GVBO': 'AH',
          'VWOR': 'DH',
          'WVGB': 'JS',
        }
        
        # map categories to digits 1-5
        d = dict(A=1, D=2, H=3, J=4, S=5)
        
        # construct an alphametic puzzle to assign categories to the colours
        p = SubstitutedExpression(
          [
            # WGYW has H and S adjacent
            "{3, 5} in [{W, G}, {G, Y}, {Y, W}]",
            # BOPV has A and S adjacent
            "{1, 5} in [{B, O}, {O, P}, {P, V}]",
            # GVBO has A and H adjacent
            "{1, 3} in [{G, V}, {V, B}, {B, O}]",
            # VWOR has D and H adjacent
            "{2, 3} in [{V, W}, {W, O}, {O, R}]",
            # WVGB has J and S adjacent
            "{4, 5} in [{W, V}, {V, G}, {G, B}]",
          ],
          digits=(1, 2, 3, 4, 5),
          distinct=(),
        )
        
        # set of banned adjacencies
        banned = set(frozenset([d[x]]) for x in cats)
        banned.update(frozenset([d[x], d[y]]) for (x, y) in inv.values())
        
        @wrap(uniq)
        # change one of the arrangements
        def change(ks):
          for k in ks:
            for (i, x) in enumerate(k):
              # make a changed arrangement
              for y in cols:
                if y != x:
                  yield update(k, [(i, y)])
        
        # solve the alphametic puzzle to map colours to categories
        for m in p.solve(verbose=0):
          # find a changed arrangement that is not objectionable
          for s in change(inv.keys()):
            # look for banned adjacencies in the new arrangement
            if not any(frozenset([m[x], m[y]]) in banned for (x, y) in tuples(s, 2)):
              # output solution
              printf("{s} [{m}]", m=map2str(m, sep=" ", enc=""))
        

        Like

  • Jim Randell 4:27 pm on 21 October 2022 Permalink | Reply
    Tags: by: Colin Vout   

    Teaser 3135: Rhythmic gymnastics 

    From The Sunday Times, 23rd October 2022 [link] [link]

    Skaredahora used three rhythmic patterns of quaver beats in a short, purely percussive, composition. His “Dotykam” rhythm has accents on beats 1, 4, 6, 7, 8, 10 & 11; “Kluc” has accents on beats 1, 8 and one particular beat in between; and “Omacka” has accents on beats 1, 2, 5, 6 & 10. Several percussion instruments are involved, each playing one of the three rhythms, but starting at different times. Overall the patterns overlap, with every beat in the composition being filled by an accent from exactly one of the instruments, and all the patterns finishing by the end of the composition.

    What is the other beat of Kluc, and what is the order of appearance of the rhythmic patterns (e.g. DOOKD)?

    [teaser3135]

     
    • Jim Randell 4:51 pm on 21 October 2022 Permalink | Reply

      This Python program considers possible additional accent positions for pattern K, and then fills out patterns with an accent on every beat, but no overlaps, until there is a continuous sequence of accents.

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

      Run: [ @replit ]

      from enigma import (irange, inf, update, peek, printf)
      
      # the rhythm patterns
      D = [1, 4, 6, 7, 8, 10, 11]
      K = [1, None, 8]  # a beat in the range [2, 7] is missing
      O = [1, 2, 5, 6, 10]
      
      # disjoint union of two sets (or None)
      def disjoint_union(ss, xs):
        ss = set(ss)
        for x in xs:
          if x in ss: return
          ss.add(x)
        return ss
      
      # fill out patterns from <ps> with an accent on every beat
      # starting from <s>
      def solve(ps, s=1, vs=[], bs=set()):
        # we are done if there are no missing beats
        if bs and len(bs) == max(bs):
          yield vs
        else:
          # find the first missing beat
          b = peek(k for k in irange(s, inf) if k not in bs)
          # and choose a pattern to start here
          for (k, pattern) in ps.items():
            bs_ = disjoint_union(bs, (x + b - 1 for x in pattern))
            if bs_ is not None:
              yield from solve(ps, s + 1, vs + [(k, b)], bs_)
      
      # consider the missing beat in pattern K
      for k in irange(2, 7):
        for vs in solve(dict(D=D, K=update(K, [1], [k]), O=O)):
          printf("k={k} vs={vs}")
      

      Solution: Kluc has an additional accent on beat 5. The order of the patterns as: OOKKDDK.

      The composition lasts for 33 beats (or a multiple of 33 beats). The patterns being:

      O @ 1: (1, 2, 5, 6, 10)
      O @ 3: (3, 4, 7, 8, 12)
      K @ 9: (9, 13, 16)
      K @ 11: (11, 15, 18)
      D @ 14: (14, 17, 19, 20, 21, 23, 24)
      D @ 22: (22, 25, 27, 28, 29, 31, 32)
      K @ 26: (26, 30, 33)

      Which covers all beats from 1 – 33.

      In order for the composition to end after 33 beats with each beat being accented by exactly one of the instruments, we need pattern K to end after the last accented beat. Pattern D can have 0 or 1 non-accented beats after the last accented beat. And pattern O could have up to 21 non-accented beats after the last accented beat.

      Like

    • NigelR 10:47 am on 25 October 2022 Permalink | Reply

      Less elegant than Jim’s solution, but gets the job done!

      rhy = [[1, 4, 6, 7, 8, 10, 11],[1, 2, 8],[1, 2, 5, 6,10]] 
      patts=('DO','KL','OM')
      ntotxt = lambda k : [[patts[j[0]],j[1]] for j in k]  #makes print out more intelligible using labels
      score = lambda k : sorted([y+x[1]-1 for x in k for y in rhy[x[0]]]) # creates list of beat numbers filled
      gap = lambda k : sorted([x for x in range(1,len(k)+1) if x not in k]) # identifies gaps in beat sequence
      for n in range(2,8): # iterate for missing value in KL
          rhy[1][1] = n
          seq=[[0,1]] #Initialise seq.  Entries in seq are in format:[pattern no.,starting beat]
          while seq:
              beats=score(seq)
              if dup:=len(beats)-len(set(beats)): #if overlap of beats found, go back in sequence
                  while seq and seq[-1][0]==2:
                      seq.pop()                
                  if not seq:break
                  seq[-1][0]+=1   #try next pattern in exisiting sequence
              else: #no overlaps in current sequence
                  if g:=gap(beats):  # start next pattern at first gap in sequence
                      seq.append([0,g[0]])                
                  else: # if no gap and no overlaps, solution has been found
                      print('solution found: ',ntotxt(seq), '   n=',n)
                      exit()                         
          print('options exhausted for n='         ,n)
      

      Like

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

    Teaser 3124: Lawn order 

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

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

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

    [teaser3124]

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

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

      The following program runs in 399ms.

      Run: [ @replit ]

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

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


      The planned layout looks like this:

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

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

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

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

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

      Liked by 2 people

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

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

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

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

        We then proceed as described above.

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

        Run: [ @replit ]

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

        Like

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

          @Jim,

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

          Test:

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

          Do set parameters always have a global scope?

          Like

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

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

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

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

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

            Like

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

              Thanks.

              Like

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

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

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

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

              This is very similar to just using a global variable:

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

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

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

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

              Like

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

          @Jim,

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

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

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

          Like

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

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

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

            Like

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

              Now you process the expected 80 circuits.

              Like

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

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

      Uncomment the four plot related lines for displaying the polygon.

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

      Liked by 1 person

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

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

        Like

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

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

          Like

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

      Code to print polygons with 90 degree angles.

      (I have problems installing matplotlib under PyPy)

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

      Like

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

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

        I have uploaded it to GitHub. [@github]

        Like

  • Jim Randell 5:00 pm on 17 June 2022 Permalink | Reply
    Tags: by: Colin Vout   

    Teaser 3117: Stop me if you’ve heard this one 

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

    A square, a triangle and a circle went into a bar.

    The barman said: “Are you numbers over 18?”

    They replied: “Yes, but we’re under a million”

    The square boasted: “I’m interesting, because I’m the square of a certain integer”

    The triangle said: “I’m more interesting — I’m a triangular number, the sum of all the integers up to that same integer”

    The circle said: “I’m most interesting — I’m the sum of you other two”

    “Well, are you actually a circular number?”

    “Certainly, in base 1501, because there my square ends in my number exactly. Now, shall we get the drinks in?”

    The square considered a while, and said: “All right, then. You(‘)r(e) round!”

    In base 10, what is the circular number?

    [teaser3117]

     
    • Jim Randell 5:27 pm on 17 June 2022 Permalink | Reply

      Circular numbers are also called automorphic numbers [@wikipedia], and we have encountered them before. See: Enigma 49, Enigma 1736.

      There is a unique value for the “certain integer” (and so S, T, C).

      This Python program runs in 59ms. (Internal runtime is 4.5ms).

      Run: [ @replit ]

      from enigma import (irange, inf, sq, tri, nsplit, zip_eq, join, printf)
      
      # consider possible "certain" integers
      for n in irange(6, inf):
        S = sq(n)
        T = tri(n)
        C = S + T
        if not (C < 1000000): break
        # consider the digits of C and C^2 in base 1501
        Cds = nsplit(C, base=1501)
        C2ds = nsplit(sq(C), base=1501)
        # does C^2 end with C?
        if zip_eq(Cds, C2ds, reverse=1):
          # output solution
          fmt = lambda ds: join(ds, sep=":", enc="{}")
          printf("n={n}: S={S} T={T} C={C} [C={Cds} C^2={C2ds}]", Cds=fmt(Cds), C2ds=fmt(C2ds))
      

      Solution: The circular number is 1027.

      Numbers up to 999,999 can be represented in base 1501 using 1- or 2- digits.

      And there are six 1- or 2- digit automorphic numbers in base 1501, which give potential values for C:

      0
      1
      475
      1027
      368220
      1884782

      The first two are too small. The last one is too big.

      Of the remaining three only 1027 gives a viable value for n, which is n = 26.

      i.e.

      S = sq(26) = 676
      T = tri(26) = 351
      C = 676 + 351 = 1027

      And in base 1501 we have:

      1027 = {1027}
      1027² = {702:1027}

      So (in base 1501) the final digit of C² is C.


      In fact, even if S and T are square and triangular numbers of (possibly) different integers, we can still work out a unique value for C.

      Like

      • Jim Randell 8:26 pm on 17 June 2022 Permalink | Reply

        Here is a faster version that doesn’t construct the base 1501 representations.

        It has an internal run time of 852µs.

        Run: [ @replit ]

        from enigma import (irange, inf, sq, tri, printf)
        
        # consider possible "certain" integers
        M = B = 1501
        for n in irange(6, inf):
          S = sq(n)
          T = tri(n)
          C = S + T
          if not (C < 1000000): break
          # consider the digits of C and C^2 in base 1501
          while not (C < M): M *= B
          if pow(C, 2, M) == C:
            # output solution
            printf("n={n}: S={S} T={T} C={C}")
        

        Liked by 1 person

        • Jim Randell 4:11 pm on 30 June 2022 Permalink | Reply

          I read up on how to find modular roots of integer-valued polynomials using Hensel lifting and the Chinese Remainder Theorem, and then wrote some code to implement it.

          Given the “certain integer” n, the following Python code constructs a polynomial function for f(n) = sq(C(n)) − C(n), and then finds the roots of this function modulo 1501^k (for k = 1, 2). We then check these roots give viable values of S, T, C.

          The internal runtime is 564µs, so it is faster than my simple approach above, but quite a lot more complicated.

          Run: [ @replit ]

          from enigma import (irange, prime_factor, gcd, lcm, egcd, cproduct, sq, tri, ndigits, arg, printf)
          
          # simplified CRT
          # solve: x = a (mod m); x = b (mod n)
          def crt1(a, b, m, n):
            g = gcd(m, n)
            if (a - b) % g != 0: return None
            (x, y, z) = (m // g, n // g, (m * n) // g)
            (u, v, _) = egcd(x, y)
            return (b * u * x + a * v * y) % z
          
          # general Chinese Remainder Theorem
          # solve: x = rs[i] (mod ms[i])
          def crt(rs, ms):
            assert len(rs) == len(ms) # or use zip(..., strict=1)
            x = mm = None
            for (r, m) in zip(rs, ms):
              if x is None:
                (x, mm) = (r, m)
              else:
                x = crt1(r, x, m, mm)
                if x is None: return None
                mm = lcm(m, mm)
            return x
          
          # find modular roots of a polynomial
          class PolyRootsMod(object):
          
            def __init__(self, f, cache=1):
              self.f = f
              self.cache = (dict() if cache else None)
          
            # find roots of <f> mod (<b>^<k>) using Hensel's lemma
            def hensel(self, b, k):
              if k == 0: return [0]
              assert k > 0
              bk = b ** k
              # check the cache
              cache = self.cache
              if cache:
                rs = cache.get(bk)
                if rs is not None:
                  return rs
              # find the roots
              f = self.f
              k_ = k - 1
              bk_ = b ** k_
              rs = list()
              for r in self.hensel(b, k_):
                for i in irange(b):
                  x = i * bk_ + r
                  if f(x) % bk == 0:
                    rs.append(x)
              # cache if necessary
              if cache is not None: cache[bk] = rs
              return rs
          
            # find roots of polynomial <p> mod <n>^<k>
            def roots_mod(self, n, k=1):
          
              # find roots for each prime factor of <n>^<k>
              (rs, bs) = (list(), list())
              for (f, e) in prime_factor(n):
                rs.append(self.hensel(f, e * k))
                bs.append(pow(f, e * k))
          
              # combine roots using CRT
              for xs in cproduct(rs):
                yield crt(xs, bs)
          
          
          B = arg(1501, 0, int)
          printf("[B={B}]")
          
          # start with polynomial functions: sq, tri, circ
          circ = lambda n: sq(n) + tri(n)
          
          # find k-digit automorphic values for C in base B
          f = lambda x: x * x - x
          poly = PolyRootsMod(lambda n: f(circ(n)))
          for k in irange(1, ndigits(999999, base=B)):
            for n in poly.roots_mod(B, k):
              S = sq(n)
              T = tri(n)
              C = circ(n)
              if S < 18 or T < 18 or not (C < 1000000): continue
              if ndigits(C, base=B) != k: continue
              printf("S={S} T={T} C={C} [n={n}]")
          

          Like

      • Jim Randell 9:50 am on 18 June 2022 Permalink | Reply

        Here is a version adapted from my code for Enigma 49. It proceeds by constructing possible automorphic values for C and then calculating the corresponding “certain integer” n, and from that S and T. Although this is not as fast as my previous program.

        from enigma import (irange, ndigits, uniq, quadratic, sq, tri, printf)
        
        # generate <k> digit automorphic numbers (in base <b>)
        # i.e. x where the rightmost k digits of x^n are the digits of x
        # yield (<k>, <x>) where <k> in <ks>
        def automorphic(ks, b=10, n=2):
          K = max(ks)
          (k, xs, p, q) = (1, [0], 1, b)
          while not (k > K):
            f = (k in ks)
            xs_ = list()
            for d in irange(b):
              for x in xs:
                x_ = d * p + x
                if pow(x_, n, q) == x_:
                  if f: yield (k, x_)
                  xs_.append(x_)
            (k, xs, p, q) = (k + 1, xs_, q, q * b)
        
        # consider 1-, 2- digit automorphic numbers in base 1501
        d = ndigits(999999, base=1501)
        for C in uniq(x for (k, x) in automorphic(irange(1, d), 1501)):
          if C < 18 or not (C < 1000000): continue
          # calculate n: C = n(3n + 1)/2
          for n in quadratic(3, 1, -2 * C, domain="Z"):
            if n < 6: continue
            S = sq(n)
            T = tri(n)
            printf("C={C} S={S} T={T} [n={n}]")
        

        And here is a version which proceeds by constructing possible values for C using the technique given on the Wikipedia page for automorphic numbers [@wikipedia].

        from enigma import (irange, quadratic, sq, tri, printf)
        
        # Hensel's lemma - see [ https://en.wikipedia.org/wiki/Automorphic_number ]
        def hensel(poly, base, power):
          if power == 0: return [0]
          roots = hensel(poly, base, power - 1)
          rs = list()
          for r in roots:
            for i in irange(base):
              j = i * base ** (power - 1) + r
              x = poly(j) % (base ** power)
              if x == 0:
                rs.append(j)
          return rs
        
        # generate <k> digit automorphic numbers in base <b>
        # i.e. values of x where the rightmost k digits of x^2 are the digits of x
        def automorphic(k, b=10):
          poly = lambda x: x * x - x
          return hensel(poly, b, k)
        
        # consider 1-, 2- digit automorphic numbers in base 1501
        for k in (1, 2):
          for C in automorphic(k, 1501):
            if C < 18 or not (C < 1000000): continue
            # calculate n: C = n(3n + 1)/2
            for n in quadratic(3, 1, -2 * C, domain="Z"):
              if n < 6: continue
              S = sq(n)
              T = tri(n)
              printf("C={C} S={S} T={T} [n={n}]")
        

        Like

    • Robert Brown 6:19 pm on 17 June 2022 Permalink | Reply

      Hi Jim
      Your version of the text differs from the Sunday Times site. This asks “In base 10, what is the circular number?” You seem to have “what is the certain integer”.

      Like

      • Jim Randell 6:27 pm on 17 June 2022 Permalink | Reply

        Thanks. Of course if you know the “certain integer”, you can easily calculate the square, triangular and circular numbers.

        Interestingly, there is only one possible value for C, even if S and T are square and triangular numbers of different integers.

        Like

    • GeoffR 8:32 pm on 17 June 2022 Permalink | Reply

      if S and T are both less than 1,000,000, then C is less than 2,000,000.

      The last two digits in base 1501 give a max value of 2,253,000.

      i.e. 1500 *1501 + 1500, which is adequate to define C.

      
      # Square and triangular numbers are less than 1,000,000
      sqs = [x * x for x in range(5, 1000)]
      tris = [ x * (x+1)// 2 for x in range(6, 1410)]
      
      CNum = []  # list to store circular numbers
      
      # consider possible (S, T) combinations
      for S in sqs:
        for T in tris:
          C = S + T
          C2 = C * C
          # only 2 digits in base 1501 are needed
          # for the maximum value of C
          num, rem = divmod(C2, 1501)
          if rem == C:
            if C not in CNum: CNum.append(C)
      
      for n in CNum:
          print(f"Circular number = {n}")
      
      

      Like

      • Jim Randell 9:42 pm on 17 June 2022 Permalink | Reply

        @GeoffR: This is very similar to the first program I wrote. And then I realised that S = n² and T=tri(n) for the same value of n, which makes things much faster.

        It does however lead to the same answer for C, so there is a harder problem lurking inside this puzzle.

        Also I think the text implies that all of S, T, C are less than a million (and more than 17).

        But C is 1- or 2-digits in base 1501, so C² could be up to 4 digits, and we need to check the final 2 digits if C is length 2.

        Like

    • Frits 11:11 pm on 17 June 2022 Permalink | Reply

      Approaching it from the possible C values.

      I have assumed that when the number of digits in the remainder of (C^2 base 1501) is smaller than the number of digits in C we need to also check the last digits of the divisor of (C^2 base 1501).

         
      B = 1501
      
      # C = f(n) = n(3n + 1) // 2
      # f(n+1) - f(n) = (n + 1)(3(n + 1) + 1) // 2 - n(3n + 1) // 2
      #               = 2 + 3n
      
      C = 40        # as C >= 2 * 18
      for n in range(5, 817):  
        sC = str(C)
        lC = len(sC)
          
        C2 = C**2
        sC2 = str(C2)
        
        # next C
        C += (2 + 3 * n)
        
        # calculate remainder
        R1 = C2 % B
        lR1 = len(str(R1))
        
        # can we directly check all digits of C
        if lR1 >= lC:
          if str(R1)[-lC:] != sC: continue
        else: # len(R1) < lC
          # check last digits of C
          if sC[-lR1:] != str(R1): continue
          
          # check the digits of the divisor
          R2 = ((C2 - R1) // B) % B
          lR2 = len(str(R2))
          
          # check if digits in C correspond with the remainder of the divisor
          if sC[-lR1 + lR2:-lR1] != str(R2): continue
          
          # too lazy to code what happens if lR1 + lR2 < lC
          if lR1 + lR2 < lC: continue
          
        print("answer:", sC)
      

      Like

    • Frits 2:39 pm on 18 June 2022 Permalink | Reply

      @Jim,

      If the base is 272 is C = 57 an answer as C2ds=(11, 257) ?

      Like

      • Jim Randell 2:55 pm on 18 June 2022 Permalink | Reply

        @Frits: 57 is not automorphic in base 272.

        57 = {57}
        57² = {11:257}

        You compare the “digits” as atomic values not strings, so the final digit of 57² is 257 and this is not the same as 57.

        But 17 and 256 are both 1-digit automorphic numbers in base 272:

        17 = {17}
        17² = {1:17}

        256 = {256}
        256² = {240:256}

        Like

    • Frits 4:48 pm on 18 June 2022 Permalink | Reply

      There is no solution if the circular number has to be a round number as well (at least not in base 10).

      Like

    • Jim Randell 9:06 am on 21 June 2022 Permalink | Reply

      For an answer with larger values for S, T, C, but a smaller base, try solving the same puzzle with a base of 105.

      Like

    • GeoffR 12:08 pm on 21 June 2022 Permalink | Reply

      Easy to adapt Jim’s first program, substituting 105 for 1501 as the number base.

      This gives:

      n=458: S=209764 T=105111 C=314875 [C={28:58:85} C^2={7:80:71:28:58:85}]
      C is 3 digits long, so:
      28 * 105**2 + 58 * 105 + 85 = 314875

      Like

  • Jim Randell 4:38 pm on 22 April 2022 Permalink | Reply
    Tags: by: Colin Vout   

    Teaser 3109: Hole numbers 

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

    In theoretical golf, you have a set of “clubs” each of which hits a ball an exact number of yards forwards or backwards. You own the following set: 3, 8, 17, 19 and 35. For example, if a hole is 31 yards long, you can reach it in three strokes, with two forward hits of the 17 and a backward hit of the 3. In the next competition, you are only allowed to use three clubs, and the course consists of three holes whose lengths are 101, 151 and 197 yards. In order to get round the course in the fewest possible strokes, you must make a wise choice of clubs.

    Which three clubs (in ascending order) should you choose, and what will the individual hole scores be (in order)?

    [teaser3109]

     
    • Jim Randell 4:59 pm on 22 April 2022 Permalink | Reply

      This Python program runs in 61ms.

      Run: [ @replit ]

      from enigma import ordered, subsets, Accumulator, printf
      
      clubs = [3, 8, 17, 19, 35]
      holes = [101, 151, 197]
      
      # generate hole lengths and strokes using the specified clubs
      # m = max number of strokes
      def generate(clubs, m):
        # record total distance and individual strokes
        d = { 0: () }
        # distances to extend
        ts = list(d.keys())
        while ts:
          ts_ = list()
          for t in ts:
            # choose a club
            for n in clubs:
              # forwards or backwards?
              for x in (n, -n):
                t_ = t + x
                # is this a new distance?
                if t_ > 0 and t_ not in d:
                  ns_ = ordered(x, *d[t], reverse=1)
                  yield (t_, ns_)
                  d[t_] = ns_
                  if len(ns_) < m:
                    ts_.append(t_)
          # process the next batch
          ts = ts_
      
      # find lowest total number of strokes
      r = Accumulator(fn=min, collect=1)
      
      # choose 3 clubs
      for cs in subsets(clubs, size=3):
        # attempt to make the required holes
        rs = list()
        for (t, ns) in generate(cs, 30):
          if t in holes:
            rs.append((t, ns))
            if len(rs) == 3:
              # find total number of strokes
              ts = sum(len(ns) for (t, ns) in rs)
              printf("[cs={cs} -> {ts} strokes]")
              r.accumulate_data(ts, (cs, rs))
              break
      
      # output solution
      printf()
      printf("min = {r.value} strokes")
      for (cs, rs) in r.data:
        printf("-> clubs = {cs}")
        for (t, ns) in sorted(rs):
          printf("--> hole {t} = {ns}; {n} strokes", n=len(ns))
        printf()
      

      Solution: The optimal set of clubs is (3, 17, 35). Which achieves the 101 hole in 5 strokes, the 151 hole in 7 strokes, the 197 hole in 9 strokes, for a total of 21 strokes.

      hole 101 = (35, 35, 17, 17, −3)
      hole 151 = (35, 35, 35, 35, 17, −3, −3)
      hole 197 = (35, 35, 35, 35, 17, 17, 17, 3, 3)

      If the selection of clubs is not restricted the holes can be achieved in 18 strokes (although only 3 clubs are used per hole):

      hole 101 = (35, 35, 17, 17, −3)
      hole 151 = (35, 35, 35, 35, 8, 3)
      hole 197 = (35, 35, 35, 35, 35, 19, 3)

      Like

    • GeoffR 4:39 pm on 24 April 2022 Permalink | Reply

      This solution uses MiniZinc’s minimize constraint to minimise the total strokes for the clubs used for the three holes.

      It finds five sets of minimum total strokes in decreasing magnitude,
      The first four sets use clubs(3,8,35)

      The last (5th) print out is the answer to this teaser and uses a different set of three clubs to the first four solutions.

      % A Solution in MiniZinc
      include "globals.mzn";
       
      % Fixed golf hole lengths (yd), specified in teaser
      int: H1 = 101;  
      int: H2 = 151; 
      int: H3 = 197; 
      
      % a set of “clubs”
      set of int: clubs = {3, 8, 17, 19, 35};
      
      % Three clubs used from a set of six clubs
      var clubs: c1; var clubs: c2; var clubs: c3;
      constraint all_different([c1, c2, c3]);
      
      % Multiples of club strokes for each hole for three clubs
      % .. allowing for 3rd multiple as possible backward strokes
      var 1..5: m1; var 1..5: m2; var -5..5: m3;  % Hole 101 yd
      var 1..5: m4; var 1..5: m5; var -5..5: m6;  % Hole 151 yd
      var 1..5: m7; var 1..5: m8; var -5..5: m9;  % Hole 197 yd
      
      % 1st hole(101 yd)
      constraint H1 == m1*c1 + m2*c2 + m3*c3;
      % 2nd hole(151 yd)
      constraint H2 == m4*c1 + m5*c2 + m6*c3;
      % 3rd hole(197 yd)
      constraint H3 == m7*c1 + m8*c2 + m9*c3;
      
      % use abs function for 3rd club possible negative value
      solve minimize(m1 + m2 + abs(m3) + m4 + m5 + abs(m6) + m7 + m8 + abs(m9));
      
      output ["Total strokes = " ++ 
      show (m1 + m2 + abs(m3) + m4 + m5 + abs(m6) + m7 + m8 + abs(m9))
      ++ ", Clubs used = " ++ show([c1, c2, c3]) 
      ++ "\n" ++ "Hole 101 yd = " ++ show([m1, c1, m2, c2, m3, c3])
      ++ "\n" ++ "Hole 151 yd = " ++ show([m4, c1, m5, c2, m6, c3])
      ++ "\n" ++ "Hole 197 yd = " ++ show([m7, c1, m8, c2, m9, c3])
      ];
      
      
      

      Like

  • Jim Randell 4:35 pm on 21 January 2022 Permalink | Reply
    Tags: by: Colin Vout   

    Teaser 3096: That strikes a chord 

    From The Sunday Times, 23rd January 2022 [link] [link]

    Skaredahora used a scale with seven notes, labelled J to P, for an idiosyncratic composition. It had a sequence of chords, each comprising exactly three different notes (the order being immaterial). The sequence started and ended with JNP. Each change from one chord to the next involved two notes increasing by one step in the repeating scale, and the other decreasing by two steps (e.g. JNP changing to KLJ).

    Every chord (eventually) reachable from JNP was used at least once; every allowable change from one of these chords to another was used exactly once. The number of chord changes between the first pair of JNPs was more than that between the last such pair, but, given that, was the smallest it could be.

    With notes in alphabetical order, what was the seventh chord in the sequence?

    [teaser3096]

     
    • Jim Randell 7:20 pm on 21 January 2022 Permalink | Reply

      I am assuming notes that are an octave apart are considered identical. So going up three notes from M to P gives the same note as going down 4 notes from M to P. Also that chords are identical if they contain the same three notes, and a chord change requires at least one of the notes to change.

      This Python program constructs the graph of transitions between chords, and then finds paths from JNP back to JNP that traverse all the edges (Eulerian circuits). We then apply the remaining conditions, and find the 7th element of the paths.

      It runs in 51ms.

      Run: [ @replit ]

      from enigma import (mod, all_different, ordered, tuples, Accumulator, join, printf)
      
      # there are 7 notes in the scale
      fn = mod(7)
      
      # format a sequence, 0..6 represent J..P
      fmt = lambda s: join("JKLMNOP"[i] for i in s)
      fmts = lambda ss: join((fmt(s) for s in ss), sep=" ", enc="()")
      
      # start node = JNP
      start = (0, 4, 6)
      assert fmt(start) == 'JNP'
      
      # generate changes for chord <s>
      def changes(s):
        (x1, y1, z1) = (fn(n + 1) for n in s)
        (x2, y2, z2) = (fn(n - 2) for n in s)
        for t in ((x2, y1, z1), (x1, y2, z1), (x1, y1, z2)):
          t = ordered(*t)
          if t != s and all_different(*t):
            yield t
      
      # generate possible transitions, starting with <start>
      adj = dict()
      trans = set()
      ns = {start}
      while ns:
        ns_ = set()
        for s in ns:
          ts = set(changes(s))
          adj[s] = ts
          trans.update((s, t) for t in ts)
          ns_.update(ts)
        ns = ns_.difference(adj.keys())
      
      # find sequences that use every transition in <ts>, starting from <ss>
      def seqs(ts, ss):
        # are we done?
        if not ts:
          yield ss
        else:
          # make a transition
          s = ss[-1]
          for x in adj[s]:
            t = (s, x)
            if t in ts:
              yield from seqs(ts.difference([t]), ss + [x])
            
      # find viable sequences
      def generate(trans, start):
        for ss in seqs(trans, [start]):
          # sequence must be a circuit
          if ss[0] != ss[-1]: continue
          # find the indices of start
          js = list(j for (j, x) in enumerate(ss) if x == start)
          # and distances between them
          ds = list(j - i for (i, j) in tuples(js, 2))
          # first distance is greater than last
          if not (ds[0] > ds[-1]): continue
          # return (distances, sequence)
          yield (ds, ss)
      
      # find the smallest first distance
      r = Accumulator(fn=min, collect=1)
      for (ds, ss) in generate(trans, start):
        r.accumulate_data(ds[0], ss)
      
      # output solutions
      for ss in r.data:
        printf("{x} {ss}", x=fmt(ss[6]), ss=fmts(ss))
      

      Solution: The seventh chord in the sequence is: KNO.

      The complete sequence is:

      1. JNP
      2. JKL
      3. KMP
      4. JKL
      5. LMO
      6. JNP
      7. KNO
      8. LMO
      9. KMP
      10. JNP

      [Follow the [@replit] link, click on “Show Files”, and select “Teaser 3096.mp3” to hear the chords played with JP transposed to notes AG in a single octave].

      There are 4 chords between the first two JNPs, and 3 chords between the last two JNPs.

      And this is the only progression of the form (JNP [4] JNP [3] JNP).

      There are 4 other viable progressions of the form (JNP [5] JNP [2] JNP), but we are only interested in progressions with the shortest possible distance between the first two occurrences of JNP.

      Like

  • Jim Randell 4:56 pm on 3 December 2021 Permalink | Reply
    Tags: by: Colin Vout   

    Teaser 3089: An old square 

    From The Sunday Times, 5th December 2021 [link] [link]

    Archaeologists have excavated an ancient area that has the shape of a perfect square. Fragmentary documents give some information about its measurements: the number of major units along a side is less than the remaining number of minor units; there is a whole number of minor units in a major unit (no more than 10); and the area is a certain number of square major units plus a remainder of 15 square minor units.

    Expressed just in terms of minor units, how many are there along a side?

    [teaser3089]

     
    • Jim Randell 5:08 pm on 3 December 2021 Permalink | Reply

      If we suppose a major unit consists of x minor units (x ≤ 10), then the side of the square can be expressed as a major units plus b minor units (= ax + b minor units) where a < b < x.

      The following Python program runs in 45ms.

      Run: [ @replit ]

      from enigma import (irange, subsets, div, sq, printf)
      
      # consider x minor units in a major unit (no more than 10)
      # consider a major + b minor units (a < b < x)
      for (a, b, x) in subsets(irange(1, 10), size=3):
        # the side of the square is (ax + b) (minor units)
        s = a * x + b
        # can s^2 be expressed as k x^2 + 15?
        k = div(sq(s) - 15, sq(x))
        if k is not None:
          printf("x={x} a={a} b={b}; s={s} (= {a}x + {b}); s^2 = {k}x^2 + 15")
      

      Solution: The area is a square with each side measuring 41 minor units.

      So the entire area measures 41 × 41 = 1681 minor units.

      There are 7 minor units in a major unit (so the side of the square is 5 major + 6 minor units).

      And the area of the square can be expressed as 34 square major + 15 square minor units.

      Like

    • Frits 3:28 pm on 4 December 2021 Permalink | Reply

      I have the feeling X might be logically determined as the Wolframalpha site for this equation only shows solutions for a specific positive X.

        
      #!/usr/bin/env python3 -m enigma -r
       
      SubstitutedExpression
       
      --base=11
       
      "B < X"
      
      # if X is even then A * X + B must be odd so B must be odd as well
      "X % 2 or B % 2"
      
      # if X is 10 then sq(A * X + B) ends on a 5 so B must be 5
      "X < 10 or B == 5"
      
      "A < B"
       
      "div(2 * A * B * X + B * B - 15, sq(X))"
       
      --answer="A * X + B"
      # if X is 5 then sq(A * X + B) ends on 0 or 5 so B must be 0 or 5, impossible
      --invalid="0|1|2|3|5,X"
      --invalid="0|1|10,B"
      # A can't be 8 as if X is 10 then B must be 5
      --invalid="0|8|9|10,A"
      #--verbose=256   # print generated code
      

      Like

    • GeoffR 9:29 am on 5 December 2021 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % a major units, x minor units in one major unit and b minor units
      var 1..9:a; var 1..9:b; var 1..9:x;
      % S = side of perfect square
      var 1..50:S;
      
      constraint a < b  /\ b < x;
      constraint S == a * x + b;  
      
      % the area is a certain number of square major units
      % plus a remainder of 15 square minor units
      constraint S * S mod (x*x) == 15;
      
      solve satisfy;
      
      output["Side in minor units = " ++ show(S) ++ "  " 
      ++ "\n" ++ "a = " ++ show(a)  ++ ", b = " ++ show(b) ++ ", x = " ++ show(x)];
      
      
      

      Like

      • Jim Randell 9:54 am on 5 December 2021 Permalink | Reply

        @GeoffR: x is “no more than 10”, so [[ var 1..10: x; ]] would be more appropriate.

        Like

    • GeoffR 10:19 am on 5 December 2021 Permalink | Reply

      @Jim: Yes, correct. I was assuming x < 10.
      Fortunately, it does not affect the answer.

      Like

  • Jim Randell 4:18 pm on 22 October 2021 Permalink | Reply
    Tags: by: Colin Vout   

    Teaser 3083: Village signposts 

    From The Sunday Times, 24th October 2021 [link]

    Inside a shed I saw where the council was preparing signposts for seven neighbouring villages. Between any two villages there is at most one direct road, and the roads don’t meet except at village centres, where the signposts are to stand. The arms were all affixed, and labelled except for one name to be completed on each. The names in clockwise order on each were as follows:

    Barton, Aston, ?
    Barton, Grafton, ?
    Carlton, Forton, Eaton, ?
    Grafton, Aston, ?
    Dalton, Grafton, Eaton, ?
    Barton, Forton, Carlton, ?
    Dalton, Aston, ?

    Starting at Dalton, I walked along roads, taking the road furthest rightwards at each village and returning to Dalton. I chose the first road so that I visited as many other villages as possible with this method.

    In order, what were the other villages I visited?

    [teaser3083]

     
    • Jim Randell 10:18 pm on 22 October 2021 Permalink | Reply

      I’m not quite sure what “furthest rightwards” means in this context. At the moment I’m assuming it means when I arrive in a village I take the “first right” (i.e. the road that is anti-clockwise from that which I entered the village on).

      And using this interpretation I think there is a unique layout and solution.

      I determined the layout manually (but with programmatic assistance, a fully programmatic determination is given below). The following Python program finds the longest “first right” journey on this layout.

      Run: [ @replit ]

      from enigma import (Accumulator, join, printf)
      
      # the layout is determined by teaser3083c.py
      graph = dict(D='BAC', E='BGF', G='CFEB', F='GAE', B='DGEA', A='BFCD', C='DAG')
      
      # make a journey on the graph, taking the "first right" at each village
      def journey(vs):
        while True:
          (v0, v1) = vs[-2:]
          # are we done?
          if v1 == vs[0]:
            return vs
          # choose the next destination
          ds = graph[v1]
          i = ds.index(v0)
          vs.append(ds[i - 1])
      
      # format a journey
      fmt = lambda vs: join(vs, sep=" -> ")
      
      # find maximal length journeys
      r = Accumulator(fn=max, collect=1)
      
      # start at D, and choose initial destination
      for v in graph['D']:
        vs = journey(['D', v])
        printf("{vs}", vs=fmt(vs))
        r.accumulate_data(len(vs), vs)
      
      for vs in r.data:
        printf("longest: {vs}", vs=fmt(vs))
      

      Solution: The other villages visited were: Carlton, Grafton, Barton.

      Here is a diagram that shows the layout of the roads:

      The possible “first right” journeys from D are:

      D → A → C → D
      D → B → A → D
      D → C → G → B → D

      Like

      • Jim Randell 10:34 pm on 23 October 2021 Permalink | Reply

        And here is a fully programmed solution that determines the layout of the graph (as used in the program above).

        It considers possible ways to complete the signs that give 12 roads, with a signpost at each end, and then assembles them into an acceptable layout with no crossing roads. It does this by turning each town into a “molecule” with the specified roads leading out of it, and then allows one molecule to gradually absorb each of the others so that the roads form a viable layout.

        It runs in 603ms.

        from enigma import (union, multiset, ordered, unpack, irange, find, seq_all_different, Accumulator, map2str, printf)
        
        # the given signposts (with known destinations)
        signs = [ 'BA', 'BG', 'CFE', 'GA', 'DGE', 'BFC', 'DA' ]
        
        # determine the labels used
        labels = union(signs)
        assert len(labels) == len(signs)
        
        # choose a distinct element from each set
        def choose(ss, s=[]):
          # are we done?
          if not ss:
            yield s
          else:
            for x in ss[0]:
              if x not in s:
                yield from choose(ss[1:], s + [x])
        
        # look for the longest match between s1 and s2
        def align(s1, s2):
          r = Accumulator(fn=max)
          n = len(s2)
          for j in irange(1, n):
            # does the first element of s2 match s1?
            i = find(s1, s2[0])
            if i != -1:
              # bring it to the front of s1
              if i > 0: s1 = s1[i:] + s1[:i]
              k = 1
              # extend the match if possible
              while k < n and s1[-1] == s2[k]:
                s1.insert(0, s1.pop(-1))
                k += 1
              # all matches must be used
              if seq_all_different(s1[k:] + s2[k:]):
                # save the length of the match and the aligned sequences      
                r.accumulate_data(k, (list(s1), list(s2)))
              if k == n: break
            if j < n:
              # rotate s2
              s2.append(s2.pop(0))
          if r.value: return (r.value,) + (r.data)
          return (None, None, None)
        
        # can we merge the blobs into a single blob?
        def merge(blobs, blob=None):
          rev = lambda s: s[::-1]
          # initial blob?
          if blob is None:
            (i, blob) = max(enumerate(blobs), key=unpack(lambda i, x: len(x)))
            blob = list(rev(x) for x in blob)
            blobs.pop(i)
          # process the remaining blobs
          while blobs:
            # find the most matching of the remaining blobs
            r = Accumulator(fn=max)
            for (j, b) in enumerate(blobs):
              (k, blob_, b_) = align(blob, b)
              if k:
                r.accumulate_data((k, k - len(b)), (j, b_, blob_))
            if not r.value: return False
            ((k, _), (j, b, blob)) = (r.value, r.data)
            # merge blobs
            blob = blob[k:] + list(rev(x) for x in b[k:])
            blobs.pop(j)
          # did everything match up?
          return not blob
        
        # check the graph can be laid out (could check graph planarity)
        def check(g):
          # each blob is a list roads
          blobs = list(list(k + v for v in vs) for (k, vs) in g.items())
          # can the blobs be merged?
          return merge(blobs)
        
        # choose a location for each signpost
        for locs in choose(list(labels.difference(s) for s in signs)):
          # choose the missing destinations
          for dests in choose(list(labels.difference(s + v) for (v, s) in zip(locs, signs))):
            # make the graph
            g = dict((v, s + d) for (v, s, d) in zip(locs, signs, dests))
            # count the roads
            rs = multiset()
            for (s, ds) in g.items():
              rs.update_from_seq(ordered(s, d) for d in ds)
            # each road should have 2 ends
            if not all(v == 2 for v in rs.values()): continue
            # can the graph be laid out?
            if not check(g): continue
            # output the graph
            printf("graph = {g}", g=map2str(g))
        

        Without the [[ check() ]] function at line 90, we find there are 8 candidate layouts, which originally I drew out manually, and the “correct” one was immediately obvious. But it was quite fun to come up with an algorithm to determine which of the layouts is viable.

        Like

  • Jim Randell 4:33 pm on 10 September 2021 Permalink | Reply
    Tags: by: Colin Vout   

    Teaser 3077: Shuffling series schedules 

    From The Sunday Times, 12th September 2021 [link]

    A TV company planned a set of programmes to fill a weekly slot (one programme per week for many weeks) with six consecutive series of three different types (Arts, Biography and Comedy). None of the series was followed by another of the same type (e.g. there could be an Arts series for three weeks then a Comedy series for four weeks and so on). Then it decided to change the order of the series within the same overall slot, but to minimise disruption it would not alter the gaps between series of the same type. It did this by scheduling each of the three Arts series 6 weeks earlier than first planned, each of the two Biography series 20 weeks later than first planned, and the Comedy series 21 weeks earlier than first planned.

    How many programmes are in each of the six series after the change, in order?

    [teaser3077]

     
    • Jim Randell 5:31 pm on 10 September 2021 Permalink | Reply

      The following Python program finds orders that satisfy the given conditions, and then choose a “before” and “after” ordering, and uses them to construct a collection of 6 equations in 6 variables, which it then solves for positive integer solutions.

      It runs in 56ms.

      Run: [ @replit ]

      from enigma import subsets, tuples, multiset, matrix, as_int, map2str, join, printf
      
      # the programs
      progs = "AAABBC"
      
      # label a sequence, e.g. label(ABCABA) -> (A1 B1 C1 A2 B2 A3)
      def label(ps):
        m = multiset()
        s = list()
        for p in ps:
          m.add(p)
          s.append(p + str(m.count(p)))
        return s
      
      # find orderings of the programs with no consecutive letters
      orders = list(label(s) for s in subsets(progs, size=len, select="mP") if all(x != y for (x, y) in tuples(s, 2)))
      
      # choose a before and after ordering
      for (before, after) in subsets(orders, size=2, select="P"):
      
        # name the variables
        vs = sorted(before)
      
        # construct a collection of equations
        eqs = list()
        for v in vs:
          eq = [0] * len(vs)
          # add in the after amounts
          for q in after:
            if q == v: break
            eq[vs.index(q)] += 1
          # and subtract the before amounts
          for q in before:
            if q == v: break
            eq[vs.index(q)] -= 1
          eqs.append(eq)
          
        # solve the equations, for positive integers
        try:
          rs = list(as_int(x, '+') for x in matrix.linear(eqs, [-6, -6, -6, 20, 20, -21]))
        except ValueError:
          continue
      
        # output solution
        printf("runs: {rs} [before = {bf}; after = {af}]",
          rs=map2str(zip(vs, rs), sep=" ", enc=""),
          bf=join(before, sep=" ", enc="()"),
          af=join(after, sep=" ", enc="()"),
        )
      

      Solution: The number of programmes in each series after the change are: 5, 6, 9, 6, 5, 6.

      The two schedules are:

      Before: B1 (6); A1 (5); B2 (6); A2 (9); C1 (6); A3 (5)
      After: A1 (5); C1 (6); A2 (9); B1 (6); A3 (5); B2 (6)


      Manually:

      Neither A1 nor C1 can start the “before” sequence (as the As and Cs must be earlier in the “after” sequence), so the before sequence must start with B1, and the 5 remaining spaces must be (A1, ?, A2, ? A3), in order for the As not to be consecutive:

      before = (B1, A1, C1, A2, B2, A3)
      before = (B1, A1, B2, A2, C1, A3)

      Both these sequences end in A3, so A3 cannot be last in the “after” sequence, and in order for the As to be non-consecutive we have (A1, ?, A2, ?, A3, ?), giving:

      after = (A1, B1, A2, B2, A3, C1)
      after = (A1, B1, A2, C1, A3, B2)
      after = (A1, C1, A2, B1, A3, B2)

      The first of these is eliminated as C1 must occur 21 weeks earlier than in “before”, so cannot come at the end. So B2 comes at the end.

      We can go ahead and look at the equations produced by the 4 possibilities:

      before = (B1, A1, C1, A2, B2, A3)
      after = (A1, B1, A2, C1, A3, B2)

      [A1] (0) − (B1) = −6 ⇒ B1 = 6
      [B1] (A1) − (0) = +20 ⇒ A1 = 20
      [C1] (A1 + B1 + A2) − (B1 + A1) = −20 ⇒ A2 = −20 [***impossible***]

      before = (B1, A1, C1, A2, B2, A3)
      after = (A1, C1, A2, B1, A3, B2)

      [A1] (0) − (B1) = −6 ⇒ B1 = 6
      [C1] (A1) − (B1 + A1) = −21 ⇒ −6 = −21 [***impossible***]

      So “before” must be (B1, A1, B2, A2, C1, A3):

      before = (B1, A1, B2, A2, C1, A3)
      after = (A1, B1, A2, C1, A3, B2)

      [B1] (A1) − (0) = +20 ⇒ A1 = 20
      [A1] (0) − (B1) = −6 ⇒ B1 = 6
      [A2] (A1 + B1) − (B1 + A1 + B2) = −6 ⇒ B2 = 6
      [C1] (A1 + B1 + A2) − (B1 + A1 + B2 + A2) = −21 ⇒ B2 = 21
      [B2] (A1 + B1 + A2 + C1 + A3) − (B1 + A1) = +20 ⇒ A3 = −7 [***impossible***]

      So, there is only one possibility left:

      before = (B1, A1, B2, A2, C1, A3)
      after = (A1, C1, A2, B1, A3, B2)

      [A1] (0) − (B1) = −6 ⇒ B1 = 6
      [A3] (A1 + C1 + A2 + B1) − (B1 + A1 + B2 + A2 + C1) = −6 ⇒ B2 = 6
      [A2] (A1 + C1) − (B1 + A1 + B2) = −6 ⇒ C1 = 6
      [C1] (A1) − (B1 + A1 + B2 + A2) = −21 ⇒ A2 = 9
      [B1] (A1 + C1 + A2) − (0) = +20 ⇒ A1 = 5
      [B2] (A1 + C1 + A2 + B1 + A3) − (B1 + A1) = +20 ⇒ A3 = 5

      Hence: A1=5, A2=9, A3=5, B1=6, B2=6, C1=6.

      Like

      • Frits 1:30 pm on 12 September 2021 Permalink | Reply

        @Jim

        Just wondering, how did you come up with this linear equations approach?

        Like

        • Jim Randell 1:46 pm on 12 September 2021 Permalink | Reply

          There are six unknowns we need to work out (the number of programs in each series), and we were given six known values (the difference between the start weeks of each series in the “before” and “after” schedules). So it seemed like a good candidate for a collection of 6 equations in 6 unknowns.

          The start week of each series is just the sum of the number of programs of the preceding series, so we can express the difference between the start weeks of a series in both schedules as the difference between these sums, and that gives us six linear equations in the six unknowns.

          The [[ matrix.linear() ]] solver from the enigma.py library will reject any system of equations that is inconsistent or incomplete, and we look for solutions where the results are all positive integers, and only a single answer popped out, and in a very reasonable time, so there was no need for any additional analysis.

          Manually, a little bit of analysis shows us that there are only 2 possible “before” sequences, and 2 possible “after” sequences, and only one of the 4 possible pairings give equations that solve to give positive integers.

          Like

  • Jim Randell 4:59 pm on 23 July 2021 Permalink | Reply
    Tags: by: Colin Vout   

    Teaser 3070: Film binge 

    From The Sunday Times, 25th July 2021 [link]

    I’m going to have a day binge-watching films. My shortlist is:

    Quaver, starring Amerton, Dunino, Emstrey, Fairwater and Joyford;
    Rathripe, starring Amerton, Codrington, Fairwater, Glanton and Ingleby;
    Statecraft, starring Amerton, Codrington, Dunino, Hendy and Ingleby;
    Transponder, starring Codrington, Dunino, Emstrey, Hendy and Ingleby;
    Underpassion, starring Blankney, Emstrey, Fairwater, Hendy and Ingleby;
    Vexatious, starring Amerton, Blankney, Dunino, Emstrey and Joyford;
    Wergild, starring Blankney, Fairwater, Glanton, Hendy and Joyford;
    X-axis, starring Blankney, Codrington, Fairwater, Glanton and Ingleby;
    Yarborough, starring Blankney, Dunino, Glanton, Hendy and Joyford;
    Zeuxis, starring Amerton, Codrington, Emstrey, Glanton and Joyford.

    I dislike Ingleby and Joyford, so I don’t want either of them in more than two films; but I want to see each of the others in at least two films.

    Which are the films I should watch?

    [teaser3070]

     
    • Jim Randell 5:17 pm on 23 July 2021 Permalink | Reply

      A directed search would let us prune away subsets with too much I and J in, but on a problem of this size we can just examine all possible subsets of films to see which collections meet the criteria.

      The following Python program runs in 67ms.

      Run: [ @replit ]

      from enigma import subsets, union, multiset, join, printf
      
      # the films and the stars
      films = {
        'Q': 'ADEFJ', 'R': 'ACFGI', 'S': 'ACDHI', 'T': 'CDEHI', 'U': 'BEFHI',
        'V': 'ABDEJ', 'W': 'BFGHJ', 'X': 'BCFGI', 'Y': 'BDGHJ', 'Z': 'ACEGJ',
      }
      stars = union(films.values())
      
      # selection criteria:
      # I, J in no more than 2 films, otherwise in at least 2 films
      fn = lambda k, n: (n <= 2 if k in 'IJ' else n >= 2)
      
      # choose films
      for ks in subsets(films.keys(), min_size=2):
        # collect the stars
        ss = multiset.from_seq(*(films[k] for k in ks))
        # perform the check
        if all(fn(k, ss.count(k)) for k in stars):
          printf("films = {ks}", ks=join(ks, sep=' '))
      

      Solution: The chosen films are: Rathripe, Transponder, Vexatious, Wergild.

      For this collection, each of the stars (including I and J) are in exactly 2 of the films. And this is the only collection that meets the required condition.

      Like

      • Jim Randell 1:04 pm on 26 July 2021 Permalink | Reply

        The particular set of films used in the puzzle allow us to make some shortcuts:

        As exactly one of I or J is in each of the films, we can see that we can be looking for no more than 4 films (2 with I and 2 with J). And each of the films has exactly 4 of the other stars in.

        So to see at least 2 films involving each of the other stars we are going to need to see at least 8×2/4 = 4 films. So of the 20 stars involved in each of the 4 films, each must appear twice.

        Hence we need to look for exactly 4 films, so we could just pass [[ size=4 ]] at line 15 of my original program. Or, more efficiently, we could consider combinations of 2 films involving I and 2 films involving J.

        from enigma import subsets, join, printf
        
        # the films and the stars
        filmsI = {
          #     ABCDEFGHIJ
          'R':  1010011010,
          'S':  1011000110,
          'T':    11100110,
          'U':   100110110,
          'X':   110011010,
        }
        
        filmsJ = {
          #     ABCDEFGHIJ
          'Q':  1001110001,
          'V':  1101100001,
          'W':   100011101,
          'Y':   101001101,
          'Z':  1010101001,
        }
        
        # collect sums for pairs of films for I and J
        pairs = lambda d: dict((d[x] + d[y], (x, y)) for (x, y) in subsets(d.keys(), size=2))
        (psI, psJ) = (pairs(filmsI), pairs(filmsJ))
        
        # consider a pair of films for I ...
        target = 2222222222
        for (sI, fsI) in psI.items():
          # ... with a corresponding value for J
          fsJ = psJ.get(target - sI, None)
          if fsJ is not None:
            printf("films = {fs}", fs=join(sorted(fsI + fsJ), sep=' '))
        

        Technically this program will find a solution, but the selection of films in this particular puzzle have been chosen so there is a unique subset that give the required answer.

        Note: Placing leading zeroes in the film values does not work in Python 3 ([[ 0011100110 ]] is not a valid integer literal, although [[ int('0011100110') ]] does work). In Python 2.7 [[ 0011100110 ]] is a valid integer literal, but is interpreted as an octal (base 8) number, so although the program does run, it will not give the correct answer. (Which is presumably why this was made an error in Python 3).

        To allow leading zeroes we could do everything in octal, by prefixing with 0o (or in hexadecimal, using the 0x prefix – there is no corresponding 0d prefix for decimal), including the target value 2222222222.

        Like

  • Jim Randell 4:40 pm on 2 July 2021 Permalink | Reply
    Tags: by: Colin Vout   

    Teaser 3067: Reciprocal arrangement 

    From The Sunday Times, 4th July 2021 [link]

    Twelve men from our football squad had turned up for training, and I’d promised them a game of six-a-side at the end of the session; so while they were off on a gentle three-mile run I worked out what the two teams would be. They were wearing their squad numbers, which had one or two digits: 2, 3, 4, 5, 6, 7, 8, 9, 15, and three others. It appealed to me when I found that I could divide them into two teams of six, such that the sum of the reciprocals of the squad numbers in each team equalled one exactly.

    What were the squad numbers in the team containing number 2?

    [teaser3067]

     
    • Jim Randell 4:49 pm on 2 July 2021 Permalink | Reply

      (See also: Enigma 348, Enigma 1087, Enigma 1062, Enigma 501).

      I used the [[ reciprocals() ]] function from the enigma.py library (originally written for Enigma 348) to generate the sums of reciprocals. And this lets us keep things entirely in the integer domain.

      This Python program runs in 83ms.

      Run: [ @replit ]

      from enigma import (reciprocals, subsets, union, printf)
      
      # numbers we are given
      numbers = {2, 3, 4, 5, 6, 7, 8, 9, 15}
      
      # look for 6 (different) reciprocals that sum to 1
      ss = reciprocals(6, M=99, g=1)
      
      # choose 2 disjoint sets of numbers
      for (t1, t2) in subsets(ss, size=2):
        ns = union([t1, t2])
        if len(ns) == 12 and ns.issuperset(numbers):
          printf("teams = {t1} vs {t2}")
      

      Solution: The six members of the team containing 2 were: 2, 6, 7, 9, 18, 42.

      And the six members of the other team were: 3, 4, 5, 8, 15, 40.

      Like

      • Jim Randell 5:32 pm on 2 July 2021 Permalink | Reply

        Here’s a slightly longer, but more efficient program.

        It finds three additional shirt numbers that bring the total reciprocal sum for all 12 numbers to 2. And then looks for 5 numbers with a reciprocal sum of 1/2 to go with 2 to make one of the teams.

        Using the [[ fraction() ]] function from the enigma.py library means we don’t have to use rationals.

        It runs in 54ms.

        from enigma import (fraction, unpack, flatten, reciprocals, subsets, printf)
        
        # numbers we are given
        numbers = {2, 3, 4, 5, 6, 7, 8, 9, 15}
        
        # find the sum of the reciprocals
        rsum = lambda xs, fn=unpack(fraction): fn(flatten((1, x) for x in xs))
        (p, q) = rsum(numbers)
        
        # find 3 more numbers that bring the total reciprocal sum to 2
        for xs in reciprocals(3, q, 2 * q - p, m=10, M=99, g=1):
          ns = numbers.union(xs)
          if len(ns) != 12: continue
        
          # choose 5 numbers to go with 2
          for ns1 in subsets(ns.difference([2]), size=5, fn=list):
            if rsum(ns1) == (1, 2):
              t1 = sorted([2] + ns1)
              t2 = sorted(ns.difference(t1))
              printf("teams = {t1} vs {t2}")
        

        Like

    • Frits 1:56 pm on 3 July 2021 Permalink | Reply

      Based on Jim’s second approach (avoiding rational number logic).

      from enigma import lcm, divisors
      
      # pick <k> elements from list <li> that sum to <s>
      def pickElements(k, li, s, ns=[]):
        if k == 1:
          r = s - sum(ns)
          if r in li and r not in ns:
            yield [L // x for x in ns + [r]]
        else:
          for i in range(len(li)):
            yield from pickElements(k - 1, li[i + 1:], s, ns + [li[i]])
      
      # numbers we are given
      numbers = {2, 3, 4, 5, 6, 7, 8, 9, 15}
      
      L = lcm(*numbers)  # Least Common Multiple
      
      # sum(i=1..12, 1 / x) = 2 then also sum(i=1..12, L / x) = 2 * L
      rest = 2 * L - sum(L // x for x in numbers)
      
      # determine candidates for three remaining squad numbers
      cands = [L // x for x in divisors(L) if 9 < x < 100 and x not in numbers]
      
      last2 = cands[-1] + cands[-2]
      # remove big values from list
      cands = [x for x in cands if x + last2 <= rest]
      
      # pick three remaining squad numbers
      for p in pickElements(3, cands, rest):
        twelve = numbers | set(p)
        (s1, s2) = (twelve.difference([7]), [7])
      
        # in the group containing 7 there must be a multiple of 7 as well
        p7 = [x for x in p if x % 7 == 0]
        if len(p7) == 1:
          s1 = s1.difference([p7[0]])
          s2.append(p7[0])
      
        # determine candidates for the group with 7
        cands2 = [L // x for x in twelve if x not in s2]
        rest2 = L - sum(L // x for x in s2)
       
        # pick squad numbers to go with 7 (and multiple of 7)
        for p2 in pickElements(6 - len(s2), cands2, rest2):
          t1 = p2 + s2
          if 2 in t1:
            print("answer:", sorted(t1))
          else:
            print("answer:", sorted(twelve.difference(t1)))
      

      Like

    • GeoffR 7:08 pm on 16 September 2021 Permalink | Reply

      Probably not the best idea to mix floating point and integer numbers generally, but with very small difference tests, it gave the correct solution.

      from itertools import combinations
      
      NL = []   # list for squad numbers of two teams
      
      # set of given squad numbers
      NS = {2, 3, 4, 5, 6, 7, 8, 9, 15}
      
      for p1 in combinations(range(10, 100), 3):
        # find three other squad numbers
        a, b, c = p1
        if any(x in NS for x in (a, b, c)):
          continue
        s12num = 1 / 2 + 1 / 3 + 1 / 4 + 1 / 5 + 1 / 6 + 1 / 7 + \
               1 / 8 + 1 / 9 + 1 / 15 + 1 / a + 1 / b + 1 / c
        if abs(s12num - 2) >= 1e-9:
          continue
        NS = NS.union([a, b, c])  # missing squad numbers
        
        # find numbers in 1st squad
        for p2 in combinations(NS, 6):
          d, e, f, g, h, i = p2
          # find reciprocal sum of 1st squad numbers
          t1 = 1 / d + 1 / e + 1 / f + 1 / g + 1 / h + 1 / i
          if abs(t1) - 1 >= 1e-9:
            continue
          Q = NS.difference([d, e, f, g, h, i])
      
          # find numbers in 2nd squad
          for p3 in combinations(Q, 6):
            j, k, m, n, p, q = p3
            # find reciprocal sum of 2nd squad numbers
            t2 = 1 / j + 1 / k + 1 / m + 1 / n + 1 / p + 1 / q
            if abs(t2) - 1 >= 1e-9:
              continue
            if p2 not in NL: NL.append(p2)
            if p3 not in NL: NL.append(p3)
            
      # find team numbers of two teams
      if len(NL) == 2:
        print(f" 1st Team Numbers are {sorted(NL[0])}")
        print(f" 2nd Team Numbers are {sorted(NL[1])}")
          
      # 1st Team Numbers are [2, 6, 7, 9, 18, 42] <<< Ans
      # 2nd Team Numbers are [3, 4, 5, 8, 15, 40]
      
      
      

      Like

  • Jim Randell 7:56 pm on 4 June 2021 Permalink | Reply
    Tags: by: Colin Vout   

    Teaser 3063: Pie by five 

    From The Sunday Times, 6th June 2021 [link]

    We had a delicious pie, rectangular and measuring 20 centimetres along the top and 13 centimetres in the other direction. We divided it into five pieces of equal area, using five straight cuts radiating from one internal point. This internal point was rather off centre, in the top left-hand quarter, although the distances from the left and top sides were both a whole number of centimetres. The points where the cuts met the edges were also whole numbers of centimetres along the edges; one edge had two cuts meeting it, and the other three edges had one each.

    How far was the internal point from the left and top sides, and how far along the four sides (starting at the top) did the cuts reach the edges (measured clockwise along the edges)?

    [teaser3063]

     
    • Jim Randell 9:59 pm on 4 June 2021 Permalink | Reply

      Each portion has an area equal to one fifth of the whole pie.

      The portion between the two cuts on the same side is composed of a single triangle (with, as it turns out, its base along the bottom edge). The remaining portions are composed of two adjacent triangles, with their bases on adjacent edges.

      Using the top left corner of the pie as the origin, we can consider integer (x, y) co-ordinates for the starting point of the cuts (in the top left quadrant of the pie). We can then consider 2 integer marks on the bottom that give a triangular slice with one fifth the area of the pie, and the marks on the other edges can then be determined.

      This Python program runs in 54ms.

      Run: [ @replit ]

      from itertools import product
      from enigma import Rational, irange, divf, printf
      
      Q = Rational()
      
      # is rational q an integer?
      as_int = lambda q: (q.numerator if q.denominator == 1 else None)
      
      # dimensions of the rectangle
      (X, Y) = (20, 13)
      
      # area of each portion
      A = Q(X * Y, 5)
      printf("[X={X} Y={Y}; A={A}]")
      
      # calculate area of a triangle with base b and height h
      area = lambda b, h: Q(b * h, 2)
      
      # calculate base of triangle with area A and height h
      base = lambda A, h: Q(2 * A, h)
      
      # find solutions with cuts starting at (x, y)
      def solve(x, y):
        # look for the portion composed of 1 triangle:
        # bottom marks, (a, Y), (b, Y); distance z (= b - a) apart
        z = as_int(base(A, Y - y))
        if z is None: return
        for a in irange(1, X - z - 1):
          b = a + z
          # remaining bottom triangles left and right
          (B1, C1) = (area(a, Y - y), area(X - b, Y - y))
          # left mark, (0, c)
          c = as_int(Y - base(A - B1, x))
          if c is None or not(0 < c < Y): continue
          # right mark (X, d)
          d = as_int(Y - base(A - C1, X - x))
          if d is None or not(0 < d < Y): continue
          # top mark (e, 0)
          e = as_int(base(A - area(c, x), y))
          if e is None or not(0 < e < X): continue
          printf("x={x} y={y} -> bottom: {a}, {b}; left: {c}; right: {d}; top: {e}")
      
      # choose a position for the start of the cuts
      for (x, y) in product(irange(1, divf(X - 1, 2)), irange(1, divf(Y - 1, 2))):
        solve(x, y)
      

      Solution: The cuts started from a point 8 cm in from the left edge and 5 cm in from the top edge. The end of cuts were: top = 16 cm from the left; right = 7 cm from the top; bottom = 4 cm and 17 cm from the right; left = 10 cm from the bottom.

      A similar approach can be used to look for situations with 2 cuts on other edges, but these yield no viable solutions.

      The idea of splitting each portion into triangles can be used to show that for any regular polygon, portions (cut from the centre) with equal amounts of the perimeter have equal size.

      Like

      • Frits 10:18 am on 5 June 2021 Permalink | Reply

        @Jim, very clever. I am looking forward to next week (or earlier) when you explain the method you have used.

        Like

    • Frits 9:48 am on 5 June 2021 Permalink | Reply

      Having done most of the work myself.

      # x = distance internal point from left edge
      # y = distance internal point from top edge
      # a = distance top left-hand corner to meeting point on left edge
      # b = distance top left-hand corner to meeting point on top edge
      # c = distance top right-hand corner to meeting point on right edge
      # d = distance bottom left-hand corner to 2nd meeting point on bottom edge
      # e = distance bottom left-hand corner to 1st meeting point on bottom edge
      
      # if we make a triangle with the bottom edge (points e and d) 
      # then the following formula can be derived: (d - e)(13 - y) = 104 = 8 * 13
      #
      # only one value for y is possible.
      
      # with this derived value of y we calculate the areas of the 5 slices
      # and end up with 5 equations and 6 variables
      #
      #  (13 - a)x = 8(13 - e)       (A)
      #  5b + ax = 104               (B)
      #  (20 - x)c = 4 + 5b          (C)
      #  13x + 8d + 20c - cx = 316   (D)
      #  d = 13 + e                  (E)
      
      for a in range(1, 7):                  # (not disclosing y)
        for x in range(1, 10):
          # consider equation B
          ax = a * x
          if ax % 10 not in {4, 9}: continue
          b = (104 - ax) // 5 
          # meeting point with edge is not in the corner
          if b > 19: continue 
         
          # consider equation A
          y = 13 * x - ax
          if y % 8: continue
          
          e = 13 - y // 8
          d = 13 + e
          
          # consider equation C
          (c, r) = divmod(4 + 5 * b, 20 - x)
          if r: continue
          
          # check equation D
          if 13 * x + 8 * d + 20 * c - c * x != 316: continue
          
          # use bogus formula for derived value y (not disclosing y)
          print(f"{x=} y={x-a}, top: {b} right: {c} bottom: {e=} {d=} left: {a}")  
      

      Like

      • Tony Brooke-Taylor 7:53 am on 7 June 2021 Permalink | Reply

        My approach was similar to yours Frits, but I could not satisfy myself by general reasoning that the two cuts had to be on the bottom edge as opposed to the right-hand edge. I therefore tested for the triangle to be on the right-hand edge but this did not produce a valid solution. Therefore the triangle must be on the bottom edge and there is only one solution.

        I got formulae similar to yours by considering parallelograms with missing triangles. Jim’s solution is much more elegant because it divides all the areas into triangles.

        Like

        • Jim Randell 9:31 am on 7 June 2021 Permalink | Reply

          @Tony: I did start by considering the two cuts on different edges, but it turned out they had to be on the bottom.

          As my program didn’t have a neat way to try the alternates, I just removed the dead paths from my program.

          I’ve put a more complete program up as teaser3063x.py on replit.

          from itertools import product
          from enigma import Rational, irange, divf, printf
          
          Q = Rational()
          
          # is rational q an integer?
          as_int = lambda q: (q.numerator if q.denominator == 1 else None)
          
          # dimensions of the rectangle
          (X, Y) = (20, 13)
          
          # area of each portion
          A = Q(X * Y, 5)
          printf("[X={X} Y={Y}; A={A}]")
          
          # calculate area of a triangle with base b and height h
          area = lambda b, h: Q(b * h, 2)
          
          # calculate base of triangle with area A and height h
          base = lambda A, h: Q(2 * A, h)
          
          # find solutions with cuts starting at (x, y)
          def solve(x, y):
            # look for the portion composed of 1 triangle:
          
            # top marks, distance z apart
            z = as_int(base(A, y))
            if z is not None:
              for a in irange(1, X - z - 1):
                b = a + z
                printf("x={x} y={y} -> top: {a}, {b}; ...")
          
            # bottom marks, distance z apart
            z = as_int(base(A, Y - y))
            if z is not None:
              for a in irange(1, X - z - 1):
                b = a + z
                # remaining bottom sections of slices left and right
                (B1, C1) = (area(a, Y - y), area(X - b, Y - y))
                # left mark
                c = as_int(Y - base(A - B1, x))
                if c is None or not(0 < c < Y): continue
                # right mark
                d = as_int(Y - base(A - C1, X - x))
                if d is None or not(0 < d < Y): continue
                # top mark
                e = as_int(base(A - area(c, x), y))
                if e is None or not(0 < e < X): continue
                printf("x={x} y={y} -> bottom: {a}, {b}; left: {c}; right: {d}; top: {e}")
          
            # left marks, distance z apart
            z = as_int(base(A, x))
            if z is not None:
              for a in irange(1, Y - z - 1):
                b = a + z
                printf("x={x} y={y} -> left: {a}, {b}; ...")
          
            # right marks, distance z apart
            z = as_int(base(A, X - x))
            if z is not None:
              for a in irange(1, Y - z - 1):
                b = a + z
                # remaining sections of right slices above and below
                (B1, C1) = (area(a, X - x), area(Y - b, X - x))
                # top mark
                c = as_int(X - base(A - B1, Y - y))
                if c is None or not(0 < c < X): continue
                # bottom mark
                d = as_int(X - base(A - C1, Y - y))
                if d is None or not(0 < d < X): continue
                printf("x={x} y={y} -> right: {a}, {b}; top={c}; bottom={d}; ...")
          
          # choose a position for the start of the cuts
          for (x, y) in product(irange(1, divf(X - 1, 2)), irange(1, divf(Y - 1, 2))):
            solve(x, y)
          

          Like

  • Jim Randell 4:37 pm on 7 May 2021 Permalink | Reply
    Tags: by: Colin Vout   

    Teaser 3059: Nine blocks to the diner 

    From The Sunday Times, 9th May 2021 [link]

    “Sure, I can help. From this hotel it’s nine blocks to the diner; from there it’s five blocks to the library, and then six blocks back here. I guess instead you could come back from the diner to the museum — that’s four blocks — and then seven blocks back here. Or three blocks to the gallery and then eight blocks back here.”

    “So the diner’s straight along here?”

    “No sir, it’s not straight along one road for any of these trips; I just meant so many edges of blocks. The city’s on a square grid, and all these places are on corners, but, fact is, none of them is on the same street or avenue as any other one.”

    How many blocks between the library and the museum, museum and gallery, and gallery and library?

    [teaser3059]

     
    • Jim Randell 5:28 pm on 7 May 2021 Permalink | Reply

      Here’s a quick solution using the [[ SubstitutedExpression ]] solver from the enigma.py library. It runs in 127ms.

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      # suppose:
      #   (X, Y) = hotel
      #   (A, B) = diner
      #   (C, D) = library
      #   (E, F) = museum
      #   (G, H) = gallery
      
      SubstitutedExpression
      
      --digits="0-7" # smallest grid with solutions
      
      # each location has x, y co-ordinates different from all the other locations
      --distinct="ACEGX,BDFHY"
      
      # distance metric (work around PEP 3113)
      --code="dist = ulambda('(a, b), (x, y): abs(a - x) + abs(b - y)')"
      
      # 9 blocks from hotel (X, Y) to diner (A, B)
      "dist((X, Y), (A, B)) = 9"
      
      # 5 blocks from diner (A, B) to library (C, D)
      "dist((A, B), (C, D)) = 5"
      
      # 6 blocks from library (C, D) to hotel (X, Y)
      "dist((C, D), (X, Y)) = 6"
      
      # 4 blocks from diner (A, B) to museum (E, F)
      "dist((A, B), (E, F)) = 4"
      
      # 7 blocks museum (E, F) to hotel (X, Y)
      "dist((E, F), (X, Y)) = 7"
      
      # 3 blocks from diner (A, B) to gallery (G, H)
      "dist((A, B), (G, H)) = 3"
      
      # 8 blocks from gallery (G, H) to hotel (X, Y)
      "dist((G, H), (X, Y)) = 8"
      
      # eliminate some duplication
      "min(A, C, E, G, X) = 0"
      "min(B, D, F, H, Y) = 0"
      
      # answer is the distances between:
      #   library (C, D) and museum (E, F)
      #   museum (E, F) and gallery (G, H)
      #   gallery (G, H) and library (C, D)
      --answer="(dist((C, D), (E, F)), dist((E, F), (G, H)), dist((G, H), (C, D)))"
      
      # [optional] tidy up output
      --template="(X, Y) (A, B) (C, D) (E, F) (G, H)"
      --solution=""
      

      Solution: It is 7 blocks from the library to the museum. It is 7 blocks from the museum to the gallery. It is 4 blocks from the gallery to the library.

      Here is a possible layout:

      Reflections and rotations of this layout also provide viable solutions, to give the 8 different layouts found by the program.

      Like

      • Jim Randell 7:00 pm on 7 May 2021 Permalink | Reply

        And here is a standalone Python program that finds the same solution. It runs in 54ms.

        Run: [ @replit ]

        from collections import namedtuple
        from enigma import (irange, multiset, printf)
        
        # x/y coordinates
        P = namedtuple('P', 'x y')
        
        # distance metric between 2 points
        def dist(p, q):
          return abs(p.x - q.x) + abs(p.y - q.y)
        
        # generate positions at a distance d from point p
        def position(d, p):
          for dx in irange(0, d):
            dy = d - dx
            yield P(p.x + dx, p.y + dy)
            yield P(p.x + dx, p.y - dy)
            yield P(p.x - dx, p.y + dy)
            yield P(p.x - dx, p.y - dy)
        
        # check x/y co-ordinates are distinct
        def check(p, *qs):
          return all(p.x != q.x and p.y != q.y for q in qs) 
        
        # record solutions
        r = multiset()
        
        # fix the diner at (0, 0)
        D = P(0, 0)
        
        # the gallery is 3 blocks from the diner
        for G in position(3, D):
          if not check(G, D): continue
        
          # the hotel is 8 blocks from the gallery ...
          for H in position(8, G):
            if not check(H, G, D): continue
            # ... and 9 blocks from the diner
            if not (dist(H, D) == 9): continue
            
            # the museum is 4 blocks from the diner ...
            for M in position(4, D):
              if not check(M, H, G, D): continue
              # ... and 7 blocks from the hotel
              if not (dist(M, H) == 7): continue
        
              # the libray is 5 blocks from the diner ...
              for L in position(5, D):
                if not check(L, M, H, G, D): continue
                # ... and 6 blocks from the hotel
                if not (dist(L, H) == 6): continue
        
                # calculate the required distances
                ds = (dist(L, M), dist(M, G), dist(G, L))
        
                printf("[ds={ds}; D={D} G={G} H={H} M={M} L={L}]")
                r.add(ds)
        
        # output solution
        for (ds, n) in r.most_common():
          printf("ds = {ds} [{n} solutions]")
        

        The program fixes D at (0, 0) and then looks for possible positions for G at a distance of 3. There are 8 viable positions (think knight moves), and each layout corresponds to one of these positions. So we can eliminate multiple solutions by only considering just one viable position for G.

        Like

    • Tony Brooke-Taylor 1:26 pm on 9 May 2021 Permalink | Reply

      I saved a bit of time by constraining the diner to be in one quadrant relative to the hotel, and the other three destinations to be in either that quadrant or the two adjacent. This still gives two solutions by reflection in y=x but of course all solutions that meet the puzzle’s conditions are identical.

      Like

  • Jim Randell 8:11 pm on 9 April 2021 Permalink | Reply
    Tags: by: Colin Vout   

    Teaser 3055: Proceed to checkout 

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

    The dartboard at the Trial and Arrow pub is rather different from the standard one: there are only 3 sectors, each with a positive whole number label, and no central bullseye scoring region. There are still double and treble rings: for instance, if the sector label is 3, a dart in that sector can score 3, 6 or 9.

    As usual, scores are counted down from a starting value, the idea being to finish (“check out”) by reaching exactly zero. Players take turns throwing three darts, or fewer if they check out before that. Unusually, the checkout doesn’t have to finish on a double.

    The lowest impossible checkout is the smallest value that can’t be achieved in one turn; on this board that value is 36.

    What are the sector labels?

    [teaser3055]

     
    • Jim Randell 8:42 pm on 9 April 2021 Permalink | Reply

      (See also: Puzzle #06).

      In order to have a score of 1 there must be a “1” sector. This Python program considers sets of three sectors of the form (1, a, b), and calculates the lowest score not achievable with 3 darts, until it finds a value of 36. It runs in 54ms.

      Run: [ @replit ]

      from enigma import union, subsets, irange, inf, peek, printf
      
      # find the lowest score not achievable with k darts and values vs
      def lowest(vs, k):
        # scores with 1 dart
        scores = union((v, 2 * v, 3 * v) for v in vs)
        # scores with up to k darts
        ss = set(sum(s) for s in subsets(scores, max_size=k, select="R"))
        # find the lowest score that cannot be made
        return peek(n for n in irange(0, inf) if n not in ss)
      
      # find 3 sectors with lowest impossible score of x
      def solve(x, k=3):
        # consider sectors [1, a, b], where a + b = t
        for t in irange(5, inf):
          for a in irange(2, (t - 1) // 2):
            vs = [1, a, t - a]
            if lowest(vs, k) == x:
              yield vs
      
      for vs in solve(36):
        printf("sectors = {vs}")
        break
      

      Solution: The sector labels are: 1, 5, 22.

      Like

    • Frits 3:08 pm on 10 April 2021 Permalink | Reply

      from enigma import SubstitutedExpression
      from itertools import combinations_with_replacement
      
      # find the lowest score not achievable with 3 darts
      # only consider values less equal to <n>
      def low(vs, n):
        s = {p for v in vs for i in range(1, 4) if (p := v * i) <= n}
        s = set(su if (su := sum(c)) <= n else 0
                   for c in combinations_with_replacement(s, 3))
                  
        for x in range(10, n + 1):
          if x not in s:
            return x
      
        return 99      # high number
      
      p = SubstitutedExpression(
        [
         # look for sectors [1, X, YZ], Y >= X
         # X < 11 as otherwise 10 will be the lowest impossible checkout
        
         # with 2 sectors [1, X] we can never make number Y = 6X + 4
         # with 2 sectors [1, X] we can't make number Y = 4X + 4 unless X < 5
         "YZ < 4 * X + 5 + (X < 5) * 2 * X",
       
         "YZ > max(X, 4)",                # max total [1, X, YZ] >= 35
      
         # The lowest impossible checkout is 36
         "low([1, X, YZ], 36) == 36",
        ],
        answer="1, X, YZ",
        # exclude X = 4, 6 and 9 as they are factors of 36
        # exclude X = 7 as 5 * 7 + 1 = 36
        # exclude X = 10 as 3 * 10 + 6 * 1 = 36
        # highest value for Y is 2 (as of YZ = 30 you can make 36)
        d2i=dict([(0, "X")] + [(1, "X")] + [(3, "Y")] + [(4, "YX")] + [(5, "Y")] +
        [(k, "YX") for k in range(6, 8)] +
        [(8, "Y")] +
        [(9, "YX")]),
        env=dict(low=low),
        distinct="",   # allow variables with same values
        reorder=0,
        verbose=0,
      )
      
      # print answer
      for (_, ans) in p.solve():
        print(f"The sectors are: {ans}")
      

      Like

    • Frits 9:04 pm on 12 April 2021 Permalink | Reply

      # sector candidates which can go with 1 without immediately making 36 
      cands = [X for X in range(2, 36) if X * 9 != 36 and
               not any((29 if i < 4 else 32) < X * i < 37 for i in range(1, 7))]  
      
      # consider the 2nd sector, it must be less than 11 
      # as otherwise 10 will be the lowest impossible checkout
      for X in [c for c in cands if c < 11]:
        one = [0, 1, 2, 3, X, 2 * X, 3 * X]
        two = {o1 + o2 for o1 in one for o2 in one}   
        
        mi = max(5, X + 1)
        # determine lowest score which can't be made with 3 darts in sectors [1, X]
        if X > 7:
          ma = 15 + (X - 8)
        elif X > 4:  
          ma = 4 * X + 4
        else:
          ma = 6 * X + (4 if 4 % X else 5) 
        
        # one dart in sector Y
        candsY = [Y for Y in cands if mi <= Y <= ma and 
                  all(36 - i not in two for i in [Y, 2 * Y, 3 * Y])]
        
        # two darts in sector Y scoring at least 4 * Y
        candsY = [Y for Y in candsY if
                  all(36 - i not in one for i in [4 * Y, 5 * Y, 6 * Y])]
        
        # if X > 2 and Y > 18 then number Y + 3 * X + 4 is no checkout
        candsY = [Y for Y in candsY if X == 2 or Y < 18 or Y + 3 * X + 4 > 35]   
        
        if candsY:
          three = {t + o for t in two for o in one}  
          remaining = [x for x in range(ma, 36) if x not in three]  
         
        for Y in candsY:
          if all(r - Y in two for r in remaining):
            print(f"The sectors are: 1, {X} and {Y}")
      

      Like

  • Jim Randell 4:57 pm on 12 March 2021 Permalink | Reply
    Tags: by: Colin Vout   

    Teaser 3051: Shipping forecast 

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

    “Here is the shipping forecast for the regions surrounding our island.

    First, the coastal regions:

    Hegroom: E 6, rough, drizzle, moderate.
    Forkpoynt: E 7, rough, rain, good.
    Angler: NE 7, rough, drizzle, moderate.
    Dace: NE 7, smooth, drizzle, moderate.

    Now, the offshore regions:

    Back: E gale 8, rough, rain, moderate.
    Greigh: E 7, smooth, drizzle, poor.
    Intarsia: SE 7, rough, drizzle, moderate.
    Catter: E gale 8, high, drizzle, moderate.
    Eighties: E 7, rough, fair, good.”

    In this forecast, no element jumps from one extreme to another between adjacent regions.

    The extremes are:

    wind direction: SE & NE;
    wind strength: 6 & gale 8;
    sea state: smooth & high;
    weather: fair & rain;
    visibility: good & poor.

    Each region adjoins four others (meeting at just one point doesn’t count).

    Which of the regions does Angler touch?

    [teaser3051]

     
    • Jim Randell 10:37 pm on 12 March 2021 Permalink | Reply

      (You might like to work out which sea areas this puzzle is spoofing [ @wikipedia ]).

      It took me a bit of doodling to come up with a map of the sea areas that satisfied the description. (I’ll put up a diagram of it later – [link]). But once that is done the program is relatively straightforward.

      I don’t know that it is the only possible map though, but I assume the setter must have checked that the any viable map will give the same solution.

      This Python program runs in 58ms.

      Run: [ @replit ]

      from enigma import (subsets, update, peek, join, map2str, printf)
      
      # suppose the coastal regions are: 0, 1, 2, 3
      # and the offshore regions are: 4, 5, 6, 7, 8
      
      # the adjacency map
      adj = [
        (1, 3, 6, 8), # 0
        (0, 2, 4, 6), # 1
        (1, 3, 4, 5), # 2
        (0, 2, 5, 8), # 3
        (1, 2, 6, 7), # 4
        (2, 3, 7, 8), # 5
        (0, 1, 4, 7), # 6
        (4, 5, 6, 8), # 7
        (0, 3, 5, 7), # 8
      ]
      
      # the forecast, region -> (dir, str, sea, wea, vis)
      forecast = dict(
        # coastal
        H=('E', 6, 'rough', 'drizzle', 'moderate'),
        F=('E', 7, 'rough', 'rain', 'good'),
        A=('NE', 7, 'rough', 'drizzle', 'moderate'),
        D=('NE', 7, 'smooth', 'drizzle', 'moderate'),
        # offshore
        B=('E', 8, 'rough', 'rain', 'moderate'),
        G=('E', 7, 'smooth', 'drizzle', 'poor'),
        I=('SE', 7, 'rough', 'drizzle', 'moderate'),
        C=('E', 8, 'high', 'drizzle', 'moderate'),
        E=('E', 7, 'rough', 'fair', 'good'),
      )
      
      # extremes (in the same order)
      extreme = ({'SE', 'NE'}, {6, 8}, {'smooth', 'high'}, {'fair', 'rain'}, {'good', 'poor'})
      
      # check forecast for <k> can be placed at region <r> without giving an extreme pair
      # return an updated map, or None
      def check(k, r, m):
        for (i, (v0, xs)) in enumerate(zip(forecast[k], extreme)):
          # is there an extreme in the forecast?
          if v0 in xs:
            # check the other extreme is not in any adjacent areas
            for r1 in adj[r]:
              s = m.get(r1, None)
              if s:
                v1 = forecast[s][i]
                if v1 != v0 and v1 in xs: return None
        # looks good, map r -> k
        return update(m, [(r, k)])
      
      # attempt to map regions <rs> to keys <ks>
      def assign(rs, ks, m):
        for (r, k) in zip(rs, ks):
          m = check(k, r, m)
          if m is None: break
        return m
      
      # assign the coastal regions (0, 1, 2, 3) -> "ADFH"
      for ks in subsets("ADFH", size=len, select="P"):
        m0 = assign((0, 1, 2, 3), ks, dict())
        if m0 is None: continue
      
        # assign the offshore regions (4, 5, 6, 7, 8) -> "CBEGI"
        for ks in subsets("CBEGI", size=len, select="P"):
          m = assign((4, 5, 6, 7, 8), ks, m0)
          if m is None: continue
      
          # which region is A?
          r = peek(k for (k, v) in m.items() if v == 'A')
      
          # output the regions adjacent to A
          adjA = sorted(m[x] for x in adj[r])
          printf("adj[A] = {adjA} {m}", adjA=join(adjA, sep=",", enc="()"), m=map2str(m, arr="->", enc="[]"))
      

      Solution: Angler adjoins Catter, Eighties, Forkpoynt, Hegroom.

      The program finds 4 ways to assign the areas to regions of the map. But the map can be drawn to have two axes of symmetry, so there is essentially only one solution (and the other 3 found are just reflections of this).


      My initial stetch, with the required connectivity looked like this:

      Which I redrew using straight lines to get this map:

      Which I think looks more like a map of sea areas. (The point where areas 2, 4, 5, 7 meet could be small outcrop with a lighthouse perhaps).

      But it is topologically equivalent to the following diagram, which has horizontal and vertical symmetry:

      The four solutions found by the program correspond to the reflections of a single solution:

      Like

      • Jim Randell 10:18 am on 21 March 2021 Permalink | Reply

        I think the derivations of the sea areas are:

        Angler → Fischer
        Back → Forth
        Catter → Dogger
        Dace → Sole
        Eighties → Forties
        Forkpoynt → Tyne
        Greigh → Wight
        Hegroom → Hebrides
        Intarsia → Fair Isle [knitting]

        Like

      • Tony Brooke-Taylor 1:19 pm on 17 April 2021 Permalink | Reply

        I was curious about the possibility of other viable maps giving different solutions (and cross that I did not come up with the map that seems to work). Several weeks and a crash-course in graph theory later, I developed a routine that generates all possible combinations of 18 allowed borders and then applies constraints until it produces a unique solution. My conclusions are as follow:

        Combinations of 18 from the set of 26 allowed borders gives a long-list of 1562275 possibilities.

        Only 564 of these contain all 9 regions with 4 borders each.

        Only 9 of these are planar. I used Pyladder, which is a Python implementation of the graph planarity algorithm sourced from ‘Efficient Planarity Testing’ by John Hopcroft and Robert Tarjan. See https://github.com/haraldujc/pyladder

        As far as I can see, there is no reason why any of these 9 might not, in principle, be valid. They do not all give the same result for Angler. However, if we apply a couple more constraints to the coastal regions, we do get Jim’s solution uniquely:
        1 – one of the 9 only has 2 coastal-coastal borders, so the ‘island’ would be two islands.
        2 – only one of the 9 has exactly 2 coastal borders per coastal region. All of the others have at least one coastal region with either 1 or 3 coastal borders. If we assume that the coastal regions represent quadrants of the island (which makes sense) then they will indeed have two coastal neighbours each. Hence the unique solution has that form.

        Like

        • Jim Randell 10:24 am on 21 April 2021 Permalink | Reply

          @Tony:

          Interesting. I did wonder if there was a programmatic way to generate viable graphs in order to show uniqueness (or otherwise).

          I had a brief tussle with planar graphs when solving Enigma 1035.

          Like

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

          Having been looking at packages to manipulate graphs for Teaser 3083, I thought I’d revisit this problem.

          I wrote a Python program to generate all possible potential graphs, and output them in “graph6” format. I saved this to a file, so I could use the “nauty” tools on it. [ link ]

          The graphs generated have nodes 0-3 as the coastal regions, and nodes 4-8 are the off-shore regions. We generate all possible graphs with 4 connections between each of the nodes to give us a viable adjacency graph for the regions, but then add in an additional region to represent the island (9), which is adjacent to all 4 of the coastal regions.

          This program takes 7m22s to generate all possible graphs.

          from enigma import (subsets, ordered)
          
          # generate graphs with each node connected to K others
          def generate(K, ns, g=set()):
            # are we done?
            if not ns:
              yield g
            else:
              # deal with the next node
              n = ns[0]
              k = sum(n in x for x in g)
              if k <= K:
                # choose K - k edges to add
                ns_ = ns[1:]
                for xs in subsets(ns_, size=K - k):
                  yield from generate(K, ns_, g.union(ordered(n, x) for x in xs))
          
          # "graph6" format for a graph (edge list) 
          import networkx as nx
          def graph6(g):
            g6 = nx.to_graph6_bytes(nx.Graph(g), header=0)
            return g6.decode(encoding="ascii").rstrip()
          
          # generate graphs:
          #   0, 1, 2, 3: are the 4 coastal regions
          #   4, 5, 6, 7, 8: are the off-shore regions
          for g in generate(4, [0, 1, 2, 3, 4, 5, 6, 7, 8]):
            # add in edges from the coastal regions to the island (9)
            g.update([(0, 9), (1, 9), (2, 9), (3, 9)])
            # output in graph6 format
            print(graph6(g))
          

          And we can process the list of generated graphs as follows:

          # generate the graphs, and save those that are isomorphically distinct
          % python3 teaser3051g.py | shortg > graphs3051.g6 
          1024380 graphs read from stdin
          494 graphs written to stdout
          
          # find which of them are planar
          % planarg graphs3051.g6 | showg
          494 graphs read from graphs3051.g6, 1 written to stdout; 0.01 sec.
          
          Graph 1, order 10.
            0 : 1 2 3 4;
            1 : 0 2 6 7;
            2 : 0 1 6 8;
            3 : 0 4 7 9;
            4 : 0 3 8 9;
            5 : 6 7 8 9;
            6 : 1 2 5 7 8;
            7 : 1 3 5 6 9;
            8 : 2 4 5 6 9;
            9 : 3 4 5 7 8;
          

          (Or without the intermediate file, just run: [[ python3 teaser3051g.py | shortg | planarg | showg ]]).

          The initial 1024380 generated graphs are reduced to a set of 494 isomorphically different graphs, and only 1 of these is planar.

          From the output we see that nodes 6-9 are the coastal regions, and 5 is the island itself, so 0-4 are the off-shore regions.

          And if we take my diagram and relabel it as follows:

          We see that the graph corresponds to the adjacency matrix that I started with, and this is the only possible layout.

          Like

    • Frits 1:39 pm on 14 March 2021 Permalink | Reply

      Without diagram or explanation of analysis (no permission was given).
      Same results as Jim (using same adjacency map).

      from itertools import permutations
      
      regions = "HFADBGICE"
      d = dict()
      
      # coastal regions       low/mid/high = 1/2/3
      d["H"] = [2, 1, 2, 2, 2]
      d["F"] = [2, 2, 2, 3, 1]
      d["A"] = [3, 2, 2, 2, 2]
      d["D"] = [3, 2, 1, 2, 2]
      
      # offshore regions      low/mid/high = 1/2/3
      d["B"] = [2, 3, 2, 3, 2]
      d["G"] = [2, 2, 1, 2, 3]
      d["I"] = [1, 2, 2, 2, 2]
      d["C"] = [2, 3, 3, 2, 2]
      d["E"] = [2, 2, 2, 1, 1]     
      
      # the adjacency map             credit: Jim Randell
      adj = [
        (1, 3, 6, 8), # 0
        (0, 2, 4, 6), # 1
        (1, 3, 4, 5), # 2
        (0, 2, 5, 8), # 3
        (1, 2, 6, 7), # 4
        (2, 3, 7, 8), # 5
        (0, 1, 4, 7), # 6
        (4, 5, 6, 8), # 7
        (0, 3, 5, 7), # 8
      ]
      
      # generate "not bordering" dictionary
      nb = {r: [] for r in regions}             # init dictionary      
      for i, r1 in enumerate(regions): 
        for j, r2 in enumerate(regions): 
          if j == i: continue
          # check for opposite extremes
          if any(x * y == 3 for (x, y) in zip(d[r1], d[r2])):
            nb[r1] += [r2]
            
      # check which region can be the outer region
      outer = [r for r in regions[4:] 
                if not any(x for x in nb[r] if x in regions[4:])] 
                
      if len(outer) == 1:
        outer = outer[0]
        cdict = {outer: 7}
      else:
        outer = ""
        cdict = {}
      
      # check offshore regions (except outer)
      for p in permutations("BCEGI".replace(outer, "")):
        o2no = dict(zip(p, (4, 5, 6, 8)))
        
        # regions 4, 6 share a border
        if p[0] in nb[p[2]]: continue     
        
        # regions 5, 8 share a border
        if p[1] in nb[p[3]]: continue
        
        # check coastal regions
        for q in permutations("ADFH"):
          c2no = dict(zip(q, (0, 1, 2, 3)))
        
          # F shares a border with A, also D and H have to share a border
          if q[0] + q[2] in {"AF", "FA", "DH", "HD"} : continue
          
          # A and D don't share a border
          if abs(c2no["A"] - c2no["D"]) != 2: continue
          
          # C shares a border with A
          if c2no["A"] not in adj[o2no["C"]]: continue
       
          # B doesn't share a border with A 
          if c2no["A"] in adj[o2no["B"]]: continue
          
          # B doesn't share a border with H
          if c2no["H"] in adj[o2no["B"]]: continue
          
          # C doesn't share a border with H
          if c2no["H"] in adj[o2no["C"]]: continue
          
          # merge dictionaries (not using | as PyPy doesn't support it yet)
          comb = {**o2no, **c2no, **cdict}
          
          print("".join(k for k, v in comb.items() if v in adj[c2no["A"]]), 
                end = ": ")
          print(", ".join(str(v) + "->" + k 
                for k, v in sorted(comb.items(), key=lambda x: x[1])))
      

      Like

    • Tony Brooke-Taylor 11:32 am on 19 March 2021 Permalink | Reply

      I’ve spent hours trying to find a unique solution: manually (found a solution but could not prove unique), and with two entirely different approaches to looping and eliminating possibilities. However, I did not try a map that allowed one of the offshore regions to surround the entire space. Without allowing that, the only map I found topologically possible yielded three solutions. Oh well, I can console myself that my objective is to learn Python, not to second-guess problem-setters 🙂

      Like

  • Jim Randell 5:02 pm on 22 January 2021 Permalink | Reply
    Tags: by: Colin Vout   

    Teaser 3044: Building blocks 

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

    The kids had used all the blocks each of them owned (fewer than 100 each) to build triangular peaks — one block on the top row, two on the next row, and so on.

    “My red one’s nicer!”

    “My blue one’s taller!”

    “Why don’t you both work together to make one bigger still?” I said.

    I could see they could use all these blocks to make another triangle.

    This kept them quiet until I heard, “I bet Dad could buy some yellow blocks to build a triangle bigger than either of ours was, or a red and yellow triangle, or a yellow and blue triangle, with no blocks ever left over.”

    This kept me quiet, until I worked out that I could.

    How many red, blue and yellow blocks would there be?

    [teaser3044]

     
    • Jim Randell 5:18 pm on 22 January 2021 Permalink | Reply

      The following Python program runs in 43ms.

      Run: [ @repl.it ]

      from enigma import tri, irange, inf, first, subsets, is_triangular, printf
      
      # generate triangular numbers from tri(a) to tri(b)
      tris = lambda a=1, b=inf: (tri(i) for i in irange(a, b))
      
      def solve():
        # collect triangular numbers less than 100
        ts = first(tris(), (lambda x: x < 100))
      
        # choose (R, B) pairs that sum to another triangular number
        RBs = list(s for s in subsets(ts, size=2) if is_triangular(sum(s)))
      
        # consider values for Y
        for Y in tris(is_triangular(min(B for (R, B) in RBs)) + 1):
          # look for R, B pairs that work with Y
          for (R, B) in RBs:
            if B < Y and is_triangular(R + Y) and is_triangular(B + Y):
              yield (R, B, Y)
      
      # look for the first solution
      for (R, B, Y) in solve():
        printf("R={R} B={B} Y={Y}")
        break
      

      Solution: There were 45 red blocks; 91 blue blocks; 990 yellow blocks.

      We have:

      R = 45 = T(9)
      B = 91 = T(13)
      R + B = 136 = T(16)

      Y = 990 = T(44)
      R + Y = 1035 = T(45)
      B + Y = 1081 = T(46)


      It makes me wish Python allowed something like a [[ while ... ]] clause in list comprehensions, so they could be terminated early:

      ts = (t for t in tris() while t < 100)
      

      This exact syntax was actually proposed [ PEP 3142 ], but not implemented.

      I’ve folded the functionality into the [[ first() ]] function in the enigma.py library, so it can take a function and collection of items will stop when the function returns a false value for an item.

      Like

      • Frits 11:11 pm on 22 January 2021 Permalink | Reply

        @Jim, I can imagine a similar puzzle in 3D. Didn’t we have such a puzzle before?

        Like

      • Jim Randell 10:58 am on 23 January 2021 Permalink | Reply

        Here’s an exhaustive version, based on the observation that if Y = tri(y) then R ≥ y + 1, otherwise it will not be possible to complete an additional row of the Y triangle using R blocks.

        It still runs in 46ms.

        Run: [ @repl.it ]

        from enigma import tri, irange, inf, first, subsets, is_triangular, printf
        
        # generate triangular numbers from tri(a) to tri(b)
        tris = lambda a=1, b=inf: (tri(i) for i in irange(a, b))
        
        # collect triangular numbers less than 100
        ts = first(tris(), (lambda x: x < 100))
        
        # choose (R, B) pairs that sum to another triangular number
        for (R, B) in subsets(ts, size=2):
          if not is_triangular(R + B): continue
        
          # consider values for Y
          for Y in tris(is_triangular(B) + 1, R - 1):
            if is_triangular(R + Y) and is_triangular(B + Y):
              printf("R={R} B={B} Y={Y}")
        

        This code can also be used to explore larger solutions by increasing the limit at line 7.

        There is 1 further solution below 1275:

        R = T(23) = 276
        B = T(30) = 465
        Y = T(90) = 4095

        Like

    • Frits 10:55 pm on 22 January 2021 Permalink | Reply

      Nothing has been implemented regarding upper limits of RE and BL, the program runs fast enough (between 31 ms and 46 ms).

      from enigma import SubstitutedExpression 
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
        # number of reds    = RE * (RE + 1)/2
        # number of blues   = BL * (BL + 1)/2
        # number of yellows = YW * (YW + 1)/2
        "RE > 0",
        "BL > 0", 
        
        # My blue one's taller
        "BL > RE",
        
        # fewer than 100 each
        "BL * (BL + 1) // 2 < 100",
        
        # they could use all these blocks to make another triangle
        "RE * (RE + 1) // 2 + BL * (BL + 1) // 2 == JK * (JK + 1) // 2",
        
        # Dad could buy some yellow blocks to build a triangle bigger 
        # than either of ours was, or a red and yellow triangle, 
        # or a yellow and blue triangle, with no blocks ever left over
        "YW > BL",
        
        "YW * (YW + 1) // 2 + RE * (RE + 1) // 2 == CD * (CD + 1) // 2",
        "YW * (YW + 1) // 2 + BL * (BL + 1) // 2 == FG * (FG + 1) // 2",
        
        ],
        answer="RE * (RE + 1) // 2, BL * (BL + 1) // 2, YW * (YW + 1) // 2",
        distinct="",
        reorder=0,
        d2i={},
        verbose=0)   
      
      for (_, ans) in p.solve():
        print(f"{ans}")
      

      Like

      • Frits 8:52 am on 23 January 2021 Permalink | Reply

        Similar.

        from enigma import SubstitutedExpression, is_square 
        
        # the alphametic puzzle
        p = SubstitutedExpression(
          [
          # If n is the mth triangular number, then n = m*(m+1)/2
          # and m = (sqrt(8n+1) - 1) / 2
        
          # number of reds    = RE * (RE + 1)/2
          # number of blues   = BL * (BL + 1)/2
          # number of yellows = YW * (YW + 1)/2
          "RE > 0",
          "BL > 0", 
          
          # My blue one's taller
          "BL > RE",
          
          # fewer than 100 each
          "BL * (BL + 1) // 2 < 100",
          
          # they could use all these blocks to make another triangle
          "is_square(4 * (BL * (BL + 1) + RE * (RE + 1)) + 1)",
          
          # Dad could buy some yellow blocks to build a triangle bigger 
          # than either of ours was, or a red and yellow triangle, 
          # or a yellow and blue triangle, with no blocks ever left over
          "YW > BL",
          
          "is_square(4 * (YW * (YW + 1) + RE * (RE + 1)) + 1)",
          "is_square(4 * (YW * (YW + 1) + BL * (BL + 1)) + 1)",
          
          ],
          answer="RE * (RE + 1) // 2, BL * (BL + 1) // 2, YW * (YW + 1) // 2",
          distinct="",
          reorder=0,
          d2i={},
          verbose=0)   
        
        for (_, ans) in p.solve():
          print(f"{ans}")
        

        Like

      • Frits 10:53 am on 23 January 2021 Permalink | Reply

        One (ugly) statement, no imports.

        The “is_square” method “n**.5 % 1 == 0” will fail for large numbers of n (like 152415789666209426002111556165263283035677490).

        print([(r * (r + 1) // 2, b * (b + 1) // 2, y * (y + 1) // 2) 
          # Triangular root <m> of n = m*(m+1)/2  is (sqrt(8n+1) - 1) / 2
          # combinations of red and blue triangular roots and number of blocks < 100
          for (r, b) in [(c1, c2) 
            for c1 in range(1, [m for m in range(1, 50) if m * (m + 1)> 198][0] - 1) 
            for c2 in range(c1 + 1, [m for m in range(1, 50) if m * (m + 1)> 198][0]) 
            # they could use all these blocks to make another triangle
            if (4 * (c1 * (c1 + 1) + c2 * (c2 + 1)) + 1)**.5 % 1 == 0] 
          for y in range(b + 1, 99) 
          # red and yellow triangle, with no blocks ever left over
          # blue and yellow triangle, with no blocks ever left over
          if (4 * (r * (r + 1) + y * (y + 1)) + 1)**.5 % 1 == 0 and
             (4 * (b * (b + 1) + y * (y + 1)) + 1)**.5 % 1 == 0])  
        

        Like

        • Frits 12:44 pm on 23 January 2021 Permalink | Reply

          [m for m in range(1, 50) if m * (m + 1)> 198][0]
          

          can be achieved more efficiently (probably) by:

          next(filter(lambda m: m * (m + 1)> 198, range(1, 50)))
          

          Like

  • Jim Randell 4:56 pm on 8 January 2021 Permalink | Reply
    Tags: by: Colin Vout   

    Teaser 3042: A question of scale 

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

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

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

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

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

    What was Skaredahora’s favourite scale?

    [teaser3042]

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

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

      This Python program runs in 45ms.

      Run: [ @repl.it ]

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

      Solution: Skaredahora’s favourite scale is 100010101110.

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

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

      There are also 12 possible scales starting with 0.

      Like

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

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

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

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

        Run: [ @repl.it ]

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

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

        Like

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

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

          Like

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

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

      Like

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

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

        Like

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

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

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

      Like

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

        check5 can also be written as:

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

        Like

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

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

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

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

      Like

  • Jim Randell 1:54 pm on 27 November 2020 Permalink | Reply
    Tags: by: Colin Vout   

    Teaser 3036: That old chestnut 

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

    Clearing out an old drawer I found a wrinkled conker. It was my magnificent old 6709-er, a title earned by being the only survivor of a competition that I had had with friends. The competition had started with five conkers, veterans of many campaigns; each had begun at a different value between 1300 and 1400.

    We used the rule that if an m-er beat an n-er in an encounter (by destroying it, of course!) the m-er would become an m+n+1-er; in effect, at any time the value of a conker was the number of destroyed conkers in all confrontations in its “ancestry”.

    I recall that at the beginning of, and throughout, the competition, the value of every surviving conker was a prime number.

    What were the values of the five conkers at the start?

    [teaser3036]

     
    • Jim Randell 2:10 pm on 27 November 2020 Permalink | Reply

      There are 5 conkers (with values, say A, B, C, D, E), and there are 4 matches where one conker is destroyed in each match. The ultimate winner ending up with a value of (A + B + C + D + E + 4), and we know this value is 6079.

      This Python 3 program runs in 49ms.

      from enigma import Primes, subsets, printf
      
      # target for the champion
      T = 6709
      
      # for checking primes
      primes = Primes(T)
      
      # play values against each other until there is an ultimate winner
      def solve(vs, ss=[]):
        # are we done?
        if len(vs) == 1:
          yield ss
        # choose 2 conkers to play
        for ((i, m), (j, n)) in subsets(enumerate(vs), size=2):
          v = m + n + 1
          if v in primes:
            yield from solve(vs[:i] + vs[i + 1:j] + vs[j + 1:] + [v], ss + [(m, n)])
            
      
      # choose 5 initial primes values between 1300 and 1400
      for vs in subsets(primes.irange(1300, 1400), size=5):
        if sum(vs) + 4 != T: continue
        # check for a possible sequence of matches
        for ss in solve(list(vs)):
          # output solution
          printf("{vs} -> {ss}")
          break # we only need one possibility
      

      Solution: The values of the five starting conkers were: 1301, 1303, 1361, 1367, 1373.

      The conkers are:

      A = 1301
      B = 1303
      C = 1361
      D = 1367
      E = 1373

      And one possible sequence of matches is:

      A vs C → AC = 2663
      D vs E → DE = 2741
      AC vs B → ABC = 3967
      ABC vs DE → ABCDE = 6709

      An alternative sequence is:

      B vs E → BE = 2677
      C vs D → CD = 2729
      BE vs CD → BCDE = 5407
      A vs BCDE → ABCDE = 6709

      Note that by selecting pairs of conkers for battle by index (rather than value) we ensure that the program works even if more than one conker has the same value. It turns out that in the solution sequence all the conkers do have different values, so it is possible to get the correct answer with a less rigorous program.

      Like

      • Jim Randell 12:49 pm on 14 December 2020 Permalink | Reply

        Here’s a solution using [[ multiset() ]] from the enigma.py library, which is a bit neater than using indices (and also more efficient).

        This Python 3 program runs in 44ms.

        from enigma import Primes, subsets, multiset, ordered, printf
        
        # target for the champion
        T = 6709
        
        # for checking primes
        primes = Primes(T)
        
        # play values against each other until there is an ultimate winner
        def solve(vs, ss=[]):
          # are we done?
          if len(vs) == 1:
            yield ss
          # choose 2 conkers to play
          for (m, n) in subsets(vs, size=2, select="mC"):
            v = m + n + 1
            if v in primes:
              yield from solve(vs.difference((m, n)).add(v), ss + [ordered(m, n)])
        
        # choose 5 initial primes values between 1300 and 1400
        for vs in subsets(primes.irange(1300, 1400), size=5):
          if sum(vs) + 4 != T: continue
          # check for a possible sequence of matches
          for ss in solve(multiset(vs)):
            # output solution
            printf("{vs} -> {ss}")
            break # we only need one possibility
        

        Like

    • Frits 5:58 pm on 28 November 2020 Permalink | Reply

      2 encounters are enough to filter out a unique solution (we have been told there is a solution).
      Coding more encounters would have resulted in an even more messy code.

      from enigma import SubstitutedExpression, is_prime
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [ 
        # 5 increasing prime numbers between 1300 and 1400
        "is_prime(1300 + AB)",
        "CD > AB",
        "is_prime(1300 + CD)",
        "EF > CD",
        "is_prime(1300 + EF)",
        "GH > EF",
        "is_prime(1300 + GH)",
        "IJ > GH",
        "is_prime(1300 + IJ)",
        
        # winner has value of (A + B + C + D + E + 4), has to be 6709.
        "AB + CD + EF + GH + IJ == 205",
       
       # 1st encounter 
        "is_prime(2601 + V*AB + W*CD + X*EF + Y*GH + Z*IJ)",
        
        # 1st encounter : pick 2
        "V + W + X + Y + Z == 2",
        
        # 2nd encounter 
        "is_prime(1301 + \
                  (1 - P)*1300 + P*(2601 + V*AB + W*CD + X*EF + Y*GH + Z*IJ) + \
                  Q*(1-V)*AB + R*(1-W)*CD + S*(1-X)*EF + T*(1-Y)*GH + U*(1-Z)*IJ)",
                  
        # 2nd encounter: pick exactly 2          
        "P + Q*(1-V) + R*(1-W) + S*(1-X) + T*(1-Y) + U*(1-Z) == 2",    
        
        # limit number of same solutions
        "Q * V == 0",        # force Q to be 0 if V equals 1
        "R * W == 0",        # force R to be 0 if W equals 1
        "S * X == 0",        # force S to be 0 if X equals 1
        "T * Y == 0",        # force T to be 0 if Y equals 1
        "U * Z == 0",        # force U to be 0 if Z equals 1
        ],
        answer="AB, CD, EF, GH, IJ, 2601 + V*AB + W*CD + X*EF + Y*GH + Z*IJ, \
                1301 + (1 - P)*1300 + P*(2601 + V*AB + W*CD + X*EF + Y*GH + Z*IJ) + \
                Q*(1-V)*AB + R*(1-W)*CD + S*(1-X)*EF + T*(1-Y)*GH + U*(1-Z)*IJ, \
                P,Q,R,S,T,U,V,W,X,Y,Z",
        d2i={k:"PQRSTUVWXYZ" for (k) in range(2,10)},
        distinct="",
        verbose=0)   
      
      # Print answers 
      prev = ""
      print("   I    II    III   IV     V    e1    e2   "
            "P, Q, R, S, T, U, V, W, X, Y, Z]")
      for (_, ans) in p.solve():
        if ans[:5] != prev:
          print([x if i > 4 else x + 1300 for (i, x) in enumerate(ans)])
        prev = ans[:5]
      

      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: