Find the conflict-free sitting arrangement

Question

Party time! All of your guests are sitting around a round table, but they have very particular seating requirements. Let's write a program to organize them automatically!

Guests are represented by letters: Female guests are uppercase, males are lowercase. Couples have the same letter, one lower and one upper, like gG, who just had their golden marriage (congrats!).

The rules

1. Neither place a male between two other males nor a female between two other females.
2. Couples must sit next to each other.
3. Alphabetically adjacent letters of the same sex are rivals! Never place two rivals next to each other (like BA) or a rival next to the partner of an attendant partner (like bBc, but xaBcz is fine, because none of them have jealous partners at the party). Answering a comment: Aand Z are not adjacent in any alphabet I'm aware of. (-;

I/O

You may take input as either a string or a list of letters [a-zA-Z] _{*(or, only if your language of choice has no characters, integers from 1 to 52 representing them, males are even, females are odd :-)}, which will always be unique (i.e. no duplicates). Remember: this is a round table, so ensure that your answer takes wrapping into account.

Your output has to be at least one of all possible table arrangements for the input. Where the cut is doesn't matter. If no valid arrangements exist for the input, give an output of your choice which is obviously no sitting arrangement, from an ugly program crash over empty output to some polite message (sorry, no extra score for that).

Examples

A       --> A (boring party, but valid)
BbCc    --> <none>
gdefEDH --> HfdDgeE
OMG     --> <none>
hiJk    --> <none>
hMJkK   --> hJMkK
NoP     --> NoP
rt      --> rt
qQXZxyz --> <none>
BIGbang --> bIgGanB

(P.S.: In case you miss same-sex couples, non-binaries, polycules, and such – I like those at my personal party, but not in this challenge, to keep it simple.)

Answer 1

Ruby, 151 bytes

f=->x{[x,x[1..-1]+x[0]].any?{|g|a=g.upcase
g=~/[a-z]{3}|[A-Z]{3}/||a=~/(.).+\1/||a.bytes.each_cons(2).any?{|a,b|(a-b).abs==1}}?f[x.chars.shuffle*'']:x}

Try it online!

Shuffles input until valid, if can't find shuffles forever as undefined behavior

Answer 2

Python3, 486 bytes:

R=lambda a,b:chr(ord(a)+1)!=b and chr(ord(a)-1)!=b
K=lambda a,b:len(a)<2or a[-2].islower()!=b.islower()
V=lambda a,i:K(a,i)and R(a[-1],i)and(len(a)<2 or R(a[-2],i))
def f(s):
 q=[(i,{*s}-{i})for i in s]
 for a,b in q:
  if not b:
   if V(a,a[0]):return a
   continue
  if(T:=a[-1].upper())in b:
   if K(a,T):q+=[(a+T,b-{T})];q+=[(T+a,b-{T})]*(len(a)==1)
  elif(T:=a[-1].lower())in b:
   if K(a,T):q+=[(a+T,b-{T})];q+=[(T+a,b-{T})]*(len(a)==1)
  else:q+=[(a+i,b-{i})for i in b if V(a,i)]

Try it online!

A little long, but not naive brute force.

Answer 3

Jelly, 49 37 bytes

O-ṫ?3;Od32ạƝS‘1¦Ʋ3Ƥ;ạƝ’Ʋ;ŒuĠIỊƲȦ
Œ!ÇƇ

Try it online!

(shows just one example for each case for brevity)

Thanks to @JonathanAllan for saving 2 bytes!

A pair of monadic links taking a list of characters and returning a list of lists of characters. Returns all possible arrangements except those where a couple is split across the join.

Handling inputs with length 1 and 2 added more complexity than I would have expected!

Explanation (outdated)

