26
\$\begingroup\$

Golf Me An OOP!

Two important components of object-oriented programming are inheritance and composition. Together, they allow for creating simple yet powerful class hierarchies to solve problems. Your task is to parse a series of statements about a class hierarchy, and answer questions about the hierarchy.

Input

A series of statements and questions about a class hierarchy, read from a file or standard input, whichever is best for your language. If you use the file option, the filename will be passed as the first argument to your code (function argument or command line argument, whichever you choose). The format is as follows:

<statement> : <name> is a <name>. | <name> has a <name>.
<question> : Is <name> a <name>? | Does <name> have a <name>?
<name> : a-z | A-Z | sequence of alphanumerics or underscores, starting with a letter

The input will always be statements, then questions. All class names will begin with an uppercase English letter (A-Z), and all member names will begin with a lowercase English letter (a-z). All names are case-sensitive - ABC123 is not the same class as Abc123.

There will not be any cyclical inheritance - if B inherits from A, A will not inherit from B or any of B's children.

Only class names will be a part of a hierarchy - statements such as foo is a bar. or document has a name. will not occur.

Output

A series of truthy or falsey values, as answers to the queries, written to standard output or as the return value of your function. If you do not have enough information to answer a question (e.g. questions that involve names you have not seen in the statements), answer with a falsey value.

Test Cases

Case 1:

Input:

B is a A.
C is a B.
A has a foo.
Does B have a foo?
Is C a A?
Is D a A?

Output:

True
True
False

Case 2:

Input:

Cop is a Person.
Criminal is a Person.
Sheriff is a Cop.
Crooked_Cop is a Cop.
Crooked_Cop is a Criminal.
BankRobber is a Criminal.
Cop has a badge.
Criminal has a criminal_record.
Person has a name.
Is Crooked_Cop a Person?
Does Criminal have a name?
Is Crooked_Cop a BankRobber?
Does Person have a potato?
Is Cop a Cop?

Output:

True
True
False
False
True

Rules

  • You may answer with a function or a program
  • Standard loopholes are forbidden
  • This is , so shortest correct answer in bytes wins
  • The winning answer will be chosen in one week

Good luck, and may the OOP be with you!

Leaderboard

The Stack Snippet at the bottom of this post generates the leaderboard from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

## Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

## Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

## Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the snippet:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table><script>var QUESTION_ID = 61097; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 45941; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>

\$\endgroup\$
  • \$\begingroup\$ How is Does Criminal have a name? equal to True? Do all objects have a name? \$\endgroup\$ – J Atkin Oct 17 '15 at 23:56
  • 4
    \$\begingroup\$ @JAtkin Criminal is a Person. Person has a name. \$\endgroup\$ – Reto Koradi Oct 18 '15 at 0:04
  • \$\begingroup\$ Ahh... I had missed that. \$\endgroup\$ – J Atkin Oct 18 '15 at 0:04
  • \$\begingroup\$ Do I need to take all the input at once, or can I take it line by line like a interactive console? If #2, can I output a truthy\falsey even if the input is a statment? \$\endgroup\$ – J Atkin Oct 18 '15 at 1:46
  • \$\begingroup\$ @JAtkin All at once or line-by-line, your choice. If it's a statement, there shouldn't be any output. Only questions get answers. \$\endgroup\$ – Mego Oct 18 '15 at 3:13
13
\$\begingroup\$

CJam, 59 bytes

