S2T2

Jim Randell 4:14 pm on 21 April 2023 Permalink Reply
Tags: by: Colin Vout ( 37 )   

• 

  Jim Randell 4:44 pm on 21 April 2023 Permalink | Reply

  This Python program runs in 60ms. (Internal runtime is 4.9ms).

  Run: [ @replit ]

  from enigma import (subsets, update, join, filter2, irange, printf)
  
  # the colours (K = black)
  colours = "BKRY"
  
  # x before y
  before = lambda s, x, y: s.index(x) < s.index(y)
  
  # is there a colour where all "before yellow" < all "after yellow"
  def check(ss, n):
    for k in colours:
      if k == "Y": continue
      (bY, aY) = filter2((lambda i: before(ss[i], k, 'Y')), irange(n))
      if bY[-1] < aY[0]: return True
    return False
  
  # solve the puzzle
  def solve(ss):
    n = len(ss)
    # are we done?
    if n == 12:
      if check(ss, n):
        yield ss
    else:
      # choose 2 indices to swap
      s = ss[-1]
      for ((i, x), (j, y)) in subsets(enumerate(s), size=2):
        if (j == i + 1) == (n in {5, 10}): continue
        s_ = update(s, [(i, y), (j, x)])
        # blue before black, and no repeats
        if before(s_, 'B', 'K') and s_ not in ss:
          # move on to the next hoop
          yield from solve(ss + [s_])
  
  # choose an order for the first hoop, with blue before black
  for s in subsets(colours, size=len, select='P', fn=join):
    if not before(s, 'B', 'K'): continue
    # solve for the remaining hoops
    for ss in solve([s]):
      # output solution
      printf("hoop 12 = {s12} [{ss}]", s12=ss[-1], ss=join(ss, sep=" "))
  

  Or [here] is a (longer) version that verifies the “yellow” condition as it goes along (instead of just checking it at the end).

  Solution: The order for the 12th hoop was: Red, Yellow, Blue, Black.

  The full list of orders is (B = Blue, K = Black, R = Red, Y = Yellow):

   1: B K Y R (K before Y)
   2: B K R Y (3/4 swapped; K before Y)
   3: B R K Y (2/3 swapped; K before Y)
   4: R B K Y (1/2 swapped; K before Y)
   5: R B Y K (3/4 swapped; Y before K)
   6: Y B R K (1/3 swapped; Y before K)
   7: Y B K R (3/4 swapped; Y before K)
   8: B Y K R (1/2 swapped; Y before K)
   9: B Y R K (3/4 swapped; Y before K)
  10: B R Y K (2/3 swapped; Y before K)
  11: Y R B K (1/3 swapped; Y before K)
  12: R Y B K (1/2 swapped; Y before K)

  And we see the non-adjacent swaps are between hoops 5 & 6 and 10 & 11.

  

  LikeLike

• 

  Frits 11:44 pm on 21 April 2023 Permalink | Reply

  Without recursion.

     
  from itertools import permutations, product
  from collections import defaultdict
  
  # the colours (K = black)
  colours = "BKRY"
  
  # possible running orders (blue before black)
  ps = list(p for p in permutations(range(4)) if p.index(0) < p.index(1))
  
  adj_moves = defaultdict(list)
  nonadj_moves = defaultdict(list)
  
  # determine all possible next running orders for a specific running order
  for (x, y) in product(ps, repeat=2):
    if x == y: continue
    swaps = [i for i, (a, b) in enumerate(zip(x, y)) if a != b]
    # only one swap took place ...
    if len(swaps) != 2: continue
    # .. and store for adjacent fields and non-adjacent fields
    (adj_moves if abs(swaps[0] - swaps[1]) == 1 else nonadj_moves)[x].append(y)
   
  
  # first hoop
  ss = [(x, ) for x in ps]
  # process remaining hoops after first hoop
  for n in range(1, 12):
    ss_ = []
    for s in ss:
      # determine next running order
      for ro in (adj_moves if n not in {5, 10} else nonadj_moves)[s[-1]]:
        if ro not in s:
          ss_.append(s + (ro, ))
    ss = ss_
   
  # is there a colour where all "before yellow" < all "after yellow"
  for s in ss:  
    for k in range(3):
      # make string with only digits 3 and k 
      # (like k3-k3-3k-3k-3k-3k-k3-k3-3k-3k-3k-3k)
      s_3k = '-'.join([''.join(str(x) for x in y if x in {k, 3}) for y in s])
      f_3k = s_3k.index('3' + str(k))   # first 3k string
      
      if f_3k == 0: continue
      # all k3 strings must occur before first 3k string
      if s_3k[f_3k + 3:].find(str(k) + '3') >= 0: continue
      
      print("answer:", ''.join(colours[x] for x in s[-1]))
      break
  

  LikeLike

• 

  Frits 4:21 pm on 25 April 2023 Permalink | Reply

  John Crabtree said that it was not hard to determine the “particular colour”.
  The following code will reject two out of three colours.

   
  from itertools import permutations
  
  # the colours (K = black)
  colours = "BKRY"
  
  # possible running orders (blue before black)
  ps = list(p for p in permutations(range(4)) if p.index(0) < p.index(1))
  
  # return possible outcomes after a non-adjacent swap
  def n_adj(s):
    return set(((s[2], s[1], s[0], s[3]), 
                (s[3], s[1], s[2], s[0]), 
                (s[0], s[3], s[2], s[1])))
  
  particular_colours = []
  for k in range(3):
    a, b = [], []       # after/before
    for p in ps:
      (b if p.index(k) < p.index(3) else a).append(p)
    
    # the "after" group has at least 3 elements
    # with at least one non-adjacent move 
    if all(n_adj(e).isdisjoint(a) for e in a): continue
    particular_colours.append(colours[k])
  
  print("possible particular colours:", particular_colours) 
  

  LikeLike