Свиньи могут летать?

45

задача

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

вход

Входные данные представляют собой строку, которую можно прочитать из STDIN, принять в качестве аргумента функции или даже сохранить в файле. Входные данные могут быть описаны с использованием следующего EBNF:

input = statement , {statement};
statement = (("Pigs are ", attribute) | ("Everything that is ", attribute, "is also ", attribute)), ". ";
attribute = [not], ("able to fly" | singleAttribute);
singleAttribute = letter, {letter};
letter = "a" | "b" | "c" | "d" | "e" | "f" | "g"
       | "h" | "i" | "j" | "k" | "l" | "m" | "n"
       | "o" | "p" | "q" | "r" | "s" | "t" | "u"
       | "v" | "w" | "x" | "y" | "z" ;

Пример ввода (см. Дополнительные примеры ниже):

Pigs are green. Everything that is green is also intelligent. Everything that is able to fly is also not intelligent. Pigs are sweet. 

Выход

Вывод может быть возвращен вашей функцией, записан в файл или распечатан в STDOUT. Есть 5 различных случаев, которые нужно обработать:

  1. Данные утверждения являются действительными, последовательными и имеют в качестве логического следствия, что свиньи могут летать. В этом случае вы должны вывести Yes.
  2. Данные утверждения являются действительными, последовательными и имеют логическое следствие того, что свиньи не могут летать. В этом случае вы должны вывести No.
  3. Из приведенных, действительных и последовательных утверждений нельзя сделать вывод, могут ли свиньи летать или нет. В этом случае вы должны вывести Maybe.
  4. Данные утверждения являются действительными, но не последовательными (т.е. в данных утверждениях есть противоречие). Так как ex falso quodlibet , мы решаем выводить Yesв этом случае.
  5. Данные утверждения недействительны, то есть они не отформатированы в соответствии с данным EBNF. В этом случае вы можете делать все, что хотите.

Детали

  • Вы можете предположить, что данные атрибуты независимы друг от друга. Так, например, свинья может быть молодой и старой, зеленой, красной и синей одновременно, не вызывая каких-либо противоречий. Однако свинья не может быть «зеленой» и «не зеленой» в одно и то же время, это противоречит и должно рассматриваться, как описано в (4).
  • Для каждого атрибута предположим, что в юниверсе есть хотя бы один объект (не обязательно свинья), у которого есть данный атрибут, и один объект, у которого его нет.

Пример входов и выходов

Входные данные:

Pigs are green. Everything that is green is also intelligent. Everything that is able to fly is also not intelligent. 

Вывод: поскольку свиньи зеленые и, следовательно, умные, а все, что умеет летать, не разумно, свиньи не могут летать. Выход есть No.

Входные данные:

Pigs are old. Everything that is not able to fly is also not old. 

Вывод: если свиньи не могли летать, они также не были старыми. Но так как они старые, вы должны вывести Yes.

Входные данные:

Everything that is sweet is also not old. Everything that is intelligent is also blue. 

Выход: Maybe .

Входные данные:

Pigs are not able to fly. Everything that is red is also sweet. Everything that is sweet is also not red. 

Вывод: хотя первое утверждение подразумевает, что свиньи не могут летать, следующие утверждения противоречат друг другу, и поэтому вывод должен быть Yes.

Входные данные:

Pigs are very smart. Pigs are able to fly. 

Вывод: все, что вы хотите, так как строка не соответствует критериям, указанным выше.

победитель

Это , поэтому выигрывает самый короткий правильный ответ (в байтах). Победитель будет выбран через неделю после публикации первого правильного ответа.

Летающая свинья

vauge
источник
почему третий пример возвращает да?
xem
10
Я подумываю написать ответ, который переведет ввод в код Пролога.
Тал
1
Вы можете только заключить, что ничего красного не существует. Сладкие, не красные вещи в порядке.
user2357112 поддерживает Monica
1
Я надеялся на дополнительные примеры, просто чтобы я мог сделать их сам.
cjfaure
1
@xem: ex falso quodlibet, посмотрите на Википедию как на принцип взрыва. Если существует противоречие, то все может быть доказано. Таким образом, если «Бог существует» - это правда, а «Бог не существует» - это правда, все, что может быть доказано, является правдой, поэтому свиньи могут летать, и это может быть доказано.
боец истребителя

Ответы:

10

Perl, 363 353 350 347 343 297 266 264

$_=<>;s/able to fly/X/g;$m=' ?(not )?\b(P|\w+)';$h{$1?N.$2:$2}{$3?N.$4:$4}=$h{$3?$4:N.$4}{$1?$2:N.$2}=1while s/$m.{8}$m\.//;map{%x=0,r($_,$_)}%h;sub r{($a,$b)=@_;$e+=$h{$a}{N.$b};$x{$b}++or$h{$a}{$b}=1,map{r($a,$_)}%{$h{$b}}}print$e|$h{P}{X}?Yes:$h{P}{NX}?No:Maybe

