28
\$\begingroup\$

This is a code-golf challenge whereby you need to devise a program that acts like a quine or a quine that modifies itself to illustrate machine learning.

Background

There is a basic artificial intelligence program called 'the pangolin game' which is described here. The basic ideas is that the program when run the first time asks:

OK, please think of something

Is it a pangolin?

You may then reply either:

Yes

In which case it says:

Good. That was soooo easy.

Or if not it says:

Oh. Well you win then -- What were you thinking of?

To which you might say:

a dog

To which it would say

Please give me a question about a dog, so I can tell the difference between a dog and a pangolin

you might reply

Does it eat ants?

It would then ask:

What is the answer for a dog?

To which you would say

no

And it would say

Thanks

Next time it runs, it would ask the question above, and would build up a binary tree of such questions.

The challenge

Enough of the background. This challenge is to write a self modifying pangolin program. The rules are as follows:

  1. Program output (as described above) should be to STDERR. The final response will always be "Good. That was soooo easy." or "Thanks". After this, it should output either the current version of the program, or a new version of the program that incorporates the question to STDOUT. No answer written in a language that does not support writing to STDOUT and STDERR or reading from STDIN will be valid.

  2. In other words under UNIX you could invoke the program like this:

example:

$ mylanguage myprogram > myprogram.1
[dialog goes here]
$ mylanguage myprogram1 > myprogram.2
[dialog goes here]
  1. The program has to use exactly the specified prompts (because shortening the prompts shows no skill). The prompts are (without the quotes, and where %s is substituted) as follows:

list:

"OK, please think of something"
"Is it %s?"
"Good. That was soooo easy."
"Oh. Well you win then -- What were you thinking of?"
"Please give me a question about %s, so I can tell the difference between %s and %s"
"What is the answer for %s?"
"Thanks"
  1. When expecting yes/no answers, your program should accept y or yes in any case for 'yes', and n or no in any case for 'no'. What you do with non-conforming inputs is up to you. For instance you might decide to take any answer that begins with y or Y as 'yes', and anything else as no.

  2. You may assume that the names of the things supplied and the questions consist only ASCII letters, numbers, spaces, hyphens, question marks, commas, full stops, colons, and semicolons, i.e. they match following regex ^[-?,.;: a-zA-Z]+$. If you can cope with more than that (especially the quoting characters in your chosen language) you get to be smug, but don't gain any extra points.

  3. Your program may not read or write any file (excluding STDIN, STDOUT, and STDERR), or from the network; specifically it may neither read nor write its own code from disk. Its state must be saved in the program code itself.

  4. When the program is run and guesses the answer correctly, it must perform exactly as a quine, i.e. it must write to STDOUT exactly its own code, unchanged.

  5. When the program is run and guesses the answer incorrectly, it must encode the provided new question and answer within its own code and write it to STDOUT in its own code, so it is capable of distinguishing between its original guess and the provided new object, in addition to distinguishing between all previously given objects.

  6. You must be able to cope with multiple sequential runs of the software so it learns about many objects. See here for examples of multiple runs.

  7. Test runs are given at the link in the head (obviously covering only the STDIN and STDERR dialog).

  8. Standard loopholes are excluded.

\$\endgroup\$
  • \$\begingroup\$ Should the program be able to mutate multiple times and support more than 2 animals? If so, can you provide an example "Please give me a question about ..." dialogue when there are already two or more animals the program knows about? \$\endgroup\$ – Cristian Lupascu Sep 7 '15 at 7:24
  • \$\begingroup\$ What if the user only says "dog" instead of "a dog"? Shall we parse the sentence to detect "a/an" or can we treat the answer literally? I assume so given the prompts you gave (%s). \$\endgroup\$ – coredump Sep 7 '15 at 8:45
  • 1
    \$\begingroup\$ @coredump if the user says "dog" not "a dog", then the replies will not be grammatical. That's not an issue. \$\endgroup\$ – abligh Sep 7 '15 at 8:55
  • 1
    \$\begingroup\$ Oof. Trying to do this in Runic would be a nightmare. The primary reason being that wiring up all the bits to cope with arbitrary input strings (which then need to be present as string literals in the resulting output program) would be basically impossible. Oh and Runic can't output to STDERR. \$\endgroup\$ – Draco18s Jun 23 at 21:38
  • 1
    \$\begingroup\$ This seemed like a fun "game", so rather than golf it, I made a codepen where you can play the Pangolin Game to your heart's content. Enjoy! \$\endgroup\$ – Skidsdev Jun 26 at 20:11
20
\$\begingroup\$

Common Lisp, 631 576

