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:
- Podane stwierdzenia są prawidłowe, spójne i mają logiczną konsekwencję, że świnie mogą latać. W takim przypadku musisz wydrukować
Yes
. - Podane stwierdzenia są ważne, spójne i mają logiczną konsekwencję, że świnie nie mogą latać. W takim przypadku musisz wydrukować
No
. - Z podanych, ważnych i spójnych stwierdzeń nie można wywnioskować, czy świnie mogą latać, czy nie. W takim przypadku musisz wydrukować
Maybe
. - Podane instrukcje są poprawne, ale niespójne (tzn. Istnieje sprzeczność w podanych instrukcjach). Ponieważ ex falso quodlibet decydujemy się na wyjście
Yes
w tym przypadku. - 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.
źródło
Odpowiedzi:
Perl,
363353350347343297266264Niegolfowane / Objaśnienie:
źródło
Haskell,
586566547 bajtówNapisał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”.
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
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%.
źródło
u n=(:)<$>[t,f]<*>u(n-1)
(choć wymagałoby to importowania Control.Aplikacja, więc w drugiej chwili było gorzej)c l=(all(==l!!0)l,and l)
Python,
547536525521513509497503501Dla każdego
a -> b
z 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) aZeroDivisionError
i drukujemyYes
.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.źródło
try
blok w tej samej linii cotry:
Ruby 1.9.3 (
365 364362)Stosowanie
Kod powyżej definiuje funkcję
f
, której jeden parametr reprezentujący wprowadzania tekstu i powracaYes
,No
lubMaybe
.Na przykład:
Test online: http://ideone.com/fxLemg
Kod bez golfa (w tym testy jednostkowe) jest dostępny tutaj .
źródło