Descifrar los símbolos matemáticos.

13

Si ha leído el libro Contacto de Carl Sagan, este desafío puede parecerle familiar.


Dada una entrada de un conjunto de ecuaciones matemáticas que consisten en un número, un operador desconocido, otro número y un resultado, deduce qué operadores representan la suma, resta, multiplicación o división.

Cada ecuación de entrada siempre consistirá en

  • un entero no negativo
  • una de las cartas A, B, C, oD
  • otro entero no negativo
  • el personaje =
  • un entero final no negativo

concatenados juntos Por ejemplo, una posible entrada es 1A2=3, a partir de la cual puede deducir que Arepresenta la suma. Cada uno de los enteros satisfará 0 ≤ x ≤ 1,000.

Sin embargo, no siempre es tan simple como eso. Es posible que haya ambigüedad entre:

  • 5A0=5: suma resta
  • 1A1=1: multiplicación / división
  • 0A5=0: multiplicación / división
  • 2A2=4: suma / multiplicación
  • 4A2=2: resta / división
  • 0A0=0: suma / resta / multiplicación

y así. El desafío es utilizar esta capacidad para reducir las opciones, combinadas con el proceso de eliminación, para determinar qué operador representa cada letra. (Siempre habrá al menos una ecuación de entrada, y siempre será posible hacer coincidir inequívocamente y de manera única cada letra utilizada en la entrada con un solo operador).

Por ejemplo, supongamos que la entrada es las siguientes ecuaciones:

  • 0A0=0: esto reduce A a la suma, resta o multiplicación (no se puede dividir por 0).
  • 10B0=10: B tiene que ser suma o resta.
  • 5C5=10: C es obviamente la suma, lo que hace que la resta B, que hace la multiplicación A.

Por lo tanto, la salida para estas ecuaciones de entrada debe coincidir Acon *, B con -y Ccon +.

La entrada puede darse como una sola cadena delimitada por espacios en blanco / coma o una matriz de cadenas, cada una representando una ecuación. La salida puede ser una sola cadena ( "A*B-C+"), una matriz ( ["A*", "B-", "C+"]) o una matriz 2D tipo diccionario / diccionario ( {"A": "*", ...}o [["A", "*"], ...]).

Puede suponer que un número nunca se dividirá por otro número por el que no sea divisible (por lo tanto, no debe preocuparse por si la división debe ser de punto flotante o truncada).

Como se trata de , gana el código más corto en bytes.

Casos de prueba:

In                       Out
-------------------------------
0A0=0 10B0=10 5C5=10     A*B-C+
100D100=10000            D*
4A2=2 4B2=2 0A0=0        A-B/
15A0=15 4B2=2 2C2=0      A+B/C-
1A1=1 0A0=0              A*
0A0=0 2A2=4 5B0=5 2B2=4  A*B+
2A2=4 0C0=0 5B0=5 5A0=5  A+B-C*
0A1000=0 4A2=2           A/
Pomo de la puerta
fuente
1
¿Estamos haciendo división entera (truncada)?
Martin Ender
@ MartinBüttner Puede suponer que nunca habrá división por un número que no resulte en un número entero. (Editado en la pregunta.)
Pomo de la puerta
¿Podemos sacar como diccionario?
lirtosiast
@ThomasKwa Claro, un diccionario también es una salida aceptable.
Pomo de la puerta
La mayoría de los ejemplos son inconsistentes con " siempre será posible identificar inequívocamente y de manera única qué letra representa a qué operador ", aunque son consistentes con " siempre será posible identificar inequívocamente qué operador está representado por cada letra utilizada en el entrada ".
Peter Taylor

Respuestas:

9

MATL , 53 bytes

j61tthYX'+-*/'X{Y@!"t'ABCD'!XKX{@YXU?K@Y}hwxKGm1L3$).

Utiliza la versión actual (10.1.0)

EDITAR (12 de junio de 2016): para adaptarse a los cambios en el idioma, reemplazar Y}por gy 1L3$)por Y). El siguiente enlace incorpora esas modificaciones

Pruébalo en línea!

Explicación

Esto prueba todas las permutaciones posibles de los cuatro operadores en un bucle hasta que una permutación hace que todas las ecuaciones sean verdaderas.

Para probar si las ecuaciones son verdaderas, se aplica una expresión regular para reemplazar las cuatro letras por los operadores (en el orden dictado por la permutación actual), y la cadena se convierte en números (evaluado). Esto proporciona una matriz con tantos números como ecuaciones, en la que se convierten las 1ecuaciones verdaderas y las ecuaciones falsas 0. Si este vector solo contiene 1valores, hemos terminado.

