gistfile1.txt

def find_room_plans(plan, depth):
  if depth == 0:
    return [plan]
  prev = plan[-1]
  heads = [x[0] for x in prev]
  ret = []
  perms = []
  unique_permutations(heads, perms)
  for perm in perms:
    if any(x[0] == y[0] for x,y in zip(heads, perm)):
      continue
    next = [prev[x][1:] + perm[x] for x in range(len(perm))]
    ret.extend(find_room_plans(plan + [next], depth - 1))
  return ret

find_room_plans([["ABC", "DEF", "GHI"]], 8)

def score_room_plan(plan):
  ret = []
  
  rooms = [''.join(sorted(room)) for day in plan for room in day]
  alphabet = set(c for room in rooms for c in room)
  
  size_count = defaultdict(lambda: defaultdict(int))
  for day in plan:
    for room in day:
      for person in room:
        size_count[len(room)][person] += 1
  for size, people in sorted(size_count.items()):
    min_days = min(people[x] for x in alphabet)
    max_days = max(people[x] for x in alphabet)
    ret.append(max_days - min_days)
  
  max_tuple_size = max(len(x) for x in rooms) - 1
  for i in range(max_tuple_size, 1, -1):
    tuple_counts = defaultdict(int)
    for room in rooms:
      for t in itertools.combinations(room, i):
        tuple_counts[t] += 1
    ret.append(max(tuple_counts.values()) - min(tuple_counts.values()))
  
  ret.append(len(rooms) - len(set(rooms)))  # Number of non-distinct room arrangements
  
  return ret

def get_scored_plans(first, nights):
  plans = find_room_plans([first], nights - 1)
  plans = [score_room_plan(x) + (x,) for x in plans]
  plans.sort()
  return plans

def unique_permutations(l, ret, idx=0):
  if idx + 1 == len(l):
    ret.append(list(l))
  else:
    for i in range(idx + 1, len(l)):
      l[idx], l[i] = l[i], l[idx]
      unique_permutations(l, ret, idx + 1)
      l[idx], l[i] = l[i], l[idx]