Escribir una palabra para resolver ecuaciones [duplicar]

17

Introducción

Considere el siguiente ejemplo:

  CODE
+ GOLF
——————
 GREAT

Esta es una ecuación en la que cada letra representa un dígito decimal y las palabras representan números naturales (letras similares representan dígitos similares y letras diferentes representan dígitos diferentes). La tarea es hacer coincidir cada letra con su valor de dígito para que la ecuación sea correcta. Una solución para la ecuación anterior es:

  9265
+ 1278
——————
 10543

Tu tarea

Su tarea es escribir un programa o una función que pueda resolver tales ecuaciones como se ve arriba.

Entrada

La entrada es una cadena en el siguiente formato:

[A-Z]+\+[A-Z]+=[A-Z]+

Ejemplo:

  1. CODE+GOLF=GREAT
  2. AA+BB=CC

Se omiten los espacios y solo se utilizarán letras entre mayúscula A y Z (sin letras especiales o minúsculas).

Esta cadena se puede leer desde la entrada estándar, desde un archivo o como un parámetro de función.

Salida

Tiene las siguientes dos opciones para el formato de salida:

  1. la ecuación original con los dígitos sustituidos
  2. lista de las letras y sus valores

Si hay varias soluciones, se debe devolver cualquiera (pero solo una) de ellas. Si no hay soluciones, el programa debería devolver una cadena vacía o nula. La salida se puede devolver como una cadena, se puede escribir en la salida estándar o en un archivo.

Ejemplo:

  1. 9265+1278=10543
  2. A=1 B=2 C=3 (puedes usar cualquier delimitador)

Reglas

  1. Para facilitar las cosas, los números se aceptan para comenzar con 0, pero puede manejar números con 0 a la izquierda como soluciones no válidas, depende de usted
  2. Letras similares representan dígitos similares y letras diferentes representan dígitos diferentes
  3. Puede usar cualquier idioma y la biblioteca estándar del idioma elegido (sin bibliotecas externas)
  4. No puede conectarse a ningún recurso en Internet (¿por qué lo haría de todos modos?)
  5. Esta es una tarea de golf de código, el código más corto gana. Los caracteres de espacio en blanco consecutivos cuentan como un solo carácter. (Entonces, cualquier programa escrito en espacios en blanco gana automáticamente)

Tengo una solución algo hacking usando 179 caracteres. Si algo no está claro, por favor pregúntame en los comentarios.

David Frank
fuente
Creo que la respuesta óptima es "todo es 0". Es posible que desee prohibir específicamente eso.
undergroundmonorail
1
¿Qué quieres decir con que todo es 0? Las diferentes letras tienen que denotar diferentes números.
David Frank
Perdido eso, no importa :)
undergroundmonorail
If there are no solutions, the program should return an empty string or null.Los bucles infinitos aún no generan nada ... ¿puedo?
Titus
1
Todas las respuestas ganadoras a este desafío se reducen efectivamente a explotar la regla de puntuación de espacios en blanco, por lo que votar de cerca como un duplicado.
pppery

Respuestas:

11

Python - 48 caracteres

exec("".join(map(chr,map(len,'                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             '.split("    ")))))

Abusar de la regla del espacio en blanco.

Primero, convertí cada personaje en la respuesta de CesiumLifeJacket a su valor ASCII (podría haber escrito el mío pero soy flojo, y de todos modos no habría afectado el puntaje final). La cadena larga en mi solución es un espacio para cada uno de esos valores ASCII, y las pestañas que los separan. Dividir en pestañas, encontrar las longitudes, convertir de nuevo a caracteres y ejecutar.

SE convierte las pestañas en 4 espacios cada una, por lo que el copiado no funcionará. Solo tendrás que creerme :)

metro subterráneo
fuente
1
¿Puede proporcionar un enlace a ideone o un volcado hexadecimal de su código?
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
1
Además: exec es una palabra clave, puede guardar 2 caracteres eliminando el primer y último paréntesis
ɐɔıʇǝɥʇuʎs
4

Ruby 2.0, 122 caracteres

Fuerza bruta barajando + eval! Esto aún no cumple los criterios de devolver una cadena nula / vacía cuando no hay solución; simplemente gira infinitamente. Si no puede encontrar un resultado después de ~ 300 millones de iteraciones, devolverá cero. ¿Suficientemente cerca?

f=->s{d=*0..9
d.shuffle!&&$.+=1until$.>9**9||z=eval((r=$_.tr(s.scan(/\w/).uniq*'',d*'')).gsub(/\b0/,'').sub ?=,'==')
z&&r}

