S2T2

Jim Randell 4:18 pm on 22 October 2021 Permalink Reply
Tags: by: Colin Vout ( 37 )   

• 

  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

  LikeLike

  • 

    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.

    Run: [ @replit ]

    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.

    LikeLike