S2T2

Jim Randell 4:57 pm on 12 March 2021 Permalink Reply
Tags: by: Colin Vout ( 37 )   

• 

  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 any viable map will give the same solution.

  This Python program runs in 58ms.

  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:

  

  LikeLike

  • 

    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]

    LikeLike

  • 

    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.

    LikeLike

    • 

      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.

      LikeLike

    • 

      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.

      LikeLike

• 

  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])))
  

  LikeLike

• 

  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 🙂

  LikeLike