Encuentra todas las letras únicas en la entrada, luego baraja repetidamente los dígitos 0-9 e intenta unirlas con las letras hasta que encuentra una configuración que funcione.

El código se presenta como una función llamada fque devuelve una cadena con los números sustituidos, como en la Opción de salida 1 anterior. Ejemplo de uso:

puts f["AA+BB=CC"]
 #=> 22+44=66
puts f["CODE+GOLF=GREAT"]
 #=> 8673+0642=09315

El tiempo de ejecución para el CODE+GOLF=GREATejemplo en mi máquina varía de instantáneo a aproximadamente 6 segundos, ¡depende de la suerte que tenga con los barajaduras!

Estoy particularmente descontento con el gsub(/\b0/,'')bit para eliminar los ceros a la izquierda, pero fue lo único que pude pensar para evitar evalinterpretar los números como entradas octales.

( BONIFICACIÓN : ¡Debido a que usa eval, funciona para expresiones arbitrarias de Ruby y no solo para la suma!)

Paul Prestidge
fuente
Tuve la misma idea cuando leí esto, pero obtuve ~ 170 caracteres de código, muy bien hecho. 0..9 son diez dígitos, entonces ¿no debería ser el límite de 10 ** 10? Puede usar la permutación Array # para recorrer todas las asignaciones posibles, pero eso puede hacer que el código sea más largo.
blutorange
@blutorange Acabo de elegir 9 ** 9 porque era un gran número que podías escribir con pocos caracteres. ¡Creo que debería ser más que suficiente para cualquier caso de prueba razonable! No he probado una versión basada en permutation, pero como dices, me preocupaba principalmente la longitud del código.
Paul Prestidge
4

LiveScript (179 caracteres)

Tiene un tiempo de ejecución determinista y relativamente rápido y también funciona con otros operadores (+, -, *).

f=(s)->                     # define function that takes parameter s
  c=s.replace /[^A-Z]/g ''  # remove all the non-letters
  if c                      # if any letters remain
    for i from 0 to 9       # loop from 0 to 9
       if s.indexOf(i)<0&&a=f s.split(c.0).join i  # if i is not present in the number, replace the first letter with i and call the function recursively
         return a           # if there is a solution, return it
  else                      # if there are no letters left
    if eval s.replace(/(^|\D)0+(\d)/g,'$1$2').replace \= \==  # if the expression is correct (we need to remove leading 0, because javascript interprets numbers with leading 0 as octal)
       return s  # return solution



f("CODE+GOLF=GREAT")
David Frank
fuente
2

Python, 256 213 caracteres

Horrible tiempo de ejecución, intentará mejorar aún más:

q='='
e=input()
v=set(e)-set([q,'+'])
for x in __import__('itertools').permutations(range(10),len(v)):
    t=e
    for l,n in zip(v,x):t=t.replace(l,str(n))
    try: 
        if eval(t.replace(q,q*2)):print(t);break
    except:pass
CesioVida Chaqueta
fuente
2

JavaScript 138

for(s=prompt(p='1');eval(p.replace('=','!='));)for(p=s,i=64;i++<90;)p=p.replace(new RegExp(String.fromCharCode(i),'g'),10*Math.random()|0)

Fuerza bruta al azar.
Puede tomar un tiempo (mi mejor tiro CODE+GOLF=GREATes de 3 segundos, mis peores 3 minutos).
Pruébalo con una expresión simple comoA+B=C

Michael M.
fuente
2

Haskell, 222

import Data.List
z=(\(b,(_:c))->b:z c).span Data.Char.isUpper
j(Just g)=g
main=interact$(\d@[a,b,c]->show$take 1[e|e<-map(zip$nub$d>>=id)$permutations['0'..'9'],(\f->f a+f b==(f c::Int))(read.map(j.(`lookup`e)))]).take 3.z

Fuerza bruta. Intenta todas las coincidencias posibles hasta que encuentre una, o después de que haya terminado de probarlas todas. Estiré las reglas de salida: imprime algo parecido [[('C','3'),('O','8'),('D','6'),('E','7'),('G','0'),('L','5'),('F','2'),('R','4'),('A','1'),('T','9')]]a la solución y, si no existe, imprime []. Avísame si necesito cambiar esto.

YawarRaza7349
fuente
Creo que esta salida es aceptable.
David Frank
2

CJam - 17

"





























































































































































































































































































































    ""  
"f#3b127b:c~

