S2T2

Jim Randell 12:59 pm on 21 July 2024 Permalink Reply
Tags: by: B W M Young ( 10 )   

• 

  Jim Randell 1:00 pm on 21 July 2024 Permalink | Reply

  This Python program colours the provinces so that no two adjacent regions share a colour, and then checks to see if there are two roads that meet the requirements.

  It runs in 68ms. (Internal runtime is 4.5ms).

  Run: [ @replit ]

  from enigma import (peek, update, join, union, map2str, printf)
  
  # adjacency matrix for provinces
  adj = {
    1: {2, 3, 4, 5},
    2: {1, 6, 7},
    3: {1, 4, 14},
    4: {1, 3, 5, 8, 15},
    5: {1, 4, 6, 9, 10},
    6: {2, 5, 7, 10, 13},
    7: {2, 6, 13, 18, 21, 22},
    8: {4, 9, 11, 16},
    9: {5, 8, 10, 11},
    10: {5, 6, 9, 12},
    11: {8, 9, 12, 17},
    12: {10, 11, 13, 17},
    13: {6, 7, 12, 18},
    14: {3, 15, 19},
    15: {4, 14, 16, 20},
    16: {8, 15, 17, 20},
    17: {11, 12, 16, 18, 21},
    18: {7, 13, 17, 21},
    19: {14, 20, 22},
    20: {15, 16, 19, 21, 22},
    21: {7, 17, 18, 20, 22},
    22: {7, 19, 20, 21},
  }
  
  # colour regions <rs> with colours <cs>
  def colour(rs, cs, m=dict()):
    # are we done?
    if not rs:
      yield m
    else:
      # choose an uncoloured region
      r = peek(rs)
      # choose a colour
      xs = cs.difference(m[x] for x in adj[r] if x in m)
      for x in xs:
        yield from colour(rs.difference([r]), cs, update(m, [(r, x)]))
  
  # regions for each road
  roads = dict(
    NW=[11, 16, 20, 19],
    NE=[11, 17, 21, 7],
    SE=[11, 10, 6, 2],
    SW=[11, 8, 4, 1],
  )
  
  # check roads
  def check(m):
    # map roads to colours
    r = dict((k, join(m[x] for x in v)) for (k, v) in roads.items())
    # find roads the do not pass through a blue province
    R1 = set(k for (k, v) in r.items() if not ('B' in v))
    if not R1: return
    # find roads that do not pass directly from blue to yellow (or vice versa)
    R2 = set(k for (k, v) in r.items() if not ('BY' in v or 'YB' in v))
    if not R2: return
    # check we can find one of each
    if len(union([R1, R2])) < 2: return
    return r
  
  # colour the regions
  for m in colour(set(adj.keys()), set("RBY")):
    # and check the roads
    r = check(m)
    if r:
      # output solution
      printf("{m}", m=map2str(m))
      printf("-> {r}", r=map2str(r))
      printf()
  

  Solution: Province 1 is red. Province 2 is yellow.

  The complete map is shown below:

  

  There is one province that can be either red or blue (On the extreme left of the diagram. I numbered it 14, and gave it both colours).

  The NE road passes through no blue, and the SW road does not pass directly from a blue to a yellow (or vice versa).

  We can see that there is no point trying to colour the central province blue (as that would make blue appear in every road), but I think the code is fast enough without this.

  LikeLike

  • 

    Ruud 9:27 am on 22 July 2024 Permalink | Reply

    Here’s my code:

    neighbours = {
        1: {2, 3, 4, 5},
        2: {1, 6, 7},
        3: {1, 4, 14},
        4: {1, 3, 5, 8, 15},
        5: {1, 4, 6, 9, 10},
        6: {2, 5, 7, 10, 13},
        7: {2, 6, 13, 18, 21, 22},
        8: {4, 9, 11, 16},
        9: {5, 8, 10, 11},
        10: {5, 9, 6, 12},
        11: {8, 9, 12, 17},
        12: {10, 11, 13, 17},
        13: {6, 12, 7, 18},
        14: {3, 15, 19},
        15: {4, 14, 16, 20},
        16: {8, 15, 17, 20},
        17: {11, 12, 16, 18, 21},
        18: {13, 17, 7, 21},
        19: {14, 20, 22},
        20: {15, 16, 19, 21, 22},
        21: {17, 18, 20, 7, 22},
        22: {19, 20, 21, 7},
    }
    roads = [(1, 4, 8, 11), (2, 6, 10, 11), (19, 20, 16, 11), (7, 21, 17, 11)]
    
    
    def solve(province, colors):
        for color in colors[province]:
            new_colors = colors.copy()
            new_colors[province] = color
            for neighbour in neighbours[province]:
                new_colors[neighbour] = new_colors[neighbour].replace(color, "")
            if province == 22:
                not_blue = set()
                not_blue_yellow = set()
                for road in roads:
                    road_colors = "".join(colors[province] for province in road)
                    if "b" not in road_colors:
                        not_blue.add(road)
                    if not ("yb" in road_colors or "by" in road_colors):
                        not_blue_yellow.add(road)
    
                if len(not_blue) > 0 and len(not_blue_yellow) > 0 and len(not_blue | not_blue_yellow) >= 2:
                    print(new_colors[1], new_colors[2])
            else:
                solve(province + 1, colors=new_colors)
    
    
    solve(province=1, colors={province: "ryb" for province in range(1, 23)})
    

    LikeLike