Esse é um desafio do código-golfe, no qual você precisa criar um programa que atue como uma solução ou uma solução que se modifique para ilustrar o aprendizado de máquina.

fundo

Existe um programa básico de inteligência artificial chamado 'o jogo dos pangolins' descrito aqui . As idéias básicas são que o programa, quando executado pela primeira vez, pergunta:

OK, por favor, pense em algo

É um pangolim?

Você pode então responder:

sim

Nesse caso, diz:

Boa. Isso foi muuuuito fácil.

Ou, se não, diz:

Oh Bem, você venceu então - No que estava pensando?

Para o qual você pode dizer:

um cachorro

Para o que diria

Por favor, faça uma pergunta sobre um cachorro, para que eu possa dizer a diferença entre um cachorro e um pangolim

você pode responder

Come formigas?

Em seguida, perguntaria:

Qual é a resposta para um cachorro?

Para o qual você diria

não

E diria

obrigado

Da próxima vez que for executado, ele fará a pergunta acima e criará uma árvore binária de tais perguntas.

O desafio

Chega de plano de fundo. Esse desafio é escrever um programa de pangolins auto-modificável. As regras são as seguintes:

1. A saída do programa (como descrito acima) deve ser para STDERR. A resposta final sempre será "Bom. Isso foi muuuuito fácil". ou "obrigado". Depois disso, ele deve gerar a versão atual do programa ou uma nova versão do programa que incorpora a pergunta STDOUT. Nenhuma resposta escrita em um idioma que não suporte a escrita para STDOUTe / STDERRou leitura STDINserá válida.

2. Em outras palavras, no UNIX, você poderia invocar o programa assim:

exemplo:

$ mylanguage myprogram > myprogram.1
[dialog goes here]
$ mylanguage myprogram1 > myprogram.2
[dialog goes here]

3. O programa precisa usar exatamente os prompts especificados (porque encurtá-los não mostra nenhuma habilidade). Os prompts são (sem as aspas e onde% s é substituído) da seguinte maneira:

Lista:

"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"

4. Quando esperando respostas sim / não, seu programa deve aceitar you yesem qualquer caso, 'sim', e nou noem qualquer caso, para 'não'. O que você faz com entradas não conformes é com você. Por exemplo, você pode optar por receber qualquer resposta que comece com you Ycomo 'sim' e qualquer outra coisa como não.

5. Você pode assumir que os nomes dos itens fornecidos e as perguntas consistem apenas em letras ASCII, números, espaços, hífens, pontos de interrogação, vírgulas, pontos finais, dois pontos e ponto e vírgula, ou seja, eles correspondem ao regex seguinte ^[-?,.;: a-zA-Z]+$. Se você pode lidar com mais do que isso (especialmente os caracteres citados no idioma escolhido), pode ser convencido, mas não ganha pontos extras.

6. Seu programa não pode ler ou escrever qualquer arquivo (excluindo STDIN, STDOUTe STDERR), ou a partir da rede; especificamente, ele não pode ler nem escrever seu próprio código do disco. Seu estado deve ser salvo no próprio código do programa.

7. Quando o programa é executado e adivinha a resposta corretamente, ele deve funcionar exatamente como um quine, ou seja, deve escrever STDOUTexatamente no seu próprio código, inalterado.

8. Quando o programa é executado e adivinha a resposta incorretamente, ele deve codificar a nova pergunta fornecida e responder dentro de seu próprio código e gravá-la STDOUTem seu próprio código, para que seja capaz de distinguir entre sua suposição original e o novo objeto fornecido, em além de distinguir entre todos os objetos fornecidos anteriormente.

9. Você deve ser capaz de lidar com várias execuções seqüenciais do software para que ele aprenda sobre muitos objetos. Veja aqui exemplos de várias execuções.

10. As execuções de teste são fornecidas no link na cabeça (obviamente, cobrindo apenas as caixas de diálogo STDINe STDERR).

11. As brechas padrão são excluídas.