Total de 975 caracteres, pero 960 de ellos son espacios en blanco en 2 secuencias, por lo que esos cuentan como 2 caracteres, y junto con los otros 15, obtenemos 17.
975 puede parecer mucho, pero tenga en cuenta que la solución python de undergroundmonorail tiene 18862 caracteres, ellos solo estás en una sola línea :)

Puede ejecutarlo en http://cjam.aditsu.net/ para palabras cortas, pero probablemente debería usar el intérprete de java para las más largas. Con Java en mi computadora portátil, se SEND+MORE=MONEYejecuta en 30-40 segundos y CODE+GOLF=GREATen casi 3 minutos. No acepta números que comienzan con 0 (porque eso no es genial).

Aquí hay un programa que genera el programa anterior (también ayuda si StackExchange no muestra el espacio en blanco correctamente):

"{L__&=}:U;
{L!!{L))_9>{;:L;I}{+:L;}?}*}:I;
{{U!_{I}*}g}:M;
{L,N<L,g&}:K;
{I{K{L0+:L;}*MK}g}:G;
{{C#L=}%si}:R;
{XRYR+ZR=PRAb0#0<&}:F;
l'+/~'=/~:Z;:Y;:X;
[X0=Y0=Z0=]:P;
XYZ++_&:C,:NB<{0a:L;{F0{GL}?}g}*
L{XR'+YR'=ZR}{L}?"
127b3b[32 9 A]:cf='"\'"_32c9cAc"\"f#3b127b:c~"

Las primeras 11 líneas contienen el programa original (no realmente golfizado) en una cadena, y la última línea realiza la conversión y agrega la parte de decodificación.

aditsu
fuente
0

Powershell, 137 bytes

puerto de LiveScript

$f={param($s)if($c=$s-replace'[^A-Z]'){0..9|?{$s-notmatch$_}|%{&$f ($s-replace$c[0],$_)}|Select -f 1}elseif($s-replace'=','-eq'|iex){$s}}

Script de prueba sin golf:

$f={

param($s)                           # parameter string
$c=$s-replace'[^A-Z]'               # remove all the non-letters
if($c){                             # if any letters remain
    0..9|?{                         # loop from 0 to 9
        $s-notmatch$_               # if $s is not contains current number
    }|%{
        &$f ($s-replace$c[0],$_)    # replace the first letter with current number and call the function recursively
    }|Select -f 1                   # seelct first non-null value (break if found)
}
elseif($s-replace'=','-eq'|iex){    # else if evaluated value if the expression is $true
    $s                              # return $s as solution
}

}

&$f "AA+BB=CC"
&$f "A+AB=A"            # empty because it has no solution
&$f "CODE+GOLF=GREAT"

Salida:

11+22=33
2846+0851=03697
mazzy
fuente
0

PHP, 118 113 bytes

for(;;)eval(strtr($argn,"=".$w=substr(count_chars($argn,3),2),"-".$n=str_shuffle(1234567890))."||die('$w
$n');");

imprime dígitos debajo de las letras y sale del programa; se repite infinitamente si no se puede resolver. Ejecutar como tubería con -nr.

Descompostura

for(;;)
    eval(                               # 6. evaluate
        strtr($argn,                    # 4. translate letters to digits, "=" to "-"
            "=".$w=substr(              # 2. remove non-letters
                count_chars($argn,3)    # 1. get characters used in the argument
                ,2),
            "-".$n=str_shuffle(1234567890)  # 3. shuffle digits
        )."||die('$w\n$n');"            # 5. if falsy (`A+B-C==0`), print translation and exit
    )
;
Tito
fuente
0

PHP, 145 bytes

function f($s){for(;$i<10*preg_match("/[A-Z]/",$s,$m);)strpos(_.$s,++$i+47)||f(strtr($s,$m[0],$i-1));$i||eval(strtr($s,"=","-")."||die('$s');");}

función recursiva, imprime la ecuación resuelta y sale del programa; vuelve NULLcuando no tiene solución.

Pruébalo en línea

Descompostura

function f($s)
{
    for(;
        $i<10                   # loop $i from 0 to 9
        *preg_match("/[A-Z]/",$s,$m)    # find a letter; if not found: $i<10*0 == falsy
        ;
    )
        strpos(_.$s,++$i+47)            # find $i in string
        ||f(strtr($s,$m[0],$i-1));      # if not found, replace letter with $i, recurse
    $i||                        # no letter found ($i is unset):
        eval(                   # evaluate:
            strtr($s,"=","-")       # replace "=" with "-"
            ."||die('$s');"         # if falsy (A+B-C==0), print equation, exit program
        );
    # else implicitly return NULL
}
Tito
fuente