S2T2

Jim Randell 9:33 am on 30 November 2021 Permalink Reply
Tags: by: A K Austin ( 4 )   

• 

  Jim Randell 9:35 am on 30 November 2021 Permalink | Reply

  Considering the 5 pieces that are correct, but of unknown orientation. The entire painting is covered by these 5. In particular each of the corner sub-squares of the painting must correspond to 4 of the pieces (in some orientation), so we can look for those.

  The following Python 3 program runs in 110ms.

  Run: [ @replit ]

  from enigma import (irange, repeat, subsets, cproduct, join, printf)
  
  # the 6 pieces
  pieces = {
    1: (0, 1, 0, 0, 1, 0, 0, 1, 1),
    2: (1, 0, 1, 0, 0, 1, 0, 1, 1),
    3: (0, 1, 0, 1, 0, 0, 1, 1, 1),
    4: (0, 0, 1, 1, 0, 0, 0, 1, 1),
    5: (0, 0, 0, 0, 0, 1, 0, 1, 0),
    6: (1, 0, 0, 1, 1, 1, 0, 0, 1),
  }
  
  # rotate a piece
  rotate = lambda p: tuple(p[i] for i in (6, 3, 0, 7, 4, 1, 8, 5, 2))
  
  # return all 4 rotations
  rots = lambda p: repeat(rotate, p, 3)
  
  # placements for the corners
  corners = [(0, 0), (0, 2), (2, 0), (2, 2)]
  
  # place p at (x, y) in the grid
  # return a new grid or None
  def place(g, p, x, y):
    g_ = dict(g)
    for (j, v) in enumerate(p):
      (dx, dy) = divmod(j, 3)
      k = (x + dx, y + dy)
      v_ = g_.get(k)
      if v_ is None:
        g_[k] = v
      elif v_ != v:
        return None
    return g_
  
  # place pieces <ps> at locations <ls>
  def solve(ps, ls, g=dict()):
    # are we done?
    if not ps:
      yield g
    else:
      # place a piece in the next location
      (p, (x, y)) = (ps[0], ls[0])
      # consider possible rotations
      for p in rots(p):
        g_ = place(g, p, x, y)
        if g_ is not None:
          yield from solve(ps[1:], ls[1:], g_)
  
  # locate a piece from ps in grid g
  def locate(g, ps):
    for p in ps:
      for (x, y) in cproduct([(0, 1, 2), (0, 1, 2)]):
        if place(g, p, x, y):
          yield (x, y)
  
  # consider possible orderings of pieces
  for (p1, p2, p3, p4, p5, p6) in subsets(pieces.keys(), size=6, select="P"):
  
    # place the first 4 (in some orientation) in the corners
    for g in solve(list(pieces[i] for i in (p1, p2, p3, p4)), corners):
  
      # check the 5th piece fits in some orientation at some other location
      l5s = set(z for z in locate(g, rots(pieces[p5])) if z not in corners)
      if not l5s: continue
  
      # and the remaining piece has one square wrong but fits the right way up
      l6s = dict()
      for j in irange(0, 8):
        p = list(pieces[p6])
        p[j] ^= 1
        for z in locate(g, [p]):
          if z not in corners:
            l6s[z] = j
      if not l6s: continue
      if not any(a != b for (a, b) in cproduct([l5s, l6s.keys()])): continue
  
      # output solution
      printf("corners = [{p1}, {p2}, {p3}, {p4}]; other = {p5} @ {l5s}; wrong = {p6} @ {l6s}\n")
      for x in (0, 1, 2, 3, 4):
        printf("{row}", row=join((g[(x, y)] for y in (0, 1, 2, 3, 4)), sep=" ", enc="[]"))
      printf()
  

  Solution: The solution is as follows:

  

  There are 9 possible locations for a 3×3 sub-square of the 5×5 square. The 4 corners, the 4 edges, and the central sub-square.

  The corners consist of pieces 4, 5, 6, 1 (in suitable orientations), and piece 2 corresponds to the left edge sub-square. The central sub-square correspond to piece 3 (the right way up), except the cell marked “x” is the wrong colour.

  Note that each of the pieces 1 – 6 corresponds to a different 3×3 sub-square in the finished painting. If two pieces are allowed to correspond to the same sub-square, then this solution is not unique.

  The program produces 2 solutions corresponding to the same diagram. This is because piece 6 is the same when rotated through 180°.

  LikeLike