(let((X"a pangolin"))#1=(labels((U(M &AUX(S *QUERY-IO*))(IF(STRINGP M)(IF(Y-OR-N-P"Is it ~A?"M)(PROG1 M(FORMAT S"Good. That was soooo easy.~%"))(LET*((N(PROGN(FORMAT S"Oh. Well you win then -- What were you thinking of?~%")#2=(READ-LINE S)))(Q(PROGN(FORMAT S"Please give me a question about ~A, so I can tell the difference between ~A and ~A~%"N N M)#2#)))(PROG1(IF(Y-OR-N-P"What is the answer for ~A?"N)`(,Q ,N ,M)`(,Q ,M ,N))(FORMAT S"Thanks~%"))))(DESTRUCTURING-BIND(Q Y N)M(IF(Y-OR-N-P Q)`(,Q ,(U Y),N)`(,Q ,Y,(U N)))))))(write(list'let(list`(X',(U x)))'#1#):circle t)()))

Example session

Name the script pango1.lisp and execute as follows (using SBCL):

~$ sbcl --noinform --quit --load pango1.lisp > pango2.lisp
Is it a pangolin? (y or n) n
Oh. Well you win then -- What were you thinking of?
a cat
Please give me a question about a cat, so I can tell the difference between a cat and a pangolin
Does it sleep a lot?
What is the answer for a cat? (y or n) y
Thanks

Another round, adding the bear:

~$ sbcl --noinform --quit --load pango2.lisp > pango3.lisp
Does it sleep a lot? (y or n) y

Is it a cat? (y or n) n
Oh. Well you win then -- What were you thinking of?
a bear
Please give me a question about a bear, so I can tell the difference between a bear and a cat
Does it hibernate?
What is the answer for a bear? (y or n) y
Thanks

Adding a sloth (we test the case where the answer is "no"):

~$ sbcl --noinform --quit --load pango3.lisp > pango4.lisp
Does it sleep a lot? (y or n) y

Does it hibernate? (y or n) n

Is it a cat? (y or n) n
Oh. Well you win then -- What were you thinking of?
a sloth
Please give me a question about a sloth, so I can tell the difference between a sloth and a cat
Does it move fast?
What is the answer for a sloth? (y or n) n
Thanks

Testing the last file:

~$ sbcl --noinform --quit --load pango4.lisp > pango5.lisp
Does it sleep a lot? (y or n) y

Does it hibernate? (y or n) n

Does it move fast? (y or n) y

Is it a cat? (y or n) y
Good. That was soooo easy.

Remarks

  • I first forgot printing "Thanks", here it is.
  • As you can see, questions are followed by (y or n), which is because I'am using the existing y-or-n-p function. I can update the answer to remove this output if needed.
  • Common Lisp has a bidirectional *QUERY-IO* stream dedicated to user-interaction, which is what I'am using here. Standard output and user-interaction do not mess, which follows IMHO the spirit of the question.
  • Using SAVE-LISP-AND-DIE would be a better approach in practice.

Generated output

Here is the last generated script:

(LET ((X
       '("Does it sleep a lot?"
              ("Does it hibernate?" "a bear"
               ("Does it move fast?" "a cat" "a sloth"))
              "a pangolin")))
  #1=(LABELS ((U (M &AUX (S *QUERY-IO*))
                (IF (STRINGP M)
                    (IF (Y-OR-N-P "Is it ~A?" M)
                        (PROG1 M (FORMAT S "Good. That was soooo easy.~%"))
                        (LET* ((N
                                (PROGN
                                 (FORMAT S
                                         "Oh. Well you win then -- What were you thinking of?~%")
                                 #2=(READ-LINE S)))
                               (Q
                                (PROGN
                                 (FORMAT S
                                         "Please give me a question about ~A, so I can tell the difference between ~A and ~A~%" 
                                         N N M)
                                 #2#)))
                          (PROG1
                              (IF (Y-OR-N-P "What is the answer for ~A?" N)
                                  `(,Q ,N ,M)
                                  `(,Q ,M ,N))
                            (FORMAT S "Thanks~%"))))
                    (DESTRUCTURING-BIND
                        (Q Y N)
                        M
                      (IF (Y-OR-N-P Q)
                          `(,Q ,(U Y) ,N)
                          `(,Q ,Y ,(U N)))))))
       (WRITE (LIST 'LET (LIST `(X ',(U X))) '#1#) :CIRCLE T)
       NIL))

Explanations

A decision tree can be:

  • a string, like "a pangolin", which represents a leaf.
  • a list of three elements: (question if-true if-false) where question is a closed yes/no question, as a string, and if-true and if-false are the two possible subtrees associated with the question.

The U function walks and returns a possibly modified tree. Each question are asked in turn, starting from the root until reaching a leaf, while interacting with the user.

  • The returned value for an intermediate node (Q Y N) is (Q (U Y) N) (resp. (Q Y (U N))) if the answer to question Q is yes (resp. no).

  • The returned value for a leaf is either the leaf itself, if the program correctly guessed the answer, or a refined tree where the leaf is replaced by a question and two possible outcomes, according to the values taken from the user.

This part was rather straightforward. In order to print the source code, we use reader variables to build self-referential code. By setting *PRINT-CIRCLE* to true, we avoid infinite recursion during pretty-printing. The trick when using WRITE with :print-circle T is that the function might also returns the value to the REPL, depending on whether write is the last form, and so, if the REPL doesn't handle circular structures, like it is defined by the standard default value of *PRINT-CIRCLE*, there will be an infinite recursion. We only need to make sure the circular structure is not returned to the REPL, that's why there is a NIL in the last position of the LET. This approach greatly reduces the problem.

\$\endgroup\$
  • \$\begingroup\$ Looks good! The (y or n) is not required, but I am tempted to permit it as it is an improvement. \$\endgroup\$ – abligh Sep 7 '15 at 17:12
  • \$\begingroup\$ @abligh Thanks. About y/n, that would be nice, it helps and IMHO this is not really in contradiction with #3 which is about avoiding shortening the prompts. \$\endgroup\$ – coredump Sep 7 '15 at 18:29
9
\$\begingroup\$

Python 2.7.6, 820 728 bytes

(Might work on different versions but I'm not sure)

def r(O,R):
 import sys,marshal as m;w=sys.stderr.write;i=sys.stdin.readline;t=O;w("OK, please think of something\n");u=[]
 def y(s):w(s);return i()[0]=='y'
 while t:
  if type(t)==str:
   if y("Is it %s?"%t):w("Good. That was soooo easy.")
   else:w("Oh. Well you win then -- What were you thinking of?");I=i().strip();w("Please give me a question about %s, so I can tell the difference between %s and %s"%(I,t,I));q=i().strip();a=y("What is the answer for %s?"%q);w("Thanks");p=[q,t];p.insert(a+1,I);z=locals();exec"O"+"".join(["[%s]"%j for j in u])+"=p"in z,z;O=z["O"]
   t=0
  else:u+=[y(t[0])+1];t=t[u[-1]]
 print"import marshal as m;c=%r;d=lambda:0;d.__code__=m.loads(c);d(%r,d)"%(m.dumps(R.__code__),O)
r('a pangolin',r)

Well, it's not not as short as the Common Lisp answer, but here is some code!

\$\endgroup\$
4
\$\begingroup\$

Python 3, 544 bytes

q="""
d=['a pangolin'];i=input;p=print
p("OK, Please think of something")
while len(d)!=1:
    d=d[1+(i(d[0])[0]=="n")]
x=i("Is it "+d[0]+"?")
if x[0]=="n":
    m=i("Oh. Well you win then -- What were you thinking of?")
    n=[i("Please give me a question about "+m+", so I can tell the difference between "+d[0]+" and "+m),*[[d[0]],[m]][::(i("What is the answer for "+m+"?")[0]=="n")*2-1]]
    p("Thanks")
    q=repr(n).join(q.split(repr(d)))
else:
    p("Good. That was soooo easy.")
q='q=""'+'"'+q+'""'+'"'+chr(10)+'exec(q)'
p(q)
"""
exec(q)

Try it Online!

The questions/answers/responses are stored in an array, where if the array stores three items (e.g. ['Does it eat ants',['a pangolin'],['a dog']]) then it gets an answer to the question and repeats with just the contents of either the second or third item, depending on the answer. When it gets to an array with only one item, it asks the question, and since it has its entire source codeas a string it is able to use the split-join method to insert the extension to the array in order to add the new branch.

I originally wrote this not realising the quine requirement, so rereading the question and having to find a way that I could both execute code and use it as a string was difficult, but I eventually stumbled upon the idea of the nice expandable quine format:

q="""
print("Some actual stuff")
q='q=""'+'"'+q+'""'+'"'+chr(10)+'exec()'
print(q)
"""
exec(q)
\$\endgroup\$
1
\$\begingroup\$

Python 3, 497 bytes

t=["a pangolin"];c='''p=print;i=input;a=lambda q:i(q)[0]in"Yy"
def q(t):
  if len(t)<2:
    g=t[0]
    if a(f"Is it {g}?"):p("Good. That was soooo easy.")
    else:s=i("Oh. Well you win then -- What were you thinking of?");n=i(f"Please give me a question about {s}, so I can tell the difference between {s} and {g}.");t[0]=n;t+=[[g],[s]][::1-2*a(f"What is the answer for {s}?")];p("Thanks")
  else:q(t[2-a(t[0])])
p("Ok, please think of something");q(t);p(f"t={t};c=''{c!r}'';exec(c)")''';exec(c)

Quite similar to Harmless' answer for tree representation. It recursively asks the next question, while going deeper into the list, until there is only one response.

Ungolfed version (without quining)

tree = ['a pangolin']

def ask(question):
  answer = input(question + '\n')
  if answer.lower() in ['yes', 'no']:
    return answer.lower() == 'yes'
  else:
    print('Please answer "yes" or "no".')
    return ask(question)
    
def query(tree):
  if len(tree) == 1:
    guess = tree.pop()
    if ask(f'Is it {guess}?'):
      print('Good. That was soooo easy.')
      tree.append(guess)
    else:
      thing = input('Oh. Well you win then -- What were you thinking of?\n')
      new_question = input(f'Please give me a question about {thing}, so I can tell the difference between {thing} and {guess}.\n')
      answer = ask(f'What is the answer for {thing}?')
      print('Thanks')
      tree.append(new_question)
      if answer:
        tree.append([thing])
        tree.append([guess])
      else:
        tree.append([guess])
        tree.append([thing])
  else:
    if ask(tree[0]):
      query(tree[1])
    else:
      query(tree[2])
      
while True:
  input('Ok, please think of something\n')
  query(tree)
\$\endgroup\$

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.