Golf Me An OOP!

26

Golf Me An OOP!

Dos componentes importantes de la programación orientada a objetos son la herencia y la composición. Juntos, permiten crear jerarquías de clase simples pero poderosas para resolver problemas. Su tarea es analizar una serie de declaraciones sobre una jerarquía de clases y responder preguntas sobre la jerarquía.

Entrada

Una serie de declaraciones y preguntas sobre una jerarquía de clases, leídas de un archivo o entrada estándar, lo que sea mejor para su idioma. Si usa la opción de archivo, el nombre de archivo se pasará como primer argumento a su código (argumento de función o argumento de línea de comando, lo que elija). El formato es el siguiente:

<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

La entrada siempre será declaraciones, luego preguntas. Todos los nombres de clase comenzarán con una letra mayúscula en inglés ( A-Z), y todos los nombres de miembros comenzarán con una letra minúscula en inglés ( a-z). Todos los nombres distinguen entre mayúsculas y minúsculas, ABC123no es la misma clase que Abc123.

No habrá ninguna herencia cíclica; si Bhereda de A, Ano heredará de Bninguno de Blos hijos de ninguno .

Solo los nombres de clase formarán parte de una jerarquía: declaraciones como foo is a bar.odocument has a name. no ocurrirán.

Salida

Una serie de valores verdaderos o falsos, como respuestas a las consultas, escritos en la salida estándar o como el valor de retorno de su función. Si no tiene suficiente información para responder una pregunta (por ejemplo, preguntas que involucran nombres que no ha visto en las declaraciones), responda con un valor falso.

Casos de prueba

Caso 1:

Entrada:

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?

Salida:

True
True
False

Caso 2:

Entrada:

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?

Salida:

True
True
False
False
True

Reglas

  • Puedes responder con una función o un programa
  • Las lagunas estándar están prohibidas
  • Este es el código de golf , por lo que la respuesta correcta más corta en bytes gana
  • La respuesta ganadora se elegirá en una semana.

¡Buena suerte, y que la OOP esté contigo!

Tabla de clasificación

El Fragmento de pila al final de esta publicación genera la tabla de clasificación a partir de las respuestas a) como una lista de la solución más corta por idioma yb) como una tabla de clasificación general.

Para asegurarse de que su respuesta se muestre, comience con un título, utilizando la siguiente plantilla de Markdown:

## Language Name, N bytes

¿Dónde Nestá el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:

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

Si desea incluir varios números en su encabezado (por ejemplo, porque su puntaje es la suma de dos archivos o desea enumerar las penalizaciones de la bandera del intérprete por separado), asegúrese de que el puntaje real sea el último número en el encabezado:

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

También puede hacer que el nombre del idioma sea un enlace que luego aparecerá en el fragmento:

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

Mostrar fragmento de código

code-golf decision-problem graph-theory natural-language Mego
fuente
¿Cómo es Does Criminal have a name?igual a True? ¿Todos los objetos tienen un nombre?
J Atkin
44
@JAtkin Criminal is a Person.Person has a name.
Reto Koradi
Ahh ... me había perdido eso.
J Atkin
¿Debo tomar todas las entradas de una vez o puedo hacerlo línea por línea como una consola interactiva? Si es el n. ° 2, ¿puedo generar un "truey \ falsey" incluso si la entrada es una declaración?
J Atkin
@JAtkin Todo a la vez o línea por línea, tú eliges. Si se trata de una declaración, no debería haber ningún resultado. Solo las preguntas obtienen respuestas.
Mego

Respuestas:

13

CJam, 59 bytes

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

Esto termina instantáneamente para ambos casos de prueba.

Imprime el segundo nombre de la pregunta o 1(ambos de verdad), o0 (falso).

Pruébelo en línea en el intérprete de CJam .

Idea

Debido a la distinción entre clases y miembros, el desafío se reduce a crear un preorden para el cual la entrada proporciona una definición parcial.

Definimos que x ≺ y iff x es una Y o X tiene una Y .

Para el primer caso de prueba, la entrada indica que B ≺ A , C ≺ B y A ≺ foo . Debido a la transitividad, también tenemos B ≺ foo , C ≺ A y A ≺ foo . Además, debido a la reflexividad, x ≺ x siempre es cierto.

Para una entrada dada, podemos extraer la definición parcial de ≺ de las declaraciones, aplicar la transitividad una cantidad suficiente de veces para completar la definición de ≺ y finalmente responder las preguntas.

Código

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#
Dennis
fuente
2
Esto es impresionante teniendo en cuenta que CJam no tiene clases: D
Beta Decay
Esto es hermoso.
Mego
@BetaDecay Las clases son esencialmente conjuntos anidados; Las clases se implementan en todos los idiomas. Digamos en el primer ejemplo. C:{B:{A:{foo:{}}}}
A̲̲
8

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)

Esta es la versión completa con comentarios.

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)

Salida para el caso de prueba # 1:

True
True
False

Caso # 2:

True
True
False
False
True

Eliminé los comandos de depuración para mayor claridad en el programa principal, pero si desea verlos solo mire el historial