ŒuĠIỊ;O.ịjƊ;-$L>2Ɗ?:96E3Ƥ;%32IASƲ3Ƥ;IỊƲƲ¬ƲȦ  # ‎⁡Helper link: takes a list of characters and returns 1 if it’s a valid arrangement and 0 if not
Œu                                           # ‎⁢Convert to upper case
  Ġ                                          # ‎⁣Indices of like-members (partners here) grouped together
   I                                         # ‎⁤Increments within each group
    Ị                                        # ‎⁢⁡<= 1 (overall, this tests for rule 2; i.e. indices of partners are adjacent 
     ;                                   Ʋ   # ‎⁢⁢Concatenate to the following, applied to the original helper link argument:
      O                                      # ‎⁢⁣- Convert to codepoints
              L>2Ɗ?                          # ‎⁢⁤- If length of list >2:
       .ịjƊ                                  # ‎⁣⁡  - Then: Take the last and first members of the list, and respectively prepend and append them
           ;-$                               # ‎⁣⁢  - Else: Concatenate -1
                                       Ʋ     # ‎⁣⁣- Following as a monad (argument to this is referred to as a in description below):
                   :96                       # ‎⁣⁤  - z div 96
                      E3Ƥ                    # ‎⁤⁡  - Check whether each overlapping infix length 3 has three equal values
                         ;            Ʋ      # ‎⁤⁢  - Concatenate to the result of the following applied to z:
                                Ʋ3Ƥ          # ‎⁤⁣    - Apply the following to each infix of z of length 3:
                          %32                # ‎⁤⁤    - Mod 32
                             I               # ‎⁢⁡⁡    - Increments
                               S             # ‎⁢⁡⁢    - Sum
                              A              # ‎⁢⁡⁣    - Absolute
                                   ;I        # ‎⁢⁡⁤    - Concatenate to increments of z
                                     Ị       # ‎⁢⁢⁡    - Absolute of this <= 1
                                        ¬    # ‎⁢⁢⁢- Not
                                          Ȧ  # ‎⁢⁢⁣Any and all (flattened list contains no zeros)

Œ!ÇƇ                                         # ‎⁢⁣⁡Main link: takes a list of characters and returns a list of lists of characters
Œ!                                           # ‎⁢⁣⁢All permutations
  ÇƇ                                         # ‎⁢⁣⁣Keep those where the helper link returns 1
💎

Created with the help of Luminespire.

Answer 4

05AB1E, 44 43 40 bytes

œʒā._»A3ãDu«åylDÔsÙÊyĆÇüαyĆlÇüαĆü«Dí)˜≠P

Outputs a list of all valid table-arrangements, or [] if none are. (If this is not allowed, ʒ can be .Δ for +1 byte, so it'll output the first valid result, or -1 if none are.)

Try it online. (Times out after 60 seconds, only outputting some of the valid results.)

Here a slightly modified version (A3ãDu« to Dáü3Dlsu«) which is fast enough to output all test cases:
Try it online or verify all test cases.

Explanation:

œ                 # Get all permutations of the (implicit) input
 ʒ                # Filter the list of permutation-strings by:
  ā._»A3ãDu«å)˜≠P #  Verify rule 1:
  ā               #   Push a list in the range [1,length] (without popping)
   ._             #   For each value, convert it to a rotation of the permutation
     »            #   Join this list of rotation-strings by newlines
      A           #   Push the lowercase alphabet
       3ã         #   Cartesian power of 3 to create all possible lowercase triplets
         D        #   Duplicate this list of triplets
          u       #   Uppercase each string in the copy
           «      #   Merge the lowercase and uppercase lists of triplets together
            å     #   Check for each triplet if it's a substring of the joined
                  #   rotations of the current permutation
             ...  #   (rules 2 and 3)
             )    #   Wrap all checked rules into a list (of lists/values)
              ˜   #   Flatten it
               ≠P #   Verify that none are truthy
  ylDÔsÙÊ)˜≠P     #  Verify rule 2:
  y               #   Push the permutation string again
   l              #   Convert the string to lowercase
    D             #   Duplicate it
     Ô            #   Connected uniquify its characters
      s           #   Swap so the lowercase string is at the top again
       Ù          #   Regular uniquify its characters
        Ê         #   Check that they are NOT the same
         ...      #   (rule 3)
         )˜≠P     #   Same as above: verify that it's not truthy,
                  #   which is why we've used an inverted equals-check `Ê` here
  yĆÇüα)˜≠P       #  Verify rule 3a:
  y               #   Push the permutation string yet again
   Ć              #   Enclose; append its own first character
    Ç             #   Convert it to a list of codepoint integers
     ü            #   For each overlapping pair:
      α           #    Get the absolute difference
       ...        #   (rule 3b)
       )˜≠P       #   Same as above: verify that none are 1
  yĆlÇüαĆü«Dí)˜≠P #  Verify rule 3b:
  y               #   Push the permutation string yet again
   Ć              #   Enclose; append its own first character
    l             #   Convert it to lowercase
     Ç            #   Convert it to a list of codepoint integers
      üα          #   For each overlapping pair: Get the absolute difference
        Ć         #   Enclose this list as well
         ü«       #   Join each overlapping pair of integers together to a string
           D      #   Duplicate this list of integer-strings
            í     #   Reverse each string in the copy
             )˜≠P #   Same as above: verify that none are "01"
                  # (after which the filtered list is output implicitly)