Lisp comum, 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)()))

Sessão de exemplo

Nomeie o script pango1.lispe execute da seguinte forma (usando 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

Outra rodada, adicionando o urso:

~$ 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

Adicionando uma preguiça (testamos o caso em que a resposta é "não"):

~$ 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

Testando o último arquivo:

~$ 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.

Observações

• Eu esqueci a impressão "Thanks", aqui está ela.
• Como você pode ver, as perguntas são seguidas (y or n), porque eu estou usando a y-or-n-pfunção existente . Posso atualizar a resposta para remover esta saída, se necessário.
• O Common Lisp possui um *QUERY-IO*fluxo bidirecional dedicado à interação do usuário, que é o que estou usando aqui. Saída padrão e interação com o usuário não mexem, o que segue IMHO o espírito da pergunta.
• Usar SAVE-LISP-AND-DIEseria uma abordagem melhor na prática.

Saída gerada

Aqui está o último script gerado:

(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))

Explicações

Uma árvore de decisão pode ser:

• uma corda, como "a pangolin", que representa uma folha.
• uma lista de três elementos: (question if-true if-false)onde questionestá uma pergunta sim / não fechada , como uma sequência, e if-truee if-falsesão as duas subárvores possíveis associadas à pergunta.

A Ufunção caminha e retorna uma árvore possivelmente modificada. Cada pergunta é feita por sua vez, começando da raiz até chegar a uma folha, enquanto interage com o usuário.

• O valor retornado para um nó intermediário (Q Y N)é (Q (U Y) N)(resp. (Q Y (U N))) Se a resposta à pergunta Qfor sim (resp. Não ).

• O valor retornado para uma folha é a própria folha, se o programa adivinhou corretamente a resposta, ou uma árvore refinada em que a folha é substituída por uma pergunta e dois resultados possíveis, de acordo com os valores obtidos pelo usuário.

Esta parte foi bastante direta. Para imprimir o código-fonte, usamos variáveis ​​de leitor para criar código auto-referencial.Ao definir *PRINT-CIRCLE*como true, evitamos recursões infinitas durante a impressão bonita.O truque ao usar WRITEwith :print-circle Té que a função também pode retornar o valor para o REPL, dependendo da forma de gravação ser a última forma e, portanto, se o REPL não manipular estruturas circulares, como é definido pelo valor padrão padrão de *PRINT-CIRCLE*, haverá uma recursão infinita. Precisamos apenas garantir que a estrutura circular não seja retornada ao REPL, é por isso que existe um NIL na última posição do LET. Essa abordagem reduz bastante o problema.

Python 2.7.6, 820 728 bytes

(Pode funcionar em versões diferentes, mas não tenho certeza)

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)

Bem, não é tão curto quanto a resposta do Common Lisp, mas aqui está um código!

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)

Experimente Online!

As perguntas / respostas / respostas são armazenadas em uma matriz, onde se a matriz armazena três itens (por exemplo ['Does it eat ants',['a pangolin'],['a dog']]), ela obtém uma resposta para a pergunta e se repete apenas com o conteúdo do segundo ou terceiro item, dependendo da resposta. Quando chega a uma matriz com apenas um item, ele faz a pergunta e, como possui toda a sua origem como código, é capaz de usar o método de junção dividida para inserir a extensão na matriz e adicionar a nova ramificação. .

Originalmente, eu escrevi isso sem perceber o requisito de quine, então reler a pergunta e ter que encontrar uma maneira de executar código e usá-lo como uma string eram difíceis, mas acabei encontrando a ideia do bom formato expansível de quine:

q="""
print("Some actual stuff")
q='q=""'+'"'+q+'""'+'"'+chr(10)+'exec()'
print(q)
"""
exec(q)

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)

Muito semelhante à resposta do Harmless para a representação em árvore. Ele recursivamente faz a próxima pergunta, aprofundando a lista, até que haja apenas uma resposta.

Versão ungolfed (sem citar)

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)