Ungolfed / Пояснение:

# Read one line from STDIN
$_=<>;
# Replaces special attribute with X
s/able to fly/X/g;
# Prepare attribute match
$m=' ?(not )?\b(P|\w+)';
# Match "Everything that is A is also B. "
#                        "\bA........ \bB\."
# Match "Pigs are B. "
#     "\bP........\bB\."
while(s/$m.{8}$m\.//)
{
  # Add facts for A => B and !B => !A, where A may equal "P" for "Pigs are"
  # Facts are stored as a hash of hashes %h; keys%h are the source attributes;
  # keys%{$h{$a}} are the attributes that follow from attribute $a
  # A "not attribute" is stored as "Nattribute", while a "attribute" is just stored as "attribute"
  $h{$1?N.$2:$2}{$3?N.$4:$4}=$h{$3?$4:N.$4}{$1?$2:N.$2}=1
}
# For all known source attributes ... (this should really be keys%h but we dont mind the extra hashrefs)
map{%x=0,r($_,$_)}%h;
sub r
{
  ($a,$b)=@_;
  # ... remember that we hit a negation and therefor an inconsistency ...
  # If we check/add $b and find an existing "N$b" that means that attribute $b is supposed to be true and not true at the same time
  # It is cheaper bytewise to just add up all consistency errors (remember each fact has a hard value of 1) than to exit right here
  $e+=$h{$a}{N.$b};
  # ... remember that we processed this attribute for the current source attribute so we prevent loops ...
  $x{$b}++or
  # ... add a new fact and then follow the chains (again omitting keys).
  $h{$a}{$b}=1,map{r($a,$_)}%{$h{$b}}
}
# Did we happen on an inconsistency? Do pigs fly? Dont pigs fly? Maybe (Bitwise or is okay too)
print$e|$h{P}{X}?Yes:$h{P}{NX}?No:Maybe
Thaylon
источник
4
Было бы здорово, если бы вы могли рассказать нам, как это работает / написать несколько комментариев!
Flawr
И еще одно возражение для большего количества комментариев ... что-нибудь конкретное нуждается в большем количестве объяснений?
Тайлон
Добавлено еще больше комментариев ...
Thaylon
@AlanBerndt предложил постфикс пока. Так как он не может комментировать, а я не могу одобрить. Я хотел бы сказать спасибо! Вот.
Тайлон
10

Haskell, 586 566 547 байт

Я написал это в предположении, что для каждого свойства P должно существовать несколько x и y, таких, что P (x) истинно, а P (y) ложно; без этого предположения входные данные четвертого примера не имели бы противоречия и отвечали бы «нет».

#define X p s q m
#define W where
t=0<1;f=0>1;y="Yes"
l=length;r=filter;h=head;(#)=(,)
u 0=[[]];u n=[x:y|x<-[t,f],y<-u$n-1]
c l=all(==h l)l#and l
X[]|or[fst$c$map(!!(n-1))e|n<-[1..l$h e]]=y|z t=y|z f="No"|t="Maybe"W e=m$u$l s;z m=t#m==(c$map h$q e)
X("Pigs":_:y)=p v((r$(==a).(!!k)).q)m z W((k,v),z,a)=s%y
X(_:_:_:y)=p w q((r(\x->(x!!j/=a)||(x!!k==b))).m)v W((j,u),_:_:z,a)=s%y;((k,w),v,b)=u%z
s%("not":w)=(i,u,not p)W(i,u,p)=s%w
s%(_:"to":_:w)=(0#s,w,t)
s%(w:z)=(maybe(l s,s++[w#l s])(#s)$lookup w s,z,t)
main=interact$p[""#0]id id.words.r(/='.')

Это должно быть скомпилировано с опцией командной строки ghc "-cpp". Ввод должен быть завершен EOF (^ D). Вы можете попробовать это онлайн на http://melpon.org/wandbox/ , но вы не можете установить параметры командной строки. Вместо этого вы можете добавить в программу префикс языка

{-# LANGUAGE CPP #-}

Он работает, собирая набор признаков, затем фильтруя набор характеристик -> истинностных оценок, используя значения во входных данных. Затем результат проверяется, чтобы удостовериться, что каждая черта может быть правильно назначена как True, так и False (неудача здесь - это случай ex falso quodlibet ). Наконец, он ищет оценки, которые соответствуют фактам свиньи, проверяя значение «способен летать» в каждой оценке.

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

Изменить: Сохранение нескольких байтов по предложению гордого haskeller, а затем пару дополнительных путем замены привязки z и "u% drop 2 z" с привязкой к "_: _: z" и "u% z", сохраняя 3.

Редактировать 2: Сохранено еще немного. Использовал трюк (#) = (,), чтобы сохранить 2 байта, и узнал о синонимах шаблонов ( https://ghc.haskell.org/trac/ghc/wiki/PatternSynonyms ), но запись была слишком многословной, чтобы получить экономию от устранение остальных пар в этой программе. Выжали немного больше экономии, изменив шаблоны, которые ищет синтаксический анализатор. Например: если предложение не начинается с Pigs и у нас что-то осталось в состоянии синтаксического анализатора, мы анализируем предложение «Все, что есть ..». Это сохранило много символов в шаблонах для X и%.

Мэтт Нунан
источник
Ваше предположение верно, я забыл упомянуть об этом в первую очередь, но теперь я добавил его в раздел деталей!
Vauge
2
Вы должны включить флаги в ваш счетчик байтов (см. Тег wiki для code-golf ). Следовательно, это 607 байтов.
nyuszika7h
Это действительно правильно? В ссылке упоминаются только флаги, связанные с кодировкой Unicode; В meta упоминается аналогичная проблема, касающаяся флагов C ++ -D (очевидный обман) vs -std = c ++ 11 (выбор конкретного варианта языка, так что, вероятно, все в порядке). IMO, используемые флаги для включения довольно распространенного расширения GHC для Haskell98, следовательно, аналогично -std = c ++ 11. Ссылка: meta.codegolf.stackexchange.com/questions/1859/…
Мэтт Нунан
вы можете заменить ваше второе определение на u u n=(:)<$>[t,f]<*>u(n-1)(хотя для этого потребуется импортировать Control.Applicative, так что, во-вторых, это хуже)
гордый haskeller
1
Вы можете заменить определение c наc l=(all(==l!!0)l,and l)
гордый haskeller
6

Питон, 547 536 525 521 513 509 497 503 501

m=map
o='not ';R={'':{''}}
S=lambda x,y:filter(len,m(str.strip,x.split(y)))
N=lambda a:[o+a,a[4:]][a[:4]==o]
def C(s):a,c=S(s[19:],'is also');return[(a,c),(N(c),N(a))]
X=lambda A:A&set(m(N,A))and 1/0 or A
for a,c in sum(m(lambda x:[('',x[9:])]if'P'==x[0]else C(x),S(raw_input(),'.')),[]):R.setdefault(a,{a}).add(c)
def F(s):
 i,n={s},{s}
 while 1:
  for r in i:n|=R.get(r,n)
  if X(i)>=n:return i
  i|=n
try:a='able to fly';n=N(a);c={n:'No','':'Maybe'}[''.join({a,n}&m(F,R)[0])]
except:c='Yes'
print c

Для каждого a -> bиз входных данных мы добавляем данное предложение и его отрицание not b -> not a к набору предложений, а затем вычисляем набор предложений, которые ->достижимы из любого предложения, используя цикл с фиксированной точкой. Всякий раз, когда мы сталкиваемся с противоречием, мы бросаем (а потом ловим) a ZeroDivisionErrorи печатаем Yes.

Наконец, мы проверяем, достижимо ли «летать» (и / или его отрицание) из предложения «является свиньей», ''и печатаем соответствующий ответ.

РЕДАКТИРОВАТЬ : Это глючит, исправить это. Исправлена.

user2361830
источник
1
Вы должны быть в состоянии сэкономить 2 байта, поместив tryблок в ту же строку, что иtry:
подземный
@undergroundmonorail: спасибо, что заметили это! изменил это.
user2361830
5

Рубин 1.9.3 ( 365 364 362)

h='able to fly'
i="(not )?(#{h}|\\w+)"
o=->s{n=Regexp.new(i+" (is also|are) "+i).match s
[[n[2],!n[1]],[n[5],!n[4]]]}
c=e=!z=[]
w=->r{z.member?(r)||(z<<(a,b=r)
c|=a[0]==b[0]&&a[1]!=b[1]
w[[[b[0],!b[1]],[a[0],!a[1]]]]
z.map{|q|q[1]==r[0]&&w[[q[0],r[1]]]})}
y=->x{z.member?([[p='Pigs',!e],[h,x]])}
f=->x{x.split(?.).map{|s|w[o[s]]}
c|y[!e]?'Yes':y[e]?'No':'Maybe'}

использование

Выше код определяет функцию f, которая принимает один параметр , представляющий текстовый ввод и возвращается Yes, Noили Maybe.

Например:

f['Pigs are old. Everything that is not able to fly is also not old.']
=> "Yes"

Онлайн тест: http://ideone.com/fxLemg

Разгруженный код (включая юнит-тесты) доступен здесь .

Кристиан Лупаску
источник
* доступны (под заголовком «онлайн тест»). Множественное число, мой хороший друг.
Стэн Струм
@StanStrum Спасибо! Я изменил текст - я имею в виду код является доступным и он также включает в себя модульные тесты.
Кристиан Лупаску