S2T2

Jim Randell 4:36 pm on 19 November 2021 Permalink Reply
Tags: by: Nick MacKinnon ( 51 )   

• 

  Jim Randell 5:30 pm on 19 November 2021 Permalink | Reply

  It looks like I implemented my polyiamonds.py module at just the right time (see Teaser 2838).

  I added the other hexiamonds to it and then used it to generate the only possible map. From this we see there are only 2 achiral shapes involved, and only one of them has an axis of symmetry that passes through the counties, so the required answer is determined directly from the map.

  The following Python program runs in 1.16s. Although by limiting the sets of pieces tested to those containing 2 chiral shapes, this can be reduced to 668ms.

  Run: [ @replit ]

  from enigma import (subsets, join, primes, printf)
  import polyiamonds
  
  # collect the possible hexiamonds
  shapes = polyiamonds.shapes("O6 I6 C6 E6 F6 G6 H6 J6 P6 S6 V6 X6".split())
  
  # map cells of the 24-hex grid to county numbers
  cells = [
    (0, 6), (0, 7), (1, 6), (1, 7), (2, 6), # 1 - 5
    (0, 4), (0, 5), (1, 4), (1, 5), (2, 4), (2, 5), (3, 4), # 6 - 12
    (0, 3), (1, 2), (1, 3), (2, 2), (2, 3), (3, 2), (3, 3), # 13 - 19
    (1, 1), (2, 0), (2, 1), (3, 0), (3, 1), # 20 - 24
  ]
  county = dict((cell, i) for (i, cell) in enumerate(cells, start=1))
  grid = set(cells)
  
  primes.extend(130)
  
  # choose 4 of the shapes
  for ps in subsets(shapes.keys(), size=4):
  
    # attempt to fit the shapes into the grid
    ss = list(shapes[p] for p in ps)
    for g in polyiamonds.fit(ss, grid):
      # the sum of the counties in each region should be prime
      t = dict((n, 0) for n in (1, 2, 3, 4))
      for (k, v) in g.items():
        t[v] += county[k]
      if not all(v in primes for v in t.values()): continue
  
      printf("{ps}\n", ps=join(ps, sep=" ", enc="[]"))
      polyiamonds.output_grid(g)
  

  Solution: The Prime Minister’s Mansion is in county 16.

  The layout of the departments is as follows:

  

  The departments have the following prime totals: blue (H6) = 31; red (C6) = 61; green (E6) = 101; orange (J6) = 107.

  The two departments with axes of symmetry are the red one (C6) and the green one (E6).

  The red one’s axis is along the 6/13 border, so this gives us the location of the President’s Residence (so Department A is red), and the axis in the green department (Department B) is indicated with the dotted line. This passes through counties 15 and 16, but we want to be as far from the President’s Residence as possible, so the Prime Minister’s Mansion must be in county 16.

  In fact C6 is the only achiral piece that can give a prime total, and has an axis on a border, so C6 must be involved in the map with one of E6 or V6 (which are the remaining achiral pieces with axes that pass through cells). And the remaining 2 counties must be chosen from F6, G6, H6, I6, J6, P6, S6 (chiral).

  LikeLike

  • 

    Jim Randell 10:28 pm on 19 November 2021 Permalink | Reply

    Here is a faster version, where we only consider combinations of 2 achiral and 2 chiral pieces, and positions of pieces in the grid are only considered if the counties involved have a prime sum.

    It runs in 67ms.

    Run: [ @replit ]

    from enigma import (subsets, join, primes, defaultdict, intersect, exact_cover, printf)
    import polyiamonds
    
    # collect the possible hexiamonds
    achiral = "O6 C6 E6 V6 X6".split()
    chiral = "I6 F6 G6 H6 J6 P6 S6".split()
    shapes = polyiamonds.shapes(achiral + chiral)
    
    # map cells of the 24-hex grid to county numbers
    cells = [
      (0, 6), (0, 7), (1, 6), (1, 7), (2, 6), # 1 - 5
      (0, 4), (0, 5), (1, 4), (1, 5), (2, 4), (2, 5), (3, 4), # 6 - 12
      (0, 3), (1, 2), (1, 3), (2, 2), (2, 3), (3, 2), (3, 3), # 13 - 19
      (1, 1), (2, 0), (2, 1), (3, 0), (3, 1), # 20 - 24
    ]
    county = dict((cell, i) for (i, cell) in enumerate(cells, start=1))
    grid = set(cells)
    
    primes.extend(130)
    
    # look for placements that give a prime total
    ss = defaultdict(list)
    for (k, vs) in shapes.items():
      for cs in polyiamonds.placements(vs, grid):
        if sum(county[c] for c in cs) in primes:
          ss[k].append(cs)
    
    achiral = sorted(intersect([achiral, ss.keys()]))
    chiral = sorted(intersect([chiral, ss.keys()]))
    
    # choose 2 achiral shapes
    for ps1 in subsets(achiral, size=2):
      # and the rest are chiral
      for ps2 in subsets(chiral, size=2):
        ps = ps1 + ps2
        # look for an exact cover using these pieces
        for rs in exact_cover(list(ss[p] for p in ps), grid):
          # output solution
          printf("{ps}\n", ps=join(ps, sep=" ", enc="[]"))
          g = dict()
          for (i, cs) in enumerate(rs, start=1):
            g.update((c, i) for c in cs)
          polyiamonds.output_grid(g)
    

    LikeLike

  • 

    Frits 5:20 pm on 20 November 2021 Permalink | Reply

    @Jim, you don’t answer the question

    LikeLike

    • 

      Jim Randell 5:48 pm on 20 November 2021 Permalink | Reply

      @Frits: I reveal the answers to competition puzzles after the deadline for entries is closed.

      LikeLike

      • 

        Frits 6:57 pm on 20 November 2021 Permalink | Reply

        @Jim, I mean that your program doesn’t seem to print in what county will the Prime Minister’s mansion be built. You normally don’t hide the answer in your program output. It doesn’t matter.

        LikeLike