Answer 5

sed -E,  455  448 bytes

(theoretically 447 bytes, see explanation, but who cares as long as sed beats python?!)

I finally added my own reference implementation using sed just because regex-golfing is fun.

G
s/./&_-/
:1
s/(\S*)_(\S*)-(\S)(\S*\n)/\1\3_-\2\4\1_\2\3-\4/
t1
s/[-_]//g
h
:2
g
/^$/q
s/\S*.//
x
s/\n.*//
s/(..)?.+/aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ #:&\1/
:r  
/:#/b4
/^(..)*(.)(.)(.)(.).*(\2\4|\3\5\3\2\5|\2\3\4|\3\4\5|\2\5\4)/b2
/(.).(..)*(.).(..)*(.).* .*(\1\3\5|\1\5\3|\3\1\5)/b2
:3
s/ (.*:)(.)/ \2\1/
t3
s/(\S*):/:\1/
br  
:4
s/^((..)*)(.)(.)(.*(\3\4|\4\3))/\1\5/
t4
/^(..)*(.)(.).*(\2.+\3|\3.+\2)/b2
s/.*#(..)?(...*)/\2/

It's brute force, with the 1 loop producing all combinations of guests, ignoring duplicates in favor of size over speed. Yes, you could save one more byte with s/^/_-/ in line two, but this will create so extremely amounts of duplicates that it will time out even for quite small parties.

The 2 loop takes one combination after another from the hold space to test it. I need to waste a lot of bytes to teach sed the alphabet, but at the same time I can close the round table by duplicating the first two guest at the end. Here I originally had a giant regex for the rival test and another regex for the three-of-the-same-sex-test, both backwards and forwards. But then I discovered that the extra bytes for reverting the string in loop 3 and using loop r to check the reversed order pays out by having only half of the expressions.

The test for couples sitting apart was more tricky: A simple regex check won't work, because if they are at the first two seats, they will look like sitting apart because of the first partner reappearing on the other end. I solved it by removing couples I found sitting next to each other from the alphabet in loop 4 before testing. I wonder if there are still some bytes to save!

Try it online!

Answer 6

Charcoal, 158 133 131 114 bytes

≔§θ⁰η⊞υηＦυ«≔⁻⪪θ¹⪪ι¹ζＦ∨ζη«≔⁺κιδ¿∨‹Ｌδ³﹪ΣＥ…δ³№αλ³¿⬤⁻ζ⟦κ⟧¬№↥⁻ιη↥λ¿⊖↔⁻℅↥κ℅↥§ι⁰¿ζ⊞υδ¿∨‹Ｌι³﹪ΣＥ…⁺§ι⁰⮌ι³№αλ³¿¬№↥✂ι¹±²¦¹↥η⟦ι

Try it online! Link is to verbose version of code. Always places the first guest last but will output each solution twice, once with the guests in reverse order. Explanation:

≔§θ⁰η

Get the first guest.

⊞υηＦυ«

Start a breadth-first search with just the first guest seated so far.

≔⁻⪪θ¹⪪ι¹ζ

Get the unplaced guests. (There is an alternative way of doing this using the newer version of Charcoal on ATO which is the same length but allows for a two byte saving later on.)

Ｆ∨ζη«

If there are unplaced guests, then loop over the guests, otherwise just check the first guest can sit after the last guest.

≔⁺κιδ

Get the updated placement.

¿∨‹Ｌδ³﹪ΣＥ…δ³№αλ³

Except on the first pass, check that this doesn't cause there to be three men or women in a row, by checking that the number of the last three guests which are women is not a multiple of 3. (The two guests sitting on either side of the first guest are checked later.)

¿⬤⁻ζ⟦κ⟧¬№↥⁻ιη↥λ

Check that this doesn't separate a guest from their spouse. (The first guest's spouse is checked later.)

¿⊖↔⁻℅↥κ℅↥ε

Check that this doesn't place a guest next to a rival.

¿ζ

If there are more guests to check, then...

⊞υδ

... save the updated placement for later processing.

¿∨‹Ｌι³﹪ΣＥ…⁺§ι⁰⮌ι³№αλ³

Check that the first guest is not the middle of three men or women in a row.

¿¬№↥✂ι¹±²¦¹↥η

Check that the first guest is sitting next to their spouse (if present).

⟦ι

Output the found placement on its own line.