Фон

Есть два человека, Билл и Джон. Один из них - рыцарь, который всегда говорит правду, а другой - мошенник, который всегда говорит ложь. Вы не знаете, кто рыцарь, а кто мошенник. Затем каждый говорит несколько утверждений о том, кто мошенник, а кто рыцарь. Используя эту информацию, вы должны прийти к выводу, кто рыцарь, а кто мошенник.

Логическая задача Рыцарей и мошенников основана на Booleen алгебре. Слова, которые произносит человек, образуют проблему булевской выполнимости. Заявления мошенника всегда должны быть ложными, а заявления другого рыцаря всегда должны быть правдой.

Джон говорит: «И я мошенник, а Билл мошенник». Если бы Джон был рыцарем, то это утверждение было бы ложным, поэтому он не мог быть рыцарем. Если бы он был мошенником, а Билл - рыцарем, это утверждение было бы ложным, даже если бы первая часть была правдой. Итак, Джон мошенник.

Соревнование

Ваша задача состоит в том, чтобы написать самую короткую возможную программу, которая будет содержать список утверждений, сделанных каждым человеком, и выяснить, кто мошенник, а кто рыцарь. Здесь есть много деталей, поэтому эта проблема описана в трех разделах.

вход

Ввод будет состоять из двух строк, за которыми следует новая строка. В каждой строке будет указано имя одного из символов, за которым следует двоеточие, а затем несколько предложений, произнесенных этим человеком. Если один человек является рыцарем, то все его предложения будут верными, а все предложения мошенника будут ложными. Первая буква предложения всегда будет написана заглавными буквами, а каждое предложение будет заканчиваться точкой. Вот пример:

Joe: Both I am a knight and neither Steve is a knave nor I am a knave.
Steve: Joe is a knave. Either Joe is a knight or I am a knight.

анализ

Каждое предложение состоит как минимум из одного предложения. Каждый пункт содержит одну из нескольких вещей (надеюсь, вы понимаете мою запись):

both [clause] and [clause]
either [clause] or [clause]
neither [clause] nor [clause]
[I am | (other person's name) is] a [knight | knave]

Это недвусмысленно, потому что это может быть понято так же, как польская запись. Вот пример предложения:

Both I am a knight and neither Steve is a knave nor I am a knave.

Перевод в булеву алгебру прост. «Оба» являются оператором «И», «любой» является XOR, а оператор «ни» является NOR.

(I am a knight) AND ((Steve is a knave) NOR (I am a knave))

Выход

Выход будет состоять из двух строк. Каждая строка состоит из имени человека (по порядку) и затем говорит, является ли он рыцарем или мошенником. Всегда будет один рыцарь и один мошенник. Вот вывод для приведенного выше примера:

Joe is the knave.
Steve is the knight.

Если проблема неразрешима (либо вы не можете сказать, кто есть что, либо решения не существует), тогда ваша программа может делать все, КРОМЕ, кроме правильного вывода.

Больше примеров

вход

Sir Lancelot: Either both I am a knight and Merlin is a knave or both I am a knave and Merlin is a knight.
Merlin: Either both I am a knight and Sir Lancelot is a knight or both I am a knave and Sir Lancelot is a knave.

Выход

Sir Lancelot is the knight.
Merlin is the knave.

вход

David: Neither I am a knave nor Patrick is a knight. Either I am a knight or Patrick is a knave.
Patrick: Either I am a knight or both I am a knight and David is a knight.

Выход

David is the knave.
Patrick is the knight.

вход

Lizard: I am a knight.
Spock: I am a knave.

Один возможный выход

Rock Paper Scissors

Правила, положения и примечания

1. Применяются стандартные правила игры в гольф
2. Ваша программа должна состоять только из печатного ASCII
3. Все входные и выходные данные будут от STDIN и STDOUT

Питон, 491 символ

Работает путем преобразования каждой строки в выражение Python и его оценки.
Мошенник и рыцарь оцениваются как 0 и 1. Для двух человек мы пробуем оба варианта.
Например, Joe: Steve is a knaveстановится Joe==(Steve==knave). Таким образом, если Joeэто мошенник, результат верен, только если он лжет.
Вы получаете ужасные ошибки, когда это невозможно или не решено. Если невозможно, r[0]это ошибка индекса, потому что rпусто. Если неразрешимо, конкатенация r[1:]со списком строк вызывает проблемы.

import sys
def p():
    a=s.pop(0)
    try:return{"both":"(%s*%s)","either":"(%s|%s)","neither":"(1-(%s|%s))"}[a.lower()]%(p(),p())
    except KeyError:r=s[2];del s[:4];return"(%s==%s)"%((a,m)[a=="I"],r)
x=[];w=[]
for l in sys.stdin:
    m,l=l.split(":");w+=[m]
    for s in l.split("."):
        s=s.split()
        while s:x+=["%s==%s"%(m,p())]
k=("knave","knight")
r=[a for a in[{w[0]:z,w[1]:1-z}for z in(0,1)]if all(eval(l,{k[0]:0,k[1]:1},a)for l in x)]
print"\n".join(x+" is the "+k[r[0][x]]+"."for x in w+r[1:])

Рубин, 352 персонажа

Решение стало довольно длинным, так что, возможно, еще есть место для гольфа. Требуется, чтобы входные данные были правильно сформированы (как и все приведенные выше примеры - но не пытайтесь назвать человека «Оба» ...).

q=->{gets.split /: |\.\s/}
C,*E=q[]
D,*F=q[]
r=->c,m{t=c.shift;t[1]?(x=r[c,m];c.shift;y=r[c,m];t[0]==?B?x&y :t[0]==?E?x^y :1-(x|y)):(c.shift(2);h=c.shift[2]==?I?m : 1-m;t==?I?h :1-h)}
s=->u,v,b{u.map{|c|r[c.gsub(v,?J).upcase.split,b]==b}.all?}
t=->b{s[E,D,b]&&s[F,C,1-b]}
u=->v,b{v+" is the kn#{b ?:ight: :ave}."}
puts t[1]^t[0]&&u[C,t[1]]+$/+u[D,t[0]]

Perl - 483 байта

(($a,$b),($c,$d))=map{split':'}@ARGV;$h='y';$i='x';$s=' is the kn';$g='ight.';$v='ave.';for($b,$d){$_.=' 1';s/ am a | is a /==/g;s/knight/1)/g;s/knave/0)/g;s/I=/(\$$i=/g;s/($a|$c)=/(\$$h=/g;s/([^.]+)\./($1)and/g;s/ or / xor /g;s/ nor / or /g;while(s/(?<= )(\w+ \((?:[^()]+|(?1))\) \w+ \((?:[^()]+|(?1))\))/($1)/g){}s/neither/!/gi;s/both|either//gi;$h=$i++}$x=0;$y=1;$k=!eval($b)&&eval($d);$x=$y--;$n=!eval($d)&&eval($b);print"$a$s$v
$c$s$g"if($k&&!$n);print"$a$s$g
$c$s$v"if($n&&!$k)

Похоже на решение Python. Он сводит предложения к Perl-коду, а затем evalс ними. Он может печатать почти действительный вывод, если ввод странный, но ничего не печатает, если он неразрешим. Хорошо сформированный ввод работает как ожидалось. Предложения передаются в командной строке внутри кавычек, и никаких специальных флагов не требуется.