La solución encontrada asigna operadores a las cuatro letras, pero no todas aparecen necesariamente en la entrada. Entonces, se realiza una prueba final para descartar las letras no utilizadas (y sus operadores coincidentes).

j            % input data string
61           % '=' (ASCII)
tth          % duplicate twice and concat: '==' (ASCII)
YX           % regexprep to change '=' into '==' in input string
'+-*/'       % push string
X{           % transform into cell array {'+','-','*','/'}
Y@!          % all permutations, each in a column
"            % "for" loop. Iterate columns (that is, permutations)
  t          %   duplicate data string containing '=='
  'ABCD'!XK  %   create column array ['A';'B';'C';'D'] and copy to clipboard K
  X{         %   transform into column cell array {'A';'B';'C';'D'} 
  @          %   push column cell array with current permutation of operator symbols
  YX         %   regexprep. Replaces 'A',...,'D' with current permutation of operators
  U          %   convert to numbers, i.e. evaluate string
  ?          %   if all numbers are 1 (truthy result): found it! But before breaking...
    K        %     push column array ['A';'B';'C';'D']
    @Y}      %     push column array with current permutation of operator symbols
    h        %     concatenate horizontally into 4x2 char array
    wx       %     delete original input so it won't be displayed
    K        %     push ['A';'B';'C';'D']
    G        %     push input string
    m        %     logical index that tells which of 'A',...,'D' were in input string
    1L3$)    %     apply that index to select rows of the 4x2 char array
    .        %     we can now break "for" loop
             %   implicitly end "if"
             % implicitly end "for"
             % implicitly display stack contents
Luis Mendo
fuente
6

Python, 278 caracteres

Mi primera respuesta en el código de golf ...

Es solo una función que implementa un algoritmo de fuerza bruta, lo llama pasar como argumento la cadena de ecuaciones.

from itertools import *
def f(s):
    l=list("ABCD")
    for p in permutations("+-*/"):
        t=s
        for v,w in zip(l+["="," "],list(p)+["=="," and "]):
            t=t.replace(v, w)
        try:
            o=""
            if eval(t):
                for c,r in zip(l,p):
                    if c in s:
                        o+=c+r
                return o
        except:
            pass
Beto
fuente
No estoy seguro de si funciona, pero se puede sustituir ["A","B","C","D"]con list("ABCD")?
Adnan
Lo que sugirió @Adnan sí funciona. También puede eliminar los espacios alrededor =en la definición de l.
Alex A.
@Adnan y Alex A. gracias, edité el código.
Bob
Aquí hay 257 bytes para el mismo enfoque, más un entorno de prueba en línea.
Alex A.
Hicimos algunos cambios: repl.it/BfuU . Puede cortar muchos bytes más eligiendo un formato de salida diferente. Esta solución solo funciona en python 3 por cierto ( 4A2=2 4B3=1).
Nabb
4

JavaScript (ES6), 213208 bytes

f=(l,s="+-*/",p="",r)=>s?[...s].map(o=>r=f(l,s[g="replace"](o,""),p+o)||r)&&r:l.split` `.every(x=>(q=x.split`=`)[1]==eval(q[0][g](/[A-D]/g,m=>p[(a="ABCD").search(m)])))&&a[g](/./g,(c,i)=>l.match(c)?c+p[i]:"")

Explicación

La entrada y la salida son cadenas.

Define una función fque también funciona como una función recursiva para generar todas las permutaciones de los operadores y prueba permutaciones completas con las ecuaciones de entrada usando eval.

f=(
  l,                          // l = input expression string
  s="+-*/",                   // s = remaining operators
  p="",                       // p = current permutation of operators
  r                           // r is here so it is defined locally
)=>
  s?                          // if there are remaining operators
    [...s].map(o=>            // add each operator o
      r=f(
        l,
        s[g="replace"](o,""), // remove it from the list of remaining operators
        p+o                   // add it to the permutation
      )
        ||r                   // r = the output of any permutation (if it has output)
    )
    &&r                       // return r
  :                           // else if there are no remaining operators
    l.split` `.every(x=>      // for each expression
      (q=x.split`=`)          // q = [ equation, result ]
      [1]==eval(              // if the results is equal to the eval result

        // Replace each letter with the current permutation
        q[0][g](/[A-D]/g,m=>p[(a="ABCD").search(m)])
      )
    )

    // If all results matched, add permutation symbols to present characters and return
    &&a[g](/./g,(c,i)=>l.match(c)?c+p[i]:"")

Prueba

La prueba no utiliza argumentos predeterminados para la compatibilidad del navegador.

usuario81655
fuente