Zadanie

Twoim zadaniem jest napisanie funkcji lub programu w wybranym języku, który analizuje kilka instrukcji i określa, czy można wywnioskować z tych instrukcji, że świnie są w stanie latać.

Wejście

Dane wejściowe to ciąg znaków, który można odczytać ze STDIN, wziąć jako argument funkcji lub nawet zapisać w pliku. Dane wejściowe można opisać za pomocą następującego 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" ;

Przykładowe dane wejściowe (zobacz więcej przykładów poniżej):

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

Wynik

Dane wyjściowe mogą zostać zwrócone przez twoją funkcję, zapisane w pliku lub wydrukowane do STDOUT. Do rozwiązania jest 5 różnych przypadków:

1. Podane stwierdzenia są prawidłowe, spójne i mają logiczną konsekwencję, że świnie mogą latać. W takim przypadku musisz wydrukować Yes.
2. Podane stwierdzenia są ważne, spójne i mają logiczną konsekwencję, że świnie nie mogą latać. W takim przypadku musisz wydrukować No.
3. Z podanych, ważnych i spójnych stwierdzeń nie można wywnioskować, czy świnie mogą latać, czy nie. W takim przypadku musisz wydrukować Maybe.
4. Podane instrukcje są poprawne, ale niespójne (tzn. Istnieje sprzeczność w podanych instrukcjach). Ponieważ ex falso quodlibet decydujemy się na wyjście Yesw tym przypadku.
5. Podane instrukcje są niepoprawne, tzn. Nie są sformatowane zgodnie z danym EBNF. W takim przypadku możesz zrobić, co chcesz.

Detale

• Możesz założyć, że podane atrybuty są od siebie niezależne. Na przykład świnia może być jednocześnie młoda i stara, zielona, ​​czerwona i niebieska jednocześnie, nie powodując niespójności. Jednak świnia może nie być jednocześnie „zielona” i „nie zielona”, co stanowi sprzeczność i należy z nią postępować zgodnie z opisem w (4).
• Dla każdego atrybutu załóżmy, że istnieje co najmniej jeden obiekt (niekoniecznie świnia) we wszechświecie, który ma dany atrybut, i jeden obiekt, który go nie ma.

Przykładowe wejścia i wyjścia

Wejście:

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

Wyjście: ponieważ świnie są zielone, a zatem inteligentne, a wszystko, co potrafi latać, nie jest inteligentne, świnie nie mogą latać. Dane wyjściowe to No.

Wejście:

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

Wyjście: jeśli świnie nie były w stanie latać, nie były również stare. Ale ponieważ są one stare, musisz generować dane wyjściowe Yes.

Wejście:

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

Wyjście: Maybe .

Wejście:

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

Wyjście: Chociaż pierwsze stwierdzenie sugeruje, że świnie nie mogą latać, poniższe stwierdzenia są ze sobą sprzeczne i dlatego wynik musi być Yes.

Wejście:

Pigs are very smart. Pigs are able to fly. 

Dane wyjściowe: Cokolwiek chcesz, ponieważ ciąg nie spełnia kryteriów wymienionych powyżej.

Zwycięzca

To jest golf golfowy , więc wygrywa najkrótsza poprawna odpowiedź (w bajtach). Zwycięzca zostanie wybrany tydzień po opublikowaniu pierwszej poprawnej odpowiedzi.

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

Niegolfowane / Objaśnienie:

# 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

Haskell, 586 566 547 bajtów

Napisałem to na założeniu, że dla każdej własności P musi istnieć jakieś X i Y takie, że P (x) jest prawdziwe i P (Y) jest fałszem; bez tego założenia czwarty przykład danych wejściowych nie miałby sprzeczności i odpowiedziałby „Nie”.

#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(/='.')

Powinno to zostać skompilowane z opcją wiersza polecenia ghc „-cpp”. Wejście musi być zakończone przez EOF (^ D). Możesz spróbować online na http://melpon.org/wandbox/ , ale nie możesz ustawić opcji wiersza poleceń. Zamiast tego możesz poprzedzić program opcją języka

{-# LANGUAGE CPP #-}

Działa poprzez zebranie zestawu cech, a następnie filtrowanie zestawu wycen cechy -> prawdy przy użyciu implikacji z danych wejściowych. Wynik jest następnie testowany, aby upewnić się, że każdą cechę można poprawnie przypisać zarówno Prawdzie, jak i Fałszowi (tutaj niepowodzenie jest przypadkiem ex falso quodlibet ). Wreszcie, szuka wycen, które pasują do faktów na temat świni, sprawdzając wartość „w stanie latać” w każdej wycenie.

Kilka bajtów zostało utraconych do stanu wątkowania wokół: zbioru cech do tej pory obserwowanych, funkcji selekcji faktów świni i funkcji filtrowania określonej przez implikacje. Prawdopodobnie ten sam pomysł byłby znacznie krótszy w nieczystym języku.

Edycja: Zapisano kilka bajtów dzięki sugestii dumnego haskellera, a następnie kilka dodatkowych, zastępując wiązanie z i „u% upuść 2 z” powiązaniem z „_: _: z” i „u% z”, oszczędzając 3.

Edycja 2: Zapisałem trochę więcej. Użyłem sztuczki (#) = (,), aby zaoszczędzić 2 bajty i poznałem synonimy wzorców ( https://ghc.haskell.org/trac/ghc/wiki/PatternSynonim ), ale notacja była zbyt szczegółowa, aby uzyskać oszczędności z eliminując resztę par w tym programie. Wycisnąć więcej oszczędności, zmieniając wzorce, których szuka parser. Na przykład: jeśli zdanie nie zaczyna się od Świnie i pozostało nam cokolwiek w stanie analizatora, analizujemy zdanie „Wszystko, co jest…”. To zapisało wiele znaków we wzorach dla X i%.

Python, 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

Dla każdego a -> bz danych wejściowych dodajemy podaną klauzulę i jej negację not b -> not a do zestawu klauzul, a następnie obliczamy zestaw zdań, które są ->osiągalne z dowolnego zdania przy użyciu pętli punktu stałego. Ilekroć napotykamy sprzeczność, rzucamy (a później łapiemy) a ZeroDivisionErrori drukujemy Yes.

Na koniec sprawdzamy, czy „zdolny do latania” (i / lub jego negacji) jest osiągalny z propozycji „jest świnia” ''i drukujemy odpowiednią odpowiedź.

EDYCJA : To jest błąd, naprawianie go. Naprawiony.

Ruby 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'}

Stosowanie

Kod powyżej definiuje funkcję f, której jeden parametr reprezentujący wprowadzania tekstu i powraca Yes, Nolub Maybe.

Na przykład:

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

Test online: http://ideone.com/fxLemg

Kod bez golfa (w tym testy jednostkowe) jest dostępny tutaj .