S2T2

Jim Randell 7:08 am on 24 November 2024 Permalink Reply
Tags: by: Peter Good ( 27 ), flawed ( 53 )   

• 

  Jim Randell 11:25 am on 24 November 2024 Permalink | Reply

  Initially I thought that the dominoes were formed into a collection of [straight linear] strips, and then these strips were used (as is) to make the border of a (single) square.

  However, after working on the puzzle for some time I was not able to find a solution using this interpretation (or variations thereof).

  You can see my thoughts in the chat page [ here ].

  ---

  However, I think I have now found an alternative interpretation that does lead to a unique answer to the puzzle.

  To me the use of the term “strip” implied that a selected set of dominoes were formed into a straight linear arrangement, whereas it seems that they need to be formed into a square loop. So in the following I just used the term “pile”.

  The set of 28 dominoes is formed into a collection of piles, such that for each pile:

  + The total sum of the pips is the square of the number of the dominoes in that pile.

  + The dominoes in each pile can be arranged to form a closed loop that is the outline of a square, and where two dominoes meet the pip values on the adjoining ends are the same.

  Additional requirements for the collection of piles are:

  + There is a single pile that is identifiably the largest pile, and it contains more than half of the double tiles.

  + There are (exactly) two piles that are identifiably the smallest piles. One of these piles contains a double tile, and this double is the largest possible double that can occur in a pile of that size (constructed subject to the conditions above).

  + The other smallest pile does not have a double in it, and the required answer is a list of dominoes that make up this pile.

  I have verified that under this interpretation there is a unique answer to the puzzle, and have posted my code below.

  Solution: [see below]

  LikeLike

  • 

    Rob Bellis 8:48 am on 26 November 2024 Permalink | Reply

    hello Jim

    Is there any reason why the square cound not be bounded by 2 x 8 tiles and 2 x 6 tiles (to enclose a 6×6 square) ?
    If each side length 6 was constructed of a 2 +4 tile strings then the sum of the squares would = 168 which is the total domino spots .

    LikeLike

    • 

      Jim Randell 8:56 am on 26 November 2024 Permalink | Reply

      In my initial interpretation of the puzzle I did look at attempting to make the outline of a single 14×14 square from a collection of straight strips, but it was not possible using 26 of the dominoes (for example: [7] + [4, 3] + [4, 2] + [4, 2]).

      In the (presumably) intended interpretation, enclosing a 6×6 square would require 14 dominoes, so to form an allowable loop there would have to be 14^2 = 196 pips in the selection. But there are only 168 pips in the entire set of dominoes, so the squares must be smaller than this.

      LikeLike

• 

  NigelR 5:38 pm on 24 November 2024 Permalink | Reply

  A single domino doesn’t seem to satisfy being a border of an empty square. However, the wording would seem to allow a single strip being part of more than one square. Perhaps we are looking for a more complex shape than one or more detached squares?

  LikeLike

