Your task is to write a function or a program in a language of your choice that analyzes a couple of statements and determines whether it can be concluded from those statements that pigs are able to fly.


The input is a String that can be read from STDIN, taken as a function argument or even be stored in a file. The input can be described using the following 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" ;

Example input (see more examples below):

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


The output can be returned by your function, be written to a file or print to STDOUT. There are 5 different cases to be handled:

  1. The given statements are valid, consistent and have as a logical consequence that pigs can fly. In that case, you must output Yes.
  2. The given statements are valid, consistent and have as a logical consequence that pigs can not fly. In that case, you must output No.
  3. It can not be concluded from the given, valid and consistent statements whether pigs can fly or not. In that case, you must output Maybe.
  4. The given statements are valid, but not consistent (i.e. there's a contradiction in the given statements). Since ex falso quodlibet, we decide to output Yes in that case.
  5. The given statements are not valid, i.e. they are not formatted according to the given EBNF. In that case, you may do whatever you want.


  • You may assume that the given attributes are independent from each other. So, for example, a pig may be young and old, green, red and blue at the same time without causing any inconsistency. However, a pig may not be 'green' and 'not green' at the same time, that's a contradiction and should be handled as described in (4).
  • For every attribute, assume that there is at least one object (not necessarily a pig) in the universe that has the given attribute, and one object that doesn't have it.

Example Inputs & Outputs


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

Output: Since Pigs are green and therefore intelligent, and everything that is able to fly is not intelligent, pigs cannot fly. Output is No.


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

Output: If pigs were not able to fly, they were also not old. But as they are old, you must output Yes.


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

Output: Maybe.


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

Output: Although the first statement implies that pigs can not fly, the following statements contradict each other and therefore the output must be Yes.


Pigs are very smart. Pigs are able to fly. 

Output: Whatever you want, as the String doesn't match the criteria mentioned above.


This is , so the shortest correct answer (in bytes) wins. The winner will be chosen one week after the first correct answer is posted.

A flying Pig

  • \$\begingroup\$ why does the third example return yes? \$\endgroup\$
    – xem
    Commented Aug 2, 2014 at 19:27
  • 11
    \$\begingroup\$ I'm considering writing an answer that translates the input into Prolog code. \$\endgroup\$
    – Tal
    Commented Aug 2, 2014 at 20:36
  • 2
    \$\begingroup\$ You can only conclude that nothing red exists. Sweet, non-red things are fine. \$\endgroup\$ Commented Aug 2, 2014 at 23:59
  • 1
    \$\begingroup\$ I was hoping for more examples, just so I can do them myself. \$\endgroup\$
    – cjfaure
    Commented Aug 3, 2014 at 16:37
  • 1
    \$\begingroup\$ @xem: ex falso quodlibet, look it up on wikipedia as the principle of explosion. If a contradiction exists, then anything can be proven. So if 'god exists' is true and 'god does not exist' is true, anything can be shown to be true, therefore pigs can fly can be proven true. \$\endgroup\$ Commented Sep 19, 2014 at 5:30

4 Answers 4


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


# 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\."
  # 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"
# For all known source attributes ... (this should really be keys%h but we dont mind the extra hashrefs)
sub r
  # ... 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
  # ... remember that we processed this attribute for the current source attribute so we prevent loops ...
  # ... add a new fact and then follow the chains (again omitting keys).
# Did we happen on an inconsistency? Do pigs fly? Dont pigs fly? Maybe (Bitwise or is okay too)
  • 4
    \$\begingroup\$ Would be great if you could tell us how it does work / write some comments! \$\endgroup\$
    – flawr
    Commented Aug 3, 2014 at 7:45
  • \$\begingroup\$ And another upvote for more comments... anything in particular need more explanation? \$\endgroup\$
    – Thaylon
    Commented Aug 4, 2014 at 23:00
  • \$\begingroup\$ Added even more comments ... \$\endgroup\$
    – Thaylon
    Commented Aug 6, 2014 at 9:46
  • \$\begingroup\$ @AlanBerndt suggested a postfix while. Since he cant comment and I cant approve. I'd like to say thanks! here. \$\endgroup\$
    – Thaylon
    Commented Aug 6, 2014 at 19:01

Haskell, 586 566 547 bytes

I wrote this on the assumption that for every property P there must exist some x and y such that P(x) is true and P(y) is false; without this assumption, the fourth example input wouldn't have a contradiction and would answer "No".

#define X p s q m
#define W where
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%(w:z)=(maybe(l s,s++[w#l s])(#s)$lookup w s,z,t)
main=interact$p[""#0]id id.words.r(/='.')

This should be compiled with the ghc command line option "-cpp". Input must be terminated by EOF (^D). You can try it online at http://melpon.org/wandbox/, but you cannot set command line options. Instead, you can prefix the program with the language option


It works by collecting the set of traits, then filtering the set of trait -> truth valuations using the implications in the input. The result is then tested to ensure that every trait can be validly assigned to both True and False (failure here is the ex falso quodlibet case). Finally, it looks for valuations which match the pig facts, checking the value for "able to fly" in each valuation.

Quite a few bytes were lost to threading state around: the set of traits seen so far, the pig-fact-selector function, and the filtering function determined by the implications. Probably the exact same idea would be much shorter in an impure language.

Edit: Saved several bytes by proud haskeller's suggestion, then a couple extra by replacing the binding of z and "u%drop 2 z" with a binding to "_ : _ : z" and "u%z", saving 3.

Edit 2: Saved some more. Used the (#)=(,) trick to save 2 bytes and learned about pattern synonyms (https://ghc.haskell.org/trac/ghc/wiki/PatternSynonyms), but the notation was too verbose to get a savings from eliminating the rest of the pairs in this program. Squeezed out some more savings by changing the patterns that the parser searches for. For example: if a sentence doesn't start with Pigs and we have anything left in the parser state, we parse a "Everything that is.." sentence. This saved lots of characters in the patterns for X and %.

  • \$\begingroup\$ Your assumption is correct, I forgot to mention it in the first place but I've now added it to the details section! \$\endgroup\$
    – vauge
    Commented Aug 3, 2014 at 6:51
  • 2
    \$\begingroup\$ You should include the flags in your byte count (see the tag wiki for code-golf). Therefore, it's 607 bytes. \$\endgroup\$
    – user344
    Commented Aug 3, 2014 at 11:42
  • \$\begingroup\$ Is that really correct? The link only mentions flags related to unicode encodings; meta mentions a similar issue regarding C++ flags -D (an obvious cheat) vs -std=c++11 (selecting a specific language variation, so probably ok). IMO the flags used are for enabling a rather common GHC extension of Haskell98, hence analogous to -std=c++11. Ref: meta.codegolf.stackexchange.com/questions/1859/… \$\endgroup\$ Commented Aug 3, 2014 at 20:30
  • \$\begingroup\$ you can replace your second definition of u with u n=(:)<$>[t,f]<*>u(n-1) (although this would require importing Control.Applicative, so in second thought it is worse) \$\endgroup\$ Commented Aug 4, 2014 at 2:01
  • 1
    \$\begingroup\$ you do can replace the definition of c with c l=(all(==l!!0)l,and l) \$\endgroup\$ Commented Aug 4, 2014 at 2:22

Python, 547 536 525 521 513 509 497 503 501

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):
 while 1:
  for r in i:n|=R.get(r,n)
  if X(i)>=n:return i
try:a='able to fly';n=N(a);c={n:'No','':'Maybe'}[''.join({a,n}&m(F,R)[0])]
print c

For each a -> b in the input, we add the given clause and its negation not b -> not a to the set of clauses and then compute the set of propositions that are ->-reachable from any proposition using a fixpoint loop. Whenever we encounter a contradiction, we throw (and later catch) a ZeroDivisionError and print Yes.

Finally, we check if 'able to fly' (and/or its negation) is reachable from the 'is pig' proposition '' and print the appropriate response.

EDIT: This is buggy, fixing it. Fixed.

  • 1
    \$\begingroup\$ you should be able to save 2 bytes by putting the try block on the same line as try: \$\endgroup\$ Commented Aug 4, 2014 at 5:31
  • \$\begingroup\$ @undergroundmonorail: thanks for spotting that! changed it. \$\endgroup\$ Commented Aug 4, 2014 at 9:54

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


The code above defines a function f, which takes one parameter representing the textual input and returns Yes, No, or Maybe.

For example:

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

Online test: http://ideone.com/fxLemg

The ungolfed code (including unit tests) is available here.

  • \$\begingroup\$ *are available (under header "online test"). Plurals, my good friend. \$\endgroup\$
    – Stan Strum
    Commented Oct 31, 2017 at 19:47
  • \$\begingroup\$ @StanStrum Thanks! I modified the text - I mean the code is available and it also includes unit tests. \$\endgroup\$ Commented Nov 1, 2017 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.