• 

  Frits 1:10 pm on 1 March 2024 Permalink | Reply

  When looking for similar puzzles to the 1994 IMO C1 question I stumbled upon this puzzle.

  @Jim, do you know a more elegant/compact alternative for diff_comb()?

  from enigma import SubstitutedExpression
  from itertools import product
  
  # the 6 pieces
  pieces = {
    1: (0, 1, 0, 0, 1, 0, 0, 1, 1),
    2: (1, 0, 1, 0, 0, 1, 0, 1, 1),
    3: (0, 1, 0, 1, 0, 0, 1, 1, 1),
    4: (0, 0, 1, 1, 0, 0, 0, 1, 1),
    5: (0, 0, 0, 0, 0, 1, 0, 1, 0),
    6: (1, 0, 0, 1, 1, 1, 0, 0, 1),
  }
  
  # rotate a piece clockwise
  rotate = lambda p: tuple(p[x] for x in [3 * i + j for j in range(2, -1, -1)
                                                    for i in range(3)])
  
  # return all 4 rotations
  def rotations(p):
    yield p
    for _ in range(3):
      p = rotate(p)
      yield p
  
  # dictionary of 3x3 box usage
  d_3x3 = dict()
  for k, v in pieces.items():
    for r in rotations(v):
      d_3x3[r] = d_3x3.get(r, set()) | {k}
  
  # placements for the corners
  corners = {(0, 0), (0, 2), (2, 0), (2, 2)}
  
  # get the four corner 3x3 boxes
  get_corners = lambda m: [topLeft_3x3(m, c) for c in corners]
  
  # check if a corner can be made by one of the pieces
  check_corner = lambda r: set() if r not in d_3x3 else d_3x3[r]
  
  # check if a combination with different values exists
  def diff_comb(s):
    for p in product(*s):
      if len(set(p)) == len(p):
        return True
    return False
  
  # return the 3x3 box values starting at the top left <tl>
  def topLeft_3x3(m, tl):
    (tlx, tly) = tl
    return tuple(m[tlx + x][tly + y]
                 for (x, y) in product((0, 1, 2), (0, 1, 2)))
  
  # perform checks for the two remaining pieces
  def check_oth(m, cs):
    # nine possible 3x3 boxes minus the four corner 3x3 boxes
    five3x3 = {topLeft_3x3(m, tl) for tl in product((0, 1, 2), (0, 1, 2))
               if tl not in corners}
  
    # check all combinations of 4 corners
    for p in product(*cs):
      if len(set(p)) != len(p): continue
      # remaining two pieces
      rest = set(range(1, 7)).difference(p)
  
      found_rotated = []
      found_wrong = []
      for pc in rest:
        # check possible rotation (without the corners)
        for rot in [k for k, v in d_3x3.items() if pc in v]:
          if rot in five3x3:
            found_rotated.append((pc, rot))
  
        # check if a "right way up" piece has exactly 8 correct squares
        for a in five3x3:
          if sum([x == y for x, y in zip(a, pieces[pc])]) == 8:
           found_wrong.append((pc, a))
  
      # check options for 2 last pieces
      for (rn, r), (wn, w) in product(found_rotated, found_wrong):
        # different pieces
        if rn == wn: continue
        # both pieces must be at a different spot
        w_spots = {i for i, x in enumerate(five3x3) if x == w}
        r_spots = {i for i, x in enumerate(five3x3) if x == r}
        if len(w_spots | r_spots) < 2: continue
        return True
  
    return False
  
  A_Y = [chr(x) for x in range(ord("A"), ord("Y") + 1)]
  
  # 5x5 matrix of A-E, F-J, K-O, P-T, U-Y
  M = [[A_Y[5 * i + j] for j in range(5)] for i in range(5)]
  
  # all variable names in a 5x5 matrix layout (without quotes)
  mat = "((" + "), (".join(','.join(r) for r in M) + "))"
  
  answer = f"{mat}"
  
  exprs = []
  # check if every corner can be made from a piece
  for i, c in enumerate(get_corners(M), start=1):
    s = "(" + ', '.join(c) + ")"
    exprs.append(f"len(c{i} := check_corner({s})) > 0")
  
  # 4 corners use different pieces
  exprs.append("diff_comb([c1, c2, c3, c4])")
  
  # check remaining two pieces
  exprs.append(f"check_oth({mat}, [c1, c2, c3, c4])")
  
  # the alphametic puzzle
  p = SubstitutedExpression(
    exprs,
    answer=answer,
    distinct="",
    env=dict(check_oth=check_oth,
             check_corner=check_corner,
             diff_comb=diff_comb),
    digits=range(0, 2),
    decl="global c1, c2, c3, c4",
    denest=2,
    reorder=0,    # necessary because of assignment statements
    verbose=0,    # use 256 to see the generated code
  )
  
  # print answers
  print("answer:")
  for ans in p.answers():
    for x in ans:
      print(f"{x}")
    print()     
  

  LikeLike

  • 

    Jim Randell 8:19 am on 12 June 2024 Permalink | Reply

    @Frits: You could use the [[ disjoint_cproduct() ]] function from Teaser 3220 to implement diff_comb.

    diff_comb(s) → any(disjoint_cproduct(s))

    LikeLike

    • 

      Frits 10:23 am on 12 June 2024 Permalink | Reply

      Thanks, I tested it. I had forgotten I had asked the question.

      LikeLike