• 

  Jim Randell 11:12 am on 25 November 2024 Permalink | Reply

  This Python 3 program solves the interpretation of the puzzle given above in my first comment.

  It assumes the two smallest piles are the same size.

  It runs in 851ms.

  from enigma import (
    defaultdict, irange, inf, first, subsets, sq, express, flatten,
    rev, remove, trim, cproduct, multiset, join, printf
  )
  
  # we represent a domino by a tuple (x, y)
  
  # format a collection of dominoes
  fmt = lambda ds: join((join(d, sep='-', enc="[]") for d in ds), sep=' ')
  
  # number of pips on a domino
  pips = sum
  
  # a complete set of dominoes
  ds = set(subsets(irange(0, 6), size=2, select='R'))
  
  # normal form of dominoes
  normalise = lambda d: tuple(sorted(d))
  normal = lambda *ss: (normalise(d) for d in flatten(ss, fn=iter))
  
  # invalid pips (sorts before all valid pips)
  X = -1
  
  # generate loops with <k> dominoes and <t> pips, from dominoes <ds>
  # <m> = min starting domino
  def loops(k, t, ds, m=(X, X), ss=[]):
    # are we done?
    if k == 0:
      # remove duplicate loops
      if normalise(ss[1]) > normalise(ss[-1]): return
      # check all pips are used, and a loop is formed
      if t == 0 and ss[0][0] == ss[-1][-1]:
        yield (ss, ds)
    elif not (t > 12 * k):
      # choose the next domino
      for d in ds:
        nd = normalise(d)
        if nd < m or (ss and normalise(ss[0]) > nd): continue
        p = pips(d)
        if p > t: continue
        if (not ss) or (d[0] == ss[-1][-1]):
          yield from loops(k - 1, t - p, remove(ds, d, rev(d)), m, ss + [d])
  
  # make a collection of loops with length <ks>, from dominoes <ds>
  def piles(ks, ds, rs=[]):
    # are we done?
    if not ks:
      yield (rs, ds)
    else:
      k = ks[0]
      m = (normalise(rs[-1][0]) if rs and k == len(rs[-1]) else (X, X))
      for (ss, ds_) in loops(k, sq(k), ds, m):
        yield from piles(ks[1:], ds_, rs + [ss])
  
  # find the doubles in a set of dominoes
  doubles = lambda ds: sorted(x for (x, y) in ds if x == y)
  
  # max or X
  max_ = lambda xs: (max(xs) if xs else X)
  
  # total number of pips
  tpips = sum(pips(d) for d in ds)
  printf("[{n} dominoes, total pips = {tpips}]", n=len(ds))
  
  # piles have an even number of dominoes, minimum 4
  ns = first(irange(4, inf, step=2), count=(lambda x: sq(x) < tpips))
  printf("[pile sizes = {ns}]")
  
  # initial set of dominoes in either orientation
  dss = set(flatten({d, rev(d)} for d in ds))
  
  # collect results
  rs = multiset()
  
  # look for possible numbers of piles (at least 3)
  for qs in express(tpips, list(sq(n) for n in ns)):
    if sum(qs) < 3: continue
    # form the pile sizes (in order)
    ks = flatten([n] * q for (n, q) in zip(ns, qs) if q > 0)
    # use all the dominoes
    if sum(ks) != 28: continue
    # there should be 2 identifiable smallest piles, and 1 identifiable largest pile
    if not (ks[0] == ks[1] < ks[2] and ks[-2] < ks[-1]): continue
    # the largest pile has 4 doubles -> a loop of at least 8 dominoes
    if ks[-1] < 8: continue
    printf("[checking {ks} = {n} dominoes]", n=sum(ks))
  
    # start with the smallest piles (size k)
    (k, gs) = (ks[0], defaultdict(list))
    for (ss, _) in loops(k, sq(k), dss):
      gs[max_(doubles(ss))].append(ss)
    # max possible double in a smallest pile
    m = max(gs.keys())
    assert m != X
  
    # choose the two smallest piles
    for (ss1, ss2) in cproduct([gs[X], gs[m]]):
      # which must contain distinct dominoes
      xs = set(normal(ss1, ss2))
      if len(xs) < 2 * k: continue
  
      # choose the largest pile (size K)
      (K, dss_) = (ks[-1], dss.difference(xs, (rev(x) for x in xs)))
      for (ssz, dsz) in loops(K, sq(K), dss_):
        # which must have at least 4 doubles
        if len(doubles(ssz)) < 4: continue
  
        # fill out the remaining piles
        for (ps, _) in piles(trim(ks, head=2, tail=1), dsz):
          ans = tuple(sorted(normal(ss1)))
          # display the collection of piles
          printf("ss1 = {ss1} -> answer", ss1=fmt(ss1))
          printf("ss2 = {ss2}", ss2=fmt(ss2))
          for (i, ss) in enumerate(ps, start=3):
            printf("ss{i} = {ss}", ss=fmt(ss))
          printf("ss{z} = {ssz}", z=len(ps) + 3, ssz=fmt(ssz))
          printf()
          rs.add(ans)
  
  # output solutions
  for (ss, n) in rs.most_common():
    printf("dominoes = {ss} [{n} solutions]", ss=fmt(ss))
  

  Solution: The required dominoes are: [0-1] [0-5] [1-2] [2-5].

  Here are the 28 dominoes split into 5 piles, and each pile laid out as a square loop:

  [1-0] [0-5] [5-2] [2-1]
  [2-0] [0-3] [3-3] [3-2]
  [0-0] [0-4] [4-3] [3-5] [5-6] [6-0]
  [3-1] [1-4] [4-2] [2-2] [2-6] [6-3]
  [1-1] [1-5] [5-5] [5-4] [4-4] [4-6] [6-6] [6-1]

  

  The dominoes that make up the answer to the puzzle are those in the first (top-left) square, which has 4 dominoes and 16 pips in total.

  The second (top-right) square uses the double [3-3], which is the largest possible double for a loop with 4 dominoes. It also has 16 pips in total.

  Each of the middle squares consists of 6 dominoes, and has 36 pips in total.

  The bottom square consists of 8 dominoes, uses 4 doubles ([1-1] [5-5] [4-4] [6-6]), and has 64 pips in total.

  There is a further layout that also provides a solution:

  [1-0] [0-5] [5-2] [2-1]
  [2-0] [0-3] [3-3] [3-2]
  [0-0] [0-4] [4-5] [5-3] [3-6] [6-0]
  [3-1] [1-6] [6-2] [2-2] [2-4] [4-3]
  [1-1] [1-4] [4-4] [4-6] [6-6] [6-5] [5-5] [5-1]

  The first two loops are the same as the layout above.

  And of course any loop in a solution can be reflected or rotated.

  LikeLike

  • 

    Brian Gladman 2:56 pm on 29 November 2024 Permalink | Reply

    @Jim. Your optimisation in this code very is impressive. I have a structurally similar solution but it is painfully slow because it finds the same loops many thousands of times and I have not found a technique for preventing this. I can see that you have managed to do this but I am wondering what principle you have based this on?

    LikeLike

    • 

      Jim Randell 3:08 pm on 29 November 2024 Permalink | Reply

      @Brian: Yes, this was a tricky one to program (even after determining the intended interpretation of the text).

      I used several “normal forms” to eliminate duplicate solutions:

      + for a domino (x, y) the normal form is when x ≤ y. (Otherwise we might also consider (y, x)).

      + for a loop, the normal form is to start with smallest domino (as above), and travel round the loop such that the second domino is less than the final domino. (There are at least 4 dominos in a loop, so these are all different). (Otherwise we could start at any domino, and go round the loop in either direction).

      + for a collection of loops of the same size, I require that they are ordered by the first domino. (Otherwise we might find the same loops in a different order).

      Together these bring the number of solutions down to two different collections of dominoes.

      LikeLiked by 1 person

      • 

        Brian Gladman 5:15 pm on 29 November 2024 Permalink | Reply

        Thanks Jim, It looks like eliminating duplicate solutions is as much, if not more work, than finding solutions in the first place!

        LikeLike

  • 

    Frits 11:53 am on 12 December 2024 Permalink | Reply

    @Jim,

    If you are only interested in the answer then you might split the cproduct for ss1 and ss2 to two separate loops and do some else/continue/break constructs. This will bring down the run time by a factor 3.

    Also using a simpler normalise() is faster.

    normalise = lambda d: d if d[0] <= d[1] else (d[1], d[0])
    

    LikeLike

