Line up for golf!

Question

Alice, Bob, Carol, Dave, and Eve are going out for a nice game of golf and need your help to decide in what order they will play.

Your program will input some statements, which are defined as a condition, and then one or more optional logical boolean operators followed by another condition. (That's [Condition]([Logical][Condition])* in regexp notation.) A logical boolean operator is "and" or "or." You may chose either and or or to have higher precedence, as long as it is consistent.

A condition is a name, followed by the word "is," followed optionally by the word "not," followed by one of these:

• in front of
• behind
• n spaces in front of
• n spaces behind
• next to
• nth
• nth to last

An example of a valid condition is "Alice is not next to Bob".

Associativity is from left to right, except for "not," which only applies to a single statement. This means that "x or y and z or not a" means "((x or y) and z) or a," where x could be "Alice is 1st" or "Alice is behind Bob" or "Alice is not 2nd to last."

Your output must be the order in which the players line up, separated by commas, from front to back of the line.

Here's the full specification in regexp notation:

[Statement] = [FullCondition]([Logical][FullCondition])*
[FullCondition] = [Name] is [Condition]
[Condition] = (not)? (in front of|behind|[Number] space(s)? (in front of|behind)|next to|[Ordinal]|[Ordinal] to last)
[Logical] = and|or
[Number] = 1|2|3|4...
[Ordinal] = 1st|2nd|3rd|4th...

Standard methods of input and output. Input should be as a string, and output can be as a string or list. And finally, here are some sample inputs and outputs.

Input:
The players are Alice, Bob, and Carol.
Alice is 2nd.
Bob is in front of Alice.

Output:
Bob, Alice, Carol

Input:
The players are Alice, Bob, and Carol.
Alice is 1 space in front of Bob. // remember to handle pluralization correctly!
Carol is 1st to last.

Output:
Alice, Bob, Carol

Input:
The players are Alice, Bob, and Carol.
Alice is in front of Bob.

Output:
Alice, Bob, Carol
Carol, Alice, Bob // multiple outputs may be required

Input:
The players are Alice, Bob, and Carol.
Alice is in front of Bob.
Bob is in front of Alice.

Output:
// nothing

Input:
The players are Alice, Bob, and Carol.
Alice is not in front of Bob and Carol is not 2nd or Bob is 1st.

Output:
Carol, Bob, Alice
Bob, Alice, Carol
Bob, Carol, Alice

This is code-golf, so the shortest code in bytes will win!

A great many thanks to @Doorknob for posting this in the Secret Santa's Sandbox. Again, thank you.

Answer 1

JavaScript (ES6), 554 499 ... 463 bytes

Takes input as an array of strings and returns an array of arrays of strings. Parsing rule: and has higher precedence than or.

Below is a slightly formatted version. The compact version is included in the snippet.

([P,...C])=>
  [...Array(m=9349)]
  .map(_=>p[a=P.match(/[A-E]\w+/g).sort(_=>(k=k*2%m)&1)]?0:p[a]=a,p={},k=1)
  .filter(s=>
    s&&eval(
      C.join`and `.match(/.+?(or |and |$)/g)
      .map(s=>
        (
          c=s.match(/([A-E]\w+|\d|no|la|fr|be|x|p|or|an)/g),
          S=n=>`s.indexOf('${c[p+n]}')`,
          E=`]=='${c[0]}'`,
          c[p=1]=='no'?(p++,'!(s['):'(s['
        )+
        (
          (x=+c[p])&&p++,
          {
            la:'s.length-'+x+E,
            fr:F=S(1)+-1+E,
            be:B=S(1)+'+1'+E,
            x:F+'||s['+B,
            p:S(2)+(c[p+1]>'f'?-x:'+'+x)+E
          }[c[p]]||--x+E
        )+
        (c.pop()>'o'?')||':')&&')
      ).join``+1
    )
  )

How it works

1. Initialization

The input array is split into:

• P = first line, describing the players
• C = array containing all other lines

We first extract the names of all players from P:

P.match(/[A-E]\w+/g)

We compute all permutations of the names, using several iterations of sort():

sort(_ => (k = k*2 % 9349) & 1)

The prime 9349 was (empirically) chosen in such a way that all permutations are guaranteed to be found, given enough iterations of the sort, for up to 5 players.

2. Filtering

The main part of the function consists of filtering these permutations to keep only the ones that match all conditions in C.

We join the different condition lines with and and split the resulting string on or and and to get an array of conditions.

Each condition is parsed to isolate the relevant tokens:

Token          | RegExp part
---------------+------------
Name of player | [A-E]\w+
Digit          | \d
'not'          | no
'last'         | la
'in front of'  | fr
'behind'       | be
'next to'      | x
'spaces'       | p
'or'           | or
'and'          | an

Each condition is translated into JS code:

Condition                     | JS code
------------------------------+-------------------------------------------------------------
'X is Nth'                    | s[N - 1] == 'X'
'X is Nth to last'            | s[s.length - N] == 'X'
'X is in front of Y'          | s[s.indexOf('Y') - 1] == 'X'
'X is behind Y'               | s[s.indexOf('Y') + 1] == 'X'
'X is next to Y'              | s[s.indexOf('Y') - 1] == 'X' || s[s.indexOf('Y') + 1] == 'X'
'X is N spaces in front of Y' | s[s.indexOf('Y') - N] == 'X'
'X is N spaces behind Y'      | s[s.indexOf('Y') + N] == 'X'

Finally, all codes are joined with || and && operators and the resulting string is eval()'d.

For example, below are the translations of the test cases as JS code:

(s[1]=='Alice')&&(s[s.indexOf('Alice')-1]=='Bob')&&1
(s[s.indexOf('Bob')-1]=='Alice')&&(s[s.length-1]=='Carol')&&1
(s[s.indexOf('Bob')-1]=='Alice')&&1
(s[s.indexOf('Bob')-1]=='Alice')&&(s[s.indexOf('Alice')-1]=='Bob')&&1
!(s[s.indexOf('Bob')-1]=='Alice')&&!(s[1]=='Carol')||(s[0]=='Bob')&&1

Test cases

let f =

([P,...C])=>[...Array(m=9349)].map(_=>p[a=P.match(/[A-E]\w+/g).sort(_=>(k=k*2%m)&1)]?0:p[a]=a,p={},k=1).filter(s=>s&&eval(C.join`and `.match(/.+?(or |and |$)/g).map(s=>(c=s.match(/([A-E]\w+|\d|no|la|fr|be|x|p|or|an)/g),S=n=>`s.indexOf('${c[p+n]}')`,E=`]=='${c[0]}'`,c[p=1]=='no'?(p++,'!(s['):'(s[')+((x=+c[p])&&p++,{la:'s.length-'+x+E,fr:F=S(1)+-1+E,be:B=S(1)+'+1'+E,x:F+'||s['+B,p:S(2)+(c[p+1]>'f'?-x:'+'+x)+E}[c[p]]||--x+E)+(c.pop()>'o'?')||':')&&')).join``+1))

console.log(JSON.stringify(f([
  'The players are Alice, Bob and Carol.',
  'Alice is 2nd.',
  'Bob is in front of Alice.'
])));

console.log(JSON.stringify(f([
  'The players are Alice, Bob, and Carol.',
  'Alice is 1 space in front of Bob.',
  'Carol is 1st to last.'
])));

console.log(JSON.stringify(f([
  'The players are Alice, Bob, and Carol.',
  'Alice is in front of Bob.'
])));

console.log(JSON.stringify(f([
  'The players are Alice, Bob, and Carol.',
  'Alice is in front of Bob.',
  'Bob is in front of Alice.'
])));

console.log(JSON.stringify(f([
  'The players are Alice, Bob, and Carol.',
  'Alice is not in front of Bob and Carol is not 2nd or Bob is 1st.'
])));

Answer 2

Python 3, 527 524 511 bytes

import re,itertools as I
S=re.sub
p=re.findall(r"\w+(?=[,.])",input())
l=[]
try:
 while 1:
  c=[["not "*("not "in c)+S(" .+o (.+)",r" in[\1+1,\1-1]",S(" .+f","+1==",S(" .+d","-1==",S(r" .+(\d+).+",r"+1==\1",S(r" .+(\d+).+st",r"==len(p)-\1",S(r" .+(\d+).+f",r"+\1==",S(r" .+(\d+) .+d",r"-\1==",c[:-1]))))))),c][len(c)<7]for c in re.split("(or|and) ",input())]
  while c[1:]:c[:3]=["("+" ".join(c[:3])+")"]
  l+=[c[0]]
except:print([P for P in I.permutations(p)if eval("and ".join(l),dict(zip(P,range(len(p)))))])

Try it online!

Outputs an array of valid permutations. Expects the names to only contain A-Za-z0-9_ (Alice through Eve are obviously valid).

Answer 3

PHP, way too long (790 744 725 697 678 669 bytes)

foreach(file(F)as$i=>$s)if($i){$g("#(.*)( and | or |\.)#U",$s,$w,2);foreach($w as $q){preg_match("#^(\w+)(.*?)(\w+)$#",$q[1],$m);$n=$u[-3+$p=($o=strpos)($u=$m[2],p)];$d.="!"[!$o($u,no)]."(".strtr(!$o($u,x)?A.($o($u,f)?$p?"==B-$n":"<B":($o($u,b)?$p?"==B+$n":">B":"==".preg_replace("#.*(\d).*#",($k=$o($u,a))?"$z-$1":"$1",$k?$u:$m[3]))):"(A-B)**2<2",[A=>$m[1],B=>$m[3]]).")$q[2]";}$d=!$x.="&"[!$x]."($d)";}else{($g=preg_match_all)("#(\w+)[.,]#",$s,$m);$z=count($y=$m[1]);}for(;$j++<10**$z;)if(count_chars($p="$j",3)==join(range(1,$i=$z))){for($c=$x;$i--;)$c=strtr($c,["."=>"","not"=>"",$y[$p[$i]-1]=>$i+1]);for(;eval("return$c;")&++$i<$z;)echo$y[$p[$i]-1],"
,"[$i<$z-1];}

takes input from file F, no trailing newline; and before or. Run with -nr or test it online.

breakdown

foreach(file(F)as$i=>$s)if($i)              # loop through input lines
{
    $g("#(.*)( and | or |\.)#U",$s,$w,2);       # split statement to conditions
    foreach($w as $q)
    {
        preg_match("#^(\w+)(.*?)(\w+)$#",$q[1],$m); # 1. copy names to $m[1],$m[3]
        $n=$u[-3+$p=($o=strpos)($u=$m[2],p)];       # 2. remove names, 3. find N in "N spaces"
        $d.="!"[!$o($u,no)]."(".                    # 4. negate, 6. concatenate
            strtr(                                  # 5. translate condition:
            !$o($u,x)
            ?A.($o($u,f)?$p?"==B-$n":"<B"               # (N spaces) in front of
            :($o($u,b)?$p?"==B+$n":">B"                 # (N spaces) behind
            :"==".preg_replace("#.*(\d).*#",            # N-th
                ($k=$o($u,a))?"$z-$1":"$1"                  # ... (to last)
                ,$k?$u:$m[3])
            ))
            :"(A-B)**2<2"                               # next to
        ,[A=>$m[1],B=>$m[3]])
        .")$q[2]";
    }
    $d=!$x.="&"[!$x]."($d)";                    # concatenate statements, clear statement
}else                                           # first line: import names to $y, count to $z
{($g=preg_match_all)("#(\w+)[.,]#",$s,$m);$z=count($y=$m[1]);}
                                            # loop through combinations
for(;$j++<10**$z;)if(count_chars($p="$j",3)==join(range(1,$i=$z))){
    for($c=$x;$i--;)                            # remove dot and "not", replace names
        $c=strtr($c,["."=>"","not"=>"",$y[$p[$i]-1]=>$i+1]);
                                                # all conditions met? print combination!
    for(;eval("return$c;")&++$i<$z;)echo$y[$p[$i]-1],"\n,"[$i<$z-1];
}