q_'.e=\N/{)'?=\S/>_,(%}%/(__,*{(2$z~@f=.*\m*|}/ff{1$e=>:=N}

This finishes instantly for both test cases.

It either prints the second name name of the question or 1 (both truthy), or 0 (falsy).

Try it online in the CJam interpreter.

Idea

Because of the distinction between classes and members, the challenge boils down to creating a preorder for which the input provides a partial definition.

We define that xy iff x is a y or x has a y.

For the first test case, the input states that BA, CB and Afoo. Because of transitivity, we also have Bfoo, CA and Afoo. Also, because of reflexivity, xx is always true.

For a given input, we thus can extract the partial definition of ≺ from the statements, apply transitivity a sufficient amount of times to complete the definition of ≺ and finally answer the questions.

Code

q_     e# Push all input from STDIN and a copy.
'.e=   e# Count the number of dots/statements (C).
\N/    e# Split the original input at linefeeds.
{      e# For each line:
  )'?= e#   Pop the last character and check if it is a question mark.
       e#   Pushes 1 for '?', 0 for '.'.
  \S/  e#   Split the modified line at spaces.
  >    e#   Remove the first chunk ("Does" or "Is") for questions.
  _,(% e#   Keep the first and last element of the resulting array.
}%/    e# Split the line array into chunks of length C.
(_     e# Extract the first chunk (statements) and push a copy.
       e# The original becomes an accumulator for ≺.
_,*    e# Repeat the statements C times.
{      e# For each of the repeated statements:
  (    e#   Shift out the first name.
       e#     ["w" "x"] -> ["x"] "w"
  2$z~ e#   Copy the accumulator, zip it and dump.
       e#     [["x" "y"] ["z" "w"]] -> ["x" "z"] ["y" "w"]
  @f=  e#   Rotate the shifted out name on top and check for equality.
       e#     ["y" "w"] "w" -> [0 1]
  .*   e#   Vectorized string repetition.
       e#     ["x" "z"] [0 1] -> ["" "z"]
  \m*  e#   Swap the result with the shifted array and apply Cartesian product.
       e#     ["" "z"] ["x"] -> [["" "x"] ["z" "x"]]
       e#   This accounts for transitivity; we had ["w" "x"] and ["z" "w"],
       e#   so now we have ["z" "x"].
  |    e#   Perform set union with the accumulator to add the new pairs.
}/     e#
ff{    e# For each of the questions on the bottom of the stack.
  1$e= e#   Count the occurrences of the question pair in the accumulator.
  >    e#   Remove 0 or 1 elements from the question pair.
  :=   e#   Check for equality.
       e#   If the question pair occurs in the accumulator, this pushes the
       e#   second name of the question pair. Otherwise, it pushes 1 if the
       e#   names are equal (to account for reflexivity) and 0 otherwise.
  N    e#   Push a linefeed.
}      e#
\$\endgroup\$
  • 2
    \$\begingroup\$ This is impressive considering that CJam doesn't have classes :D \$\endgroup\$ – Beta Decay Oct 18 '15 at 8:43
  • \$\begingroup\$ This is beautiful. \$\endgroup\$ – Mego Oct 18 '15 at 16:37
8
\$\begingroup\$

Python 3, 431 331 308 bytes

o={}
f={}
def h(z,f):
 if z not in o:f[z]=[z];o[z]=[]
while 1:
 g=input().split(' ');r=2;l=g[-1][:-1]
 if'.'in g[3]:
  if'i'in g[1]:h(g[0],f);h(l,f);f[g[0]]+=f[l]
  if'h'in g[1]:o[g[0]]+=l,
 else:
  if'I'in g[0]:r=any(l in z for z in f[g[1]])
  if'D'in g[0]:r=any(l in o[z] for z in f[g[1]])
 if r<2:print(r)

This is the full version with comments

objects = {}
synonyms = {}

def createObject(name):
    """
    Create a object with `name` if is does not yet exist and start a synonym tree.
    """
    if name not in objects:
        synonyms[name] = [name]
        objects[name] = []

# use this to read from a file
# with open("questions.txt") as file: 
#     for l in file:
        # print(">>> " + l, end='')
        # inArg = l.replace("\n","").split(" ")


while True: # to read from a file comment this
        inArg = input(">>> ").split(" ") # and this out

        out = -1

        if '.' in inArg[3]: # statement
            last = inArg[3].replace('.','')

            if 'i' in inArg[1]: # is a
                createObject(inArg[0])
                createObject(last)
                synonyms[inArg[0]] += synonyms[last]

            if 'h' in inArg[1]: # has a
                objects[inArg[0]] += [last]

        else:# question
            last = inArg[-1].replace('?','')

            createObject(inArg[1])
            if 'I'in inArg[0]: # Is a
                out = any([last in syn for syn in synonyms[inArg[1]]])

            if 'D'in inArg[0]: # Does have a
                out = any(last in objects[syn] for syn in synonyms[inArg[1]])

        if out != -1:
            print(out)

Output for test case #1:

True
True
False

Case #2:

True
True
False
False
True

I removed the debug commands for clarity in the main program, but if you would like to see them just look in the history

\$\endgroup\$
  • \$\begingroup\$ Instead of using global f in h(z), use def h(z,f) and pass the global f in when calling it. In fact, you don't need h(z) at all - just put the body where you call it. You don't need r=2, and you can just do print(r) without the if, since you need to output a falsey value for false queries. You can rename syn to z and shave off several bytes there. I don't think you need the [] around your list comprehension in the first any. \$\endgroup\$ – Mego Oct 18 '15 at 23:37
  • \$\begingroup\$ You also use e once, so you can do away with the definition and just use [a,b,c,d]. Instead of if s(i,g) is not None, do if s(i,g) - re.Match objects are always evaluated to True if a match is found. You can also drop 2 bytes with f[x]+=f[y]. \$\endgroup\$ – Mego Oct 18 '15 at 23:42
  • \$\begingroup\$ @Mego Wow, thanks for all the tips. I'll need to put them in later. \$\endgroup\$ – J Atkin Oct 19 '15 at 0:36
  • \$\begingroup\$ This post will probably help you out a lot \$\endgroup\$ – Mego Oct 19 '15 at 0:43
  • \$\begingroup\$ @Mego Big thanks, its down to 396 now. I will post is shortly. \$\endgroup\$ – J Atkin Oct 19 '15 at 1:20
4
+50
\$\begingroup\$

Haskell, 157 bytes

o s=v(x 0#k)#(x 1#q)where(k,q)=break((=='?').l.l)(words#lines s)
x n w=(w!!n,init$l w)
v k(a,c)=a==c||or[v k(b,c)|b<-snd#(filter((==a).fst)k)]
(#)=map
l=last

Give the string to o. Not sure if making x and v ('extract' and 'verify') infixes cuts more than making map an infix, or if both is possible.

EDIT: Explanation

So, (#) is how you define an infix operator, I use it just as a shorthand for map, applying a function to each element of a list. Resolving this and the other alias l, avoiding the 'direct-function-application'-operator $ and adding even more parentheses and spacing things out, and with real function names we arrive at:

oop string = map (verify (map (extract 0) knowledge)) (map (extract 1) questions)
 where (knowledge,questions) = break ((=='?').last.last) (map words (lines string))

extract n wordlist = (wordlist!!n,init (last wordlist))

verify knowledge (a,c) = (a==c)
               || or [verify knowledge (b,c) | b <- map snd (filter ((==a).fst) knowledge)]

map words (lines string) is a list of word lists of each lines in the input string.

(=='?').last.last is a predicate indicating whether the last letter in the last word of a line is a question mark, i.e. whether the line is a question.

break breaks the list in a tuple of the first part without questions (all statements) and the part from the first question on (all questions).

mapping extract n on these takes out of each word list the elements we really want, the nth one (which in statements is the first word - so n == 0, and in questions is the second word - so n == 1) using the !! operator and the last one, from which we have to cut the last letter (either '.' or '?') using init.

(Note that I completetely ignore capitalization, that's because I completely ignore the distinction between classes and members, members are just leafs of a tree constructed by the knowledge base (but not all leafs represent members, they may also be classes with neither subclasses nor members), in which every child node represents a subclass or member of what its parent node represents. I JUST REALIZED THIS IS A WRONG THING TO DO in cases not covered by OP. Will edit solution soon.)

Now, map (extract 0) knowledge and map (extract 1) questions are lists of tuples of names representing a subclass- or member-relationship of the first to the second.

The tuples in map (extract 0) knowledge are all true relationships, those in map (extract 1) questions are now mapped the verify function over, with the first argument set to map (extract 0) knowledge.

(From now on, inside verify, knowledge is a parameter name and refers to the already extracted tuple list.)

(Also, when reading verify, note that while the || (after the inelegant linebreak to avoid horizontal-scroll on SE) is a normal boolean disjunction between the 'reflexive' and the 'recursive' case, or folds that over a list, i.e. checks if any list element is true.)

Now, a relations is obviously correct if it is reflexive. Strictly speaking, no, a potato does not have a potato (and it isn't even one in the sense 'is' is used here, as in 'A Cop is a Cop'), but that's just the termination condition that covers all relationships after walking down the tree (which unlike in the case of real trees means 'towards the leafs').

In all other cases, we try to take a tuple from knowledge (after we filtered to make sure we 'see' only pairs with the same first element as that we want to check), and go on from where it points to. The list comprehension deals with all possible tuple to continue with and calls verify again in each case. A dead end will just have an empty list here and return false overall, and so not influence the instance of verify it was called by.

\$\endgroup\$
  • \$\begingroup\$ Could you add a short explanation for non haskell fluent people? \$\endgroup\$ – J Atkin Nov 21 '15 at 15:13
  • \$\begingroup\$ Happily! I just don't do it for every post until requested. \$\endgroup\$ – Leif Willerts Nov 21 '15 at 18:29
  • \$\begingroup\$ Ok, thanks! (filler) \$\endgroup\$ – J Atkin Nov 21 '15 at 18:58
  • \$\begingroup\$ Wow, that's some explanation. \$\endgroup\$ – J Atkin Nov 21 '15 at 21:05
  • 2
    \$\begingroup\$ I just finished reading the first half of Learn you a haskell for great good! and this now I understand this! (This answer is actually what prompted me to learn more about haskell and FP, and it is sooooo cool!) \$\endgroup\$ – J Atkin Jan 3 '16 at 15:05
4
\$\begingroup\$

JavaScript, 265 263 bytes

for(o={};i=prompt().split(/\W/);)a=i[0],b=i[1],d=i[2],b=="is"?((o[a]=o[a]||{p:[],k:{}}).p.push(d),o[d]=o[d]||{p:[],k:{}}):b=="has"?o[a].k[d]=1:alert(o[b]&&(a>"E"?b==d|(c=n=>~(p=o[n].p).indexOf(d)|p.some(c))(b):(c=n=>o[n].k.hasOwnProperty(i[4])|o[n].p.some(c))(b)))

Enter a blank string to quit.

Explanation

for(
  o={};                               // o = all objects
  i=prompt().split(/\W/);             // i = command as an array of words
)
  a=i[0],                             // a = first word
  b=i[1],                             // b = second word
  //c=i[2],                           // c = third word
  d=i[3],                             // b = fourth word
  //e=i[4],                           // e = fifth word

  // Case: <name> is a <name>.
  b=="is"?(
    (o[a]=o[a]||{p:[],k:{}})          // create the object if it does not exist
      .p.push(d),                     // add the parent to the object's list of parents
    o[d]=o[d]||{p:[],k:{}}            // create the parent if it does not exist
  ):

  // Case: <name> has a <name>.
  b=="has"?
    o[a].k[d]=1                       // set the specified property

  :
  alert(                              // display the responses to the questions
    o[b]                              // false if the queried object does not exist
    &&(

      // Case: Is <name> a <name>?
      a>"E"?                          // "Is" > "E" and "Does" < "E"
        b==d                          // check if it is itself
        |(c=n=>
          ~(p=o[n].p)                 // p = direct parents of current object
            .indexOf(d)               // check direct parents for the object
          |p.some(c)                  // check the grandparents
        )(b)

      // Case: Does <name> have a <name>?
      :
        (c=n=>
          o[n].k.hasOwnProperty(i[4]) // check if this object has the property
          |o[n].p.some(c)             // check it's parents for the property also
        )(b)
    )
  )
\$\endgroup\$
  • \$\begingroup\$ Could you use string.split(" ");? \$\endgroup\$ – J Atkin Nov 21 '15 at 15:17
  • \$\begingroup\$ @JAtkin I used .match(/\w+/g) to remove the punctuation from the words. \$\endgroup\$ – user81655 Nov 22 '15 at 2:01
  • \$\begingroup\$ I saw that, but wouldn't .split(" ") be shorter or am I missing something? (I don't know javascript) \$\endgroup\$ – J Atkin Nov 22 '15 at 2:02
  • \$\begingroup\$ @JAtkin If I used .split I would also have to use .slice(0,-1) (twice) because B is a A. would make B inherit A. (with the .). \$\endgroup\$ – user81655 Nov 22 '15 at 2:28
  • \$\begingroup\$ @JAtkin Actually I just found out that split accepts regular expressions so I could use .split(/\W/). Thanks for causing me to look that up! \$\endgroup\$ – user81655 Nov 22 '15 at 2:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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