• 

  Frits 10:59 am on 12 December 2024 Permalink | Reply

  This program runs in 35ms (not as fast as Brian’s recursive program).
  A lot of work again.

  from enigma import SubstitutedExpression
  
  mx_dom = 6
  
  # sorted tuple
  stup = lambda s: tuple(sorted(s))
  # generate circular pairs
  circular = lambda s: set(stup([x, y]) for x, y in zip(s, s[1:] + s[:1]))
  
  # including (x, y) and (y, x)
  allcombs = lambda s: s | set((y, x) for x, y in s)
  tri = lambda n: n * (n + 1) // 2
  
  # decompose <t> into at least <mn> non-decreasing square piles
  def decompose(t, mn=4, ns=[], fn=lambda x: x * x, ss = ()):
    unpack = lambda f: (lambda x: f(*x))
    if t == 0 and len(ss) >= mn:
      # also require that the two smallest values in <ss> are
      # equal and that there is only one largest value
      if ss[0] == ss[1] and ss[-1] > ss[-2]:
        yield ss
    else:
      for i, s in enumerate(ns):
        if t >= fn(s):
          yield from decompose(t - fn(s), mn, ns[i:], fn, ss + (s, ))
  
  # run the SubstitutedExpression with specific expressions
  def run(exprs, answer, d2i, syms, s2d=dict(), reorder=0, verbose=0):
    # eg for strip 'a-b-c-d-e-f-g-h-i-j' a must be different from c and i
    distinct = set(x + y if x < y else y + x for x, y in zip(syms, syms[2:] + syms[:2]))
  
    p = SubstitutedExpression(
        exprs,
        symbols=syms,
        answer=answer,
        d2i=d2i,
        distinct=distinct,
        env=dict(stup=stup, allcombs=allcombs),
        base=mx_dom + 1,
        s2d=s2d,
        digits=(range(mx_dom + 1)),
        reorder=reorder,
        verbose=verbose,  # use 256 to see the generated code
      )
    return tuple(p.answers())
  
  # solve remaining strips after 3 strips are known
  def solve(k, strips, pairs, ss=tuple()):
    if k == 0:
      yield ss
    else:
      s_size = strips[0]
      syms = allsyms[:s_size]
      vars = ','.join(syms)
      varlist = "[" + vars + "]"
      pairs4 = f"list(zip({varlist}, [{vars[2:]},{syms[0]}]))"
      s2d = dict()
  
      exprs = []
  
      # check if remaining strips all have the same size
      if len(set(strips)) == 1:
        # let strip begin with lowest remaining domino
        low = next(x for x in dominoes if x not in pairs)
        s2d[syms[0]], s2d[syms[1]] = low[0], low[1]
        first_domino_set = 1
      else:
        first_domino_set = 0
        # start with lowest number
        for i in range(1, s_size - 1):
          exprs.append(f"{syms[0]} <= {syms[i]}")
  
      # try to speed up the process
      #for i in range(2, 3):
      #  exprs.append(f"({syms[i - 1]}, {syms[i]}) not in {pairs}")
  
      # calculate last variable: sum(syms) * 2 = s_size^2
      exprs.append(f"{s_size**2 // 2} - sum([{vars[:-2]}]) = {syms[-1]}")
  
      if not first_domino_set:
        exprs.append(f"{syms[0]} <= {syms[-1]}")
      # ABCD <= ADCB
      exprs.append(f"{syms[1]} <= {syms[-1]}")
  
      # use different dominoes than already used
      exprs.append(f"allcombs(set(p4 := {pairs4})).isdisjoint({pairs})")
  
      # all dominoes must be unique
      exprs.append(f"len(set([stup([x, y]) for x, y in p4])) == {s_size}")
  
      # avoid rotations if list starts with a doublet
      exprs.append(f"{syms[0]} != {syms[1]} or "
                   f"{varlist} <= [{syms[1]},{syms[0]},{','.join(syms[2:][::-1])}]")
  
      answer = "tuple(" + varlist + ")"
  
      # limit variable values
      if first_domino_set:
        # other values in <syms> may not be smaller than first value
        # and for strip 'a-b-c-d-e-f-g-h-i-j' a must be different from c and i
        d2i = dict([(k, vars[2:]) for k in range(s2d[syms[0]])] +
                   [(s2d[syms[0]], syms[2] + syms[-2])])
        d2i[s2d[syms[1]]] = d2i.get(s2d[syms[1]], "") + syms[3] + syms[-1]
      else:
        # calculate highest possible starting domino
        ln = len(dominoes)
        mx = next(i for i in range(6, -1, -1)
                  if ln - dominoes.index((i, i)) >= s_size)
        d2i = dict([(k, vars[0]) for k in range(mx + 1, mx_dom + 1)])
  
      # solve one strip
      for r in run(exprs, answer, d2i, syms, s2d, reorder=0, verbose=0):
        yield from solve(k - 1, strips[1:], pairs | circular(r), ss + (r, ))
  
  allsyms = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  
  # the 28 dominoes
  dominoes = tuple((i, j) for i in range(mx_dom + 1) for j in range(i, mx_dom + 1))
  # the total number of spots
  n_spots = sum(a + b for a, b in dominoes)
  rt_spots = int(n_spots**.5)
  
  mn_pile = 4 # at least 4 sides
  # sum of spots of <n> largest dominoes must be >= n^2
  mx_pile = next(i for i in range(rt_spots - rt_spots % 2 , 2, -2)
                 if i * i <= sum(a + b for a, b in dominoes[-i:]))
  sols = set()
  
  # generate valid piles of strips
  for pile in decompose(n_spots, mn_pile, range(mn_pile, mx_pile + 1, 2)):
    # ----------------------
    # get shortest strips
    # ----------------------
    min_strip = pile[0]
    syms = allsyms[:min_strip]
    vars = ','.join(syms)
    varlist = "[" + vars + "]"
    exprs = []
    pairs1 = f"[stup([x, y]) for x, y in zip({varlist}, [{vars[2:]},{syms[0]}])]"
    for i in range(1, min_strip - 1):
      exprs.append(f"{syms[0]} <= {syms[i]}")
  
    # calculate last variable: sum(syms) * 2 = min_strip^2
    exprs.append(f"{min_strip**2 // 2} - sum([{vars[:-2]}]) = {syms[-1]}")
  
    exprs.append(f"{syms[0]} <= {syms[-1]}")
    exprs.append(f"{syms[1]} <= {syms[-1]}")  # ABCD <= ADCB
    # strip should have 0 or 1 doublets
    exprs.append(f"len({{{vars}}}) >= {min_strip - 1}")
  
    # all dominoes must be unique
    exprs.append(f"len(set({pairs1})) = {min_strip}")
  
    answr = f"next((x for x, y in {pairs1} if x == y), -1), "
    answr += "tuple(" + varlist + ")"
    # calculate highest possible starting domino
    ln = len(dominoes)
    mx = next(i for i in range(6, -1, -1)
              if ln - dominoes.index((i, i)) >= min_strip)
    d2i = dict([(k, vars[0]) for k in range(mx + 1, 10)])
    # reverse sort on doublet
    answs = sorted(run(exprs, answr, d2i, syms, s2d=dict(),
                       reorder=0, verbose=0), reverse=True)
  
    mx_doublet = answs[0][0]
    # find strips with 1 doublet
    for ans1 in answs:
      if ans1[0] != mx_doublet or ans1[0] == -1: break
      pairs1 = circular(ans1[1])
  
      # find strips without a doublet
      for ans2 in answs:
        if ans2[0] != -1: continue
        # first 2 strips have to use different dominoes
        if len(pairs12 := pairs1 | circular(ans2[1])) != 2 * min_strip: continue
  
        # store potential answer
        sol = tuple((x, y) for x, y in zip(ans2[1], ans2[1][1:] + (ans2[1][0], )))
        if sol in sols: continue
  
        # get all possible pairs of both strips
        pairs12all = allcombs(pairs12)
  
        # ---------------------------------
        # find longest strip
        # ---------------------------------
        max_strip = pile[-1]
        syms = allsyms[:max_strip]
        mn_doublets = mx_dom // 2 + 1   # minimum number of doublets required
  
        exprs = []
  
        # all dominoes are doublets?
        if (all_doublets := (max_strip == 2 * mn_doublets)):
          # create <vars> like A,A,C,C,E,E,G,G
          vars = ','.join(x + "," + x for x in allsyms[:max_strip][::2])
          varlist = "[" + vars + "]"
          pairs3 = f"list(zip({varlist}, [{vars[2:]},{syms[0]}]))"
          for i in range(2, max_strip - 2, 2):
            exprs.append(f"{syms[0]} < {syms[i]}")
  
          # calculate last variable: sum(syms) * 2 = max_strip^2
          exprs.append(f"div({max_strip**2 // 2} - sum([{vars[:-4]}]), 2) = {syms[-2]}")
          exprs.append(f"{syms[0]} < {syms[-2]}")
        else:
          vars = ','.join(syms)
          varlist = "[" + vars + "]"
          pairs3 = f"list(zip({varlist}, [{vars[2:]},{syms[0]}]))"
          # start strip with the smallest doublet
          exprs.append(f"{syms[0]} = {syms[1]}")
          for i in range(2, max_strip - 1):
            exprs.append(f"{syms[i - 1]} != {syms[i]} or {syms[0]} < {syms[i]}")
            exprs.append(f"({syms[i - 1]}, {syms[i]}) not in {pairs12all}")
  
          # calculate last variable: sum(syms) * 2 = max_strip^2
          exprs.append(f"{max_strip**2 // 2} - sum([{vars[:-2]}]) = {syms[-1]}")
          exprs.append(f"{syms[0]} <= {syms[-1]}")
          exprs.append(f"{syms[1]} <= {syms[-1]}")    # ABCD <= ADCB
          exprs.append(f"({syms[-1]}, {syms[0]}) not in {pairs12all}")
          # more than half doublets
          exprs.append(f"len({{{vars}}}) <= {pile[-1] - mn_doublets}")
  
        # use different pairs
        exprs.append(f"allcombs(set(p3 := {pairs3})).isdisjoint({pairs12all})")
        # all dominoes must be unique
        exprs.append(f"len(set([stup([x, y]) for x, y in p3])) == {max_strip}")
  
        # avoid rotations if strip starts with a doublet
        if all_doublets:
          exprs.append(f"{varlist} <= [{vars[:3]},{vars[4:][::-1]}]")
        else:
          exprs.append(f"{syms[0]} != {syms[1]} or "
                       f"{varlist} <= [{syms[1]},{syms[0]},{','.join(syms[2:][::-1])}]")
  
        # eg. the four doublets (3, 3)...(6, 6) have too many spots
        max_smallest_doublet = next(i for i in range(max_strip - mn_doublets, -1, -1)
                                    if 4 * (i * mn_doublets + tri(mn_doublets - 1))
                                    <= max_strip**2)
  
        # limit first domino
        d2i = dict([(k, vars[0]) for k in range(max_smallest_doublet + 1, 10)])
        if all_doublets:
          # if (0, 0) is present then it has to be the first doublet
          d2i[0] = syms[::2][1:]
          d2i[ans1[0]] = syms # exclude the doublet used in shortest strip
        answr = f"tuple(" + varlist + ")"
  
        for ans3 in run(exprs, answr, d2i, syms, s2d=dict(), reorder=0, verbose=0):
          pairs123all = allcombs(pairs12 | circular(ans3))
          # solve remaining strips
          for s in solve(len(pile) - 3, pile[2:-1], pairs123all):
            sols.add(sol)
            break # as <sol> only depends on 2nd strip
          else: # no break
            continue
          break
  
  for s in sols:
    print("answer:", s)
  

  LikeLike