J Atkin
fuente
En lugar de usar global fin h(z), use def h(z,f)y pase el global fin cuando lo llame. De hecho, no necesitas h(z)nada, solo coloca el cuerpo donde lo llamas. No necesita r=2, y puede print(r)prescindir de él if, ya que debe generar un valor falso para consultas falsas. Puede cambiar el nombre syna zafeitará varios bytes allí. No creo que necesites la []comprensión de tu lista en el primero any.
Mego
También lo usa euna vez, por lo que puede eliminar la definición y simplemente usarla [a,b,c,d]. En lugar de if s(i,g) is not Nonehacer if s(i,g), los re.Matchobjetos siempre se evalúan Truesi se encuentra una coincidencia. También puede soltar 2 bytes con f[x]+=f[y].
Mego
@Mego Wow, gracias por todos los consejos. Tendré que ponerlos más tarde.
J Atkin
Esta publicación probablemente te ayudará mucho
Mego
@Mego Muchas gracias, ahora se ha reducido a 396. Voy a publicar es en breve.
J Atkin
4

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

Dale la cuerda a o. No estoy seguro si hacer xe infijar v('extraer' y 'verificar') corta más que hacermap un infijo, o si ambos son posibles.

EDITAR: Explicación

Entonces, así (#)es como define un operador infijo, lo uso solo como una abreviatura para mapaplicar una función a cada elemento de una lista. Resolviendo este y el otro alias l, evitando el operador 'aplicación de función directa' $y agregando aún más paréntesis y espaciando cosas, y con nombres de funciones reales llegamos a:

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) es una lista de listas de palabras de cada línea en la cadena de entrada.

(=='?').last.last es un predicado que indica si la última letra en la última palabra de una línea es un signo de interrogación, es decir, si la línea es una pregunta.

break rompe la lista en una tupla de la primera parte sin preguntas (todas las declaraciones) y la parte de la primera pregunta (todas las preguntas).

maphacer ping extract nen estos saca de cada lista de palabras los elementos que realmente queremos, el nth (que en las declaraciones es la primera palabra - entonces n == 0, y en las preguntas es la segunda palabra - so n == 1) usando el !!operador y el último, del cual tiene que cortar la última letra (ya sea '.'o '?') usandoinit .

(Tenga en cuenta que ignoro por completo las mayúsculas, eso se debe a que ignoro completamente la distinción entre clases y miembros, los miembros son solo hojas de un árbol construido por la base de conocimiento (pero no todas las hojas representan miembros, también pueden ser clases sin subclases ni miembros) ), en el que cada nodo secundario representa una subclase o un miembro de lo que representa su nodo primario. Me acabo de dar cuenta de que ESTO ES UNA COSA INCORRECTA EN CASOS no cubiertos por OP. Editaré la solución pronto).

Ahora map (extract 0) knowledgeymap (extract 1) questions son listas de tuplas de nombres que representan una relación de subclase o miembro de la primera a la segunda.

Las tuplas map (extract 0) knowledgeson todas relaciones verdaderas, las de map (extract 1) questionsahora están asignadas a la verifyfunción, con el primer argumento establecido enmap (extract 0) knowledge .

(De ahora en adelante, dentro verify, knowledgehay un nombre de parámetro y se refiere a la extractlista de tuplas ya editada).

(Además, al leer verify, tenga en cuenta que si bien ||(después del salto de línea poco elegante para evitar el desplazamiento horizontal en SE) es una disyunción booleana normal entre el caso 'reflexivo' y el 'recursivo', lo orpliega sobre una lista, es decir, verifica si existe el elemento de la lista es verdadero)

Ahora, una relación es obviamente correcta si es reflexiva. Estrictamente hablando, no, a potatono tiene un potato(y ni siquiera es uno en el sentido de que 'es' se usa aquí, como en 'Un policía es un policía'), pero esa es solo la condición de terminación que cubre todas las relaciones después de caminando por el árbol (que a diferencia de los árboles reales significa 'hacia las hojas').

En todos los demás casos, tratamos de tomar una tupla de knowledge(después de filtereditar para asegurarnos de que 'vemos' solo pares con el mismo primer elemento que queremos verificar), y continuar desde donde apunta. La comprensión de la lista trata con todas las tuplas posibles para continuar y verifyvuelve a llamar en cada caso. Un callejón sin salida solo tendrá una lista vacía aquí y volverá en falsegeneral, y no influirá en la instancia por la verifyque fue llamado.

Leif Willerts
fuente
¿Podría agregar una breve explicación para las personas que no dominan Haskell?
J Atkin
¡Felizmente! Simplemente no lo hago para cada publicación hasta que lo solicite.
Leif Willerts
¡Vale gracias! (relleno)
J Atkin
Wow, esa es una explicación.
J Atkin
2
Acabo de terminar de leer la primera mitad Learn you a haskell for great good!y ¡ahora entiendo esto! (Esta respuesta es en realidad lo que me impulsó a aprender más sobre haskell y FP, ¡y es tan genial!)
J Atkin
4

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

Ingrese una cadena en blanco para salir.

Explicación

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)
    )
  )
usuario81655
fuente
¿Podrías usar string.split(" ");?
J Atkin
@JAtkin Solía .match(/\w+/g)eliminar la puntuación de las palabras.
user81655
Lo vi, pero no .split(" ")sería más corto o me estoy perdiendo algo. (No sé javascript)
J Atkin
@JAtkin Si lo usara .split, también tendría que usarlo .slice(0,-1)(dos veces) porque B is a A.haría Bheredar A.(con el .).
user81655
@JAtkin En realidad, me acabo de enterar de que split acepta expresiones regulares para poder usar .split(/\W/). ¡Gracias por hacerme buscar eso!
user81655