S2T2

Jim Randell 3:13 pm on 18 July 2019 Permalink Reply
Tags: by: N A Phillips ( 5 )   

• 

  Jim Randell 3:14 pm on 18 July 2019 Permalink | Reply

  This Python program runs in 88ms.

  Run: [ @repl.it ]

  from enigma import subsets, update as _update, join, printf
  
  # possible names
  names = "ABCDE"
  
  # update a string with new items
  def update(s, js, vs):
    return join(_update(list(s), js, vs))
  
  # generate possible seating plans
  def generate(ss):
    # find unseated people, and empty places
    (xs, js) = (set(names), list())
    for (j, x) in enumerate(ss):
      if x == '?':
        js.append(j)
      else:
        xs.remove(x)
  
    # complete the seating plan
    for s in subsets(xs, size=len, select='P'):
      yield update(ss, js, s)
  
  # groups of adjacent and opposite seats: w -> m
  group = {
    0: [0, 1, 3],
    1: [1, 2, 4],
    2: [2, 3, 0],
    3: [3, 4, 1],
    4: [4, 0, 2],
  }
  
  # check no men reuse seats, apart from seat 0
  def m_check(ms, ss):
    for (i, x) in enumerate(ms):
      if i == 0: continue
      if any(s[i] == x for (s, _) in ss):
        return False
    return True
  
  # check no woman is seated opposite or next to her husband
  def w_check(ms, ws):
    for (i, w) in enumerate(ws):
      if any(ms[j] == w for j in group[i]):
        return False
    return True
  
  # find seating plans, given previous plans
  def solve(ms, ws, ss=[]):
  
    # complete the seating plan for the men
    for ms1 in generate(ms):
      if not m_check(ms1, ss): continue
  
      # complete the seating plan for the women
      for ws1 in generate(ws):
        if not w_check(ms1, ws1): continue
        yield (ms1, ws1)
  
  # find the January seating plan
  for Jan in solve('ABCDE', '??B??'):
  
    # find the April seating plan
    # Mrs D sits in the same place as in Jan
    ws = update('??C??', [Jan[1].index('D')], ['D'])
    for Apr in solve('A????', ws, [Jan]):
  
      # find the July seating plan
      # Mrs A sits in the same place as in April
      ws = update('??D??', [Apr[1].index('A')], ['A'])
      for Jul in solve('A????', ws, [Jan, Apr]):
  
        # find the October seating plan
        for Oct in solve('A????', '??E??', [Jan, Apr, Jul]):
  
          # output the seating plans
          printf("Jan={Jan[0]}+{Jan[1]} Apr={Apr[0]}+{Apr[1]} Jul={Jul[0]}+{Jul[1]} Oct={Oct[0]}+{Oct[1]}")
  

  Solution: The seating arrangement in October was:

  Mr A; Mrs B; Mr E; Mrs A; Mr D; Mrs E; Mr C; Mrs D; Mr B; Mrs C

  The other seating plans are:

  Jan = Mr A; Mrs E; Mr B; Mrs A; Mr C; Mrs B; Mr D; Mrs C; Mr E; Mrs D
  Apr = Mr A; Mrs B/E; Mr D; Mrs E/B; Mr B/E; Mrs C; Mr E/B; Mrs A; Mr C; Mrs D
  Jul = Mr A; Mrs E/B; Mr C; Mrs B/E; Mr E/B; Mrs D; Mr B/E; Mrs A; Mr D; Mrs C
  Oct = Mr A; Mrs B; Mr E; Mrs A; Mr D; Mrs E; Mr C; Mrs D; Mr B; Mrs C

  In places where there are options either the first or second option is used consistently throughout.

  LikeLike